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

На правах рукописи

Романов Сергей Владимирович

МЕТОД ИЕРАРХИЧЕСКОЙ МАРШРУТИЗАЦИИ МОБИЛЬНОЙ САМООРГАНИЗУЮЩЕЙСЯ СЕТИ ДОСТУПА

Специальность 05.12.13 Системы, сети и устройства телекоммуникации

Автореферат диссертации на соискание ученой степени кандидата технических наук

Киров - 2014

005550554

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

Научный руководитель:

доктор технических наук, профессор Прозоров Дмитрий Евгеньевич Официальные оппоненты:

доктор технических наук доцент Красников Анатолий Константинович (ОАО «Концерн «Моринформсистема-Агат», начальник управления научно-образовательных программ и подготовки кадров)

доктор технических наук доцент Приоров Андрей Леонидович (Ярославский государственный университет, доцент кафедры динамики электронных систем)

Ведущая организация: Закрытое акционерное общество «Московский научно-исследовательский телевизионный институт» (ЗАО «МНИТИ»)

Защита диссертации состоится 20 июня 2014 года в 13.00 на заседании диссертационного совета Д212.131.01 (ауд. Д-117) при ФГБОУ ВПО «Московский государственный технический университет радиотехники, электроники и автоматики» (МГТУ МИРЭА) по адресу: 119454, г. Москва, проспект Вернадского, 78

С диссертацией можно ознакомиться в библиотеке МГТУ МИРЭА и на сайте http://www.mirea.ru/d-21213101/plan/index.html

Автореферат диссертации разослан «_» апреля 2014 г.

//

Ученый секретарь

диссертационного совета

Стариковский А.И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Фундаментальной особенностью 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, TBRPF, FLAME, AMRoute, AMRIS, FSR) предполагают построение таблиц маршрутизации на сетевых узлах предварительно, до получения запроса на передачу данных. Кроме того, сетевые узлы осуществляют периодический обмен служебными сообщениями для получения и обновления информации о структуре сети.

Основная идея, заложенная в реактивных протоколах (AODV, DSR), или -

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

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

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

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

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

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

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

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

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

- разработка архитектуры протокола,

- разработка алгоритма иерархической маршрутизации,

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

- разработка алгоритма кластеризации узлов MANET,

- разработка метода рассылки служебной информации MANET с кластеризацией узлов.

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

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

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

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

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

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

- алгоритм кластеризации узлов.

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

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

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

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

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

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

1. Взаимодействие алгоритмов внутрикластерной и межкластерной

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

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

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

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

5. Разработанный метод локального разделения каналов, обеспечивает вероятность коллизий при передаче пакетов данных не более 2% при равномерном размещении сетевых узлов.

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

использованием адекватной модели MANET, включающей в себя модели уровней OSI, обоснованием полученных научных и экспериментальных результатов, результатами внедрения разработок в процессе выполнения НИР.

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

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

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

Публикации. По результатам исследования опубликовано 14 работ; в том

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

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Во второй главе определены показатели качества протоколов маршрутизации, поставлена и решена задача разработки метода иерархической маршрутизации мобильной самоорганизующейся сети с динамической топологией. При решении поставленной задачи предполалось, что узлы (мобильные терминалы) сети обладают свойством групповой мобильности, объем сети имеет порядок 102ч-103 узлов, тип передаваемого трафика -смешанный (речь и данные), соблюдение показателей качества QoS не требуется.

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

Для реализации указанных алгоритмов протокол иерархической маршрутизации разделен на следующие независимые модули (агенты):

- агент иерархической маршрутизации (АИМ), реализующий алгоритм определения маршрута на основании иерархического идентификатора узла-адресата, в том числе алгоритм межкластерной маршрутизации;

- агент внутрикластерной маршрутизации (АВМ), реализующий алгоритм геомаршрутизации пакетов внутри кластера узла;

- агент кластеризации (АК), инкапсулирующий: метод кластеризации узлов сети, метод получения информации о топологии сети;

