автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Разработка методов анализа протоколов управления доступом к среде в централизованных беспроводных сетях

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

ВИНЕЛЬ Алексей Викторович

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

Специальности 05 13 13 — 05.13.01-

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва-2007

003059451

003059451

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

Научные руководители.

доктор технических наук, профессор Вишневский Владимир Миронович

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

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

профессор Жданов Владимир Сергеевич

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

доцент Гончаров Михаил Владимирович

Ведущая организация - Институт проблем управления им. В А Трапезникова РАН, г Москва.

Защита состоится « » мая 2007 г в */часов на заседании диссертационного совета Д 002.077 01 при Институте проблем передачи информации им А А Харкевича РАН по адресу 127994, г Москва, ГСП-4, Большой Каретный переулок, д 19

С диссертацией можно ознакомиться в библиотеке ИППИ РАН

Автореферат разослан «_» апреля 2007 г

Ученый секретарь

диссертационного совета

доктор физико-математических наук

Цитович И.И

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

Актуальность темы В настоящее время стремительными темпами происходит развитие сетей передачи данных. Это особенно заметно по активным процессам международной стандартизации, производства оборудования и развертывания беспроводных вычислительных сетей Среди них все большее распространение получают, например, такие технологии как персональные сети IEEE 802 15 (Bluetooth), применяемые для связи компьютера с периферийным оборудованием и локальные сети IEEE 802.11 (Wi-Fi), активно используемые для организации зон общего доступа (hot-spot) в глобальную сеть Интернет. К настоящему моменту также принят международный стандарт универсальных городских сетей IEEE 802 16 (WiMAX), в которых беспроводной широкополосный доступ будет использоваться очень широким спектром приложений - от традиционного голосового сервиса до современных мультимедиа-приложений

Все упомянутые технологии включают в себя специальные протоколы взаимодействия узлов сети для управления передачей пакетов по общему каналу связи Наличие общего канала связи, коллективно используемого абонентами (зачастую очень большим их числом), является общей чертой современных и перспективных беспроводных вычислительных сетей Вызванная практикой необходимость обеспечения максимально эффективного использования ограниченного ресурса беспроводного канала большим числом абонентов определяет огромный интерес и актуальность исследований в области анализа и разработки соответствующих протоколов множественного доступа В частности, значительный интерес представляют исследования централизованных вычислительных сетей, в которых имеется центральная станция, координирующая работу остальных абонентов Именно такая сетевая архитектура является основной в стандарте IEEE 802 16 Отличительными особенностями этого стандарта являются высокая сложность протокола подуровня управления доступом к среде (УДС), отвечающего, в частности, за организацию доступа абонентов к общему каналу связи, а также наличие большого числа неопределенных (vendor-dependent) частей, в которых стандартизированы лишь некоторые механизмы сетевого взаимодействия, эффективное использование которых возлагается на производителя оборудования Эти особенности технологии WiMAX, а также ее новизна, приводят к необходимости разработки методов анализа протоколов УДС для централизованных вычислительных сетей такого типа

Согласно стандарту IEEE 802 16 для резервирования ресурса канала абонентскими станциями используются либо методы случайного множественного доступа (СМД), либо упорядоченного опроса (поллинга) В первом случае абоненты передают запросы центральной станции в интервале передачи запросов и, если запросы от разных абонентов накладываются друг на друга, то возникает кон-

з

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

Разработке методов анализа описанных выше процессов, применительно к сети IEEE 802 16, посвящена диссертационная работа Среди трудов по теории СМД можно выделить работы Дж Месси, Б С Цыбакова, Дж Капетанакиса, И Рабина и др , по анализу систем поллинга - Л. Клейнрока, X Такаги, С. Борста и др Аналитические методы анализа подуровня УДС современных беспроводных сетей, в частности, применительно к сетям ШЕЕ 802 11 разрабатываются в работах Дж Бьянки, Ф Кали, В M Вишневского, А И Ляхова и др Однако, в них практически не рассматриваются особенности управления доступом к среде в централизованных сетях стандарта IEEE 802 16

Целью работы является разработка методов анализа протокола УДС стандарта IEEE 802 16 и оценка показателей производительности централизованной вычислительной сети передачи данных этого стандарта

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

1 Разработка модели централизованной системы СМД с резервированием, отражающей особенности функционирования сети IEEE 802 16

2 Разработка метода построения границ пропускной способности централизованной системы СМД с резервированием Определение оптимального соотношения длительностей интервала передачи запросов и интервала передачи пакетов в восходящем канале централизованной сети

3 Разработка метода расчета характеристик алгоритма СМД, используемого в централизованных сетях IEEE 802 16

4 Разработка метода расчета характеристик алгоритма циклического опроса абонентов в централизованных сетях стандарта IEEE 802 16

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

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

1 Метод расчета границ пропускной способности централизованной сети с резервированием посредством случайного доступа

2 Метод расчета средней задержки передачи запроса для алгоритма случайного доступа стандарта IEEE 802 16,

3 Метод расчета средней задержки передачи запроса при использовании в IEEE 802 16 циклического опроса абонентов

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

1 Разработана модель централизованной системы СМД с резервированием, которая в отличие от известных моделей, отражает существенные особенности протокола УДС перспективных беспроводных сетей IEEE 802.16

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

3 Разработаны методы расчета средней задержки при выполнении резервирования с использованием алгоритма binary exponential backoff и с использованием циклического опроса абонентов, учитывающие, в отличие от известных методов, специфику формирования и передачи запросов в IEEE 802 16

Практическая ценность работы и реализация результатов

Полученные результаты позволяют оценивать характеристики производительности перспективной беспроводной сети IEEE 802 16, что может быть использовано при ее построении Найденное оптимальное соотношение длительностей интервала передачи запросов и интервала передачи пакетов может использоваться производителями оборудования для повышения эффективности алгоритма распределения ресурсов восходящего канала планировщиком центральной станции.

Результаты диссертационной работы получены при выполнении госбюджетной НИР «Анализ и оптимизация производительности широкополосной беспроводной сети протокола IEEE 802 16» (Per № 01200603037), выполненной под руководством автора диссертации, в Санкт-Петербургском Государственном Университете Аэрокосмического Приборостроения (ГУАП) по заказу Федерального агентства по образованию

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

Апробация работы Основные результаты работы докладывались на следующих научно-технических конференциях- международной молодежной школе-семинаре БИКАМП'03 (Санкт-Петербург, 23 - 27 июня 2003 г), VII научной сессии аспирантов ГУАП (Санкт-Петербург, 12-16 апреля 2004 г), VIII научной сессии ГУАП (Санкт-Петербург, 11-15 апреля 2005 г ), на 16th Annual IEEE Interna-

International Symposium on Personal, Indoor and Mobile Radio Communications -IEEE PIMRC'05 (Берлин, Германия, 11-14 сентября 2005 г), политехническом симпозиуме «Молодые ученые - промышленности Северо-Западного региона» (Санкт-Петербург, 15 декабря 2005 г), научной сессии ГУАП (Санкт-Петербург, 10 - 14 апреля 2006 г.), на 10th IEEE International Symposium on Consumer Electronics - ISCE'06 (Санкт-Петербург, 29 июня - 1 июля 2006 г), Всероссийской школе-конференции «Мобильные системы передачи данных» (Москва, 11-17 сентября 2006 г), на 49th IEEE Global Telecommunications Conference -GLOBECOM'06 (Сан-Франциско, США, 27 ноября - 1 декабря 2006г), Всероссийской научно-практической конференции молодых ученых, аспирантов и студентов в рамках Программы «Участник молодежного научно-инновационного конкурса «Электроника 2006-2007» (Москва, 28 ноября 2006 г), политехническом симпозиуме «Молодые ученые - промышленности Северо-Западного региона» (Санкт-Петербург, 8 декабря 2006 г)

