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

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

Тухтамирзаев Адхам Юлбарсмирзаевич

КРИТИЧЕСКИЕ РЕЖИМЫ РАБОТЫ ТЕЛЕКОММУНИКАЦИОННОЙ СЕТИ И АЛГОРИТМЫ МАРШРУТИЗАЦИИ

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

Автореферат

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

1 и яка гт

Владимир 2012

005048086

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Владимирский государственный университет имени Александра Григорьевича и Николая Григорьевича Столетовых» (ВлГУ).

Научный руководитель: доктор физико-математических наук,

профессор, заведующий кафедрой «Алгебра и геометрия» ВлГУ, Дубровин Николай Иванович

Официальные оппоненты: доктор технических наук, профессор,

заместитель директора ФГАУ ГНИИ ИТТ «Информика» Скуратов Алексей Константинович

кандидат технических наук, доцент кафедры «Управление и информатика в технических и экономических системах» ВлГУ Дерябин Вячеслав Михайлович

Ведущая организация: ФГБОУ ВПО «Ивановский

государственный энергетический университет»

Защита состоится 28 декабря 2012 года в 16 00 часов в ауд. 301-3 на заседании диссертационного совета Д 212.025.04 Владимирского государственного университета имени Александра Григорьевича и Николая Григорьевича Столетовых по адресу: 600000, Владимир, ул. Горького, 87, ВлГУ, ФРЭМТ.

Отзывы на автореферат, заверенные печатью, просим направлять по адресу: 600000, Владимир, ул. Горького, 87, ВлГУ, ФРЭМТ.

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

Автореферат разослан « 23 » ноября 2012 г.

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

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

доктор технических наук, профессор

А.Г. Самойлов

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

Актуальность темы. Наблюдаемый в последнее время повышенный интерес к беспроводным вычислительным сетям использующих радио или инфракрасные каналы привело к тому, что такие технологии передачи данных стали одним из наиболее быстро прогрессирующих направлений телекоммуникационного рынка. Таким образом, они начали постепенно вытеснять проводные сети как региональные, так и локальные. При этом одним из наиболее востребованных сегодня направлений является использование т.н. сетей MANET (Mobile Ad Hoc Network, мобильная сеть для изменяющихся ситуаций). Это самостоятельно адаптирующаяся беспроводная сеть для динамически изменяющихся ситуаций, и сеть, обладающая возможностью автоконфигурации мобильных маршрутизаторов (и связанных хостов), использующая в работе соединения по радиоканалу, объединенные в топологию произвольной формы. Они позволяют создавать децентрализованные телекоммуникационные сети произвольной топологии с элементами искусственного интеллекта. Сети MANET не используют фиксированную инфраструктуру и выбирают оптимальный маршрут для передачи трафика в условиях меняющейся конфигурации, благодаря чему их надежность очень высока. Алгоритмы, разработанные специально для решения этой задачи, получили название алгоритмов маршрутизации. Под маршрутизацией понимаем процесс определения в коммуникационной сети пути, по которому вызов, либо блок данных может достигнуть адресата. В процессе работы с такими сетями мобильные маршрутизаторы автоматически настраиваются на доступные ресурсы. Модули сети анализируют структуру трафика и адаптируют топологию системы под текущие нужды. С их помощью можно обеспечить движущуюся наземную и воздушную технику средствами связи дальнего радиуса действия, динамически подключать старые радиокомплексы. Узлы MANET самостоятельно объединяются в сеть, как только включается их питание. Кроме того, пользователи смогут динамически настраивать ширину канала связи, дальность действия сети и зону покрытия.

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

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

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

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

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

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

Реализация этой цели выполняется решением следующих задач:

- изучение и анализ условий целевой среды и специализированных алгоритмов маршрутизации;

- выявление критических режимов функционирования целевых сетей;

- формализация модели функционирования каналов передачи данных в сетевой среде;

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

- выработка предложений для совершенствования алгоритмов маршрутизации;

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

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

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

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

2. На основе разработанной модели создан принципиально новый

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

с ограниченной мобильностью, работоспособность и эффективность

которого подтверждена численными экспериментами.

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

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

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

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

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

Результаты исследований были внедрены в следующих организациях:

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

- ООО "ИНРЭКО ЛАН ФИРМА".

Личный вклад автора

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

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

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

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