- агент геоинформации (АГ), реализующий метод получения информации о местоположении узлов сети.

Рис. 1. Кластерная структура сети

Структура MANET-сети с кластеризацией узлов представлена на рис.1. Определены основные типы сетевых узлов: сетевой узел с возможностью транзита (обычный узел сети), сетевой узел с функциями вершины кластера (вершина кластера), сетевой узел с функциями шлюза (шлюз). Сетевые узлы (рис.1) могут одновременно выполнять различные функции на различных уровнях. Например, вершина кластера на уровне L1 является «обычным» узлом уровня L2.

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

Маршрутизация на каждом уровне иерархии поддерживается независимо от других уровней. Взаимодействие между уровнями — рекурсивное. Аналогом данного метода маршрутизации (при использовании сосредоточенных шлюзов) является метод иерархической маршрутизации с логической организацией узлов в кластеры HSR (Hierarchical State Routing).

На каждом уровне иерархии сетевой узел имеет уникальный идентификатор (иерархический адрес). Если узел выполняет функции шлюза,

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

Начальным этапом работы MANET-сети (рис.1) является инициализация, включающая в себя этап кластеризации узлов. Известно, что методы кластеризации, основанные на идентификаторах (IBC - identifier-based clustering) имеет преимущество перед методами, основанными на связности узлов (СВС - connectivity-based clustering) в случае подвижности узлов. Поэтому, в качестве основы для разработки алгоритма кластеризации выбран алгоритм наименьшего идентификатора (LID). Разработана модификация алгоритма LID для корректной работы на сети с иерархической структурой (рис. 1). Сущность модификации заключается в адаптивном контроле количества узлов кластера с целью балансировки его среднего размера.

Метод получения информации о топологии сети определяет способность протокола реагировать на изменения топологии сети в реальном масштабе времени и, косвенным образом, определяет показатели эффективности протокола маршрутизации. Информация о топологии сети в локальных окрестностях узлов обычно распространяется широковещательными HELLO-пакетами.

В работе рассмотрены две стратегии распространения информации о структуре кластера. В «стратегии 1» промежуточные узлы кластера не производят ретрансляции широковещательных пакетов. Информация о топологии активных связей соседнего узла извлекается из широковещательных HELLO-пакетов. Примером такой стратегии является протокол OLSR. В предложенной «стратегии 2» каждый промежуточный узел кластера является источником широковещательного трафика интенсивностью и, кроме того, является ретранслятором широковещательного трафика других узлов кластера.

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

с^ ГНЕЦО([0.9/ц>]+1)

1 (I-jvxbAV)!09/¥M '

Tm([0.9/i|>] + l) 2 '

где THELLO - интервал между рассылкой HELLO-пакетов, Тш( - время обработки и ретрансляции широковещательного пакета на промежуточном узле, i|)=V-tR2/A , R — радиус зоны радиопокрытия узла, N - количество узлов кластера, А - площадь кластера, Д = 20мкс - временной слот, в течение которого сетевой интерфейс узла занят (при приеме HELLO-пакетов).

Проведенный анализ показывает, что:

1. «Стратегия 2» обработки широковещательных пакетов обеспечивает меньшее время распространения информации об изменениях топологии при относительно небольших размерах кластеров сети: N ~ 102 и отношении средней площади зоны радиовидимости узла к площади кластера 1.

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

3. «Стратегия 1» проигрывает «Стратегии 2» при уменьшении зоны радиовидимости узлов, но обеспечивает функционирование узлов кластера в более широком диапазоне вариации параметров протокола.