Публикации По теме диссертационной работы опубликовано 17 печатных работ (из них 2 - статьи в ведущих рецензируемых научных журналах из перечня, утвержденного ВАК)

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

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

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

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

В централизованных беспроводных сетях используются два логически обособленных коммуникационных канала- нисходящий - используемый центральной станцией для передачи данных абонентам и восходящий - используемый для передачи данных от абонентов к центральной станции Каналы могут быть сформиро-

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

Согласно стандарту IEEE 802.16 для трафика с низким приоритетом, при выполнении резервирования, описанного выше, могут использоваться различные методы В частности, используется либо алгоритм случайного доступа, позволяющий нескольким абонентам передавать запросы одновременно и осуществлять повторные передачи в случае невозможности успешного приема центральной станцией из-за наложения сигналов, либо механизм опроса, когда в отведенной частотно-временной области передавать может только один абонент

Рассмотрена модель, с бесконечным числом абонентов, где каждый абонент может иметь не более одного пакета требующего передачу Эта модель, предложенная Б С Цыбаковым и Дж Капетанакисом и подробно описанная Р Галлагером, является базовой по отношению к другим моделям множественного доступа, используемым в диссертационной работе

Согласно допущениям базовой модели абоненты передают пакеты фиксированной длины, которая принята за единицу времени Система синхронна, абоненты могут начинать передачу пакетов только в моменты времени t е {0,1,2, }. Временной интервал (f,f+l) называется окном Канал связи является бесшумным и предполагается, что все абоненты к моменту времени /+1 знают, какое из трех возможных событий - пустое окно, успех или конфликт (одновременная передача двух и более абонентов) имело место в окне (м+1) Моменты возникновения пакетов всех абонентов формируют суммарный входной поток, который считается дискретным пуассоновским Вероятность того, что j новых пакетов появляются в системе в некоторый момент времени t, равна е~хХ' I где А - суммарная интенсивность входного потока

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

Задержкой передачи пакета называется интервал времени с момента возникновения пакета до момента его успешной передачи Пусть в произвольный момент времени t на какую-либо незагруженную абонентскую станцию вводят пакет, задержку которого обозначим через ¿¡0)(Л,/0) Виртуальная средняя задержка передачи пакета по определению равна

Скоростью алгоритма СМД fQ называется максимум (или более точно супремум) величины интенсивности входного трафика, который может быть передан алгоритмом с конечной средней задержкой

Д„(/„) = 8иР{Л А, Я/„)<«>}

Наиболее высокоскоростной из известных алгоритмов СМД - алгоритм дробления имеет скорость Rpl = 0 487. Пусть Fq - множество всех алгоритмов СМД Пропускная способность базовой системы СМД (на классе F0) определяется как

С„ = sup R0(f0)

Точное значение пропускной способности С0 в настоящее время неизвестно Наилучшая из известных верхних границ пропускной способности С0 была найдена Н Б Лихановым и Б С Цыбаковым и равна 0 587

В первой главе рассмотрена модификация базовой модели на случай наличия задержки обратной связи специального вида Такая задержка отражает разбиение времени передачи по каналу на фиксированные интервалы времени, содержащие группы окон, которое используется в централизованных беспроводных сетях Пусть все окна сгруппированы в равные последовательные отрезки длины К, и ситуации в окнах текущего отрезка становятся известными абонентам только к началу следующего отрезка Для заданного значения К любой алгоритм СМД, удовлетворяющий этому условию, и множество таких алгоритмов обозначены /0<лг) и соответственно Для такой системы СМД доказаны, в частности, следующие утверждения

Утверждение 1 Для любого алгоритма fa<sF0, имеющего скорость R0, и для любого значения К существует алгоритм f'K) е , также имеющий скорость R0

Утверждение 2 Для любого значения К пропускная способность С'/', достигаемая на классе F0m равна пропускной способности С0 базовой системы

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

Модель для исследования централизованной беспроводной сети построена на основе базовой модели СМД Рассмотрена сеть передачи данных с одной центральной станцией и бесконечным числом абонентских станций Центральная станция связана со всеми абонентами посредством двух каналов связи - нисходящего и восходящего Моменты поступления пакетов образуют пуассоновский процесс, который обеспечивает входной поток интенсивности X пакетов в единицу времени В отличие от базовой модели, каждый абонент, имеющий новый пакет, передает центральной станции запрос для того, чтобы зарезервировать время вос-

ходящего канала Длительность передачи запроса принимается равной а<1 единиц времени Длительности передачи пакетов и запросов фиксированы, а использование восходящего канала организовано следующим образом. Время передачи по каналу разделено на равные отрезки времени, называемые кадрами Все кадры имеют фиксированную структуру Каждый кадр состоит из а: > 1 интервалов времени длительности а, которые называются мини-окнами, и Ь 1 интервалов времени единичной длительности, которые называются окнами Окна используются абонентами для передачи пакетов, а мини-окна - для передачи запросов.

Система является синхронной Центральная станция и все абоненты знают моменты начала кадров, окон и мини-окон В каждом мини-окне / е {1,2, ,К) кадра номер 1-1 возможно три ситуации (будем обозначать их 0,(,)) успешная передача абонента (б/0 =1), пустое мини-окно (отсутствие передач =0) и конфликт, когда два и более абонента передают в мини-окне (0,(,) = 2) К началу каждого г-го кадра центральная станция передает всем абонентам по нисходящему каналу информацию о ситуациях во всех мини-окнах предыдущего кадра 1-1 Эта информация представляет собой вектор обратной связи в, = (0,("Д(2), Д*')

Абоненты передают запросы посредством некоторого алгоритма СМД /'*' для централизованной системы с резервированием Этот алгоритм есть правило, которое основывается на ситуациях в мини-окнах предыдущих кадров и используется абонентами в начале очередного кадра для того, чтобы определить передавать ли запросы в каких-либо мини-окнах этого кадра или нет. Аналогично базовой модели /(К) введена как функция трех аргументов /т[х,в(п),у{х,п)] Здесь х - момент времени, когда пакет был сгенерирован, в{п) = Д Д, Д) - последовательность векторов обратной связи, известных к началу кадра п, а у{х,п) = (у,(х),у2(х), ,у„(х)) - последовательность векторов, связанная с абонентом, который сгенерировал пакет в момент времени х, у,(х) = (у,0'(х),у12'(х), ,у\к){х)) Введены обозначения у^'Ч*) = 0, если абонент пакет которого был сгенерирован в момент х не передавал запрос в /-ом мини-окне (<-1)-го кадра и у,и>(*) = 1 - в противном случае. Областью значений функции / является множество векторов длины К• р = (рт,рт, ,р'к)), где каждый элемент рю представляет вероятность передачи абонента в /-ом мини-окне п -го кадра

На центральной станции имеется бесконечная очередь для запросов Когда запрос успешно передается некоторым абонентом, он попадает в хвост этой очереди Центральная станция обслуживает запросы из очереди согласно некоторому правилу - дисциплине обслуживания ga) Обслуживание производится посредством передачи к началу каждого кадра в нисходящем канале информации о том, каким абонентам разрешено передавать пакет в каждом из Л окон следующего кадра (Рис 1)

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

