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

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

Шамин Павел Юрьевич

Многоцелевая маршрутизация в самоорганизующихся сетях с ограниченной мобильностью

Специальность 05 12 13 - «Системы, сети и устройства телекоммуникаций»

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

л. <-¿¿463

Владимир 2008

003172463

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

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

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

Аракелян Сергей Мартиросович

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

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

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

Ведущая организация ФГУГНИИ

ИТТ «Информика»

Защита диссертации состоится «2» июля 2008 года в 14— на

заседании диссертационного совета Д 212 025 04 в ауд 211(1)

Владимирского государственного университета по адресу 600000, Владимир, ул Горького, 87

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

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

Ученый секретарь диссертационного совета доктор технических наук, профессор

А Г. Самойлов

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

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

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

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

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

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

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

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

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

• разработана математическая модель для специфического класса сетей с ограниченной мобильностью,

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

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

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

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

В ходе работы над диссертацией разработано управляющее программное обеспечение для узла сети с переменной топологией, на которое получено свидетельство о государственной регистрации программы для ЭВМ «Управляющее программное обеспечение для узла гетерогенной беспроводной сети», зарегистрированная программа для ЭВМ (Номер гос регистрации №2008610134) / Правообладатель ГОУ ВПО ВлГУ, Авторы Голубев Андрей Сергеевич, Шамин Павел Юрьевич, Батаев Роман Алексеевич и др

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

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

- ООО "ФС Сервис"

- ФГУ ГНИИ ИТТ «Информика»

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

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

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

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

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

- Международная научная конференция «Информационные технологии и телекоммуникации в образовании и науке 1Т&Т Е8'2007», Турция, Фетхие, Май 2007 г

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

На защиту выносятся:

• концепция многоуровневой самоорганизации сети,

• математическая модель сети с ограниченной мобильностью (МО-модель),

• алгоритмы маршрутизации на основе МО-модели

- доставки медленного трафика с опциональной агрегацией,

- алгоритм организации устойчивого канала связи с опциональной синхронизацией,

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

Публикации

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

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

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

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

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

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

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

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

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

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

В параграфе 13 рассматривается перспективный алгоритм маршрутизации для сетей с переменной топологией - TORA (Temporally-Ordered Routing Algorithm), который следует принципу минимальной реакции на изменение топологии сети и рассылает служебные сообщения лишь в пределах малой окрестности Вследствие упомянутых

особенностей TORA хотя и проигрывает в сети с относительно стабильной топологией алгоритмам, строящим кратчайший путь (например, OSPF и ILS), при повышении частоты изменений топологии TORA уверенно лидирует по эффективности

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

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

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

Параграф 1 6 посвящен специфической категории сетей с переменной топологией, на которой были сконцентрированы исследования - сетям с ограниченной мобильностью

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

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

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

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

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

Уровень 0 предполагает выделение в сети узла-координатора, выполняющего функции координации работы сети

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

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

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

В параграфе 2 2 рассматривается математическая модель МО-сети (МО-модель) МО-модель - это математическая модель МО-сети Она позволяет представить сеть в виде графа, каждой вершине и дуге сопоставлены две числовые характеристики (см рис 1)

Числовые характеристики, сопоставляемые вершинам и дугам, характеризуют их с точки зрения надежности и имеют следующее значение

- Для вершины - среднее время активности узла 1, 5Т0' - среднее время неактивности узла ]

- Для дуги /,у - среднее время активности связи между узлами I и у при условии активности обоих узлов (среднее время нахождения узлов / и у в зоне досягаемости друг друга), - среднее время неактивности связи между узлами г и _/ при условии активности обоих узлов (среднее время нахождения узлов I и ] вне зоны досягаемости друг друга)

ST,\ST0" ST^Stf (?) ©

Im I/ a^X. tf

Узел g

ST? „ST/

Рис 1 Представление МО-сети МО-моделью

Построение МО-модели и дальнейшие расчеты с ее помощью выполняет узел-координатор. Все вышеперечисленные параметры модели узел-координатор получает от остальных узлов сети Состав поступающей информации представлен на рис 2

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

