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

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

(762

Шпилев Сергей Алексеевич

Исследование механизмов управления и оценка производительности широкополосных беспроводных сетей передачи информации под управлением протокола

IEEE 802.11

Специальность 05.13.13 — Телекоммуникационные системы и компьютерные сети

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

1 2 ДЕК 2008

Москва — 2008

003457762

Рабо.та выполнена в Учреждении Российской академии наук Институте проблем передачи информации им. A.A. Харкевича РАН

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

Вишневский Владимир Миронович

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

Саксонов Евгений Александрович доктор физико-математических наук, профессор Рыков Владимир Васильевич

Ведущая организация: Институт программных систем РАН

Защита состоится 22 декабря 2008 г. в 11 часов на заседании диссертационного совета Д.002.077.01 при Учреждении Российской академии наук Институте проблем передачи информации им. A.A. Харкевича РАН по адресу: 127994, г. Москва, ГСП-4, Большой Каретный пер., д. 19, стр. 1.

С диссертацией можно ознакомиться в библиотеке Учреждения Российской академии наук Институте проблем передачи информации им. A.A. Харкевича РАН.

Автореферат разослан 20 ноября 2008 г.

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

диссертационного совета Д.002.077.01, доктор физико-математических наук

И.И. Цитович

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

Актуальность темы диссертации. В последние годы псе большую популярность завоевывают беспроводные сети передачи информации. Это связано с легкостью и быстротой их развертывания, простотой в обслуживании и другими их преимуществами. При этом, среди беспроводных сетей передачи информации наибольшее распространение получили широкополосные беспроводные сети передачи информации (ШБС) под управлением протокола IEEE 802.11, известные также как Wi-Fi. Успех данного протокола объясняется высокими скоростями передачи данных (до 300 Мбит/с для нового стандарта IEEE 802.11ц), широким набором сервисов, огромным диапазоном устройств, представленных на рынке, поддерживающих данный стандарт сетей. Так в настоящее время большинство современных ноутбуков, КПК, смартфонов и даже многие модели цифровых фото- и видеокамер, принтеров и цифровых фоторамок используют Wi-Fi сети. В крупных городах мира, таких как Москва, Париж, Мельбурн и др. Wi-Fi доступ к Интернету есть практически повсеместно, а в большинстве аэропортов и многих кафе по всему миру беспроводный доступ к Интернету и вовсе бесплатный. Таким образом, исследование локальных сетей передачи информации под управлением протокола IEEE 802.11 является весьма актуальным.

Кроме беспроводных локальных сетей передачи информации Wi-Fi может применяться и для развертывания региональных сетей, для чего на его основе могут строиться многокилометровые каналы точка-точка, обеспечивающие связь областей с областными центрами. Такой подход позволит наиболее дешево и эффективно обеспечить отдапенные регионы доступом в Интернет, телефонной связью и телевидением. Такое применение ШБС, в том числе, помогло в реализации национального проекта "Образование" при обеспечении школ доступом в Интернет. Такой же подход позволит решить проблему "информационного неравенства".

Новым и наиболее многообещающим направлением развития протокола IEEE 802.11 является дополнение IEEE 802.11s, известное, как mesh-ceni. Одним из главных принципов построения mesh-сети является принцип самоорганизации архитектуры, обеспечивающий следующие возможности: реализацию топологии сети "каждый с каждым"; устойчивость сети при отказе отдельных компонентов; масштабируемость сети: увеличение зоны информационного покрытия в режиме самоорганизации; динамическую маршрутизацию трафика, контроль состояния сети и т. д.

Для вышеперечисленных задач характерно использование сетей с различными топологиями. При каждой топологии используются различные функ-

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

Исследованию ШБС и механизмов, используемых при их построении, посвящено значительное количество работ российских и зарубежных ученых: О.М. Брехова, В.А. Васенина, В.М. Вишневского, B.C. Жданова, А.П. Кулешова, А.И. Ляхова, И.А. Мизина, В.В. Рыкова, Е.А. Саксонова, G. Ash, G. Bianchi, S. Borst, O. Boxma, F. Cali, M. Conti, R. G. Gallager, L. Kleinrock, P. Kyasanur, M. Neuts, C. Perkins, E. Royer, H. Takagi и др. Обзор работ, посвященных каналу точка^точка, приведен в главе 2, региональным беспроводным сетям - в главе 3, mesh-сетям - в главе 4 диссертации. Однако круг нерешенных задач непрерывно растет, и модели, построенные всего несколько лет назад, уже не удовлетворяют всем требованиям и особенностям современных протоколов. Так, например, несмотря на распространение идеи об использовании Wi-Fi при построении региональных сетей и появлении на рынке устройств, пригодных для организации многокилометровых каналов, особенности работы протокола в данном случае до сих нор остаются неисследованными. В сетях с централизованным управлением остается немало неизученных механизмов опроса, которые могут быть реализованы в современном оборудовании, что значительно улучшит дифференциацию качества обслуживания, уменьшит дрожание задержек и т. д. К современным протоколам маршрутизации, предложенным в mesh-сетях, предъявляются характерные для таких сетей требования и, следовательно, необходимы новые модели для оценки эффективности данных протоколов. Таким образом, интенсивное развитие широкополосных беспроводных технологий привело к необходимости исследования новых моделей, которые и рассматриваются в настоящей диссертационной работе.

Целью диссертационной работы является разработка и исследование моделей функционирования ШБС под управлением протокола IEEE 802.11: оценка производительности и выбор оптимальных параметров для различных видов топологии, в том числе точка-точка, точка-многоточка и mesh; и различных функций управления, включая централизованную, распределенную и гибридную.

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

Научная новизна работы заключается и комплексном исследовании основных видов топологии и механизмов управления ШБС под управлением протокола IEEE 802.11: аналитическом и имитационном моделировании канала точка-точка произвольной длины и с различными функциями управления; моделировании адаптивного механизма опроса со шлюзовой дисциплиной обслуживания; изучении и сравнении протоколов маршрутизации в новых inesli-сстях стандарта IEEE 802.11s.

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

1. Разработка аналитической и имитационной моделей канала точка-точка произвольной длины под управлением протокола 1ЕЕЕ 802.11 с распределенным или гибридным управлением в режиме насыщения и с распределенным управлением в режиме нормальной нагрузки с ограниченными очередями.

2. Исследование ШБС под управлением протокола IEEE 802.11 с централизованным управлением с использованием аналитической и имитационной моделей системы адаптивного поллинга.

3. Проведение сравнительного анализа протоколов маршрутизации OLSR и HWMP в mesh-ссти под управлением протокола IEEE 802.11s с использованием имитационного моделирования.

4. Разработка программного комплекса, объединяющего в себе все перечисленные модели, позволяющего провести аналитическое или имитационное моделирование сетей передачи информации под управлением протокола IEEE 802.11 с различными механизмами управления и топологиями.

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

• Федеральной целевой программы "Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса

России на 2007-2012 годы", проект 2007-4-2.4-00-03-004 "Разработка интегрированной технологической платформы для мониторинга элементов и систем жизненно важной инфраструктуры на основе информационно-коммуникационных технологий расширенного Интернета";

• Программы фундаментальных исследований Отделения нанотехноло-гий и информационных технологий РАН (ОНИТ РАН) "Новые физические и структурные решения в инфотелекоммуникациях" проекта 3.2 - Структура и методы построения инфокоммупикационных сетей;

• Гранта РФФИ № 08-07-90102 "Разработка методов и алгоритмов исследования протоколов передачи мультимедийной информации в широкополосных беспроводных сетях с централизованным управлением".

Результаты работы также используются в курсах "Протоколы и стандарты телекоммуникационных сетей", "Математические и имитационные модели телекоммуникационных сетей" и "Моделирование сстсй", которые читаются студентам Московского физико-технического института (ГУ).

Апробация результатов работы. Основные результаты диссертации докладывались и обсуждались на:

• Третьей международной конференции по проблемам управления Института проблем управления (Москва, 2006);

• Международном семинаре "Распределенные компьютерные и телекоммуникационные сети. Теория и приложения" (София, Болгария, 2006; Москва, 2007; София, Болгария, 2008);

• 19-й международной научной конференции "Математические методы повышения эффективности информационно-телекоммуникационных сетей", (Гродно, Белоруссия, 2007);

• 30-й и 31-й конференциях молодых ученых и специалистов ИППИ РАН "Информационные технологии и системы" (Звенигород, Россия, 2007; Геленджик, Россия, 2008);

• Третьей всероссийской молодежной научной конференции по проблемам управления (Москва, 2008);

Публикации. По теме диссертации опубликовано 15 научных работ, список которых приведен в конце автореферата. Из них 5 статей в научных журналах, 10 статей в сборниках материалов научных конференций. Кроме того, получен 1 патент на полезную модель, поданы 2 заявки на изобретение и 1 заявка на свидетельство об официальной регистрации программ для ЭВМ.

Структура ii объем диссертационной работы. Диссертация состоит из списка условных обозначений и сокращений, введения, пяти глав, заключения и списка литературы, включающего 88 наименований. Работа изложена на 125 страницах и содержит 17 рисунков и 14 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ

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

В первой главе представлены принципы построения и особенности ШБС. В разделе 1.1 дается общее описание ШБС, история их развития, классификация и текущее положение дел. В разделе 1.2 более детально рассмотрено семейство протоколов IEEE 802.llx, его физический уровень и уровень управления доступом к среде. Представлены особенности и отличия различных версий протокола и дополнений к нему (IEEE 802.Ha/b/g/e/s). Описаны функции управления, включая последнюю из предложенных - функцию гибридного управления (HCF) и две основные - функции централизованного и распределенного управления. В разделе 1.3 приведены основные виды топологий сети - точка-точка, точка-многоточка или сота и mesh, и даны области их применения.

Во второй главе проведено исследование простейшей из топологий сети -канала точка-точка с различными функциями управления, представлен обзор литературы по данной тематике. В разделе 2.1 дан краткий обзор возможных методов повышения производительности канала точка-точка, описаны проблемы, возникающие при построении многокилометровых каналов и их особенности. В разделе 2.2 исследованы две аналитические модели, описывающие канал точка-точка как в режиме насыщения (в том числе и многокилометровый канал), так и в режиме нормальной нагрузки. В подразделе 2.2.1 представлена модать широкополосного беспроводного канала точка-точка в режиме насыщения. Согласно подходу Бьянки в модели используется дискретная целочисленная шкала времени, в которой t и f + 1 соответствуют началу двух последовательных виртуальных слотов. Виртуальным слотом называется интервал времени между двумя последовательными изменениями счетчика отсрочки. Виртуальные слоты имеют разную длину. Каждый из них может быть: 1) "пустым" слотом отсрочки а, когда ни одна станция ие передает, 2) "успешным" слотом, когда одна и только одна станция передаст и 3) "коллизионным" слотом, когда две или более станций пробуют передать одновременно.