ле всем абонентам Пара (/т,£(1>) назвала протоколом множественного доступа для централизованной сети с резервированием с параметрами (К,Ь)

\ Н— ЦС ЕШГ\ Планирование согласно

--некоторой дисциплине

обслуживания д<ч

Успешно переданные запросы

-У-

Интервал для

запросов (С мини-окон длительности а

Интервал для пакетов и окон единичной длительности

Длительность кадра (восходящая передача)

Время

Запросы передаются

в мини-окнах согласно некоторому алгоритму СМД /<">

ИГ"

Пакеты передаются в назначенных окнах

Бесконечное число абонентов

■ ■

Пуассоновский входной поток пакетов

Рис 1 - Упрощенная схема модели централизованной вычислительной сети с резервированием

Определения Цыбакова расширены применительно к централизованной сети с резервированием Интервал времени с момента возникновения пакета до момента его успешной передачи будем называть задержкой передачи пакета Пусть в некотором произвольном кадре (имеющем номер и) в систему вводится пакет Задержка передачи этого пакета обозначена за 8,

Согласно алгоритму работы системы задержка передачи пакета складывается из двух компонент Первая компонента - задержка передачи запроса посредством алгоритма СМД ¿¡1Г>(Л,К,1,/1К)) Это время с момента возникновения пакета до момента успешной передачи соответствующего ему запроса Вторая компонента -время с момента успешной передачи запроса до момента, когда успешно будет передан соответствующий пакет

Средняя задержка передачи пакета для заданной интенсивности входного потока Л, числа мини-окон К, окон I и протокола множественного доступа определена, как = ) +3[г') и сред-

няя задержка передачи запроса обозначена за £>, = йт»^»^'11

Величина = 5ирх{Л В(Л,К,1,/(К\гщ)«о} названа скоростью

протокола множественного доступа Если же протокол множественного доступа не зафиксирован, то пропускной способностью сети передачи данных названо следующее значение С^К.^Р^.^-вар^^^^ где множество всех алгоритмов СМД для системы с К мини-окнами, а <3(1> - множество всех дисциплин обслуживания для системы с I окнами

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

Утверждение 3 Средняя задержка Д передачи запроса и средняя задержка Х> передачи пакета бесконечна, если не выполняется неравенство Л(аК +1) < С0К

Утверждение 4 Средняя задержка £> передачи пакета бесконечна, если не выполняется неравенство Л(аК + !)<!

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

Утверждение 5 Для заданного значения а выполняется следующее неравенство для пропускной способности централизованной сети передачи данных

Доказательство этого утверждения основано на построении областей на плоскости (Я, К / Ь), где система возможно стабильна Из утверждений 3 и 4 следует, что эти области задаются следующими неравенствами А,(Я) = Х1(С„ -аХ) < К!Ь и А2(А) Л)/аЛ > К/Ь С ростом значения Л сужается область для допустимых значений отношения КИ (Рис 2) Наконец, неравенства перестают выполняться в точке Л0=С0/(а + С0) такой, что Л,(Я0) = А2(Я0) из чего показывается справедливость утверждения

тахС(К,Ь,Рт,вт) <---

1 + а/С0

К1

И

О

О 01

03

0 5 Х0 0 7

09

Рис 2 Области неустойчивости протокола множественного доступа

и

Из утверждения 1 следует, что в классе F(K) существует алгоритм СМД, имеющий такую же скорость передачи Л,,, как алгоритм дробления Более того, в конструктивном доказательстве утверждения 1 указан явный способ построения такого алгоритма Этот алгоритм обозначен как фт и доказывается следующее утверждение для нижней границы пропускной способности

Утверждение 6. Пусть в централизованной сети с резервированием используется алгоритм СМД фт и дисциплина облуживания в порядке поступления (first input first output - FIFO), которую обозначим <рщ Тогда максимальная скорость передачи протокола множественного доступа (Ф{К\<р{1)) для всех возможных значений К и L равна

ma>iR(K,L,0iK) ,<ри)) = ——— и достигается, когда К/L=l/Rpl

Далее выдвигается следующая гипотеза. Пусть рассматривается централизованная вычислительная сеть, в которой используется некоторый "рациональный" алгоритм СМД /(АГ), имеющий скорость R0, которая не зависит от значения к, и некоторая "простая" дисциплина обслуживания g,L> (например, FIFO) Тогда, отношение K/L, которое минимизирует среднюю задержку передачи пакета D(X,K,L,f-K),gw) - есть неубывающая функция от интенсивности входного потока Л, и для любого а значения этой функции лежат в узком диапазоне не превосходящем [1,1 /Ra] Более того сама средняя задержка минимальна, когда К и L минимальны среди значений, удовлетворяющих оптимальному соотношению К/ L Таким образом, с учетом гипотезы, структура кадра может быть выбрана оптимальным образом, и она практически не зависит от соотношения между длительностями передачи запроса и пакета

В главе 3 разработан метод расчета характеристик алгоритма binary exponential backoff, используемого в сетях IEEE 802 16 В частности, приведены способы расчета средней задержки передачи запроса для произвольной интенсивности входного потока

Расчет средней задержки передачи пакета для сети с резервированием в общем виде представляет собой достаточно сложную задачу. В главе 3 передача пакетов не рассматривается (L = 0) и разрабатывается метод расчета средней задержки передачи запроса посредством определенного в стандарте IEEE 802 16 алгоритма СМД binary exponential backoff (ВЕВ) В русскоязычной литературе закрепился достаточно неудачный перевод названия этого алгоритма - "двоичный экспоненциальный откат".

В ряде документов рабочей группы IEEE 802 16 для моделирования трафика сети предлагается использовать модель с двумя состояниями активным, когда формируются пакеты, и пассивным, когда нет Поскольку точный алгоритм формирования запросов в стандарте IEEE 802 16 не определен (зависит от реализации) то, следуя указанному подходу, мы также будем различать два состояния у каждо-

го абонента Будем предполагать, что абонент переходит в активное состояние, когда у него появляется запрос на некоторые пакеты, требующие передачу При успешной передаче запроса происходит переход абонента в пассивное состояние

Рассмотрим п абонентов, имеющих буфер, достаточный для хранения только одного запроса Определим номинальную величину входного потока запросов X как среднее число запросов, появляющихся в системе за длительность кадра, при условии, что в системе нет активных абонентов За длительность кадра каждый пассивный абонент генерирует запрос с вероятностью я- = Л/и

На основе спецификации IEEE 802 16 вводится следующее формальное описание алгоритма BEB Перед каждой попыткой передачи, абонент равномерно выбирает целое число из интервала [0,W, -1], где W, - это текущее значение его конкурентного окна Выбранное значение (счетчик отложенной передачи), показывает количество мини-окон, которое абонент должен ждать перед попыткой передачи запроса Для первой попытки передачи величина конкурентного окна устанавливается равной Wmu = IK, где / — натуральное число В случае конфликта абонент удваивает это значение, так что после i конфликтов, оно становится равным W, =2lWm (значение i называется стадией отката) Конкурентное окно не удваивается в том случае, если оно достигло максимального значения Wmx =2 "Wmn. В случае успешной передачи конкурентное окно устанавливается в минимальное значение Wma Таким образом, алгоритм описывается парой параметров (1,т)

