Классификация и сравнительный анализ схем гибридной маршрутизации MANET-DTN



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

Ключевые слова: компьютерные ad hoc-сети, схемы маршрутизации, гибридные подходы MANET-DTN, сети, мобильный узел сети, мобильная распределенная компьютерная сеть.

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

1. Показатели производительности и модели мобильности

Схемы гибридной маршрутизации MANET–DTN оцениваются с использованием различных показателей производительности. Коэффициент доставки и средняя задержка являются общими показателями для всех схем гибридной маршрутизации MANET–DTN. Кроме того, некоторые гибридные схемы маршрутизации MANET–DTN оцениваются с помощью других метрик, таких как количество передач на сообщение, полезность полосы пропускания, среднее количество переходов, служебные данные, среднее количество «спасаемых» пакетов и уровень предсказуемости атрибута контекста (точность контекстная информация) для определения их производительности.

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

Сводка моделей мобильности и метрик производительности гибридных схем маршрутизации MANET–DTN, использованных в работах, обобщенных в разделе 3, представлена в таблице 1 ниже.

Таблица 1

Модели мобильности ипоказатели производительности гибридных схем маршрутизации MANET–DTN

Протоколы	Модели мобильности	Показатели эффективности
HYMAD	Две модели мобильности: 1. Модель мобильности с произвольной путевой точкой. 2. Трасса подключения Rollernet.	1. Коэффициент доставки. 2. Средняя задержка.
Стратегия маршрутизации в отключенных мобильных одноранговых сетях c групповой мобильностью	Перемещение группы опорных точек	1. Коэффициент доставки. 2. Средняя задержка.
Групповая маршрутизация на основе лидера в отключенных мобильных одноранговых сетях C групповой мобильностью	Перемещение группы опорных точек	1. Коэффициент доставки. 2. Средняя задержка.
Переход по островам	Узлы выполняют случайное блуждание из одного региона в другой регион (расположение узла, либо в регионе или на маршруте между регионами)	1. Коэффициент доставки. 2. Средняя задержка. 3. Количество передач в сообщение.
Использование групповых структур для эффективной маршрутизации в сетях, устойчивых к задержкам	Используются три модели мобильности: Случайная модель путевой точки;In–Place модель; Модель сообщества.	1. Коэффициент доставки. 2. Средняя задержка.
Переход по островам	Узлы выполняют случайное блуждание из одного региона в другой регион (расположение узла, либо в регионе или на маршруте между регионами)	1. Коэффициент доставки. 2. Средняя задержка. 3. Количество передач в сообщение.
Использование групповых структур для эффективной маршрутизации в сетях, устойчивых к задержкам	Используются три модели мобильности: 1. Случайная модель путевой точки; 2. In–Place модель 3. Модель сообщества.	1. Коэффициент доставки. 2. Средняя задержка.
Групповая маршрутизация в отключенных одноранговых сетях	Используются три модели мобильности: 1. Случайная модель путевой точки 2. In–Place модель 3. Модель сообщества.	1. Коэффициент доставки. 2. Средняя задержка.
EAR	Модель мобильности случайных путевых точек	1. Коэффициент доставки. 2. Утилита пропускной способности
CAR	Модель на основе сообщества	1. Коэффициент доставки. 2. Средняя задержка. 3. Уровень предсказуемости атрибута контекста
SCAR	Трассировка, генерируемая генератором трассировки Zebranet	1. Коэффициент доставки. 2. Средняя задержка.
Интеграция DTN и MANET	–	1. Коэффициент доставки.
STAR	Усеченная модель мобильности ходьбы Леви	1. Коэффициент доставки.
NOMAD	Тактическая модель мобильности, генерируемая инструментом Swarms	1. Коэффициент доставки.
Основанный на доверии алгоритм выбора узла–кандидата в гибридном MANET–DTN	Модель случайных точек	1. Среднее число «спасенных» пакетов 2. Средняя задержка 3. Среднее количество прыжков
Комбинирование маршрутизации по требованию и условной маршрутизации для прерывистого подсчета количества переходов в сети	1. Сетчатая случайная маршрутная точка 2. Запланированные маршруты 3. Случайная модель путевой точки	1. Коэффициент доставки. 2. Коэффициент сигнализации (накладные расходы)
Адаптивная маршрутизация	1. Случайная модель путевой точки. 2. «Отслеживание такси в Сан–Франциско» 3. «Синтетическая трасса Хельсинки»:	1. Коэффициент доставки. 2. Средняя задержка. 3. Среднее количество прыжков

2. Гибридные схемы маршрутизации MANET–DTN на основе групп