Рассмотрена сеть состоящая из п узлов. Заметим, что в начале каждого слота все станции сети имеют одинаковую вероятность т начать отправку пакета. В модели Кали время отсрочки Ь предполагается независящим от количества попыток послать текущий пакет пс, и имеет геометрическое распределение: Р{Ь = к} = т(1 — т)к,к > 0. Однако т выбирается с учетом реального правила отскрочки и вероятности коллизии. Таким образом, вероятности возникновения "пустого" (ре), "успешного" (р5), и "колизионного" (рс) слотов определяются равенствами

ре = (1-тР, р, =пт(1-т)п-\ рс=1-(1-т)п-пт(1-т)п-\ (1)

Для упрощения дальнейшего анализа предполагается, что используется только базовый механизм доступа к среде, и считается, что все пакеты в сети имеют одинаковый размер. Обозначим длительности слотов в случае короткого канала точка-точка верхним индексом 0; в случае многокилометрового канала точка-точка при условии, что Н + Р < 25 - индексом s; и при условии, что Н + Р > 25 - индексом I. Здесь Р и Я - времена, необходимые для передачи данных и заголовка пакета данных соответственно. Разделение случая многокилометрового канала на два типа связано с тем, что при коротком пакете в случае коллизии одна станция все же успешно передает пакет, а при длинном пакете коллизия происходит практически так же, как и в случае короткого канала точка-точка. Таким образом, длительности "успешного" и "коллизионного" слотов - Ts и Тс задаются выражениями

T^ = H + P + tACK+ SIFS + DIFS, = Я + Р + ACK_TimeOut, (2) Tss = Т* = Я + Р + tACK + 25 + SIFS + DIFS, (3)

T\=TS, = H + P + 25 + EIFS. (4)

Рассмотрим временной интервал tv между двумя последовательными успешными передачами, который будем называть виртуальным временем передачи. Тогда пропускная способность в режиме насыщения S определяется формулой S = где E[tv] - среднее значение tv, a Vc - номинальная скорость передачи данных в канале.

Как в случае короткого, так и в случае многокилометрового канала при условии Н + Р > 25 виртуальное время передачи может состоять из I > 1 виртуальных слотов, где последний слот "успешный", к слотов "коллизионные" [к = 0,1 - 1) и / - 1 - к слотов "пустые", то есть t°v = + кТ? + (I - 1 - к)а. Таким образом,

+ + (5)

Ps Ps

Однако, п случае многокилометрового канала при условии Н + Р < 2<5 в случае возникновення коллизии одна из станций, тем не менее, успешно передает свой пакет. Поэтому виртуальное время передачи может состоять из I > 1 виртуальных слотов, где последний слот "успешный" или "коллизионный", а оставшиеся I - 1 слотов "пустые", то есть £f - 7'/ + {I - шш t" = Tg -I- (I — 1 )cr. Таким образом,

1-A + (1-й)1 ■ (6)

Чтобы определить пропускную способность S в режиме насыщения, остается найти т. Конкурентное окно при ¿-ой посылке пакета задастся выражением

_ Г CWmin2\ при i < т;

1 [ GWmaz = cwmln2m, при i > т.

Воспользуемся формулой т = 2/(£[ги] + 1) и леммой, которая гласит: если количество повторных посылок пакета ограничено числом R, то среднее конкурентное окно £■[«>] определяется следующими формулами:

{ELp^W, + ¿И} X при л < т и

{E-li + Wm - I» + 2У + } iffi, в против-

ном случае. Здесь р = 1 — (1 — r)n_1 - вероятность того, что данная попытка передачи оказалась неуспешной. В случае канала точка-точка р = г.

Далее, численными методами находим г и подстановкой его в (1)-(6), получаем пропускную способность канала точка-точка во всех описанных случаях.

В случае использования функции централизованного или гибридного управления в режиме насыщения, осуществляется неконкурентный доступ к среде, а в этом случае нет коллизий и отсрочки посылки пакетов. Вместо пакетов данных и подтверждений координатор использует пакет D + А + Р - данные с подтверждением и опросом, а вторая станция использует пакет D + А - данные с подтверждением, что разрешено стандартом IEEE 802.11, для минимизации накладных расходов. При этом размеры этих пакетов равны размеру обычного пакета данных. В этом случае виртуальное время передачи задается формулой tv = H + P+S + SIFS, и, следовательно, S =

В подразделе 2.2.2 представлен матричный метод анализа ШБС с протоколом IEEE 802.11 и ограниченными очередями при нормальной нагрузке. Стохастическое поведение станции моделируется цепью Маркова, где станция может быть в одном из следующих состояний: простоя, отсрочки, передачи и заключительной отсрочки.

Будем различать два типа передач: 1) синхронные передачи, выполняемые

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

Пусть x(t) - случайный процесс, описывающий число пакетов в очереди данной станции в момент времени t, с пространством состояний {0,1,..., К}. Буфер каждой станции предполагается конечным и равным К. Пусть s(t) -случайный процесс, описывающий стадию отсрочки в момент времени t, с пространством состояний {0,1,..., /}. s(t) представляет собой число неудачных передач первого пакета в очереди. Пусть W = CWmin. Тогда W; = 2mm^'m^W, где 0 < i < I, а тп находится из условия CW„mx = 2mCWmin. Если пакет передан неудачно на максимальной стадии отсрочки I, он отбрасывается. Пусть b(t) - стохастический процесс, описывающий счетчик отсрочки данной станции в момент времени t, с пространством состояний {0,1,..., И7, — 1}, определяемым стадией отсрочки г. Применяется дискретная целочисленная шкала времени, идентичная предложенной в предыдущей модели.

Считаем, что при каждой попытке передачи независимо от числа предшествующих попыток пакет попадает в коллизию с постоянной вероятностью р: р - это условная вероятность коллизии, т. е. это вероятность попадания в коллизию пакета, передача которого началась. Вероятность р тесно связана с вероятностью т того, что станция передает синхронно в произвольно выбранном слоте, и эта связь будет отражена далее уравнением (8). Введем также вероятность та того, что станция передает асинхронно. Далее будем считать, что все информационные пакеты имеют фиксированный размер, одинаковый для всех станций, и канал занимается на время Тр при каждой передаче кадра DATA. Пакеты поступают в соответствии со стационарным пуассоновским потоком с параметром Л. Сеть состоит из п станций.

Можно выделить следующие типы слотов:

• пустой слот ст, когда ни одна станция не передаст;

• успешный слот, когда только одна станция передает синхронно; длительность этого слота составляет Ts = Тр + SIFS + îack + DIFS; tACK - время передачи подтверждения;

• коллизионный слот, когда две или более станции передают синхронно; длительность этого слота равна Тс = T¡, + АСК JTimeOut, где АС К JTimcOut = S1FS + а+25 мкс;

• асинхронный слот, когда одна из станций передает асинхронно; средняя длительность этого слота равна Та = Ts 4- a¡1.

Случайный процесс & = {x(t), s(t), &(<)}, t > 0 - вложенная цепь Маркова. Пространство состояний этой цени: {(0,j),0 < j < w - l}(J{{k,i,j) : 1 < k < К, 0 < i < 1,0 < j < Wi - 1}. Здесь (0, j), j = 1, W - 1, - состояние заключительной отсрочки с текущим значением счетчика, равным j; (0,0) -состояние простоя. Для дальнейшего анализа введем ряд вероятностей.

• Ре - вероятность того, что случайно выбранный слот является пустым при условии, что данная станция не передает, Ре = (1 — т — та)п~1.

• Р, - вероятность того, то случайно выбранный слот является успешным при условии, что данная станция не передаст, Ps = (п — 1)т(1 — т)"~2.

• Ра - вероятность того, что случайно выбранный слот является асинхронным при условии, что данная станция не передает, Ра = (п — 1)та(1 — г)"-2.

• Рс - вероятность того, что случайно выбранный слот является коллизионным при условии, что данная станция не передает, Рс = l—Pe—Ps—Pa.

• rt, Si, cii и ti - вероятности того, что данная станция генерирует (т. е. в ее очередь поступают) i пакетов в течение соответственно пустого, успешного, асинхронного и коллизионного слота,

г! i\ г\

Так как пХа <<1, можно считать, что не более одного пакета может поступить в очереди всех станции за время а, т. е. Г\ к Аае~Ха ~ Лег и r¿ и 0 при i > 1. По той же причине a¿ ~ s¡.

• qt - вероятность того, что i пакетов поступит в очередь данной станции за случайно выбранный слот при условии, что данная станция не передает, ql = Per¿ + Pss¡ + Pas¡ 4- PCU-

Отсюда получаем следующие вероятности одношаговых переходов:

Р{(0,0)|(0,0)} = qo+süriPe/W: ни одного пакета не поступило за слот, либо 1) пакет поступает в пустую очередь станции находящейся в состоянии простоя, в слоте, когда ни одна станция не передает синхронно, и, следовательно,

пакет передается асинхронно; 2) больше ни одного пакета не поступает в очередь данной станции в течение данной асинхронной передачи, что означает переход в состояние заключительной отсрочки; 3) время отсрочки выбирается равным 0, поэтому станция возвращается в состояние простоя.