Изменение количества активных абонентов в такой системе во времени есть случайный процесс Будем наблюдать состояния системы в начале каждого кадра Тогда последовательность состояний может быть описана цепью Маркова с дискретным временем, причем состоянием является текущее число активных абонентов Покажем, как можно получить переходные вероятности этой цепи

Вводится следующее допущение Пусть, к началу кадра имеется г активных абонентов и вероятность того, что некоторый абонент будет передавать запрос в этом кадре, равна аналогичной вероятности, полученной для сети в которой всегда есть I активных абонентов

Для расчета вероятности x(i) исследуется система, в которой всегда имеется фиксированное число абонентов Рассматривается p(1\t) - вероятность того, что в кадре с номером t абонент с номером j попадет в конфликт и, используя подход Дж. Бьянки, вводится следующее допущение Вероятность pii](t) не меняется со временем для произвольно взятого абонента и одинакова для всех абонентов Таким образом, фактически работа одного абонента считается независимой от состояния других абонентов С учетом этого допущения предлагается два метода расчета вероятности x(i)

Согласно первому методу вводится дискретная и целочисленная временная шкала, где t и t +1 соответствует началу двух последовательных кадров и рассматривается с, (/) - стохастический процесс, представляющий собой число кадров, которые абонент должен ждать в момент времени t, до того как начнет передачу Пусть b(t) - стадия отката абонента в момент t Далее, на основе правил работы алгоритма BEB выписываются переходные вероятности двумерной эргодической це-

