Метод иерархической маршрутизации мобильной самоорганизующейся сети доступа тема диссертации и автореферата по ВАК РФ 05.12.13, кандидат наук Романов, Сергей Владимирович

• Романов, Сергей Владимирович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Романов, Сергей Владимирович

Оглавление

Введение

ГЛАВА 1. Анализ и протоколов гибридной и иерархической маршрутизации MANET

1.1 Методы гибридной и иерархической маршрутизации

1.2 Анализ затрат на хранение таблиц маршрутизации

1.3 Анализ затрат на коммутацию

Выводы по главе 1

ГЛАВА 2. Разработка метода иерархической маршрутизации самоорганизующейся сети связи

2.1 Постановка задачи

2.2 Показатели качества протоколов маршрутизации

2.3 Определение требований к методу маршрутизации

2.4 Разработка метода иерархической дистанционно-векторной геомаршрутизации (HDVG)

2.4.1 Архитектура протокола иерархической маршрутизации

2.4.2 Агент кластеризации

2.4.3 Агент внутрикластерной маршрутизации

2.4.4 Агент иерархической маршрутизации

2.4.5 Агент геоинформации

2.4.6 Обработка и ретрансляция служебных пакетов

2.4.7 Временное псевдослучайное разделение каналов

Выводы по главе 2

ГЛАВА 3. Моделирование и анализ метода иерархической маршрутизации HDVG

3.1 Выбор сетевого симулятора

3.2 Программная модель самоорганизующейся сети

3.2.1 Модель сетевого узла

3.2.2 Модели подвижности узлов

3.3 Программная реализация распределенной системы имитационного моделирования

3.4 Анализ эффективности метода иерархической маршрутизации

3.4.1 Анализ показателей эффективности метода иерархической маршрутизации при изменении масштаба сети и плотности узлов

3.4.2 Анализ показателей эффективности метода иерархической маршрутизации при изменении параметров мобильности сети

3.4.3 Анализ показателей эффективности метода иерархической маршрутизации при изменении размера кластера

Выводы по главе 3

ГЛАВА 4. Разработка архитектуры абонентского терминала

4.1 Приложения MANET

4.2 Архитектура сетевого узла MANET

Выводы по главе 4

Заключение

Список литературы

ОПРЕДЕЛЕНИЯ, ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ

ABR (Associativity-Based Routing) - маршрутизация на основе

ассоциативности Ad-hoc Беспроводная самоорганизующаяся сеть

ADV (Adaptive Distance Vector Routing) - адаптивная векторная маршрутизация

AMRIS (Ad Hoc Multicast Protocol utilizing Increasing id-numbers) - как и AMRoute представляет собой протокол многоадресной машрутизации AMRoute (Ad-hoc Multicast Routing protocol) - протокол проактивной маршрутизации, предназначенный для многоадресной передачи (multicast) в ad-hoc сетях AODV (On-Demand Distance Vector) - протокол реактивной маршрутизации предназначенный для использования мобильными узлами в одноранговой сети

BRP (Bordercast Resolution Protocol) - протокол разрешающий рассылку

периферийным узлам CBRP (Cluster-Based Routing Protocol) - протокол маршрутизации на основе кластеров

CGSR (Cluster Gateway Switch Routing Protocol) - кластерный протокол

маршрутизации с переключаемыми шлюзами DAG (Directed Acyclic Graph) - направленный ациклический граф DHAR (Dual-Hybrid Adaptive Routing) - гибридный адаптивный протокол маршрутизации

DSDV (Dynamic Destination-Sequenced Distance-Vector Routing Protocol) -векторный протокол с динамическим последовательным назначением DSR (Dynamic Source Routing) - протокол реактивной маршрутизации с

динамически изменяющимися путями FSR (FishEye State Routing) - протокол проактивной маршрутизации,

использует аналогию с особенностями зрительной картины у рыб GAF (Geographic adaptive fidelity "географически адаптивная точность")

-алгоритм маршрутизации, основанный на геоинформации GB (Gafni-Bertsekas) - алгоритм Гафнии-Бертсекаса

GSR (Global State Routing) - маршрутизация

GZRP (Genetic Zone Routing Protocol) - генетический зонный протокол маршрутизации

IARP (Intrazone Routing Protocol) - протокол внутризоновой маршрутизации

IERP (Interzone Routing Protocol) - компонент глобальной реактивной

маршрутизации в гибридном протоколе ZRP HSR (Hierarchical State Routing) - маршрутизация иерархических состояний

HWMP (Hybrid Wireless Mesh Protocol) - гибридный протокол для

беспроводных ячеистых сетей LANMAR (Landmark Ad Hoc Routing) - маршрутизация ad hoc сетей с

географической привязкой LMR (Link Life Based Routing) - маршрутизация на основе длительности связи

MANET (Mobile ad-hoc network) - мобильная ad-hoc сеть MPR (Multipoint Relay) - многоточечный ретранслятор MPRs "Избиратель" многоточечного ретранслятора (mulripoint relay selector — MPRs)

OLSR (Optimized Link State Routing) - протокол проактивной маршрутизации, является адаптацией классического link state протокола маршрутизации (протокола маршрутизации по состоянию канала)

