Введение 3
Постановка задачи 4
Обзор литературы 5
Глава 1. Математическая модель 6
1.1 Теоретико-игровой подход 6
1.2 Описание сетевой структуры 7
1.3 Основные определения 10
1.4 Меры центральности и мера PageRank 11
Глава 2. Алгоритм решения задачи 18
2.1 Сеть на прямоугольной решётке 18
2.2 Алгоритм 18
Глава 3. Программная реализация решения задачи 21
3.1 Структура программы 21
3.2 Примеры решения задачи 24
Заключение 29
Список литературы 30
Приложение. Программный код 32

Купить

В данной работе рассматривается задача оптимизации передачи информации в самоорганизующихся сетях различных конфигураций c использованием теоретико-игрового подхода. Под самоорганизующимися подразумеваются сети, образуемые агентами (приёмо-передатчиками) без существующей заранее сетевой инфраструктуры (сотовые вышки, роутеры и т. п.). Часто такие сети находят применение в ситуациях, когда необходимо организовать связь между группами людей на местности, где сотовая связь недоступна. Например, при действиях спасательных групп [6,16] в горах, болотах и других труднопроходимых районах, одни группы используют переносное оборудование для общения с другими, причём, вследствие ограничений на дальность передачи радиосигнала, а также ландшафтных ограничений местности, при необходимости передать некоторое сообщение от одной группы до другой, информация зачастую идёт не напрямую, а через другие группы (узлы сети), которые выступают посредниками, транслируя сообщение по сети. В англоязычной терминологии такие сети называются Mobile Ad Hoc Network или Wireless Ad Hoc Network [10,15] и часто сокращаются до аббревиатур (MANET/WANET).
Основная особенность задачи состоит в том, что не все агенты сети принадлежат одному лицу. В сети присутствует несколько игроков, каждый из которых владеет некоторым набором агентов. Передавать друг другу информацию могут только агенты одного и того же игрока. В рассматриваемом варианте задачи агенты сети неподвижны. Оптимизация работы сети происходит за счёт изменения её структуры путём добавления в неё новых агентов - у каждого из игроков есть дрон с приёмо-передатчиком, который может быть помещён в некоторую позицию и включён в сеть, а кроме того, в отличие от неподвижных агентов, дрон может взаимодействовать с агентами любого игрока.
Таким образом, в постановке задачи вырисовывается теоретико-игровой подход: во-первых, есть множество игроков, владеющих дронами, во-вторых, у каждого из игроков есть стратегия - выбор конкретной позиции, куда поместить дрон, в-третьих, у каждого из игроков есть функция выигрыша, которая характеризует степень оптимизации сети каждого игрока (фактически, в данный момент не совсем корректно говорить, что функция выигрыша уже есть - она будет введена в процессе решения задачи, а здесь имеется ввиду, что для игроков возможно тем или иным образом определить меру улучшения их подсетей).
Здесь рассмотрен кооперативный подход к решению задачи, при котором игроки стремятся улучшить не каждый свою подсеть, а достичь максимального общего улучшения.
Постановка задачи
Основной целью ВКР являлось улучшение характеристик работы сети при помощи теоретико-игрового подхода к вопросу расстановки дополнительных узлов сети, которыми являются подвижные управляемые агенты.
В связи с поставленной целью можно сформулировать следующие основные задачи дипломной работы:
1) Формально описать сетевую структуру MANET/WANET при помощи теории графов;
2) Сформулировать кооперативную (однократную) игру между игроками, которым принадлежат различные агенты сети, намеревающиеся совместными усилиями улучшить характеристики общей сети;
3) Описать алгоритм поиска оптимальных стратегий в кооперативной игре;
4) Детализировать процедуру отбора оптимальных решений в случае их неединственности;
5) Реализовать предложенный алгоритм при помощи программных
средств.
Обзор литературы
Варианты аналогичной некооперативной многошаговой игры с поиском равновесия по Нэшу рассмотрены в работах [7,12]. В [12] было выявлено, что существование такого равновесия не гарантировано и сформулированы некоторые условия, при которых оно существует. В [7] помимо прямоугольной используются также треугольная и шестиугольная решётки. Проводится тестирование с помощью симулятора сетей «Network Simulator 3» и выясняется, что предложенные методы действительно дают значительное улучшение производительности сети.
В [1] рассматривается кооперативный вариант, в котором максимизируется суммарный выигрыш игроков и, таким образом, вычисляется множество оптимальных решений задачи.
В работах [1,7] сеть рассматривается в виде графа, построенного на узлах, расположенных в вершинах решеток заранее определённой конфигурации (шестиугольных или прямоугольных), которые в дальнейшем будем называть неподвижными агентами. Рёбрами в графе соединяются вершины, которые соответствуют узлам сети, способным передавать информацию друг другу, т.е. тем, которые находятся в зоне доступа друг для друга. При решении вопроса об оптимизации передачи данных используются метрики графов, которые необходимо улучшить.
Различные коммуникационные сети, их моделирование с помощью графов, алгоритмы на них, а также сетевые метрики (в частности, меры центральности, используемые в данной работе), сетевые процессы и особенности генерации случайных сетей подробно описаны в книге [14].
Особенности применения теоретико-игрового подхода при моделировании сетевых коммуникационных структур и решении задач на них рассмотрены в книгах [3,10].

Купить