Метод локального восстановления маршрута в эпизодических сетях
Аннотация
В данной статье приводится исследование предлагаемого метода для восстановления маршрута в беспроводных эпизодических сетях. Приводится анализ предложенного методы восстановления маршрута с использованием соседних узлов. Кроме того, в статье приводится описание разработанного метод маршрутизации, использующий служебную информацию, содержащуюся в информационном пакете, и алгоритм адаптации. В статье также приводится сравнение производительности некоторых существующих методов маршрутизации и разработанного метода. Представленные модели и результаты моделирования позволяют провести оценку параметров, влияющих на связанность в ad hoc сети. На основе моделирования определяется время взаимодействия узлов при прямой передаче и ретрансляции, а также определяются требования к модернизации алгоритмов маршрутизации в ad hoc сети с точки зрения поддержания связи. Основными направлениями развития, которые определяют производительность беспроводных сетей будущих поколений, являются методы маршрутизации и алгоритмы адаптации к внешним условиям.
Ключевые слова: маршрутизация, беспроводная, эпизодическая, сеть, маршрут, узел, мобильность, адаптация.
- Введение
Мобильные беспроводные эпизодические сети являются одним из перспективных направлений развития беспроводных телекоммуникационных систем. Основной задачей при реализации таких сетей является задача связности в сети. При использовании восприимчивых к задержкам приложений (потоковый звук, видео и т.п.) задача быстрого восстановления маршрутов, в эпизодической сети, является критически важной с точки зрения связности. При восстановлении маршрутов нужно учитывать дополнительные критерии. Например, некоторые маршруты восстановления могут не подходить из-за большой загруженности. Термин «связность» тесно взаимосвязан с понятием «выживаемости, живучести» эпизодической сети как способности системы адаптироваться к новым, изменившимся и, как правило, непредвиденным (аварийным) ситуациям, т.е. ее способности выполнять заданные функции (передачи, сбора информации, управление) в течение определенного времени, несмотря на нежелательные обстоятельства. Обеспечения связности является важной составляющий алгоритма маршрутизации в эпизодической сети.
В статье приводиться особенности алгоритма САМ (самоадаптирующийся алгоритм маршрутизации). Представлено моделирование метода лекального восстановления маршрута как составной части алгоритм САМ .
- Особенности САМ
1 не используется адреса промежуточных узлов для построения маршрута,
2 не используется 3 уровень OSI для маршрутизации, ко всем пакетам дописывается служебная информация маршрутизации
3 отсутствует служебные пакеты маршрутизации
4 для обеспечения связности применяется метод локального восстановления маршрута
5 балансировка нагрузки на основе самостоятельно принятия узлом решения о участие в маршруте
6 подтверждение доставки пакета осуществляется косвенными способами
Алгоритм предназначен для поиска оптимального маршрута между вызывающим и вызываемым абонентом в составе эпизодической сети. Особенность и уникальность алгоритма состоит в его распределенности между всеми участниками маршрута. Алгоритм не строит таблицы маршрутизации на узле, абоненты не имеют информации о местонахождении каждого участника сети. Но в тоже время алгоритм позволяет найти оптимальный маршрут между участниками соединения. Достигается это следующими свойствами алгоритма.
В момент, когда необходимо установить связь, происходит рассылка пакетов во всех направлениях: от каждой точки всем соседним точкам. Для избавления от дубликатов пакетов и пакетов, которые удалились от маршрута, используются следующие поля пакета:
• Уникальный идентификатор соединения - позволяет избавляться от дубликатов пакетов
• Метрика прямого маршрута - данная метрика нужна вызываемому узлу для выбора маршрута
• Метрика обратного маршрута - данная метрика нужна промежуточным узлам для принятия решения о ретрансляции пакета
• Время жизни пакета - нужно для отбрасывания «заблудившихся» пакетов
• Номер пакета - необходим для определения дублированных пакетов и определения обратных пакетов от вызываемого к вызывающему.
При переходе через каждую точку маршрута, узел изменяет поля пакета. Поля пакет имеют переменную величину. Таким образом, при попадании пакета в точку назначения сравниваются значения полей пакета «Метрика прямого маршрута», пришедших разными маршрутами, и путь, имеющий наименьшее значение поля, становится оптимальным маршрутом. Промежуточные узлы сами определяют свою принадлежность к выбранному маршруту на основе поля пакета «Метрика обратного маршрута».
Для уменьшения времени передачи пользовательских данных, пользовательские данные отправляются ещё до того, как был выбран оптимальный маршрут, то есть поиск маршрута и передача данных происходит одновременно.
Применение этих метода позволяет сети самоорганизоваться и самоконфигурироваться, что означает отсутствие необходимости в существовании сетевой инфраструктуры и ее администрировании.
- Метод локального восстановления маршрута
Задача построения «выживаемой» сети может решаться как традиционными для эпизодической сети средствами, например, разработка более эффективных и робастных алгоритмов маршрутизации сбережения энергии, так и нетрадиционными способами – использование техники «локального восстановления маршрута» для восстановления связей/связности в сети.
В статье предложены простые модели позволяющие оценить время взаимодействия узлов при прямой передаче и ретрансляции. С помощью предложенного подхода можно прогнозировать сходимость в эпизодической сети в типовых условиях. На основе представленных результатов видно, что при увеличении скорости передвижения узлов, время связности между узлами сокращается.
Для обеспечения связности рассмотрим область сети состоящей из нескольких узлов (рис.1).
Рисунок 1-Вырианты эпизодической сети
Передача данных ведется от А к В через Б. В зоне радиовидимости, транзитных узлов, обычно находится некоторое количество узлов. В связи с этим и учитывая то, что радиоэфир является открытой средой передачи данных узлы, находящиеся в зоне радиовидимости (рис.1 Узел С) могут принимать пакеты, циркулирующие по радиоэфиру. На основе этого факта можно предположить, что соседние узлы косвенно получают информацию о маршруте. На основе перехваченной информации узел С может восстановить маршрут в случае если узел Б не выйдет из состава маршрута.
Для исследования и определения области, в которой можно восстановить маршрут на основе «подслушанной» информации, построена модель (рис. 2). Модель позволяет определить площадь, где возможен сбор информации о маршруте и его восстановления. Область восстановления также является областью, где должен располагаться ретранслятор.
На основе простых геометрических расчетов определяется площадь области.
Рисунок 2- Область возможной ретрансляции
На рисунке 2 точками O1 и O2 обозначены положения узлов 1 и 2. R – радиус зоны радиовидимости каждого из узлов. Заштрихованной областью обозначена зона, в которой может находиться промежуточный узел и ретранслировать данные между узлами О1 и О2. Площадь данной области можно найти по следующей формуле:
Площадь фигуры:
Где 
– площадь сектора с углом 
, 
– площадь сектора с углом 
, 
- площадь треугольника со сторонами 
, 
и 
.
Углы 
и 
также зависят от 
и находятся соответственно по формулам:
, 
.
Таким образом, конечное выражение для площади зоны ретрансляции имеет вид:
Кроме того, расстояние между узлами ограничено неравенством:
Где 
- наименьший из двух радиусов 
и 
.
При 
, площадь стремится к нулю.
При X<= R существует прямая связность между узлами 1 и 2, и ретранслирующий узел не требуется.
При X>R для связности узлов 1 и 2 требуется ретранслятор,
При X>2R связность узлов через 1 ретранслятор нарушается.
Исходя из вышесказанного, можно считать, что площадь области возможной ретрансляции и замещения также ограничена неравенством:
.
Область восстановления маршрута позволяет восстанавливать маршрут без использования рассылки дополнительных пакетов для постановления маршрута. Рассмотренный метод был реализован в разработанном алгоритме маршрутизации как составная часть.
- Моделирование метода локального восстановления маршрута
Для проведения моделирования мобильной беспроводной эпизодической сети была выбрана среда моделирования OPNET Modeler 14.0.[статья Смирнов] Беспроводная сеть состояла из 10 узлов. Площадь области моделирования составляла 1,6 км2. Сценарий моделирования включал в себя передачу голосовых сообщений между двумя узлами через мобильные ретрансляторы. Ретранслятора двигаются со скоростью 10-15 м/с, что приводит к разрушению маршрута.
Были получены диаграммы общей пропускной способности, задержки, нагрузки на сеть (рисунки 2, 3, 4 соответственно) и графики количества переданных и полученных пакетов (рисунки 5 и 6 соответственно).
Рисунок 3. Средняя задержка при передаче голосовых данных
Рисунок 4. Средняя нагрузка на сеть
Рисунок 5. Количество переданных пакетов при передаче голосовых данных
Рисунок 6. Количество полученных пакетов при передаче голосовых данных
- Выводы
Предложенное решение позволяет минимизировать потери производительности беспроводной мобильной эпизодической сети при разрушении маршрутов передачи данных. Небольшое увеличение нагрузки на сеть по сравнению с другими протестированными протоколами не приводит к серьезным задержкам при передаче голосовых данных, однако влияет на количество потерь пакетов, что видно при анализе рисунков 5 и 6.
Исследование, проведенное в этой работе, позволяет определить дополнительные требования к протоколам маршрутизации и эффективнее использовать беспроводные мобильные эпизодические сети для передачи голосовых данных.
Литература
[1] Charles E Perkins Sun Microsystems Laboratories Advanced Development Group Menlo Park CA cperkin@eng.sun.com, Elizabeth M Royer Dept of Electrical and Computer Engineering University of California, Santa Barbara, Santa Barbara CA eroyer@alpha.ece.ucsb.edu, Ad-hoc OnDemand Distance Vector Routing
[2] David B. Johnson David A. Maltz Josh Broch, DSR: The Dynamic Source Routing Protocol for Multi-Hop Wireless Ad Hoc Networks, Computer Science Department Carnegie Mellon University Pittsburgh, PA 15213-3891 http://www.monarch.cs.cmu.edu/
[3] P. Jacquet, Ed. Project Hipercom, INRIA October 2003 http://www.ietf.org/rfc/rfc3626.txt
[4] Баринов В.В., Бахтин А.А., Прокофьев А.А., Меркушев В.А., К расчету времени связи мобильных абонентов в сети ad hoc. Естественные и технические науки, №2, 2009.
[5] Бахтин А. А., Попов Л. А., Смирнов А. В., Эффективность реализации межуровневого взаимодействия для протокола быстрой маршрутизации в беспроводных ad-hoc сетях. Вестник Московского авиационного института № 5., т. 16., 2009 г.,