4. Поскольку при полном заполнении кластеров и двухуровневой иерархической структуре емкость сети (< 103 узлов) обеспечивается при среднем количестве узлов кластера N ~[v'l03], для использования рекомендуется «Стратегия 2».

В связи с тем, что в соответствии приказом №92 Минкомсвязи России от 03.05.2011 г. оборудование беспроводной передачи данных подлежит оснащению аппаратурой спутниковой навигации ГЛОНАСС или ГЛОНАСС/GPS, в перспективную группу протоколов маршрутизации MANET можно выделить протоколы, использующие данные о местоположении абонентов сети. Поэтому в качестве протокола внутрикластерной маршрутизации предложено использовать протокол геомаршрутизации. Разработанный алгоритм внутрикластерной дистанционно-векторной геомаршуртизации применяет следующие стратегии для повышения показателей качества передачи данных:

- использует информацию о местоположении сетевых узлов;

- использует метрики, учитывающих трехмерный вектор движения и расстояние от промежуточных узлов-ретрансляторов до адресата;

- использует геометрические ограничения на область ретрансляции служебных пакетов;

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

В диссертационной работе разработан метод межкластерной маршрутизации, позволяющий открывать маршруты между соседними кластерами без участия вершины кластера (рис.2, маршрут a-c-d-f) и

обеспечивающий относительный выигрыш в длине маршрутов сети до 25% по сравнению с методом маршрутизации, открывающим маршруты через вершины кластеров (рис.2, маршрут а-Ь-с-сН). Значение выигрыша рассчитано для наихудшего случая взаимного расположения кластеров.

Рис. 2. Иллюстрация метода межкластерной маршрутизации (т, - средняя длина маршрута между узлами кластера, ш2 — средняя длина маршрута от узла кластера до вершины кластера, т3 - средняя длина маршрута от узла кластера до шлюза)

Для иллюстрации разработанного метода иерархической маршрутизации рассмотрим сеть, содержащую три кластера с вершинами Ь, 'Г, т и суперкластер, содержащий вершины кластеров (рис.3). Узел-источник а имеет идентификатор (иерархический адрес) Юа=<Ь, а>. Узел-приемник (1) имеет идентификатор Ю1=<ш, 1>.

Шаг 1. Узел а просматривает список узлов кластера и не находит адресат 1. АИМ возвращает два идентификатора: на уровне 1Л - идентификатор следующего узла по направлению к вершине - Юь; на уровне Ь2 -идентификатор вершины кластера — 1с1ь. 1Р-пакет отправляется к узлу Ь -вершине кластера и содержит вектор маршрута уровня VI и идентификатор адресата - рис.3.

Рис.3. Пример работы протокола НОУС, шаг 1

Шаг 2. Узел Ь просматривает список узлов кластера и не находит адресат 1. Узел Ь, являясь вершиной кластера отправляет запрос АИМ уровня Ь2 (суперкластера). На уровне Ь2 узел Ь просматривает список узлов суперкластера и обнаруживает узел ш, входящий в идентификатор адресата ЮгМг=<т, 1>. Узел Ь на уровне Ь2 просматривает таблицу маршрутизации и определяет вектор маршрута к адресату: 10„ех1=^, I1 > - рис.4.

Рис. 4. Пример работы протокола 1ШУС, шаг 2

Узел Ь возвращает на уровень Ы ответ в виде 10„ех1=<^, Узел Ь на уровне 1Л интерпретирует идентификатор Юпех^*^, f> как идентификатор вершины соседнего кластера; узел Ь на уровне 1Л просматривает список узлов кластера для поиска шлюза к кластеру с вершиной f и обнаруживает узел с (шлюз с идентификаторами ЮС=<Ь, с> и , с1>) во втором

идентификаторе которого содержится адрес f. Узел Ь формирует 1Р-пакет к узлу с. 1Р-пакет отправляется к узлу с и содержит вектор маршрута уровня Ь2 и идентификатор адресата - рис.5.

© © ©

О \ / \/ О

©:Ь1^Чз](о] © ш)(и ©

© У ® У о У

Рис. 5. Пример работы протокола НОУв, шаг 2

Шаг 3. Узел с руководствуясь вектором маршрута уровня Ь2 , I1 >),

