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

Хоров Евгений Михайлович

Анализ эффективности механизмов доставки

потоковых данных с заданными требованиями

к качеству обслуживания

в самоорганизующихся беспроводных сетях

05.12.13 – Системы, сети и устройства телекоммуникаций

АВТОРЕФЕРАТ

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

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

Москва – 2012

Работа выполнена в Федеральном государственном автономном образовательном учреждении высшего профессионального образования «Московском физико-техническом институте (государственном университете)».

Научный руководитель: доктор технических наук, старший научный сотрудник Ляхов Андрей Игоревич

Официальные оппоненты: Степанов Сергей Николаевич, доктор технических наук, профессор, ОАО «Интеллект-телеком», директор информационноаналитического департамента Осипов Дмитрий Сергеевич, кандидат технических наук, Федеральное государственное бюджетное учреждение науки Институт проблем передачи информации Российской академии наук (ИППИ РАН), старший научный сотрудник

Ведущая организация: Федеральное государственное бюджетное учреждение науки Институт проблем информатики Российской академии наук

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

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

Автореферат разослан « » 2012 г.

Ученый секретарь диссертационного совета д. ф.-м. н. Цитович И.И.

Общая характеристика работы

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

Децентрализованные сети, или сети класса ad hoc, – это сети, создавае­ мые при необходимости из равнозначных станций без какой-либо заранее раз­ вернутой инфраструктуры. Большая потребность в таких сетях нашла отра­ жение в стандартах беспроводных сетей, например в стандарте IEEE 802.11, известном под коммерческой маркой Wi-Fi. В этом стандарте сети ad hoc со­ здаются из однотипных устройств и используют распределенное управление, при этом каждая станция находится в зоне непосредственного радиоприема всех остальных станций. С момента публикации первой версии стандарта в 1997 г. появилось множество новых задач, которые требовали обеспечения бесперебойной работы движущихся станций и расширения зоны покрытия сети. Расширение зоны покрытия сети означает, что некоторые станции связ­ ной сети находятся вне зоны радиоприема друг друга, поэтому для доставки пакетов между ними требуется ретрансляция пакетов через промежуточные станции. Таким образом, расширение зоны покрытия сети приводит к пере­ ходу от одношаговой сети к многошаговой. Технологиями, обеспечивающими работу движущихся станций в многошаговой сети, стали 1) оформленная в виде спецификаций организации IEFT технология мобильных ad hoc сетей (сетей MANET) и 2) технология mesh-сетей стандарта IEEE 802.11s (сетей Wi-Fi Mesh).

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

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

Исследованию эффективности доставки данных в многошаговых беспро­ водных самоорганизующихся сетях посвящено значительное количество ра­ бот, среди которых следует особо отметить работы российских и зарубеж­ ных ученых: О.М. Брехова, А.В. Винеля, Н.Д. Введенской, А.Б. Гольдштейн, А.А. Гончарова, А.П. Кулешова, Д.В. Лаконцева, А.И. Ляхова, Д.Н. Мацне­ ва, В.И. Неймана, Д.С. Осипова, А.Н. Рыбко, А.А. Сафонова, О.Д. Соколо­ вой, С.Н. Степанова, И.И. Цитовича, М.Ю. Якимова, G. Bianchi, T. Clausen, M. Conti, R.Draves, P. Jacquet, G. Hiertz, A. Nayebi, E.Perkins, R. Ramanathan, C. Santivanez, J. Sobrinho, M. Voorhaen, Y. Yang и др. Некоторые из этих работ исследуют эффективность механизмов, отличных от используемых в недавно изданных спецификациях сетей MANET и сетей Wi-Fi Mesh. Другие анали­ зируют передачу данных именно в таких сетях, но не уделяют достаточно­ го внимания обеспечению выполнения требований к качеству обслуживания.

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

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

Цель диссертационной работы состоит в построении аналитических и имитационных моделей механизмов доставки потоковых данных в сетях MANET и Wi-Fi Mesh, позволяющих произвести оценку эффективности этих механизмов и настроить их для выполнения требований к качеству обслужи­ вания трафика.

Для достижения поставленной цели в диссертации ставятся и решаются следующие задачи.