пи Маркова {6(0, с, (г)}. Рассчитывается стационарное распределение этой цепи и находится вероятность х передачи в кадре

(\-2p){l + \) + pl(\-{2pY) К >

где р - вероятность возникновения конфликта при условии, что абонент начал передачу, которая рассчитывается следующим образом

'-■-К' (2)

Согласно второму методу вводится дискретная и целочисленная временная шкала, в которой t и t + 1 соответствует началам двух последовательных мини-окон и рассматривается марковский процесс {6(0.c2(i)}, где b(t) и с2(г) - соответственно счетчик отложенной передачи и стадия отката некоторого абонента в момент времени /. Выписываются переходные вероятности такой цепи, рассчитывается ее стационарное распределение и показывается, что вероятность хг события, что абонент передает в случайно выбранном мини-окне, может быть выражена как

__2(1-2 р) _

= Ь-2р1к1+1)+Рк1[\-(гРТ)+{к-\1\-гР) &

Кроме того, выполняется очевидное соотношение

р = 1-(1-х2У'\ (4)

Далее, возвращаясь к анализу производительности сети для произвольной интенсивности входного потока, выписывается вероятность Qk, выбора данного

кадра к из i абонентами Qk, = C/[x(i)]t(l-*('))'~*, где x(i) - вероятность передачи в кадре, рассчитываемая путем решения системы уравнений (1) - (2) или (3) - (4) относительно неизвестных (р,х) или (р,х2) соответственно, для некоторого числа абонентов г, С* - число сочетаний из i элементов по к.

Рассчитывается вероятность успешной передачи г абонентами в кадре, при условии, что к его началу к абонентов будут передавать в этом кадре Она равна К к = N{r,k,K)l Кк, где N(r,k,K) обозначает число возможных способов разместить к шаров по К урнам, так чтобы в точности г урн содержало по одному шару В диссертационной работе приводятся рекурсивные правила расчета этой функции

Тогда, вероятность успешной передачи г абонентами в кадре, при условии, что имеется i активных абонентов, равна =^t.rRrtQt, Поскольку поступление

запросов моделируется потоком Бернулли, то число новых запросов, появляющихся в системе за длительность кадра, имеет биномиальное распределение с парамет-

ром л и вероятность появления j новых запросов за время кадра, при условии, что имеется i активных абонентов, имеет вид y/jt = С^я1 (I- л)"~'~'

Затем, с использованием вероятностей и ц/h выписывается матрица переходных вероятностей цепи, описывающей число активных абонентов в системе Рассчитываются стационарные вероятности полученной эргодической цепи и среднее число запросов в системе N, откуда по формуле Литтла находится средняя задержка при передаче запроса dBEB =05 + Nn/[(n - N)X\.

В главе 4 разработан метод расчета средней задержки передачи запроса при использовании в стандарте IEEE 802.16 циклического поллинга абонентов в канале с шумом Результаты главы 3 также обобщены на случай наличия шума в канале связи Выполнен сравнительный анализ случайного доступа и циклического поллинга в сети IEEE 802 16

Беспроводной канал связи характеризуется высокой вероятностью искажения передаваемого по нему сигнала Классическая модель канала с шумом применительно к базовой системе СМД была предложена Г С Евсеевым Согласно этой модели шумы в канале могут приводить к тому, что абоненты совершают ошибки в определении ситуаций в окнах А именно, шум на окнах с ситуациями "пусто" или "успех" приводит к тому, что все абоненты принимают решение о том, что была ситуация "конфликт" Шум на пустом окне не оказывает никакого влияния на работу алгоритма BEB Пусть ре - вероятность перехода "успех" - "конфликт" (ложного конфликта) В главе 4 показывается как, используя анализ из главы 3, учесть влияние ложных конфликтов на работу BEB.

Циклический поллинг (polling) рассматривается применительно к централизованной сети в рамках модели из главы 3, что позволяет сопоставить полученные результаты с результатами, полученными для BEB

Считается, что абоненты занумерованы, и каждое из мини-окон последовательно назначается абонентам С учетом того, что в интересных для практики случаях и » К, полный цикл опроса занимает т-п/К кадров (для простоты полагаем что К - делитель п, а все кадры имеют циклическую нумерацию от 1 до о) Информация о распределении мини-окон данного кадра между абонентами сообщается центральной станцией к его началу в нисходящем канале

Рассматривается некоторый произвольный абонент и, не умоляя общности, предполагается, что он опрашивается в кадрах, имеющих номер 1 Тогда, его работа может быть описана цепью Маркова {y(t),z(t)} с дискретным временем, где единицей времени являются начала кадров, y(t) - номер кадра, который начинается в момент времени t, a z(r) - состояние рассматриваемого абонента (0 - пассивное, 1 - активное) в этот момент времени Выписываются переходные вероятности этой цепи, выполняется расчет ее стационарного распределения и средней задержки при передаче запроса

-т nc Q-я)"+а>(1-л)""1 я2 + ал-I р,а> а „„,,,„ =05 +--—--—-+ --

Используя правило Лопиталя, показывается, что в асимптотическом случае при ж -» 0, средняя задержка передачи запроса равна <э/ 2 + 1, а в сильно загруженной системе, когда ж = 1, средняя задержка равна со-1/2

По средней задержке передачи запроса сравниваются алгоритм ВЕВ и пол-линг как в бесшумном канале, так и при наличии ложных конфликтов В частности, в качестве примера рассмотрен сценарий с параметрами л = 30, к = 5 и построены зависимости средней задержки при передаче запроса от номинальной интенсивности входного потока на мини-окно пж!К (Рис 3) для случая бесшумного канала связи Можно видеть, что проведенный сравнительный анализ, проиллюстрированный на данном примере, имеет большое значение на практике Он позволяет для любых параметров сети рассчитывать такое значение вероятности возникновения запроса у абонента за длительность кадра, при котором центральной станции целесообразно производить переключение со случайного доступа на циклический опрос абонентов

„I-и-,-,-,-,-,-,-,-,-

0 05 1 15 2 25 3 35 4 45 5 д/К

Рисунок 3 — Сравнение производительности случайного доступа и циклического поллинга

В заключении приводятся основные результаты, полученные в диссертационной работе

В приложении приведен метод расчета стационарного распределения цепи ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2 Построены нижняя и верхняя границы пропускной способности централизованной беспроводной сети

3 Найдено отношение длительностей интервала передачи пакетов и интервала передачи запросов, при котором пропускная способность сети максимальна

4 Разработано два метода анализа алгоритма СМД ВЕВ, применяемого для управления передачей запросов в централизованной сети стандарта IEEE 802 16, для случая фиксированного числа активных абонентов

5 Разработан метод вычисления распределения вероятностей числа абонентов в системе и средней задержки при передаче запроса с использованием алгоритма ВЕВ для случая переменного числа активных абонентов

6 Разработан метод вычисления средней задержки передачи запроса при использовании метода циклического поллинга для резервирования в IEEE 802 16 в случае произвольной интенсивности входного потока Выполнен сравнительный анализ алгоритма ВЕВ и алгоритма циклического опроса в бесшумном канале и в канале с шумом

7. Разработан комплекс программ имитационного моделирования и численного расчета вероятностно-временных характеристик протоколов множественного доступа централизованных беспроводных сетей

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Винель А В Исследование работы протокола IEEE 802 11 в канале с шумом // Международная школа-семинар "БИКАМП'ОЗ" Сб тр / ГУАП, СПб, 2003, С 171-174.

2 Винель А В Сравнение методов анализа работы протокола IEEE 802 11 при высокой нагрузке в канале с шумом // VII научная сессия аспирантов ГУАП Сб докл /ГУАП, СПб, 2004, С 170-173

3 Винель А В Анализ случайного доступа протокола IEEE 802 16 при большом числе абонентов // VIII научная сессия ГУАП Сб докл / ГУАП, СПб, 2005, С 272-275

4 Vmel А, Zhang Y, Lott М , Turlikov A Performance Analysis of the Random Access m IEEE 802 16 // Proc of the 16th Annual IEEE International Symposium on Personal, Indoor and Mobile Radio Communications - IEEE PIMRC'05, Berlin, Germany, 2005

5 Lott M, Vinel A, Zhang Y. Propagation Modeling for Systems Beyond 3G // Proc of the International Wireless Summit 2005 - WPMC'05, Aalborg, Denmark, 2005

6 Ляхов А И, Баранов А В , Винель А В Оценка взаимозависимости поведения станций в локальных беспроводных сетях с протоколом IEEE 802 11 // VIII международный семинар "Распределенные компьютерные и телекоммуникационные сети"-DCCN'05, София, Болгария Сб.тр / Москва, Техносфера, 2005, С 95-104

7. Винель А В , Кобляков В А Алгоритмы случайного множественного доступа для централизованных беспроводных сетей передачи данных // Сб тр Политехнического Симпозиума "Молодые ученые - промышленности Северо-Западного Региона", декабрь 2005 / ГПУ, СПб, 2005, С 48

8 Винель А В., Андреев С Д Оценка среднего времени пребывания алгоритма Binary Exponential Backoff в устойчивом состоянии // Научная сессия ГУАП, посвященная всемирному Дню авиации и космонавтики и 65-летию ГУАП Сб. докл / ГУАП, СПб, 2006, С 250-253

9 Kobhakov A.V, Turlikov А М, Vinel А V. Distributed Queue Random Multiple Access Algorithm for Centralized Data Networks // Proc of the 10th IEEE International Symposium on Consumer Electronics - ISCE'06, St -Petersburg, Russia, 2006

10 Винель А В Высокоскоростной алгоритм случайного доступа для централизованной сети передачи данных // Сб тр Российской школы-конференции «Мобильные системы передачи данных» / МИЭТ, Москва, 2006, С 55-57

11 Винель А В., Кобляков В А Разработка и анализ алгоритмов случайного множественного доступа для беспроводных централизованных сетей передачи данных // Сборник материалов Всероссийского конкурса инновационных проектов аспирантов и студентов по приоритетному направлению развития науки и техники «Информационно-телекоммуникационные системы» / Под ред А О Сергеева, Москва, ГНИИ ИТТ "Информика", 2006, С 149-150

12 Vinel А, Zhang Y, Ni Q , Lyakhov A Efficient Request Mechanisms Usage m IEEE 802 16 // Proc of 49th IEEE Global Telecommunications Conference -GLOBECOM'06, San Francisco, California, USA, 2006

13 Винель А В Разработка протокола подуровня управления доступом к среде для высокоскоростной беспроводной локальной вычислительной сети // Всероссийская научно-практическая конференция молодых ученых, аспирантов и студентов в рамках Программы «Участник молодежного научно-инновационного конкурса «Электроника 2006-2007» / МИЭТ, Москва, 2006, С 40

14. Винель AB. Анализ механизмов передачи запросов по протоколу IEEE 802 16 в канале с шумом // Сб тр Политехнического Симпозиума "Молодые ученые — промышленности Северо-Западного Региона", декабрь 2006 / ГПУ, СПб, 2006, С 51-52

15. Винель AB. Управление передачей пакетов в централизованных сетях // Одиннадцатая Санкт-Петербургская Ассамблея молодых ученых и специалистов (аннотации работ по грантам конкурса 2006 года для студентов и аспирантов ВУЗов и академических институтов Санкт-Петербурга) / ГУ, СПб, 2006, С 41

16. Ni Q , Vinel А, Xiao Y, Turlikov A, Jiang T Investigation of Bandwidth Request Mechanisms under Point-to-Multipomt (PMP) Mode of WiMAX Networks // IEEE Communications Magazine, № 5,2007.

17 Винель А В , Кобляков В A , Тюрликов A M Класс алгоритмов случайного множественного доступа с очередью для централизованных сетей передачи данных // Информационные технологии, № 5,2007, С 32—41

Список использованных сокращений.

Введение.

1 Принципы функционирования протоколов подуровня УДС современных беспроводных централизованных сетей передачи данных.

1.1 В вод ные замечания.

1.2 Протокол подуровня УДС беспроводной сети стандарта IEEE 802.16.

1.2.1 Общие сведения.

1.2.2 Структура подуровня УДС.

1.2.3 Основные режимы работы.

1.2.4 Принципы предоставления канальных ресурсов.

1.3 Обзор исследований систем случайного множественного доступа.

1.4 Базовая модель случайного множественного доступа.

1.5 Вспомогательные результаты для базовой модели.

1.6 Обзор исследований систем поллинга.

1.7 Постановка задачи исследования.

1.8 Выводы по главе.

2 Исследование протокола УДС централизованной беспроводной сети.

2.1 Использование СМД при резервировании.

2.2 Модель централизованной сети с резервированием.

2.3 Показатели производительности централизованной сети.

2.4 Оценка пропускной способности централизованной сети.

2.5 Учет особенностей беспроводной сети протокола IEEE 802.16.

2.6 Выводы по главе.

3 Исследование механизма резервирования посредством СМД в централизованных вычислительных сетях.

3.1 Модель системы для исследования механизма резервирования.

3.2 Описание алгоритма СМД binary exponential backoff.

3.3 Анализ алгоритма binary exponential backoff в условиях насыщения.

3.3.1 Подход с цепью Маркова и биномиальным распределением.

3.3.2 Подход с цепью Маркова и дополнительными состояниями простоя

3.4 Сравнение результатов аналитического и имитационного моделирования

3.5 Оценка эффективности случайного доступа в IEEE 802.16.

3.5.1 Оптимизация размера конкурентного окна.

3.5.2 Чувствительность задержки к изменению числа станций.

3.5.3 Производительность алгоритма BEB для различного числа абонентов и оптимизированных значений параметров.

3.6 Анализ алгоритма binary exponential backoff в условиях произвольной нагрузки.

3.7 Выводы по главе.

4 Сравнительный анализ методов выполнения резервирования в централизованных вычислительных сетях.

4.1 Вводные замечания.

4.2 Модель канала с шумом.

4.3 Анализ циклического опроса абонентов.

4.4 Сравнительный анализ эффективности алгоритма BEB и метода циклического опроса.

4.5 Выводы по главе.

Актуальность темы. В настоящее время стремительными темпами происходит развитие сетей передачи данных. Это особенно заметно по активным процессам международной стандартизации, производства оборудования и развертывания беспроводных вычислительных сетей. Среди них все большее распространение получают, например, такие технологии как персональные сети IEEE 802.15 (Bluetooth), применяемые для связи компьютера с периферийным оборудованием и локальные сети IEEE 802.11 (Wi-Fi), активно используемые для организации зон общего доступа (hot-spot) в глобальную сеть Интернет. К настоящему моменту также принят международный стандарт универсальных городских сетей IEEE 802.16 (WiMAX), в которых беспроводной широкополосный доступ будет использоваться очень широким спектром приложений - от традиционного голосового сервиса до современных мультимедиа-приложений.

Все упомянутые технологии включают в себя специальные протоколы взаимодействия узлов сети для управления передачей пакетов по общему каналу связи. Наличие общего канала связи, коллективно используемого абонентами (зачастую очень большим их числом), является общей чертой современных и перспективных беспроводных вычислительных сетей. Вызванная практикой необходимость обеспечения максимально эффективного использования ограниченного ресурса беспроводного канала большим числом абонентов определяет огромный интерес и актуальность исследований в области анализа и разработки соответствующих протоколов множественного доступа. В частности, значительный интерес представляют исследования централизованных вычислительных сетей, в которых имеется центральная станция, координирующая работу остальных абонентов. Именно такая сетевая архитектура является основной в стандарте IEEE 802.16. Отличительными особенностями этого стандарта являются высокая сложность протокола подуровня управления доступом к среде (УДС), отвечающего, в частности, за организацию доступа абонентов к общему каналу связи, а также наличие большого числа неопределенных (vendor-dependent) частей, в которых стандартизированы лишь некоторые механизмы сетевого взаимодействия, эффективное использование которых возлагается на производителя оборудования. Эти особенности технологии WiMAX, а также ее новизна, приводят к необходимости разработки методов анализа протоколов УДС для централизованных вычислительных сетей такого типа.

Согласно стандарту IEEE 802.16 для резервирования ресурса канала абонентскими станциями используются либо методы случайного множественного доступа (СМД), либо упорядоченного опроса (поллинга). В первом случае абоненты передают запросы центральной станции в интервале передачи запросов и, если запросы от разных абонентов накладываются друг на друга, то возникает конфликт. Абоненты, попавшие в конфликт, осуществляют повторную передачу в соответствии с определенными правилами. Во втором случае центральная станция по некоторому алгоритму назначает каждое мини-окно для передачи запроса в точности одному абоненту и конфликтов не возникает. В обоих случаях, если запрос успешно принимается центральной станцией, то ею осуществляется распределение ресурса канала между абонентами, выполнившими резервирование, на основе метода временного разделения.

Разработке методов анализа описанных выше процессов, применительно к сети IEEE 802.16, посвящена диссертационная работа. Среди трудов по теории СМД можно выделить работы Дж. Месси, Б.С. Цыбакова, Дж. Капетанакиса, И. Рабина и др.; по анализу систем поллинга - JI. Клейнрока, X. Такаги, С. Борста и др. Аналитические методы анализа подуровня УДС современных беспроводных сетей, в частности, применительно к сетям IEEE 802.11 разрабатываются в работах Дж. Бьянки, Ф. Кали, В.М. Вишневского, А.И. Ляхова и др. Однако, в них практически не рассматриваются особенности управления доступом к среде в централизованных сетях стандарта IEEE 802.16.

Основной целью работы является разработка методов анализа протокола УДС стандарта IEEE 802.16 и оценка показателей производительности централизованной вычислительной сети передачи данных этого стандарта. Для достижения поставленной цели в работе решались следующие задачи:

1). Разработка модели централизованной системы СМД с резервированием, отражающей особенности функционирования сети IEEE 802.16.

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

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

4). Разработка метода расчета характеристик алгоритма циклического опроса абонентов в централизованных сетях стандарта IEEE 802.16.

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

Научная новизна диссертационной работы заключается в следующем:

1). Разработана модель централизованной системы СМД с резервированием, которая в отличие от известных моделей, отражает существенные особенности протокола УДС перспективных беспроводных сетей IEEE 802.16.

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

3). Разработаны методы расчета средней задержки при выполнении резервирования с использованием алгоритма binary exponential backoff и с использованием циклического опроса абонентов, учитывающие, в отличие от известных методов, специфику формирования и передачи запросов в IEEE 802.16.

Практическая ценность и реализация результатов. Полученные результаты позволяют оценивать характеристики производительности перспективной беспроводной сети IEEE 802.16, что может быть использовано при ее построении. Найденное оптимальное соотношение длительностей интервала передачи запросов и интервала передачи пакетов может использоваться производителями оборудования для повышения эффективности алгоритма распределения ресурсов восходящего канала планировщиком центральной станции.

Результаты диссертационной работы получены при выполнении госбюджетной НИР «Анализ и оптимизация производительности широкополосной беспроводной сети протокола IEEE 802.16» (Per. № 01200603037), выполненной под руководством автора диссертации, в Санкт-Петербургском Государственном Университете Аэрокосмического Приборостроения (ГУАП) по заказу Федерального агентства по образованию.

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

Апробация работы. Основные результаты работы докладывались на следующих научно-технических конференциях: международной молодежной школе-семинаре БИКАМП'03 (Санкт-Петербург, 23 - 27 июня 2003 г.), VII научной сессии аспирантов ГУАП (Санкт-Петербург, 12-16 апреля 2004 г.), VIII научной сессии ГУАП (Санкт-Петербург, 11-15 апреля 2005 г.), на 16th Annual IEEE International Symposium on Personal, Indoor and Mobile Radio Communications -IEEE PIMRC'05 (Берлин, Германия, 11-14 сентября 2005 г.), политехническом симпозиуме «Молодые ученые - промышленности Северо-Западного региона» (Санкт-Петербург, 15 декабря 2005 г.), научной сессии ГУАП (Санкт-Петербург, 10 - 14 апреля 2006 г.), на 10th IEEE International Symposium on Consumer Electronics - ISCE'06 (Санкт-Петербург, 29 июня - 1 июля 2006 г.), Всероссийской школе-конференции «Мобильные системы передачи данных» (Москва, 11 -17 сентября 2006 г.), на 49th IEEE Global Telecommunications Conference -GLOBECOM'06 (Сан-Франциско, США, 27 ноября - 1 декабря 2006 г.), Всероссийской научно-практической конференции молодых ученых, аспирантов и студентов в рамках Программы «Участник молодежного научно-инновационного конкурса «Электроника 2006-2007» (Москва, 28 ноября 2006 г.), политехническом симпозиуме «Молодые ученые - промышленности Северо-Западного региона» (Санкт-Петербург, 8 декабря 2006 г.).

Публикации. По теме диссертационной работы опубликовано 17 печатных работ (из них 2 - статьи в ведущих научных журналах).

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

1). Метод расчета границ пропускной способности централизованной сети с резервированием посредством случайного доступа.

2). Метод расчета средней задержки передачи запроса для алгоритма случайного доступа стандарта IEEE 802.16;