Введение диссертации (часть автореферата) на тему «Метод иерархической маршрутизации мобильной самоорганизующейся сети доступа»

Введение

Активно развивающейся в настоящий момент областью беспроводных систем передачи данных и сетей связи являются MANET - мобильные самоорганизующиеся сети (Mobile Ad-hoc NETworks). MANET является сложной распределенной системой, включающей в себя мобильные узлы, имеющие возможность самостоятельно организовываться в сеть с динамически меняющейся топологией. Динамическая структура MANET позволяет абонентам пользоваться сетевыми сервисами в областях, где фактически отсутствует традиционная фиксированная структура телекоммуникационных, в том числе беспроводных сетей. Подобные сети могут применяться во время военных действий, в структурах МЧС, в транспортных системах и различных силовых структурах [1], [2].

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

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

Анализ публикаций зарубежных (X. Hong, G.V. Kumar, Т. Clausen, M. Gerla,

A. Iwata, M.S. Corson, S. Taneja, Z.J. Haas, P.S. Kumar, Винокуров В.M.) и отечественных (А.И. Ляхов, A.A. Сафонов, В.Г. Маркин, В.Г. Орлов, А.Н. Фадеев, А.Л. Афанасьев, B.C. Еремин, М.А. Гоголева и др.) авторов, посвященных протоколам маршрутизации MANET позволяет подразделить протоколы маршрутизации MANET на три основные группы:

- протоколы с проактивной маршрутизацией,

- протоколы с реактивной маршрутизацией,

- гибридные и иерархические протоколы.

Проактивные протоколы (OLSR [3], TBRPF [4], FLAME [5], AMRoute [6], AMRIS [7], FSR [8]) предполагают построение таблиц маршрутизации на сетевых узлах предварительно, до получения запроса на передачу данных. Кроме того, сетевые узлы осуществляют периодический обмен служебными сообщениями для получения и обновления информации о структуре сети.

Основная идея, заложенная в реактивных протоколах (AODV [9], DSR [10]), или - протоколах, работающих по запросу, состоит в сокращении служебного трафика за счет рассылки пакетов с маршрутными запросами только при необходимости передачи данных через конкретный узел.

Недостатком обеих групп «плоских» протоколов маршрутизации является быстрый рост служебного трафика и расхода энергоресурсов каждого узла при увеличении количества и подвижности узлов сети.

Отдельно можно отметить протоколы использующие данные о местоположении и векторе движения узлов, что позволяет оптимизировать маршруты в соответствии с выбранными количественными метриками (GPSR Г111, DREAM [121, LAR [13], LAKER [14]). К их недостаткам можно отнести необходимость согласования системы доставки геоинформации с алгоритмом маршрутизации и необходимость обновления информации о местоположении узлов для поддержания актуальности и правильности маршрутизации.

Гибридные и иерархические протоколы (TORA [15], ZRP [16], ZHLS [17], OPHMR [18], LANMAR [19], CGSR [20], CBRP [21], HSR [22], DDR [23], THRP [24]) сочетают в себе подходы проактивных и реактивных протоколов, снижая объем служебного трафика, циркулирующего в MANET-сетях большого размера за счет организации сетевых узлов в иерархические структуры или кластеры. В протоколы данной группы также может быть встроен механизм геомаршрутизации, позволяя улучшить показатели качества сети. Недостатком протоколов данного класса является относительная сложность реализации.

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

Для достижения указанной цели поставлены и решены следующие задачи.

1. Обзор, анализ и классификация алгоритмов маршрутизации мобильных самоорганизующихся сетей связи (MANET).

2. Разработка критериев оценки алгоритмов маршрутизации мобильных ad-hoc сетей, анализ недостатков существующих алгоритмов маршрутизации.

3. Разработка метода иерархической маршрутизации и реализация прототипа протокола маршрутизации MANET, в том числе:

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

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

вычислительного кластерного комплекса. 5. Разработка архитектуры абонентского терминала MANET.

Методы исследования. Для решения поставленных в работе задач используются методы статистической теории связи, статистического моделирования, теории телетрафика, линейной алгебры и тригонометрии, интегрального счисления, системного анализа.

Научная новизна полученных результатов состоит в следующем:

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

алгоритм межкластерной маршрутизации, алгоритм внутрикластерной маршрутизации, алгоритм кластеризации узлов.

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

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

1. На основе разработанного метода иерархической маршрутизации реализована программная модель прототипа протокола HDVG, обеспечивающего, в среднем, лучшие показатели по коэффициенту и времени доставки пакетов по сравнению с протоколами OLSR, AODV, GPSR в следующем диапазоне изменения параметров мобильной самоорганизующейся сети: скорость движения узлов ve[0;32] (м/с), количество узлов сети пе[50;300], среднее расстояние между узлами Д„е[3;150] (м).

2. Реализованный протокол иерархической маршрутизации HDVG позволяет

развертывать мобильные самоорганизующиеся сети доступа большой емкости (до ~ 103 узлов). При этом нормированный коэффициент доставки пакетов слабо зависит от степени мобильности узлов и находится в пределах, от Кдн=80% при п=50,до Кдн=30% при п=300 и скорости движения узлов до v=32 (м/с) (~ 115 (км/ч)).

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

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

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

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

3. Использование информации о местоположении и векторах движения сетевых узлов в алгоритме внутрикластерной маршрутизации MANET позволяет оптимизировать открываемые маршруты.

4. Разработанный метод обработки и ретрансляции служебных широковещательных пакетов сокращает время распространения информации о локальных изменениях структуры MANET с кластеризацией

узлов.

Б. Разработанный метод локального разделения каналов, обеспечивает вероятность коллизий при передаче пакетов данных не более 2% при равномерном размещении сетевых узлов. 6. Программная модель MANET с кластеризацией сетевых узлов, позволяет оценить показатели качества разработанного метода иерархической маршрутизации в системе распределенного моделирования телекоммуникационных сетей на основе кластерного комплекса. Достоверность материалов диссертационной работы подтверждается использованием адекватной модели MANET, включающей в себя модели уровней OSI, обоснованием полученных научных и экспериментальных результатов, результатами внедрения разработок в процессе выполнения НИР. Личный вклад автора.

Выносимые на защиту положения предложены автором в процессе выполнения НИР, а также изложены в научных работах автора. Реализация программной модели MANET с кластеризацией узлов выполнялась коллективом исследователей на кафедре радиоэлектронных средств ФГБОУ ВПО «ВятГУ» при личном участии автора.

Внедрение результатов работы. Теоретические и практические результаты, полученные при выполнении диссертационной работы использованы в НИР «Разработка прототипа телекоммуникационного протокола полносвязной самоорганизующейся сети связи повышенной устойчивости» (шифр заявки «2011-1.4-514-064-002») в рамках федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2013 годы»; внедрены в ЗАО «МНИТИ» (г. Москва); ОАО «НИИ СВТ» (г.Киров); учебный процесс в Вятском государственном университете.

Апробация работы. Основные результаты работы докладывались и

обсуждались на следующих конференциях: всероссийской НТК «Общество, наука, инновации» (НТК-2012); международной НТК «Цифровая обработка сигналов и ее применение - 05РА-2013»; XIII международной НТК «Теория и практика современной науки», 2013 г.

Публикации. По результатам исследования опубликовано 14 работ; в том числе: 8 статей в изданиях из числа рекомендованных ВАК для опубликования результатов диссертационных исследований), 1 учебное пособие, 3 тезиса докладов. Получено свидетельство об официальной регистрации программы для ЭВМ.