1. Аналитическое исследование влияния методов размещения биконов в сетях Wi-Fi Mesh, использующих детерминированный метод доступа, на емкость сети.

2. Разработка аналитической модели передачи данных постоянной интен­ сивности c выполнением требований к качеству обслуживания в усло­ виях помех с помощью периодических резервирований канала.

3. Разработка аналитических моделей для оценки значений показателей эффективности механизмов управления соединениями.

4. Оценка эффективности различных механизмов маршрутизации в сетях Wi-Fi Mesh и MANET, в т. ч. метрик маршрутизации и механизмов рас­ сылки информации о соединениях, при доставке данных с требуемым качеством обслуживания путем имитационного моделирования.

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

Научная новизна В диссертации впервые:

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

исследовано влияние метода размещения биконов на емкость сети Wi-Fi Mesh, использующей детерминированный метод доступа;

разработаны аналитические модели процесса изменения состояния со­ единений в сетях MANET и Wi-Fi Mesh, позволяющие оценить показа­ тели эффективности механизмов управления соединениями;

исследованы ошибки маршрутизации, возникающие в сети под управле­ нием проактивного протокола маршрутизации OLSR, и разработаны ре­ активные методы рассылки сетевой информации, дополняющие OLSR и снижающие вероятность возникновения ошибок маршрутизации;

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

Практическая ценность и реализация результатов Использование теоретических и практических результатов, полученных в диссертации, при разработке сетей MANET и Wi-Fi Mesh позволит суще­ ственно повысить их емкость и вероятность выполнения требований к каче­ ству обслуживания мультимедийного трафика реального времени.

Результаты работы внедрены и используются на практике, а также в учебном процессе на кафедре МФТИ (ГУ) в ИППИ РАН «Проблемы переда­ чи и обработки информации», что подтверждено соответствующими актами.

В частности, разработанные модели и механизмы использованы в НИР, вы­ полняемых ИППИ РАН по программе ОНИТ РАН «Фундаментальные про­ блемы разработки новых структурных решений и элементной базы в теле­ коммуникационных системах», в международном исследовательском проекте FLAVIA, проводимом в рамках 7-й рамочной программы Евросоюза, а также в НИР по заказу ЗАО «Телум».

Основные положения, выносимые на защиту 1. Разработанный метод аналитического моделирования передачи потоко­ вых данных постоянной интенсивности с помощью периодических ре­ зервирований канала позволяет минимизировать объем зарезервирован­ ных канальных ресурсов при выполнении требований к качеству обслу­ живания трафика в условиях помех.

2. Построенные аналитические модели протоколов управления соединени­ ями с синхронизацией и без синхронизации состояния соединения в се­ тях MANET и Wi-Fi Mesh позволяют оценивать значения показателей эффективности этих протоколов, а также определять область допусти­ мых значений параметров протокола, при которых выполняются огра­ ничения на значения показателей эффективности.

3. Разработанные метрики маршрутизации для сетей Wi-Fi Mesh, исполь­ зующих как случайный, так и детерминированный методы доступа к каналу, а также реактивное дополнение к протоколу маршрутизации OLSR для сетей MANET позволяют в до 3 раз снизить вероятность невыполнения требований к качеству обслуживания.

Апробация работы Основные результаты диссертации докладывались и обсуждались на ве­ дущих международных и российских конференциях: 3rd Int. Workshop on Multiple Access Communications (Испания, 2010 г.), 8th IEEE Int. Conf. on Mobile Ad-hoc and Sensor Systems (Испания, 2011 г.), 29th Int. Symp. on Computer Performance, Modeling, Measurements and Evaluation (Нидерланды, 2011 г.), «Информационные технологии и системы» в 2009, 2010 и 2011 гг., а также на семинарах ИППИ РАН и МФТИ.

Публикации Материалы диссертации опубликованы в 15 печатных работах, из них 6 статей ([1–6]) в рецензируемых изданиях, 3 из которых ([1–3]) входят в перечень ВАК, 9 статей ([7–15]) в сборниках трудов конференций. Подготовка к публикации полученных результатов проводилась совместно с соавторами, причем вклад диссертанта был определяющим.

Структура и объем диссертации Диссертация состоит из введения, 4 глав, заключения, библиографии и приложения. Общий объем диссертации 142 страницы, включая 39 рисунков и 11 таблиц. Библиография включает 78 наименований.

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

