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

• Автор: Базенков, Николай Ильич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Москва
• Количество страниц: 125 с. : ил.

Содержание

ВВЕДЕНИЕ
Глава 1. ТЕОРИЯ ИГР И БЕСПРОВОДНЫЕ СЕТИ
1.1. Теория игр в беспроводных сетях
1.1.1. Актуальность направления
1.1.2. Классификация задач
1.1.3. Примеры приложений
1.1.4. Дискуссионные вопросы
1.2. Самоорганизующиеся беспроводные сети
1.2.1. Классификация самоорганизующихся сетей
1.2.2. Архитектура и принципы функционирования
1.3. Управление топологией беспроводных сетей
1.3.1. Задачи управления топологией
1.3.2. Однородное управление топологией
1.3.3. Неоднородное управление топологией
1.4. Выводы по результатам обзора
Глава 2. ФОРМИРОВАНИЕ ТОПОЛОГИИ БЕСПРОВОДНОЙ СЕТИ
2.1. Введение
2.2. Постановка задачи
2.2.1. Модель сети
2.2.2. Задача формирования топологии
2.3. Игра формирования топологии
2.3.1. Основные понятия теории игр
2.3.2. Описание игры
2.3.3. Равновесия в игре формирования топологии

2.4. Алгоритмы формирования сети . . .
2.4.1. Базовый алгоритм формирования сети
2.4.2. Двойной наилучший ответ
2.4.3. Алгоритм двойных наилучших ответов
2.4.4. Алгоритм с переменным наилучшим ответом
2.5. Исследование эффективности алгоритмов
2.6. Выводы
Глава 3. РЕАЛИЗАЦИЯ АЛГОРИТМОВ
3.1. Реализация и вычислительная сложность алгоритмов
3.1.1. Общая схема формирования сети
3.1.2. Реализация наилучшего ответа
3.1.3. Реализация двойного наилучшего ответа
3.2. Программный комплекс моделирования формирования сети
3.2.1. Описание комплекса
3.2.2. Методика проведения экспериментов
3.2.3. Генерация и визуализация случайных сетей
3.2.4. Алгоритмы формирования сети
3.3. Выводы
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
Приложение. Акт о внедрении

ВВЕДЕНИЕ
Актуальность темы исследования
В данной работе рассматриваются децентрализованные сети с нефиксированной топологией, к которым относятся беспроводные сенсорные сети, мобильные ad hoc сети и др. Они используются для распределенного сбора данных, организации связи в полевых условиях, расширении пропускной способности обычных сотовых сетей и решения других задач, где требуется создать коммуникационную сеть без какой-либо дополнительной инфраструктуры, кроме самих беспроводных узлов. Такие сети состоят из большого числа устройств, как правило, работающих от автономных аккумуляторов. Поскольку заряд аккумуляторов ограничен, задача обеспечения энергоэффективности является одной из основных при управлении ad hoc сетями.
Формирование эффективной топологии сети - это один из методов экономии энергии узлов и снижения взаимных помех. Беспроводные узлы могут регулировать мощность своих передатчиков. Для того чтобы два узла образовали беспроводную связь, необходимо, чтобы мощности обоих передатчиков были выше некоторого порога, зависящего от расстояния между узлами. Задача состоит в назначении узлам таких мощностей, чтобы сформировалась связная сеть и суммарная мощность передатчиков была минимальна.
Методы формирования эффективных по тому или иному критерию сетей в настоящее время активно изучаются. Как правило, использование централизованных алгоритмов невозможно по причине отсутствия в сети единого управляющего центра, ограниченного обмена информацией и малых вычислительных мощностей узлов. Среди децентрализованных алгоритмов формирования сетей используются, в том числе, методы теории игр. В теоретико-игровых алгоритмах важную роль играет метод принятия решения рациональным агентом. Актуальной задачей является поиск новых методов принятия решения,

время поиска маршрута за счет дополнительного обмена служебными сообщениями. К проактивным протоколам относится OLSR (Optimized Link-State Routing), DSDV (Destination Sequenced Distance-Vector Routing), B.A.T.M.A.N. (Better Approach to Mobile Ad hoc Networks) и многие другие [69]. Поддержка постоянных таблиц маршрутизации оправдана, если изменения в топологии редки. Например, такой подход используется в mesh сетях. Иерархическая организация сети сокращает объем необходимых сообщений за счет того, что таблицы поддерживаются только узлами-маршрутизаторами, как в сенсорных сетях ZigBee [45].
Реактивные протоколы выполняют поиск путей только при поступлении запроса. Таким образом, исключается необходимость поддерживать актуальную информацию о топологии сети. Недостаток реактивных алгоритмов в том, что возрастает время поиска маршрута, а также появление сразу нескольких запросов может привести к лавинообразному росту объема служебных сообшений и отказу сети. Типичными реактивными протоколами являются AODV (Ad hoc On-demand Distance Vector), DSR (Dynamic Source Routing) и другие [69].
Гибридные протоколы совмещают оба подхода. Например, в протоколе ZRP (Zone Routing Protocol) сеть разделена на зоны, внутри которых поддерживаются актуальные таблицы маршрутизации. А при поиске пути между зонами используются реактивные запросы. К гибридным протоколам относятся CEDAR (Core Extraction Distributed Ad hoc Routing), SRP (Secured Routing Protocol) [69].
Позиционные методы организации сети используют информацию о географических координатах узлов. Такая информация может быть предоставлена с помощью встроенных модулей GPS или триангуляцией по нескольким опорным узлам. Вместо поиска маршрута от отправителя к получателю источник указывает координаты получателя и отправляет сообщение следующем узлу, который находится ближе всего к получателю. Для сенсорных сетей информация о местоположении узлов часто необходима для использования полученных