— Научно-практическая конференция «Перспективы развития телекоммуникационных систем и информационные технологии», Санкт-Петербург, 2009г.

— XVII Международная конференция «Математика. Образование», Чебоксары, 24-31 мая 2009 г.

— II Всероссийская научно-практическая конференция «Инновации и информационные технологии в образовании», Липецк, 2009 г.

— XVI Всероссийская научно-методическая конференция "Телематика'2009", Санкт-Петербург, 22-25.06.2009 г.

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

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

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

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

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

Публикации

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

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

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

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

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

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

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

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

Вторая глава носит теоретический характер. Задача «огрубления» в ней ставится в чисто математической постановке. По непрерывной случайной величине требуется построить некоторую дискретную случайную величину - «огрубление»; при этом, количество её значений невелико и заранее обговорено. Дискретная случайная величина и определяет «шкалу» или разбиение диапазона изменения исходной случайной величины на классы.

Пусть М - натуральное число. М - огрублением случайных величин назовем алгоритм Г, в силу которого случайной величине О, принимающая значения на отрезке [а,Ь] с функцией распределения ^(х) ставится в соответствие дискретная случайная величина Г(О) принимающая М возможных значений ц1 < д2 < •■• < (назовем эту последовательность шкалой). Шкала есть функция алгоритма Г и случайной величины О, но она не завит от конкретных реализаций случайной величины О. Чаще всего алгоритм Г выбирается так, чтобы обеспечить минимальное отличие О от Г(£>) в смысле некоторого заданного критерия отличия К. Выбирается число М £ {1,2,3,4,5,6,7,8,9} — степень огрубления («число уровней») и число е > О - точность. Перебираем наборы из М — 1 точек а < а± < а2 < •■• < ам_г < Ь. Считаем а0 = а, ам — Ь а также считаем д,- = , £ = 1, ...,М.

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

Для заданного р > 1 сформулируем критерий Кр(р)

где ГР(х) - функция распределения случайной величины Г(0).

Случай критерия р — со.

Яау = шах^(аг) - - РСа^), I = 1,2, ...,М) ■

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

F(x)

Рис. 1. Графическое представление критерия Кр(р) при р = <х>

Случай критерия р = 1.

м / it <ч \