В первой главе описывается архитектура сетей Wi-Fi Mesh и сетей MANET, в которых доступ к среде осуществляется по технологии Wi-Fi и которые на сегодняшний день являются наиболее проработанными техноло­ гиями самоорганизующихся беспроводных сетей. Особое внимание уделено методам доступа к каналу, механизмам управления соединениями, методам распространения информации о соединениях и метрикам маршрутизации.

В сетях Wi-Fi базовым методом доступа к каналу является случайный (режим распределенного управления DCF, в основе которого лежит метод CSMA/CA). Случайный выбор момента начала передачи пакета является причиной возможных коллизий – одновременной передачи пакетов нескольки­ ми станциями, приводящей к тому, что приемник не может правильно декоди­ ровать сигнал и не получает ни один из переданных пакетов. Если приемник получает пакет, он подтверждает получение пакета с помощью кадра ACK.

Если станция-отправитель не получает ACK, она повторяет передачу пакета до тех пор, пока не получит ACK или не будет достигнут допустимый порог попыток передачи. В сетях, где все станции находятся в зоне радиоприема друг друга, вероятность коллизий мала, и такой метод позволяет эффектив­ но бороться с их последствиями. Однако в многошаговых сетях вероятность коллизий значительно возрастает из-за эффекта скрытых станций.

Для повышения надежности передачи пакетов в многошаговых сетях стандарт IEEE 802.11s вводит дополнительный детерминированный метод доступа – MCCA, основанный на предварительном резервировании интерва­ лов времени, в течение которых возможна бесконкурентная передача данных станцией-владельцем резервирования. Поскольку даже резервирование сре­ ды не позволяет гарантировать успешную передачу пакета, например, из-за шумов в канале, передача пакета подтверждается.

Для сокращения накладных расходов MCCA резервирует не единичный интервал времени, а множество интервалов времени, которое определяется тремя параметрами: 1) длительностью каждого зарезервированного интер­ вала; 2) периодичностью – числом зарезервированных интервалов в течение единицы времени, называемой DTIM-интервалом; 3) смещением первого за­ резервированного интервала от начала DTIM-интервала.

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

Если при создании нового резервирования превышает на самой станции или на ее соседях, то станция отказывается от нового резерви­ рования.

Метод MCCA используется для повышения надежности передачи поль­ зовательских данных. Однако в сетях Wi-Fi Mesh присутствует еще один механизм резервирования среды, MBCA, используемый для повышения на­ дежности передачи биконов, в которых передается служебная информация и которые также служат для обнаружения станциями друг друга. Биконы по­ сылаются каждой станцией строго периодически, 1 раз в бикон-интервал (но биконы разных станций размещены друг относительно друга произвольным образом). Для предотвращения коллизий биконов и повышения надежности их передачи MBCA запрещает станции вести любую передачу в то время, как хотя бы 1 станция из ее двухшагового окружения передает бикон.

Далее в первой главе описываются механизмы управления соединения­ ми, используемые в сетях MANET и mesh-сетях.

В сетях MANET, использующих, пожалуй, наиболее распространенный протокол маршрутизации OLSR, за управление соединениями с соседними станциями отвечает протокол управления соединениями NHDP. Согласно ему каждая станция периодически рассылает широковещательно на 1 шаг специ­ альные служебные HELLO-сообщения. Получив HELLO-сообщение от стан­ ции, станция считает, что между станциями открыто соединение (состо­ яние соединения ), и указывает в своем HELLO-сообщении адрес станции (в третьей главе рассматривается обобщенная схема, в которой открытие происходит по 1 HELLO-сообщениям, полученным подряд). При поте­ ре HELLO-сообщений подряд станция закрывает соединение со станци­ ей и прекращает указывать адрес станции в своих HELLO-сообщениях (состояние соединения – ). Открытое соединение () может быть однона­ правленным () или симметричным ( ). Если в последнем полученном HELLO-сообщении, отправленном станцией, указан адрес станции, то станция считает соединение симметричным, иначе – однонаправленным.

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