Схемы гибридной маршрутизации MANET–DTN [3, 221], которые обсуждаются в разделе 7, могут быть в целом разделены на гибридные схемы маршрутизации MANET–DTN, которые применяют явную группировку мобильных узлов, и гибридные схемы маршрутизации MANET–DTN, которые не применяют явную группировку мобильных узлов. Гибридные схемы маршрутизации MANET–DTN, которые применяют явную группировку мобильных узлов, адаптируют различные способы формирования групп и управления группами. В дополнение к сквозному соединению между мобильными узлами каждая явная схема гибридной маршрутизации MANET–DTN на основе групп, рассматривает один из следующих критериев для формирования группы:

1. Миссия (Задача): Мобильные узлы, имеющие одну цель или задачу, перемещаются вместе как участники одной группы.

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

3. Максимальный диаметр группы: размеры групп мобильных узлов ограничены фиксированным значением диаметра.

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

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

2.1 Формирование группы и управление

Подходы групповой гибридной маршрутизации MANET–DTN по-разному обрабатывают формирование групп и управление ими [4, 153].

В групповой маршрутизации на основе лидера в отключенных мобильных одноранговых сетях с групповой мобильностью и стратегии маршрутизации в отключенных мобильных одноранговых сетях c групповой мобильностью группа формируется из набора узлов, имеющих одинаковую миссию (задачу) и одинаковую мобильность группы. Лидер группы координирует группу и случайным образом выбирает следующий пункт назначения, а обычные члены перемещаются относительно лидера группы. Когда узлы разных групп сближаются, узел–член одной группы может покинуть свою текущую группу и присоединиться к другой группе, если узел генерирует вероятность, превышающую пороговое значение () и, если число членов текущей группы больше группового минимума (). Пороговое значение является очень высоким значением, и поэтому у узлов будет очень маленький шанс покинуть свои группы. Тогда как в HYMAD и EAR формирование групп основано на физической близости подвижных моделей. HYMAD ограничивает диаметр группы меньше фиксированного максимального диаметра. Любой проходящий узел может присоединиться к данной группе, если диаметр группы остается меньше максимального диаметра после включения узла новичка. Но EAR ограничивает количество узлов, которые рассматриваются как члены логического облака (группы) данного узла, и любой проходящий мимо узел может быть включен в логическое облако данного узла, заменив узел–член высоким скачком, если узел новичка имеет меньшее количество прыжков. Поскольку мобильные узлы перемещаются независимо друг от друга, формирование групп и управление ими очень динамично в HYMAD и EAR. В групповой маршрутизации в отключенных одноранговых сетях и групповых структурах эффективной маршрутизации в сетях, устойчивых к задержкам мобильные узлы должны иметь сквозную связь в течение времени, превышающего минимальное время ожидания группового слияния (это заранее установленное время, чтобы узлы не могли случайно объединиться. Переход по островам предполагает, что сеть имеет стационарные стабильные области, где плотность узлов относительно высока, а мобильные узлы в стабильной области напрямую связаны, и они считаются членами одной и той же группы.

2.2 Внутри- и межгрупповая маршрутизация

Для внутригрупповой маршрутизации большинство гибридных протоколов на основе групп использует протокол DSDV [1, 427]. HYMAD и Island Hopping используют простой алгоритм векторного расстояния для внутригрупповых сообщений.

Для межгрупповой маршрутизации эти разные гибридные схемы MANET–DTN на основе групп применяют разные механизмы маршрутизации. В стратегии маршрутизации в отключенных мобильных одноранговых сетях c групповой мобильностью и групповой маршрутизации на основе лидера в отключенных мобильных одноранговых сетях с групповой мобильностью эпидемическая маршрутизация используется для межгрупповой маршрутизации. В то время как в групповой маршрутизации в отключенных одноранговых сетях и групповых структурах эффективной маршрутизации в сетях, устойчивых к задержкам протокол маршрутизации PRoPHET применяется с неограниченным и ограниченным методом репликации, соответственно. Кроме того, HYMAD и EAR реализуют двоичный протокол распыления и ожидания и протокол распыления и ожидания соответственно для межгрупповой маршрутизации. Перескок островов пересылает межгрупповые сообщения с использованием мобильных узлов, которые перемещаются в другие группы.

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

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

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

Таблица 2 ниже показывает механизмы репликации и маршрутизации каждой гибридной схемы MANET–DTN.

Таблица 2

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

Протокол	Механизм репликации	Маршрутизация
Интеграция DTN и MANET	Единственный экземпляр	Расширенный AODV восстановления маршрута используется для поиска узлов DTN и номера узлов. Маршрутизации AODV используется, если приложение–источник выбирает Мане коммуникации. Если исходный узел поддерживает протокол пакета, он может выбрать передачу механизмом маршрутизации DTN.
STAR	Единственный экземпляр	Маршрутизация OLSR [2, 488] используется при наличии сквозного подключения. Данные сохраняются при необычных изменениях ссылок (нарушения) произошли вдоль пути.
NOMAD	Единственный экземпляр	Маршрутизация OLSR используется при наличии сквозного подключения. Если есть путь между двумя узлами, эти узлы будут действовать как Store–Carry Пересылка маршрутизаторов на все уязвимые узлы
Основанный на доверии алгоритм выбора узла–кандидата в гибридном MANET–DTN	Единственный экземпляр	Алгоритм маршрутизации AODV [3, 221] используется при наличии сквозного соединения. Но если соединение между исходным и конечным узлами не существует, данный узел с сообщением выбирает защищенный мобильный узел следующего прыжка на основе значения доверия.
Адаптивная маршрутизация	Множество копий	Исходный узел выбирает маршрутизацию MANET или DTN в зависимости от локальной информации о плотности сети, размере сообщения и скорости узла. AODV используется для связи MANET. Эпидемическая маршрутизация используется для связи DTN. Маршрутизация DTN может быть предпочтительнее маршрутизации MANET, если расчетное время жизни сообщения больше времени жизни пути или если плотность сети разрежена.
CAR	Единственный экземпляр Наилучший носитель определяется методом прогнозирования и многокритериальным решением атрибутов	Назначение–последовательная векторная маршрутизация расстояния, используется для связи MANET. Маршрутизация с поддержкой мобильности используется, когда нет сквозного соединения с узлом назначения. Узел лучшей несущей переносит сообщение из одной группы в другую.
Объединение маршрутизации по требованию и оппортунистической маршрутизации для периодически подключаемых сетей.	Две копии; используются исходное сообщение и одна резервная копия.	AODV используется для связи Мане. При наличии сквозного соединения с узлом назначения исходный узел выбирает два прокси–узла (на основе значений контактов), которые считаются ближайшими к назначению, и передает каждую копию каждому прокси–узлу. И каждый прокси пересылает сообщение другой узел с более высоким значением контакта, когда они подключаются к другому разделу.

4. Выводы

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

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

Гибридные схемы маршрутизации MANET–DTN могут быть в общих чертах разделены на гибридные схемы маршрутизации MANET–DTN, которые применяют явное группирование мобильных узлов, и гибридные схемы маршрутизации MANET–DTN, которые не применяют явную группировку мобильных узлов.

Гибридные схемы маршрутизации MANET–DTN, которые применяют явную группировку мобильных узлов, адаптируют различные способы формирования групп и управления группами. В некоторых протоколах мобильные узлы группируются в соответствии с их назначением определенным образом, аналогично группам солдат или спасательных бригад в чрезвычайных ситуациях. Некоторые другие группируют сквозные соединенные мобильные узлы на основе их физической близости. Однако группировка, основанная на физической близости мобильных узлов, является нестабильной и очень динамичной из-за независимого перемещения мобильных узлов. Чтобы уменьшить нестабильность группы, некоторые схемы рассматривают возможность подключения в течение достаточного времени в качестве критерия для группы формирование и объединение групп.

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

Различные гибридные схемы маршрутизации MANET–DTN также реализуют разные стратегии репликации. Некоторые протоколы фокусируются на улучшении скорости доставки за счет реализации механизмов множественного копирования, а другие нацелены на снижение накладных расходов за счет использования механизмов единого копирования.

Литература:

1. Haas, Z. J., Member, S., & Pearlman, M. R. (2001). Zone Routing Protocol. Journal of Research in Engineering & Applied Sciences, vol. 9, pp. 427–438
2. Holliday, P. (2009). NOMAD A Mobile Ad Hoc and Disruption Tolerant Routing Protocol for Tactical Military Networks. Proceedings of the 29th IEEE International Conference on Distributed Computing Systems Workshops-ICDCS Workshops '09, pp. 488–492.
3. Ott, J., Kutscher, D., & Dwertmann, C. (2006). Integrating DTN and MANET routing. Proceedings of the 2006 SIGCOMM Workshop on Challenged Networks — CHANTS ’06, pp. 221- 228.
4. D. Johnson, D. M. (1996). Dynamic source routing in ad hoc wireless networks. The Kluwer International Series in Engineering and Computer Science -Mobile Computing, vol. 353, pp. 153–181.