- T{'J - среднее время активности связи между узлами inj,

- - среднее время активности связи между узлами inj,

- ptJ - вероятность одновременной активности узлов inj,

При построении МО-модели мы основываемся на том, что ее параметры 57/ и являются математическими ожиданиями случайных величин длительностей периодов активности и неактивности узла I, которые в свою очередь образуют поток событий А, с ограниченным последействием

Аналогично параметры МО-модели ^ и ¡Ц - математические ожидания случайных величин длительностей периодов нахождения узлов / и 7 в зоне и вне зоны досягаемости друг друга соответственно При этом

Измеряются Изивряются Вычисляются узлами «ли узлами в узлах

UIDarTULl Uli у___________

узлами или известны им

известны им (опционально)

априорно

Рис 2 Состав истории наблюдений

считаем, что эти две случайные величины, применяемые попеременно, также образуют поток событий / с ограниченным последействием

В зависимости от дополнительных требований, предъявляемых к потокам событий /г, и определяющим параметры МО-модели будем

различать две модификации МО-модели

— МО-модель в широком смысле — требуется только независимость всех Л, и /„,

— МО-модель в узком смысле - дополнительно требуется, что случайные величины, генерирующие потоки событий А, и 1у распределены экспоненциально

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

Таблица 1

Метрики, применимые в МО-сети

Модификаци я МО-модели Метрика Назначение Примечапия

Вероятностная ¿1(1,7) = где „ V г., =- - вероятность " 77 +Г0» активности связи Максимизация вероятности прохождения пакета без ожидания

МО-модель в широком смысле Метрика «времени доставки» =(!-*•,) П Минимизация времен доставки пакета

8-метрика [ +«./¡,</4, , где / = - Р, вероятность активности связи, при условии активности обоих Отбор стабильных связей для устойчивого канала связи 1) Требуется априорное знание о длинном периоде переключения связей 2)Вследствие независимости ря =р, р,

МО-модель в узком смысле

узлов

Метрика «времени жизни» ¿з(г,у) = -|-,где

тч •ч

1 1

ЗТ/ ЛТ/

среднее вречя активности связи, при условии активности обоих узлов

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

Отбор стабильных связей для

устойчивого канала связи

+оЬ _ и —

, где - котачество выходов узлов из зоны досягаемости друг друга, -аЬ _\аЬ

Т^ , Т ^ - моменты возникновения и потери связи между узлами по той или иной причине

Метрика «времени доставки» для синхронизированного кластера

где

1-Л

л

V У

среднее время неактивности связи, при условии активности обоих узлов

Метрика «времени доставки» при блокировке узла-отправителя

¿ЛАУМ^Л)'*-

. где У „ ~- — среднее

Р)

время неактивности связи, при условии активности первого узла,

Маршрутизация в синхронизированно й сети

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

Если первый узел

зафиксирован во включенном состоянии, то

1 1 1

— =----, при

Т? 5Т>

синхронизации расписаний узлов

У = Т1} ч м

ПаЬ вычисляется по объединённой истории

наблюдений пары смежных узлов

Дает среднее время прохождения связи при

условии блокировки обоих узлов

Для вычисления ,

применяемой в формуле для I р можно применить следующее соотношение

_1_=Л___}_

1"{ ~ т» ¿т/

II (1 -Г } ■> и /7

Г \ 1 ч ) ' 1

вероятность активности связи,

при условии активности

первого узла

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

В третьей главе рассматривается применение МО-модели для управления медленным трафиком Под медленным трафиком понимаются пакеты данных, для которых не требуется немедленная доставка

В параграфе 31 кратко описываются основные принципы организации управления доставкой медленного трафика в МО-сети В частности приводится постановка задачи доставки медленного трафика, методика самоорганизации с использованием МО-модели, алгоритм функционирования сети по завершении самоорганизации с опциональным введением агрегирования пакетов данных и принципы маршрутизации медленного трафика в условиях выхода из строя части узлов

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

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

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

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

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

Ч-.р = 1п Рч>

где / - предельное время ожидания реактивации шлюза, а ^ -

параметр алгоритма

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

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

В параграфе 3 3 описывается разработанная нами с целью апробирования предложенных алгоритмов имитационная модель мобильной сети, которая использует дискретно-событийный подход и представляет собой набор взаимодействующих объектов, включающих в себя всю логику поведения Данная модель была реализована с использованием MS Visual С++ 2005, а ее адекватность подтверждена экспертной оценкой с участием 14 экспертов (степень адекватности модели - 87%, коэффициент вариации оценок экспертов - 4,3%)

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

Параграф 3 5 посвящен результатам проведенных экспериментов В нем показано превосходство вероятностной стратегии над классической (географической) во времени доставки (см рис 3)

50000 аооте

JOW3

гоооо JCM00

время доставки «А времени

ЛСРВЯЯ

