Библиографическое описание:

Ткачев Д. Ф., Лящук М. З., Лисейкин Р. Е. Реактивный алгоритм динамической маршрутизации в перспективной мобильной сети, построенной на радиосредствах нового поколения // Молодой ученый. — 2016. — №11. — С. 501-505.



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

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

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

Проактивные протоколы, называемые также табличными, предполагают создание на каждой мобильной станции таблиц маршрутизации, содержащих информацию о маршрутах со всеми станциями сети [4]. Маршрутная информация обновляется с помощью передачи служебных сообщений об изменениях топологии сети. По сформированной на основании служебных сообщений топологии сети производится предварительное построение таблиц маршрутов, которые хранятся в памяти каждого узла для немедленной передачи поступивших пакетов любому получателю. Примерами данных протоколов являются: DSDV (Destination Sequenced Distance Vector), OLSR (Optimized Link State Routing), TBRPF (Topology Dissemination Base on Reverse-path Forwarding), FSR (Fisheye State Routing).

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

При высоком уровне трафика в мобильной сети применение реактивных протоколов менее желательно, так как частый поиск маршрутов ведет к постоянным лавинным рассылкам пакетов в сети. Примерами реактивных протоколов являются: DSR (Dynamic Source Routing), AODV (Ad hoc On-Demand Distance Vector), ТОRА (Temporally Ordered Routing Algorithm).

Гибридные протоколы маршрутизации получили такое название из-за объединения на различных уровнях иерархии сети свойств проактивных и реактивных протоколов. Гибридные протоколы более эффективны на многоуровневых сетях. К ним относятся следующие протоколы: HWMP (Hybrid Wireless Mesh Protocol), HDVG (Hierarchical Distance-Vector Georouting), ZRP (Zone Routing Protocol) [5].

Применение того или иного протокола маршрутизации напрямую зависит от особенностей планируемой сети связи, и окончательный выбор протокола возможен только после детального рассмотрения данной сети. В структуре мобильной распределенной сети радиосвязи, построенной на радиосредствах нового поколения, можно выделить несколько основных типов беспроводных сетей [3]: распределенные сети радиодоступа конечных пользователей (абонентов), городские распределенные опорные сети и магистральную региональную опорную сеть. При этом в распределенных сетях радиодоступа используются в основном портативные (носимые) радиостанции, а в опорных сетях, к которым подключаются базовые станции сетей радиодоступа, используются возимые базовые (узловые) радиостанции.

Исходя из того, что в перспективных мобильных сетях радиосвязи может насчитываться от нескольких сотен до нескольких тысяч радиостанций, в зависимости от уровня (поселок-город-регион) всех видов, алгоритмы только с реактивной или проактивной маршрутизацией будут неэффективными из-за быстрого роста доли служебного трафика [2]. В качестве протокола маршрутизации в рассматриваемых многоуровневых мобильных сетях радиосвязи целесообразно применить гибридный протокол маршрутизации HWMP, основная идея которого — разбиение сети на несколько подсетей, внутри каждой из которых работает проактивный протокол, в то время как взаимодействие между подсетями осуществляется реактивным способом. С учетом выбора гибридного протокола маршрутизации HWMP при использовании ступенчатого способа адресования предлагается:

– в распределенных сетях радиодоступа непосредственно между абонентами использовать проактивный протокол маршрутизации OLSR;

– между подсетями и сетями использовать реактивный протокол маршрутизации AODV.

Протокол AODV динамически создает таблицы маршрутов в соответствии с динамикой изменения топологии, при этом каждый узел поддерживает возрастающий счетчик пакетов, что позволяет удалять неиспользованные или прекратившие существование маршруты [6]. Алгоритм работы реактивного протокола динамической маршрутизации AODV представлен на рисунке 1.

Рис. 1. Алгоритм работы реактивного протокола AODV

Запрос создания маршрута инициируется, когда узел хочет соединиться с узлом-получателем, но не имеет маршрута к этому узлу, для чего он посылает пакет «запрос на установку маршрута» — RREQ (Path Request) соседним узлам, которые пересылают этот пакет дальше, одновременно записывая узел, от которого был принят запрос. Поля сообщения RREQ, передаваемого от исходного узла, представлены в таблице 1.

Таблица 1

Поля сообщения RREQ

Тип

(8 бит)

Флаги

Резерв

(11 бит)

Количество шагов

(8 бит)

Идентификационный номер сообщения RREQ (RREQ ID)

IP-адрес узла-получателя (Destination IP Address)

Порядковый номер узла-получателя (Destination Sequence Number)

IP-адрес узла-инициатора (Originator IP Address)

Порядковый номер узла-инициатора (Originator Sequence Number)

В поле «Флаги» могут быть внесены следующие обозначения:

«J» — если RREQ передается широковещательно; «R» — при восстановлении маршрута; «G» — при необходимости установки маршрута до узла-получателя и обратно; «D» — при необходимости доставки сообщения RREQ узлу-получателю; «U» — при неизвестном порядковом номере узла-получателя.

