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

• Автор: Шамин, Павел Юрьевич
• Шифр специальности: 05.12.13
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Владимир
• Количество страниц: 173 с. : ил.

Оглавление
ВВЕДЕНИЕ
1. МАРШРУТИЗАЦИЯ В СЕТЯХ С ПЕРЕМЕННОЙ ТОПОЛОГИЕЙ. СОВРЕМЕННОЕ СОСТОЯНИЕ ПРОБЛЕМЫ
1.1 Введение
1.2 АЛГОРИТМЫ МАРШРУТИЗАЦИИ ДЛЯ СЕТЕЙ С ПЕРЕМЕННОЙ ТОПОЛОГИЕЙ
1.3 Алгоритм TORA
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 Результаты моделирования
Выводы по главе
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
ПРИЛОЖЕНИЯ
Приложение 1. Блок-схема процедуры обмена сообщениями при сборе статистики
Приложение 2. Блок-схема лавинной рассылки для заполнения маршрутных таблиц
Приложение 3. Блок-схема агрегирования
Приложение 4. Используемые наборы правил для переключения узлов при экспериментальной проверке эффективности алгоритмов маршрутизации медленного трафика

Приложение 5. Количество отосланных пакетов при первой (географической) стратегии в зависимости
ОТ РАЗМЕРА СЕТИ и I, ЕД
Приложение 6. Отношение количества отосланных пакетов при первой стратегии к аналогичному
ПАРАМЕТРУ ВТОРОЙ СТРАТЕГИИ В ЗАВИСИМОСТИ ОТ РАЗМЕРА СЕТИ И I, OTH
Приложение 7. Отношение количества отосланных пакетов при первой стратегии к аналогичному ПАРАМЕТРУ ТРЕТЬЕЙ СТРАТЕГИИ В ЗАВИСИМОСТИ ОТ РАЗМЕРА СЕТИ И I, OTH
Приложение 8. Отношение количества отосланных пакетов к размеру сети при первой стратегии в
ЗАВИСИМОСТИ ОТ РАЗМЕРА СЕТИ И Г, ЕД
Приложение 9. Среднее время доставки пакета при первой стратегии в зависимости от размера сети и г,
ЕД. ВРЕМЕНИ
Приложение 10. Отношение среднего времени доставки пакета при первой стратегии к аналогичному
параметру второй стратегии в зависимости от РАЗМЕРА СЕТИ И X, ОТН
Приложение 11. Число операций пересылки при первой стратегии в зависимости от размера сети и е, ед.

Приложение 12. Отношение числа операций пересылки при второй стратегии к аналогичному параметру
первой стратегии в зависимости от размера сети ИI, ОТН
Приложение 13. Отношение числа операций пересылки при первой стратегии к аналогичному параметру
третьей стратегии в зависимости от размера сети и параметра X, ОТН
Приложение 14. Доля быстрых пакетов при первой стратегии в зависимости от размера сети и г, отн. ед.

Приложение 15. Доля быстрых пакетов при второй стратегии в зависимости от размера сети и х, отн. ед.

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

Приложение 17. Методика эксперимента по определению возможной точности измерения величин Т0 и
Tj, В СЛУЧАЕ, КОГДА УЗЛЫ СЕТИ ИСПОЛЬЗУЮТ ПРОТОКОЛ BLUETOOTH
Постановка задачи
Порядок проведения эксперимента
Приложение 18. протокол эксперимента по определению возможной точности измерения величин ТО и
Т1, в случае, когда узлы сети используют протокол Bluetooth
Результаты проведения эксперимента
Выводы

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