стратегия ' (географ)

вторая — — страгегия(ве роятн )

трети стратегия («Р = irperauuett)

21 27 J1 35 И 47 51 г<™ « *Д

о операций Пересылки Ы

размер сети N «д.

Рис 3 Зависимость времени доставки от размера сети

Рис 4 Зависимость количества пересылок от размера сети

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

В конце главы приведены выводы по главе которые, в основном, сводятся к следующим положениям

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

2 Использование агрегирования увеличивает время доставки незначительно

3. Средняя длина маршрута при использовании вероятностной стратегии

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

В четвертой главе предлагаются еще некоторые алгоритмы, основанные на МО-модели

В параграфе 4 1 рассматривается алгоритм построения устойчивого канала связи в МО-сети В ней делается постановка задачи построения устойчивого канала связи (УКС), рассматриваются параметры МО-модели, существенные при построении и использовании УКС, выбираются соответствующие метрики, приводится алгоритм построения УКС, описываются эксперименты, проведенные с целью проверки разработанного алгоритма, и приводятся их результаты

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

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

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

активности обоих узлов - /оЬ, - средним периодом активного состояния связи, при условии активности обоих узлов -

Если поток событий, описывающий МО-модель стационарен, то обе эти величины для каждой связи являются константами Для полностью стабильной связи /аЬ = 1, г, = +оо

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

короткий период активного состояния, несмотря на высокую вероятность активности

Возможность управления расписаниями включения и выключения узлов позволяет значительно увеличить вероятность активного состояния связи, так как в типичном случае /аЬ » РаЬ

При наличии информации, о том, что связей с коротким циклом в сети нет (или их количество пренебрежимо мало) рекомендуется использовать 5-метрику, чтобы не переходить к МО-модели в узком смысле, в противном случае метрики с12 и </3 в составе той или иной целевой функции

Метрики с!г и с1ъ, примененные совместно, позволяют достичь максимальных значений сразу по обоим критериям качества УКС Эти критерии следующие

Временя установления УКС - это промежуток времени от момента инициирования процесса поиска канала до момента доведения служебного пакета до центрального узла

Время жизни УКС - это промежуток времени от момента установления УКС до момента обрыва УКС

Базовый алгоритм построения УКС выглядит следующим образом

1 В некоторый момент времени один из узлов сети принимает решение установить УКС с узлом-координатором

2 Узел блокирует себя от выключения

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

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

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

6 Получив пакет, подтверждающий успешное построение УКС узел, инициировавший его построение, начинает передачу данных

Эксперименты для проверки эффективности этого алгоритма в различных вариантах (с разными метриками) проводились на имитационной модели МО-сети Рассматривалось 4 модификации алгоритма по в-метрике в обычной («стандарт») и синхронизированной («синхронизация») МО-сети, и по метрикам с12 и также в обычной

(«информация о связях») и синхронизированной («обе опции») сети. Результаты проведённых экспериментов приведены на рис. 5 и 6.

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

100Р00 т----------------------1

90530 91 170 90 МО---^^Н-

30000 ---^^И----

70000 --^^В-Ц^В-

б осао----^^И-^^Н-

ЬОООО-------ВЦ-^ЯВ-

— ' я в