Если узел, получивший запрос RREQ, уже знает необходимый маршрут к узлу-получателю, при конкретном значении флага «D» в принятом сообщении RREQ, то он посылает сообщение RREP (Path Reply) по временному маршруту к узлу-отправителю или направляет сообщение RREQ к узлу-получателю, который, в свою очередь, отправляет RREP обратно узлу-отправителю. При этом узел-отправитель пользуется маршрутом с наименьшим количеством промежуточных (транзитных) узлов. Записи, которые не были использованы в таблицах маршрутизации, стираются через временной интервал ART (Active route time-out), отвечающий за своевременное удаление несуществующих при высокой мобильности узлов маршрутов.

Более подробно рассмотрим пример маршрутизации по реактивному протоколу AODV на фрагменте сети, состоящей из 7 радиостанций (узлов).

Предположим, что узлу 1 требуется послать информацию узлу 7, однако, только узел 6 знает маршрут к узлу 7 (рис. 2). Необходимо отметить, что при этом в сети нет больше никакой маршрутной информации относительно узла 7.

В начале, узел 1 шлет каждому из своих соседних узлов 2 и 4 пакет RREQ следующего содержания: IP-адрес узла-инициатора = 1; IP-адрес узла-получателя = 7; идентификационный номер сообщения RREQ = 1; порядковый номер узла-инициатора = 1; порядковый номер узла-получателя = 7. Узлы 2 и 4 подтверждают, что это новый пакет RREQ и переправляют его дальше соседним узлам (рис. 3), при этом обновляя порядковый номер и добавляя количество шагов в пакет RREQ.

Пакет RREQ достигает узла 6, который знает маршрут к узлу 7. Узлу 6 необходимо убедиться в том, что порядковый номер узла-получателя в пакете RREQ меньше или равен порядковому номеру узла 7. Узлы 3 и 5 также переправляют пакет RREQ, при этом получатели признают данный пакет как дублирующийся.

Рис. 2. Рассылка узлом 1 RREQ пакета соседним узлам

Рис. 3. Перенаправление узлами 2 и 4 RREQ пакета

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

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

– если порядковый номер узла-получателя меньше предыдущего;

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

Таблица 2

Поля сообщения RREP

Тип

(8 бит)

Флаг

Резерв

(11 бит)

Количество шагов

(8 бит)

IP-адресузла-получателя (Destination IP Address)

Порядковый номер узла-получателя (Destination Sequence Number)

IP-адресузла-инициатора (Originator IP Address)

Время жизни (время ожидания возвращения по маршруту)

Узел 6 знает путь к узлу 7 и шлет RREP пакет узлу 4 (рис. 4) следующего содержания: IP-адрес узла-инициатора = 1; IP-адрес узла-получателя = 7; порядковый номер узла-получателя = 7; количество шагов = 1.

Узел 4, убедившись, что это ответ о новом маршруте (в данном случае) или имеющий меньшее число переходов, передает RREP пакет узлу 1, увеличивая количество шагов в пакете RREP. Таким образом, узел 1 может использовать маршрут из 3-х шагов к узлу 7 (рис. 5) для передачи пакетов данных, но первый пакет данных, для которого потребовался поиск пути, задерживается, пока не будет получен пакет RREP.

Рис. 4. Действие узла 6 при наличии пути к узлу 7

Рис. 5. Построенный маршрут от узла 1 к узлу 7

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

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

Литература:

  1. Ефремов А. Ю., Легович Ю. С. К вопросу выбора беспроводных технологий в задачах сетецентрического управления системами с маневрирующими объектами // Труды 3-й Всероссийской конференции с международным участием «Технические и программные средства систем управления, контроля и измерения». М.: ИПУ РАН, 2012. С. 154–157.
  2. Осипов И. Е. Mesh-сети: технологии, приложения, оборудование // Технологии и средства связи. 2006. № 4. — С. 39–45.
  3. Гольштейн Б. С., Соколов Н. А., Яновский Г. Г. Сети связи: Учебник для ВУЗов. СПб.: БХВ-Петербург, 2011. — 400 с.
  4. Лящук М. З., Ткачев Д. Ф. Проактивный алгоритм динамической маршрутизации в мобильных распределенных перспективных сетях, построенных на радиосредствах нового поколения // Фундаментальные и прикладные исследования в современном мире. 2016. № 13–1 — С. 18–24.
  5. Ляхов А. И., Некрасов П. О., Островский Д. М., Сафонов А. А., Хоров Е. М. Анализ совместного использования проактивного и реактивного методов распространения сетевой информации в многошаговых беспроводных сетях // Информационные процессы. 2012. Т. 12. № 3 — С. 198–212.
  6. RFC 3561: Ad hoc On-Demand Distance Vector (AODV) Routing. 2003. — 37 с.

Обсуждение

Социальные комментарии Cackle