Использование методов machine learning для улучшения характеристик самоорганизующихся сетей

Введение 3
Постановка задачи 5
Обзор литературы 6
Глава 1. Математическая модель 7
1.1. Сетевая структура 7
1.2. Подвижный агент: дрон 8
1.3. Альтернативы и выигрыши 9
1.4. Меры центральности 10
Глава 2. Описание алгоритмов решения задачи 13
2.1. Алгоритм решения с использованием метрики
betweenness centrality 13
2.2. «Жадный» алгоритм 14
Глава 3. Программная реализация 18
3.1. Алгоритм на основе метрики betweenness centrality. Описание структуры 18
3.2. Примеры решения задач 20
3.3. «Жадный» алгоритм 22
3.4. Примеры решения задачи 23
Глава 4. Сравнение полученных результатов 25
4.1. Сеть, состоящая из одного игрока 25
4.2. Сеть, состоящая из двух игроков 30
Глава 5. Моделирование в Network Simulator 3 32
5.1. Симулятор NS-3 32
5.2. Сравнение полученных результатов с помощью моделирования в NS-3 32
Выводы 37
Заключение 38
Список литературы 39
Приложение. Программный код 41

Купить

В данной работе рассматривается задача оптимизации передачи информации в сaмooргaнизующихся сетях различной конфигурации [4] с точки зрения теории игр [3], а также с применением одного из методов машинного обучения. Самоорганизующиеся означают то, что сетевая инфраструктура изначально не существует, рассматриваемые сети формируются агентами с нуля без какой либо существующей сетевой инфраструктуры (вышки сотовой связи, маршрутизаторы и т. д.). Такие мобильные сети обычно называют Мобильными специальными сетями (MANET) [1] или Беспроводными специальными сетями (WANET) [2], [3].
Последнее время наблюдается повышенный интерес к изучение таких сетей. Одним из конкретных направлений исследований, которое оказалось ценным при решении различных задач, связанных с оптимизацией мобильных сетей, является применение методов теории игр. Мобильные аб-Ьое сети используются в ситуациях, когда необходимо организовать связь между группами людей в районе, где сотовая связь недоступна. Применение этой технологии потенциально может спасти жизни. Например, во время поисково-спасательных работ связь между поисковыми группами является ключевым требованием. Когда происходят стихийные бедствия, нарушается коммуникационная инфраструктура, и чем быстрее устанавливается связь, тем быстрее координируются поисковые усилия.
Сетевая структура представляет собой граф, где вершины это агенты, а ребра — устойчивые связи между ними. Выигрыш каждого игрока зависит от диаметра подграфа, определенного на вершинах, принадлежащих игроку. Диаметром графа называется длина кратчайшего пути между двумя наиболее удаленными друг от друга вершинами. Диаметр графа используется для оценки максимального времени, требующегося для доставки пакета информации от одного агента к другому.
В рассматриваемом варианте задачи сетевые агенты неподвижны. Одним из эффективных способов уменьшения нагрузки на канал является использование беспилотных летательных аппаратов — дронов. Оптимизация работа сети осуществляется путем изменения ее структуры. У каждого игрока есть дрон с приемопередатчиком, который может быть размещен в определенном положении и подключен к сети, и, кроме того, в отличие от стационарных агентов, дрон может взаимодействовать с агентами любого игрока. Следует подчеркнуть, что главной особенностью беспилотных летательных аппаратов, является их мобильность. В отличие от почти статичных агентов, беспилотник может быть размещен в любой позиции по желанию игроков.
В данной работе, как и в работах [5], [8], [16], задача сводится к поиску наилучшего местоположения для дронов. Под наилучшим местом понимается такое место, что добавление дрона в эту позицию приводит к увеличению производительности сети, а именно уменьшение диаметра подграфа игрока. Число доступных беспилотных летательных аппаратов фиксировано. Выигрыш каждого игрока зависит от диаметра подграфа, определенного на вершинах, принадлежащих игроку. Цель каждого игрока — уменьшение диаметра результирующего расширенного подграфа.
Для решения данной задачи рассматриваются два алгоритма. Первый основывается на кооперативном подходе, когда игроки стремятся достичь максимального общего улучшения. Затем применяется одна из мер центральности для отбора единственного решения среди множества оптимальных. А во втором алгоритме — «жадном» — игроки хотят улучшить каждый свою подсеть. Такой алгоритм относится к одному из методов машинного обучения.
Затем для сравнения полученных результатов было выполнено экспериментальное моделирование в среде NS-3. Моделирование сети было реализовано на основе алгоритмов организации сетей MANET посредством библиотек для моделирования NS-3 [13].
Некоторые результаты, полученные в ходе работы над выпускной работой, были опубликованы в [14], проиндексированы в системе Web of Science. Также работа [15] была принята к публикации.
Постановка задачи
Основной задачей в рассматриваемой работе является сравнение результатов работы двух алгоритмов поиска оптимальной позиции для дронов в сети с неподвижными агентами. Для этого нужно решить следующие задачи:
1. Описать сетевую структуру сети MANET.
2. Сформулировать игру между игроками, которым принадлежат агенты сети.
3. Описать алгоритм поиска множества оптимальных решений.
4. Описать и детализировать алгоритм отбора единственного решения среди оптимальных с помощью меры центральности.
5. Описать «жадный» алгоритм.
6. Реализовать программный код.
7. Сравнить результаты работы двух алгоритмов.
8. Провести моделирование сети с помощью симулятора Network Simula¬tor 3.

Купить