Содержание к диссертации
Введение
ГЛАВА 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
- Анализ затрат на хранение таблиц маршрутизации
- Разработка метода иерархической дистанционно-векторной геомаршрутизации (HDVG)
- Программная реализация распределенной системы имитационного моделирования
- Анализ показателей эффективности метода иерархической маршрутизации при изменении размера кластера
Введение к работе
Актуальность проблемы. Активно развивающейся в настоящий момент областью беспроводных сетей доступа являются MANET – мобильные самоорганизующиеся сети (Mobile Ad-hoc NETworks). MANET является сложной распределенной системой, включающей в себя мобильные узлы, имеющие возможность самостоятельно организовываться в сеть с динамически меняющейся топологией. Динамическая структура MANET позволяет абонентам пользоваться сетевыми сервисами в областях, где фактически отсутствует традиционная фиксированная структура телекоммуникационных, в том числе беспроводных сетей. Подобные сети могут применяться во время военных действий, в структурах МЧС, в транспортных системах и различных силовых структурах.
Фундаментальной особенностью MANET является функциональная эквивалентность узлов сети в отличие от беспроводных «инфраструктурных», в том числе – сотовых сетей. Отсутствие централизованного управления в подобных сетях требует от абонентских терминалов применения специализированных протоколов, использующих служебные пакеты для получения информации о топологии сети и построения маршрутных таблиц. Вследствие этого абонентские терминалы MANET являются не только приемопередатчиками, но и «интеллектуальными» маршрутизаторами сети.
Проблема маршрутизации пакетов данных с учетом мобильности узла-отправителя, узла-приемника и транзитных узлов при масштабировании сети до единиц и десятков тысяч абонентов в таких условиях становиться чрезвычайно сложной, а задача разработки протоколов маршрутизации, быстро адаптирующихся к изменениям топологии сети и имеющих небольшие накладные расходы на поиск и поддержку маршрутов, одной из наиболее важных и актуальных задач.
Анализ публикаций зарубежных (X. Hong, G.V. Kumar, T. Clausen, M. Gerla, A. Iwata, M.S. Corson, S. Taneja, Z.J. Haas, P.S. Kumar, Винокуров В.М.) и отечественных (А.И. Ляхов, А.А. Сафонов, В.Г. Маркин, В.Г. Орлов, А.Н. Фадеев, А.Л. Афанасьев, В.С. Еремин, М.А. Гоголева и др.) авторов, посвященных протоколам маршрутизации 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-сетях большого размера за счет организации сетевых узлов в иерархические структуры или кластеры. В протоколы данной группы также может быть встроен механизм геомаршрутизации, позволяя улучшить показатели качества сети. Недостатком протоколов данного класса является относительная сложность реализации.
Целью диссертационной работы является улучшение показателей качества и масштабируемости мобильной самоорганизующейся сети доступа с иерархической кластеризацией узлов.
Для достижения указанной цели поставлены и решены следующие задачи.
-
Обзор, анализ и классификация алгоритмов маршрутизации мобильных самоорганизующихся сетей связи (MANET).
-
Разработка критериев оценки алгоритмов маршрутизации мобильных ad-hoc сетей, анализ недостатков существующих алгоритмов маршрутизации.
-
Разработка метода иерархической маршрутизации и реализация прототипа протокола маршрутизации MANET, в том числе: разработка архитектуры протокола, разработка алгоритма иерархической маршрутизации, разработка алгоритма внутрикластерной геомаршрутизации, разработка алгоритма кластеризации узлов MANET, разработка метода рассылки служебной информации MANET с кластеризацией узлов.
-
Разработка программной модели протокола иерархической маршрутизации MANET в системе моделирования телекоммуникационных сетей на основе вычислительного кластерного комплекса.
-
Разработка архитектуры абонентского терминала MANET. Методы исследования. Для решения поставленных в работе задач
используются методы статистической теории связи, статистического моделирования, теории телетрафика, линейной алгебры и тригонометрии, интегрального счисления, системного анализа.
Научная новизна полученных результатов состоит в следующем:
1. Разработан новый метод иерархической маршрутизации, позволяющий
строить мобильные самоорганизующиеся сети доступа (MANET) большой
емкости (до ~103 узлов) и включающий:
алгоритм межкластерной маршрутизации,
алгоритм внутрикластерной маршрутизации,
алгоритм кластеризации узлов.
-
Разработан новый метод обработки и ретрансляции широковещательных пакетов в мобильных самоорганизующихся сетях с кластеризацией узлов.
-
Разработан новый метод локального временного разделения каналов для алгоритма внутрикластерной маршрутизации пакетов данных.
Практической значимостью обладают следующие результаты.
-
На основе разработанного метода иерархической маршрутизации реализована программная модель прототипа протокола HDVG, обеспечивающего, в среднем, лучшие показатели по коэффициенту и времени доставки пакетов по сравнению с протоколами OLSR, AODV, GPSR в следующем диапазоне изменения параметров мобильной самоорганизующейся сети: скорость движения узлов ve[0;32] (м/с), количество узлов сети иє[50;300], среднее расстояние между узлами Диє[3;150](м).
-
Реализованный протокол иерархической маршрутизации HDVG позволяет развертывать мобильные самоорганизующиеся сети доступа большой емкости (до ~103 узлов). При этом нормированный коэффициент доставки пакетов слабо зависит от степени мобильности узлов и находится в пределах, от KdH = 80% при и = 50, до Кдн=30% при п=300 и скорости движения узлов до v=32 (м/с) (~115 (км/ч)).
-
Разработана программная среда для распределенной симуляции MANET на основе кластерной вычислительной системы, позволяющая тестировать программную модель мобильной самоорганизующейся сети доступа, использующей протокол иерархической маршрутизации HDVG и включающая модели физического, канального, сетевого уровней OSI и уровня приложения.
-
Разработана архитектура мобильного сетевого терминала MANET, позволяющая реализовать автоматическую интеллектуальную маршрутизацию пакетных данных в соответствии с разработанным протоколом HDVG с учетом географических координат абонентов.
Положения, выносимые на защиту.
1. Взаимодействие алгоритмов внутрикластерной и межкластерной маршрутизации позволяет сократить накладные расходы на открытие и
поддержку маршрутов MANET.
-
Разработанный алгоритм кластеризации, формирующий распределенные шлюзы между соседними кластерами сети позволяет сбалансировать средний размер кластеров MANET.
-
Использование информации о местоположении и векторах движения сетевых узлов в алгоритме внутрикластерной маршрутизации MANET позволяет оптимизировать открываемые маршруты.
-
Разработанный метод обработки и ретрансляции служебных широковещательных пакетов сокращает время распространения информации о локальных изменениях структуры MANET с кластеризацией узлов.
-
Разработанный метод локального разделения каналов, обеспечивает вероятность коллизий при передаче пакетов данных не более 2% при равномерном размещении сетевых узлов.
-
Программная модель MANET с кластеризацией сетевых узлов, позволяет оценить показатели качества разработанного метода иерархической маршрутизации в системе распределенного моделирования телекоммуникационных сетей на основе кластерного комплекса. Достоверность материалов диссертационной работы подтверждается
использованием адекватной модели MANET, включающей в себя модели уровней OSI, обоснованием полученных научных и экспериментальных результатов, результатами внедрения разработок в процессе выполнения НИР.
Личный вклад автора. Выносимые на защиту положения предложены автором в процессе выполнения НИР, а также изложены в научных работах автора. Реализация программной модели MANET с кластеризацией узлов выполнялась коллективом исследователей на кафедре радиоэлектронных средств ФГБОУ ВПО «ВятГУ» при личном участии автора.
Внедрение результатов работы. Теоретические и практические результаты, полученные при выполнении диссертационной работы использованы в НИР «Разработка прототипа телекоммуникационного протокола полносвязной самоорганизующейся сети связи повышенной устойчивости» (шифр заявки «2011-1.4-514-064-002») в рамках федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2013 годы»; внедрены в ЗАО «МНИТИ» (г. Москва); ОАО «НИИ СВТ» (г. Киров); учебный процесс в Вятском государственном университете.
Апробация работы. Основные результаты работы докладывались и обсуждались на следующих конференциях: всероссийской НТК «Общество, наука, инновации» (НТК-2012); международной НТК «Цифровая обработка сигналов и ее применение – DSPA-2013»; XIII международной НТК «Теория и практика современной науки», 2013 г.
Публикации. По результатам исследования опубликовано 14 работ; в том числе: 8 статей в изданиях из числа рекомендованных ВАК для опубликования
результатов диссертационных исследований), 1 учебное пособие, 3 тезиса докладов. Получено свидетельство об официальной регистрации программы для ЭВМ.
Структура и объем работы. Диссертационная работа состоит из введения, 4 глав, заключения и списка литературы. Работа изложена на 148 страницах машинописного текста, содержит 58 рисунков и 8 таблиц. Список литературы включает 63 наименования.
Анализ затрат на хранение таблиц маршрутизации
Иерархические протоколы CGSR и HSR прокладывают путь через выделенные узлы - вершины кластеров и шлюзы, образуя субоптимальные маршруты. Два протокола с неявной иерархией - ZRP и LANMAR используют алгоритм поиска кратчайшего пути для каждого узла. Однако, LANMAR гарантирует кратчайший путь только для узлов внутри локальной зоны. Для удаленных узлов LANMAR сначала прокладывает маршрут к ориентиру в локальной зоне которого находится адресат; при этом часть хопов может переместиться прежде чем пакет будет доставлен. Подобно этому, другой протокол с неявной иерархией ZRP не поддерживает оптимальный кратчайший путь для всех возможных случаев.
CGSR поддерживает две таблицы - таблицу членов кластера и таблицу маршрутизации. Таблица маршрутизации содержит по одному маршруту к каждому кластеру (точнее, к вершине кластера). Порядок расходов на хранение этих маршрутов равен 0(N/M), где N - среднее число узлов сети, М -размер кластера. Таблица членов кластеров содержит по одной записи на каждый кластер. Расходы на хранение этой таблицы также равны 0(Ы/М).
В HSR узлы, выполняющие функции различных логических уровней, требуют различных ресурсов для хранения данных. Наихудшая ситуация наблюдается на узлах высших уровней, поскольку узлы высшего уровня поддерживают Я таблиц маршрутизации, где Я - число логических уровней иерархии сети. Таким образом, расходы на хранение маршрутной информации в худшем случае равны
ZRP имеет различные таблицы маршрутизации для протоколов внутризоновой и межзоновой маршрутизации. Протокол внутризоновой маршрутизации - проактивный и расходы на его поддержание равны О(ь), где L - среднее число узлов локальной зоны маршуртизации. Протокол межзоновой маршрутизации относится к классу дистанционно-векторных протоколов и расходы на его поддержание равны 0(l)+0(e), где е - средний коэффициент индивидуальной связности узла.
В протоколе LANMAR каждый узел также поддерживает две таблицы маршуртизации. Одна из них - таблица “локальной” маршрутизации, хранящая треки для всех узлов внутри локальной зоны. Вторая - таблица маршрутизации, поддерживающая пути к ориентирам групп узлов. Таким образом, расходы на поддержание этих таблиц равны 0(L)+0(G), где G - число групп. Обычно, число групп мало. Например, сеть из 100 узлов может содержать 4 группы по 25 узлов, а сеть из 1000 узлов может быть разделена на 40 групп.
Протокол DDR предусматривает хранение списка узлов для локальной зоны (интра-зона) и списка шлюзов к соседним зонам (интер-зона). Затраты на хранение списка интра-зоны имеют порядок О(ь); затраты на хранение списка шлюзов к соседним зонам равны 0(E) , где Е - коэффициент связности зоны. Общие затраты равны 0{L)+0(E).
Узел ZHLS поддерживает таблицу “уровня узла” со списком узлов зоны и их соседей и таблицу “уровня зоны”, содержащую по одной записи на каждую зону сети. На хранение первой таблицы требуются затраты порядка O(L-e); на хранение второй - 0(G), где G - число зон. Общие затраты равны 0(L-e)+0(G).
Расходы на поддержание связи в CGSR протоколе имеют порядок O(N) , поскольку таблица маршрутизации и таблица членов кластеров рассылается по всей сети. Обновление связей между узлами в протоколе HSR распространяется по дереву иерархии. В худшем случае, если изменяется вершина кластера высшего уровня, расходы на поддержку связей равны О(М-Я). Выражение О(М-Я) можно раскрыть как 0(M-logMiV). Для ZRP худший случай возникает, когда обрыв связи вызывает открытие нового маршрута через всю сеть; в этом случае расходы равны 0(N). В LANMAR, DDR и ZHLS расходы на коммуникацию внутри группы (или зоны) имеют порядок О(ь), суммарные расходы имеют порядок O(N).
Сравнение затрат при использовании “плоских” и иерархических протоколов показывает сокращение затрат на поддержку таблиц маршрутизации при использовании иерархических методов и примерно равные затраты на поддержку коммуникаций. Иерархические протоколы позволяют значительно сократить объем служебного трафика, рассылаемого по сети, поскольку изменение топологии внутри кластера или локальной зоны приводит только к локальному росту трафика. Например, оценка затрат на коммутацию протокола HSR приближенно равна 0(M-logMiV), в то время как у “плоских” протоколов аналогичные затраты равны O(N).
В то же время, протоколы с явной иерархией (HSR) имеет сложные процедуры регистрации иерархического адреса и маршрутизации данных. ZRP и LANMAR используют проактивную маршрутизацию внутри локальных зон. Для маршрутизации пакетов вне локальной зоны ZRP использует реактивный, а LANMAR - проактивный протоколы. При увеличении масштаба сети, возрастает вероятность нахождения конечного адресата за пределами локальной зоны. При использовании протоколов ZRP и ZHLS в этом случае возникают проблемы, аналогичные проблемам реактивных протоколов на больших сетях, в частности, непредсказуемый рост служебного трафика. LANMAR в этом случае имеет преимущество, поскольку средний размер вектора от узла к ориентиру увеличивается медленно. Существенное ограничение LANMAR связано с поведением мобильных узлов - “групповой мобильностью”. DDR, в свою очередь, создает существенные задержки при инициализации сети и добавлении/удалении узлов (что приводит к перестроению дерева топологии в локальной области). Кроме того, отсутствует гарантия, что “лесом” деревьев будет покрыта вся сеть [36].
Анализ рассмотренных протоколов маршрутизации позволяет выделить следующие основные подходы к организации сетевых узлов в группы:
- по географическому положению;
- неявная иерархия, в которой логика маршрутизации пакетов зависит от нахождения адресата внутри или снаружи некоторой локальной области вокруг текущего узла; маршрутизация пакетов между локальными областями осуществляется за счет их перекрытия;
- явная логическая иерархия узлов, в которой сетевые узлы могут выполнять различные функции в зависимости от принадлежности той или иной «иерархической плоскости».
На основании приведенного в главе 1 краткого обзора можно обощить стратегии, применяемые для повышения параметров эффективности протоколов гибридной и иерархической маршрутизации:
использование методов теории графов для сокращения служебного трафика: TORA, CBRP, DDR,
использование геоинформационных данных, в том числе от систем геопозиционирования: ZHLS, LANMAR,
адаптивное изменение размеров зон (кластеров) в зависимости от локальных метрик сети: ZHLS, DDR,
Разработка метода иерархической дистанционно-векторной геомаршрутизации (HDVG)
В главе 1 показано, что методы гибридной и иерархической маршрутизации, а также реализующие их протоколы в общем случае могут включать в себя несколько независимых компонент:
метод внутрикластерной (внутризоновой) маршрутизации,
метод межкластерной (межзоновой) маршрутизации,
метод кластеризации,
метод формирования уникальных идентификаторов сетевых узлов (метод иерархической адресации),
метод получения информации о топологии сети.
Наличие информации о местоположении сетевых узлов позволяет улучшить показатели эффективности методов маршрутизации [1], [2], [17], [34], [41]. Таким образом, дополнительной компонентой метода маршрутизации может являться:
метод получения информации о местоположении сетевых узлов. Указанные компоненты должны быть, по возможности, независимыми для снижения временных затрат на практическую реализацию разработанного метода в виде протокола маршрутизации MANET и его отладку.
Для формирования логики взаимодействия отдельных компонент метода иерархической маршрутизации необходимо также разработать архитектуру функциональных модулей протокола, реализующего метод маршрутизации.
Архитектура протокола иерархической маршрутизации
Здесь и далее будем называть функциональные модули (компоненты) протокола, реализующего метод маршрутизации «агентами».
С учетом вышесказанного, протокол маршрутизации должен состоять из следующих независимых модулей:
агент иерархической маршрутизации (АИМ),
агент внутрикластерной маршрутизации (АВМ),
агент кластеризации (АК), инкапсулирующий: метод кластеризации узлов сети, метод получения информации о топологии сети,
агент геоинформации (АГ), инкапсулирующего метод получения информации о местоположении узлов сети.
Обобщенная архитектура протокола маршрутизации.
Обобщенная архитектура протокола, реализующего метод иерархической маршрутизации и позволяющего использовать геоинформационные данные представлена на рис.2.2.
Определим основные типы сетевых узлов:
1. сетевой узел с возможностью транзита (обычный узел сети),
2. сетевой узел с функциями вершины кластера (вершина кластера),
3. сетевой узел с функциями шлюза (шлюз).
. Иллюстрация проблемы кластеризации при наличии «сосредоточенных» шлюзов.
В гибридных и иерархических протоколах маршрутизации могут применяться как обычные, принадлежащие одновременно нескольким кластерам, так и распределенные шлюзы. Под распределенным шлюзом понимается пара узов, принадлежащих разным кластерам, через которые осуществляется межкластерный обмен данными.
Большинство методов маршрутизации предусматривают возможность образования в процессе кластеризации нескольких шлюзов между парой близко расположенных кластеров. В этом случае, при использовании «сосредоточенных» шлюзов — узлов, одновременно принадлежащих нескольким кластерам, может наблюдаться процесс, приводящий к значительному сокращению емкости сети — рис.2.3.
На рис.2.3 изображен процесс кластеризации узлов при сближении двух кластеров: первый кластер содержит узлы 1 и 2, второй — узлы 3, 4 и 5. После появления узла 3 в зоне радиовидимости первого кластера, узел 3 меняет свой статус на статус шлюза — рис.2.3, б. На этом этапе первый кластер содержит узлы 1, 2 и 3, второй — узлы 3, 4 и 5. При дальнейшем сближении кластеров количество шлюзов увеличивается — рис. 2.3, в. В наихудшем случае все узлы обоих кластеров могут стать шлюзами. Тогда общая емкость сети остается прежней, а емкость кластеров увеличивается. Вследствие быстрого роста служебного трафика при увеличении количества узлов кластеров ухудшаются показатели эффективности протокола маршрутизации.
Для решения описанной проблемы будем использовать идеологию «распределенных» шлюзов.
С учетом вышесказанного, иерархическая структура сети может иметь вид рис. 2.4.
Сетевые узлы могут одновременно выполнять различные функции на различных уровнях. Например: вершина кластера на уровне L1 является «обычным» узлом уровня L2.
В качестве протокола внутрикластерной маршрутизации будем использовать проактивный геопротокол. Преимуществом геопротоколов является отсутствие этапа поиска маршрута, уменьшение служебного трафика и уменьшение задержек, связанных с прокладкой маршрута.
Маршрутизация на каждом уровне иерархии поддерживается независимо от других уровней. Взаимодействие между уровнями — рекурсивное. Аналогом данного метода маршрутизации является HSR [22].
Программная реализация распределенной системы имитационного моделирования
Несмотря на то, что системой NS-3 предоставлен ряд операций, способных выполняться параллельно, задача симуляции беспроводной самоорганизующиеся сети на данный момент не имеет возможности быть распределенной в рамках одной из рассмотренных систем симуляции. Это связано с тем, что подвижные узлы могут свободно перемещаться по всему полю симуляции. При этом системе моделирования неизвестно, какие узлы в итоге могут взаимодействовать в данный момент. Это обстоятельство вынуждает отказаться от идеи распараллеливания симуляции в рамках одного эксперимента. Однако сохраняется возможность распараллеливания «по параметрам» симуляции. Для упрощения и автоматизации такой задачи реализован программный комплекс parallelshell, который отвечает за распределённый запуск симуляций на всех узлах.
Принцип распределения вычислений «по параметрам» заключается в следующем. Система симуляции собирается в один исполняемый файл, способный принимать входные параметры симуляции и отдавать выходные данные после симуляции. Из этого исполняемого файла формируется задача.
Под задачей понимается специально подготовленная директория, содержащая:
- исполняемый файл (как правило, для экономии ресурсов используется не сам файл, а символическая ссылка на него),
- файл параметров, автоматически сгенерированный системой,
- скрипт, который подставляет указанные параметры в исполняемый файл,
- файл выходные данные, появляющийся после выполнения задачи.
На этапе инициализации происходит опрос доступных узлов и
формирования стека задач. Каждая задача получает свой уникальный идентификатор и рассчитывается её ориентировочная сложность. Необходимость в расчёте сложности связана с равномерным распределением задач между узлами вычислительного кластера.
Этап обработки начинается с поиска решённых задач. Поскольку множество экспериментов на разных испытаниях пересекается, есть шанс, что некоторые симуляции уже были совершены. Происходит поиск в кэше задач с такой же сложностью, затем производится поэлементное сравнение входных параметров. Если параметры совпадают, то система вместо отправки задачи на вычислительный кластер берёт сразу готовое решение. Подобный метод позволяет существенно сэкономить машинное время.
Далее управляющая программа опрашивает узлы на занятость. В случае если узел свободен, программа отправляет на выполнение задачу из очереди. В случае, если свободных узлов нет, система ожидает освобождения одного из узлов. Если узел освобождается, система забирает у него решённую задачу и отдаёт следующую. Как только задачи из очереди заканчиваются, система дожидается решения последней задачи и сообщает пользователю о завершении вычислений.
На этапе анализа происходит агрегирование всех входных и выходных данных, их статистический анализ и построение графиков.
Исследуем четыре варианта протокола маршрутизации мобильных самоорганизующихся сетей связи, на основе созданной программной реализации протокола (HDVG) и уже существующих в симуляторе NS-3 реализаций (протколы AODV, OLSR, GPSR):
- HDVG, иерархический протокол с проактивной дистанционно-векторной геомаршрутизацией,
- OLSR, проактивный протокол маршрутизации по состоянию канала,
- AODV, реактивный дистанционно-векторный протокол маршрутизации для одноранговых сетей,
- GPSR, протокол маршрутизации, использующий данные о местоположении сетевых узлов.
- 107 С целью анализа и подтверждения теоретических положений, проведем имитационное моделирование мобильной самоорганизующейся сети для каждого из указанных типов протоколов маршрутизации. Имитационное моделирование позволяет оценить количественные метрики эффективности протоколов маршрутизации. В п.2.2, а также работе [38] показано, что наиболее важными количественными метриками пакетной беспроводной сети являются:
- коэффициент доставки пакетов,
- среднее время доставки пакетов по маршруту.
Будем использовать нормированный коэффициент доставки пакетов, учитывающий долю открывшихся маршрутов.
Варьируемыми параметрами мобильной самоорганизующейся сети являются:
- п - количество сетевых узлов,
- Rn - расстояние между сетевыми узлами,
- N - максимальное количество узлов в кластере для протокола HDVG,
- v - скорость движения сетевых узлов.
Анализ показателей эффективности метода иерархической маршрутизации при изменении масштаба сети и плотности узлов
На рис. 3.3 - 3.9 представлены графики зависимости нормированного коэффициетна доставки и среднего времени доставки пакета от количества узлов в сети и расстояния между узлами. Расчеты произведены при следующих параметрах сети:
- количество узлов сети пє[50;300] ,
- среднее расстояние между узлами і?пє[3; 150] (м) ,
- скорость движения узлов v=0 (м/с),
- максимальное количество узлов в кластере (HDVG) N= 30 .
Анализ показателей эффективности метода иерархической маршрутизации при изменении размера кластера
На рис. 3.18, 3.19 представлены графики зависимости нормированного коэффициетна доставки и среднего времени доставки пакета от размера кластера. Исследования произведены при следующих параметрах сети:
- скорость движения узлов v=0 (м/с),
- количество узлов сети пє[50;300] (м),
- расстояние между узлами Rn=100 (м),
- количество узлов в кластере: iV=30, iV=100 узлов.
По рис. 3.18, 3.19 можно сделать вывод, что коэффициенты доставки пакетов практически не зависят от максимального размера кластера мобильной самоорганизующейся сети, а среднее время доставки пакетов при использовании протокола HDVG может быть снижено в 2,5 раза путем уменьшения размера кластера при большом количестве узлов (N= 100 (ед.)).
1. В соответствии с выбранными критериями оценки сетевых симуляторов (тип лицензии, кроссплатформенность, поддержка беспроводных стандартов связи, поддержка распределенных вычислений) оптимальным для тестирования программной модели протокола маршрутизации является проект NS-3.
2. Разработанная в симуляторе NS-3 программная модель мобильной самоорганизующейся сети доступа, реализует метод иерархической маршрутизации HDVG и включает модели физического, канального, сетевого уровней OSI и уровня приложения.
3. Протокол HDVG, реализующий разработанный метод иерархической маршрутизации, имеет, в среднем, лучшие показатели по коэффициенту и времени доставки пакетов по сравнению с протоколами OLSR, AODV, GPSR в следующем диапазоне изменения параметров мобильной самоорганизующейся сети: скорость движения узлов ve[0;32] (м/с), количество узлов сети пє[50;300], среднее расстояние между узлами Дпє[3;150](м).
- При средней скорости узлов v = 1 (м/с) и количестве узлов /1 = 300, протокол HDVG имеет преимущество по нормированному коэффициенту доставки над протоколами : OLSR в 1,9 раза, AODV в 17 раз, GPSR в 2,1 раза; по среднему времени доставки пакета: OLSR в 3,4 раза, AODV в 1,1 раза, GPSR в 2,2 раза.
При средней скорости узлов v=32 (м/с) , количестве узлов n=300 , протокол HDVG имеет преимущество по нормированному коэффициенту доставки над протоколами : OLSR в 7,5 раз, AODV в 15 раз, GPSR в 2,1 раза; по среднему времени доставки пакета: AODV в 6 раз, GPSR в 4,3 раза.
4. Наибольшую эффективность протокол HDVG показывает при небольшой и средней плотности распределения сетевых узлов (расстояние между узлами более 25 метров). При этом нормированный коэффициент доставки пакетов слабо зависит от степени мобильности узлов и находится в пределах, от Кдн=80 % при n=50 , до Кдн=30% при n=300 .
Особенности MANET позволяют рекомендовать к внедрению разработанный протокол маршрутизации в следующих сферах деятельности:
- тактические сети – военные тактические сети передачи данных;
- сенсорные сети – сети интеллектуальных датчиков, используемые для сбора данных в реальном масштабе времени;
- мониторинг погодных условий;
- мониторинг сейсмической активности Земли;
- автоматизация сбора данных в жилых зданиях;
- аварийные службы – организация связи в поисковых и спасательных операциях и прочих медицинских приложениях;
- автомобильные сети - обеспечение контроля дорожного трафика, связь с техническими службами и дорожной полицией, доступ к информационным сервисам (погода, пробки, новости) из автомобиля;
- коммерческие приложения – «электронная коммерция», проведение платежей в произвольной точке;
- домашние и корпоративные сети - доступ к сетевым ресурсам с мобильных устройств, персональные сети;
- образовательные приложения – виртуальные учебные классы или виртуальные конференции с доступом к медиа-ресурсам и возможностью общения;
- развлечения – многопользовательские игры, игрушечные роботы и доступ к интернету вне дома;
- сервисы, зависящие от местоположения - переадресация вызовов в любую точку, сохранение настроек локального информационного окружения независимо от местоположения абонента, информационные сервисы для туристов, навигационные сервисы для туристов. Помимо классификации, представленной в главе 1, MANET можно классифицировать в зависимости от области покрытия сети [60]:
- BAN-Body Area Network – для связи носимых устройств, находящихся непосредственно на теле человека;
- PAN – Personal (персональная) Area Network – для связи носимых пользователем устройств с другими стационарными или мобильными устройствами, находящимися вблизи пользователя;
- LAN- Local (локальная) Area Network;
- MAN- Metropolitan (региональная (городская)) Area Network;
- WAN- Wide (глобальная) Area Network.
В таблице 4.1 приведены некоторые характеристики ad-hoc сетей разного маштаба, основанные на данных работы [60].
