Назад в библиотеку

УДК 004.724.4

В.М. Винокуров, А.В. Пуговкин, А.А. Пшенников, Д.Н. Ушарова, А.С. Филатов

Маршрутизация в беспроводных мобильных Ad hoc-сетях


Источник:http://old.tusur.ru/filearchive/reports-magazine/2010-2-1/288.pdf

Аннотация

Описаны особенности маршрутизации в беспроводных самоорганизующихся сетях Ad hoc и представлен обзор соответствующих протоколов маршрутизации. Показано, что для оценки работоспособности протоколов маршрутизации в условиях мобильных Ad hoc-сетей наиболее доступным и достоверным средством в настоящее время является имитационное моделирование. Приведен пример моделирования работы протоколов маршрутизации: AODV, DSR, LANMAR, OLSR, OSPFv2, ZRP. Ключевые слова: Ad hoc-сеть, протокол маршрутизации, время построения маршру- та, коэффициент доставки пакетов, имитационное моделирование.


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

Специфика сетей Ad hoc состоит в том, что их топология постоянно изменяется из-за перемещения узлов сети в пространстве или изменения условий распространения радио- сигнала. Помимо этого, для Ad hoc-сетей, как и для любых беспроводных систем, ха- рактерны ограниченные полоса пропускания и зона радиовидимости. В результате прото- колы и технические решения, используемые в классических проводных сетях передачи данных, например централизованная маршрутизация с иерархией заранее назначенных маршрутизаторов, в сетях Ad hoc оказываются неэффективными и не обеспечивают нуж- ную производительность [1]. Для успешного применения в Ad hoc-сетях протоколы маршрутизации должны обла- дать следующими качествами:


1. Быть распределенными. Все узлы в сети должны быть способны осуществлять мар- шрутизацию и не иметь жестко закрепленных за собой функций.
2. Обеспечивать надежную доставку пакетов в условиях постоянно изменяющейся топологии сети, когда использование классических механизмов гарантированной достав- ки, как, например, на транспортном уровне в протоколе ТСР, затруднено.
3. Обеспечивать малое время построения маршрута в условиях постоянно изменяю- щейся топологии сети.
4. Обладать механизмами оперативного обнаружения разрыва маршрута и его вос- становления.
5. Не допускать образования петель в маршрутах.
6. Рассылать при функционировании как можно меньший объем служебной инфор- мации.
7. Обладать высокой масштабируемостью, т.е. обеспечивать высокую производитель- ность сети при различных ее размерах.
8. Поддерживать QoS.

Существующие на данный момент протоколы маршрутизации можно классифициро- вать следующим образом [1–2].
По типу используемых для маршрутизации данных:

1) Топологические. Используют информацию о существующих сетевых соединениях между узлами сети.

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

По принципу работы:

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

2) Реактивные или работающие по запросу (англ. reactive, on-demand). Составляют маршруты до конкретных узлов лишь при возникновении необходимости в передаче им информации. Для этого узел-отправитель широковещательно рассылает по сети сообще- ние-запрос, которое должно дойти до узла-адресата. В ответ адресат высылает сообщение- подтверждение, из которого отправитель узнает необходимый маршрут и записывает его в свою таблицу маршрутизации. Для повторных отправок сообщений данному адресату маршрут просто считывается из таблицы. Если обнаруживается его разрушение, то за- пускается так называемая процедура поддержания маршрута, которая фактически за- ключается в поиске нового маршрута до адресата.

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

По критерию определения оптимальности маршрута:
1) Протоколы вектора расстояния (англ. distance-vector, hop-count). Всегда считают оптимальным маршрут, содержащий наименьшее число хопов (ретрансляций пакета) между отправителем и адресатом.

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

По числу задействованных в маршрутизации уровней ЭМВОС: 1) Одноуровневые. Работают чисто на сетевом уровне, поэтому обладают универ- сальностью и сетевой прозрачностью.

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

1) Однопутевые (англ. single-path). При обработке информации о топологии сети дан- ные протоколы выбирают лишь один, наиболее оптимальный, маршрут до адресата и заносят его в свою таблицу маршрутизации.

2) Многопутевые (англ. multi-path). В отличие от однопутевых, заносят в таблицу маршрутизации два или несколько наиболее оптимальных маршрутов до адресата. В слу- чае обнаружения разрушения основного маршрута данные протоколы просто считывают из таблицы запасной, а не инициализируют процедуру повторного построения маршрута. Также при обнаружении перегрузки сети по основному маршруту многопутевые протоко- лы могут перераспределять часть нагрузки на резервные. Каждый класс протоколов потенциально имеет свои преимущества и недостатки при использовании в условиях мобильных Ad hoc-сетей. Например, проактивные протоколы обладают явным преимуществом перед реактивными во времени построения маршрута. У проактивных протоколов этот процесс, по сути, происходит заранее, и требуется лишь

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