3). Метод расчета средней задержки передачи запроса при использовании в IEEE 802.16 циклического опроса абонентов.

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

4.5 Выводы по главе

1) Работа метода циклического поллинга, используемого для управления передачей запросов в централизованной сети стандарта IEEE 802.16, описана с использованием методов теории цепей Маркова.

2) Разработан метод вычисления средней задержки при передаче запроса при использовании метода циклического поллинга для случая произвольной интенсивности входного потока.

3) Исследовано влияние шума в канале связи на производительность алгоритма BIB и циклического опроса.

4) Выполнен сравнительный анализ алгоритма ВЕВ и алгоритма циклического опроса в бесшумном канале и канале с шумом.

Заключение

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

2). Построены нижняя и верхняя границы пропускной способности централизованной беспроводной сети.

3). Найдено отношение длительностей интервала передачи пакетов и интервала передачи запросов, при котором пропускная способность сети максимальна.

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

5). Разработан метод вычисления распределения вероятностей числа абонентов в системе и средней задержки при передаче запроса с использованием алгоритма BEB для случая переменного числа активных абонентов.

6). Разработан метод вычисления средней задержки передачи запроса при использовании метода циклического поллинга для резервирования в IEEE 802.16 в случае произвольной интенсивности входного потока. Выполнен сравнительный анализ алгоритма BEB и алгоритма циклического опроса в бесшумном канале и в канале с шумом.