S = Z / [FW " F(-a^dx + / [F(ai) ~ F^dx min

' = 1 VOi-! Qi }

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

Случай критерия р — 2.

м / <ii а( \

5 = Z ( / [Пх) ~ F(ai-^2dx + / ~ Fm2dx U min

¡=1 \ai_i qi J

В общем случае оптимизация достигается итерационным методом.

Был построен алгоритм огрубления методом итераций:

1 Задаем функцию распределения у — F(x) на [0.1]

2 Задаем обратную функцию х — G (у) на [ОД]

3 Задаем натуральное число M

4 Задаем массивы q[l..M] и а[0.. М]

5 Полагаем а[0] = 0

6 Задаем начальный отрезок [qL, qR] для <?[1] (можно qL = 0,qR = 0.5)

7 Начало итераций: пока а[М] не станет 1 с заданной точностью е выполнять следующее

(*) q[l] = (qL + qR)/2

Цикл по £ от 1 до M — 1

a[i] = G(2F(q[i]-)-F(a[i-lV)

Если a[i] > 1, то qR = q[ 1] и возврат к началу итерацийС')

Иначе q[t + 1] = 2a[i] — <7Й Конец если

Если q[i + 1] > 1, то qR = £/[1] и возврат к началу итераций (*). Конец если

Конец цикла

Считаем а[М] = G(2F(q[M]) - F(jcl[M - 1])) Если a [M] > 1 + eps/2, то qR = q[l], Конец если

Если а[М\ < 1 — eps/2,то qL — q[l] Иначе стоп, выход из итераций, Конец если

Возврат к началу итераций (*)

8 Результат — полученные в итоге итераций массивы gft] и a[t]

9 Огрубленная функция распределения ГР(лг) = F(a[fc]),

если q[k — 1] < х < q[k]

На языке программирования Visual Basic этот алгоритм можно оформить в виде следующей программы:

Sub Rouf()

Const М = 6 Dim q{ 1 To M) As Single Dim a(Ai) As Single Dim qh, qR As Single Const eps = 0.00001

a(0) = 0:qL = 0: qR = 0.5. Do Until Abs(a(M) - 1) < eps Linel: q(l) = {qL + qR)/2 For i = 1 To М-1 a(f) = G (2 * F(q(i)) - F(a(i - 1)))

If a(i) > 1 Then

qR = G0T0 Linel Else

q(i + 1) = 2 * a(i) -End If

If q(i + 1) > 1 Then qR = q( 1): G0T0 Linel Next

a(M) = С (2 * F((?(M)) - F(a(M - 1))) If a(M) > 1 + eps/2 Then qR = q{ 1) If a(M) < 1 - eps/2 Then ql = q(l) Loop

Cells (1,1).Value = q( 1) End Sub

Function F(x As Single) As Single

F = x * x End Function

Function G(y As Single) As Single

G = Sqr(y) End Function

Подсчитаны огрубления для следующих функций xyfx, arctgx, х, х2, sin (тс 2 • arcsin|. Для некоторых специальных распределений получены аналитические методы огрубления.

Предложена, без моделирования сетевого взаимодействия, методика использования «огрубления» применительно к рассматриваемой в диссертации задаче:

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

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

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

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

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

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

2. Он должен быть построен на других (по сравнению с базовыми проактивными и реактивными алгоритмами) принципах. Например, если он использует маршрутную таблицу, она должна быть:

a) статична;

b) корректироваться не напрямую от изменения топологии сети (существенно реже).

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

«Структурные особенности сети» - это достаточно широкое понятие, но мы будем использовать его в двух следующих смыслах:

1. «Структурные особенности сети» - информация о положении или движении узлов сети.

2. «Структурные особенности сети» - информация о характере переключении связи между узлами.

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

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

1. «Структурные особенности сети» - как информация о положении или движении узлов сети (чаще всего приблизительная). Предполагается, что она известна априорно и на её основании могут быть построены специальные маршрутные таблицы, которые предоставляются узлам перед началом функционирования сети.

2. «Структурные особенности сети» - информация о характере переключении связи между узлами. Эта информация получается динамическим путем в результате наблюдения и обработки статистики переключения некоторых специально выделенных связей (то есть не является априорной).

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

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

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

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

Модуль расширения 2 (генератор топологии)

Модуль расширения 3 (сборщик статистики)

Модуль расширения 4 (генератор трафика)

»J

Модуль расширения 1 (протокол маршрутизации)

Ядро симулятора

Модуль расширения 5 (модификатор состояния узла)

Рис. 2. Модульная архитектура ПСС

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

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

Модули расширения ПСС представляют собой динамически подключаемые библиотеки операционной системы семейства UNIX (файлы с префиксом lib и расширением имени so). Благодаря гибкой модульной

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

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

Поэтому структура вызовов модулей логически должна быть примерно такой:

1. Генерирование топологии (однократно).

2. Модификация топологии.

3. Генерирование трафика.

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

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

Модуль генерирования топологии

Для каждого узла сети заполняет его список смежности таким образом, что бы минимальное число соседей по всей сети было равно Amin, максимальное - Атах, среднее - 0.5 (.Amin + Атах). Модуль изменений топологии

Для каждой связи осуществляет процесс переключение согласно процессу «обобщенная телеграфная волна» с интенсивностью ц и вероятностью активности f, создавая таким образом, динамическую топологию. Параметр процесса/разыгрывается случайно для каждой связи и является случайной величиной со степенным распределением (показатель Pj), параметр ц одинаков для всех связей.

Модуль классификации связей

Осуществляет классификацию связей по равномерному или степенному алгоритму с М уровнями.

Модуль генерирования таблиц

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

Модуль генерирования трафика

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

Модуль проактивной маршрутизации

Извлекает пакеты из буфера входящих пакетов, анализирует их и принимает решение о передаче (на основе таблиц маршрутизации)

Модуль реактивной процедуры поиска маршрута

Имитирует реактивную процедуру поиска маршрута (дистанционно-векторный алгоритм АСЮУ без кеширования).

Модуль лавинной рассылки

Моделирует лавинную рассылку: копирует и рассылает пакеты из буфера входящих пакетов всем активным смежным узлам.

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

Доля особых ситуаций для АСШУ:

-«—успех RREQ -«-успех RREP

успех доставки

Рис. 3. Доля особых ситуаций алгоритма AODV в зависимости от интенсивности изменения состояния связи ц

RREQ («route request») — пакет запроса маршрута.

RREP («route reply») - пакет с сообщением-ответом.

Доля доставленных проактивной компонентой пакетов:

0,6

0,5 0,4 0,3 0,2 ОД 0

и

0,3 0,4 0,5 0,6 0,7

-♦-лавина -»-гибридный по с11 -»-гибридный по сЮ

Рис. 4. Доля доставленных проактивной компонентой пакетов в зависимости от интенсивности ц

-♦-гибридный по сЛ -»-гибридный по сЮ

Рис. 5. Доля доставленных проактивной компонентой пакетов в зависимости от А - числа соседей узла

<10 = /{/ > 0} = еСЛИ/нач° - естественная метрика.

4 = -1п(/) - вероятностная метрика, /' - вероятность активности связи.

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

Доля доставленных проактивной компонентой пакетов 0,2

123456789 10 --без классификации М-равномерная

Рис. 6. Доля доставленных проактивной компонентой пакетов в зависимости от параметра надежности связи р1 (р1 = 1.0)

123456789 10 -без классификации—»-М-равномерная

-^-степенная с р=2.0

Рис. 7. Доля доставленных проактивной компонентой пакетов в зависимости от параметра надежности связи рг (рг = 2.0)

0,6

0,4

0,5

0,3

0,2

ОД

О

М

123456789 10 —без классификации —»-М-равноплерная ь-степенная с р=3.0

Рис. 8. Доля доставленных проактивной компонентой пакетов в зависимости от параметра надежности связи {р1 = 3.0)

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

Как показывают эксперименты, предложенная во второй главе вероятностная маршрутизация (проактивно-реактивный алгоритм, основанный на статистической информации), успешно справляется с задачей обеспечения большой доли трафика по постоянным таблицам. В зависимости от параметров сети от 45% дл 75% трафика можно направлять по таблицам, построенным по метрике (1! и от 25% до 40% по таблицам, построенным по метрике с10. Полученные результаты демонстрирует главную сильную сторону подхода: простым наблюдением за статистикой связи можно добиться существенной выгоды при маршрутизации. Еще раз подчеркнем тот факт, что проактивная часть в комбинации алгоритмов носит опциональный характер.

В заключении представлены основные результаты и выводы.

1. Предложена методика разбиения диапазона изменения «основного параметра связи» на классы, по различным критериям. В

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

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

3. Численным экспериментом подтверждается обоснованность предлагаемого подхода - «разбиение на классы». А именно:

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

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

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

1. Милованов, Д.С. Проблемы маршрутизации в сети с быстро меняющейся топологией / Д.С.Милованов, А.Ю. Тухтамирзаев, П.Ю. Шамин // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. - 2009. -№ 1.-С.28-32.

2. Аракелян, С.М. Об организации интеллектуальной маршрутизации в сети с динамической топологией с использованием статистических характеристик связей / С.М. Аракелян, Д.С. Милованов, В.Г. Прокошев, А.Ю. Тухтамирзаев, П.Ю. Шамин // Информатизация образования и науки. -2010. -№ 5. -С. 43-55.

3. Тухтамирзаев, А.Ю. Прогнозирование вероятности активности связи /А.Ю.Тухтамирзаев // XVI Всероссийская научно-методическая конференция "Телематика'2009", Санкт-Петербург, 22-25.06.2009 г. - С. 384-387.

4. Тухтамирзаев, А.Ю. Огрубление случайных величин его применение в сетях передачи данных / А.Ю. Тухтамирзаев // XVI Всероссийская научно-методическая конференция "Телематика'2009", Санкт-Петербург, 22-25.06.2009 г.-С. 381-384.

5. Аракелян, С.М. Некоторые вопросы оценки качества связей в сетях с переменной топологией / С.М. Аракелян, В.Г. Прокошев, М.Ю. Звягин, Д.С. Милованов, А.Ю. Тухтамирзаев // II Всероссийской научно-практической конференции «Инновации и информационные технологии в образовании», Липецк, 2009. - С. 140-144.

!)Х '/ъ

6. Дубровин, Н.И. Огрубление распределения нагрузки в сетях передачи данных / Н.И.Дубровин, А.Ю. Тухтамирзаев // XVII Международная конференция «Математика. Образование», Чебоксары, 2009. - С. 257.

7. Дубровин, Н.И. Оценка минимального сечения взвешенного графа / Н.И. Дубровин, А.Ю. Тухтамирзаев // Девятая международная конференция-семинар "Высокопроизводительные параллельные вычисления на кластерных системах", Владимир, 2-3.11.2009 г. - С. 155158.

8. Дубровин, Н.И. Связность коммуникационных сетей с переменной топологией / Н.И.Дубровин, А.Ю. Тухтамирзаев // II Всероссийской научно-практической конференции «Инновации и информационные технологии в образовании», Липецк, 2009. - С. 170-173.

9. Дубровин, Н.И. Дублирование информации при передаче по широкополостному каналу / Н.И. Дубровин, Т.В. Дубровина, А.Ю. Тухтамирзаев // XVI Всероссийская научно-методическая конференция "Телематика'2009", Санкт-Петербург, 22-25.06.2009 г. -С. 257-260.

Ю.Милованов, Д.С. Вопросы маршрутизации в сети с быстро изменяющейся топологией на основе её статистических характеристик / Д.С. Милованов, А.Ю. Тухтамирзаев, П.Ю. Шамин // Перспективы развития телекоммуникационных систем и информационные технологии: тр. междунар. конф. - СПб, 2008. - С. 23 - 33. - ISBN 978-5-7422-2141-8.

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

Введение.

Глава I. Маршрутизация в высокодинамичных сетях: проблемные вопросы и существующие решения.

1.1. Алгоритмы маршрутизации в сетях с быстро изменяющейся топологией.

1.1.1. Проактивные алгоритмы.

1.1.2. Реактивные алгоритмы.

1.1.3. Особенности маршрутизации в сенсорных сетях.

1.2. Обоснование необходимости специальных алгоритмов для работы в критических условиях.

1.2.1. Критические режимы функционирования.

1.2.2. Вероятностная маршрутизация.

1.2.3. Концепция самоорганизации узлов.

1.2.4. Стационарная фаза работы сети.

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

Глава II. Концепция связи: существующие проблемы, предлагаемые подходы решения и математические модели.

2.1. Введение.

2.2. Общие определения и соглашения.

2.3. Шкала огрубления.

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

2.3.2. Критерии огрубления.

2.3.3. Случаи критерия р = 1 и р = оо.

2.3.4. Случай р = 2 для функционального распределения.

2.3.5. Алгоритм огрубления методом итераций.

2.4. Правила оценки вероятности активности связи.

2.4.1. Моделирование активности связи в вероятностных сетях.

2.4.2. Прогнозирование вероятности активности связи.

2.4.3. Вычисление частоты переключения активности.

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

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

3.1 Введение.

3.2 Реактивная процедура поиска маршрута (РППМ) как основа дистанционно-векторных алгоритмов маршрутизации для ас! Ьос сетей (на примере базового протокола АСЮУ).

3.3 Лавинная рассылка. Проактивно-реактивная комбинация алгоритмов для случая экстремальной топологии.

3.4 Необходимость классификации связей.

3.5 Постановка и реализация эксперимента на кластере «СКИФ-Мономах».

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

3.5.2 Описание параллельного сетевого симулятора.

3.5.3 Требования к программному обеспечению и оборудованию.

3.5.4 Используемые для экспериментов модули расширения.

3.5.5 Методика экспериментов.

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

Глава IV. Анализ экспериментальных данных.

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

4.2 Сравнение лавинной рассылки с проактивно-реактивным (комбинационным) алгоритмом в зависимости от интенсивности изменений топологии.

4.3 Сравнение лавинной рассылки с проактивно-реактивным алгоритмом в зависимости от связности сети.

4.4 Сравнение лавинной рассылки с проактивно-реактивным алгоритмом в зависимости от размеров сети.

4.5 Результаты влияния метода классификации связей.

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

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

Наблюдаемый в последнее время повышенный интерес к беспроводным вычислительным сетям использующих радио или инфракрасные каналы привело к тому, что такие технологии передачи данных стали одним из наиболее быстро прогрессирующих направлений телекоммуникационного рынка. Таким образом, они начали постепенно вытеснять проводные сети как региональные, так и локальные. При этом одним из наиболее востребованных сегодня направлений является использование т.н. сетей MANET1 -неструктурированных мобильных вычислительных сетей. Они позволяют создавать децентрализованные телекоммуникационные сети произвольной топологии с элементами искусственного интеллекта. Сети MANET не используют фиксированную инфраструктуру и выбирают оптимальный маршрут для передачи трафика в условиях меняющейся конфигурации, благодаря чему их надежность очень высока. Алгоритмы, разработанные специально для решения этой задачи, получили название алгоритмов маршрутизации2. В процессе работы с такими сетями мобильные маршрутизаторы автоматически настраиваются на доступные ресурсы. Модули сети анализируют структуру трафика и адаптируют топологию системы под текущие нужды. С их помощью можно обеспечить движущуюся наземную и воздушную технику средствами связи дальнего радиуса действия, динамически подключать старые радиокомплексы. Узлы MANET самостоятельно объединяются в сеть, как только включается их питание.

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

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

Кроме того, пользователи смогут динамически настраивать ширину канала связи, дальность действия сети и зону покрытия.

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

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

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

Объект исследования

Объектом исследования данной работы являются высокодинамичные сети передачи данных - мобильные и сенсорные сети, в которых изменение

Сенсорная сеть - распределенная самоконфигурируемая беспроводная сеть, состоящая из малогабаритных интеллектуальных сенсорных устройств. 4

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

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

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

Реализация этой цели выполняется решением следующих задач:

- изучение и анализ условий целевой среды и специализированных алгоритмов маршрутизации;

- выявление критических режимов функционирования целевых сетей;

- формализация модели функционирования каналов передачи данных в сетевой среде;

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

- выработка предложений для совершенствования алгоритмов маршрутизации;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Научно-практическая конференция «Перспективы развития телекоммуникационных систем и информационные технологии», Санкт-Петербург, 2008г.

• XVII Международная конференция «Математика. Образование», Чебоксары, 24-31 мая 2009 г.

• II Всероссийская научно-практическая конференция «Инновации и информационные технологии в образовании», Липецк, 2009 г. 8

• XVI Всероссийская научно-методическая конференция "Телематика'2009", Санкт-Петербург, 22-25.06.2009 г.

• Девятая международная конференция-семинар "Высокопроизводительные параллельные вычисления на кластерных системах", Владимир, 2-3.11.2009 г.

Публикации

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

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

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

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

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

2. Основной результат: введение классификации связей с относительно небольшим и приемлемым на практике числе уровней сказывается на результатах маршрутизации незначительным образом. Конкретно: уже в случае десяти уровней различие между маршрутизаций с равномерной классификацией и идеальной маршрутизаций, выраженное в доле доставленных пакетов, составляют и не более 4-5%. Согласованная шкала дает лучшие результаты в области малого числа уровней (от 4 до 10), однако согласованная шкала требует наличия некоторых априорных знаний о распределении связей.

3. Как показывают эксперименты, предложенная в главе 2 вероятностная маршрутизация (проактивно-реактивный алгоритм, основанный на статистической информации), успешно справляется с задачей обеспечения большой доли трафика по постоянным таблицам. В зависимости от параметров сети от 45% до 75% трафика можно направлять по таблицам, построенным по метрике с1г и от 25% до 40% по таблицам, построенным по метрике <20. Полученные результаты демонстрирует главную сильную сторону подхода: простым наблюдением за статистикой связи можно добиться существенной выгоды при маршрутизации. Еще раз подчеркнем тот факт, что проактивная часть в комбинации алгоритмов носит опциональный характер.

ЗАКЛЮЧЕНИЕ

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

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

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

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

5. Как показывают эксперименты, предложенная в главе 2 вероятностная маршрутизация (проактивно-реактивный алгоритм, основанный на статистической информации), успешно справляется с задачей обеспечения большой доли трафика по постоянным таблицам. В зависимости от параметров сети телекоммуникации от 45% до 75% трафика можно направлять по таблицам, построенным по метрике и от 25% до 40% по таблицам, построенным по метрике с?0. Полученные результаты демонстрирует главную сильную сторону подхода: простым наблюдением за статистикой связи можно добиться существенной выгоды при маршрутизации. Еще раз подчеркнем тот факт, что проактивная часть в комбинации алгоритмов носит опциональный характер.

1. Callaway Е. Н. Wireless Sensor Networks: Architectures and Protocols / E. H. Callaway. CRC Press, 2004. - 350c.

2. Батаев P.A., Вероятностный подход при создании алгоритмов маршрутизации в сетях с изменяющейся топологией / P.A. Батаев, A.C. Голубев // Труды XIV Всероссийской научно-методической конференции «Телематика 2007». Том 1. СПб, 2007. - 267с.

3. Шамин, П.Ю. Модификация алгоритма поиска в пиринговой сети ЕВ AS / Шамин П.Ю. // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. 2007. - № 4. - Т. 2. -С. 30-34.

4. Звягин, М.Ю. Алгоритмы сбора информации, маршрутизации и агрегации в мобильных сетях / М.Ю. Звягин, Д.С. Милованов, В.Г. Прокошев // Материалы международного форума по проблемам науки, техники и образования «III тысячелетие новый мир». - М., 2007.

5. Дубровин, Н.И. Дублирование информации при передаче по широкополостному каналу / Н.И. Дубровин, Т.В. Дубровина, А.Ю. Тухтамирзаев // XVI Всероссийская научно-методическая конференция "Телематика'2009", Санкт-Петербург, 22-25.06.2009 г. -С. 257-260.

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

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

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

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

10. Тухтамирзаев, А.Ю. Огрубление случайных величин его применение в сетях передачи данных / А.Ю. Тухтамирзаев // XVI Всероссийская научно-методическая конференция "Телематика'2009", Санкт-Петербург, 2225.06.2009 г.-С. 381-384.

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

12. 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.

13. Perkins, С. E. Ad Hoc Networking / С. E. Perkins. — New York: Addison-Wesley, 2001.19.11yas, M. The Handbook of Ad Hoc Wireless Networks / edited by Mohammad Ilyas. — CRC Press LLC, 2003. — 559 p.

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

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

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

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

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

19. Дубровин, Н.И. Оценка минимального сечения взвешенного графа / Н.И. Дубровин, А.Ю. Тухтамирзаев // Девятая международная конференция-семинар "Высокопроизводительные параллельные вычисления на кластерных системах", Владимир, 2-3.11.2009 г. С. 155158.

20. 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.

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

22. 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.

23. 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.

24. Тухтамирзаев, А.Ю. Прогнозирование вероятности активности связи /А.Ю.Тухтамирзаев // XVI Всероссийская научно-методическая конференция "Телематика'2009", Санкт-Петербург, 22-25.06.2009 г. С. 384-387.

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

26. 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.

27. 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.

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

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

30. Manets Working Group InternetDraft, 14 Oct. 2003. — Режим доступа: http://www.ietf.org/internet-drafts/draft-ietf-manet-tbrpf-l 1 .txt.

31. 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.

32. 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.

33. 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.

34. 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.

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

36. 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.

37. 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.

38. 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.

39. 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.l 1-18.

40. 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.

41. Ко, 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.

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

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

44. 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.

45. 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.

46. Hu, Y.-C. Ariadne: A secure on-demand routing protocol for ad hoc networks / Ни, 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.

47. Santivanez, C. 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.

48. Беспроводные сенсорные сети Электронный ресурс. / Садков Александр http://www.sumkino.com/wsn/course/

49. Милованов, Д.С. Проблемы маршрутизации в сети с быстро меняющейся топологией / Д.С.Милованов, А.Ю. Тухтамирзаев, П.Ю. Шамин // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. 2009. - № 1. - С. 28 - 32.

50. Дубровин, Н.И. Связность коммуникационных сетей с переменной топологией / Н.И. Дубровин, А.Ю. Тухтамирзаев // II Всероссийской научно-практической конференции «Инновации и информационные технологии в образовании», Липецк, 2009. С. 170-173.

51. Дубровин, Н.И. Огрубление распределения нагрузки в сетях передачи данных / Н.И. Дубровин, А.Ю. Тухтамирзаев // XVII Международная конференция «Математика. Образование», Чебоксары, 2009. С. 257.

52. Таненбаум, Э. Компьютерные сети. / Э. Таненбаум. 4-е изд., - СПб.: Питер, 2006. - 992 с. - (Классика computer science). - ISBN 5-318-00492-Х.

53. Бертсекас, Д. Сети передачи данных: пер. с англ. / Д. Бертсекас, Р. Галлагер ; М.: Мир, 1989. - 544с., ил. - ISBN 5-03-000639-7.

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