авторефераты диссертаций БЕСПЛАТНАЯ РОССИЙСКАЯ БИБЛИОТЕКА - WWW.DISLIB.RU

АВТОРЕФЕРАТЫ, ДИССЕРТАЦИИ, МОНОГРАФИИ, НАУЧНЫЕ СТАТЬИ, КНИГИ

 
<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Pages:   || 2 | 3 |

Управление множественным доступом в централизованных сетях передачи данных

-- [ Страница 1 ] --

На правах рукописи

КОБЛЯКОВ Владимир Андреевич

УПРАВЛЕНИЕ МНОЖЕСТВЕННЫМ ДОСТУПОМ В ЦЕНТРАЛИЗОВАННЫХ СЕТЯХ ПЕРЕДАЧИ ДАННЫХ

Специальность 05.13.01 – Системный анализ, управление и обработка

информации (в технике и технологиях)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени

кандидата технических наук

Санкт-Петербург – 2006

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Санкт-Петербургский государственный университет аэрокосмического приборостроения» (ГУАП).

Научный руководитель:

кандидат технических наук, доцент Тюрликов Андрей Михайлович

Официальные оппоненты: доктор технических наук,

профессор Крук Евгений Аврамович

кандидат технических наук, старший научный сотрудник Егоров Владимир Викторович

Ведущая организация – ОАО «Всероссийский Научно-исследовательский

институт радиоаппаратуры», г. Санкт-Петербург.

Защита состоится «_26__» ___декабря__ 2006 г. в __15___ часов на заседании диссертационного совета Д 212.233.02 при Государственном образовательном учреждении высшего профессионального образования «Санкт-Петербургский государственный университет аэрокосмического приборостроения» по адресу: 190000, Санкт-Петербург, ул.Б.Морская, 67, ГУАП.

С диссертацией можно ознакомиться в библиотеке ГУАП.

Автореферат разослан «_20_» __ноября_ 2006 г.

Ученый секретарь диссертационного совета доктор технических наук, профессор Осипов Л.А

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Активное развитие сетей передачи данных обуславливает необходимость исследования распространенного метода, используемого при передаче в этих сетях – множественного доступа абонентов к общему каналу связи. Множественный доступ предполагает разделение ресурсов канала между абонентами. Такое разделение каналов может быть частотным, временным или кодовым. Множественный доступ применяется и в проводных и в беспроводных сетях. Различают бесконфликтные и конфликтные методы доступа. Бесконфликтные методы множественного доступа используют в сотовых сетях стандартов AMPS, NAMPS, GSM (в режиме передачи речи) и других. Среди конфликтных методов доступа широкое распространение получил стандарт для локальных проводных сетей IEEE 802.3 (Ethernet) и стандарт для локальных беспроводных сетей – IEEE 802.11. В настоящее время идет активное внедрение стандарта для беспроводных MAN-сетей – IEEE 802.16. Данный стандарт, как и стандарт для проводных сетей IEEE 802.14, характеризуется наличием центральной станции. Особенностью стандартов IEEE 802.16 и IEEE 802.14 для сетей с центральной станцией (централизованные сети) является использование конкурентного интервала в процессе передачи. В конкурентном интервале абоненты передают запросы к центральной станции на предоставление канальных ресурсов. Абонент передает запрос случайным образом. Если передачи запросов от разных абонентов накладываются друг на друга, то возникает конфликт. В этом случае абоненты делают повторную передачу в соответствии с определенными правилами. И так далее. Ясно, что правила управления передачей в конкурентном интервале могут оказывать большое влияние на задержку передачи запроса. А это, в конечном счете, повлияет на время, которое затратит абонент на передачу данных. Диссертационная работа посвящена исследованию алгоритмов управления передачей в конкурентном интервале, которые принято называть алгоритмами случайного множественного доступа. Основная идея метода случайного множественного доступа (СМД) предложена в начале 70-х годов прошлого века и развита в работах Капетанакиса, Цыбакова, Михайлова, Месси и др. Специально для централизованных сетей в 1999 году Блонди и другими разработан алгоритм СМД, получивший название «FS-ALOHA».