7). Разработан комплекс программ имитационного моделирования и численного расчета вероятностно-временных характеристик протоколов множественного доступа централизованных беспроводных сетей.

1. В.М. Вишневский, А.И. Ляхов, С.Л. Портной, И.Л. Шахнович, Широкополосные беспроводные сети передачи информации / М.: Техносфера, 2005, 592 с.

2. Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. ANSI/IEEE Std 802.11, 1999 Ed.

3. G. Bianchi, "Performance Analysis of the IEEE 802.11 Distributed Coordination Function," IEEE Journal On Selected Areas In Communications, 2000, Vol. 18, No. 3, p. 535 547.

4. B.M. Вишневский, Теоретические основы проектирования компьютерных сетей, М: Техносфера, 2003, 512с.

5. IEEE Std 802.16-2004 IEEE Standard for Local and Metropolitan Area Networks - Part 16: Air Interface for Fixed Broadband Wireless Access Systems.

6. H. Zimmermann OSI Reference Model — The ISO Model of Architecture for Open Systems Interconnection // IEEE Transactions on Communications, vol. 28, no. 4, April 1980, pp. 425-432.

7. D. Bertsekas and R. Gallager, Data Networks, Englewood Cliffs, NJ: Prentice-Hall, 1st ed., 1987; 2nd ed., 1992.

8. С.Г. Марковский, Управление доступом к общему каналу связи с использованием адресов абонентов для разрешения конфликтов, Автореферат диссертации на соискание ученой степени кандидата технических наук, ГУАП, СПб, 2006.

9. R. Rom, М. Sidi, Multiple Access Protocols (Performance Analysis), SpringlerVerlag, New York, etc., 1990, pp. 172.

10. N. Abramson, "The ALOHA system Another alternative for computer communications," Proc. Of Fall Joint Computer Conference, 1970, Vol.37, P. 281-285.

11. B. S. Tsybakov, "Survey of USSR Contributions to Random Multiple-Access Communications," IEEE Transactions on Information Theory, Vol. IT-31, No. 2, pp. 143-165, March 1985.

12. Б.С. Цыбаков, В.А. Михайлов "Свободный синхронный доступ пакетов в широковещательный канал с обратной связью," Проблемы передачи информ.1978, T. 14, №4, C. 32-59.

13. J.I. Capetanakis "Tree Algorithms for Packet Broadcast Channels // IEEE Trans, on Information Theory. 1979. V. 25. №5. p. 505-515.

14. G. Dimic, N.D. Sidiropoulos, R. Zhang, "Medium Access Control-Physical Cross-Layer Design," IEEE Signal Processing Magazine, September 2004, p. 40-50.

15. M.L. Molle, G.S. Polyzos, "Conflict resolution algorithms and their performance analysis," Technical report, University of Toronto, 1993.

16. B. Van Houdt, C. Blondia, "Robustness of Q-ary Collision Resolution Algorithms in Random Access Systems," Performance Evaluation, V.57,2004, P.357-377.

17. B. Van Houdt, C. Blondia "Throughput of Q-ary Splitting Algorithms for Contention Resolution in Communication Network," Communications in Information and Systems, Vol.4, No.2, P. 135-164,2005.

18. A. Ephremides and B. Hajek, "Information Theory and Communication Networks: An Unconsummated Union," IEEE Transactions on Information Theory, Vol. 44, No. 6, pp. 2416-2434, October 1998.

19. B. S. Tsybakov and N. B. Likhanov, "Upper Bound on the Capacity of a Random Multiple-Access System," Problems of Information Transmission, Vol. 23, No. 3, pp. 224-236, July-September 1987.

20. B. S. Tsybakov and V. A. Mikhailov, "Random Multiple Packet Access: Part-and-Try Algorithm," Problems of Information Transmission, Vol. 16, No. 4, pp. 305317, October-December 1980.

21. B. Hajek, N. B. Likhanov and B. S. Tsybakov, "On the Delay in a Multiple-Access System with Large Propagation Delay," IEEE Transactions on Information Theory, Vol. 40, No. 4, pp. 1158-1166, July 1994.

22. J. Weinmiller, M. Schlager, A. Festag, A. Wolisz, "Performance Study of Access Control in Wireless LANs IEEE 802.11 DFWMAC and ETSI RES 10 HIPERLAN," Mobile Networks and Applications, Vol.2, No. 1, 1997, P. 55-76.

23. L. Bononi, M. Conti, L. Donatiello, "Design and Performance Evaluation of Distributed Contention Control (DCC) Mechanism for IEEE 802.11 Wireless Local Area Network," J. Parallel Distrib. Comput, 2000, V.60, N.4.

24. T.S. Но, К.С. Chen, "Performance Analysis of IEEE 802.11 CSMA/CA Medium Access Control Protocol," Proc. PIMRC'96, October 1996, pp.407-411.

25. F. Cali, M. Conti, E. Gregoiy, "IEEE 802.11 Wireless LAN: Capacity Analysis and protocol enhancement," Proc. INFOCOM'98, San Francisco, 1998, P. 142-149.

26. V.M. Vishnevsky, A.I. Lyakhov, "IEEE 802.11 Wireless LAN: Saturation Throughput Analysis with Seizing Effect Consideration," Cluster Computing, Apr. 2002. V.5, N.2, P. 133-144.

27. А.В. Винель, "Исследование работы протокола IEEE 802.11 в канале с шумом," IV международная школа-семинар БИКАМП'ОЗ: Сб. тр., ГУАП, СПб, 2003, С. 171-174.

28. А.В. Винель, "Сравнение методов анализа работы протокола IEEE 802.11 при высокой нагрузке в канале с шумом," VII научная сессия аспирантов ГУАП: Сб. докл., ГУАП, СПб, 2004. С. 170-173.