В отличие от него протокол PMP (Peering management protocol), исполь­ зуемый для управления соединениями в сетях Wi-Fi Mesh, содержит меха­ низм «двойного рукопожатия», синхронизирующий состояние соединения на обеих станциях. При этом соединение является либо симметричным, либо закрытым, т.е. является однонаправленным пренебрежимо малое время.

Стандарт mesh-сетей явно не оговаривает правил, по которым соедине­ ния должны открываться и закрываться. На практике может использовать­ ся подход, схожий с NHDP, когда при получении служебных сообщений (в mesh-сетях такими сообщениями являются биконы) соединение открывается, а при потере сообщений – закрывается.

Помимо вышесказанного, в первой главе описываются механизмы марш­ рутизации и дается краткое описание протоколов маршрутизации OLSR и HWMP, используемых соответственно в сетях MANET и в mesh-сетях, а так­ же метрики Airtime link, описанной в стандарте IEEE 802.11s.

Содержание главы опубликовано в работах [1, 5, 6, 10, 13].

Во второй главе анализируется метод MCCA детерминированного до­ ступа в сетях Wi-Fi Mesh.

В разделе 2.1 разрабатывается модель, предназначенная для выбора пе­ риода *, с которым следует резервировать интервалы времени для передачи потоковых данных постоянной интенсивности с требуемым качеством обслу­ живания при наличии помех в канале и с минимальным потреблением ка­ нальных ресурсов. При этом требования к качеству обслуживания задаются двумя порогами: максимально допустимой долей потерянных паке­ тов и максимально допустимым временем доставки пакетов.

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

где * – интервал между между приходами пакетов, определить долю потерянных пакетов.

В модели время делится на слоты, причем 1) размер слота выбирается таким образом, что * =, * = и, N – взаимно простые числа;

2) начало каждого зарезервированного интервала совпадает с началом неко­ торого слота. Так как интервал времени между поступлениями в очередь двух пакетов содержит целое число слотов, интервал времени между по­ ступлением в очередь пакета и началом очередного слота одинаков для всех пакетов, 0 <.

Передача пакета представляется одномерной марковской цепью с дис­ кретным временем (моменты наблюдения – начала зарезервированных интер­ валов, т.е. продолжительность шага – ). Состояние () описывается целым числом следующим образом. Если очередь непуста, то () 0 и () + соответствует времени ожидания в очереди самого старшего пакета, выра­ женному в слотах. Если очередь пуста, то () < 0 и |() + | – время до поступления следующего пакета в очередь. Минимальное значение () рав­ но. Это значение достигается в момент + 1, когда пакет поступает в пустую очередь в момент и тут же успешно передается. Очевидно, что Стационарные вероятности, { +,..., } состояний такого процесса описываются системой линейных уравнений:

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

В диссертации приводятся примеры использования разработанной мо­ дели и описывается процедура выбора периода резервирований. Показано и обосновано, что функция (* ) не является монотонной ни в одной точке и имеет локальные минимумы, в частности, в точках * = * /, N.

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

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

Станции запрещено устанавливать резервирования с периодичностью, отлич­ ной от базовой.

Одно только введение базовой периодичности не позволяет эффективно использовать среду из-за случайного размещения биконов друг относительно друга, так как моменты отправки биконов определяются до установки резер­ вирований и накладывают ограничения на выбор возможных интервалов ре­ зервирования. Для оценки значимости влияния случайного размещения бико­ нов на емкость сети (число резервирований, которое может быть установлено) в диссертации разработаны аналитические и имитационные модели.

При разработке аналитической модели сделано предположение, что вре­ мя слотировано, причем длительности передачи пакетов с данными и биконов равны продолжительности каждого слота, начало их передачи совпадает с началом слота, а пользовательские данные передаются с периодичностью пакетов за бикон-интервал. Тогда общее число слотов в одном бикон-интер­ вале равно, где =. Пронумеруем их, начиная с 1, и представим их в виде двумерного массива c столбцами высотой, причем слоты с номерами +, = 0, 1, = 1, входят в один столбец. Каждый поток перио­ дичного трафика занимает ровно один столбец. Передача бикона занимает 1 слот, однако весь столбец, в который входит этот слот, не может быть за­ резервирован для периодического трафика. Будем называть такой столбец блокированным.

В диссертации показано, что среднее число блокированных столб­ цов при случайном размещении биконов определяется формулой:

где (,,, ) = – вероятность того, что при размещении бико­ нов в слотах было занято ровно столбцов, а (,, ) – число разме­ щений биконов без коллизий ровно в выбранных столбцах размером :

Очевидно, что наиболее эффективным будет регулярное размещение би­ конов, при котором биконы размещаются в минимальном числе столбцов: в Рис. 1. Относительная емкость сети при различном числе устройств этом случае биконов блокируют только групп: =, где – мини­ мальное целое число, не меньшее. В диссертации описан алгоритм, согласно которому станции размещают свои биконы именно таким образом.

На рис. 1 изображены полученные аналитические графики зависимости емкости сети от числа устройств в двухшаговом окружении при регулярном и используемом в стандарте случайном размещении биконов. При этом за 100% принята емкость сети, которая была бы достигнута, если бы биконы не передавались. Приведенные результаты получены при = 40, = 50, что соответствует базовой периодичности – 50c1, длительности 1 бикона – 0, мс, бикон-интервалу – 1с.

Результаты, полученные в этой главе, опубликованы в [4, 5, 9].

В третьей главе проводится анализ механизмов управления соедине­ ниями (МУС): NHDP и PMP.

МУС предназначен для работы в сетях, в которых качество канала ме­ няется со временем. Пусть беспроводной канал между станциями и яв­ ляется каналом Бернулли с вероятностью успешной передачи, меняющейся со временем, например, из-за движения станций.

Ограничение числа попыток передачи пакета стандартом IEEE 802.11 не позволяет передать пакет с требуемым качеством обслуживания по соедине­ ниям с низким значением. Кроме того, использование соединений с низкой вероятностью успешной передачи пакета приводит к большим расходам ре­ сурсов канала. Таким образом, МУС должен открывать только те соедине­ ния, которые обеспечивают вероятность успешной передачи пакета не ниже некоторого заданного порогового значения 0.

Решение о текущем значении и, следовательно, об открытии/закрытии соединения принимается на основании статистики принятых/потерянных со­ общений. При этом вероятны ошибки оценки состояния канала. Однако на емкость сети влияет не столько вероятность возникновения ошибки, сколько доля времени, когда состояние соединения не соответствует ограничению на, а также частота смены состояния соединения. Информация о состоянии соединений рассылается протоколом OLSR ненадежно, поэтому даже стан­ ции вблизи соединения могут иметь различную информацию о нем, что при частых открытиях/закрытиях соединения приводит к зацикливанию марш­ рутов и другим ошибкам маршрутизации и не позволяет передавать данные с требуемым качеством обслуживания.

В диссертации рассматривается задача поиска таких наборов значений параметров и МУС, которые обеспечивают выполнение следующих тре­ бований. 1) Необходимо, чтобы соединения с > 0 были преимущественно открыты, а соединения с < 0 преимущественно закрыты. Это эквивалент­ но условию: (0 ) = 0, 5, где () – вероятность того, что соединение сим­ метрично при заданном (далее для сокращения записи будем опускать).

Вероятность определяется по формуле = +, где – сред­ нее время, в течение которого соединение непрерывно симметрично, а – среднее время, в течение которого соединение находится в других состояни­ ях (закрыто или однонаправленно). 2) Частота смены состояния соединения = + должна быть много меньше порога 0 =, где – период обновления информации о соединениях. 3) Наконец, среднее вре­ мя принятия решения механизмом управления соединениями должно быть много меньше интервала времени, в течение которого > 0. При мед­ ленном изменении (0 ), при быстром –, где – число сообщений, которое надо подряд получить, чтобы открыть соединение.

В диссертации разработаны аналитические модели, позволяющие для заданных параметров МУС оценить значения показателей эффективности Для МУС, реализуемого протоколом NHDP, построена модель, позво­ ляющая оценить значения и, через которые можно выразить все показатели эффективности. Чтобы определить, вначале находится вероят­ ность того, что станция, для определенности, считает, что состояние соединения – : =, где и определяются следующим утверждением, доказанным с применением аппарата производящих функций.

Утверждение 1. Средние длительности и состояний и определяются выражениями:

Здесь и далее время измеряется в периодах рассылки HELLO-сообщений.