Однако приведенные выше рассуждения являются сугубо абстрактными и оторван- ными от конкретных практических реализаций. Адекватное сравнение протоколов с чисто теоретических позиций затруднено тем, что на процесс передачи данных в Ad hoc-сетях оказывает влияние большое число различных факторов, многие из которых носят слу- чайных характер и слабо поддаются строгому математическому анализу. Поэтому основ- ным инструментом сравнительного анализа протоколов маршрутизации при работе в Ad hoc-сетях является имитационное моделирование, которое в целях экономии времени и средств первоначально осуществляется посредством компьютерных программ-симулято- ров, без применения реального оборудования [3].

Симуляторы моделируют работу всех уровней ЭМВОС. Для сетей радиосвязи присут- ствуют модель радиоканала, учитывающая распространение радиоволн используемого частотного диапазона, а также модели, описывающие пространство. Совокупность выше- перечисленных свойств симулятора определяет адекватность проводимых на нем экспе- риментов и достоверность получаемых при этом результатов.

В настоящий момент усилиями исследователей со всего мира были созданы следую- щие протоколы маршрутизации, наиболее часто используемые в Ad hoc-сетях [1-3]:


1) AODV (Ad hoc On-Demand Distance Vector). Реактивный протокол маршрутизации, разработанный для использования в сетях различного размера. Представляет собой ком- бинацию двух протоколов: реактивного DSR и проактивного DSDV, от которого он на- следует концепцию hello-сообщений. Это служебные сообщения, рассылаемые на рас- стояние одного хопа, которые служат для поддержания узлом актуального списка своих соседей. Это в итоге позволяет несколько ускорить процесс рассылки запросов на построе- ние маршрута. Протокол описан в документе «IETF Request for Comments 3561» от июля 2003 г. Одна из модификаций протокола, адаптированная для работы с адресами МАС- уровня и метриками маршрутов, под названием HWMP (Hybrid Wireless Mesh Protocol) используется в стандарте IEEE 802.11s.

2) DSR (Dynamic Source Routing). Реактивный протокол, разработанный специально для использования в небольших (диаметром в 5-10 хопов) Ad hoc-сетях с умеренной мо- бильностью узлов. Описан в документе «IETF Request for Comments 4728» от февраля 2007 г.

3) OLSR (Optimized Link-State Routing). Проактивный протокол, который является попыткой адаптации классического LSR (Links State Routing) к использованию в услови- ях беспроводных сетей. Основным нововведением является концепция многоточечных ретрансляторов, которая оптимизирует процесс широковещательной рассылки, значи- тельно сокращая объемы рассылаемой информации. Протокол OLSR описан в документе «IETF Request for Comments 3626» от октября 2003 г. Одна из модификаций протокола под названием RA-OLSR (Radio Aware-OLSR) используется в стандарте IEEE 802.11s.

4) OSPF MANET. Под этим общим названием объединяют несколько протоколов, являющихся попытками адаптации классического проактивного протокола OSPF (Open Shortest Path First) к использованию в условиях беспроводных сетей. Варианты OSPF MANET-MPR и OSPF MANET-OR/SP, подобно OLSR, используют концепцию многото- чечных ретрансляторов, а OSPF MANET-MDR придерживается традиционных алгоритмов, заложенных в OSPF. Все протоколы OSPF MANET описаны в рамках соответствующих интернет-драфтов.

5) FSR (Fisheye State Routing). Иерархичный проактивный протокол, целью создания которого была попытка уменьшить объем рассылаемой по сети служебной информации за счет использования концепции «рыбьего глаза», где каждый узел сети осуществляет ши- роковещательные рассылки до узлов с различной частотой: чем дальше находится узел, тем реже ему осуществляется рассылка. Протокол был разработан на базе фирмы Lucent Technologies в 2000 г.

6) LANMAR (Landmark routing protocol). Гибридный протокол, который объединяет узлы в группы по принципу их склонности к совместному передвижению в качестве еди- ной группы. В каждой из групп один узел динамически назначается так называемой ре- перной точкой, которая служит своеобразным «маяком» при пересылке пакетов между узлами различных групп. Протокол был разработан на базе Калифорнийского универси- тета в сотрудничестве с Rockwell Scientific Company в 2002 г.

