Введение 3
Постановка задачи 6
Обзор литературы 7
Глава 1. Математическая модель 10
1.1. Базовые элементы игры 10
1.2. Сетевая структура 11
1.3. Кооперативная игра 12
1.4. Функции выигрыша для кооперативной игры 12
Глава 2. Алгоритм 16
2.1. Описание алгоритма решения задачи 16
2.2. Поиск потенциальных позиций
при помощи квадратной сетки 20
Глава 3. Анализ результатов моделирования 21
3.1. Преимущества и недостатки MANET 22
3.2. Протоколы маршрутизации, использующиеся в MANET . . 24
3.3. Описание моделируемой сети 24
3.4. Примеры 25
Выводы 44
Заключение 45
Список литературы 47
Приложения 50
В данной работе рассматривается задача оптимизации передачи ин-формации между группами в самоорганизующихся сетях. Задача решена при использовании теоретико-игрового подхода.
Под самоорганизующейся сетью подразумевается MANET (Mobile Ad-hoc Network) [1] — беспроводная самоорганизующаяся децентрализованная сеть, состоящая из мобильных узлов, способных устанавливать и поддерживать соединения между узлами. Она не зависит от ранее существующей инфраструктуры, например, от маршрутизаторов в проводных сетях или от точек доступа в инфраструктурных беспроводных сетях. Маршрутизаторы могут свободно перемещаться и организовываться произвольно, из-за этого беспроводная топология сети может изменяться быстро и непредсказуемо. В данном виде сетей каждый узел участвует в маршрутизации путем пересылки данных для других узлов, поэтому определение узлов, пересылающих данные, производится динамически на основе сетевого подключения и используемого алгоритма маршрутизации.
MANET широко применяется во многих проектах. Он хорошо подходит для ситуаций, когда при организации сетей нет необходимости или возможности использовать глобальную сеть. Существует ряд задач, которые требуют быстрого развертывания сети, но при этом нет необходимости в крупной и сложной сети, например, в чрезвычайных ситуациях: при действиях спасательных групп в горах или других труднодоступных местностях; при землетрясении и т. д. Для таких ситуаций при разворачивании сети используется данный вид сети.
В структуре сетей часто можно выделить некоторые скопления узлов, в которых узлы между собой имеют более качественную и устойчивую к изменениям связь в сравнении со связью между узлами разных скоплений. При исчезновении случайной связи в сети вероятность того, что качество связи ухудшится между скоплениями, или по-другому кластерами, гораздо выше, чем внутри них. Для того чтобы улучшить передачу данных между узлами из разных кластеров, стоит построить более устойчивую связь между ними, когда между скоплениями узлов есть связь. Если связей между ними нет, то может возникнуть необходимость установить связь между ними.
Имеем, что устройства внутри кластера имеют довольно хорошую связь друг с другом, в то время как связь между кластерами слабая или отсутствует в целом. Например, возникают ситуации, когда несколько организаций должны объединиться для достижения общей цели. Внутри каждой организации устройства имеют связь друг с другом, но, несмотря на необходимость поддержания сети между ее участниками, устройства одной организации не имеют возможности передать нужную информацию другой из-за того, что у устройств разных организаций могут различаться настройки сети. В данной работе для установки связи между кластерами или ее улучшения предлагается использовать специальные устройства, которые могут устанавливать связь со всеми организациями, таким образом обеспечивая связь между ними. Далее обычные устройства будем называть агентами, специальные устройства - дронами, организации — игроками.
В работе рассматривается случай, когда между организациями нет связи, при таком обстоятельстве можно очень просто выделить кластер каждого игрока. Из-за этого в данной работе не рассматривается вопрос, каким способом их лучше определять. Таким образом, возникает модель задачи, в основе которой лежит сетевая структура в виде графа. В его вершинах находятся агенты, принадлежащие различным игрокам. Каждый агент сети принадлежит одному из игроков. Агенты могут построить связь только с агентами того же игрока или с дронами, дроны могут взаимодействовать со всеми. Создание связи между игроками происходит с помощью добавления в граф дронов.
В задаче просматривается теоретико-игровой подход в следствии следующих оснований: во-первых, в задаче организации представляют собой игроков, которые могут выбрать позиции дронов. Во-вторых, они могут выбрать различные позиции, значит у них есть возможность оперировать стратегиями.
В-третьих, для выбора оптимальных позиций есть возможность использовать функцию выигрыша игрока, которая будет отображать качество установленной связи между игроками. Для объединения подсетей, игрокам имеет смысл согласовать свои действия, а не действовать поодиночке. Из этого вытекает использование кооперативной структуры в данной задаче. В итоге игроки образуют коалиционную структуру для улучшения передачи информации между друг другом.
В данной работе сформулирована математическая модель для описанной задачи, предложен алгоритм ее решения и проведен анализ различных вариаций сетей с дронами, включая результаты моделирования в симуляторе сетей ns-3 [2]. Вариации сетей образуют связи с разными наборами агентов в каждом случае, и некоторых характеристик графов, соответствующих этим сетям.
Основной целью работы является составление алгоритма, который объединяет обособленные сети в единую сеть с помощью добавления дополни-тельных узлов, используя теоретико-игровой подход. Набор позиций дронов, который предлагает алгоритм, должен обеспечить лучшие характеристики сети в сравнении с большинством других возможных вариантов. Далее сформулируем задачи, и опишем требования к ожидаемому решению.
В данной работе получена формулировка задачи оптимизации передачи информации в самоорганизующихся мобильных сетях, используя графы в качестве модели сети. Сформулирован алгоритм, способный решить данную задачу. Данный алгоритм использует некоторые геометрические особенности задачи для ее решения. Для подсчета значения функции выигрыша используются меры центральности. Рассмотрена мера центральности через вектор Майерсона, а также некоторые другие, более известные меры центральности: по степени, близости и посредничеству.
Написана и протестирована программная реализация алгоритма на языке программирования python. Также проведено моделирование различных ситуаций в ns-3, полученные результаты проанализированы. Из них следует, что алгоритм при использовании меры центральности через вектор Майерсона или центральности по близости для подсчета значения функции выигрыша дают близкие к оптимальным или оптимальные решения по результатам моделирования и рассмотренной характеристике графа сети. Другие рассмотренные меры центральности не подошли для данной задачи.
Некоторые результаты, полученные в процессе работы над ВКР, опубликованы в [19].
В итоге все поставленные задачи были выполнены. В дальнейшем планируется реализовать другие способы объединения сети, требующие несколько дронов для образования связи между двумя игроками, рассмотреть случаи, когда кластеры уже имеют связь между друг другом. На данный момент подразумевается, что кластеры известны заранее. В общем решении задачи может потребоваться определить кластеры с помощью алгоритма, поэтому рассматривается возможность выяснить подходящие способы определения кластеров для данной задачи. Определив кластеры и образовав новые связи между ними с помощью дронов можно улучшить качество связи между этими кластерами. Также планируется рассмотреть критерии устойчивости [20] вновь созданной при помощи дрона сети. Связь между узлами сети является устойчивой, если между ними существуют два непересекающихся пути или они связаны напрямую.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