Утверждение 2. Вероятность нахождения станции в состоянии определяется формулой: =.

Для определения рассматриваются независимые On-Off процессы и () изменения состояния станций и соответственно и опре­ деляется процесс * () переходов между состояниями * и * следующим образом. Процесс * () находится в состоянии * тогда и только тогда, когда оба процесса () и () находятся в состоянии ; в остальных случаях процесс * () находится в состоянии *.

Используется допущение, заключающееся в том, что оценить среднюю длительность состояния можно по средней длительности * состояния * процесса * (). На самом деле, при низких значениях эти длительности могут не совпадать из-за низкой вероятности доставки сообщений, по которым станция узнает о состоянии соединения на другой станции, однако, как подтверждено в ходе имитационного моделирования, при > 0, 5 ошибка, вызванная этим допущением, не превосходит 1%.

Утверждение 3. Математическое ожидание * длительности со­ стояния * определяется выражением * = 2.

Таким образом, определены все показатели эффективности протокола NHDP.

Также в диссертации исследуются показатели эффективности протокола PMP. Так как стандарт mesh-сетей допускает, что станция, получив запрос на открытие соединения, может отказаться от открытия соединения, в дис­ сертации исследуется подход, в котором станция соглашается на открытие соединения, только если сама получила биконов. При этом рассматривают­ ся 2 предельных случая: = 0, что соответствует стратегии с безусловным подтверждением, когда станция всегда соглашается на открытие соединения, и = 1 – стратегия с условным подтверждением, когда для согласия тре­ буется получение наибольшего числа биконов (показано, что бессмысленно устанавливать ).

При анализе PMP подход, используемый для NHDP, оказывается непри­ годным, поэтому разработан другой метод, позволяющий определить значе­ ния величин и, однозначно определяющих все показатели эффективности. Этот метод сводится к анализу последовательности { } полученных биконов: = 1, если в момент времени станция получила бикон от, и = 0, если бикон не был получен.

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

Утверждение 4. Вероятность, () того, что произвольная последова­ тельность { } является -правильной, определяется выражением:

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

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

а при использовании стратегии с условным подтверждением:

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

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

Кроме того, предложен алгоритм выбора параметров МУС, состоящий из 1) метода определения значений требуемых показателей эффективности из параметров сценария работы сети и 2) поиска с помощью разработанных мо­ делей набора значений параметров МУС, обеспечивающего достижение тре­ буемых значений показателей эффективности. С помощью имитационного мо­ делирования подтверждено, что выбор значений параметров МУС согласно этому методу позволяет получить наивысшую или почти наивысшую емкость сети при передаче потоковых данных с заданными требованиями к качеству обслуживания в различных сценариях работы сети.

Основные результаты третьей главы опубликованы в [3, 6–8].

В четвертой главе исследуются механизмы маршрутизации.

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

Назовем маршрут 0 от источника 0 до конечного получателя в некоторый момент времени корректным, если в этот момент существует множество различных станций {, } таких, что = 0, 1,..., 1 в таблице маршрутизации станции существует запись о маршруте до станции че­ рез станцию +1, находящуюся в области радиоприема станции. Наличие корректного маршрута будем обозначать. В остальных случаях проис­ ходит одна из ошибок маршрутизации, которую обозначим –,, :

может принимать одно из двух значений: “+”, если 0 и находятся в одной компоненте связности сети; “”, в остальных случаях;

характеризует тип возникшей ошибки: “”, если маршрут зациклился;

“”, если в таблице маршрутизации одной из станций, через которую проходит маршрут, отсутствует запись о маршруте; “”, если некоторая станция передает пакет станции +1, которую все еще считает своим соседом, но которая уже находится вне области радиоприема ;

принимает одно из двух значений: “”, если ошибка произошла на источнике; “”, если ошибка произошла на промежуточном ретрансля­ Например, ошибка,, происходит, когда 0 и находятся в раз­ личных компонентах связности сети и в таблице маршрутизации 0 нет необ­ ходимой для маршрутизации пакета записи. Правильная работа протокола приводит к тому, что для любой пары источника и конечного получателя вы­ полняется одно из двух условий: либо имеется корректный маршрут (), либо, если источник и конечные получатели находятся в разных компонентах связности,,,.

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

