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


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

Работа №128407

Тип работы

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

Предмет

информатика

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

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


Введение 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.


Возникли сложности?

Нужна помощь преподавателя?

Помощь студентам в написании работ!


В работе была решена задача оптимизации передачи информации в сетях MANET с использованием теоретико-игрового подхода и одного из методов машинного обучения. Параметром оптимизации работы сети был выбран диаметр подграфа каждого из игроков, а сеть была представлена в виде графа. Были рассмотрены и проанализированы два алгоритма. Первый алгоритм основан на поиске и отборе единственного решения среди множества оптимальных с помощью метрики betweenness centrality. Второй - «жадный» алгоритм - основан на принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным.
Была написана и протестирована программа, реализующая алгоритм поиска решения задачи. Программа позволяет быстро изменять количество игроков, количество подвижных агентов, а также добавлять новые параметры для того, что определить их влияние на результат. Для сравнения полученных результатов работы двух алгоритмов было проведено моделирование сети с помощью симулятора Network Simulator-3.
В дальнейшем планируется рассмотреть задачу, где учитывается bet-weenness centrality вершин расширенного подграфа, т.е. тех узлов, где рас-положены неподвижные агенты. В зависимости от величины «вклада» каждого узла в сеть принимать решение о постановке дрона. Также планируется протестировать другие меры центральности как критерия отбора решения из множества оптимальных, усовершенствовать «жадный» алгоритм, улучшив качество его работы. Также планируется работа над программной реализацией алгоритма: оптимизация времени работы.



[1] Yu F. R. Cognitive Radio Mobile Ad Hoc Networks. Springer, 2011 507 c.
[2] 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.
[3] Novikov D. A. Games and networks // Automation and Remote Control. 2014. Vol. 75. No 6. P. 1145-1154.
[4] 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 approach to drone positioning // Вестник Санкт- Петербургского университета. Прикладная математика. Информатика. Процессы управления. 2019 Т. 15 Вып. 1 С. 22-38.
[5] Gromova, E., Gromov, D., Timonin, N., Kirpichnikova, A., Blakeway, S. (2016, June). A dynamic game of Mobile Agent placement in a MANET. In 2016 International Conference on Systems Informatics, Modelling and Simulation (SIMS) (pp. 153-158). IEEE.
[6] E. Gromova, A. Vorontsov, S. Blakeway, A. Kirpichnikova. Pareto- optimal Solutions in a Game of Mobile Agents Placements in a MANET. Lancaster Game Theory conference, November, 2019, DOI:10.13140/RG.2.2.17885.64485
[7] Воронцов А. О поиске местоположения дронов для оптимизации работы сети типа MANET. // Процессы управления и устойчивость. 2019. Т. 6. Вып. 1. С. 404-408.
[8] Киреев С. А. Оптимизация передачи информации в самоорганизующихся сетях // Процессы управления и устойчивость. 2020. Т. 7. № 1. С. 381-386.
[9] Newman M. Networks: An Introduction. 1st Edition. Oxford University Press, 2010. 772 p.
[10] Ulrik Brandes. A Faster Algorithm for Betweenness Centrality. // Journal of Mathematical Sociology. 2001 Vol. 25 P. 163-177.
[11] Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн, С.. Алгоритмы: построение и анализ. // 2-е издание, С. 443-481.
[12] В.Е. Алексеев, В.А. Таланов. Графы и алгоритмы. Структуры данных. Модели вычислений. // Москва, Интернет-университет информационных технологий, 2006.
[13] NS-3 Documentation [Электронный ресурс]:URL:https://www.nsnam.org/doxygen/index.html (дата обращения: 21.03.21).
[14] Gromova E., Kireev S., Lazareva A., Kirpichnikova A., Gromov D. MANET Performance Optimization Using Network-Based Criteria and Unmanned Aerial Vehicles. // Journal of Sensor and Actuator Networks.
[15] Лазарева А., Бусел В. Использование различных мер центральности в задаче оптимизации передачи информации в самоорганизующихся сетях // Процессы управления и устойчивость. 2021.
[16] Тимонин Н. О. Одна динамическая игра управления мобильными агентами в сети. // https://nauchkor.ru/uploads/documents/587d36465f1be77c40d58b3f.pdf
[17] Alex Bavelas. Communication Patterns in Task-Oriented Groups. // The Journal of the Acoustical Society of America. 1950. Vol. 22. P. 725-730.
[18] Brin S., Page L. The anatomy of a large-scale hypertextual Web search engine. // Computer Networks and ISDN Systems. 1998. Vol. 30. P. 107-117
[19] Plekhanova T., Gromova E., Gromov D., Kirpichnikova A., Blakeway S. The strategic placement of mobile agents on a hexagonal graph using game theory // Proc. of the IEEE conference ICAT 2017. doi:10.1109/ICAT.2017.8171635.
[20] Мазалов В. В., Чиркова Ю. В. Сетевые игры. 1-е изд. СПб.: Лань, 2018. 320 c.


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



Подобные работы


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