отправляет 1Р-пакет к шлюзу с! с идентификатором Idd=<f, с!> - рис.6 .

о © ©

Рис. 6. Пример работы протокола НСУС, шаг 3

Шаг 4. Узел с1 руководствуясь вектором маршрута уровня Ь2 (Ю^^, f>), отправляет 1Р-пакет к вершине кластера f.

Шаг 5. Узел f принимает 1Р-пакет с Юа[к|г=сш, 1>. Узел f: просматривает список узлов кластера и не обнаруживает узла 1; просматривает список шлюзов и обнаруживает шлюз д, один из идентификаторов которого содержит адрес ш вершины кластера адресата 1. Узел f отправляет 1Р-пакет к шлюзу д.

Шаг 6. Узел д принимает 1Р-пакет с ЮаЛс1г=<1Л, 1> и, руководствуясь вектором маршрута уровня Ь2, отправляет его шлюзу И.

Шаг 7. Узел И просматривает список узлов кластера с вершиной ш и обнаруживает узел 1, адрес которого содержится в Юаййг=<т, 1>. Узел 11 просматривает таблицу маршрутизации и (в соответствии с полученным из таблицы маршрутом) отправляет 1Р-пакет к ш.

Шаг 8. Узел ш принимает 1Р-пакет с 10аааг=<П1,1> и в соответствии с таблицей маршрутизации отправляет его узлу 1 - рис. 2.23.

Шаг 9. Узел 1 принимает 1Р-пакет с Юа1,6г=<т, 1>. Поскольку идентификатор адресата совпадает с идентификатором текущего узла, пакет считается доставленным.

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

В разработанном методе иерархической маршрутизации 1ШУО используются следующие типы служебных пакетов:

1. НЕЬЬО-пакеты. Необходимы для установлении связи между узлами на сетевом уровне, передачи информации о структуре кластера и реализации алгоритма кластеризации.

2. Нв ГО-пакеты. Необходимы для поддержки работы алгоритма внутрикластерной геомаршрутизации. Для снижения доли служебного трафика НСЕО-пакет отправляется узлом-источником только при

изменении положения узла, превышающем значение заданного порога. При этом, ЯСЕО-пакет «заменяет» собой отправку НЕ1ХО-пакета.

3. ReqID-пaкeты. Являются запросами на получение иерархического идентификатора узла по его 1Р-адресу. ReqID-иaкeты являются адресными и направляются по маршрутам к вершинам кластеров.

4. RepID-пaкeты. Являются ответами на запросы ReqID. RepID-пaкeты являются адресными и доставляются получателю кратчайшим путем в соответствии с уникальным идентификатором получателя.

Рис. 7. Рассылка ReqID-запросов

Рис. 7 иллюстрирует процесс рассылки ReqID-пакетов. Узел 3 является источником запроса. Далее, ReqlD-пакет направляется всем шлюзам (узлы 1 и 7), входящим в кластер узла 3. Адресная рассылка ReqID-пакетов позволяет снизить долю служебного трафика и вероятность коллизий в процессе маршрутизации пакетов.

Децентрализованное управление узлами MANET создает ряд проблем, одной из которых является организация доступа к разделяемым частотным и временным ресурсам системы связи (Media Access Control - MAC). В наихудшем случае отсутствие централизованного управления сетью может приводить к появлению «скрытых» (hidden) и «засвеченных» (explosed) узлов.

Одним из способов улучшения производительности MANET при большом количестве и высокой плотности узлов является разработка методов доступа к разделяемым ресурсам сети.

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

В произвольный момент времени доступ узлов кластера к радиоканалам может быть распределен следующим образом — рис. 8.

Количество фреймов М равно максимальному количеству кластеров сети. Количество слотов N, составляющих фрейм, равно максимальному количеству узлов кластера.

TS„ TS, TS,

фрейм 1

фрейм 2

фрейм M

Рис. 8. Схема разделения доступа к каналам (Р-ЬТОМА).

Пусть Рсегг(/с = п) - функция (3) распределения вероятности коллизий при отправке пакетов; п - количество узлов, пытающихся получить доступ к радиоканалу; каждый узел находится в отличном от остальных кластере. Распределение (3) зависит от множества факторов: количества выбранных узлов, количества узлов сети, плотности распределения и взаимного расположения узлов сети, площади сети и т. п.

I ^ 1 ^—N — 1 м-1 .

Рсе,г(к = ")=П

С'С

-i ° MN-n-i(N-l)

п

J MN — n — i (iV — 1)

hzRt А„

1

(3)

Для предельного (и наиболее распространенного случая) п = 2 выражение (3) можно преобразовать к виду

Рсегг('< = 2) =

1 —

nRi

А,

NT

(4)

Показано, что при типовом соотношении средней площади кластера к площади сети ^=0.1 вероятность коллизий примерно равна 2%. В наихудшем случае пространственного совмещения всех десяти кластеров вероятность коллизий не превышает 20%.

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

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

В результате анализа количественных показателей эффективности протоколов маршрутизации OLSR, AODV, GPSR и HDVG определены границы применимости разработанного протокола иерархической маршрутизации (HDVG) - рис. 9.

Количество узлов

а)

Количество узлов 6)

Рис. 9. Область применения протоколов маршрутизации при гарантированном коэффициенте доставки Кдн>20%

Показано, что:

1. Протокол НОУС, реализующий разработанный метод иерархической маршрутизации, имеет, в среднем, лучшие показатели по коэффициенту и времени доставки пакетов по сравнению с протоколами ОЬЭК, АСЮУ, СРЙК в следующем диапазоне изменения параметров мобильной

самоорганизующейся сети: скорость движения узлов ve[0;32] (м/с), количество узлов сети пб[50;300], среднее расстояние между узлами Я„е[3;150] (м).

2. При средней скорости узлов v = l (м/с) и количестве узлов п=300, протокол HDVG имеет преимущество по нормированному коэффициенту доставки над протоколами : OLSR в ],9 раза, AODV в 17 раз, GPSR в 2,1 раза; по среднему времени доставки пакета: OLSR в 3,4 раза, AODV в 1,1 раза, GPSR в 2,2 раза.