В частности, в ходе исследования обнаружено, что в некоторых сцена­ риях вероятность ошибок маршрутизации может быть значительной. Напри­ мер, в решетчатой топологии 3 16 при включении или выключении станции с координатами (2, 8) соответственно более 15% или более 35% маршрутов оказываются некорректными на протяжении нескольких секунд, в течение которых передача данных реального времени невозможна.

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

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

В разделах 4.3 и 4.4 четвертой главы производится анализ метрик марш­ рутизации, которые могут быть применяться в сетях Wi-Fi Mesh при исполь­ зовании соответственно случайного и детерминированного методов доступа.

Физический смысл метрики маршрутизации Airtime link, описанной в стандарте IEEE 802.11s, – ожидаемое суммарное время занятости канала при всех попытках передачи пакета некоторой фиксированной длины. В диссер­ тации показано, что из-за игнорирования степени занятости канала этой мет­ рикой маршруты, выбираемые согласно Airtime link, проходят через загру­ женные участки сети, в которых при случайном методе доступа практически невозможно выполнить требования к качеству обслуживания. Особенностью случайного метода доступа к среде в сетях IEEE 802.11 является счетчик отсрочки, который замораживается, когда среда занята. Из-за этого при уве­ личении нагрузки на сеть значительно увеличивается время обслуживания пакета, т.е. длительность промежутка времени, состоящего из всех попыток передачи, а также интервалов отсрочки между ними. Это позволяет постро­ ить простые в реализации метрики маршрутизации, значение которых значи­ тельно возрастает при увеличении доли времени, когда канал занят.

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

С помощью имитационного моделирования показано, что использование этих метрик маршрутизации вместо стандартной метрики Airtime link уве­ личивает вероятность выполнения требований к качеству обслуживания для мультимедийных потоков реального времени и емкость сети. Например, на рис. 2 изображена зависимость доли голосовых данных, не доставлен­ ных с удовлетворительным качеством обслуживания, от нагрузки на сеть из 64 станций, размещенных случайно на площадке 5 5 радиусов радиопри­ ема. Если = 30% станций являются источниками голосовых пакетов, то использование предложенных метрик уменьшает с 6% до 2%.

Однако, при использовании MCCA время обслуживания каждого паке­ та не зависит от загруженности сети, что делает вышеупомянутые метрики неэффективными. В то же время при установлении резервирования станция должна учитывать степень занятости канала, а именно – суммарную долю временных ресурсов сети внутри одного DTIM-интервала, которые мо­ гут быть заняты при использовании данной станцией и ее соседями метода MCCA. Эта доля ограничена параметром. Поэтому для детер­ Рис. 2. Доля голосовых данных, не доставленных с удовлетворительным качеством обслу­ живания, при различных метриках и методах доступа (слева: случайный, справа: детер­ минированный) минированного метода доступа предлагается метрика Maf-metric, значение которой для соединения между станциями и определяется по формуле = 1 +, где – максимальное из значений суммар­ ной доли интервалов времени, зарезервированных MCCA, на станциях, и их соседях, – время занятости канала при передачи 1 пакета определенной длины, – среднее число попыток передачи, которое надо совершить, чтобы успешно передать пакет по соединению, – настраиваемый параметр, значе­ ние которого принято равным 2 согласно результатам имитационного моде­ лирования. Как показало имитационное моделирование, при использовании MCCA метрика Maf-metric обеспечивает большую до полутора раз емкость сети, чем метрика Airtime link (см. рис. 2).

Основные результаты четвертой главы опубликованы в [1, 2, 10–12, 14].

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

Основные результаты В данной диссертации разработан комплекс аналитических и имитаци­ онных моделей для анализа механизмов доставки потоковых данных с требу­ емым качеством обслуживания в mesh-сетях и сетях MANET. В частности:

1. Разработана аналитическая модель передачи данных постоянной интен­ сивности с заданными требованиями к качеству обслуживания при ис­ пользовании детерминированного метода доступа в сетях Wi-Fi Mesh в условиях помех.

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

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

4. При помощи разработанной имитационной модели сети MANET иссле­ дованы ошибки маршрутизации, возникающие при использовании про­ токола маршрутизации OLSR, и показано, что использование дополни­ тельных модулей реактивного распространения информации о соедине­ ниях и информации об ошибках маршрутизации позволяет в 2-3 раза снизить вероятность этих ошибок.