7) ZRP (Zone Routing protocol). Протокол, разработанный для использования в круп- ных мобильных Ad hoc-сетях с небольшой плотностью размещения узлов и реализующий классическую концепцию гибридной маршрутизации. Разработан в Корнеллском универ- ситете в 2002 г.

В дальнейшем авторами статьи планируется произвести детальное сравнение выше- указанных протоколов путем имитационного моделирования их работы в различных ус- ловиях, совокупность которых принято называть сценариями работы сети. На основании анализа полученных результатов планируется внести в наиболее перспективные протоко- лы доработки, повышающие их эффективность, или же создать на их основе новый про- токол. Ниже в качестве примера приведены результаты одного подобного эксперимента, произведенного в симуляторе «QualNet Developer 4.5». Измерялась зависимость коэффи- циента доставки пакетов (отношения числа принятых пакетов с данными к числу пере- данных) от размера сети для протоколов AODV, DSR, LANMAR, OLSR, OSPFv2, ZRP в условиях следующего сценария:

- модель канального уровня – IEEE 802.11b (Wi-Fi), с распределенной функцией управления (MAC DCF) и жестко зафиксированной пропускной способностью 2 Мб/с; - рабочий диапазон – 2,4 ГГц;


- мощность передатчиков каждого узла – 15 дБм;
- чувствительность приемников каждого узла – (–89) дБм;
- тип антенны – ненаправленная, с коэффициентом усиления 0 дБ, эффективностью 0,8 и потерями в фидере 0,5 дБ, высота подвеса 1,5 м;
- модель распространения сигнала – двулучевая;
- размеры сети – 16, 25, 64 и 100 узлов соответственно;
- узлы сети перемещаются со скоростью 16 м/с на плоской поверхности, ограничен- ной квадратами со сторонами 1,4, 1,6, 2,3 и 2,8 км соответственно, с паузами по 4 с, после чего случайным образом меняют направление движения;
- количество активных соединений в сети – 4;
- тип трафика – CBR (Constant Bit Rate) с размером пакета 512 байт и интенсивно- стью отправки 10 пакетов в секунду;
- протокол транспортного уровня – UDP;
- время работы сети – 300 с.
Результаты моделирования, усредненные по всем четырем соединениям и трем экспериментам, приведены на рис. 2.

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


Литература


1. Azzedine Boukerche. Algorithms and protocols for wireless, mobile ad hoc networks. – New Jersey: John Wiley & Sons, Inc., 2009. – 495 p.

2. Carlos de Morais Cordeiro. Ad hoc & Sensor Networks, Theory and Applications / Carlos de Morais Cordeiro, Dharma Prakash Agrawal. – Singapore: World Scientific Pub- lishing Co, 2006. – 642 p.

3. Julian Hsu Bhatia. Performance of Mobile Ad hoc Networking Routing Protocols in Large Scale Scenarios / Julian Hsu Bhatia, S. Tang, K. Bagrodia, R. Acriche // IEEE Military Communications Conference. – 2004. – Vol. 1. – P. 21–27. 

Винокуров Владимир Михайлович 
Канд. техн. наук,   профессор каф. телекоммуникаций и основ радиотехники (ТОР) ТУСУРа 
Тел.: (382-2) 41-33-98 
Эл. почта: VinokurovVM@tor.tusur.ru
Пуговкин Алексей Викторович Докт. техн. наук, профессор каф. ТОР ТУСУРа Тел.: (382-2) 41-33-98 Эл. почта: PugovkinAV@tor.tusur.ru Пшенников Артур Андреевич Аспирант каф. ТОР ТУСУРа Эл. почта: PshennikovAA@tor.tusur.ru Ушарова Дарья Николаевна Техник каф. ТОР ТУСУРа Эл. почта: UDN@sibmail.com Филатов Александр Сергеевич Аспирант каф. ТОР ТУСУРа Эл. почта: dimentius@mail.ru Vinokurov V.M., Pugovkin A.V., Pshennikov A.A., Usharova D.N., Filatov A.S. Routing in wireless mobile Ad hoc networks The routing features in wireless Ad hoc networks are described. The corresponding routing protocols are reviewed. It is shown that the simulation is the most accessible and reliable technique for evaluat- ing the routing protocols performance in present mobile Ad hoc networks. An example of the perform- ance simulation in mobile Ad hoc network is presented for such protocols as AODV, DSR, LANMAR, OLSR, OSPFv2, ZRP. Keywords: Ad hoc network, routing protocol, route settling time, packet delivery ratio, simulation.