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

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

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

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

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

• •    прямое соединение;

• •    маршрутизация по умолчанию;

• •    статическая маршрутизация;

• •    динамическая маршрутизация.

Ланин Михаил Андреевич аспирант, Институт информационных систем и компьютерных технологий, Российский новый университет, Москва. Сфера научных интересов: информационные технологии. Автор пяти опубликованных научных работ. SPIN-код: 2510-0037, AuthorID: 1146755.

Беспроводная децентрализованная самоорганизующаяся сеть (далее – БДСС), или беспроводная ad-hoc-сеть, в профессиональной терминологии также известная как MANET (Mobile Ad Hoc Network) – это самонастраивающаяся сеть мобильных устройств, которые взаимодействуют друг с другом без необходимости централизованной инфраструктуре. Подобные сети применяются, в частности, при проведении спасательных работ в районах стихийных бедствий с разрушенной централизованной инфраструктурой.

В этих условиях каждый смартфон, планшет или иное цифровое устройство выступает одновременно и передатчиком, и маршрутизатором, передавая сообщения, в том числе на устройства, находящиеся вне зоны прямой связи, посредством их передачи через несколько узлов, каждым из которых является одно из подобных устройств. Организация подобной сети позволяет обмениваться информацией в режиме реального времени. При развертывании MANET, как правило, используются алгоритмы реактивной маршрутизации DSR (Dynamic Source Routing) или AODV (Ad Hoc On-Demand Distance Vector). Кроме того, в сетях типа MANET нередко применяются алгоритмы проактивной маршрутизации и гибридные алгоритмы, такие как ZRP (Zone Routing Protocol).

Сравнительный анализ алгоритмов реактивной маршрутизации в сети MANET

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

Сравним два широко применяемых алгоритма (см. Таблицу 1).

Таблица 1

Сравнительная характеристика алгоритмов AODV и DSR

Наименование	AODV (Ad Hoc On-Demant Distance Vector)	DSR (Dynamic Source Routing)
Подход к маршрутизации	Реактивный (по требованию)	Реактивный (по требованию)
Таблица маршрутизации	Поддерживает таблицу маршрутизации, содержащую порядковые номера пунктов назначения и информацию о следующем переходе	Поддерживает кэш маршрутизации с полными маршрутами
Обнаружение маршрута	Когда требуется маршрут, AODV инициирует процесс обнаружения маршрута, передавая пакеты запроса маршрута (RREQ)	Исходные узлы включают полные маршруты в заголовки пакетов. Промежуточные узлы используют кэш маршрутов для пересылки пакетов

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

Окончание таблицы 1

Наименование	AODV (Ad Hoc On-Demant Distance Vector)	DSR (Dynamic Source Routing)
Обслуживание маршрута	Периодически отправляет пакеты RREP для поддержания активных маршрутов	Маршруты поддерживаются, пока они активно используются. Периодические сообщения об обновлении маршрута не отправляются
Предотвращение зацикливания	Используются порядковые номера для предотвращения зацикливания маршрутов	Полагается на использование исходных маршрутов для предотвращения зацикливания

*Источник: здесь и далее таблицы составлены автором.

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

• •    ресурсоемкость – затраты ресурсов на обнаружение и обслуживание маршрутов;

• •    сквозная задержка – время, затрачиваемое пакетами данных на прохождение по сети от источника к месту назначения;

• •    масштабируемость – способность адаптироваться к различным размерам и плотности сети;

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

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

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

Рассмотрим общий принцип работы алгоритма AODV.

Обнаружение маршрута (запрос маршрута – RREQ ). Когда с исходного узла ( S ) необходимо отправить данные узлу назначения ( D ) и не имеется маршрута, инициируется процесс обнаружения маршрута путем широковещательной передачи пакета RREQ .

RREQ включает в себя адреса источника ( S ), адрес назначения ( D ), порядковый номер источника ( SeqS ), порядковый номер назначения ( SeqD ), широковещательный идентификатор ( BID ), количество переходов ( H ) и идентификатор запроса ( RID ).

Таким образом, данный пакет может быть представлен в виде

RREQ = S , SeqS , D , SeqD , BID , H , RID .

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

Количество переходов обновляется по формуле

H new = H old + 1.

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

Обслуживание маршрута (ответ на маршрут – RREP ). Когда пакет RREQ достигает узла назначения или узла, у которого есть действительный маршрут к месту назначения, с последнего отправляется пакет Route Reply ( RREP ).

Пакет RREP включает адрес назначения ( D ), адрес источника ( S ), порядковый номер назначения ( SeqD ), порядковый номер источника ( SeqS ), количество переходов ( H ) и уникальный идентификатор и может быть представлен как выражение

RREP = ( D , S , SeqD , SeqS , H , Unique ID ).

С промежуточных узлов происходит отправка RREP обратно к источнику с использованием записанного маршрута в пакете RREP .

Узел-источник получает RREP и обновляет таблицу маршрутизации.

Поддержание маршрутов. AODV использует механизм периодического объявления маршрута путем периодической отправки RREP для поддержания активных маршрутов. Подобный пакет RREP может быть представлен выражением

RREPperiodic = (S, SeqS, N, Hsource), где N – следующий переход к узлу назначения.

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