5. Предложены метрики маршрутизации для случайного и детерминиро­ ванного методов доступа, и показано, что их использование увеличивает емкость сети до полутора раз по сравнению с метрикой маршрутизации, описанной в стандарте IEEE 802.11s.

Список публикаций 1. Khorov Evgeny, Safonov Alexander. Multiple metrics in MANET with end­ to-end QoS support for unicast and multicast traffic // Lecture Notes in Computer Science, Vol. 6235. 2010. Pp. 251–262.

2. Khorov Evgeny, Lyakhov Andrey, Safonov Alexander. Flexibility of Routing Framework Architecture in IEEE 802.11s Mesh Networks // Proceedings of the 8th IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS). 2011. Pp. 777–782.

3. А.Г. Кирьянов, А.И. Ляхов, А.А. Сафонов, Е.М. Хоров. Метод оценки эффективности механизмов управления соединениями в беспроводных самоорганизующихся сетях // Автоматика и телемеханика. 2012. № 5.

С. 39–56.

4. А.И. Ляхов, А.А. Сафонов, Е.М. Хоров. Распределение времени присо­ единения устройств к беспроводной персональной сети с распределенным управлением // Труды конференции «Информационные технологии и си­ стемы». 2010. № 2. С. 42–53.

5. Shvets Evgeny, Lyakhov Andrey, Safonov Alexander, Khorov Evgeny. Analyt­ ical model of IEEE 802.11s MCCAbased streaming in the presence of noise // SIGMETRICS Perform. Eval. Rev. 2011. Vol. 39, no. 2. Pp. 38–40.

6. А.И. Ляхов, Д.М. Островский, Е.М. Хоров. Аналитическое исследование качества соединений, открытых протоколом NHDP // Информационные процессы. 2012. Т. 12, № 1. С. 105–116.

7. А.Г. Кирьянов, Е.М. Хоров, Д.М. Островский. Аналитический метод ис­ следования механизма управления соединениями в мобильных многоша­ говых беспроводных сетях на примере протокола NHDP // Труды конфе­ ренции «Информационные технологии и системы». 2011. С. 258–264.

8. А.Г. Кирьянов, А.А. Сафонов, Е.М. Хоров. Аналитическое исследование эффективности механизмов управления соединениями в меш-сетях IEEE 802.11s // Труды конференции «Информационные технологии и систе­ мы». 2011. С. 9–16.

9. Е.М. Хоров. Исследование влияния рассылки биконов на передачу пе­ риодического трафика при помощи MCCA в меш-сетях IEEE 802.11s // Труды конференции «Информационные технологии и системы». 2011.

10. П.О. Некрасов, А.А. Сафонов, Е.М. Хоров. Анализ совместного исполь­ зования проактивного и реактивного способов рассылки сетевой инфор­ мации в сетях MANET // Труды конференции «Информационные техно­ логии и системы». 2011. С. 1–8.

11. А.Г. Кирьянов, А.А. Сафонов, Е.М. Хоров. Методы исследования переход­ ных характеристик протокола OLSR при включении/выключении узла сети // Труды конференции «Информационные технологии и системы».

12. А.А. Сафонов, Е.М. Хоров, А.Н. Красилов. Анализ эффективности про­ токола OLSR в канале 5МГц // Труды конференции «Информационные технологии и системы». 2010. С. 11–19.

13. А.А. Сафонов, Е.М. Хоров, П.О. Некрасов. Анализ эффективности ме­ тодов оптимизации рассылки сетевой информации в сетях MANET. // Труды конференции «Информационные технологии и системы». 2010.

14. П.О. Некрасов, Д.А. Платов, Е.М. Хоров. Методы повышения качества передачи голосовых потоков по меш-сети путем изменения механизма обслуживания пакетов в очереди Информационные технологии и систе­ мы // Труды конференции «Информационные технологии и системы».

2011. С. 394–399.

15. Е.М. Хоров. Метрика маршрутизации для трафика, чувствительного к задержкам // Труды конференции «Информационные технологии и си­ стемы». 2010. С. 11–19.