3. При средней скорости узлов v=32(m/c), количестве узлов п=300, протокол HDVG имеет преимущество по нормированному коэффициенту доставки над протоколами : OLSR в 7,5 раз, AODV в 15 раз, GPSR в 2,1 раза; по среднему времени доставки пакета: AODV в 6 раз, GPSR в 4,3 раза.

4. Наибольшую эффективность протокол HDVG показывает при небольшой и средней плотности распределения сетевых узлов (расстояние между узлами более 25 метров). При этом нормированный коэффициент доставки пакетов слабо зависит от степени мобильности узлов и находится в пределах, от Ка„=80% при п=50,до Ка„=30% при п=300.

В четвертой главе выполнен анализ архитектур сетевых узлов MANET, разработана архитектура абонентского терминала MANET-сети, реализующая протокол маршрутизации HDVG и определены требования по его техническому обеспечению. Обобщенная архитектура сетевого узла MANET, реализующая протокол маршрутизации HDVG представлена на рис. 10.

В заключении диссертационной работы сделаны следующие выводы.

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

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

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

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

- разработана архитектура протокола HDVG,

- разработан алгоритм иерархической маршрутизации,

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

- разработан алгоритм кластеризации узлов MANET,

- разработан метод рассылки служебной информации MANET с кластеризацией узлов.

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

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

Рис. 10. Обобщенная архитектура сетевого узла с протоколом маршрутизации HDVG

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

В изданиях, входящих в перечень ВАК РФ:

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

2. Романов С. В. Симуляторы беспроводных MANET-сетей / Жолобов А.Н., Прозоров Д.Е., Романов C.B. // Инфокоммуникационные технологии, 2012. - №3. - С.28 — 33.

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

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