Структура и объем работы.

Диссертационная работа состоит из введения, 4 глав, заключения и списка литературы. Работа изложена на 148 страницах машинописного текста, содержит 58 рисунков и 8 таблиц. Список литературы включает 63 наименования.

ГЛАВА 1. Анализ и протоколов гибридной и иерархической маршрутизации MANET

При увеличении размеров беспроводных сетей (более 105 узлов) «плоские» алгоритмы маршрутизации (OLSR, AODV, DSR и проч.) становятся малопригодными для использования из-за экспоненциального роста служебного трафика. Одним из путей решения этой проблемы является применение методов иерархической маршрутизации, обеспечивающих хорошую масштабируемость сетей.

1.1 Методы гибридной и иерархической маршрутизации

Иерархическая маршрутизация в MANET основана на идее организации узлов в группы и назначении узлам внутри группы различной функциональности. Иерархия позволяет уменьшить размер таблиц маршрутизации и размер пакетов с маршрутной и служебной информацией; сократить служебный трафик за счет локализации его в пределах заданной части сети. Кроме того, гибридные и иерархические протоколы маршрутизации в целом имеют больший потенциал масштабируемости, чем простые реактивные или проактивные «плоские» протоколы.

Наиболее популярной идеей, лежащей в основе иерархической маршрутизации, является объединение узлов в кластеры по тому или иному признаку. Каждый кластер содержит лидера или "вершину кластера", для связи с узлами других кластеров. Другой идея состоит в выделении локальной зоны видимости для каждого узла. При этом, способ маршрутизации меняется в зависимости от положения адресата внутри или вне зоны [1J. Рассмотрим кратко некоторые наиболее известные протоколы этой группы.

TORA (Temporary Ordered Routing Algorithm) - алгоритм маршрутизации с временным упорядочением. Данный алгоритм маршрутизации предложен Парком и Корсоном (V. Park и S. Corson) в 1997 году [25J и относится к группе

алгоритмов с реверсом связей в маршруте (link-reversal routing). Он основан на идеях GB [26] и LMR [27] алгоритмов. TORA использует пакеты "запроса" и "ответа" (Query and Reply packets), как и в LMR, но объединяет их с понятием "высоты" (height), как в алгоритме GB с частичным реверсом связей.

Для прокладки маршрута ТОРА использует направленный ациклический граф (DAG - directed acyclic graph).

Пример представления участка сети в виде направленного ациклического графа показан на рисунке 1.1, где Н(г) - «относительная высота» узла г; пункт назначения имеет наименьшую высоту H(DEST). В примере (рис.1.1) узел А имеет высоту большую чем узлы В Е, узел С расположен ближе к пункту назначения, но имеет высоту большую чем узел В, а узел D имеет наибольшую высоту.

H (C}>H(B}>H(E}>H (DEST)

I А --- В - С '

I.

1 Г V

D -Е '-DEST

H (D}>H (A}?+i (В)Ж (Е }>Н (D EST)

Рис. 1.1. Представление направленного ациклического графа (DAG), ориентированного к пункту назначения (DEST) с использованием относительных высот узлов.

Для поиска маршрута применяется механизм подобный тому, который используется в LMR [27].

По сравнению с LMR, TORA является более быстрым алгоритмом и пригоден для использования в мобильных сетях достаточно большой емкости и

с высокими скоростями перемещения узлов. Ограничением алгоритма является то, что для своей работы он требует наличия временной синхронизации всех узлов. Однако, это легко осуществимо при использовании GPS приемников. Так же как и LMR, TORA может прокладывать временно недоступные маршруты [28]. В [29] отмечается, что к преимуществам TORA следует отнести поддержку нескольких маршрутов между любой парой источник-пункт назначения и невмешательство источника при перепрокладке маршрута в случае разрыва связи или удалением узла из сети.

ZRP (ZRP - Zone Routing Protocol [16], [30]) также является представителем группы гибридных протоколов маршрутизации. В основе предложенного сотрудниками университета Корнелла [16] подхода к маршрутизации лежит разбиение всей сети на зоны и применение внутри зон проактивных протоколов IARP, а вне - реактивных IERP. Архитектура ZRP (рис. 1.2) включает три части IARP - внутризоновый протокол, IERP - межзоновый протокол и BRP - протокол для граничных узлов используемый с IERP, чтобы уменьшить служебный трафик. Особенностью протокола ZRP является то, что для его работы требуется использование других протоколов (проактивных или реактивных).

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

м-f- Обмен пакетами

' • •• •■ "'......{> Информационный обмен

Рис. 1.2. Архитектура ZRP.

Рис. 1.3. ZRP общая схема зоны узла S (радиус зоны г-2). (S - центральный узел, L - узел вне зоны, A-F - соседние узлы (neighbors), G-K -

периферийные узлы).

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

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

Расширение ZRP с использованием генетических алгоритмов предложено в [32]. Алгоритм, названный GZRP, использует генетические алгоритмы в IERP и BRP частях ZRP, чтобы предоставить ограниченный набор альтернативных маршрутов с целью балансировки нагрузки сети во время процесса открытия маршрута. Особенности применения ZRP в сетях с однонаправленной связью рассмотрены в [33].

Протокол ZHLS - гибридный протокол маршрутизации, подобный ZRP. Протокол использует проактивную маршрутизацию, когда узел находится внутри зоны и реактивную маршрутизацию, когда узел находится вне зоны текущего узла. Но, в отличие от ZRP, в ZHLS сеть разделена на неперекрывающиеся зоны. Также, в ZHLS отсутствуют "лидеры зон" или "вершины кластеров". Размер зоны зависит от от мобильности узла, сетевой плотности, мощности передачи и характеристик распространения сигнала на физическом уровне. Каждый узел имеет информацию только о связях внутри зоны и связях между зонами на пространстве сети. Узел знает свою позицию и идентификатор зоны, полученные на основе GPS. Он может определить ID зоны сопоставляя свою позицию с имеющейся картой местности [17], [34].

Топология сети в ZHLS разделена на два уровня: уровень узла и уровень зоны.

На "уровене узла" рассматриваются связи узлов между собой внутри зоны. Виртуальный канал между двумя зонами образуется, если как минимум один узел зоны имеет связь с узлом другой зоны (рис. 1.4).

На "уровне зоны" рассматривается информация о связях между зонами сети. Информация этого уровня распространяется по всем узлам сети.

9 5 6

4 1 2

8 4 3 7 »

Рис. 1.5. Связь между зонами сети.

Каждый узел выполняет широковещательную рассылку запроса связи с соседями. Узлы (в пределах радиодоступности), получившие запрос, генерируют ответ, содержащий идентификатор узла и идентификатор зоны. После приема всех ответов, узел формирует LSP (link state packet) - "пакет состояния связей". Каждая запись LSP содержит идентификатор узла и идентификаторы его соседей.

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

В процессе отправки ЬБР, текущий узел может получить ответ от узла соседней зоны. Такие узлы называются шлюзами. Поскольку ЬБР содержит как идентификатор узла, так и идентификатор зоны, узел, получивший ответ от шлюза, получает информацию и об идентификаторе соседней зоны. Таким образом, каждый узел после рассылки ЬЯР будет иметь информацию о том, с какими зонами контактирует зона узла. Узлы-шлюзы рассылают ЬБР всем узлам сети. Каждая зона повторяет эту процедуру. На конечном этапе, каждый узел будет иметь информацию о зонной топологии сети ("уровень зоны"). Таблица межзонной маршрутизации может быть построена с использованием алгоритма поиска кратчайшего пути.

Таблица 1.1 - ЬБР узлов зоны

5оигсе ЬБР

а Ь,сД4

Ь а,е

с а,3

с! а

е ЬХ2

f е,2

Примечание: узлы Ь, g принадлежат другим зонам и являются шлюзами.

Таблица 1.2 - Таблица "зонной топологии"

Destination Zone Next Zone Next Node

2 2 b

3 3 с

4 3 g

5 4 g

6 2 b

7 3 с

8 3 с

9 4 h

Обе таблицы маршрутизации (таблица "уровня узла" и таблица "уровня зоны") периодически обновляются. Шлюзы не рассылают LSP, если время создания LSP не превышает времени создания таблиц маршрутизации. LSP "уровня зоны" обновляются только при отказе или создании канала связи между соседними зонами, что сокращает объем служебного трафика сети.

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

Гибридный протокол OPHMR, на базе OL SR учитывающий адаптивность и многофункциональное поведение узлов рассмотрен в работе [18]. Отмечено, что предлагаемая концепция полиморфизма открывает новые пути повышения эффективности проектирования протоколов MANET сетей.

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

В каждой из групп один узел динамически назначается так называемой

реперной точкой, которая служит своеобразным "маяком" при пересылке пакетов между узлами различных групп. LANMAR использует IP-подобную адресацию, состоящую из группового ID (или ID субсети) и ID хоста: <GroupID, HostID>. LANMAR использует понятие ориентиров (land-mark), чтобы отследить такие логические группы. Каждая логическая группа имеет один избираемый узел, называемый ориентиром. Механизм дистанционно-векторной маршрутизации (DSDV) распространяет информацию об ориентирах по всей сети. Затем LANMAR работает в симбиозе со схемой маршрутизации локальной зоны видимости. Маршрутизация в локальной зоне реализована на основе проактивного протокола типа FSR с "маршрутом источника". В результате, каждый узел имеет полную информацию о маршрутах внутри данной локальной области и векторы маршрутов ко всем ориентирам сети. Когда узлу необходимо доставить информацию внутри локальной области, он использует маршрутную информацию протокола DSR, в противном случае используется таблица маршрутизации дистанционно-векторного протокола для прокладки пути к ориентиру, в локальной области которого находится узел-приемник.

Протокол CGSR является типичным протоколом иерархической маршрутизации, основанной на кластерах [20]. Кластеризация выполняется на основе алгоритма Least Clusterhead Change (LCC). Мобильные узлы, принадлежащие более чем одному кластеру, являются шлюзами для связи между кластерами. Маршрутная информация пакетов данных имеет вид "вершина кластера - шлюз - вершина кластера -...".

CGSR относится к дистанционно-векторным алгоритмам маршрутизации. Каждый мобильный узел поддерживает две таблицы: таблицу членов кластеров и таблицу маршрутизации дистанционно-векторного алгоритма. Таблица членов кластеров содержит данные о вершинах кластеров и периодически обновляется. Таблица маршрутизации дистанционно-векторного алгоритма

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

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

CBRP [21J является еще одним протоколом, использующим кластеризацию узлов сети. Для внутри- и межкластерной маршуртизации используется метод "маршрута источника". Наличие кластерной структуры позволяет при этом сократить общий объем служебного трафика сети.

В работе [35J показано, что методы кластеризации, основанные на идентификаторах (IBC - identifier-based clustering) имеет преимущество перед методами, основанными на связности узлов (СВС - connectivity-based clustering) в случае подвижности узлов. При использовании IBC-кластеризации узел выбирается вершиной кластера, если он имеет наименьший/наибольший ID среди своих соседей. Сравнивая эти два метода можно заметить, что в случае СВС-кластеризации, каждый раз, при изменении количества соседей узла и, соответственно, его связности, может быть выбрана другая вершина кластера. В то же время, в методе IBC-кластеризации новая вершина выбирается только при потере связи узлов кластера с вершиной кластера.

Протокол CBRP использует модификацию алгоритма IBC-кластеризации, изложенную в работе [35].

В процессе формирования и поддержки кластера, каждый узел использует "таблицу соседей", в которой содержится информация об Ш-номерах соседних узлов, их функциях (обычный узел кластера, или вершина) и статусе связи (одно- или двунаправленная связь). "Таблица соседей" обновляется с помощью рассылки т.н. НЕЬЬО-сообщений, содержащих статус узла, таблицу его соседей и его таблицу смежности. Узел может находится в трех состояниях.

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

"Вершина кластера". Если вершина кластера обнаруживает двунаправленную связь с другой вершиной кластера (в течении заданного интервала времени), она меняет свой статус на статус "члена кластера", вершина которого имеет меньший ГО. В противном случае, узел сохраняет свой статус, а другой узел (вершина кластера) меняет свой статус — рис. 1.6.

- "Член кластера". Если узел - член кластера теряет вершину своего кластера, он просматривает все двунаправленные связи со своими соседями. При этом, если текущий узел имеет наинизший ГО, он становится новой вершиной кластера среди своих соседей. Иначе, текущий узел становится "неразрешенным". Каждый узел принадлежит по меньшей мере одному кластеру.

Список литературы диссертационного исследования кандидат наук Романов, Сергей Владимирович, 2014 год

Список литературы

1. Hong, X. Scalable routing protocols for mobile ad hoc networks / X. Hong et al. // IEEE Network. - 2002. - Vol. 16, №4. - P. 11-21.

2. Винокуров B.M. Маршрутизация в беспроводных мобильных Ad Ьос-сетях / В.М. Винокуров и др. // Доклады ТУСУРа. - 2010. - №2 (22), часть 1. - С. 288-292.

3. Kumar G.V. Current Research Work on Routing Protocols for MANET: A Literature Survey / G.V. Kumar, Y.V. Reddyr, Dr. M. Nagendra // (IJCSE) International Journal on Computer Science and Engineering. - 2010. - Vol.2, №3. - P. 706-713.

4. Akyildiz, I. F. CRAHNs: Cognitive radio ad hoc networks /1. F. Akyildiz, W. - Y. Lee, K. R. Chowdhury //Ad Hoc Networks. - 2009. - Vol. 7. - P. 810-836.

5. Clausen, T. Optimized Link State Routing Protocol (OLSR). [Электронный ресурс] Clausen, Т. // URL: http://www.ietf.org/rfc/rfc3626.txt (дата обращения: 11.2011).

6. Ogier, R. Topology Dissemination Based on Reverse-Path Forwarding (TBRPF). [Электронный ресурс] // URL: http://www.ietf.org/rfc/rfc3684.txt (дата обращения: 11.2011).

7. Elfrink, Ir. FLAME. Forwarding Layer for Meshing. [Электронный ресурс] // URL: https://doc.novay.nl/dsweb/Get/Document-72637/Dn2.10%20FLAME %20-%20Forwarding%20Layer%20for%20Meshing.pdf (дата обращения: 11.2011).

8. Bommaiah, E. AMRoute: Adhoc Multicast Routing Protocol // Mobile Networks and Applications. - 2002. - Vol. 7. № 6. - P. 429-439.

9. Wu, C.W. AMRIS: a multicast protocol for ad hoc wireless networks / C.W. Wu, Y.C. Tay // MILCOM 1999. - IEEE Military Communications. Conference Proceedings. -1999.-Vol.1.-P.25-29.

10. Gerla, M. Fisheye State Routing Protocol (FSR) for Ad Hoc Networks. [Электронный ресурс] / M. Gerla, X. Hong, G. Pei // URL:

http://tools.ietf.org/html/draft-ietf-manet-fsr-03 (дата обращения: 07.2002).

11. Perkins, С. Ad hoc On-Demand Distance Vector (AODV) Routing. [Электронный ресурс] / С. Perkins, E. Belding-Royer, S. Das // URL: http://www.ietf.org/rfc/rfc3561.txt (дата обращения: 04.2003).

12. Johnson, D. The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks

for IPv4. [Электронный ресурс] / D. Johnson, Y. Hu, D. Maltz // URL: http://www.ietf.org/rfc/rfc4728.txt (дата обращения: 03.2007).

13. Karp, В GPSR: Greedy perimeter stateless routing for wireless networks / В. Karp, H. T. Kung // In Proceedings of the 6-th Annual International Conference on Mobile Computing and Networking (MobiCom '00). - ACM Press, New York. - 2000. - Vol.1. -P. 243-254.

14. Basagni, S. A distance routing effect algorithm for mobility (DREAM) / Basagni, S. Let al.] // In Proceedings of the ACM MOBICOM. - 1998. - Vol.1. - P. 76-84.

15. Ко, Y Location-Aided Routing (LAR) in mobile ad hoc networks / Y. Ко, N. Vaidya // Wireless Networks. - 2000. - Vol.6, №4. - P.307-321.

16. Li, J. LAKER: Location aided knowledge extraction routing for mobile ad hoc networks / J. Li, and P. Mohapatra // In Proceedings of the IEEE WCNC. - 2003. - Vol.1. - P. 1180-1184.

17. Park, V. Temporally-Ordered Routing Algorithm (TORA). [Электронный ресурс] / V. Park, S. Corson // URL: http://toois.ietf.org/id/ draft-ietf-manet-tora-spec-04.txt (дата обращения: 08.2001).

18. Samar, P. Independent Zone Routing: An Adaptive Hybrid Routing Framework for Ad Hoc Wireless Networks / P.Samar, M.R. Pearlman, Z.J. Haas // IEEE/ACM Transactions on Networking. - 2004. - Vol. 12, №4. - P. 595-608.

19. Takashi Hamma. An Efficient ZHLS Routing Protocol for Mobile Ad Hoc Networks. [Электронный ресурс] / Takashi Hamma,Takashi Katoh, Bhed Bahadur Bista, Toyoo Takata // URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1698309 (дата обращения: 12.2006).

20. Mnaouer, A. B. OPHMR: An Optimized Polymorphic Hybrid Multicast Routing Protocol for MANET /А. B. Mnaouer et al. // IEEE Transactions On Mobile Computing.

- 2007. - Vol. 5, №. 6. - P. 505-515.

21. Gerla, M. Landmark routing for large ad hoc wireless networks / M. Gerla, X. Hong, G.Pei // Global Telecommunications Conference, 2000. GLOBECOM '00. IEEE. - 2000.

- Vol. 3. - P. 1702-1706.

22. Royer, E. M. A Review of Current Routing Protocols for Ad Hoc Mobile Wireless

Networks / E. M. Royer, Chai-Keong Toh // IEEE Personal Communications. - 1999. -Vol.6, Is.2.-P. 46-55.

23. Jiang, M. Cluster Based Routing Protocol(CBRP). [Электронный ресурс] / M. Jiang, J. Li, Y.C. Tay Jinyang Li Jinyang Li Y.C. Tay // URL:

http://tools.ietf.org/html/draft-ietf-manet-cbrp-spec-0101.ll.2012 (дата обращения: 01.2012).

24. Iwata, A. Scalable routing strategies for ad hoc wireless networks / A. Iwata Let al.J // IEEE Journal on Selected Areas in Communications. - 1999. - Vol. 17 , Is. 8. - P. 1369 -1379.

25. Nikaein, N. DDR-Distributed Dynamic Routing Algorithm for Mobile Ad hoc Networks / N. Nikaein, H. Labiod, C. Bonnet // First Annual Workshop on Mobile and Ad Hoc Networking and Computing (MobiHOC). - 2000. - Vol.1. - P. 19 - 27.

26. Xie, Jing A Threshold-based Hybrid Routing Protocol for MANET / Jing Xie, L.G.Quesada,Yuming Jiang // Proceedings of 4th IEEE International Symposium on Wireless Communication Systems, 1SWCS 2007. - 2007. - Vol.1. - P. 622 - 626.

27. Park, V.D. A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks / V. D. Park, M. S. Corson // IEEE Conference on Computer Communications, INFOCOM'97.- 7-llApril 1997. - Kobe, Japan. -. - Vol. 3. - P. 1405-1413.

28. Gafni, E.M. Distributed Algorithms for Generating Loop-Free Routes in Networks with Frequently Changing Topology / E. M. Gafni, D. P. Bertsekas // IEEE Transactions on Communications. -1981. - Vol. 29, No. 1. - P. 11-18.

29. Corson, M. S. Distributed Routing Algorithm for Mobile Wireless Networks / M. S. Corson, A. Ephremides // Wireless Networks. - 1995. - Vol. 1, Is. 1. - P. 61-81.

30. Abolhasan, M. A review of routing protocols for mobile ad hoc networks / M. Abolhasan, T.Wysocki, E. Dutkiewicz //Ad Hoc Networks. - 2004. -. - P. 1-22.

31. Taneja, Sunil A Survey of Routing Protocols in Mobile Ad Hoc Networks / Sunil Taneja, Ashwani Kush // International Journal of Innovation, Management and Technology. -2010. - Vol. 1, № 3. - P. 279-283.

32. Haas, Z.J. The Zone Routing Protocol (ZRP) for Ad Hoc Networks. [Электронный ресурс] / Z.J. Haas, M.R. Pearlman, P.Samar // URL:

http://tools.ietf.org/id/draft-ietf-manet-zone-zrp-04.txt (дата обращения: 10.2011).

33. Haas, Z.J. The Intrazone Routing Protocol (IARP) for Ad Hoc Networks. [Электронный ресурс] / Z.J. Haas, M.R. Pearlman, P.Samar // URL: http://tools.ietf.org/id/draft-ietf-manet-zone-iarp-02.txt (дата обращения: 11.2011).

34. Kumar, P. S. Load Balancing in Genetic Zone Routing Protocol for MANETs / P. S. Kumar, S. Ramachandram // International Journal of Computer and Information Engineering. - 2009. - Vol.3, №4. - P. 261-266.

35. Joa-Ng, M. A Peer-to-Peer zone-based two-level link state routing for mobile Ad Hoc Networks / M. Joa-Ng, I.-T. Lu // IEEE Journal on Selected Areas in Communications, Special Issue on Ad-Hoc Networks. - 1999. - Aug. - P.1415-1425.

36. Gerla, M. Multicluster, mobile, multimedia radio network / M. Gerla and J. Tsai //ACM Baltzer Journal of Wireless Networks. - 1995. - Vol.l,. No. 3. - PP. 255-265.

37. Bakht, H. Survey of Routing Protocols for Mobile Ad-hoc Network // International Journal of Information and Communication Technology Research. - 2011. - Vol.l. - P. 258-270.

38. Kant, K. Unicast And Multicast Routing Protocols For MANETs: A Comparative Survey. [Электронный ресурс] / К. Kant, L.K. Awasthi // URL: http://csjournals.com/IJITKM/Speciall/16.%20UNICAST%20AND %20MULTICAST.pdf (дата обращения: 01.2010).

39. Corson, J.S. Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Consideration. [Электронный ресурс] // URL: http://www.ietf.org/rfc/rfc2501.txt (дата обращения: 05.2012).

40. H. Zimmerman. OSI Reference Model - The ISO Model of Architecture for Open Systems Interconnection // IEEE Transactions on Communications. - 1980. - Vol. Com-28, No. 4. - pp. 425-432.

41. Филимонов, А. Построение мультисервисных сетей Ethernet. - Издательство: БХВ-Петербург. - 2007. - 592 С.

42. Прозоров Д.Е. Протоколы геомаршрутизации самоорганизующихся мобильных сетей / Прозоров Д.Е., Метелев А.П., Чистяков А.В., Романов С.В. // T-Comm: Телекоммуникации и транспорт. - 2012. - №5. - С. 16-19.

43. Hui Xu. A unified analysis of routing protocols in MANETs / Hui Xu, Xianren Wu, Hamid R. Sadjadpour, J.J. Garcia-Luna-Aceves // IEEE Transactions on Communications. - 2010. - Vol. 58, Is. 3. - P. 911-922.

44. Романов С.В. Анализ иерархического протокола маршрутизации MANET-сетей / Романов С.В. Прозоров Д.Е., Трубин И.С. // Перспективы науки. - 2012. - №4. - С. 86 - 89.

45. S.-Y. Ni The broadcast storm problem in a mobile ad hoc network / S.-Y. Ni, Y.-C. Tseng, Y.-S. Chen, and J.-P. Sheu // In ACM Mobicom. - 1999, NY. - №1. - P. 151-162.

46. Жолобов A.H. Принципы формирования кластеров в ad-hoc сетях / Жолобов А.Н., Лесников В.А., Романов С.В. // Научное обозрение. - 2012. - №4. - С. 264-273..

47. McDonald, А. В. A Mobility-Based Framework for Adaptive Dynamic Cluster-Based Hybrid Routing in Wireless Ad Hoc Networks: Dissertation PhD. [Электронный ресурс] // URL: http://citeseerx.ist.psu.edu/viewdoc/ download? doi=10.1.1.46.5898&rep=repl&type=pdf (дата обращения: 12.2000).

48. Basagni, S. Distributed clustering for ad hoc networks // Proceedings of International Symposium on Parallel Architectures, Algorithms and Networks. - 1999. - Vol.l. - P. 310 -315.

49. Chatterjee, M. WCA: a weighted clustering algorithm for mobile ad hoc networks / M. Chatterjee, S. K. Das, D. Turgut // Journal of Cluster Computing. - 2002. - № 5. - P. 193204.

50. Amis, A. D. Load-balancing clusters in wireless ad hoc networks / A. D. Amis, R. Prakash // Proc. 3rd IEEE ASSET'00. - 2000. - Vol.l. - P. 25 - 32.

51. Об определении видов технических средств и систем, подлежащих оснащению аппаратурой спутниковой навигации ГЛОНАСС или ГЛОНАСС/GPS. ГЭлектронный ресурс] // URL: http://minsvyaz.ru/ru/doc/?id_4=618 (дата обращения: 04.2012).

52. Boukerche, A. Algorithms and protocols for wireless, mobile ad hoc networks . - New Jersey: John Wiley & Sons, Inc. - 2009. - 495 p.

53. Stojmenovic, I. Position-Based Routing in Ad Hoc Networks // IEEE Communications Magazine. - 2002. - Vol. 40. - P. 128-134.

54. Mauve, M. A Survey on Position-based Routing in Mobile Ad hoc Networks / M. Mauve, J. Widmer, H. Hartenstein // IEEE Network Magazine. - 2001. - Vol. 15, №6. -P. 30-39.

55. A. Tanenbaum. Computer networks . - Prentice-Hall, NJ. - 1982. - 848 pp.

56. Жолобов A.H. Симуляторы беспроводных MANET-сетей / Прозоров Д.Е., Романов С.В // Инфокоммуникационные технологии. - 2012. - Т. 10, №3. - С. 28-33.

57. Балашов В. Обзор сетевого симулятора NS-3 / LVEE 2011. The 7th International conference of developers and users of free open source software. [Электронный ресурс] // URL: http://lvee.org/en/reports/LVEE_2010_31 (дата обращения: 10.2011).

58. Henderson, Т. R. NS-3 Project Goals. [Электронный ресурс] / Т. R. Henderson, S. Floyd, George F. Riley // URL:

http://www.nsnam.org/docs/meetings/wns2/wns2-ns3.pdf (дата обращения: 10.2011).

59. Ерыгина, T Проект NS-3. [Электронный ресурс] // URL: http://masters.donntu.edu.ua/2007/fvti/erygina/library/lib9.htm (дата обращения: 10.2011).

60. NS-3. [Электронный ресурс] // URL: http://www.nsnam.org (дата обращения: 10.2011).

61. Chlamtac I. Mobile ad hoc networking: imperatives and challenges /1 .Chlamtac, [et al.] //Ad Hoc Networks. - 2003. - Nal. - P. 13-64.

62. Herman, R. DEAPspase -Ttansient ad hoc networking of pervasive devices / R. Herman at all // Computer Networks. - 2001. - Vol.35. - P. 411-428.

63. Li, Frank Deploying and Experimenting Wireless Ad Hoc Networks in Mountainous Regions for Broadband Access / Frank Y. Li et all // In: Proceedings of BroadBand Europe 2007, Antwerp, Belgium. - 3-6 December 2007. - Vol. 1. - P. 1-6.