20000 • —-------ПН- .....—^^В-----В^Н-(

■ 1 II

Стандарт О^хрттз.мия ИНО. с сав(Я« Обе ОИ.ии

Рис. 6 Среднее время существования УКС (в единицах модельного времени)

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

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

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

Стандарт Син>ц>ониэ«ция Инф. с ■ Среднее и Мэнсимэ/^ьн

Рис. 5 Время установления УКС (в единицах модельного времени)

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

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

Для существенного снижения времени доставки без существенного повышения количества дублирующихся посещений, можно модифицировать алгоритм случайных блужданий, производя ветвления блужданий не только на первом шаге, но и на некоторых (возможно всех) последующих При этом с каждым шагом поиска количество блужданий будет увеличиваться Такой модифицированный алгоритм мы назвали алгоритмом ветвящихся случайных блужданий (branching random walk search method, BRWSM)

Параметром данного алгоритма является вектор количества ветвлений К Для обычных (неветвящихся) блужданий он имеет вид {к, 1,1,1,1}где ¿-количество блужданий

Вместо обычного блуждания с параметрами к и Т (TTL, начальное время жизни пакета) можно применить ветвящееся блуждание с меньшим начальным TTL равным Т и вектором ветвления следующего вида

К 1

1 1 2

Y

m

t

Рис 7 Вектор ветвления алгоритма ВЯ\У8М

Значение ТТЬ ветвящегося случайного блуждания связано с его параметрами соотношением Т = 1 + т + ( Кроме того, задав значение т мы можем определить значение ТТЬ для ветвящегося случайного блуждания эквивалентного по максимальному количеству посещаемых узлов заданному неветвящемуся

Т =Ъё2(Т-т) + т + \

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

1 На основании доли числа узлов МО-сети, захваченной синхронизированными кластерами с помощью алгоритма ЕВАБ определяем параметры классического (чеветвящегося) блуждания

2 Пересчитываем их в параметры ветвящегося блуждания

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

Ряд проведенных численных экспериментов и выполненных аналитических оценок показал, что дополнительные затраты при использовании ветвящихся блужданий вместо классических не превышают 20% (а при q >= 0 9 не превышают 10%), в то время как задержка как правило снижается в 1,5-1,8 раза

В конце главы приведены выводы по главе, сводящиеся к следующему

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

2 Разработан и апробирован алгоритм построения устойчивого канала связи

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

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

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

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

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

4 На основе данной модели разработаны и апробированы

а) Алгоритмы сбора и обработки статистической информации в сети с ограниченной мобильностью

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

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

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

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

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

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

7 Разработана имитационная модель сети с ограниченной мобильностью, позволяющая моделировать такие сети с достаточной степенью адекватности

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

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

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

2 Звягин, M Ю Повышение эффективности алгоритма случайных блужданий путем ветвления блуждания в промежуточных узлах / M Ю Звягин, П Ю Шамин, В Г Прокошев // Телематика-2007 тр XIV Всерос науч-метод конф - СПб, 2007 -T 1 - С 269-271 -ISBN 5-7577-0329-6

3 Шамин, ПЮ Модификация алгоритма поиска в пиринговой сети EBAS с целью снижения среднего времени поиска / П Ю Шамин // Телекоммуникационные и информационные системы тр междунар конф - СПб, 2007 - С 103-114 - ISBN5-7422-1583-5

4 Шамин, П Ю Экспериментальная проверка применимости алгоритма маршрутизации на основе вероятностного подхода для использования в беспроводной сети с переменной топологией на базе технологии Bluetooth / П Ю Шамин, Р А Батаев, Д С Милованов // Перспективные технологии в средствах передачи информации материалы VII междунар конф - Владимир, 2007 - С 97 - 99 -ISBN 978-5-93907-033-1

5 Голубев, АС JAVA-реализация протоколов взаимодействия для неоднородных беспроводных сетей произвольной структуры / АС Голубев, ПЮ Шамин // Перспективные технологии в средствах передачи информации материалы VII междунар конф - Владимир, 2007 - С 99- 102 - ISBN 978-5-93907-033-1

6 Голубев, А С Использование среды JAVA для создания неоднородных мобильных сетей произвольной структуры (MANET) / А.С Голубев, ПЮ Шамин, С В Рощин, СМ Араке пян // Тр междунар форума по проблемам науки, техники и образования - М, 2007 -Т 2 - С 77-78 -ISBN978-5-93411-045-2

7 Прокошев, В В Моделирование беспроводных сетей с переменной топологией с применением параллельных вычислений / СМ Аракелян, В В Прокошев, П Ю Шамин // Применение многопроцессорных суперкомпьютеров в исследованиях, наукоемких технологиях и учебной работе - 2008 Сб материалов регион науч -техн конф - Иваново, 2008 - С 23-25 - ISBN 978-5-88954-282-7

8 Милованов, ДС Методы оценки параметров линии связи в сети с ограниченно подвижными отключаемыми узлами [Электронный ресурс] / В Г Прокошев, Д С Милованов, П Ю Шамин, С М Аракелян // Телематика-2008 тр XV Всерос науч.-метод конф http //tm lfmo ru/tm2008/src/139b pdf

9 Прокошев, В В Моделирование топологии сети большой размерности с использованием параллельных вычислений [Электронный ресурс] / В В Прокошев, П Ю Шамин // Телематика-2008 тр XV Всерос науч-метод конф http //tm lfmo ru/tm2008/src/138bs pdf

Подписано в печать 28 05 08 Формат 60x84/16 Уел печ л 0,93 Тираж 100 экз Заказ Ш-Об? Издательство Владимирского государственного университета 600000, Владимир, ул Горького, 87

ВВЕДЕНИЕ.

1. МАРШРУТИЗАЦИЯ В СЕТЯХ С ПЕРЕМЕННОЙ ТОПОЛОГИЕЙ. СОВРЕМЕННОЕ СОСТОЯНИЕ ПРОБЛЕМЫ

1.1 Введение.

1.2 Алгоритмы маршрутизации для сетей с переменной топологией.

1.3 Алгоритм TOR А.

1.4 Сенсорные сети.

1.5 Вероятностный подход к управлению информационными потоками.

1.6 Сети с ограниченной мобильностью.

1.6.1 Определение.

1.6.2 Лавинная рассылка в сетях с ограниченной мобильностью.

1.6.3 Случайные блуждания в сетях с ограниченной мобильностью.

1.7 мобильные сети с ограниченно-подвижными отключаемыми узлами (мо-сети).

1.7.1 Определение.

1.7.2 Задачи маршрутизации в МО-сети. выводы по главе.

2. АНАЛИЗ ЗАДАЧИ МАРШРУТИЗАЦИИ ДАННЫХ В МО-СЕТИ.

2.1 Концепция самоорганизации в МО-сети.

2.1.1 Определение самоорганизации сети.

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

2.1.3 Уровни самоорганизации.

2.1.4 Работа сети в начальный период времени.

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

2.2.1 Назначение модели.

2.2.2 Общее описание МО-модели.

2.2.3 Частные случаи МО-моделей.

2.2.4 Функции узла-координатора.

2.2.5 История наблюдений узла.

2.2.6 Вычисление параметров МО-модели.

2.2.7 Метрики применимые с МО-моделью.

2.3 о технико-экономическом обосновании предложенной концепции, математической модели и алгоритмов на их основе. выводы по главе.

3. ПРИМЕНЕНИЕ МО-МОДЕЛИ ДЛЯ УПРАВЛЕНИЯ МЕДЛЕННЫМ ТРАФИКОМ.

3.1 Основные положения.

3.1.1 Задача доставки медленного трафика.

3.1.2 Методика самоорганизации.

3.1.3 Функционирование сети с «медленным трафиком», агрегирование.

3.1.4 Маршрутизация в условиях выхода из строя части узлов.

3.2 Служебные алгоритмы, структуры данных и особенности реализации.

3.2.1 Требования к оборудованию.

3.2.2 Структуры данных.

3.2.3. Процедуры сбора данных для истории наблюдений.

3.2.4. Лавинные процессы.

3.2.5 Алгоритмы доставки данных, ограниченного ожидания, агрегирования.

3.3. Разработка имитационной модели мобильной сети.

3.4. Методики численных экспериментов.

3.5. Результаты численных экспериментов.

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

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

4.1. Установление устойчивого канала связи для непрерывной трансляции потока данных.

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

4.1.2 Характеристики связей, существенные при построении УКС.

4.1.3 Определение параметров стабильности связей.

4.1.4 Построение УКС.

4.1.5 Методики и результаты численных экспериментов.

4.2. Межкластерная маршрутизация.

4.2.1 Особенности задачи межкластерной маршрутизации.

4.2.2 Лавинная рассылка.

4.2.3 Случайные блуждания.

4.2.4 Ветвящиеся случайные блуждания.

4.2.5 «Гибридный» алгоритм RWSM + BRWSM в составе модифицированного алгоритма EBAS.

4.2.6 Результаты моделирования.

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

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

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

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

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

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

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

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

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

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

• выявление методик эффективного управления информационными потоками в сетях с быстроизменяющейся топологией;

• выявление и классификация задач маршрутизации, которые требуется решить;

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

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

• разработка математической модели сетей с переменной топологией рассматриваемой архитектуры;

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

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

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

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

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

• разработана математическая модель для специфического класса сетей с ограниченной мобильностью;

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

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

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

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

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

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

В ходе работы над диссертацией разработано управляющее программное обеспечение для узла сети с переменной топологией, на которое получено свидетельство о государственной регистрации программы для ЭВМ: «Управляющее программное обеспечение для узла гетерогенной беспроводной сети», зарегистрированная программа для ЭВМ (Номер гос. регистрации №2008610134) / Правообладатель ГОУ ВПО ВлГУ; Авторы: Голубев Андрей Сергеевич, Шамин Павел Юрьевич, Батаев Роман Алексеевич и др.

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

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

- ООО "ФС Сервис".

- ФГУ ГНИИ ИТТ «Информика».

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

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

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

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

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

- Международная научная конференция «Информационные технологии и телекоммуникации в образовании и науке IT&T ES'2007», Турция, Фетхие, Май 2007 г.

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

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

На защиту выносятся:

• механизм многоуровневой самоорганизации сети и математическая модель сети с ограниченной мобильностью;

• алгоритм доставки медленного трафика в сети с ограниченной мобильностью с опциональной агрегацией;

• алгоритм организации устойчивого канала связи в сети с ограниченной мобильностью с опциональной синхронизацией;

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

Публикации

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

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

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

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

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

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

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

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

Заключение

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

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

2. Разработана математическая модель сети с ограниченной мобильностью, которая может быть положена в основу управляющего программного обеспечения узла-координатора. На основе данной модели разработаны и апробированы: a. Алгоритмы сбора и обработки статистической информации в сети с ограниченной мобильностью. b. Метрики, пригодные для решения различных задач маршрутизации с помощью модели сети с ограниченной мобильностью.

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

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

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

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

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

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

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

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

6. Столлингс, В. Современные компьютерные сети / В. Столлингс. 2-е изд. - СПб.: Питер, 2003.

7. Протоколы и методы управления в сетях передачи данных: Пер. с англ. / Под ред. Ф. Ф. Куо. М.: Радио и связь, 1980. - 480 с.

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

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

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

11. Denardo, Е. U. Shortest Route Methods: I. Reaching, Pruning and Buckets / E.U. Denardo, B.L. Fox// Oper. Res. 1979. - Vol. 27, N 1. - P. 164-186.

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

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

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

15. Кравец, О.Я. Оптимизация мониторинга телекоммуникационных сетей для создания резервной производительности системы / О.Я. Кравец, Н.Н. Севрюков, А.Д. Поваляев. // Системы управления и информационные технологии, 2005. № 2(19). - С. 87 - 92.

16. Хелеби, С. Принципы маршрутизации в Internet / С. Хелеби: Пер. с англ. — 2-е изд. М.: Издательский дом "Вильяме", 2001. - 448 с.

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

18. Бекетов, О. Беспроводные сети MESH Электронный ресурс. / О. Бекетов http://www.planet.com.ru/upload/ll 162990815.pdf (25.05.2008).

19. Corson, M.S Internet-Based Mobile Ad Hoc Networking / M. S. Corson et al. // IEEE Internet Computing. July-August 1999. - P. 63 - 70.

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

21. Kargl, F. Bluetooth-based Ad-Hoc Networks for Voice Transmission / F. Kargl et al. // Proc. HICSS 2003.

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. Royer, E.M. Analysis of the Optimum Node Density for Ad hoc Mobile Networks / E. M. Royer, et al. // Proc. IEEE ICC 2001.

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

25. Tschudin, C. Active Routing for Ad Hoc Networks / C. Tschudin et al. // IEEE Communications Magazine. April 2000. - P. 122 - 127.

26. Zadeh, A.N. Self-Organizing Packet Radio Ad Hoc Networks with Overlay (SOPRANO) / A. N. Zadeh et al. // IEEE Communications Magazine.- June, 2002.

27. Bao, L. Topology Management in Ad Hoc Networks / L. Bao and J. J. Garcia-Luna Aceves // Proc. MobiHoc 2003. - P. 129 - 140.

28. Eastlake, D.E. Graphs, Nets, and Meshes / D. E. Eastlake // IEEE 802.11 document 04/420. 18 March 2004.

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

30. Garces, I. Analytical Modeling of the Network Traffic Performance /1. Garces, D. Franco, and E. Luque // Proc. MASCOTS '99. P. 190 - 196.

31. Tobagi, F.A. Modeling and Performance Analysis of Multihop Packet Radio Networks / F. A. Tobagi // Proc. IEEE. January 1987. - Vol. 75. - P. 135 -155.

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

33. Subbarao, M. W. Ad Hoc Networking Critical Features and Performance Metrics / M.W. Subbarao // Wireless Communications Technology Group, NIST.-October 7, 1999.

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

35. Ad-hoc On-demand Distance Vector (Article from Wikipedia, the free encyclopedia) Электронный ресурс. http://en.wikipedia.org/wiki/AODV

36. Optimized Link State Routing protocol (Article from Wikipedia, the free encyclopedia) Электронный ресурс. http://en.wikipedia.org/wiki/Optimized LinkStateRoutingprotocol

37. Hazy Sighted Link State Routing Protocol (Article from Wikipedia, the free encyclopedia) Электронный ресурс. http://en.wikipedia.org/wiki/ HazySightedLinkStateRoutingProtocol

38. Temporally-ordered routing algorithm (Article from Wikipedia, the free encyclopedia) Электронный ресурс.: http://en.wikipedia.org/wiki/ Temporally-orderedroutingalgorithm

39. Dynamic Source Routing algorithm (Article from Wikipedia, the free encyclopedia) Электронный ресурс. http://en.wikipedia.org/wiki/Dynamic SourceRouting

40. Perkins, C. RFC 3561 Ad hoc On-Demand Distance Vector (AODV) Routing Электронный ресурс. / С. Perkins, E. Belding-Royer, S. Das http ://www.faqs.org/rfcs/rfc3561 .html

41. Clausen, T. Optimized Link State Routing Protocol (OLSR) Электронный ресурс. / Т. Clausen, P. Jacquet http://www.faqs.org/rfcs/rfc3626.html

42. Park, V.D. Temporally-Ordered Routing Algorithm (TORA) Version 1 Functional Specification Электронный ресурс. / Park V.D., Corson S.M. http ://tools .ietf.org/html/draft-i etf-manet-tora-spec-04

43. Johnson, D. The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4 Электронный ресурс. / D. Johnson, Y. Hu, D. Maltz http://www.faqs.org/rfcs/rfc4728.html

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

45. Hong, X. Scalable Routing Protocols for Mobile Ad Hoc Networks / X. Hong, K. Xu, M. Gerla // IEEE Network Magazine. July - Aug 2002. - P. 11 - 21.

46. Bisnik, N. Modeling and Analysis of Random Walk Search Algorithms in P2P Networks / Bisnik N., Abouzeid A. Rensselaer Polytechnic Institute, Troy, New York, 2005

47. Jia, Z. Random Walk Spread and Search in Unstructured P2P / Z. Jia, R. Rao, M. Li, J. You. Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai, China, 2004

48. Alkhatib, H.S. Wireless Data Networks: Reaching the Extra Mile / H.S. Alkhatib, C. Bailey, M. Gerla, J. McRae // Computer. Dec. 1997. - Vol. 30. -P. 59-62.

49. Berezdivin, R. Next-Generation Wireless Communication Concepts and Technologies / R. Berezdivin, R. Breining, R. Topp // IEEE Commun. Magazine. March 2002. - Vol. 40. - P. 108 - 116.

50. Bhagwat, P. Bluetooth: Technology for Short-Range Wireless Apps / P. Bhagwat // IEEE Internet Computing. May - June 2001, Vol. 5. - P. 96 - 103.

51. Bisdikian, C. An Overview of the Bluetooth Wireless Technology / Bisdikian C. // IEEE Commun. Magazine. Dec. 2001. - Vol. 39. - P. 86 - 94.

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

53. Geier, J. Wireless LANs / J. Geier. 2nd ed. - Indianapolis IN: Sams, 2002.

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

55. Lansford, J. Wi-Fi (802.11b) and Bluetooth: Enabling Coexistence / J. Lansford, A. Stephens, R. Nevo // IEEE Network Magazine. Sept. - Oct. 2001.-Vol. 15, P. 20-27.

56. Solomon, J.D. Mobile IP: The Internet Unplugged / J.D. Solomon. Upper Saddle River, NJ: Prentice Hall, 1998.

57. Tseng, Y.-C. Location Awareness in Ad Hoc Wireless Mobile Networks / Y.-C. Tseng, S.-L. Wu, W.-H. Liao, C.-M. Chad // Computer. 2001. - Vol. 34, P. 46-51.

58. Wang, Y. Supporting IP Multicast for Mobile Hosts / Y. Wang, W. Chen // Mobile Networks and Applications. Jan. - Feb. 2001. - Vol. 6. - P. 57 - 66.

59. Zadeh, A.N. Self-Organizing Packet Radio Ad Hoc Networks with Overlay (SOPRANO) / A.N. Zadeh, B. Jabbari, R. Pickholtz, B. Vojcic // IEEE Commun. Mag. June 2002. - Vol. 40. - P. 149 - 157.

60. Kleinrock, L. Hierarchical Routing for Large Networks: Performance Evaluation and Optimization / L. Kleinrock, F. Kamoun // Computer Networks.- 1977. Vol. 1, № 3. - P. 155 - 174.

61. Батаев, P.A. Вероятностный подход в создании алгоритмов маршрутизации в сетях с изменяющейся топологией / Р.А., Батаев // Телекоммуникационные и информационные системы: тр. междунар. конф.- СПб., 2007. С. 117 - 125. - ISBN 5-7422-1583-5.

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

63. Всерос. науч. семинар «Интернет-порталы. Содержание и технологии», сборник научных статей. 2007. - Выпуск 4. - С.440 - 464.

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

65. Estrin, D. «Wireless Sensor Network Protocols» / D. Estrin, A. Sayeed, M. Srivastava // MobiCom 2002, The Eighth ACM International Conference on Mobile Computing and Networking. Westin Peachtree Plaza, Atlanta, Georgia, USA, 2002.

66. Мишагин, К.Г. Продление времени жизни сенсорной сети с помощью методов коллективной передачи информации / К.Г.Мишагин, В.А. Пастухов, А.Н. Садков // Тр. науч. конф. по радиофизике. Нижний Новгород, ННГУ, 2005. - С. 344 - 346.

67. Warneke, В. Smart Dust: Communicating with a Cubic Millimeter Computer / B. Warneke, M. Last, B. Liebowiz, K. Pister // Computer. Jan 2001. - Vol. 34. p. 44 5l.

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

69. Кристофидес, Н. Теория графов. Алгоритмический подход: Пер. с англ. / Н. Кристофидес. М.: Мир, 1978. - 432 с.

70. Карасев, А.В. Метод выбора кратчайших направлений передач на сети связи на основе эвристических рассуждений / А.В.Карасев, А.В. Пушнин, В.И. Финаев // Перспективные информационные технологии и интеллектуальные системы. 2000. - № 4. - С. 43 - 46.

71. Уваров, Д.В. Построение дерева кратчайших путей в графе на основе данных о парных переходах / Д.В. Уваров, А.И. Перепелкин, В.П. Корячко // Системы управления и информационные технологии. 2004. — № 4(16). -С. 92-95.

72. Дорошенко, А. Е. Моделирование сенсорных сетей средствами высокого уровня Электронный ресурс. / А. Е. Дорошенко, К. А. Жереб, Р.С. Шевченко http://www.gradsoft.ua/rus/whitepapers/sensnet9.pdf

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

74. Питерсон, Дж. Теория сетей Петри и моделирование систем / Дж. Питерсон. М.: Мир, 1984. - 264 с.81 .Пранявичус, Г. И. Модели и методы исследования вычислительных систем / Г. И. Пранявичус. — Вильнюс: Монслас, 1982. 228 с.

75. Савинков, А.Ю. Имитационное моделирование компонентов управления системой связи и всей системы связи в целом / А.Ю. Савинков, С.А. Филин, С.В. Поличной // Системы управления и информационные технологии. 2006. - № 2(24). - С. 18 - 22.

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

77. Кравец, О.Я. Повышение эффективности маршрутизации в переходных режимах функционирования вычислительных сетей / О.Я. Кравец, А.В.

78. Пономарев, И.С. Подерский // Системы управления и информационные технологии. 2003. - № 1 - 2 (12). - С. 73 - 77.

79. Cavin, D. On the accuracy of MANET simulators / D. Cavin et al. // Proc. ACM Workshop on Princ. Mobile Computing (POMC'02). Oct. 2002. - P. 38 -43.

80. Bettstetter C. Mobility Modeling and Analysis of Adaptive Clustering Algorithms in Ad Hoc Networks / C. Bettstetter, J. Xi // Proc. 4th European Personal Mobile Communications Conference (EPMCC01). Vienna, February 19-22, 2001.

81. Шамин, П.Ю. Модификация алгоритма поиска в пиринговой сети EBAS с целью снижения среднего времени поиска / П.Ю. Шамин // Телекоммуникационные и информационные системы: тр. междунар. конф. СПб., 2007. - С. 103 - 114. - ISBN 5-7422-1583-5.

82. Голубев, А.С. JAVA-реализация протоколов взаимодействия для неоднородных беспроводных сетей произвольной структуры / А.С.

83. Голубев, П.Ю. Шамин // Перспективные технологии в средствах передачи информации: материалы VII междунар. конф. Владимир, 2007. - С. 99 -102. - ISBN 978-5-93907-033-1.

84. Прокошев, В.В. Моделирование топологии сети большой размерности с использованием параллельных вычислений Электронный ресурс. / В.В. Прокошев, П.Ю. Шамин // Телематика-2008: тр. XV Всерос. науч.-метод. конф. http://tm.ifmo.ru/tm2008/src/138bs.pdf