Удаление маршрута. Маршруты в AODV сохраняются до тех пор, пока они активны. Если ссылка или маршрут становятся неактивными, они удаляются из таблиц маршрутизации.

Ключевое уравнение/формула в AODV. Минимальное расстояние перехода (далее – MHD) показывает минимальное количество переходов от источника до пункта назначения и рассчитывается следующим образом:

ÌHD = H + 1, где H – количество переходов от источника к узлу, который ответил с помощью RREP.

Общий принцип работы алгоритма AODV показан на Рисунке 1.

Рисунок 1. Общий принцип работы алгоритма AODV

Источник: [6].

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

Открытие маршрута. Когда возникает потребность отправить данные от источника ( S ) к узлу назначения ( D ) и отсутствует маршрут, инициируется процесс обнаружения маршрута. Узел-источник S создает пакет запроса маршрута ( RREQ ), содержащий его

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

адрес ( S ), адрес назначения ( D ), уникальный идентификатор запроса (Unique ID) и запись посещенных узлов (Visited Nodes). Источник ( S ) передает пакет RREQ соседним узлам. Каждый узел, получающий RREQ , добавляет свой собственный адрес к записи посещенных узлов и далее ретранслирует RREQ :

RRE Q received = ( S , D , U nique ID , V isited N odes → N 1, N 2, ...).

Как только RREQ достигает пункта назначения или узла с действительным маршрутом к месту назначения, он отвечает пакетом Route Reply ( RREP ).

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

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

Конкретной математической формулы, связанной с DSR , такой как MHD в AODV не существует: DSR полагается на исходную маршрутизацию, где полный маршрут хранится в заголовке пакета, что делает его автономным.

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

Общий принцип работы алгоритма DSR представлен на Рисунке 2.

Рисунок 2. Иллюстрированный пример работы алгоритма DSR Источник: [8].

В приведенном примере адресат S 7 получает запрос по двум путям. Он выбирает один путь на основе записей маршрута во входящем пакете и отправляет ответ, используя обратный путь к исходному узлу. При каждом переходе сохраняется наилучший маршрут с минимальным переходом. В этом примере показано состояние записи маршрута при каждом переходе для достижения пункта назначения от исходного узла. Здесь выбран маршрут S 1– S 2– S 4– S 5– S 7.

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

Выбор между AODV (Ad Hoc On-Demand Distance Vector) и DSR (Dynamic Source Routing) зависит от конкретных характеристик и требований сценария применения. Каждый протокол имеет свои сильные и слабые стороны, что делает один потенциально более подходящим, чем другой, в зависимости от контекста.

Общие условия, которые следует учитывать при выборе между AODV и DSR, представлены в Таблице 2.

Таблица 2

Основные характеристики алгоритмов реактивной маршрутизации

Алгоритм	Сильные стороны	Слабые стороны
AODV	Эффективность в динамических средах: AODV хорошо подходит для динамических сценариев с частыми изменениями топологии сети. Его механизмы обнаружения маршрутов и обслуживания по требованию эффективно адаптируются к изменениям Масштабируемость: проактивный подход AODV к обслуживанию маршрутов делает его подходящим для более крупных сетей. Периодические обновления помогают активно поддерживать маршруты. Адаптируемость к мобильности: реактивность AODV позволяет алгоритму адаптироваться к мобильности узлов в сети	Затраты ресурсов при управлении пакетами: AODV увеличивает потребление ресурсов на управление пакетами при обнаружении и обслуживании маршрута. Использование памяти: обслуживание таблиц маршрутизации может привести к увеличению использования памяти, особенно в крупных сетях. Потребление энергии: периодическое обслуживание маршрута в AODV приводит к некоторому потреблению энергии
DSR	Производительность в стабильных средах: DSR более эффективен в стабильных средах, где топология сети меняется нечасто. Эффективность маршрутизации источника: подход маршрутизации источника в DSR эффективен для коротких маршрутов и в сценариях, где маршруты остаются стабильными. Энергоэффективность: DSR, как правило, более энергоэффективен, поскольку не использует механизм регулярной актуализации маршрута путем отправки пакетов управления, как в AODV	Запись маршрута в заголовок каждого пакета: исходная маршрутизация в DSR приводит к увеличению заголовков пакетов, что может повлиять на скорость, особенно для более длинных маршрутов. Использование памяти: кэш маршрутов в DSR может стать большим в сценариях с частой сменой маршрута

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

Сценарии использования и выбор алгоритма исходя из условий развертывания MANET

Рассмотрим практическое применение алгоритмов в конкретных ситуациях и оценим их потенциальную эффективность.

Сценарий 1. Команда мобильных роботов в аварийно-спасательных работах.

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

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

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

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

Почему выбор DSR будет менее предпочтительным в данном сценарии?

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

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

В-третьих, при аварийном восстановлении на большой территории может работать значительное количество мобильных роботов. Зависимость DSR от кэшей маршрутов, которые могут становиться все более объемными с увеличением числа узлов, может масштабироваться не так эффективно, как обнаружение маршрутов AODV по требованию.

Управление кэшем маршрутов и необходимость указания полных маршрутов в заголовках пакетов могут привести к проблемам масштабируемости в более крупных сетях.

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

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

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

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

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

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

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

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

Заключение

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

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