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

На правах рукописи П У ^

Голубев Андрей Сергеевич

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

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

Автореферат

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

1 5 ДЕК 2008

Владимир — 2008

003458019

Работа выполнена во Владимирском государственном университете.

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

доктор физико-математических наук, профессор Аракелян Сергей Мартиросович

Официальные оппоненты:

доктор технических наук, профессор Жигалов Илья Евгеньевич

кандидат технических наук, профессор Медведев Юрий Алексеевич

Ведущая организация:

Государственный научно-исследовательский институт информационных технологий и телекоммуникаций (ФГУ ГНИИ ИТТ «Информика»)

Защита диссертации состоится «29» декабря 2008 года в И00 на заседании диссертационного совета Д 212.025.04 в ауд. 301(3) Владимирского государственного университета по адресу: 600000, Владимир, ул.Горького, 87, ФРЭМТ.

С диссертацией можно ознакомиться в библиотеке Владимирского государственного университета.

Автореферат разослан « 2008 г.

Ученый секретарь диссертационного аа^ета / /

доктор технических наук, профессор ( У/ А.Г. Самойлов

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

Актуальность работы

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

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

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

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

Методы исследования

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

Научная новизна

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

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

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

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

Практическая ценность

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

Реализация и внедрение результатов

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

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

- Владимирский государственный университет;

- ООО «ФС Сервис»;

- Международный учебно-научный лазерный центр МГУ им. М.В.Ломоносова (МЛЦ МГУ).

Внедрение подтверждено соответствующими актами.

Апробация работы

Основные результаты работы докладывались и экспонировались на следующих научно-технических совещаниях и конференциях:

- Международная конференция «Телекоммуникационные и информационные системы», Санкт-Петербург, 2007 г.

- Международный форум по проблемам науки, техники и образования, Москва, 04-12 декабря 2007 г.

- XIV Всероссийская научно-методическая конференция «Телематика-2007», Санкт-Петербург, 18-21 июня 2007 г.

- VIII Международная научно-техническая конференция «Физика и радиоэлектроника в медицине и экологии» ФРЭМЭ'2008, Владимир, 02-04 июля 2008.

- Международная научно-техническая конференция «Перспективные технологии в средствах передачи информации», Владимир, 10-12 ноября 2007 г.

- Выставка-ярмарка «Современная образовательная среда», Москва, ВВЦ 03.10-06 ноября 2007 г.

- Всероссийская научно-методическая конференция «Инновационные технологии обучения: проблемы и перспективы», Липецк, 29-30 марта 2008.

- XV конференция представителей региональных научно-образовательных сетей «RELARN-2008», Н.Новгород, 01-08 июня 2008.

На защиту выносятся следующие положения:

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

- Математическая модель структурных особенностей сети.

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

Публикации

Основные результаты работы представлены в 7 публикациях, в том числе 1 статье в журнале из перечня ВАК, а также в научно-технических отчетах НИР, выполняемых по заданию Рособразования и Роснауки.

Объем и структура диссертации

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

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

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

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

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

В то же время беспроводные технологии позволяют организовать новый тип сетей, где абонентские устройства взаимодействуют друг с другом напрямую, без посредничества каких-либо точек доступа (сети MANET). Сфера применения MANET достаточно широка. Традиционно к ней принято относить функции организации связи при проведении военных или спасательных операций. Но с появлением новых технологий, таких как Bluetooth и Wi-Fi, растет интерес и к гражданским областям применения. Среди них можно отметить возможности организации сенсорных сетей, временных покрытий для доступа к публичным сетям, домашние сети, разнообразные сервисы мультимедийной коммуникации.

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

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

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

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

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

Рис. 1. Пример структурной особенности сети МАКЕТ при поисковой операции.

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

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

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

1. Согласно классическим представлениям, сеть ассоциируется с неориентированным связным графом С (К, Е), где V - множество вершин, Е - множество ребер. Каждая вершина символизирует узел сети, каждое ребро - канал передачи данных. Отличительная особенность заключается в том, что множество ребер включает все реализуемые связи, т.е. граф является постоянным во времени.

2. Между узлами графа вводится абстрактное отношение

эквивалентности, названное 32-отношением и обозначаемое символом Именно оно характеризует структурную особенность сети -неравноправность связей. Если пара узлов находится в ^-отношении, то ребро между ними объявляется Я-связью. Совокупность вершин и Л-связей образуют 32-граф.

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

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

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

Модель конечных состояний'.

- Каждый узел V £ V - «штатная единица».

- Согласно «штатному расписанию» узел V может находиться: а) в к(р) различных состояниях («помещениях»); б) в каждом состоянии с фиксированной вероятностью I = 1, к (и).

- Для каждой пары узлов V и и известна бинарная матрица совместимости состояний Я"" = {я™}, состоящая из 0 и 1.

л

- зг-отношение вводится следующим образом: V ~ и, если р"" > Ля, где

Р™ = (ргМ.....• (Р1(и).....рк(и)(и)) ,

О < Лх < 1 - фиксированное число (параметр).

Пространственная модель:

- Каждый узел V 6 V перемещается в пределах фиксированной области И (у).

- сНат^О?) < гтах, где гтах - максимальное расстояние, на котором возможна связь.

32

- Считаем v~u, если Я (О", О") < • гтах, Лж > 0, где Н -метрика Хаусдорфа.

Для данной модели возможны два усиления:

- Если каждый в качестве узла V рассматривать ансамбль узлов и = {-1Г(}, I = 1, заполняющих область О(г>) равномерно, то для связи между узлами V и и достаточно пересечения области О (г) с дилатацией О (и) + гтах.

- Если узлы каждого ансамбля образуют связную подсеть, то ограничение на размер области можно ослабить: В (и) с {с2;(0} + гтах> гДе ^¿(0 - положение узла в момент 1.

Модель согласованного движения:

- Положение узла V € V задается многомерной случайной величиной Xй. В двумерном случае Ху = (Х^ХЦ).

- Узлы расположены равномерно относительно центра: = 0.

- Ж-отношение: v~u, если М(\Х" - Хи\2) < г2; при М(.(Х^2 + (Х%)2) = 1 это условие сводится к ст2( 1 — р"") < 0.5(гтадг)2, где рии = (з™ + в2й - корелляция векторов Хр, Xй (среднее значение ¿Х"Хи), а ~ гтах/г ~ характеристика удаленности от центра.

Модель хаотичного движения:

- Положение узла V 6 V задается суммой случайных векторов УС = 2" + Х»° =шЧ гк0 + Х»°, где М(г"°) = М(Х*°) = О, т" - константный вектор («реперная точка»).

- Анализируется величина/ги = М(Р(|Я"и| < гтал.)).

- Выводится формула расчета Ж-отношения для случая, когда Я"0 и Xго независимы в совокупности, 2"° - равномерно распределены с дисперсией 52, Хр0 - равномерно распределены с дисперсией о2:

Г™ = А (т, С(т, о, Я),

где Л(тп, <т,Ю = 2Ф0 (*) (ф0 (*£») + Ф0 (£=)) = /2(0)/! (т),

= ^ + ®г, т = М(Я? - г?), Я = гтах, Ф0(г) = £е-Т(1х .

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

Базовый алгоритм состоит из четырех функциональных блоков:

ФБ1 - Измерение и оценка сетевых параметров.

ФБ2 - Расчет маршрутных таблиц (на основе метода рельефов).

ФБЗ - Способ рассылки служебной информации.

ФБ4 - Реализация маршрутных решений для доведения пакета, т.е. способ использования маршрутных таблиц.

Обобщенная диаграмма состояний узла, исполняющего алгоритм, приведена на рис. 2.

Рис. 2. Диаграмма состояний алгоритма -маршрутизации.

Здесь используются следующие обозначения: ^ - начальное состояние «ожидание», 52 - «расчет 72-связи», S3 - «вычисление таблицы маршрутизации», Б4 - «обработка (пересылка) пользовательского пакета». Переходы между состояниями происходят в результате наступления различных событий, при этом может вызываться некоторая процедура. Событие Е 1.1 означает обнаружение соседнего узла V!', £1.2 - завершение расчета ^-отношения; Е2.1 - обнаружение обрыва связи, £2.2 - получение служебного сообщения М1 (изменение таблицы соседнего узла); Е2.3 -изменение текущей маршрутной таблицы, £3.1 - получение сообщения М2 (активации зарегистрированной связи); £4.1 -получение (или генерация) пользовательского пакета.

Процедура Л 1.1 производит идентификацию 32-связи и вычисление весов; А1.2 пополняет список смежности; А2.1 инвертирует текущее состояние связи; Л2.2 - перерасчет маршрутной таблицы; А2.3 - генерация и рассылка корректирующих сообщений М1; Л4.1 -выбор маршрута и пересылка пакета адресату. В тексте диссертации приводится детальное описание этих процедур.

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

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

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

На текущий момент имитационное моделирование является основным средством изучения сетевых протоколов. Аналитические средства не позволяют в полной мере оценить количественные характеристики механизмов функционирования сетевой инфраструктуры. Это тем более справедливо для высокодинамичных сетей МАКЕТ, где топология меняется непредсказуемо и с большой скоростью. Исследование при помощи специально созданных программ, имитирующих работу сети, позволяет получить результаты, сравнимые по достоверности с моделированием на реальном оборудовании. Однако подобные инструменты обладают несравнимо большей доступностью и гибкостью.

Использованный в работе сетевой симулятор был создан на основе специализированной библиотеки РеегБип (http://sourceforge.net/projects/ РеегБга). Она представляет собой набор java-клaccoв с открытым исходным кодом для построения симуляторов одноранговых сетей. Инфраструктура РеегБип предоставляет базовые средства генерации и модификации графов сетевой топологии, создания модульного стека протоколов, управления имитационным процессом, конфигурирования и вывода результатов. Благодаря этому можно сосредоточиться на реализации логики исследуемых алгоритмов, а не технических средств их функционирования.

В симуляторе были реализованы четыре уровня сетевого взаимодействия эталонной модели 0Б1: физический, канальный, сетевой и прикладной. На сетевом уровне для сравнительного анализа используются следующие концепции алгоритмов маршрутизации: а) лавинная рассылка; б) реактивная маршрутизация - представлена кэширующим протоколом маршрутизации по требованию, выполняющему поиск новых маршрутов согласно алгоритму АОБУ; в) 32-маршрутизация.

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

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

Отличительной чертой алгоритма 32-маршрутизации является его вероятностная природа. Это означает, что пользовательские пакеты доставляются до адресата не гарантировано, а с некоторой вероятностью IV. Эта важнейшая характеристика напрямую зависит от «качества» выбора ^-отношения и может быть определена экспериментально: IV = Мусп/М. Здесь Мусп - число успешно доставленных сообщений, М - число всех отправленных сообщений. Тогда (1 — и')М - число сообщений, которые не будут доставлены. Понятно, что для них требуется применять другую тактику маршрутизации, потенциально более затратную. Именно этот трафик и будет избыточным для такого алгоритма.

В работе выводится аналитическая оценка объема избыточного трафика в сравнении с тем же показателем проактивного алгоритма. Преимущество ^-маршрутизации определяется следующим соотношением:

_ ^ 2аД10

а ^ ;-

1 - IV

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

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

В первом случае исходным параметром являлось общее число всех состояний т. Для них определялась булева матрица совместимости С = {су},1>/ = 1<ш. Элемент матрицы с^ принимает значение 1, если состояния Я; и 5] совместимы. Очевидно, Сц = с^ и сц = 1. Таким образом, матрица С фактически задает псевдограф совместимости состояний. В начале каждого эксперимента этот граф генерировался случайным образом. Затем производилось назначение состояний узлам. Для каждого из N узлов в произвольном порядке выбиралось И. состояний, и им

приписывались фиксированные значения вероятностей р1( ...,р/,. После этого все узлы рассматривались попарно и для них рассчитывалась вероятность связи f. Если она превосходила пороговое значение /*, то узлы считались соединенными ^-связью. Полученный таким образом 32-граф используется для формирования маршрутных таблиц. В процессе прогонки на каждом шаге разыгрываются (с соответствующими вероятностями) текущие состояния узлов. По матрице С определяется их совместимость, в результате чего формируется текущая топология сети. По ней производится тестирование маршрутизации.

Значения параметров моделирования приведены в таблице 1.

Таблица 1. Параметры модели «конечных состояний».

Параметр Обозначение Значение

Число узлов N 20

Общее число состояний т 5-10-15

Число разрешенных состояний узла К 2-3

Вероятности состояний Р1.Р2.Р3 0.1 н- 0.5

Пороговая величина вероятности для 32-связи Г 0.2 -г 0.8

Максимальная метрика (длина) маршрута V 4

Количество розыгрышей позиции (шагов М 100

прогонки)

Число и интенсивность генерации сообщений к,р 10,0.7

узлом

Число экспериментов для одинакового набора К 10

параметров

В модели хаотичного движения имитировалась сеть, состоящая из движущихся вблизи «центров» узлов. Положение центров задавалось точками на плоскости. Граф текущей топологии рассчитывался по евклидовой метрике исходя из условия, что расстояние между узлами не превосходит максимального радиуса действия связи. Моделирование производилось для двух конфигураций сети: регулярной (квадратная решетка) и случайной (в круговой области). Заданное число N точек размещались в соответствующей области так, чтобы обеспечить требуемую плотность р. Для регулярной структуры область размещения представляла собой квадрат [0,£>] х [0,0], где О — ^М/р. Точки располагались в узлах прямоугольной сетки с шагом cí = у/1/р. Для нерегулярной структуры область представляла собой круг с радиусом О = у/Ы/лр и центром в начале координат. Точки располагались случайным образом так, чтобы обеспечить равномерное заполнение области.

Параметры моделирования приведены в таблице 2.

Таблица 2. Параметры модели хаотичного движения.

Параметр Обозначение Регулярная Нерегулярная

сеть сеть

Число узлов N 49 49

Плотность размещения центров Р 2.87 3.15

Дальность связи гша* 1.0 1.0

Максимальная метрика (длина) маршрута V 4 4

Количество розыгрышей позиции (шагов M 100 100

прогонки)

Активность узлов ст 0-0.5 0-0.5

Пороговая величина вероятности для Л- г 0.7 0.7

связи

Число и интенсивность генерации к,р 10, 0.7 10, 0.7

сообщений узлом

Число экспериментов для одинакового К 5 5

набора параметров

На рис. 3 и рис. 4 проиллюстрированы некоторые результаты экспериментов. Анализ графиков показывает, что удовлетворительные показатели эффективности достигаются там, где связность 3?-графа достаточно сильная. Для модели конечных состояний рекомендуемый показатель порога /* < 0.4, для модели хаотичного движения - f < 0.5. Вне этих пределов наблюдается резкое падение доли успешно доставленных сообщений, в то время как внутри них разброс значений укладывается в рамки погрешности. Важным заключением является тот факт, что общее количество состояний (m) практически не сказывается на работе алгоритма. Напротив, в модели хаотичного движения эффективность линейно зависит от «активности» смещения узлов а.

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

100% 904 80% 70% 604 -* 504 404 30% 20% 10% • оч :

0.2 0.3 0,4 0.5 0,6 0.7 0,8

—<•«0.5

0.05 ОД 0,15 0.2 0,25 0.3 0,35 0.4 0,45 0.5

Рис. 3. Эффективность доведения. Модель конечных состояний (слева) и модель хаотичного движения (справа).

0,3 0.4 0.5 0,в 0,7 0,8 I*

> И-адюригм -»-Проомиенмй алгоритм Ре.

.05 0,1 0.15 0.2 О,« 0.5 0,35 0,4 0.4* 05

Рнс. 4. Удельные избыточные затраты на поиск одного маршрута.

Модель конечных состояний (слева) и модель хаотичного движения (справа).

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

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

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

рассылку. Топология сети при этом может меняться (включение/выключение узлов или каналов), с условием сохранения хотя бы одного возможного пути доставки (связности).

Используемая лабораторная установка представляла собой совокупность программно-аппаратных средств, при помощи которых организовывалась беспроводная неструктурированная сеть. В экспериментах было использовано до 10 различных устройств, оснащенных беспроводными интерфейсами. В качестве беспроводных средств связи применялись доступные на текущий момент в продаже сетевые адаптеры стандарта Bluetooth (IEEE 802.15.1) и Wi-Fi (ШЕЕ 802.11). Из 10 устройств 7 представляли собой стационарные персональные компьютеры на базе платформы Intel х86. Они оснащались Bluetooth-адаптерами Trendnet TBW-102UB и Wi-Fi-адаптерами DLink DWL-G520. Остальные 3 устройства являлись переносными компьютеры х86 с встроенными Bluetooth-адаптерами Tekram, Jabra и MSI и Wi-Fi-адаптерами DLink DWL-G122 и MSI со сходными техническими характеристиками. Все указанные компьютеры работали под управлением операционных систем Microsoft Windows Vista и Microsoft Windows XP SP2.

На текущий момент проблема интеграции разнообразных стандартов беспроводной связи приобретает немаловажное значение. В связи с этим управляющее программное обеспечение для узла макетной сети было разработано с учетом унифицированной архитектуры стека протоколов. Фактически, была реализована библиотека, предоставляющая Java-интерфейс взаимодействия для систем Windows XP/Vista. С ее помощью можно создавать кросс-платформенные сетевые приложения, интегрирующие технологии Wi-Fi и Bluetooth. Сеть может содержать произвольное число узлов, каждый из которых должен иметь устройство одного из стандартов. Если в сети присутствуют и те и другие устройства, хотя бы один узел должен поддерживать оба стандарта для обеспечения взаимодействия двух подсетей. При подключении узлы производят поиск и автоматически устанавливают соединение со всеми доступными соседними узлами. В результате образуется одноранговая сеть произвольной структуры. Некоторые узлы в ходе работы могут выключаться или выходить из зоны досягаемости, что не сказывается на функционировании остальной сети (при сохранении связности топологии) благодаря избыточным таблицам маршрутизации. Прикладной уровень представлен простейшими версиями протоколов обмена файлами и текстовыми сообщениями.

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

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

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

3. Установление связей с доступными узлами.

4. Обмен накопленной информацией о топологии.

5. Формирование на основе информации о топологии сети правил для маршрутизации информации в сети.

6. Маршрутизация пакетов данных в сети на основе сформированных правил.

7. Сбор статистики передачи данных в сети,

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

Для проведения лабораторных испытаний из имеющихся устройств была организована беспроводная сеть, граф которой представлен на рис. 5. Эксперимент проводился в три этапа: подключение устройств, формирование маршрутных таблиц и тестирование маршрутизации путем имитации разрывов маршрутов в процессе передачи данных. В данном случае проверялась надежность доставки из узла 1 (источник) до узла 7 (адресат).

¿К Ж о

оС" ! |

^'(к. Л ........'

Рис. 5. Топология макетной сети.

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

В заключении формулируются основные результаты, полученные в работе:

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

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

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

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

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

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

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

1. Голубев, A.C. Повышение эффективности дистанционно-векторной маршрутизации в быстро изменяющихся сетях / A.C. Голубев // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. — СПб, 2007. — № 4, —Т. 2.— С. 41-45.

2. Голубев, A.C. Разработка гибридного алгоритма маршрутизации в динамических сетях произвольной структуры / A.C. Голубев, P.A., Батаев, С.М. Аракелян // Труды XIV Всероссийской научно-методической конференции Телематика'2007. — СПб., 2007. — с. 268269. — ISBN 5-7577-0329-6.

3. Батаев, P.A. Вероятностный подход при создании алгоритмов маршрутизации в сетях с изменяющейся топологией / P.A. Батаев, A.C. Голубев // Труды XIV Всероссийской научно-методической конференции Телематика'2007. — СПб., 2007. — с. 267-268. — ISBN 57577-0329-6.

4. Голубев, A.C. Организация образовательного процесса на основе децентрализованной распределенной системы / A.C. Голубев, О.Н.Позднякова, C.B. Рощин // Инновационные технологии обучения: проблемы и перспективы. Сборник научных трудов Всероссийской научно-методической конференции. — Липецк, 2008. — С. 13-15.

5. Рощин, C.B. Применение технологий пиринговых сетей с децентрализованным управлением для формирования единого информационно-образовательного пространства в интернет / C.B. Рощин, A.C. Голубев, Т.Е. Овчинникова // XV конференция представителей региональных научно-образовательных сетей «RELARN-2008». — Н.Новгород, 2008.

6. Июгин, Н.А, Децентрализованная распределенная информационная система взаимодействия медицинских учреждений / H.A. Июгин, A.C. Голубев, C.B. Рощин // VIII Международная научно-техническая конференция «Физика и радиоэлектроника в медицине и экологии» ФРЭМЭ'2008. Доклады. — Владимир, 2008. — Кн.1. — С. 323-325.

7. Абрахин, С.И. Типовая геоинформационная система / С.И. Абрахин, A.C. Голубев, Д.П. Троицкий // Труды XIV Всероссийской научно-методической конференции Телематика'2007 / Санкт-Петербургский государственный университет информационных технологий, механики и оптики — СПб, 2007 — С. 271-272.

Подписано в печать 24.11.08 Формат 60x84/16. Усл. печ. л. 1,16. Тираж 100 экз. Заказ Издательство Владимирского государственного университета. 600000, Владимир, ул.Горького, 87.

Оглавление.

Введение.

Глава I. Сети MANET.

1.1. Тенденции развития программно-аппаратных средств мобильных сетей.

1.2. Сети MANET: проблемы и возможности.

1.3. Классификация алгоритмов маршрутизации.

1.4. Обзор маршрутизирующих протоколов MANET.

1.4.1. Destination-Sequenced Distance-Vector Routing (DSDV).

1.4.2. Optimized Link State Routing Protocol (OLSR).

1.4.3. Topology broadcast based on reverse-path forwarding (TBRPF).

1.4.4. Ad hoc On-Demand Distance Vector (AODV).

1.4.5. Dynamic Source Routing (DSR).

1.4.6. Temporally-Ordered Routing Algorithm (TORA).

1.4.7. Zone Routing Protocol (ZRP).

1.4.8. Hazy-Sighted Link State Routing Protocol (HSLS).

1.5. Сравнительная характеристика.

1.6. Маршрутизация в самоорганизующихся МО-сетях.

1.7. Выводы по главе.

Глава II. Разработка метода маршрутизации на основе структурной особенности сети.

2.1.1. Область применения.

2.2. Математическая модель.

2.2.1. Общие положения.

2.2.2. п-окрестность.

2.2.3. R-отношение.

2.2.4. Возможные приложения.

2.3. Алгоритм R-маршрутизации.

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

2.3.2. Базовый алгоритм.

2.3.3. Модификации.

2.4. Выводы по главе.

Глава III. Экспериментальное тестирование.

3.1. Имитационное моделирование сетевой среды.

3.2. Программная модель (симулятор).

3.2.1. Библиотека PeerSim.

3.2.2. Структура имитационной модели.

3.3. Тестирование алгоритма маршрутизации.

3.3.1. Исследование R-отношения.

3.3.2. Исследование параметров.

3.4. Выводы по главе.

Глава IV. Макетная реализация.

4.1. Цели и задачи.

4.2. Лабораторный стенд.

4.2.1. Аппаратное обеспечение.

4.2.2. Программное обеспечение.

4.3. Проведение испытаний.

4.3.1. Подключение устройств.

4.3.2. Формирование маршрутных таблиц.

4.3.3. Имитация разрывов маршрутов при передаче данных.

4.4. Выводы по главе.

Предмет исследования

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

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

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

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

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

Цель и задачи исследования

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

В ходе работы решались следующие задачи:

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

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

• Разработка формального математического описания данных структурных особенностей.

• Выработка рекомендаций применения данного описания, на примерах некоторых моделей мобильных сетей.

• Разработка алгоритма маршрутизации, использующего структурные особенности сети.

• Имитационное моделирование алгоритма с целью проверки его эффективности и исследования области применимости.

• Макетная реализация разработанного алгоритма с использованием реального сетевого оборудования и его лабораторное испытание.

Методы исследования

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

Научная новизна

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

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

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

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

Практическая ценность и реализация результатов

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

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

Апробация работы

Основные результаты работы докладывались и экспонировались на следующих научно-технических совещаниях и конференциях:

• Международная конференция «Телекоммуникационные и информационные системы», Санкт-Петербург, 2007 г.

• Международный форум по проблемам науки, техники и образования, Москва, 04-12 декабря 2007 г.

• XIV Всероссийская научно-методическая конференция «Телематика-2007», Санкт-Петербург, 18-21 июня 2007 г.

• VIII Международная научно-техническая конференция «Физика и радиоэлектроника в медицине и экологии» ФРЭМЭ'2008, Владимир, 02-04 июля 2008.

• Международная научно-техническая конференция «Перспективные технологии в средствах передачи информации», Владимир, 10-12 ноября 2007 г.

• Выставка-ярмарка «Современная образовательная среда», Москва, ВВЦ 03.10-06 ноября 2007 г.

• Всероссийская научно-методическая конференция «Инновационные технологии обучения: проблемы и перспективы», Липецк, 29-30 марта 2008.

• XV конференция представителей региональных научно-образовательных сетей «RELARN-2008», Н.Новгород, 01-08 июня 2008.

Положения, выносимые на защиту

Основные научные результаты диссертации, выносимые на защиту, заключаются в следующем:

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

2. Предложена математическая модель структурных особенностей мобильной сети.

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

Публикации

Основные результаты работы представлены в 7 публикациях, в том числе 1 статье в журнале из перечня ВАК, а также в научно-технических отчетах НИР, выполненных по заданию Рособразования и Роснауки.

Объем и структура диссертации

Текст диссертационной работы изложен на 141 стр. машинописного текста. Содержательная часть включает введение, четыре главы и заключение. Список использованных источников содержит 96 наименований. Таблиц 11, рисунков 42.

4.4. Выводы по главе

1. Продемонстрирована возможность практической реализации беспроводной одноранговой сети на базе технических средств ОС Windows и платформы Java.

2. Протестированы разработанные механизмы взаимодействия сетей различных беспроводных стандартов.

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

4. Выявлены недостатки алгоритма маршрутизации и возможности его дальнейшего совершенствования. Реализованы модификации алгоритма, направленные на повышение его устойчивости к разрывам маршрутов.

Заключение

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

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

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

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

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

4. Проведено экспериментальное исследование алгоритма при помощи разработанной программной модели сетевой среды. Выявлены наиболее значимые характеристики, определяющие его эффективность и область применения.

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

1. Шамин, П.Ю. Многоцелевая маршрутизация в самоорганизующихся сетях с ограниченной мобильностью: дис. . канд. тех. наук: 05.12.13 /Павел Юрьевич Шамин. — Владимир, 2008. — 172 с.

2. Шварц, М. Сети связи: протоколы, моделирование и анализ. В 2 ч. Ч. 1: Пер с англ. / М. Шварц — М.: Наука, 1992. — 336 с.

3. Аничкин, С.А. Протоколы информационно-вычислительных сетей: Справочник / С.А. Аничкин, С.А Белов, А.В. Бернштейн А.В. и др.; под ред. И.А. Мизина, А.П. Кулешова А.П. —М.: Радио и связь, 1990. — 504 с.

4. Мизин, И.А. Сети коммутации пакетов / И.А. Мизин, В.А, Богатырёв, А. П. Кулешов. — М.: Радио и связь, 1986. — 407 с.

5. Олифер, В.Г. Компьютерные сети. Принципы, технологии, протоколы: Учебник для вузов / В.Г. Олифер, Н.А. Олифер. — 2-е изд. — СПб.: Питер, 2006. — 958 с.

6. Флинт, Д. Локальные сети ЭВМ: архитектура, принципы построения, реализация: Пер. с англ. / Д. Флинт. — М.: Финансы и статистика, 1986. — 359 с.

7. Танненбаум, Э. Компьютерные сети / Э. Танненбаум. — 4-е изд. — СПб.: Питер, 2003. —992 с.

8. Зайцев, С.С. Транспортировка данных в сетях ЭВМ / С.С. Зайцев. — М.: Радио и связь, 1985. — 125 с.

9. Дэвис, Д. Вычислительные сети и сетевые протоколы / Д. Дэвис, Д. Барбер, У. Прайс, С. Соломонидес: Пер с англ. —М.: Мир, 1982. — 564 с.

10. Столлингс, В. Передача данных / В. Столлингс. — 4-е изд. — СПб.: Питер, 2004. — 752 с.

11. Богуславский, JI. Б. Управление потоками данных в сетях ЭВМ / Л.Б. Богуславский. — М.: Энергоатомиздат, 1984. — 168 с.

12. Семенов, Ю.А. Телекоммуникационные технологии Электронный ресурс. / Ю.А. Семенов. — Режим доступа: http://book.itep.ru/.

13. Лазарев, В. Г. Динамическое управление потоками информации в сетях связи / В.Г. Лазарев, Ю.В. Лазарев. — М.: Радио и связь, 1983. — 216 с.

14. Фродрих, М. Мобильные сети произвольной структуры искусство сетевизации без сетей / М.Фродих, П.Иоханссон, П.Ларсон // Мобильные телекоммуникации. — 2001. — №5. — С.49-55.

15. Разгуляев, Л. Перспективные мобильные адаптивные сети передачи информации для СВ США / Л. Разгуляев // Зарубежное военное обозрение.2008. — №1. — С. 35-39.

16. Бекетов, О. Беспроводные сети MESH Электронный ресурс. / О. Бекетов.

17. Режим доступа: http://www.planet.com.ru/upload/ll 162990815.pdf.

18. Kim, D. К. A New Mobile Environment: Mobile Ad Hoc Networks (MANET) / D.K. Kim // IEEE Vehic. Tech. Soc. News — August 2003. — P. 29-35.

19. Baker, F. An outsider's view of МАКЕТЭлектронный ресурс.: Internet Engineering Task Force document / F. Baker. — 17 March 2002. — Режим доступа: http://w3.antd.nist.gov/wctg/manet/draft-baker-manet-review-01 .txt.

20. Perkins, С. E. Ad Hoc Networking / С. E. Perkins. — New York: Addison-Wesley, 2001.

21. Ilyas, M. The Handbook of Ad Hoc Wireless Networks / edited by Mohammad Ilyas. — CRC Press LLC, 2003. — 559 p.

22. Basagni, S. Mobile Ad Hoc Networking / S. Basagni, M. Conti, I. Stojmenovic, S. Giordano. — IEEE Press, 2004. — 480 p.

23. Milanovic, N. Routing and Security in Mobile Ad Hoc Networks / Nikola Milanovic, Miroslav Malek, Anthony Davidson, Veljko Milutinovic // Computer, 2004. — Vol. 37, N 2.

24. Mohapatra, P. Group Communications in Mobile Ad Hoc Networks / (Prasant Mohapatra, Chao Gui, Jian Li // Computer, 2004. — Vol. 37, N 2.

25. Akyildiz, I.F. A Survey on Sensor Networks /1. F. Akyildiz et al. // IEEE Communications Magazine. — August 2002. —pp. 102-114.

26. Carle ,J. Energy-Efficient Area Monitoring for Sensor Networks / Jean Carle, David Simplot-Ryl // Computer, 2004. — Vol. 37, N 2.

27. Денисьева, О.М. Средства связи для «последней мили» / О.М. Денисьева, Д.Г. Мирошников. — 2-е изд. — М.: Эко-Трендз, 1999. — 137с.

28. Johanson, P. Bluetooth: An Enabler for Personal Area Networking / P. Johanson, M. Kazantzidis, R. Kapoor, M. Gerla // IEEE Network Magazine.- Sept. — Oct. 2001. —Vol. 15.—P. 28 — 37.

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

30. Royer, E.M. A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks / E. M. Royer and C.-K. Toh // IEEE Personal Communications. — April 1999. — P. 46 — 55.

31. Iwata, A. Scalable Routing Strategies for Ad-hoc Wireless Networks / A. Iwata, C.C. Chiang, G. Pei, M. Gerla, and T.-W. Chen // IEEE Journal on Selected Areas in Communications. — Aug. 1999. — P. 1369-1379.

32. Пряхин, В. Безопасность маршрутизации в беспроводных Ad Нос сетях. Протоколы SRP, ARAN Электронный ресурс. / В. Пряхин. — Режим доступа: http://www.re.mipt.ru/infsec/2004/essay/2004Securerouting inwirelessadhocnetworksSRPARANProtocolsPryakhin.pdf.

33. Лысенко, А.Г. Система обнаружения вторжений для мобильной сети / А.Г. Лысенко, А.Ю. Шевёлкин // XIV Всероссийская научная конференция. Проблемы информационной безопасности в системе высшей школы. — М: МИФИ, 2007 — С. 85-87.

34. Nie, P. Security in Ad hoc Network Электронный ресурс./ Pin Nie. — Режим доступа: http://www.tcs.hut. fi/Studies/T-79.7001/2007SPR/niepaperdraft.pdf.

35. Pei, G. Fisheye State Routing: A Routing Scheme for Ad Hoc Wireless Networks / G. Pei, M. Gerla, T.-W. Chen // Proceedings of ICC 2000. — NewOrleans, LA, June 2000.

36. Jacquet, P. Optimized Link State Routing Protocol for Ad Hoc Networks / P. Jacquet et al. // Proc. IEEE Int'l MultiTopic Conf., 2001. — IEEE Press, 2001. — P. 62-68.

37. Bellurand, B. A Reliable, Efficient Topology Broadcast Protocol for Dynamic Networks / B. Bellurand, R.G. Ogier // Proc. IEEE INFOCOM'99 . — New York, March 1999.

38. Ogier, R.G. Topology Dissemination Based on Reverse-Path Forwarding (TBRPF) Электронный ресурс./ R. Ogier, F. Templin, M. Lewis. — IETF

39. Manets Working Group InternetDraft, 14 Oct. 2003. —Режим доступа: Ьйр://у\^^ле1£ог^1п1егпе^с1гаЙ8/с1гаА;-1е1^шапеМЬф^11 .txt.

40. Perkins, C.E. Ad-hoc On-Demand Distance Vector Routing / С. E. Perkins, E. M. Royer // Proc. 2nd IEEE Wksp. Mobile Сотр. Sys. and Apps. — Feb. 1999.1. P. 90-100.

41. Johnson, D.B. Dynamic Source Routing in Ad-Hoc Wireless Networks / D.B. Johnson, D.A. Maltz // Mobile Computing / T. Imielinski, H. Korth. — Eds. Kluwer, 1996. — P. 153-181.

42. Corson, M.S. A Distributed Routing Algorithm for Mobile Wireless Networks / M. Scott Corson, Anthony Ephremides // Wireless Networks. — 1995. — Vol. 1, №1 —P. 61-81.

43. Corson, M.S. A Lightweight Adaptive Multicast Algorithm /M.S. Corson, L. Ji // Proc. GLOBECOM '98. — Nov. 1998. — P. 1036-1042.

44. Park, V.D. A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks / V.D. Park, S.M. Corson // Proceedings of the INFOCOM'97. — Kobe, Japan, 1997. — P. 1405 — 1413.

45. Perkins, C.E. Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers / С. E. Perkins and P. Bhagwat // Сотр. Commun. Rev. — Oct. 1994. — P. 234-244.

46. Moy J. OSPF Version 2 / J. Moy // Internet RFC 1583 .— Proteon, Inc., March 1994.

47. Chiang C.-C. Routing in Clustered Multihop, Mobile Wireless Networks with Fading Channel / C.-C. Chiang // Proc. IEEE SICON '97. — Apr. 1997. — P. 197-211.

48. Pei, G. A Wireless Hierarchical Routing Protocol with Group Mobility / G. Pei, M. Gerla, X. Hong, C.-C. Chiang // Proceedings of IEEE WCNC'99. — New Orleans, LA, Sept. 1999.

49. Haas, Z.J. The Performance of Query Control Schemes for the Zone Routing Protocol / Z.J. Haas, M.R. Pearlman // ACM/IEEE Transactions on Networking.vol.9, no.4. — August, 2001. — P.427-438.

50. Haas, Z.J. The Zone Routing Protocol (ZRP) for Ad Hoc Networks Электронный ресурс.: Internet Draft / Zygmunt J. Haas, Marc R. Pearlman,136

51. Prince Samar. — July 2002. — Режим доступа: http://www.ietf.org/ proceedings/02nov/I-D/draft-ietf-manet-zone-zrp-04.txt.

52. Pei, G. LANMAR: Landmark Routing for Large Scale Wireless Ad Hoc Networks with Group Mobility / G. Pei, M. Gerla, X. Hong // Proceedings of IEEE/ACM MobiHOC 2000 — Boston, MA, Aug. 2000. — P. 11-18.

53. Navas, J.C. Geographic Addressing and Routing / J.C. Navas, T. Imielinski //Proc. Of the Third ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom'97). — Budapest, September 26-30, 1997.

54. Ко, Y.B. Location-Aided Routing (LAR) in Mobile Ad Hoc Networks / Y.B. Ко, N.H. Vaidya // Proc. ACM/IEEE International Conference on Mobile Computing and Networking (MobiCOM '98). — Oct. 1998. — P.66-75.

55. Basagni, S. A Distance Routing Effect Algorithm for Mobility (DREAM) / S. Basagni, I. Chlamtac, V. R. Syrotiuk, B. A. Woodward // Proc. ACM/IEEE International Conference on Mobile Computing and Networking (MobiCOM '98). —Oct. 1998. —P.76-84.

56. Routing Information Protocol Электронный ресурс. // Internet RFC 1058. — June, 1988. —Режим доступа: http://tools.ietf.org/html/rfcl058.

57. Mtibaa, A. MMDV: Multipath and MPR based AODV routing protocol / A. Mtibaa, F. Kamoun // Proceedings of Med-Hoc-Net. — Lipari, Italy, May 2006. — P.137-144.

58. Gwalani, S. AODV-PA: AODV with Path Accumulation / S. Gwalani, E.M. Belding-Royer, C.E. Perkins // IEEE International Conference on Communications. — 2003. — Vol 1. — P. 527-531.

59. Hu, Y.-C. Ariadne: A secure on-demand routing protocol for ad hoc networks / Hu, Y. C., Perrig, A., Johnson, D. B. // Proceedings of the eighth Annual International Conference on Mobile Computing and Networking (MobiCom 2002). — Sept, 2002. — P. 12-23.

60. Santivanez, С. Hazy Sighted Link State (HSLS) Routing: A Scalable Link State Algorithm: BBN Technical Memo: BBN-TM-I30I / C. Santivanez, R. Ramanathan. — BBN Technologies, Cambridge, Mass., Aug. 2001.

61. Rangarajan, H. On-demand loop-free routing in ad hoc networks using source sequence numbers / H. Rangarajan, H., J J. Garcia-Luna-Aceves // Mobile Adhoc and Sensor Systems Conference, 2005, IEEE International Conference on 7 — 10 Nov. 2005. —2005.

62. Park, V.D. A Performance Comparison of the Temporally-Ordered Routing Algorithm and Ideal Link-State Routing / V.D. Park, S.M. Corson // Proceedings of the Third IEEE Symposium on Computers & Communications. — Washington, DC, USA, 1998. — P. 592 — 598.

63. Sarshar, N. Percolation search in power law networks: Making unstructured peer-to-peer networks scalable / Nima Sarshar // in Proc. of IEEE Peer-to-Peer Computing. — IEEE Computer Society, 2004. — P. 2-9.

64. Camp, T. Mobility Models for Ad Hoc Network Simulations / T. Camp, et al. // Wireless Comm. and Mobile Computing (WCMC), special issue on mobile ad hoc networking. — 2002. — Vol. 2, № 5. — P. 483 — 502.

65. Boudec, J.-Y. Perfect simulation and stationarity of a class of mobility models / J.-Y. Le Boudec, M. Vojnovic // Proc. IEEE INFOCOM 2005. — Miami, FL, Mar. 2005.

66. Sridhara, V. Realistic Simulation of Urban Mesh Networks Part II: Urban Propagation / V. Sridhara and S. Bohacek // U. Delaware Technical Report. — 2006.

67. Харари, Ф. Теория графов: пер. с англ. / Ф. Харари. — М.: Мир, 1973. — 297 с.

68. Асанов, М.О. Дискретная математика: графы, матроиды, алгоритмы / М.О. Асанов, В.А. Баранский, В.В. Расин. — Ижевск: ННЦ «Регулярная и хаотическая динамика», 2001. — 288 с.

69. Вентцель, Е.С. Теория случайных процессов и её инженерные приложения: Учеб. пособие для студ. втузов. / Е.С. Вентцель, JI.A. Овчаров. — Изд. 3-е, перераб. и доп. —М.: Издательский центр «Академия», 2003. — 432 с.

70. Севастьянов, Б.А. Курс теории вероятностей и математической статистики / Б.А. Севастьянов. — М.: Наука, 1982. — 244 с.

71. Булинский, А.В. Теория случайных процессов / А.В. Булинский, А.Н. Ширяев. — М.: ФИЗМАТЛИТ, 2005. — 408 с.

72. Гмурман, В.Е. Теория вероятности и математическая статистика: Учеб. пособие для вузов / В.Е. Гмурман. — Изд. 4-е, доп. — М.: Высшая школа, 1972. —368 с.

73. Вишневский, В.М. Теоретические основы проектирования компьютерных сетей / В.М. Вишневский. — М.: Техносфера, 2003. — 512 с.

74. Захаров Г.П. Методы исследования сетей передачи данных. / — М.: Радио и связь, 1982. 208 с.

75. Суворов, Д.В. Математическое моделирование неоднородных интегральных систем передачи информации / Д.В. Суворов // Системы управления и информационные технологии. Москва — Воронеж: Научная книга, 2003. — № 1-2 (12). — с. 82- 85.

76. Гайнулин, А.Г. Моделирование алгоритма маршрутизации передаваемых данных в беспроводных сетях со смешанными типами коммутации / А.Г. Гайнулин // Вестник Нижегородского университета им. Н.И. Лобачевского, 2008, — № 1, — с. 93—99.

77. Назаров, А.А. Исследование компьютерных сетей связи с протоколами случайного множественного доступа / А.А. Назаров // Вестник Томского государственного университета, 2000. — №6 (271).

78. Алексеев И.В. Адаптивная схема управления потоком для транспортного протокола в сетях с коммутацией пакетов: дис. . канд. ф.-м. наук: 05.13.17 / Алексеев Игорь Вадимович. —Ярославль, 2000. — 141 с.

79. Стерне, Т. Учимся моделировать / Т. Стерне //Сети. 1998 —№5. —с.130-135.

80. Tang, S. Modeling and Evaluation of Traffic Flow and Availability for Mobile Ad Hoc Networks / S. Tang, et al. // Proc. WCNC 2006, paper NET16-4.

81. Holzmann, C. A Theory for Protocol Validation. / C. Holzmann // IEEE Transactions on Computers, 1982. — Vol. C-31, N. 8. — P. 730-738.

82. An Improved Protocol Reachability Analysis Technique. // Software, Practice and Experience, 1988, —Vol. 18, N. 2.—P. 137-161.

83. Bajaj, S. Improving Simulation for Network Research. / Bajaj S., Breslau L., Estrin D., Fall K., Floyd S. // Technical Report 99-702. / University of Southern California. —March 1999.

84. Fall, K. Network Emulation in the Vint/NS Simulator / K. Fall // Proc. of ISCC'99. — 1999.

85. Батаев, Р.А. Вероятностный подход в создании алгоритмов маршрутизации в сетях с изменяющейся топологией / Р.А. Батаев // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. — 2007.—№ 4. —Т. 2. — С. 37-41.