Целью работы является разработка и анализ алгоритмов управления передачей запросов в конкурентном интервале, использующих случайный множественный доступ и обеспечивающих оперативную доставку запросов на центральную станцию.

Задачами диссертационного исследования являются:

1). Анализ функционирования известного алгоритма СМД с очередью для централизованных сетей.

2). Разработка алгоритмов СМД, обеспечивающих меньшую задержку при доставке запроса, чем ранее известные алгоритмы.

3). Анализ предложенных алгоритмов для различных видов входного потока.

Методы исследования. Для решения поставленных задач использованы методы теории вероятностей, теории случайных процессов, теории цепей Маркова, методы теории массового обслуживания и имитационное моделирование.

Основные положения, выносимые на защиту.

- метод расчета скорости и метод расчета распределения вероятностей для задержки запроса в алгоритме FS-ALOHA в канале с шумом;

- алгоритм управления передачей запроса в конкурентном интервале централизованных сетей – Multi FS-ALOHA;

- класс алгоритмов СМД для централизованных сетей. Метод расчета скорости и метод выбора оптимальных параметров для подкласса алгоритмов СМД.

Научная новизна.

1). Разработан метод расчета скорости алгоритма FS-ALOHA для канала с шумом, приводящим к появлению ложных конфликтов.

2). Вычислено критическое значение вероятности ложного конфликта, при котором скорость для оптимальных относительно скорости параметров алгоритма FS-ALOHA равна нулю.

3). Разработан метод расчета распределения вероятностей для задержки передачи запроса в алгоритме FS-ALOHA в канале с шумом.

4). Предложен класс алгоритмов СМД с очередью для централизованных сетей.

5). Разработан метод вычисления скорости алгоритма для подкласса алгоритмов СМД из предложенного класса. Разработан метод определения параметров алгоритма из данного подкласса, при которых его скорость максимальна. Разработан метод вычисления скорости при входном потоке со всплесками интенсивности для алгоритмов из подкласса.

Практическая ценность.

1). Предложена модификация алгоритма FS-ALOHA – алгоритм Multi FS-ALOHA. Модификация решила проблему уменьшения скорости в алгоритме FS-ALOHA при увеличении размера конкурентного интервала.

2). Предложены древовидные алгоритмы СМД для централизованных сетей. Данные алгоритмы обладают большей скоростью в сравнении с Multi FS-ALOHA, но при этом имеют и большею вычислительную сложность.

3). Получены численные значения характеристик алгоритма FS-ALOHA в канале с шумом. Численные характеристики рассчитаны для предложенных алгоритмов СМД при различных значениях их параметров.

4). Произведено сравнение алгоритма BEB, используемого в стандарте IEEE 802.16, с одним из древовидных алгоритмов СМД для централизованных сетей.

Внедрение и реализация результатов работы. Результаты диссертационной работы получены при выполнении госбюджетной научно-исследовательской работы (РК 01200501975), проведенной Санкт-Петербургским государственным университетом аэрокосмического приборостроения.

Полученные в диссертационной работе результаты используются в учебном процессе кафедры информационных систем ГУАП и кафедры АСОИУ ЛЭТИ.

Апробация работы. Основные результаты работы докладывались на пятой научной сессии аспирантов ГУАП (Санкт-Петербург, 12 – 18 апреля 2002г.), на шестой научной сессии аспирантов ГУАП (Санкт-Петербург, 14 – 18 апреля 2003г.), на седьмой научной сессии аспирантов ГУАП (Санкт-Петербург, 12 – 16 апреля 2004г.), на конференции «Информационные технологии в науке, образовании, искусстве» (Санкт-Петербург, 29 – 31 марта 2005г.), на восьмой научной сессии ГУАП (Санкт-Петербург, 11 – 15 апреля 2005г.), на политехническом симпозиуме «Молодые ученые – промышленности Северо-Западного региона» (декабрь 2005 г.), на научной сессии ГУАП, посвященной всемирному Дню авиации и космонавтики и 65-летию ГУАП (Санкт-Петербург, 10 – 14 апреля 2006г.), на международной научной конференции IEEE “ISCE 2006” (Санкт-Петербург, 28 июня – 1 июля 2006г.). Зарегистрированы программные разработки в отраслевом фонде алгоритмов и программ: регистрационный номер Гос. ФАП 50200501138, 2005 г.; регистрационный номер Гос. ФАП 50200501139, 2005 г.; регистрационный номер Гос. ФАП 50200501140, 2005 г.

