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

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

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

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

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

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

1 о ¿г,!?

I*.

Москва - 2012

005017101

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

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

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

Официальные оппоненты: Степанов Сергей Николаевич,

доктор технических наук, профессор,

ОАО с Интеллект-телеком», директор информационно-аналитического департамента

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

Ведущая организация: Федеральное государственное

бюджетное учреждение науки Институт проблем информатики Российской академии наук

Защита состоится 2012 г. в ^- часов на заседании

диссертационного совета Д 002.077.01 на базе ИППИ РАН, расположенном

по адресу: Большой Каретный пер., д. 19, стр. 1, Москва, ГСП-4, 127994

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

Автореферат разослан « ¿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).

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

Исследованию эффективности доставки данных в многошаговых беспроводных самоорганизующихся сетях посвящено значительное количество работ, среди которых следует особо отметить работы российских и зарубежных ученых: О.М. Брехова, A.B. Винеля, Н.Д. Введенской, А.Б. Гольдштейн, A.A. Гончарова, А.П. Кулешова, Д.В. Лаконцева, А.И. Ляхова, Д.Н. Мацне-ва, В.И. Неймана, Д.С. Осипова, А.Н. Рыбко, A.A. Сафонова, О.Д. Соколовой, С.Н. Степанова, И.И. Цитовича, М-Ю. Якимова, G. Bianchi, Т. 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. Разработка аналитической модели передачи данных постоянной интенсивности с выполнением требований к качеству обслуживания в условиях помех с помощью периодических резервирований канала.

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 IEËE 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). Случайный выбор момента начала передачи пакета является причиной возможных коллизий - одновременной передачи пакетов несколькими станциями, приводящей к тому, что приемник не может правильно декодировать сигнал и не получает ни один из переданных пакетов. Если приемник получает пакет, он подтверждает получение пакета с помощью кадра АСК. Если станция-отправитель не получает АСК, она повторяет передачу пакета до тех пор, пока не получит АСК или не будет достигнут допустимый порог

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

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

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

Стандарт ограничивает суммарную долю MAF временных ресурсов канала, которая может быть занята МССА, с помощью порога MAFLimit. Если при создании нового резервирования MAF превышает MAF Limit на самой станции или на ее соседях, то станция отказывается от нового резервирования.

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

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

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

В (в третьей главе рассматривается обобщенная схема, в которой открытие происходит по г > 1 HELLO-сообщениям, полученным подряд). При потере s HELLO-сообщений подряд станция А закрывает соединение со станцией В и прекращает указывать адрес станции В в своих HELLO-сообщениях (состояние соединения - L). Открытое соединение (О) может быть однонаправленным (Я) или симметричным (SYM). Если в последнем полученном HELLO-сообщении, отправленном станцией А, указан адрес станции В, то станция В считает соединение симметричным, иначе - однонаправленным.

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

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

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

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

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

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

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

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

Разработанная модель позволяет для произвольных значений £*, Б и где - интервал между между приходами пакетов, определить долю РЬК потерянных пакетов.

В модели время делится на слоты, причем 1) размер слота г выбирается таким образом, что = ¿,г, = ^т и 1С,ЬР 6 N - взаимно простые числа; 2) начало каждого зарезервированного интервала совпадает с началом некоторого слота. Так как интервал времени между поступлениями в очередь двух пакетов содержит целое число слотов г, интервал времени £ между поступлением в очередь пакета и началом очередного слота одинаков для всех пакетов, 0 < £ < т.