Р{(0, j)|(0,0)} = soriPe/W, 1 < j < W — 1: пакет поступает в пустую очередь станции в состоянии простоя в течение слота, когда ни одна станция не передает синхронно, и, следовательно, пакет передается асинхронно. В течение этой передачи больше ни одного пакета не прибывает в очередь данной станции, и станция переходит в состояние заключительной отсрочки с начальным значением счетчика j > 0.

Р{(к, 0, j)|(0,0)} = ЫпРе + PS + Ра) + tkPc)/W, l<k<K,0<j< W — 1: либо 1) пакет, поступающий в пустую очередь станции, передается асинхронно, и в течение этой передачи в очередь данной станции поступает еще к пакетов, либо 2) слот, в начале которого данная станция была в состоянии простоя, оказывается непустым, и в течение него (включая завершающий IFS интервал) в очередь данной станции поступает к пакетов.

P*{(tf,0,j)|(0,0)} = [(1 - Ем*к){пРе + ps + Ра) + (1 -Ylk=o tk)Pc\!W, 0 < j < W — 1: аналогично предыдущему выражению, но в очередь данной станции поступает не менее К пакетов.

Р{(к, 0,j —1)|(0, j)} =qk, 1 <к < К, 0 < j < W — 1: к пакетов прибывает в очередь данной станции в течение слота, когда она находилась в состоянии заключительной отсрочки со значением счетчика j.

P*{(K,0,j - 1)1(0, j)} = 1 - Ylk~o 1к, 0 < j < W - 1: не менее К пакетов прибывает в очередь данной станции в течение слота, когда она находилась в состоянии заключительной отсрочки со значением счетчика j.

~ 1)|(0, j)} = ço, 0 < j < W — 1: ни одного пакета не прибывает в очередь данной станции в течение слота, когда она находилась в состоянии заключительной отсрочки со значением счетчика j.

^{(0.j)l(M,0)} = (1 -p)sQ/W: 0<j<W~l, 0 < г < / — 1: последний пакет в очереди передается успешно, и ни одного пакета не прибывает в очередь данной станции в течение этой передачи.

P{(0,j)|(M,0)} = [(1 - p)s0 +pt0}/W, 0 < j < W - 1: последний пакет в очереди передается успешно или отбрасывается на максимальной стадии отсрочки 7, и ни одного пакета не прибывает в очередь данной станции в течение этой передачи.

P{(k + l,i,j- l)|(M,j)} = а, 1 <к<К, 0 < I < К-к, 0 < г < 1,1 < j < Wi — 1: I пакетов прибывает в очередь данной станции в течение слота, когда эта станция не передает.

Р*{{К^з - 1)|(м,:;)} - 1 - ЕЙ*-1®, 1 < к < К, 0 < г < 7, 1 < з < Щ — 1: не менее чем К — к пакетов прибывает в очередь данной станции в течение слота, когда эта станция не передает.