Публикации. По теме диссертационной работы опубликовано 13 печатных работ.

Объем и структура работы. Диссертационная работа состоит из введения, 4 разделов, заключения, списка использованных источников и 4 приложений. Работа содержит 151 страницу машинописного текста, включая 40 рисунков, и 6 рисунков на 3 страницах. В списке используемой литературы 79 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность выбранной темы, определена цель и сформулированы решаемые в работе задачи. Перечислены новые научные результаты, полученные при выполнении работы, показаны практическая ценность и апробация работы, описаны внедрение и реализация результатов. Приведены основные положения, выносимые на защиту.

В разделе 1 описаны особенности подуровня управления доступом к среде в централизованных сетях передачи данных на примере стандарта IEEE 802.16. Приведена модель системы, используемая для анализа функционирования алгоритмов СМД. Определены основные характеристики алгоритмов. Произведен обзор используемых для централизованных сетей алгоритмов СМД, а также древовидных алгоритмов разрешения конфликтов. Получены оценки характеристик алгоритма BEB в канале с шумом и в канале со всплесками интенсивности входного потока.

Структура централизованной системы предполагает разделение общего канала связи между абонентскими станциями (AC) и центральной станцией (ЦС) на два подканала: восходящий канал и нисходящий канал. Восходящий канал множественного доступа служит для передачи данных от абонентских станций к центральной станции. AC «не слышат» друг друга. Коммуникация между ними осуществляется посредством ЦС. Нисходящий канал предназначен для передачи данных от ЦС к AC. Передача происходит в широковещательном режиме. Поэтому ее «слышат» все AC.

Организация передачи в централизованной системе происходит путем разделения времени передачи на кадры, имеющие определенную структуру (рис. 1). AC передают данные с помощью пакетов, которые кроме самих данных содержат также поле с адресом получателя, контрольную сумму и другую информацию. Их отправка происходит в интервале передачи пакетов восходящего канала. Этот интервал разбит на отрезки времени, равные продолжительности передачи одного пакета. Конкурентный интервал кадра необходим АС для отправки запросов о предоставлении им места в интервале передачи пакетов. Конкурентный интервал также разбит на равные отрезки времени (слоты), в каждый из которых может быть передан один запрос от АС. Получив запросы, ЦС выносит решение о том, какие слоты в интервале передачи пакетов будут выделены для АС, и передает свое решение в заголовке следующего кадра.

  Общая структура кадра Модель-1

Рисунок 1 – Общая структура кадра

Модель СМД централизованной сети состоит в следующем:

- рассматривается только конкурентный интервал;

- в слотах возможна либо ситуация «пусто» – передачи отсутствовали, либо ситуация «успех» – произошла успешная передача, либо ситуация «конфликт» – произошла одновременная передача двух или более запросов;

- АС получают информацию о ситуациях в слотах в начале следующего кадра;

- каждая АС не может иметь больше одного запроса в один момент времени.

В качестве модели шумов используется модель ложных конфликтов, полностью определяемая двумя вероятностями: – вероятность, с которой ЦС из-за шума воспринимает слот с ситуацией «пусто» как слот с ситуацией «конфликт» и – вероятность, с которой ЦС из-за шума воспринимает слот с ситуацией «успех» как слот с ситуацией «конфликт». Шумы в нисходящем канале отсутствуют (в предположении большой мощности передатчика ЦС).

Применяются две модели поступления запросов в систему. В первой модели число поступающих запросов распределено по закону Пуассона с параметром , определяющим интенсивность поступления запросов в расчете на кадр. Вторая модель описывается дискретным пачечным марковским входным процессом (D-BMAP).

Алгоритм СМД рассматривается как алгоритм, решающий две задачи:

- задача управления передачей новых запросов (за данную задачу отвечает алгоритм доступа к каналу);

- задача управления повторной передачей запросов после возникновения конфликтов (эту задачу решает алгоритм разрешения конфликтов (АРК)).

Используются следующие определения основных характеристик алгоритмов СМД, введенные Б.С. Цыбаковым.

Задержкой запроса называется время от момента возникновения запроса до момента его успешной передачи (единица времени – один кадр).

Пусть в произвольный момент времени на какую-либо незагруженную абонентскую станцию вводят запрос, задержку которого обозначим через .

Средней виртуальной задержкой запроса называется величина

.




Скорость R алгоритма СМД – это верхняя грань интенсивности входного потока, для которой средняя задержка конечна:

,

где – средняя задержка при интенсивности запросов входного потока в расчете на слот конкурентного интервала.

В разделе 2 рассматривается известный алгоритм СМД с очередью для централизованных сетей – FIFO by Sets ALOHA (FS-ALOHA). Алгоритм является базовым по отношению к другим алгоритмам СМД с очередью, которые исследуются в диссертационной работе.

В FS-ALOHA все слотов конкурентного интервала разбиты на два непересекающихся подмножества. Первое подмножество содержит слотов доступа, второе – слотов разрешения конфликтов. Первую попытку передачи запроса абоненты производят случайным образом с помощью равномерного выбора в одном из слотов доступа. Запросы, которые не были успешно переданы в слотах доступа одного кадра, образуют конфликтное подмножество (КП). Данное КП становится в конец очереди из таких же КП, которые ожидают обслуживания. Передача запросов из КП происходит случайным образом с помощью равномерного выбора в одном из слотов разрешения конфликтов. КП находится в начале очереди до тех пор, пока все его запросы не будут успешно переданы. Если очередь пустая, то все слотов конкурентного интервала используются для передачи новых запросов. Пример передачи запросов с помощью алгоритма FS-ALOHA показан на рисунке 2. На рисунке использованы следующие обозначения: у – успешная передача, к – конфликтная передача, – абонент с номером и овал с цифрами – КП с номерами абонентов.

  Пример функционирования-20

Рисунок 2 – Пример функционирования алгоритма FS-ALOHA

Для вычисления скорости FS-ALOHA функционирование алгоритма можно описать в терминах теории систем массового обслуживания как очередь FIFO GI/GI/1. Условие устойчивости данной системы:

. (1)

где – это среднее количество КП, образующихся в течение одного кадра. А интенсивность обслуживания может быть вычислена как среднее количество КП, которые обслуживаются за один кадр, при условии, что в системе присутствует хотя бы одно КП. В диссертационной работе условие устойчивости (1) принимает следующий вид:

, (2)

где . Величина – это математическое ожидание числа кадров, необходимых для обслуживания одного КП, содержащего запросов. Вероятность – это вероятность того, что в канале с пуассоновским входным потоком интенсивности запросов в расчете на кадр и с ложными конфликтами, определяемыми вероятностями , на слотах доступа образуется КП, содержащее запросов.

Предельная интенсивность , при которой система устойчива, может быть определена как максимальная интенсивность , при которой выполняется неравенство (2). Тогда скорость алгоритма FS-ALOHA вычисляется так: .

Из работ Блонди следует, что алгоритм FS-ALOHA имеет максимальную скорость в бесшумном канале при параметрах и . В диссертационной работе показано, что это справедливо и в канале с шумом. Именно для параметров и вычислено критическое значение вероятности ложного конфликта, при котором скорость FS-ALOHA равна нулю, то есть при одинаковой вероятности ложных конфликтов скорость равна нулю, если выполняется следующее неравенство:

. (3)

Более сложный подход к описанию функционирования алгоритма FS-ALOHA позволяет найти распределение вероятностей для задержки запроса.

Процесс функционирования алгоритма FS-ALOHA описывается многомерным марковским процессом, состоящим из трех компонент:

, (4)


Pages:   || 2 | 3 |
 

Похожие работы:







 
© 2013 www.dislib.ru - «Авторефераты диссертаций - бесплатно»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.