Тип работы:
Предмет:
Язык работы:


Анализ свойств сложных сетей при наличии коалиционных структур

Работа №128208

Тип работы

Бакалаврская работа

Предмет

информатика

Объем работы64
Год сдачи2021
Стоимость4320 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено
70
Не подходит работа?

Узнай цену на написание


Введение 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] вновь созданной при помощи дрона сети. Связь между узлами сети является устойчивой, если между ними существуют два непересекающихся пути или они связаны напрямую.



[1] Bang, A.O.; Ramteke, P.L. MANET: History, challenges and applications. Int. J. Appl. Innov. Eng. Manag. (IJAIEM) 2013, 2, P. 249-251.
[2] Основной веб-сайт ns-3 [Электронный ресурс]: URL:https://www.nsnam.org/ (дата обращения: 26.05.21).
[3] Петросян Л. А., Зенкевич Н. А., Шевкопляс Е. В. Теория игр. 2-е изд. СПб.: БХВ-Петербург, 2014. 432 c.
[4] Novikov, D. A. Games and networks // Automation and Remote Control 2014, 75, 1145-1154 (2014).https://doi.org/10.1134/S0005117914060149.
[5] Тимонин Н. О. Одна динамическая игра управления агентами в сети. URL: https://dspace.spbu.rU/bitstream/11701/4505/1/Diplom.pdf (дата обращения: 26.05.21).
[6] Blakeway S., Gromov D. V., Gromova E. V., Kirpichnikova A. S., Plekhanova T. M. Increasing the performance of a Mobile Ad-hoc Network using a game-theoretic appoach to drone positioning // Вестник Санкт- Петербургского университета. Прикладная математика. Информатика. Процессы управления. 2019. Т. 15. Вып. 1. С. 22-38.https://doi.org/10.21638/11702/spbu10.2019.102.
[7] Gromova E. V., Gromov D. V., Timonin N., Kirpichnikova A. S., Blakeway S. A dynamic game of mobile agents placement on MANET // Proc. of the IEEE conference SIMS 2016. doi:10.1109/SIMS.2016.25.
[8] Воронцов А. О поиске местоположения дронов для оптимизации работы сети типа MANET // Процессы управления и устойчивость. 2019. Т. 6. № 1. С. 404-408.
[9] Киреев С. А. Теоретико-игровая модель передачи данных в беспроводных сетях с различной архитектурой. URL:https://dspace.spbu.ru/bitstream/11701/26456/1/diploma_kireev_serg_3.pdf(дата обращения: 26.05.21).
[10] Киреев С. А. Оптимизация передачи информации в самоорганизующихся сетях // Процессы управления и устойчивость. 2020. Т. 7. № 1. С. 381— 386.
[11] Han Z., Niyato D., Saad D., Basar T., Hjorungnes A. Game Theory in Wireless and Communication Networks. Theory, Models and Applications. New York: Cambridge University Press, 2012. 554 p.
[12] Мазалов В. В., Чиркова Ю. В. Сетевые игры. 1-е изд. СПб.: Лань, 2018. 320 c.
[13] Newman M. Networks: An Introduction. 1st Edition. Oxford: Oxford University Press, 2010. 772 p.
[14] Винокуров В. М., Пуговкин А. В., Пшенников А. А., Ушарова Д. Н., Филатов А. С. Маршрутизация в беспроводных мобильных Ad hoc-сетях // Доклады Томского государственного университета систем управления и радиоэлектроники. 2010. № 2-1 (22). С. 288-292.
[15] Голубева М. А. О совместном использовании узлов децентрализованной беспроводной самоорганизующейся сети. URL:https://dspace.spbu.ru/bitstream/11701/26517/1/Diplom_Golubeva.pdf(дата обращения: 26.05.21).
[16] Плеханова Т. М. Использование теоретико-игрового подхода для повышения производительности сети MANET. URL:https://dspace.spbu.ru/bitstream/11701/11944/1/diplom_plekhanova.pdf (дата обращения: 26.05.21).
[17] Gromova E. V., Kireev S. A., Lazareva A. V, Kirpichnikova A. S., Gromov D. V. MANET Performance Optimization Using Network-Based Criteria and Unmanned Aerial Vehicles // Journal of Sensor and Actuator Networks. doi:10.3390/jsan10010008.
[18] ns-3 Documentation [Электронный ресурс]: URL:https://www.nsnam.org/doxygen/index.html (дата обращения: 26.05.21).
[19] Бусел В. Д., Лазарева А. В. Использование различных мер центральности в задаче оптимизации передачи информации в самоорганизующихся сетях // Процессы управления и устойчивость. 2021.
[20] Laclau M. Robust communication on networks. URL:https://arxiv.org/pdf/2007.00457.pdf (дата обращения: 26.05.21).


Работу высылаем на протяжении 30 минут после оплаты.




©2024 Cервис помощи студентам в выполнении работ