Р{(к — 1 + 0)} = (1 I < к < К, 0 <1<К-к, 0 <

г < 7 — 1,0 < < И^ — 1: пакет передается успешно, и I пакетов прибывает в очередь данной станции в течение этой передачи.

Р*{(К,0,Л |(М,0)} = (1 -р)(1 - 1<к< К, 0<г<

7—1,0 < з < И' — 1: пакет передается успешно, и более К — к пакетов прибывает в очередь данной станции в течение этой передачи.

Р{(к - 1 + 1,0,^1(^,7,0)} = [(1 - р)з, + ри]/\У, 1 < к < К, 0 < I < К — к, 0<j<W-l: последний пакет в очереди передается успешно или отбрасывается на максимальной стадии отсрочки 7, и I пакетов прибывает в очередь данной станции в течение этой передачи.

Р*{(7Г,0,7)|(/с,7,0)} = [(1 - р)( 1 - +Р(1 - 1 <

к < К, последний пакет в очереди передается успешно или

отбрасывается на максимальной стадии отсрочки 7, и более чем К— к пакетов прибывает в очередь данной станции в течение этой передачи.

р{(к + 1,1 + и)|(М,о)} = ри/шнь 1 < к < К, 0 < I < К- к, 0 < ¿<7—1, 0 < j < \¥{+1 — 1: пакет передается неудачно из-за коллизии, и I пакетов прибывает в очередь данной станции в течение этой коллизии.

Р*{(К,г + и)|(М,0)} = р( 1 - Еьо^ММ+ь l<k<K>Q<i<

7—1, 0 < з < \Vi-i-i — 1: пакет передается неудачно из-за коллизии, и не менее чем К — к пакетов прибывает в очередь данной станции в течение этой коллизии.

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

"О» Ах Аг Лз л4 ■■■ Ак

С1 Вх в2 Вз ВА ■■■ в-к

О с2 Вг Вг В3 ВК-1

О О с2 Вг в2 ••• в*к_2

О О О с2 в1 ••• В*к_ з

о О О О С2 В[ _

Р =

- матрица размерности (ТУ + 0К) х (IV + РК), где

(2т+1 - 1)1-7, тп > I,

(2"»+1 _ I + 2т(1 - т))Ш, т < I.

(7)

Ввиду схожести вида блоков матрицы Р введем матрицу размерности ахЬ:

Ga,b(x> У) -

a; x ■ ■ X X

г/ 0 •• • 0 0

0 y ■ • 0 0

0 0 •• • У 0

Далее приводятся блоки матрицы Р. Матрицы Q, i = 0,1,2, определяются следующим образом:

Г4- son Ре , . Son P<L Wl-P«'

40 ~ w w w w

q0 0 • • ■ 0 0

0 Cn • ■ • 0 0

C0 =

Ci =

0

9o 0

9o

■ матрица размерности W x W,

Cío Cu

C12 Cu

- матрица размерности /3 x W, где

Cu = Gwyv O), 0 < i < I - 1, Cu = ((1-t;+p'°, O) ,

C*2 = [Ci O] - матрица размерности /3 x fi.

M — \Gw,w (xí, z¡) O] - матрица размерности W x p, где = и г, = q¡ при г < К, хк = Р*{(К,0,з)\М} и

Д: =

И 0 ■ Z?x /'i Я2 • Дг 0 f2 •

0 0 О 0 0 О

матрица размерности Р х /3, блоки

D/_i 0 0 Ei

^ D¡ 0 0 • • • О Fj

матрицы В* определяются аналогично и помечены верхним индексом *.

D = Gw,w (^"jp*, q,-ij , D* - Gw,w

Dj = GWj,w ,Z>; = («,,0), j = 17^1,

Dj = Gw„w 0),D} = Gw,,w (9,0),

E3 = GW,.!,™, (^птр0) = Gwj-uWj {Ы,0), j — 1,7,

Fo = Cwj.Wj (0, , F* = Gw„w, (0, m,), j = 1, /,

где = (1 -p)(l - m, = 1 -

9 = P*{(Ä-,0,i)|(Ä- + 1 -¿,/,0)} и Л, =p(l - Tïi=0~2ti)/Wr

Введем стационарные вероятности *rtly = lim P{(x(t), s(t), b(t)) = (Ä,i,j)}, tt0j - lim P{x(t) = 0,b(t) = j}.

I—>OQ t—»00

Также пусть 7rfc = (я^до , Tt,o,i, ■ ■ •, jry.wy-iX к - = (тг0,о, • • •, Ko.w-i)-

îto и iî/t, k > 1, - векторы стационарных вероятностей состояний на уровне fc, упорядоченные в лексикографическом порядке возрастания компонент i и j. Распределение стационарных вероятностей тг = (яо,..., получено методом матричного анализа.

С использованием стационарных вероятностей {тгь, к > 0}, получены вероятности т и тц того, что станция передает синхронно и асинхронно в произвольно выбранном слоте: К I

Г = та - ЩопРе, P=l-(l-r)n"1. (8)

к=1 i=0

Система (8) с тремя неизвестными г, т0 и р решается численными методами.

Вероятность потери пакета является важным показателем качества обслуживания (QoS) для большинства сетевых приложений. Согласно правилам IEEE 802.11 DCF, пакет отбрасывается при достижении предела 7 повторных попыток передачи, т. е. если все 7+1 последовательных попыток передачи этого пакета оказались неудачными. Вероятность потери пакета, передаваемого синхронно, равна pI+l, в то время как пакеты, передаваемые асинхронно, не теряются вовсе. Таким образом, вероятность потери пакета равна Ploss = где г] - доля пакетов, передаваемых синхронно, которая

и должна быть найдена.

Среди всех пакетов, прибывающих на данную станцию в течение случайно выбранного слота, не более одного пакета передается асинхронно, и вероятность такой передачи равна та. Поэтому rj = NÇr", где Ns - среднее количество пакетов, прибывающих на станцию за слот. Вычисляя это количество для каждого из возможных состояний и учитывая, что новые пакеты могут поступить в очередь данной станции, пока она передает пакет асинхронно,

получаем:

^ = та(1+Л7:,)+тго,оЛ[(Р5+Ра)Т8+РсТс]+Л^(1-7г0,о-т)+Лт[(1-р)Т5+рТс],

где tsl0t = Реа + Р/Гц + РаТа + РСТС - средняя длительность слота при условии, что данная станция не передает.

Очевидно, вероятность потери пакета непосредственно определяет пропускную способность сети Т в условиях нормальной нагрузки:

т = (1 - Ршэ)п\. (9)

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

В третьей главе рассматривается сеть с топологией точка-многоточка или сота. В данном случае оптимальным решением является централизованный механизм управления, неотъемлемой частью которого является опрос станций (иоллинг). Приведен обзор литературы посвященной различным моделям поллинга. В разделе 3.1 представлен собственно обзор механизмов опроса, их классификация и особенности. В разделе 3.2 представлена разработанная в данной работе система поллинга с адаптивным опросом и ее аналитическая модель. Система поллинга состоит из N очередей со шлюзовым обслуживанием. Поток заявок в г-ю очередь пуассоновский с параметром А,; время обслуживания заявки распределено экспоненциально с параметром щ; время подключения сервера к очереди также полагаются экспоненциально распределенными с параметром 1 /д^ Время простоя сервера распределено экспоненциально с параметром 1 /т. Пусть также р — к/^г ~~ загрузка системы. Для такой системы получены среднее время цикла и вероятность опроса очереди в цикле, для чего использован приближенный подход, основанный на описании адаптивной схемы с помощью схемы Вернулли с набором вероятностей (их,... ,ик), 0 < щ < 1, г = 1,ДГ. Сервер обслуживает г-ю очередь в цикле с вероятностью щ, ас противоположной вероятностью 1 — щ сервер перемещается к следующей очереди. I

Среднее время цикла определяется равенством

С = +rH.ii (1-ш) (10)

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

Вероятность и,- того, что очередь в цикле опрашивается, определяется равенством

1

--1 + е-д.о (П)

Равенства (10) и (11) дают систему уравнений для нахождения неизвестных С и щ,... ,идт.

Далее представлен анализ системы с адаптивным опросом методом средних. Обозначим через V, среднее время, которое сервер проводит у г-й очереди за цикл, г = 1, ЛГ. Полагаем, что за время простоя, когда все очереди должны быть пропущены, сервер уделяет каждой очереди в среднем т/М времени. Величина и, определяется равенством

N

V., = р,С + ды + г = 1, Ы, где у = Д(1 - щ).

1=1

Определим (г, ^')-й период как сумму последовательных времен посещения, начиная от г-й очереди. Среднее для этого периода определяется равенством, у^ = Еп^Г1 ^ 3 ~

Доля времени, которое занимает (г,_;)-й период, есть величина

У{ , -

Обозначим через Ь^ среднюю длину г-й очереди в произвольный момент посещения сервером ^'-й очереди, I,] = Соответствующая безусловная средняя длина г-й очереди определяется как Ц = г = 1, N.

Поскольку дисциплина обслуживания является шлюзовой, значение Ь^ в случае г = 3 разлагается на сумму двух величин ¿¡- и где Д - среднее число заявок, которое осталось обслужить серверу в г-й очереди, начинал с произвольного момента ее обслуживания, а - среднее число заявок, которое поступило в очередь за прошедшее время посещения сервером ^'-й очереди, и будет обслужено при следующем посещении. В случае г / ] имеем = ¿¿¿. Таким образом, Ь10 = + Ь,^, 1,3 = 1,-ЛЛ

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

N

и = ¿, + = ^ Чп,\и,п + ¿г<?гД, г = 1, ЛГ. (12)

П=1

Заявки, находящиеся в очереди в произвольный момент периода (г,]), - это заявки, поступившие за прошедшее время этого периода, и заявки, поступив-

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

(+.7-1 / N \

Е-

£г Чи

* 1J -*• 1

ЕЧп,1 г \ ,.1 _ ui - У ST

-и,п = Аг Vij 4- --;— у дтит

" 1 - р + pi ¿—I

' т=1

\ mj-i /

t,j = l,iv.

Подстановкойз-И находим Ьг = Аг { 4- \ Е 9тит ) ■

\ 1 гп=1 I

\ т^г /

Воспользовавшись формулой Литтла вычисляем средние длины очередей

Li = (1 +Pi)Xi

( _ _

+ ~---У^ЗтИт!, i = l,N.

i-P + fb£i 1

\ тфг

Зная Ц, можно вычислить среднее время ожидания W{ = Li/А,- и выразить Li из уравнения 12.

В разделе 3.3 описывается имитационная модель систем поллинга и ее возможности. Приводятся результаты численного исследования представленных моделей.

Четвертая глава посвящена новому варианту топологии ШБС - mesh-сети. В ней приведен краткий обзор литературы посвященной вопросам маршрутизации вообще и маршрутизации в беспроводных, в том числе mesh, сетях. В разделе 4.1 дается краткий обзор стандарта IEEE 802.11s, особенности таких сетей и их преимущества. В разделе 4.2 разъясняется ключевая роль механизмов маршрутизации при построении mesh-cereft, дается описание предложенного в стандарте протокола маршрутизации, а также описаны некоторые другие протоколы маршрутизации применимые в mesh-сетях. В разделе 4.3 описаны возможности построенной имитационной модели mesh-сети, приведены полученные с ее помощью результаты моделирования. Дана оценка выявленных сильных и слабых сторон протоколов.

В пятой главе представлен программный комплекс, который объединяет в себе все разработанные и описанные в работе аналитические и имитационные модели. Комплекс состоит из трех блоков: графического пользовательского интерфейса; программных модулей аналитических моделей, реализованых на языке программирования Java; программных модулей имитационных моделей, которые выполняются в программной среде GPSS World.

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

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

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

Блок программных модулей аналитических моделей состоит из следующею набора моделей: канал точка-точка с механизмом управления DCF; канал точка-точка с механизмом управления НССА; канал точка-точка с механизмом управления PCF; адаптивный поллинг; циклический поллинг.

Модель выбирается согласно выбранной топологии и механизму управления или дисциплине опроса, ей передаются входные параметры, заданные пользователем, и вычисляются ее характеристики. По окончании работы данного блока, характеристики модели сохраняются в файл "math.txt" в папке, в которой находится сама программа, содержимое файла также выводится на экран.

Блок программных модулей имитационных моделей. Блок включает в себя следующие модели: канал точка-точка с механизмом управления DCF; канал точка-точка с механизмом управления НССА; канал точка-точка с механизмом управления PCF; поллинг; mesh-сеть.

Однако, в зависимости от входных параметров введенных пользователем, выбранная модель несколько модифицируется, и генерируется выходной текстовый файл "gpss.txt" с моделью на языке GPSS. Кроме этого, для mesh-ссти формируется файл "topology.txt" с топологией сети. После этого пользователь должен выполнить описанный в модели эксперимент в среде имитационного моделирования GPSS World, используя команду "CONDUCT ех()". По окончании выполнения эксперимента характеристики модели сохраняются в файл "sim.txt" в папке, в которой находится сама модель, содержимое файла также выводится на экран.

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

Основные результаты и выводы

В диссертационной работе построены аналитические и имитационные модели канала точка-точка с различными механизмами управления в режиме насыщения и нормальной нагрузки. Разработан механизм адалтивного пол-линга и модель адекватно его описывающая Реализована имитационная модель mosh-сети под управлением протокола IEEE 802.11s с различными протоколами маршрутизации. Разработан программный комплекс исследования ШБС под управлением протокола IEEE 802.11.

В диссертации получены следующие основные результаты:

1. Разработаны аналитическая и имитационная модели канала точка.-точка произвольной длины под управлением протокола IEEE 802.11 с распределенным или гибридным управлением в режиме насыщения и с распределенным управлением в режиме нормальной нагрузки с ограниченными очередями.

2. Исследована широкополосная беспроводная сеть под управлением протокола IEEE 802.11 с централизованным управлением с использованием аналитической и имитационной моделей системы адаптивного поллинга.

3. Проведен сравнительный анализ протоколов маршрутизации OLSR и HWMP в широкополосной беспроводной mesh-сети под управлением протокола IEEE 802.11s с использованием имитационного моделирования.

4. Разработан программный комплекс, объединяющий в себе все перечисленные модели, позволяющий провести аналитическое или имитационное моделирование сетей передачи информации под управлением протокола IEEE 802.11 с различными механизмами управления и топологиями.

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

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

1. Шнилев С.А. Пропускная способность широкополосного беспроводного канала точка-точка в режиме насыщения // Информационные технологии и системы (ИТиС'08). / Геленджик, 2008. С. 18-22.

2. Шнилев С.А. Проактивная маршрутизация в IEEE 802.11s mesh-сетях // Третья всероссийская молодежная научная конференция по проблемам управления (ВМКПУ-2008). / М., 2008. С. 295-296.

3. Шпилев С.А., Фахриев Д.Н. Анализ характеристик широкополосных беспроводных каналов, под управлением протокола IEEE 802.11 // Третья всероссийская молодежная научная конференция но проблемам управления (ВМКПУ-2008). / М., 2008. С. 289-290.

4. Фахриев Д.Н., Шпилев С.А. Анализ характеристик многокилометрового широкополосного беспроводного канала точка-точка с различными функциями управления // Информационные технологии и системы (ИТиС'08). / Геленджик, 2008. С. 39-44.

5. Фахриев Д.Н., Шпилев С.А. Эффект захвата в многокилометровом широкополосном беспроводном канале точка-точка // Международный семинар. Распределенные компьютерные и телекоммуникационные сети (DCCN-2008). / М.: ИППИ РАН, 2008. С. 17-28.

6. Вишневский В.М., Лаконцев Д.В., Сафонов A.A., Шпилев С.А. Mesh-ceTii стандарта IEEE 802.11s: технологии и реализация // Первая миля. 2008. № 2-3. С. 26-31.

7. Вишневский В.М., Лаконцев Д.В., Сафонов A.A., Шпилев С.А. IEEE 802.11s Mesh-сети. В ожидании стандарта IEEE 802.11s // Электроника. 2008. № 3. С. 98-107.

8. Ляхов А.И., Пустогаров И.А., Шпилев С.А. Многоканальные mesh-cera: анализ подходов и оценка производительности // Информационные процессы. 2008. Т. 8, № 3. С. 173-192.

9. Вишневский В.М., Лаконцев Д.В., Сафонов A.A., Шпилев С.А. Маршрутизация в широкополосных беспроводных mesh-сстях стандарта IEEE 802.11s // Электроника. 2008. № 6. С. 64-69.

10. Вишневский В.М., Семенова О.В., Шпилев С.А. Метод анализа средних для адаптивного механизма опроса // Массовое обслуживание: потоки, системы, сети. Материалы международной научной конференции

"Математические методы повышения эффективности информационно-телекоммуникационных сетей". / Гродно, 2007. Вып. 19. С. 254-259.

11. Vishnevsky V.M., Gorodov P.'V., Shpilev S.A. Performance analisys of RA-OLSR in IEEE 802.11s mesh networks // International Workshop. Proc. Of Distributed Computer and Communication Networks (DCCN-2007). / Moscow, 2007. Vol. 1. P. 85-90.

12. Вишневский В.M., Ляхов А.И., Шпилев С. А. Обеспечение качества обслуживания для видео потоков в режиме реального времени в mesh-сстях // 30-я конференция молодых ученых и специалистов ИППИ РАН "Информационные технологии и системы" (ИТиС'07). / М.: ИППИ РАН, 2007 С. 50-53.

13. Вишневский В.М., Лаконцев Д.В., Семенова О.В., Шпилев С.А. Модель системы поллинга для исследования широкополосных беспроводных сетей // Автоматика и телемеханика. 2006. Л'5 12. С. 123-135.

14. Вишневский В.М., Лаконцев Д.В., Семенова О.В., Шпилев С.А. Об одной стохастической системе поллинга и ее применении для моделирования беспроводных сетей // Третья международная конференция по проблемам управления: Тезисы докладов. / М.: Институт проблем управления, 2006. Т. 2. С. 145.

15. Астафьева И.Н., Вишневский В.М., Лаконцев Д.В., Шпилев С.А. Адаптивный динамический механизм опроса, в применении к сетям IP телефонии // Международный семинар. Распределенные компьютерные и телекоммуникационные сети (DCCN-2006). / М.: Техносфера, 2006. С. 65-

79.

Подписано в печать 18.11.2008 г.

Печать трафаретная

Заказ № 1208 Тираж: 90 экз.

Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш, 36 (499) 788-78-56 wwvv.autoreferat.ru

Список условных обозначений и сокращений

Введение

1 Принципы построения и особенности широкополосных беспроводных сетей

1.1 Широкополосные беспроводные сети.

1.2 Семейство протоколов IEEE 802.

1.2.1 Архитектура протокола и основные понятия.

1.2.2 Физический уровень семейства протоколов IEEE 802.

1.2.3 Уровень управления доступом к среде семейства протоколов IEEE 802.

1.2.4 Функция распределенного управления (DCF) в протоколе IEEE 802.

1.2.5 Функция централизованного управления (PCF) в протоколе IEEE 802.

1.2.6 Функция гибридного управления (HCF) в протоколе IEEE 802.

1.3 Принципы построения, особенности топологии и характерные ситуации использования беспроводных широкополосных сетей.

1.3.1 Многокилометровый канал точка-точка.

1.3.2 Радиосота.

1.3.3 Самоорганизующиеся mesh-сети.

Объект исследования и актуальность темы. В последние годы все большую популярность завоевывают беспроводные сети передачи информации. Это связано с легкостью и быстротой их развертывания, простотой в обслуживании и другими их преимуществами. При этом, среди беспроводных сетей передачи информации наибольшее распространение получили широкополосные беспроводные сети передачи информации (ШБС) под управлением протокола IEEE 802.11, известные также как Wi-Fi. Успех данного протокола объясняется высокими скоростями передачи данных (до 300 Мбит/с для нового стандарта IEEE 802.lln), широким набором сервисов, огромным диапазоном устройств, представленных па рынке, поддерживающих данный стандарт сетей. Так в настоящее время большинство современных ноутбуков, КПК, смартфонов и даже многие модели цифровых фото- и видеокамер, принтеров и цифровых фоторамок используют Wi-Fi сети. В крупных городах мира, таких как Москва, Париж, Мельбурн и др. Wi-Fi доступ к Интернету есть практически повсеместно, а в большинстве аэропортов и многих кафе по всему миру беспроводный доступ к Интернету и вовсе бесплатный. Таким образом, исследование локальных сетей передачи информации под управлением протокола IEEE 802.11 является весьма актуальным.

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

ШБС, в том числе, помогло в реализации национального проекта "Образование" при обеспечении школ доступом в Интернет (в будущем в данном проекте планируется переход на отечественное оборудование). Такой же подход позволит решить проблему "информационного неравенства".

Новым и наиболее многообещающим направлением развития протокола IEEE 802.11 является дополнение IEEE 802.11s, известное, как mesh-сети. Одним из главных принципов построения mesh-сети является принцип самоорганизации архитектуры, обеспечивающий следующие возможности:

- реализацию топологии сети "каждый с каждым";

- устойчивость сети при отказе отдельных компонентов;

- масштабируемость сети: увеличение зоны информационного покрытия в режиме самоорганизации;

- динамическую маршрутизацию трафика, контроль состояния сети и т.д.

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

Исследованию ШБС и механизмов, используемых при их построении, посвящено значительное количество работ российских и зарубежных ученых: О.М. Брехова, В.А. Васенина, В.М. Вишневского, B.C. Жданова, А.П. Кулешова, А.И. Ляхова, И.А. Мнзииа, В.В. Рыкова, Е.А. Саксонова, G. Ash, G. Bianchi, S. Borst, О. Boxma, F. Cali, M. Conti, R. G. Gallager, L. Kleinrock, P. Kyasanur, M. Neuts, C. Perkins, E. Royer, H. Takagi и др.

Наиболее фундаментальными работами в данной области являются монографии В.М. Вишневского и др. /6/ и /12/. Обзор работ, посвященных каналу точка-точка, приведен в главе 2, региональным беспроводным сетям - в главе 3, mesh-сетям - в главе 4 диссертации. Однако круг нерешенных задач непрерывно растет, и модели, построенные всего несколько лет назад, уже не удовлетворяют всем требованиям и особенностям современных протоколов. Так, например, несмотря на распространение идеи об использовании Wi-Fi при построении региональных сетей и появлении на рынке устройств, пригодных для организации многокилометровых каналов, особенности работы протокола в данном случае до сих пор остаются неисследованными. В сетях с централизованным управлением остается немало неизученных механизмов опроса, которые могут быть реализованы в современном оборудовании, что значительно улучшит дифференциацию качества обслуживания, уменьшит дрожание задержек п т. д. К современным протоколам маршрутизации, предложенным в mesh-сетях, предъявляются характерные для таких сетей требования и, следовательно, необходимы новые модели для оценки эффективности данных протоколов. Таким образом, интенсивное развитие широкополосных беспроводных технологий привело к необходимости исследования новых моделей, которые и рассматриваются в настоящей диссертационной работе.

Целью диссертационной работы является разработка и исследование моделей функционирования широкополосных беспроводных сетей под управлением протокола IEEE 802.11: оценка производительности и выбор оптимальных параметров для различных видов топологии, в том числе точка-точка, точка-многоточка и mesh; и различных функций управления, включая централизованную, распределенную и гибридную.

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

Научная новизна работы заключается в комплексном исследовании всех основных видов топологии и механизмов управления ШБС под управлением протокола IEEE 802.11: аналитическом и имитационном моделировании канала точка-точка произвольной длины и с различными функциями управления; моделировании адаптивного механизма опроса со шлюзовой дисциплиной обслуживания; изучении и сравнении протоколов маршрутизации в новых mesh-сетях стандарта IEEE 802.11s.

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

1. Разработка аналитической и имитационной моделей канала точка-точка произвольной длины под управлением протокола IEEE 802.11 с распределенным или гибридным управлением в режиме насыщения п с распределенным управлением в режиме нормальной нагрузки с ограниченными очередями.

2. Исследование ШБС под управлением протокола IEEE 802.11 с централизованным управлением с использованием аналитической и имитационной моделей системы адаптивного поллинга.

3. Проведение сравнительного анализа протоколов маршрутизации OLSR и HWMP в mesh-сети под управлением протокола IEEE 802.11s с использованием имитационного моделирования.

4. Разработка программного комплекса, объединяющего в себе все перечисленные модели, позволяющего провести аналитическое или имитационное моделирование сетей передачи информации под управлением протокола IEEE 802.11 с различными механизмами управления и топологиями.

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

• Федеральной целевой программы "Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2012 годы", проект 2007-4-2.4-00-03-004 "Разработка интегрированной технологической платформы для мониторинга элементов и систем жизненно важной инфраструктуры на основе информационно-коммуникационных технологий расширенного Интернета";

• Программы фундаментальных исследований Отделения нанотехно-логий и информационных технологий РАН (ОНИТ РАН) "Новые физические и структурные решения в инфотелекоммуникациях" проекта 3.2 - Структура и методы построения инфокоммуникациопиых сетей;

• Гранта РФФИ № 08-07-90102 "Разработка методов и алгоритмов исследования протоколов передачи мультимедийной информации в широкополосных беспроводных сетях с централизованным управлением".

Результаты работы также используются в курсах "Протоколы и стандарты телекоммуникационных сетей", "Математические и имитационные модели телекоммуникационных сетей" и "Моделирование сетей", которые читаются студентам Московского физико-технического института (ГУ).

Апробация результатов работы. Основные результаты диссертации докладывались и обсуждались на:

• Третьей международной конференции по проблемам управления Института проблем управления (Москва, 2006);

• Международном семинаре "Распределенные компьютерные и телекоммуникационные сети. Теория и приложения" (София, Болгария, 2006; Москва, 2007; София, Болгария, 2008);

• 19-й международной научной конференции "Математические методы повышения эффективности информационно-телекоммуникационных сетей", (Гродно, Белоруссия, 2007);

• 30-й и 31-й конференциях молодых ученых и специалистов ИППИ РАН "Информационные технологии и системы" (Звенигород, Россия, 2007; Геленджик, Россия, 2008);

• Третьей всероссийской молодежной научной конференции по проблемам управления (Москва, 2008);

Публикации. По теме диссертации опубликовано 15 научных работ, список которых приведен в конце автореферата. Из них 5 статей в научных журналах, /7, 8, 9, 10, 22/, 10 статей в сборниках материалов научных конференций, /1, 11, 13, 15, 24, 25, 27, 28, 29, 81/. Кроме того, получено 1 и подана заявка на 1 свидетельство об официальной регистрации программ для ЭВМ, получен 1 патент на полезную модель, поданы 2 заявки на изобретение.

Структура и объем диссертационной работы. Диссертация состоит из списка условных обозначений и сокращений, введения, пяти глав, заключения, списка литературы, включающего 85 наименований, и приложения. Работа изложена на 105 страницах и содержит 15 рисунков и 13 таблиц.

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

Заключение

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

В диссертации получены следующие основные результаты:

1. Разработаны аналитическая и имитационная модели канала точка-точка произвольной длины под управлением протокола IEEE 802.11 с распределенным или гибридным управлением в режиме насыщения и с распределенным управлением в режиме нормальной нагрузки с ограниченными очередями.

2. Исследована широкополосная беспроводная сеть под управлением протокола IEEE 802.11 с централизованным управлением с использованием аналитической и имитационной моделей системы адаптивного поллинга.

3. Проведен сравнительный анализ протоколов маршрутизации RA-OLSR и HWMP в широкополосной беспроводной mesh-сети под управлением протокола IEEE 802.11s с использованием имитационного моделирования.

4. Разработан программный комплекс, объединяющий в себе все перечисленные модели, позволяющий провести аналитическое или имитационное моделирование сетей передачи информации под управлением протокола IEEE 802.11 с различными механизмами управления и топологиями.

1. Астафьева И. Н., Вишневский В. М., Лаконцев Д. В., Шпилев С. А. Адаптивный динамический механизм опроса, в применении к сетям 1. телефонии // Международный семинар. Распределенные компьютерные и телекоммуникационные сети (DCCN-2006). — 2006. — С. 65-79.

2. Баранов А. В., Ляхов А. И. Оценка производительности беспроводных локальных сетей с протоколом IEEE 802.11 при произвольной нагрузке // Автоматика и Телемеханика. — 2005. — № 7. — С. 87-101.

3. Бергпсекас Д., Галлагер Р. Сети передачи данных: Пер. с англ. — Москва: Мир, 1989. С. 544.

4. Бэ Ю. X., Ляхов А. И., Вишневский В. М., Ким К. Д., Чой Б. Д. Матричный метод анализа широкополосной беспроводной сети с протоколом IEEE 802.11 // Информационные процессы.— 2008.— Т. 8, № 1. — С. 30-46.

5. Вишневский В. М. Беспроводные сети широкополосного доступа к ресурсам Интернета // Электросвязь. — 2000. — № 10. — С. 9-13.

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

7. Вишневский В. М., Лаконцев Д. В., Сафонов А. А., Шпилев С. А. Маршрутизация в широкополосных беспроводных mesh-сетях стандарта IEEE 802.11s 11 Электроника. — 2008. — № 6, — С. 64-69.

8. Вишневский В. М.; Лаконцев Д. В., Сафонов А. А., Шпилев С. А. IEEE 802.11s Mesh-сети. В ожидании стандарта IEEE 802.11s // Электроника. 2008. — № 3. — С. 98-107.

9. Вишневский В. М., Лаконцев Д. В., Сафонов А. А., Шпилев С. А. Mesh-сети стандарта IEEE 802.11s: технологии и реализация // Первая миля. — 2008. — № 2-3. — С. 26-31.

10. Вишневский В. М., Лаконцев Д. В., Семенова О. В., Шпилев С. А. Модель системы поллинга для исследования широкополосных беспроводных сетей // Автоматика и Телемеханика. — 2006.— № 12.— С. 123135.

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

12. Вишневский В. М., Семенова О. В. Системы поллинга: теория и применение в широкополосных беспроводных сетях. — Москва: Техносфера, 2007.— С. 312.

13. Дэвис Д., Барбер Д., Прайс У., Соломонидес С. Вычислительные сета и сетевые протоколы: Пер. с англ.— Москва: Мир, 1981.— С. 563.

14. Жданов В. С., Саксонов Е. А. Условия существования установившихся режимов в циклических системах массового обслуживания // Автоматика и Телемеханика. — 1979. — № 2. — С. 29-38.

15. Клейнрок Л. Коммуникационные сети: Пер. с англ. — Москва: Наука, 1975.-С. 256.

16. Клейнрок Л. Вычислительные системы с очередями: Пер. с англ. — Москва: Мир, 1979. С. 600.

17. Климов Г. П., Мишкой Г. К. Приоритетные системы обслуживания с ориентацией. — Москва: Издательство МГУ, 1979. — С. 220.

18. Лаконцев Д. В., Семенова О. В. Математические модели централизованного управления в беспроводных сетях IEEE 802.11 // Распределенные компьютерные и телекоммуникационные сети (DCCN-2005).— 2005.-С. 77-83.

19. Ляхов А. И., Пустогаров И. А., Шпилев С. А. Многоканальные mesh-сети: анализ подходов и оценка производительности // Информационны е процессы. — 2008. — Т. 8, № 3. — С. 173-192.

20. Мизин И. А., Богатырев В. А., Кулешов А. П. Сети коммутации пакетов. — Москва: Радио и связь, 1986. — С. 408.

21. Фахриев Д. Н., Шпилев С. А. Анализ характеристик многокилометрового широкополосного беспроводного канала точка-точка с различными функциями управления // Информационные технологии и системы (ИТиС'08). — 2008. — С. 39-44.

22. Фахриев Д. Н., Шпилев С. А. Эффект захвата в многокилометровом широкополосном беспроводном канале точка-точка // Международный семинар. Распределенные компьютерные и телекоммуникационные сети (DCCN-2008). 2008. - С. 17-28.

23. Шварц М. Сети ЭВМ. Анализ и проектирование: Пер. с англ. — Москва: Радио и связь, 1981.— С. 336.

24. Шпилев С. А. Проактивная маршрутизация в IEEE 802.11s mesh-сетях // Третья всероссийская молодео/сная научная конференция по проблемам управления (ВМКПУ-2008). — 2008.

25. Шпилев С. А. Пропускная способность широкополосного беспроводного канала точка-точка в режиме насыщения // Информационные технологии и системы (ИТиС'08). — 2008. — С. 18-22.

26. Шпилев С. А., Фахриев Д. Н. Анализ характеристик широкополосных беспроводных каналов, под управлением протокола IEEE 802.11 // Третья всероссийская молодежная научная конференция по проблемам управления (ВМКПУ-2008). — 2008. — С. 289-290.

27. Adan I., Вохта О., Resing J. Queueing models with multiple waiting lines // Queueing Syst. 2001. - Vol. 37, no. 1-3. — Pp. 65-98.

28. Ash G. R. Dynamic Routing in Telecommunications Networks. — McGraw-Hill, 1998.

29. Bahr M. Proposed Routing for IEEE 802.11s WLAN Mesh Networks // ACM International Conference Proceeding Series. — 2006. — Vol. 220.

30. Bianchi G. Performance Analysis of the IEEE 802.11 Distributed Coordination Function // IEEE Journal on Selected Areas in Communications. — 2000. Vol. 18, no. 3. - Pp. 535-547.

31. Bing B. Wireless local area networkss: the new wireless revolution. — Wiley-Interscience, 2002. — P. 400.

32. Borst S. С. Polling systems. — Amsterdam: Stichting Mathematisch Centrum, 1996,- P. 232.

33. Brwieel H., Kim B. G. Discrete-time models for communication systems including ATM. — Boston: Kluwer Academic Publishers, 1993.— P. 200.

34. Bruno R., Conti M., Gregory E. Bluetooth: architecture, protocols and scheduling algorithms // Cluster Comput.— 2002.— Vol. 5.— Pp. 117131.

35. Call F., Conti M., Gregory E. IEEE 802.11 Wireless LAN: Capacity Analysis and Protocol Enhancement // Proceedings of INFOCOM'98.— 1998.— Pp. 142-149.

36. Chang К. H. First-come-first-served polling systems // Asia-Pacific J. Op-er. Res. — 2001. — Vol. 18, no. 1.—Pp. 1-11.

37. Chesoong K., Seokjun L., Lyakhov A., Vishnevsky V. 802.11 Ad Hoc LANs with Realistic Channels: Study of Packet Fragmentation // Journal of the Korean Institute of Industrial Engineers.— 2007. — September.— Vol. 33, no. 3.- Pp. 381-392.

38. Chris L., Steve P. Selecting MPLS VPN Services. — Cisco Press, 2006.— P. 428.

39. Clausen Т., Jacquet P. Optimized Link State Routing Protocol (OLSR) // IETF RFC 3626. 2003. - October.

40. Draves R., Padhye J., Zill B. Routing in Multi-Radio, Multi-Hop Wireless Mesh Networks // ACM Mobicom.— 2004.

41. Grillo D. Polling mechanism models in communication systems some application examples // Stochastic Analysis of Computer and Communication Systems. - 1990. - Pp. 659-698.

42. Gupta P., Kumar P. R. The Capacity of Wireless Networks // IEEE Transactions on Information Theory. — 2000. — March. — Vol. 46, no. 2. — Pp. 388-404.

43. Hassanein H., Zhou A. Routing with Load Balancing in Wireless Ad hoc Networks Ц ACM MSWiM. 2001.

44. Johnson D. В., Maltz D. A. Dynamic Source Routing in Ad Hoc Wireless Networks // Mobile Computing.— 1996. —Vol. 353.

45. Khalid M., Vyavahare P. D., Kerke H. B. Analysis of asymmetric polling systems // Comput. Oper. Res.— 1997. Vol. 42, no. 4, — Pp. 317-333.

46. Khanna A., Zinky J. The Revised ARPANET Routing Metric j j ACM SIGCOMM.- 1989.

47. Kopsel A., Ebert J. P., Wolisz A. A performance comparison of point and distributed function of an IEEE 802.11 WLAN in the presence of realtime reqiurements / / Proc. Inf. Workshop MoMuc2000- Waseda. — 2000. — October.

48. Kyasanur P., Vaidya N. Multi-Channel Wireless Networks: Capacity and Protocols // Tech. Rep., University of Illinois at Urbana-Champaign.— 2005.

49. Lee S.-J., Gerla M. Dynamic Load-Aware Routing in Ad hoc Networks // IEEE ICC. 2001.

50. Levy H., Sidi M. Polling systems: applications, modeling and optimization // IEEE Trans. Commun. 1990. — Vol. 38, no. 10. - Pp. 1750-1760.

51. Levy H., Sidi M., Boxma 0. J. Dominance relations in polling systems // Queueing Syst. — 1990. — Vol. 6, no. 2. — Pp. 155-171.

52. Lyakhov A., Vishnevsky V. Packet Fragmentation in Wi-Fi Ad Hoc Networks with Correlated Channel Failures // Proc. 1st IEEE Int. Conf. on

53. Mobile Ad-hoc and Sensor Systems (MASS 2004).— 2004, —5-27 October. Pp. 204-213.

54. Miorandi D., Zanella A., Pierobon G. Performance Evaluat of Bluetooth polling schemes: an analytical approach // ACM Mobile Networks and Ap-pl. 2004. - Vol. 9, no. 2. - Pp. 63-72.

55. Neuts M. F. Structured Stochastic Matrices of M/G/l Type and Their Applications. — New York: Marcel Dekker, 1989.

56. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. Amendment 4: Further Higher Data Rate in the 2.4 GHz Band // IEEE Std 802.11g-2003. 2003. - November. - P. 67.

57. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. Amendment 5: Enhancements for Higher Throughput // IEEE P802.1 In/D6.0. 2008. - July. - P. 534.

58. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. Amendment 7: Medium Access Control (MAC) Quality of Service (QoS) Enhancement // IEEE P802.11e/D12.0.— 2004.-November. — P. 179.

59. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications: Amendment: Mesh Networking // IEEE P802.11s/D2.02. 2008. - September. - P. 254.

60. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications: Amendment: Mesh Networking // IEEE P802.11s/D1.06. — 2007. — July. P. 246.

61. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications: Amendment: Mesh Networking // IEEE P802.11s/D1.07. 2007.-September. — P. 221.

62. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications: Higher-Speed Physical Layer Extension in the 2.4 GHz Band // IEEE Std 802.11Ъ-1999. — 1999. P. 89.

63. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications: High-speed Physical Layer in the 5 GHz Band // IEEE Std 802.11a-1999. 1999. - P. 83.

64. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications // IEEE Std 802.11-2007. 2007. - June. - P. 1184.

65. Perkins C. Ad-hoc on-demand distance vector routing // MILCOM panel on Ad Hoc Networks. — 1997.

66. Perkins C., Belding-Royer E., Das S. Ad hoc On-Demand Distance Vector (AODV) Routing // IETF RFC 3561. 2003. - July.

67. Qayyum, Laouiti A., Viennot L. Multipoint relaying technique for flooding broadcast messages in mobile wireless networks // HICSS: Hawai Int. Conference on System Sciences. — 2002. — January.

68. Qiao D., Choi S., Soomoro A., Shin K. G. Energy-efficient PCF operation of IEEE 802.11a Wireless LAN // Proceedings of INFOCOM 2002. -2002. June. — Vol. 2. — Pp. 580-589.

69. Richardson I. E. G. H.264 and MPEG-4 Video Compression: Video Coding for Next-generation Multimedia. — John Wiley к Sons, 2003. — P. 281.

70. Royer E. M., Toll C. A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks // IEEE Personal Communications. — 1999.— April.

71. Schriber Т. I. Simulation using GPSS.- John Wiley & Sons, 1974.— P. 548.

72. Sobrinho J. L. Algebra and algorithms for QoS path computation and hop-by-hop routing in the Inernet 11 IEEE INFO COM. — 2001.

73. Sobrinho J. L. Network Routing with Path Vector Protocols: Theory and Applications jI ACM SIGCOMM. 2003. - Pp. 49-60.

74. Takagi H. Analysis of polling systems. — MIT Press, 1986.— P. 175.

75. Takagi H. Queueing analysis of polling models: an update // Stochastic Analysis of Computer and Communication Systems. — 1990. — Pp. 267318.

76. Takagi H. Applications of polling models to computer networks // Comput. Networks ISDN Syst.— 1991. — Vol. 22, no. 3.- Pp. 193-211.

77. Takagi H. Queueing analysis of polling models: progress in 1990-1994 // Frontiers in Queueing.— 1997. — Pp. 119-146.

78. Takagi H. Analysis and applications of polling models // Performance Eval-uat: Origins and Directions. Lecture Notes Comput. Sci. — 2000. — Vol. 1769,- Pp. 423-442.

79. Vishnevsky V. M., Gorodov P. V., Shpilev S. A. Performance analisys of RA-OLSR in IEEE 802.11s mesh networks // International Workshop. Proc. Of Distributed Computer and Communication Networks (DCCN-2007). — 2007.-Vol. 1.

80. Vishnevsky V. M., Lyakhov A. I. Adaptive features of IEEE 802.11 Protocol: utilization, tuning and modifications // Proc. of 8th HP-OVUA Conf.— 2001. -June.

81. Vishnevsky V. M., Lyakhov A. I. IEEE 802.11 Wireless LAN: Saturation Throughput Analysis with Seizing Effect Consideration // Cluster Computing. — 2002. — Vol. 5, no. 2. — Pp. 133-144.

82. Vishnevsky V M., Lyakhov A. I., Guzakov N. N. An adaptive polling strategy for IEEE 802.11 PCF // Proc. 7th Int. syrnp. on Wireless Personal Multimedia Communications (WPMC'04)■— 2004.— September.— Vol. l.-Pp. 87-91.

83. Wu T.-H. Fiber Nerwork Service Survivability. — Artch House, 1992.

84. Ziouva E., Antonakopoulos T. Efficient voice communications over IEEE802.il WLANs using improved PCF procedures // Proc. Third Int. Work Conf. INC. — 2002.

85. Ziouva E., Antonakopoulos T. Improved IEEE 802.11 PCF performance using silence detection and cyclic shift on stations polling // IEE Proc. Commun. 2003. - Vol. 150, no. 1. — Pp. 45-51.