29. Q. Ni, Т. Li, D. Malone, D. Leith, Y. Xiao and T. Turletti, "A new MAC Scheme for Very High-Speed WLANs," Proc. of IEEE Symposium of World of Wireless, Mobile and Multimedia Networks, 2006.

30. Vinel A., Zhang Y., Lott М., Turlikov A. "Performance Analysis of the Random

31. Access in IEEE 802.16," Proceedings of the 16th Annual IEEE International Symposium on Personal, Indoor and Mobile Radio Communications IEEE PIMRC'05, Berlin, Germany, 2005.

32. Vinel A., Zhang Y., Ni Q. and Lyakhov A., "Efficient Request Mechanisms Usage in IEEE 802.16," Proceedings of 49th IEEE Global Telecommunications Conference IEEE GLOBECOM'06, San Francisco, California, USA, November-December 2006.

33. Seo J.-B. and Lee H.-W., "Performance of IEEE 802.16 Random Access Protocol Steady State Queueing Analysis," Proceedings of 49th IEEE Global Telecommunications Conference - IEEE GLOBECOM'06, San Francisco, California, USA, November-December 2006.

34. Seo J.B. and Lee H.W., "Performance of IEEE 802.16 Random Access Protocol -Transient Queueing Analysis," Proceedings of 49th IEEE Global Telecommunications Conference IEEE GLOBECOM'06, San Francisco, California, USA, November-December 2006.

35. V.M. Vishnevsky, O.V. Semenova, "Mathematical methods to study the polling systems," Automation and Remote Control, 2006, Vol. 67, No. 2, pp. 173-220.

36. H. Takagi, "Analysis and applications of polling models," In: Performance Evaluation: Origins and Directions, Haring G., Lindemann Ch., Reiser M. eds. Lecture Notes in Computer Science, 2000, Vol. 1769, P. 423-442.

37. H. Takagi, "Queueing analysis of polling models: an update," In: Stochastic Analysis of Computer and Communication Systems, ed. Takagi H., North-Holland, Amsterdam, 1990. P. 267-318.

38. H. Takagi, "Queueing analysis of polling models: progress in 1990-1994," In: Frontiers in Queueing, ed. Dshalalow J.H., CRC, Boca Raton, FL, 1997, P. 119-146.

39. Borst S.C. Polling systems. Amsterdam: Stichting Mathematisch Centrum, 1996.

40. Rubin, "Access-Control Disciplines for Multi-Access Communication Channels: Reservation and TDMA Schemes," IEEE Transactions on Information Theory, Vol. IT-25, No. 25, pp. 516-538, September 1979.

41. B. S. Tsybakov and M. A. Berkovskii, "Multiple Access with Reservation," Problems of Information Transmission, Vol. 16, No. 1, pp. 35-54, January-March 1980.

42. S. Redana, M. Lott, "Performance Analysis of IEEE 802.16a in Mesh Operation Mode," The 13th 1ST SUMMIT, Lyon, France, June 2004.

43. S. Redana, M. Lott, A. Capone "Performance Evaluation of Point-to-Multi-Point (PMP) and Mesh Air-Interface in IEEE Standard 802.16a," IEEE VTC Fall' 04, Los Angeles, USA, 26.-29. Sept. 2004.

44. M. Lott, S. Redana, M. Carlozzo "Reducing the delay of IEEE 802.16a in multi-hop scenarios," World Wireless Congress, USA, May 2005.

45. Klein A., Pries R., Staehle D. "Performance Study of the WiMAX FDD Mode", Proceedings of the OPNETWORK 2006, Washington D.C., August 2006.

46. Doha A., Hassanein H. and Takahara G., "Performance Evaluation of Reservation Medium Access Control in IEEE 802.16 Networks," IEEE International Conference on Computer Systems and Applications, March 2006.

47. F. Baccelli and S. Foss, "On the Saturation Rule for the Stability of Queues," Journal of Applied Probability, 32, 2, pp. 494-507, 1995.

48. D. Aldous,"Ultimate Instability of Exponential Back-off Protocol for Acknowledgment-based Transmission Control of Random Access Communication Channels," IEEE Transactions on Information Theory, Vol. 33, No. 2, pp. 219-233, March 1987.

49. N.-O. Song, B.-J. Kwak and L. E. Miller, "On the Stability of Exponential Backoff," Journal of Research of the National Institute of Standards and Technology, Vol. 108, No. 4, pp. 289-297, July-August 2003.

50. A.B. Винель, B.A. Кобляков, A.M. Тюрликов, "Класс алгоритмов случайного множественного доступа с очередью для централизованных сетей передачи данных," Информационные технологии, № 5, 2007, с. 32-41.

51. A.V. Kobliakov, A.M. Turlikov, A.V. Vinel, "Distributed Queue Random Multiple Access Algorithm for Centralized Data Networks," Proc. of the 10th IEEE International Symposium on Consumer Electronics ISCE'06, St.-Petersburg, Russia, 2006, pp. 290-295.

52. Винель А.В., "Высокоскоростной алгоритм случайного доступа для централизованной сети передачи данных," Сб. тр. Российской школы-конференции «Мобильные системы передачи данных» / МИЭТ, Москва, 2006, с. 55-57.

53. R. Schwartz. (January 19, 2001). Proposal on traffic models. IEEE 802.16 Contribution 802.16.3p-01/27.

54. J. Huang. (January 23, 2001). Presentation for generalizing 4IPP traffic model for IEEE 802.16.3. IEEE 802.16 Contribution 802.16.3p-00/58.

55. C. R. Baugh and J. Huang. (March 2, 2001). Traffic model for 802.16 TG3 MAC/PHY simulations. IEEE 802.16 Contribution 802.16.3c-01/30rl.

56. C. R. Baugh. (October 31,2000). 4IPP traffic model for IEEE 802.16.3. IEEE 802.16 Contribution 802.16.3c-00/51.

57. Ю.Б. Нечаев, АЛО. Савинков, E.B. Шадчнев, C.A. Филин, "Обзор математических моделей формирования трафика для моделирования системного уровня беспроводных сетей передачи данных по стандарту IEEE 802.16," Сборник докладов конферении RLNC, Воронеж, 2005.

58. А.В. Винель, "Анализ случайного доступа протокола IEEE 802.16 при большом числе абонентов," VIII научная сессия ГУАП: Сб. докл. / ГУАП, СПб, 2005, с. 272-275.

59. Винель А.В. Анализ механизмов передачи запросов по протоколу IEEE 802.16 в канале с шумом // Сб. тр. Политехнического Симпозиума "Молодые ученые промышленности Северо-Западного Региона", декабрь 2006 / ГПУ, СПб, 2006, с. 51-52.

60. Q. Ni, A. Vinel, Y. Xiao, A. Turlikov, Т. Jiang, "Investigation of Bandwidth Request Mechanisms under Point-to-MuItipoint Mode of WiMAX Networks," IEEE Communications Magazine, № 5,2007.

61. Г.С. Евсеев, Н.Г. Ермолаев, "Разрешение конфликтов в канале со свободным доступом и шумом," Проблемы передачи информации, 1982, т. 18, № 2, с. 101-105.

62. M. Lott, A. Vinel, Y. Zhang, "Propagation Modeling for Systems Beyond 3G," Proc. of the International Wireless Summit 2005 WPMC'05, Aalborg, Denmark, 2005.