Передача пакета представляется одномерной марковской цепью с дискретным временем (моменты наблюдения - начала зарезервированных интервалов, т.е. продолжительность шага - £г). Состояние /¡.(4) описывается целым числом следующим образом. Если очередь непуста, то к({) > 0 и И^) + £ соответствует времени ожидания в очереди самого старшего пакета, выраженному в слотах. Если очередь пуста, то Л(£) < 0 и + время до поступления следующего пакета в очередь. Минимальное значение /г(£) равно £,. — Это значение достигается в момент А -Ь 1, когда пакет поступает в пустую очередь в момент t и тут же успешно передается. Очевидно, что максимальное значение Л(£) равно в, = [—.

Стационарные вероятности 717,, И. € {—+ ..., состояний такого процесса описываются системой линейных уравнений:

( 7Гд = аи • 7Г/,_{Г + Рн ■ 7Г ь-Ир-г,, /I 6 {-Ьр +

I Ел—= 1'

где

{О, к<-1р + 2Ьг, ( 0, /г > ^ - + гг,

1 -р, и <Н<(1, , Рн = < р, /г < (1 -

1, -Ьр + 2Ьг<к<^ [ 1, й - Ц < Л < ё. - гр + и,

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

<г

РЬЕ = (1-р)1р/и

Л=й-(г+1

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

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

базовой модели при анализе многошаговой передачи, что сделано в работах других авторов.

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

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

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

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

тт{плк)

{тг) = ^ (ппг(к,1,т,п)),

771=1

где тг(кЛ,т,п) = — вероятность того, что при размещении п бико-

нов в Ы слотах было занято ровно т столбцов, а У(1,т,п) - число размещений п биконов без коллизий ровно в т выбранных столбцах размером I:

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

Относительная емкость сети

20%

"■^Регулярное.....

• Случайное

10 20 30 Число устройств

Рис. 1. Относительная емкость сети при различном числе устройств

этом случае п биконов блокируют только тд групп: тд = [у], где fx] минимальное целое число, не меньшее х. В диссертации описан алгоритм, согласно которому станции размещают свои биконы именно таким образом.

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

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

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

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

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

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

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

В диссертации рассматривается задача поиска таких наборов значений параметров г и s МУС, которые обеспечивают выполнение следующих требований. 1) Необходимо, чтобы соединения с р > ро были преимущественно открыты, а соединения с р < ро преимущественно закрыты. Это эквивалентно условию: тг(ро) = 0,5, где тг(р) - вероятность того, что соединение симметрично при заданном р (далее р для сокращения записи будем опускать). Вероятность 7Г определяется по формуле 7г = (Гдум)+(Tgyg)1 ГДЙ ^sym) ~ среднее время, в течение которого соединение непрерывно симметрично, а {Т^ум)

- среднее время, в течение которого соединение находится в других состояниях (закрыто или однонаправленно). 2) Частота смены состояния соединения д = (TsYuHiT^yj-) Должна быть много меньше порога до = Ти^и' где ^Update

- период обновления информации о соединениях. 3) Наконец, среднее время {Tfeiay} принятия решения механизмом управления соединениями должно быть много меньше интервала времени, в течение которого р > ро- При медленном изменении р {Tdday) ~ (7'doseipn)), При быстром - (Tdelay) ~ г. гДе г ~ число сообщений, которое надо подряд получить, чтобы открыть соединение.

В диссертации разработаны аналитические модели, позволяющие для заданных параметров МУС оценить значения показателей эффективности Я", 9 и {Tdelay).

Для МУС, реализуемого протоколом NHDP, построена модель, позволяющая оценить значения тг и {Tsym), через которые можно выразить все показатели эффективности. Чтобы определить 7Г, вначале находится вероятность Ро того, что станция, для определенности А, считает, что состояние соединения 0\ Ро = (t!0)°\tl)> где (То) и {Ть) определяются следующим утверждением, доказанным с применением аппарата производящих функций.

Утверждение 1. Средние длительности {То) и (TL) состояний О и L определяются выражениями:

,Т \ - /Т \ - 1~рГ

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

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

Для определения,Tsym рассматриваются независимые On-Off процессы /0A\t) и J^\t) изменения состояния станций А и В соответственно и определяется процесс Jsr\f(t) переходов между состояниями SYM* и SYM* следующим образом. Процесс Jsy.w(i) находится в состоянии SYM* тогда и только тогда, когда оба процесса jjf\t) и J(f\t) находятся в состоянии О; в остальных случаях процесс JsYM-(t) находится в состоянии SYM*.

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

Утверждение 3. Математическое ожидание (Tsym•) длительности состояния SYM* определяется выражением (Tsym*) —

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

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

При анализе РМР подход, используемый для NHDP, оказывается непригодным, поэтому разработан другой метод, позволяющий определить значения величин (Tsym) и (Т^ум), однозначно определяющих все показатели эффективности. Этот метод сводится к анализу последовательности {ct}i° полученных биконов: <т( = 1, если в момент времени t станция А получила бикон от В, и сг( = 0, если бикон не был получен.

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

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

pEf^pfW'1-'-1)' n>s-1.

1

о < п < s - 1,

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

11°°

{Tsym} = 2 + т; £ Шк) + Ф.Л - 1)ф.*{к)} ■

fc=1

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

1 1 00

{Tsym) = ~ + о £ №,i-P(k) + ~ -

Ь=1

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

(Tsym) = 5 + о £ [02r-i,i-p(2fc) + 0ar-i.i-„(2fc - 1)].

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

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

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

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

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

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

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

Назовем маршрут го -4 гп от источника г'о до конечного получателя гп в некоторый момент времени корректным, если в этот момент существует множество различных станций {г,;. } таких, что \/г = 0,1, ...,п — 1 в таблице маршрутизации станции г,; существует запись о маршруте до станции гп через станцию г!+1., находящуюся в области радиоприема станции Г;. Наличие корректного маршрута будем обозначать {ОК). В остальных случаях происходит одна из ошибок маршрутизации, которую обозначим - (а, /3,7):

• а может принимать одно из двух значений: "+", если го и гп находятся в одной компоненте связности сети; "—в остальных случаях;

• Р характеризует тип возникшей ошибки: "Г, если маршрут зациклился; "е", если в таблице маршрутизации одной из станций, через которую проходит маршрут, отсутствует запись о маршруте; "р", если некоторая станция Г{ передает пакет станции Гг+ь которую все еще считает своим соседом, но которая уже находится вне области радиоприема

• 7 принимает одно из двух значений: "в", если ошибка произошла на источнике; "г", если ошибка произошла на промежуточном ретрансляторе.

Например, ошибка (—, е, я) происходит, когда го и гп находятся в различных компонентах связности сети и в таблице маршрутизации го нет необходимой для маршрутизации пакета записи. Правильная работа протокола приводит к тому, что для любой пары источника и конечного получателя выполняется одно из двух условий: либо имеется корректный маршрут ((ОК)), либо, если источник и конечные получатели находятся в разных компонентах связности, (—,е,я).

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

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

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

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

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

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

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

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

Однако, при использовании МССА время обслуживания каждого пакета не зависит от загруженности сети, что делает вышеупомянутые метрики неэффективными. В то же время при установлении резервирования станция должна учитывать степень занятости канала, а именно суммарную долю MAF временных ресурсов сети внутри одного DTIM-интервала, которые могут быть заняты при использовании данной станцией и ее соседями метода МССА. Эта доля ограничена параметром MAFLim.it. Поэтому для детер-

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

минированного метода доступа предлагается метрика Maf-metric, значение которой для соединения между станциями г и j определяется по формуле C\iaf = 1 + (мafLimit) ^паи где MAF максимальное из значений суммарной доли интервалов времени, зарезервированных МССА, на станциях г, j и их соседях, tch - время занятости канала при передачи 1 пакета определенной длины, nat - среднее число попыток передачи, которое надо совершить, чтобы успешно передать пакет по соединению, 7 - настраиваемый параметр, значение которого принято равным 2 согласно результатам имитационного моделирования. Как показало имитационное моделирование, при использовании МССА метрика 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. А.Г. Кирьянов, А.И. Ляхов, A.A. Сафонов, Е.М. Хоров. Метод оценки эффективности механизмов управления соединениями в беспроводных самоорганизующихся сетях // Автоматика и телемеханика. 2012. № 5. С. 39 56.

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

5. Shvets Evgeny, Lyakhov Andrey, Safonov Alexander, Khorov Evgeny. Analytical 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. А.Г, Кирьянов, A.A. Сафонов, Е.М. Хоров. Аналитическое исследование эффективности механизмов управления соединениями в меш-сетях IEEE 802.11s // Труды конференции «Информационные технологии и системы». 2011. С. 9-16.

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

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

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

2010. С. 20-29.

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

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

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

2011. С. 394-399.

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

Подписано в печать: 24.04.2012

Заказ № 7287 Тираж -100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

61 12-5/2503

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

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

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

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

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

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

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

д. т. н., с. н. с.

Ляхов Андрей Игоревич

Москва - 2012

Содержание

Введение ......................................................................................4

Глава 1. Особенности механизмов доставки данных в самоорганизующихся

беспроводных сетях ....................................................................8

1.1. Назначение беспроводных многошаговых самоорганизующихся сетей .... 8

1.2. Сети MANET ........................................................................10

1.3. Сети Wi-Fi Mesh стандарта IEEE 802.11s ........................................24

1.4. Критерии эффективной работы сети..............................................32

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

Глава 2. Анализ эффективности метода детерминированного доступа . . 41

2.1. Исследование передачи потоковых данных с помощью метода детерминированного доступа......................................................................41

2.2. Анализ влияния метода размещения биконов на метод детерминированного доступа................................................................................46

2.3. Выводы ко второй главе ............................................................57

Глава 3. Исследование механизмов управления соединениями..............59

3.1. Показатели эффективности механизма управления соединениями............60

3.2. Модель МУС без синхронизации состояний соединений ........................62

3.3. Модель МУС с синхронизацией состояний соединений..........................70

3.4. Численные результаты..............................................................78

3.5. Результаты сравнения механизмов управления соединениями ................85

3.6. Выводы к третьей главе ............................................................86

Глава 4. Исследование механизмов маршрутизации............................88

4.1. Анализ ошибок маршрутизации, возникающих в сети MANET под управлением протокола OLSR ..............................................................88

4.2. Исследование совместного использования проактивного и реактивного подхода при рассылке информации о соединениях..................................99

4.3. Метрики маршрутизации для случайного метода доступа...........108

4.4. Метрика маршрутизации для детерминированного метода доступа .....124

4.5. Выводы к четвертой главе.............................129

Заключение .........................................131

Литература .........................................132

Приложение А. Акты о внедрении результатов диссертации ........140

Введение

Актуальность работы

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

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

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

Исследованию эффективности доставки данных в многошаговых беспроводных самоорганизующихся сетях посвящено значительное количество работ, среди которых следует особо отметить работы российских и зарубежных ученых: О.М. Брехова, A.B. Ви-неля, Н.Д. Введенской, A.B. Гольдштейн, A.A. Гончарова, А.П. Кулешова, Д.В. Лакон-

цева, А.И. Ляхова, Д.Н. Мацнева, В.И. Неймана, Д.С. Осипова, А.Н. Рыбко, A.A. Сафонова, О.Д. Соколовой, С.Н. Степанова, И.И. Цитовича, М.Ю. Якимова, G. Bianchi, Т. 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. Разработка аналитической модели передачи данных постоянной интенсивности с выполнением требований к качеству обслуживания в условиях помех с помощью периодических резервирований канала.

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 статей ([715]) в сборниках трудов конференций. Подготовка к публикации полученных результатов проводилась совместно с соавторами, причем вклад диссертанта был определяющим.

Структура и объем диссертации

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

Глава 1

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

1.1. Назначение беспроводных многошаговых самоорганизующихся сетей

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

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

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

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

Отказ от архитектуры «клиент-сервер» при построении сетей класса ad hoc делает решения задачи последней мили и решения задачи построения децентрализованных сетей существенно разными, что наиболее ярко отражено в разработанном международным комитетом IEEE 8021 стандарте IEEE 802.11 [16] беспроводных локальных сетей, известных под торговой маркой Wi-Fi, - в стандарте описаны два типа сетей: инфраструктурные сети и сети ad hoc.

Технология инфраструктурных сетей (Wi-Fi Hotspot) широко известна по миллионам точек беспроводного доступа, развернутых во всем мире. Опираясь на проводную инфраструктурную сеть, точки доступа предоставляют клиентским станциям, как правило, выход в Интернет. Благодаря своему широкому распространению и простоте технология Wi-Fi Hot Spot хорошо изучена и в данной работе рассматриваться не будет.

Сети ad hoc, не требующие инфраструктуры, в рамках базового стандарта IEEE 802.11 являются одноранговыми сетями, в которых каждая станция находится в зоне непосредственного радиоприема всех остальных станций. Однако с момента начала работы над стандартом появилось множество новых задач, связанных с развертыванием таких беспроводных сетей, как:

• домашние, офисные и заводские сети;

• сети университетских городков;

• муниципальные и коммерческие публичные сети;

• сети транспортных узлов (автомобилей, а в последние несколько лет и самолетов);

• сети, развертываемые в зонах чрезвычайных ситуаций;

• сети военного назначения.

Эти задачи требовали расширения зоны покрытия сети и обеспечения бесперебойной работы движущихся станций.

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

1 В рамках комитета IEEE 802 LAN/MAN Standards Committee (Комитет Института инженеров электротехники и электроники по стандартам локальных и городских сетей) оформились в виде стандартов такие технологии, как Ethernet, Token Ring, Wi-Fi, Bluetooth и WiMAX,

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

Движение же станций означает, что топология сети меняется со временем и станции могут в течение своей работы находиться то в зоне непосредственного радиоприема друг друга, то за пределами этой зоны. Технологиями, призванными расширить зону покрытия сети и обеспечить бесперебойную работу движущихся станций, стали технология самоорганизующихся мобильных ad hoc сетей MANET [17], оформленная в виде спецификаций организации IETF (англ.: Internet Engineering Task Force - Инженерный совет Интернета), и технология сетей Wi-Fi Mesh[18], разработанная в комитете IEEE 802 LAN/MAN Standards Committee.

1.2. Сети MANET

Сети MANET (англ.: Mobile Ad hoc NETwork - мобильная децентрализованная сеть) представляют собой сети, координация которых осуществляется на сетевом уровне, а доступ к каналу осуществляется с помощью одной из уже существующих технологий, допускающей построение децентрализованных сетей. Наибольшее развитие и известность получили сети MANET, построенные на базе технологии Wi-Fi ad hoc, и использующие для многошаговой доставки пакетов протоко