5. Романов С. В. Стек протоколов когнитивных ad-hoc сетей / Лесников В.А.,

Романов C.B., Частиков A.B., Дубовцев Д.В. // Научное обозрение, 2013. -№2. - С.103-109.

6. Романов C.B. Методы гибридной и иерархической маршрутизации MANET / Романов C.B., Прозоров Д.Е. // Перспективы науки. - 2013, № 6. - С.72-76.

7. Романов C.B. Метод обработки широковещательного трафика MANET / Романов C.B., Прозоров Д.Е. //T-Comm. - 2013, №4. - С.32-34.

8. Романов С.В.Прозоров Д.Е, Множественный доступ с псевдослучайным разделением времени в MANET-сетях с кластеризацией узлов // Телекоммуникации, 2014. - № 3. - С. 14-17

в других изданиях:

9. Романов С. В. Оптимизация маршрутов в иерархическом протоколе передачи данных MANET-сетей [Электронный ресурс] / Романов C.B., Прозоров Д.Е. // Всероссийская НТК «Общество, наука, инновации» (НТК-2012): 16-27 апр. 2012 г. : сб. материалов / Вят. гос.ун-т. - Киров, 2012. - 1 электрон, опт. Диск (CD-ROM). - (Секция «Методы и средства передачи и обработки сигналов», ст. 2).

10. Романов С. В. Маршрутизация в беспроводных самоорганизующихся сетях. Иерархические и гибридные протоколы: / Прозоров Д.Е., Трубин И.С., Лесников В.А., Жолобов А.Н., Романов C.B. - Киров: ПРИП ФГБОУ ВПО «ВятГУ», 2013. - 100 с.

11. Романов C.B. Метод сокращения служебного трафика в иерархическом протоколе маршрутизации MANET-сети / Романов C.B., Прозоров Д.Е. // Доклады 15-й МНТК «Цифровая обработка сигналов и ее применение -DSPA-2013». - Москва, 2013. - В 2-х т., т.1. - С. 271-274.

12. Романов C.B. Гибридные и иерархические протоколы маршрутизации MANET-сетей [Электронный ресурс] // Всероссийская НТК «Общество, наука, инновации» (НТК-2013): 15-26 апр. 2013 г. : сб. материалов / Вят. гос.ун-т. - Киров, 2013. - 1 электрон, опт. Диск (CD-ROM). - (Секция «Методы и средства передачи и обработки сигналов», ст. 14).

13. Романов C.B. Архитектура абонентского терминала MANET-сети / Романов C.B. // Материалы X МНТК «Теоретические и практические аспекты развития современной науки». - Москва, 2013. - С. 74-79.

14. Романов C.B., Жолобов А.Н. Свидетельство о регистрации программы для ЭВМ «Программа «ММ-сеть» №2012616121 от 04.07.12.

Подписано в печать 19.04.2014. Формат 200x140 мм. Тираж 100 экз. Печать цифровая . Ne заказа 217. Отпечатано в типографии ОАО «НИИ СВТ» 610025, Г.Киров, ул. Мельничная, 31. тел. (8332) 67-99-75, e-mail: niisvt@niisvt.ru

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

04201453280

РОМАНОВ СЕРГЕЙ ВЛАДИМИРОВИЧ

МЕТОД ИЕРАРХИЧЕСКОЙ МАРШРУТИЗАЦИИ МОБИЛЬНОЙ САМООРГАНИЗУЮЩЕЙСЯ СЕТИ

ДОСТУПА

05.12.13 - «Системы, сети и устройства телекоммуникации»

Диссертация

на соискание ученой степени кандидата технических наук Научный руководитель: доктор техн. наук, профессор Прозоров Д.Е.

«ВЯТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

На правах рукописи

Киров-2014

Оглавление

Введение......................................................................................................................6

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение.............................................................................................................139

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

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

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 и проч.) становятся малопригодными для