Тема: Одна динамическая игра управления агентами в сети

В работе введена новая постановка некооперативной многошаговой игры управления агентами в сети. Сетевая структура описывается графом, где вершинами являются агенты, а ребра определены как устойчивые связи между агентами [1]. Выигрыш каждого игрока зависит от диаметра под­графа, определенного на вершинах, принадлежащих игроку. Диаметром графа является длина кратчайшего пути между двумя наиболее удален­ными друг от друга вершинами. Диаметр графа используется для оценки максимального времени, требующегося для доставки пакета информации от одного агента к другому.
В данной работе будем предполагать, что каждый каждый игрок име­ет в своем распоряжении одного подвижного агента, который может быть расположен в любой допустимой позиции для образования нового подгра­фа. Целью каждого игрока является уменьшение диаметра результирую­щего расширенного подграфа.
Актуальность данного подхода определяется практической значимо­стью рассмотренной задачи в приложениях, связанных с самоорганизую­щимися одноранговыми мобильными сетями (MANET) [2]. MANET - сеть, без заранее определенной структуры, которая состоит из набора беспровод­ных мобильных узлов или хостов (роль которых, в данной работе, берут на себя агенты игроков). Правильная организация сети MANET играет ключевую роль в таких задачах как восстановление связи в местах при­родных катастроф (землетрясений, наводнений и т. п.), координирование действий спасательных отрядов и т. д. Одной из самых важных проблем, связанных с построением данной сети, является разумное использование ограниченных ресурсов, таких как электромагнитный спектр частот ра­диоволн, время работы аккумуляторов и т. п. Неразумное использование этих ресурсов может привести к ухудшению производительности всей сети в целом. Большая часть исследований, проведенных с применением тео­рии игр в области мобильных сетей, связано с обнаружения вредоносных или не приносящих пользу узлов. В данном же исследовании используется другой подход: рассматривается совместный сценарий поведения узлов для достижения максимальной выгоды.
Основной особенностью данного типа сетей является возможность ре­организовывать структуру сети (топологию, пути передачи данных, рас­пределение спектра и т. д.), основываясь на знаниях предыдущих этапов построения. Таким образом, с течением времени общая производительность сети (скорость доставки пакетов информации, расходы на доставку пакета и т. п.) будет расти.
Все узлы сети имеют некоторую область взаимодействия с други­ми узлами. Таким образом, последовательность узлов может образовывать канал (путь) для передачи данных. Большое количество промежуточных узлов в таком пути может отрицательно сказаться на скорости передачи данных. Или, в некоторых случаях, препятствия на пути (озера, обломки и т. п.) могут вызвать его разрыв. Одним из эффективных способов умень­шения нагрузки на канал или его восстановления является использование беспилотных летательных аппаратов - дронов.
Предметом данного исследования является поиск наилучшего места для внедренных мобильных агентов (дронов). Под наилучшим местом по­нимается такое место, что помещение туда дрона приводит к увеличению производительности сети, а именно уменьшение длины канала передачи данных [3]. В данной задаче жестко ограничено число доступных беспи­лотных летательных аппаратов. В процессе самоорганизации сеть самосто­ятельно определяет оптимальное место для помещения в него подвижного узла. В итоге, две части одного маршрута, состоящие из промежуточных неподвижных узлов, будут соединены между собой беспилотником.
Так как сеть MANET предполагает динамическую топологию: в каж­дый момент времени сеть самостоятельно определят как использовать бес­пилотник наилучшим образом, было принято решение, в качестве инстру­мента исследования, применять теорию позиционных игр [4], [5]. Особенно­стью данного класса игр является учет динамики конфликтно - управляе­мого процесса. Класс конечношаговых игр с полной информацией является одним из классов позиционных игр. Данный класс игр теоретически позво­ляет построить граф игры, наглядно демонстрирующий поведение игроков в конкретных ситуациях. Для класса конечношаговых игр вводится по­нятие абсолютного равновесия по Нэшу, что является усилением понятия равновесия по Нэшу для игр в нормальной форме.
Купить

Анализ проблемы оперативного восстановления связи в местах при­родных катастроф показал, что ключевую роль здесь играет разумное ис­пользование ограниченных ресурсов, в частности, беспилотников (дронов). С учетом динамики развития процесса, было принято решение в качестве сетевой структуры использовать MANET сеть. В данном исследовании ис­пользовался подход, позволяющий рассмотреть совместный сценарий по­ведения узлов сети для достижения максимальной выгоды.
Рассмотрена новая постановка динамической игры управления аген­тами в сети. Данная игра была исследована с применением методов теории многошаговых игр. Найден алгоритм, позволяющий построить дерево ре­шений для конечношаговой игры. Сформулировано условие существования абсолютного равновесия по Нэшу. Приведен пример игры двух лиц с от­сутствием такого равновесия.
Написано программное обеспечение, позволяющее построить дерево решений для конечношаговой игры. Программный продукт протестирован на примере игры двух лиц.
Данное исследование может быть расширено использованием других типов решеток, в частности треугольной и шестиугольной. Данные типы решеток более точно соответствуют архитектуре MANET сетей. Также мо­жет быть введен кооперативный поход, позволяющий более точно описать координирование действий спасательных отрядов.
Некоторые результаты данного исследования нашли отражение в сле­дующих публикациях [8], [9].
Купить