автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Теоретико-игровые алгоритмы формирования децентрализованных беспроводных сетей

На правах рукописи

Федеральное государственное бюджетное учреждение науки Институт проблем управления им. В.А. Трапезникова Российской академии наук

Базенков Николай Ильич

ТЕОРЕТИКО-ИГРОВЫЕ АЛГОРИТМЫ ФОРМИРОВАНИЯ ДЕЦЕНТРАЛИЗОВАННЫХ БЕСПРОВОДНЫХ СЕТЕЙ

Специальность: 05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

13 ФЕВ 2014

Москва 2014

005545153

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте проблем управления им. В.А. Трапезникова Российской академии наук.

Научный руководитель: доктор технических наук, профессор

Кузнецов Олег Петрович,

Официальные оппоненты: Еремеев Александр Павлович,

д.т.н., проф., Национальный исследовательский университет «МЭИ», заведующий кафедрой прикладной математики;

Тарасов Валерий Борисович, к.т.н., доцент, Московский Государственный Технический Университет имени Н.Э. Баумана, заместитель по науке заведующего кафедрой «Компьютерные системы автоматизации производства»

Ведущая организация: Федеральное государственное бюджетное

учреждение науки Институт системного анализа Российской академии наук (ИСА РАН)

Защита состоится « 5 » 2014 г. в 4! час. на заседании диссертаци-

онного совета Д002.226.03 при Институте проблем управления РАН (ИЛУ РАН) по адресу: 117997, Москва, ул. Профсоюзная, д. 65, малый конференц-зал.

С диссертацией можно ознакомиться в библиотеке ИЛУ РАН

Автореферат разослан 2014 г.

Ученый секретарь диссертационного совета Д002.226.03, кандидат технических наук,

Кулинич А.А.

Общая характеристика работы

Актуальность темы исследования. В работе рассматриваются децентрализованные беспроводные сети с нефиксированной топологией, к которым относятся сенсорные сети, мобильные ad hoc сети и др. Они используются для распределенного сбора данных, организации связи в полевых условиях, расширения пропускной способности обычных сотовых сетей и решения других задач, где требуется создать коммуникационную сеть без какой-либо дополнительной инфраструктуры, кроме самих беспроводных узлов. Такие сети состоят из большого числа устройств, как правило, работающих от автономных аккумуляторов. Поскольку заряд аккумуляторов ограничен, задача обеспечения энергоэффективности является одной из основных при управлении ad hoc сетями.

Один из методов увеличения времени жизни сети заключается в формировании эффективной топологии. Узлы настраивают мощности своих передатчиков таким образом, чтобы граф сети обладал заданными свойствами и суммарная мощность была, по возможности, минимальна. Как правило, использование централизованных алгоритмов невозможно по причине отсутствия в сети единого управляющего центра, ограниченного обмена информацией и малых вычислительных мощностей узлов. Среди децентрализованных алгоритмов формирования сетей используются, в том числе, методы теории игр, которые сейчас активно применяются для решения самых разных задач в управлении беспроводными сетями.

Теория игр рассматривает взаимодействие независимых игроков, или агентов, интересы которых могут не совпадать. В компьютерных сетях методы теории игр используются для разработки алгоритмов распределенной оптимизации. Вместо решения централизованной задачи каждому узлу сети задается индивидуальная функция полезности, которую он стремится максимизировать. При этом агенты не координируют свои действия. Такой подход удобен в том случае, когда каждый узел должен использовать только локальную информацию и обмен дополнительными сообщениями между узлами нежелателен.

Теоретико-игровым алгоритмам управления беспроводными сетями посвя-щепо множество исследований. В данной работе развиваются методы, предложенные S. Eidenbenz, S. Zust (Los Alamos National Laboratory, США), V.S. Kumar, A.B. MacKenzie, R.P. Gilles (Virginia Polytechnic Institute and State University,

США). В России работы по применению теории игр в беспроводных сетях проводились в Карельском научном центре РАН, Санкт-Петербургском государственном университете, Нижегородском государственном техническом университете им. P.E. Алексеева.

Использованный в задачах формирования сетей метод последовательных наилучших ответов имеет недостатки, связанные с тем, что получаемые им равновесия могут сильно отличаться от оптимального. Также при использовании этого метода сохраняют устойчивость недопустимые равновесия. Поэтому актуальной задачей является разработка новых методов поиска равновесий, повышающих эффективность алгоритмов.

Объектом исследования является задача формирования связной сети при минимальной суммарной мощности узлов. На плоскости расположено множество узлов, которые могут изменять мощности своих передатчиков. Необходимо назначить каждому узлу такую мощность, чтобы сеть была связна и сумма всех мощностей была минимальна.

Предметом исследования является новый метод выбора агентами своих действий, названный двойным наилучшим ответом. Изучается эффективность этого метода в алгоритмах формирования сети.

Целью диссертационной работы является разработка алгоритмов формирования сети на основе метода двойного наилучшего ответа.

В ходе достижения поставленной цели были решены следующие задачи:

1. Проведен обзор приложений теории игр к задачам управления и оптимизации в беспроводных сетях, в том числе к задаче формирования эффективной топологии сети. Обзор показал, что разработка новых теоретико-игровых алгоритмов формирования сетей является актуальной научной и практической задачей.

2. Предложен новый метод принятия решения агентами - двойной наилучший ответ. Метод основан на идеях теории рефлексивных игр. Доказано, что в задаче формирования связной сети новый метод делает неустойчивыми все недопустимые равновесия.

3. На основе метода двойного наилучшего ответа разработано два алгоритма формирования сети. Показано, что новые алгоритмы получают в среднем

более эффективные равновесия, чем стандартный метод наилучшего ответа.

4. Предложена схема реализации метода двойного наилучшего ответа, исследована ее вычислительная и коммуникационная сложность.

5. Разработан программный комплекс имитационного моделирования процесса формирования сети. Комплекс использовался для исследования эффективности алгоритмов и визуализации результатов.

Связь с планом. Работа выполнена в соответствии с плановой тематикой Института проблем управления РАН им. В.А. Трапезникова и при поддержке грантов РФФИ №№ 10-07-00104, 13-07-00491.

Методы исследования. В основе методологии исследования лежат методы теории игр, а также имитационное моделирование. Полученные аналитические результаты базируются на методах теории графов и теории некооперативных игр. Исследование эффективности алгоритмов формирования сети проведено с помощью имитационного моделирования, методика проведения экспериментов описана в работе.

Научная новизна работы заключается в следующем:

1. Предложен оригинальный метод двойного наилучшего ответа, основанный на подходе рефлексивных игр. Методы стратегической рефлексии ранее применялись в задачах управления социально-экономическими системами. В технических системах стратегическая рефлексия применялась для повышения эффективности проникновения агентов через линию обороны. В задачах формирования сетей методы рефлексивных игр применены впервые.

2. Получена оценка неэффективности равновесия Нэша в рассматриваемой игре формирования связной сети.

3. Доказано, что для игры формирования сети метод двойного наилучшего ответа делает неустойчивыми все равновесия, в которых сеть не связна. Это эквивалентно тому, что в рассматриваемой игре все равновесия, не оптимальные по Парето, будут неустойчивыми при использовании двойного наилучшего ответа.

4. Разработанные алгоритмы формирования сети показывают лучшие результаты, чем традиционный теоретико-игровой алгоритм. Это позволяет предположить, что они могут быть применены и в других задачах, где используются методы теории игр.

5. Получены оценки сложности разработанных алгоритмов и базового алгоритма наилучшего ответа. Предложенный алгоритм поиска наилучшего ответа для рассматриваемой игры нигде в литературе не описан.

Практическая значимость работы определяется разработанным комплексом имитационного моделирования, а также эффективностью разработанных алгоритмов, что позволит сэкономить мощность и продлить время жизни реальных беспроводных сетей. Разработанные в работе процедуры могут быть адаптированы для различных теоретико-игровых задач, а также для анализа социальных сетей.

Достоверность результатов обусловлена использованными методами теории игр, теории графов и имитационным моделированием. Использованный программный комплекс, исходные тестовые примеры и полученные данные экспериментов находятся в открытом доступе, что обеспечивает достоверность результатов исследования.

Положения, выносимые на защиту:

1. Предложен новый метод принятия решения агентом, названный двойным наилучшим ответом. Доказано, что для рассматриваемой игры формирования сети предложенный метод делает неустойчивыми все неоптимальные по Парето равновесия Нэша. Для рассматриваемой игры получена не встречавшаяся ранее оценка для отношения затрат в наихудшем равновесии Нэша к оптимальному равновесию.

2. На основе предложенного метода разработано два алгоритма формирования беспроводной сети. В первом алгоритме используется статический метод принятия решения, во втором агенты динамически переключаются между обычным наилучшим ответом и двойным наилучшим ответом. Показано, что разработанные алгоритмы позволяют сузить множество получаемых равновесий по сравнению с базовым алгоритмом наилучшего ответа.

3. Исследована эффективность предложенных алгоритмов. Показано, что разработанные алгоритмы формируют более эффективные сети, чем известный теоретико-игровой алгоритм наилучшего ответа.

4. Предложены схемы реализации алгоритмов базового наилучшего ответа и двойного наилучшего ответа. Получены оценки вычислительной и коммуникационной сложности предложенных алгоритмов.

5. Разработан программный комплекс имитационного моделирования, имеющий потенциальные приложения для анализа других теоретико-игровых задач, а также для анализа процессов в социальных сетях.

Апробация работы. Результаты диссертационной работы докладывались на семинарах ИПУ РАН, VII Всероссийской школе-семинаре молодых ученых «Управление большими системами» (Магнитогорск, 2011), I и II Международных школах-семинарах молодых ученых «Интеллектуальные системы и технологии: проблемы и перспективы» (Тверь-Протасово, 2012,2013), VI Международной конференции «Game Theory and Management» (Санкт-Петербург, 2012), Международном семинаре «Networking Games and Management» (Петрозаводск, 2012), VI Всероссийской мультиконференции по проблемам управления (Дивноморское, 2013).

Программный комплекс прошел апробацию и используется в аналитическом агентстве «Новые стратегии», что подтверждается актом о внедрении.

Публикации. По теме диссертационной работы опубликовано 11 печатных работ, в том числе 2 в рецензируемых изданиях, рекомендуемых ВАК. Личный вклад автора. Все результаты получены автором. Объем и структура работы. Диссертация состоит го введения, 3 глав, заключения, библиографии, включающей 122 наименования, и приложения. Общий объем диссертации составляет 125 страниц.

Содержание работы

Во введении обоснована актуальность диссертационной работы, сформулированы цели и задачи исследования, перечислены полученные результаты, показана научная и практическая значимость работы и представлены положения, выносимые на защиту.

В первой главе диссертации проведен обзор исследований, посвященных применению теории игр к задачам управления и оптимизации в беспроводных сетях. Начиная с 2003-2004 годов наблюдается существенный рост исследовательской активности по данной тематике.

Проведенная классификация исследований показала, что используется широкий спектр методов теории игр. В данной работе рассматриваются методы некооперативной теории игр, которая исследует взаимодействия независимых субъектов, или агентов, стремящихся максимизировать свой выигрыш.

Далее рассматривается определенный тип беспроводных сетей - ad hoc сети, иногда называемые самоорганизующимися. Сетями ad hoc (лат. созданный для данного случая) называют беспроводные сети, для создания которых не требуется никакой дополнительной инфраструктуры, кроме самих беспроводных узлов. Такие сети используются для связи в полевых условиях, распределенного сбора и обработки данных, расширения пропускной способности сотовых сетей и т.д. Рассмотрены основные типы самоорганизующихся сетей, а также некоторые актуальные задачи.

Устройства в таких сетях часто работают от автономных аккумуляторов, поэтому много внимания уделяется увеличению времени жизни сети. Управлением топологией (topology control) называют методы повышения знергоэффективно-сти за счет формирования и поддержания эффективной топологии сети. Здесь рассматривается только этап формирования сети.

Узлы сети могут устанавливать разные мощности своих передатчиков. Необходимо получить такой вектор мощностей узлов р, чтобы граф сети д(р) обладал заданными свойствами: связностью или k-связностью, ограниченной длиной путей и максимальной степенью узлов, разреженностью связей. При этом обычно стараются минимизировать суммарную мощность узлов.

Большинство задач формирования оптимальной сети относятся к классу ЛГР-трудных. Поэтому вместо поиска точного решения используются эвристиче-

ские алгоритмы, которые можно условно разделить на геометрические и графовые.

Геометрические используют модель сети, в которой зона действия передатчика представляет собой круг радиуса г. Далее формируется геометрический граф, обладающий некоторыми полезными свойствами. Алгоритм LMST формирует локально-минимальное остовное дерево, алгоритм СВТС - так называемый граф Яо (Yao graph). Такие алгоритмы требуют наличия информации о расположении узлов, что часто не выполнимо. Графовые алгоритмы функционируют, не используя геометрическую модель сети, а оценивая состояние связи с каждым из соседей. Например, в алгоритме ХТС каждый узел ранжирует своих соседей по качеству связи, затем устанавливает к лучших связей.

Перечисленные алгоритмы имеют ряд недостатков. Во-первых, для успешной работы все узлы сети должны использовать один алгоритм, что может создать проблемы, коща в сети используются узлы разных производителей, поскольку единых стандартов формирования топологии пока не существует. Во-вторых, может возникнуть необходимость модифицировать критерий качества. Например, кроме связности сети учесть еще и длину путей. В третьих, разные узлы могут иметь разную емкость источников питания, следовательно, "цена" мощности для них может быть разной. Один из возможных подходов к решению этих проблем заключается в переходе к задачам и методам теории игр.

Теоретико-игровые алгоритмы отличаются тем, что предполагают каждый узел самостоятельным агентом, не координирующим свои действия с другими узлами. В работах, исследующих теоретико-игровые алгоритмы, наиболее часто применяется схема поиска равновесия, основанная на последовательном применении узлами правила наилучшего ответа. Этот метод имеет ряд недостатков. Во-первых, полученное равновесие часто сильно отличается от оптимального. Во-вторых, при неправильных начальных условиях или случайной ошибке алгоритм может получить недопустимое равновесие, когда сеть не связна. Данная работа посвящена исследованию нового правила выбора действия, призванного повысить эффективность теоретико-игровых алгоритмов.

Во второй главе приводится формальная постановка задачи, даются определения основных понятий теории игр, описываются предложенные алгоритмы формирования сети и исследуется их эффективность.

Модель сети. Сеть состоит из множества узлов, N = {1,...,п}, расположенных на плоскости. Каждый узел г € N может изменять мощность своего передатчика. Мощности всех передатчиков задаются вектором р = (рь... ,рп),

Узел г может успешно передавать данные узлу, находящемся на расстоянии г, если выполняется условие

где р, - мощность передатчика узла г, р > 1 - коэффициент, учитывающий требуемое качество передачи, а > 2 - показатель затухания сигнала. Величина показателя а зависит от физических свойств среды и наличия препятствий: деревьев, домов, людей. В воздухе при отсутствии препятствий а = 2. Определение 1. Множество узлов, для которых выполняется условие (1), если узел г установит свою максимальную мощность р'™х, будем называть соседями узла г и обозначать как Щпах.

Определение 2. Графом коммуникаций, порожденным вектором мощностей р, называется неориентированный граф д(р) — (ЛГ, Е(р)), где N - множество вершин, соответствующих узлам сети, Е(р) - множество ребер, где {г,з) 6 Е(р),

если условие (1) выполняется для обоих узлов г и

(

На рисунке 1 проиллюстрирована модель образования сети. Сплошными линиями показаны неориентированные ребра. Пунктирными линиями и стрелками показаны ориентированные ребра, которые означают, что мощность только одного узла достаточна для образования связи.

Вектор мощностей, в котором каждый узел устанавливает свою максимальную мощность pi = р™ах, обозначим какртах. Граф, порождаемый этим вектором, обозначим как дтах д(рпшх).

Основным критерием качества является суммарная мощность узлов

которая соответствует среднему времени работы узлов. Другим критерием каче-

Рг 6 [0,р™4.

Р1 > рга,

(1)

(2)

ства является максимальная мощность в сети

Стах(р) = тахрь (3)

tejv

которая определяет время выхода из строя первого узла. Дополнительно используется оценка интенсивности в сети как

/(р) = max Ii (р), (4)

tsN

где /¿(р) = |{j £ N | pj > %}|, hji - минимальная мощность, необходимая для образования связи (j,i).

Задача формирования топологии формулируется как

min

¿елг

Р£€[О,РГЧ (5)

д(р) — связный граф.

Задача (5) относится к NP-трудным, и ее точное решение в реальных условиях невозможно. В данной работе исследуются децентрализованные алгоритмы ее решения, основанные на методах теории игр.

Игра формирования топологии. Введем основные понятия теории игр. Определение 3. Игрой в нормальной форме называется тройка

Г =(N,{Ai}ieN,{u¡}ieli), (6)

где

1. N = {1,..., п} - множество игроков, или агентов;

2. Ai - множество возможных действий г-го агента. Декартово произведение А = x¿e./v.A¿ называют множеством возможных исходов игры;

3. щ: А -> R - функции полезности задают выигрыши агентов в каждом из возможных исходов игры.

Профиль действий всех агентов обозначим как а — (ai,..., ап). Всех агентов за исключением г будем обозначать как —г, и профиль их действий a_¿ = (ai,..., a,_i, ai+i,..., а,,) € A-i = хj^Aj будем называть обстановкой для агента г. Иногда профиль всех действий удобно обозначать a = (a„ a-i). Определение 4. Профиль действий а* € А называется равновесием Нэша, если для каждого агента г G N и для любого действия a¿ € A¿, a¡ a* выполняется условие

«i(ai, alj) < Ui(a¡, al,) (7)

Определение 5. Множеством наилучших ответов (best response) агента i £ N на обстановку a_¿ 6 называется множество

BRi(a-i) = argmaxu¿(x,a_¡). (8)

xC

Если множество наилучших ответов всегда содержит только один элемент, выражение (8) задает функцию наилучших ответов. Для игры, рассматриваемой в данной работе, всегда выполняется этот случай. Если в системе установилось равновесие Нэша, то ни один агент не сможет увеличить полезность, в одиночку изменив свое действие, такое состояние будет устойчивым. Определение 6. Профиль действий a 6 А доминируется профилем а' £ А, если щ(а') > щ(а) Vi в N и 3i € N : щ(р') > щ(р).

Определение 7. Профиль действий а Е А является оптимальным по Парето, если он не доминируется никаким другим профилем a' G А.

Состояние а оптимально по Парето, если в нем нельзя увеличить выигрыш ни одного агента, не ухудшив при это выигрыш другого агента.

Далее описывается игра формирования связного неориентированного графа, известная из работы (Komali, MacKenzie, Gilles, 2008). Агентами являются узлы сети N, действием агента г G N является мощность его передатчика Pi 6 [0,р-"а1]. Обозначим множества действий узлов как Р, = [0, j/¡iax]. Игра формирования топологии задается тройкой

где Р = Хщ,\гРг - множество исходов игры. Функция полезности щ: Р —> К отражает требование связности сети и уменьшения мощности передатчика:

где /,(з(р)) - число узлов, с которыми узел i связан в графе д{р). M > inax^v Р?аж отражает приоритет обеспечения связности сети над минимизацией мощности.

В работе (Komali, MacKenzie, Gilles, 2008) доказано, что игра формирования топологии имеет хотя бы одно равновесие Нэша и эти равновесия соответствуют локальным минимумам суммарной мощности (2). Проблема заключается в том, что поиск равновесия, являющегося глобальным минимумом, остается NP-трудной задачей. А оставшиеся равновесия отличаются по своей эффективности. Более того, некоторые равновесия не являются допустимыми решениями задачи (5), поскольку граф сети в них не связен.

Определение 8. Недопустимым равновесием Нэша в игре формирования топологии назовем такой вектор мощностей р*, что граф д{р*) не связен, когда существует такой вектор мощностей р', при котором д(р') - связный граф. Утверждение 1. Любое недопустимое равновесие Нэша р* не является Парето-оптимальным.

В данной диссертационной работе получена оценка отношения затрат в наихудшем допустимом равновесии к оптимальному.

(9)

Ui(p) = Mfj(g(p)) - pu

(10)

S+s 8 8 8 + s 8 8

a) 6)

Рис. 2. Равновесия в линейной сети, а) наихудшее; б) оптимальное

Утверждение 2. Существует такое расположение узлов, при котором наихудшее возможное равновесие отличается от оптимального в 0(na_1).

Иллюстрацией этого утверждения служит сеть на рисунке 2. Далее рассматриваются алгоритмы формирования сети и равновесия, которые они получают.

Алгоритмы формирования сети. В литературе известен алгоритм поиска равновесия, основанный на итерационном применении наилучшего ответа (8). Все узлы начинают с максимальной мощности, затем поочередно выбирают новую мощность как наилучший ответ на текущую обстановку до тех пор, пока хотя бы один узел продолжает изменять мощность. Для игры формирования топологии наилучший ответ узла единственен, поэтому выбор мощности всегда определяется однозначно.

Этот алгоритм сходится к равновесию Нэша за п операций изменения мощности, а также сохраняет связность исходного графа дтах. Но полученное равновесие зависит от порядка действий узлов и, как следует из утверждения 2, может отличаться от оптимального в 0(rí"~l) раз. Другой недостаток этого алгоритма заключается в том, что, если вследствие ошибки установится недопустимое равновесие, оно останется устойчивым, и алгоритм придется запускать заново или вводить специальные механизмы восстановления связности.

В работе предлагается новый метод выбора агентом своего действия, названный двойным наилучшим ответом. Замена в векторе а = (a¿, a_¿) действия агента i на х € A¿ будет обозначаться как ot,x = (х, a_¡). Обстановка для узла j в этом новом векторе действий будет обозначаться как

afj = (х, a-i)_j = (аь ..., а,-_их, ai+i,..., aJ+i,..., ап).

Допустим, агент i выбрал действие х е Л;, и каждый другой агент j G Аг, j ф i выбирает свой наилучший ответ на новую обстановку all* = (i, a_¿)_;-. Тогда

вектор всех таких наилучших ответов будет обозначаться как

BR-itf*) ={BRl(al\),..., (<£»_„), BRi+i(af(i+1)),..., BRn(dlxn))

(П)

Определение 9. Двойным наилучшим ответом (double best response) агента г на обстановку а_,; называется действие

где BR-i(al,x) - вектор одновременных наилучших ответов других агентов на выбор агентом i действия х.

Определение 10. Рефлексивным мпожеством (reflexive set) Ri агента i назовем множество агентов, для которых i может вычислить наилучший ответ (8). Определение 11. Локальным двойным наилучшим ответом (local double best response) агента г на обстановку a_¿ называется действие

где одг\/г. - действия агентов, не входящих в ñ¿, BRrJ^х, a_¿) - наилучшие ответы агентов, входящих в Д,.

В системах с небольшим числом агентов может использоваться правило (12). В качестве примера можно привести управление группой мобильных роботов или мобильной ad hoc сетью с небольшим числом узлов. Сенсорные сети, как правило, состоят из десятков и сотен узлов, поэтому в них возможно использовать только локальную версию двойного наилучшего ответа. В данной работе рефлексивным множеством узла i считаются все соседи узла /?; = N["ax.

По аналогии с базовым алгоритмом наилучших ответов предложен алгоритм IDBR (Iterated Best Response), использующий правило двойного наилучшего ответа. В отличие от базового алгоритма, если узлы сети используют двойной наилучший ответ, ни одно из недопустимых равновесий Нэша не будет устойчивым.

Определение 12. Вектор действий а* является устойчивым к двойному наилуч-

DBRi(a-i) = argmaxu¡(a;, BR-i(a1,x)),

(12)

LocDBRi¡Ri{a-i) = arg maxM¡(i, aN\R¡, BRR¡(r., a_¿))

(13)

Алгоритм 1IDBR - Iterated Double Best Response _______

1. (Инициализация). Все узлы устанавливают произвольную начальную мощность р" € [О, pi""1], формируется начальный граф д° = д(р°).

2. (Настройка мощности). Узел г, выбранный в соответствии с некоторым произвольным порядком, изменяет мощность по правилу (12)

p|+i = DBRilpli) (или LocDBRi^.ipli))

3. (Обновление сети). Формируется новый граф <?t+1 = з(р'+1,р!^), t — t + 1

4. (Остановка). Шага 2 и 3 продолжаются, пока хотя бы один узел изменяет мощность

5. (Завершение). Если граф д' не связный, все узлы переходят на правило наилучшего ответа (8). Переход к шагу 2.

шему ответу, если для любого агента г е N а,* =

Утверждение 3. Если р* - равновесие Нэша и граф д(р') не связен, тогда 3 г € N : ВВЪШ ф р\-

Следствие 1. В игре формирования топологии все не оптимальные по Парето равновесия не будут устойчивыми к двойному наилучшему ответу.

Алгоритм двойных наилучших ответов устойчивее к порядку выбора узлов, чем базовый алгоритм наилучших ответов. Для сети на рисунке 2 алгоритм ГОВЯ при любом порядке действий узлов и любой начальной мощности получает оптимальную сеть. Но это выполняется не для любой сети.

Утверждение 4. Затраты С1оШ (р**) в равновесии р", полученном алгоритмом ШВИ, в худшем случае не. меньше затрат СМа1(р*) в равновесии р", полученном алгоритмом твя.

К сожалению, свойство наилучшего ответа сохранять связность сети не выполняется для двойного наилучшего ответа. Это иллюстрирует рисунок 3. Узлы с и с1, расположенные близко друг от друга, готовы установить "дешевую" связь (с, Л) и "надеются" на то, что сосед установит "дорогую" связь с узлом Ь. Алгоритм двойного наилучшего ответа стабилизируется и получает сеть на рисунке За.

Вычислительные эксперименты показывают, что после запуска одной итерации алгоритма наилучших ответов на шаге 5 связная сеть формируется всегда. Не доказано, что алгоритм ГОВЯ остановится на шаге 3. Однако эксперименты показывают, что всегда можно произвести искусственную остановку алгоритма

Рис. 3. Остановка двойного наилучшего ответа на несвязной сети а) сеть, на которой останавливается алгоритм; б) субоптимальное равновесие Ctoiai = 5+2с, в) оптимальное равновесие Ctotal — 5 + е

по истечению некоторого счетчика времени, после чего всегда формируется связная сеть. Строгое доказательство этих свойств алгоритма IDBR пока получить не удалось.

В работе предложен другой алгоритм, VDBR (Variable Best Response), который гарантированно останавливается.

Алгоритм 2 VDBR - Variable Double Best Response

1. (Инициализация). Узлы устанавливают начальную мощность pj € [0,pj"os:], формируется начальный граф д° — д(р°). Устанавливается счетчик counti = mdbr.

2. (Настройка мощности). Узел г вычисляет свой наилучший ответ pf — P'Ri{p'lii) Если Ui(p^,pti) > «¡(Р'.Р-Л или counti = 0, то p|+l = pf'

Иначе pj+1 = DBRiifLi) (или LocDВ(р'_{)), counti = counti — 1

3. (Обновление сети). Аналогично алгоритму 1

4. (Остановка). Шаги 2 и 3 продолжаются до тех пор, пока хотя бы один узел изменяет мощность

Утверждение 5. Алгоритм VDBR всегда останавливается, и финальное состояние р" есть равновесие Нэша.

Из утверждения 5 не следует, что алгоритм УБВЯ сходится к связной сети, но это наблюдается экспериментально, даже если Уг 6 N = 0, а •т<гЬг = 1.

Исследование эффективности алгоритмов. Эффективность предложенных алгоритмов исследовалась в численных экспериментах. Для проведения экспериментов использовался разработанный программный комплекс имитационного

1ВЯ -В.....ЬосШВК—*— 1РВЯ --.-■■- VDBR1 —УРВЯ2 —6— УРВЮ —— МСТ)

8

•I

2

2

О

О

10 20 30 40 50 #пойе5

10 20 30 40 50 #пос!ез

а)

б)

Рис. 4. Суммарная мощность узлов, СМсЛ а) алгоритмы с постоянным правилом выбора мощности; б) с переменным правилом

моделирования.

Алгоритмы сравнивались по четырем критериям эффективности: суммарная мощность узлов, максимальная мощность, уровень помех в сети и время сходимости. Изменение основного критерия эффективности - суммарной мощности узлов - показано на рисунке 4. Время сходимости алгоритмов показано на рисунке 5. По вертикальной оси отложено количество итераций, требующихся для остановки алгоритма. Одна итерация включает п шагов обновления сети. Графики остальных показателей приводятся в диссертации. На графиках по оси абсцисс отложена плотность сети, измеряемая как количество узлов в квадрате 100 на 100. По оси ординат отложены значения критериев. Показаны средние значения и среднеквадратичные отклонения критериев для каждой плотности узлов. Графики немного смещены относительно оси абсцисс, чтобы отрезки, показывающие отклонения от среднего, не перекрывались.

Условные обозначения алгоритмов приведены в верхней части рисунка. Алгоритмы с постоянным правилом выбора мощности: ГВ11- базовый алгоритм наилучшего ответа; ГОВЯ - двойного наилучшего ответа; ЬосГОВИ - модификация с локальным правилом двойного наилучшего ответа. Алгоритмы с переменным правилом: УОВКЛ, \DBR2, \ТШЮ - максимально допустимое число использований двойного наилучшего ответа таЬт меняется от 1 до 3. При дальнейшем увеличении то<гЬг эффективность алгоритма перестает изменяться, и эти резуль-

-*- 1Вв......£ 1-0с1РВК-~*— ЮВЯ.....у.....УРВЩ -+- УРВ1*2 —7-- УРВЯЗ|

12 10 8

ш

I 6

4 2 О

10 20 30 40 50 #пос1е5

£ 6

4 2 О

10 20 30 40 50 «посЭеБ

а)

б)

Рис. 5. Время сходимости алгоритмов а) с постоянным правилом выбора мощности; б) с переменным правилом

таты на графиках не указаны. В алгоритмах с переменным правилом выбора мощности использовалась только локальная модификация двойного наилучшего ответа (13).

Все алгоритмы с двойным наилучшим ответом демонстрируют лучшие результаты, чем базовый алгоритм. Все теоретико-игровые алгоритмы формируют менее эффективные сети, чем минимальное остовное дерево. На рисунках видно, что замена двойного наилучшего ответа на его локальную модификацию снижает эффективность алгоритма. Алгоритм с переменным правилом и локальным двойным наилучшим ответом при тп'1Ьг > 2 показывает немного лучшие результаты, чем алгоритм с глобальным наилучшим ответом.

Можно сделать вывод, что для создания прикладных алгоритмов формирования топологии лучше всего подходит алгоритм с переменным правилом выбора мощности. Также при использовании переменного правила сокращаются интервалы, в течение которых нарушена связность сети. Фактически, двойной наилучший ответ можно использовать в те моменты, когда не требуется передавать данные. Тогда допустимо нарушить связность сети на короткий период. В случае возникновения необходимости срочной передачи данных все узлы могут переключиться на обычный наилучший ответ и за 1 итерацию сформировать связную сеть.

В третьей главе исследуется вычислительная сложность алгоритмов и опи-

сывается программный комплекс имитационного моделирования. Приводится основная схема формирования сети, алгоритм BestResponse вычисления базового наилучшего ответа и DoubleBestResponse для вычисления двойного наилучшего ответа.

Утверждение 6. Алгоритм BestResponse вычисляет наилучший ответ (8) узла с функцией полезности (10) и время работы в худшем случае составляет 0(N + Е) для графа сети д = (N, Е).

Для вычисления наилучшего ответа в игре с полезностями 10 узел i должен обладать информацией о текущей топологии сети д(р), своей окрестности в графе предложений дДр) и стоимости образования связей со своими соседями hij j 6 Сложность 0(N + Е) обусловлена тем, что в ходе алгоритма в худшем случае выполняется поиск связных компонент, которым принадлежат соседи узла. При замене fi(g(p)) в функции полезности на локальную оценку, например в к-окрестности узла г, сложность уменьшится соответственно.

Утверждение 7. Вычисление двойного наилучшего ответа узла г в графе д = (N, Е) требует 0(VR(N+E)) операций, где R = |Яг| - мощность рефлексивного множества узла, V = liVJ™1 j - число соседей узла. В ходе вычислений требуется обмен 2VR служебными сообщениями.

В данной работе в качестве рефлексивного множества использовались соседи узла, Ri = NJ™". Для данного случая двойной наилучший ответ требует 0(V2(N + Е)) операций и обмена 2V2 сообщениями. Для плотных сетей, когда Е ~ N2 и V ~ N, сложность вычисления двойного наилучшего ответа возрастает до 0(N5). В другом крайнем случае, коща сеть разрежена, то есть Е ~ N и V = const, сложность двойного наилучшего ответа становится равной 0{N).

Сложность обусловлена тем, что в предложенном алгоритме при поиске мощности перебираются все соседи узла. В теле цикла перебора соседей выполняется вычисление R наилучших ответов. Каждое вычисление наилучшего ответа требует 0(N + Е) операций. Узел не обладает информацией, необходимой для вычисления наилучших ответов, и запрашивает результат у своих соседей, для чего требуется обмен служебными сообщениями.

Утверждение 8. Время вычисления двойного наилучшего ответа в алгоритме VDBR составляет 0(V2N), если R, = N?ax.

70

50

80

60

20

40

30

10

10 20 30 40 50 60 70 60

90

10 20 30 40 50 60 70 80

90

а)

б)

Рис. 6. Примеры сетей, полученных а) базовым алгоритмом; б) VDBR, mdbr = 3

Доказано, что для алгоритма YDBR сложность вычисления двойного наилучшего ответа всегда не хуже 0(V2N), что для плотных сетей преобразуется в 0(N3), а для разреженных в O(N).

Далее в третьей гааве проводится обзор существующих систем моделирования ad hoc сетей, обосновывается необходимость разработки отдельного комплекса для исследования эффективности предложенных алгоритмов, приводится описание комплекса и методики проведения экспериментов.

Комплекс реализован как библиотека функций MATLAB и доступен в интернете по адресу https://sourceforge.net/projects/netgames/. Библиотека включает функции генерации исходных данных, имитации процесса формирования сети рассмотренными алгоритмами и функции визуализации результатов. На рисунке 6 приведен пример работы алгоритмов для сети из 25 узлов.

В заключении приводятся основные выводы по результатам работы, обозначаются возможные направления дальнейших исследований.

Основные результаты и выводы

1. Формирование эффективной топологии является одним из методов увеличения времени жизни ad hoc сетей при работе от автономных аккумуляторов. Проведенный обзор алгоритмов формирования сети показал, что разработка новых методов поиска равновесий, повышающих эффективность алгоритмов, является актуальной научной задачей.

2. Исследована предложенная в литературе игровая формулировка задачи формирования связной сети при минимизации суммарной мощности передатчиков. Доказано, что в рассматриваемой игре наихудшее равновесие может отличаться от оптимального в 0(п"-1) раз, и что в игре существуют недопустимые равновесия, которые остаются устойчивыми при применении базового теоретико-игрового алгоритма наилучшего ответа.

3. Предложен новый теоретико-игровой метод принятия решения агентом, названный двойным наилучшим ответом. Доказано, что при использовании двойного наилучшего ответа любое недопустимое равновесие в игре формирования топологии перестает быть устойчивым. Это эквивалентно тому, что устойчивым может бьггь только равновесие, оптимальное по Парето.

4. На основе двойного наилучшего ответа разработано два алгоритма формирования сети: IDBR (Iterated Best Response) и VDBR (Variable Double Best Response). Показано, что оба алгоритма сходятся, получают в результате связные сети и более устойчивы к порядку действий узлов, чем базовый алгоритм. Исследована эффективность алгоритмов в сравнении с базовым алгоритмом и минимальным остовным деревом. Все алгоритмы, использующие двойной наилучший ответ, показали лучшие результаты, чем базовый алгоритм. Алгоритм VDBR превосходит алгоритм IDBR и является наиболее перспективным для практической реализации.

5. Предложены схемы реализации алгоритмов, исследована их вычислительная сложность. Вычислительная сложность наилучшего ответа составляет О (ЛГ -f Е), N - число узлов, Е - число ребер в текущем графе сети. Предложен алгоритм вычисления двойного наилучшего ответа, использующий такой же объем локальной информации, что и наилучший ответ, его сложность составляет 0(V2(N + £)), V - число соседей узла. Доказано,

что при использовании в алгоритме VDBR сложность составляет 0(V2N) операций. Предложенная реализация двойного наилучшего ответа требует обмена 2V2 служебными сообщениями.

6. Разработан комплекс имитационного моделирования, который использовался для исследований эффективности алгоритмов. Данный комплекс представляет собой библиотеку функций MATLAB, которая может быть использована в исследованиях других процессов формирования технических и социально-экономических сетей.

Список публикаций

Публикации в ведущих рецензируемых журналах, входящих в перечень ВАК

1. Базенков Н. И. Динамика двойных наилучших ответов в игре формирования топологии беспроводной ad hoc сети //Управление большими системами. Выпуск 43. -2013. -С.217-239.

2. Базенков Н. И., Губанов Д. А. Обзор информационных систем анализа социальных сетей // Управление большими системами. Выпуск 41. - 2013. - С. 357-394.

Тезисы докладов на международных конференциях

3. Bazenkov N. Reflexive Behavior in Topology Control for Ad Hoc Networks II Collected abstraets of 6th International Conference on Game Theory and Management (GTM). - 2012. - P. 39-41.

Публикации в трудах всероссийских конференций

4. Базенков Н.И. Динамика двойных наилучших ответов в игре формирования топологии беспроводной ad hoc сети // Труды 6-й Всероссийской мультиконференции по проблемам управления (МКПУ-2013). - 2013. - Т. 4. - С. 81-85.

5. Базенков Н.И., Яхин А.Ш. Экспериментальное исследование цитирования внешних сайтов в русскоязычной блогосфере // Труды 5-ой конференции «Управление в технических, эр-гатических, организационных и сетевых системах» (УТЭОСС-2012). - 2012. - С. 872-875.

6. Базенков Н.И. Обзор теоретико-игровых моделей обеспечения безопасности информационных систем И Труды 5б-й научной конференции МФТИ. Радиотехника и кибернетика. -2013.-С. 124-125

7. Базенков Н.И. Рефлексия в задаче управления топологией беспроводной сети И Труды 55-й научной конференции МФТИ. Радиотехника и кибернетика. - 2012. - Т. 1. - С. 46-47.

Публикации в трудах молодежных научных школ

8. Базенков Н.И. Динамика двойных наилучших ответов в игре формирования топологии беспроводной ad hoc сети II Труды П-й Международной летней школы-семинара по искусственному интеллекту для студентов, аспирантов и молодых ученых «Интеллектуальные системы и технологии: современное состояние и перспективы» (ISyT'2013). - 2013. -С. 111-116

9. Базенков Н.И. Теоретико-игровая постановка задачи контроля эгоистичного поведения узлов в многоагентных сетях передачи данных. // Материалы VIII Всероссийской школы-конференции молодых ученых «Управление большими системами». - 2011. - С. 130-133.

10. Базенков Н.И. Задача стимулирования кооперации узлов в многоагентных беспроводных сетях в условиях ограниченной пропускной способности // Труды международной летней школы-семинара «Интеллектуальные системы и технологии: современной состояние и перспективы» (ISyT'2011, Тверь). Тверь-Протасово: Издательство Тверского государственного технического университета - 2011. - С. 110-118.

11. Базенков Н.И. Теоретико-игровая модель кооперации узлов в мобильных Ad Нос сетях. // Аннотации докладов Научной сессии НИЯУ МИФИ 2011. - 2011. - Т. 3. - С. 60.

В работе [2] автором проведен обзор программных пакетов для сетевого моделирования, используемых в научных исследованиях. В работе [5] автором получены все основные результаты.

Подписано в печать:

27.01.2014

Заказ № 9316 Тираж - 100 экз. Неман, трафаретная. Типография «11-М ФОШЛТ» ИМИ 7726.4.10900 115230, Моекна. Варшавское ш„ 36 (499) 788-78-56 www.autorcferat.ru

Федеральное государственное бюджетное учреждение науки Институт проблем управления им. В.А. Трапезникова Российской академии наук

На правах рукописи

04201456455

О

Базенков Николай Ильич

ТЕОРЕТИКО-ИГРОВЫЕ АЛГОРИТМЫ ФОРМИРОВАНИЯ ДЕЦЕНТРАЛИЗОВАННЫХ БЕСПРОВОДНЫХ СЕТЕЙ

Специальность: 05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель: доктор технических наук, профессор Кузнецов Олег Петрович

Москва 2014

Содержание

Стр.

ВВЕДЕНИЕ 4

Глава 1. ТЕОРИЯ ИГР И БЕСПРОВОДНЫЕ СЕТИ 13

1.1. Теория игр в беспроводных сетях......................................13

1.1.1. Актуальность направления............................................13

1.1.2. Классификация задач..................................................16

1.1.3. Примеры приложений ................................................20

1.1.4. Дискуссионные вопросы..............................................26

1.2. Самоорганизующиеся беспроводные сети ............................27

1.2.1. Классификация самоорганизующихся сетей........................27

1.2.2. Архитектура и принципы функционирования......................32

1.3. Управление топологией беспроводных сетей..........................36

1.3.1. Задачи управления топологией........................................36

1.3.2. Однородное управление топологией ................................38

1.3.3. Неоднородное управление топологией..............................39

1.4. Выводы по результатам обзора..........................................41

Глава 2. ФОРМИРОВАНИЕ ТОПОЛОГИИ БЕСПРОВОДНОЙ СЕТИ 43

2.1. Введение..................................................................43

2.2. Постановка задачи........................................................46

2.2.1. Модель сети . . . .....................................................46

2.2.2. Задача формирования топологии ....................................49

2.3. Игра формирования топологии..........................................52

2.3.1. Основные понятия теории игр........................................52

2.3.2. Описание игры ........................................................56

2.3.3. Равновесия в игре формирования топологии........................57

2.4. Алгоритмы формирования сети................. - • - 61

2.4.1. Базовый алгоритм формирования сети..............................61

2.4.2. Двойной наилучший ответ............................................65

2.4.3. Алгоритм двойных наилучших ответов..............................70

2.4.4. Алгоритм с переменным наилучшим ответом......................76

2.5. Исследование эффективности алгоритмов............................79

2.6. Выводы....................................................................86

Глава 3. РЕАЛИЗАЦИЯ АЛГОРИТМОВ 89

3.1. Реализация и вычислительная сложность алгоритмов................89

3.1.1. Общая схема формирования сети....................................89

3.1.2. Реализация наилучшего ответа........................................92

3.1.3. Реализация двойного наилучшего ответа............................94

3.2. Программный комплекс моделирования формирования сети .... 97

3.2.1. Описание комплекса..................................................97

3.2.2. Методика проведения экспериментов................................99

3.2.3. Генерация и визуализация случайных сетей........................101

3.2.4. Алгоритмы формирования сети......................................102

3.3. Выводы....................................................................105

ЗАКЛЮЧЕНИЕ 107

СПИСОК ЛИТЕРАТУРЫ 111

Приложение. Акт о внедрении 125

ВВЕДЕНИЕ

Актуальность темы исследования

В данной работе рассматриваются децентрализованные сети с нефиксированной топологией, к которым относятся беспроводные сенсорные сети, мобильные ad hoc сети и др. Они используются для распределенного сбора данных, организации связи в полевых условиях, расширении пропускной способности обычных сотовых сетей и решения других задач, где требуется создать коммуникационную сеть без какой-либо дополнительной инфраструктуры, кроме самих беспроводных узлов. Такие сети состоят из большого числа устройств, как правило, работающих от автономных аккумуляторов. Поскольку заряд аккумуляторов ограничен, задача обеспечения энергоэффективности является одной из основных при управлении ad hoc сетями.

Формирование эффективной топологии сети - это один из методов экономии энергии узлов и снижения взаимных помех. Беспроводные узлы могут регулировать мощность своих передатчиков. Для того чтобы два узла образовали беспроводную связь, необходимо, чтобы мощности обоих передатчиков-были выше некоторого порога, зависящего от расстояния между узлами. Задача состоит в назначении узлам таких мощностей, чтобы сформировалась связная сеть и суммарная мощность передатчиков была минимальна.

Методы формирования эффективных по тому или иному критерию сетей в настоящее время активно изучаются. Как правило, использование централизованных алгоритмов невозможно по причине отсутствия в сети единого управляющего центра, ограниченного обмена информацией и малых вычислительных мощностей узлов. Среди децентрализованных алгоритмов формирования сетей используются, в том числе, методы теории игр. В теоретико-игровых алгоритмах важную роль играет метод принятия решения рациональным агентом. Актуальной задачей является поиск новых методов принятия решения,

i I

повышающих эффективность алгоритмов.

Степень разработанности темы

Применение методов теории игр к задачам управления беспроводными сетями началось сравнительно недавно, но этой теме уже посвящен огромный массив работ. Наиболее широкое распространение получил подход некооперативной теории игр. Однако, несмотря на разнообразие прикладных задач, для их решения применяется сравнительно ограниченный набор методов.

В большинстве работ авторы формулируют задачу в виде игры известного класса, для которого установлено существование равновесия Нэша. Затем алгоритм поиска равновесия создается на основе одной из известных динамических игровых процедур. Наиболее распространенной является процедура последовательных наилучших ответов, когда агенты поочередно выбирают действия, оптимальные для текущей обстановки, не учитывая будущие изменения. Другие процедуры поиска равновесия используют методы стохастического обучения, эволюционных игр, ограничения рациональности агентов.

Метод, предложенный в данной работе, основан на идее стратегической' рефлексии, когда агент пытается прогнозировать действия своих оппонентов. Подобные методы применялись для исследования социально-экономических задач, а также в задаче проникновения группы агентов через линию обороны. Но, несмотря на полученные в этих направлениях результаты, динамические процедуры поиска равновесия на основе методов стратегической рефлексии пока еще изучено недостаточно подробно.

Цели и задачи работы

Целью работы является разработка алгоритмов формирования сети на основе метода двойного наилучшего ответа.

В ходе достижения поставленной цели были решены следующие задачи:

1. Проведен обзор приложений теории игр к задачам управления и оптимизации в беспроводных сетях, в том числе к задаче формирования эффективной топологии сети. Обзор показал, что разработка новых теоретико-игровых алгоритмов формирования сетей является актуальной научной и практической задачей.

2. Предложен новый метод принятия решения агентами - двойной наилучший ответ. Метод основан на идеях теории рефлексивных игр. Доказано, что в задаче формирования связной сети новый метод делает неустойчивыми все недопустимые равновесия.

3. На основе метода двойного наилучшего ответа разработано два алгоритма формирования сети. Показано, что новые алгоритмы получают в среднем более эффективные равновесия, чем стандартный метод наилучшего ответа.

4. Предложена схема реализации метода двойного наилучшего ответа, исследована ее вычислительная и коммуникационная сложность.

5. Разработан программный комплекс имитационного моделирования процесса формирования сети. Комплекс использовался для исследования эффективности алгоритмов и визуализации результатов.

Связь с планом

Работа выполнена в соответствии с плановой тематикой Института проблем управления РАН им. В.А. Трапезникова и при поддержке грантов РФФИ №№ 10-07-00104, 13-07-00491.

Научная новизна

1. Предложен оригинальный метод двойного наилучшего ответа, основанный на подходе рефлексивных игр. Методы стратегической рефлексии

ранее применялись в задачах управления социально-экономическими системами. В технических системах стратегическая рефлексия применялась для повышения эффективности проникновения агентов через линию обороны. В задачах формирования сетей методы рефлексивных игр применены впервые.

2. Получена оценка неэффективности равновесия Нэша в рассматриваемой игре формирования связной сети.

3. Доказано, что для игры формирования сети метод двойного наилучшего ответа делает неустойчивыми все равновесия, в которых сеть не связна. Это эквивалентно тому, что в рассматриваемой игре все равновесия, не оптимальные по Парето, будут не устойчивыми при использовании двойного наилучшего ответа.

4. Разработанные алгоритмы формирования сети показывают лучшие результаты, чем традиционный теоретико-игровой алгоритм. Это позволяет предположить, что они могут быть применены и в других задачах, где используются методы теории игр.

5. Получены оценки сложности разработанных алгоритмов и базового алгог ритма наилучшего ответа. Предложенный алгоритм поиска наилучшего ответа для рассматриваемой игры нигде в литературе не описан.

Теоретическая и практическая значимость работы

Теоретическая значимость работы состоит в исследовании нового теоретико-игрового метода принятия решений, использованного в динамической процедуре поиска равновесия. Показано, что динамические процедуры на основе двойного наилучшего ответа сужают множество возможных устойчивых состояний системы. Такие процедуры используются как для объяснения формирования того или иного равновесия в социальных или экономических системах, так и для разработки алгоритмов распределенной оптимизации в

технических системах.

Практическая значимость определяется эффективностью разработанных алгоритмов, полученными оценками вычислительной сложности и разработанным комплексом имитационного моделирования. Алгоритмы имеют сравнительно высокую вычислительную и коммуникационную сложность. Тем не менее, возможна модификация алгоритмов, снижающая данные требования, которая может быть использована в реальных беспроводных сетях. Предложенные алгоритмы могут быть адаптированы для других задач управления беспроводными сетями. Функции программного комплекса, имитирующие принятие решения агентами, могут быть легко адаптированы для других теоретико-игровых задач. Процедуры генерации и визуализации случайных графов могут быть использованы, например, для анализа социальных сетей.

Методология и методы исследования

В основе методологии исследования лежат методы теории игр, а таюке имитационное моделирование. Полученные аналитические результаты базируются на методах некооперативных игр. Исследование эффективности алгоритмов формирования сети проведено с помощью имитационного моделирования. Методика проведения экспериментов описана в работе. Использованный программный комплекс, исходные тестовые примеры и полученные данные экспериментов находятся в открытом доступе. Это обеспечивает достоверность результатов исследования.

Положения, выносимые на защиту

На защиту выносятся следующие результаты работы:

1. Предложен новый метод принятия решения агентом, названный двойным наилучшим ответом. Доказано, что для рассматриваемой игры формирования сети предложенный метод делает неустойчивыми все неоптималь-

ные по Парето равновесия Нэша. Для рассматриваемой игры получена не встречавшаяся ранее оценка для отношения затрат в наихудшем равновесии Нэша к оптимальному равновесию.

2. На основе предложенного метода разработано два алгоритма формирования беспроводной сети. В первом алгоритме используется статический метод принятия решения, во втором агенты динамически переключаются между обычным наилучшим ответом и двойным наилучшим ответом. Показано, что разработанные алгоритмы позволяют сузить множество получаемых равновесий по сравнению с базовым алгоритмом наилучшего ответа.

3. Исследована эффективность предложенных алгоритмов. Показано, что разработанные алгоритмы формируют более эффективные сети, чем известный теоретико-игровой алгоритм наилучшего ответа.

4. Предложены схемы реализации алгоритмов базового наилучшего ответа и двойного наилучшего ответа. Получены оценки вычислительной и коммуникационной сложности предложенных алгоритмов.

5. Разработан программный комплекс имитационного моделирования, имеющий потенциальные приложения для анализа других теоретико-игровых задач, а также для анализа процессов в социальных сетях.

Личный вклад

Все результаты получены автором.

Степень достоверности и апробация результатов

Достоверность результатов обусловлена использованными методами теории игр, теории графов и имитационным моделированием. Результаты диссертационной работы докладывались на семинарах ИПУ РАН, VII Всероссийской школе-семинаре молодых ученых «Управление большими система-

ми» (Магнитогорск, 2011), I и II Между народных школах-семинарах молодых ученых «Интеллектуальные системы и технологии: проблемы и перспективы» (Тверь-Протасово, 2012,2013), VI Международной конференции «Game Theory and Management» (Санкт-Петербург, 2012), Международном семинаре «Networking Games and Management» (Петрозаводск, 2012), VI Всероссийской мультиконференции по проблемам управления (Дивноморское, 2013).

Программный комплекс прошел апробацию и используется в аналитическом агентстве «Новые стратегии», что подтверждается актом о внедрении.

Публикации

По теме диссертационной работы опубликовано 11 печатных работ, в том числе 2 в рецензируемых изданиях, рекомендуемых ВАК.

Публикации в ведущих рецензируемых журналах, входящих в перечень ВАК

1. Базенков Н. И. Динамика двойных наилучших ответов в игре формирования топологии беспроводной ad hoc сети //Управление большими

системами. Выпуск 43. - 2013. - С.217-239.

2. Базенков Н. И., Губанов Д. А. Обзор информационных систем анализа

социальных сетей // Управление большими системами. Выпуск 41. -2013. - С. 357-394.

Тезисы докладов на международных конференциях

3. Bazenkov N. Reflexive Behavior in Topology Control for Ad Hoc Networks // Collected abstracts of 6th International Conference on Game Theory and Management (GTM). - 2012. - P. 39-41.

Публикации в трудах всероссийских конференций

4. Базенков Н.И. Динамика двойных наилучших ответов в игре формирования топологии беспроводной ad hoc сети // Труды 6-й Всероссийской мультиконференции по проблемам управления (МКПУ-2013). - 2013. -Т. 4.-С. 81-85.

5. Базенков Н.И., Яхин А.Ш. Экспериментальное исследование цитирования внешних сайтов в русскоязычной блогосфере // Труды 5-ой конференции «Управление в технических, эргатических, организационных и

сетевых системах» (УТЭОСС-2012). - 2012. - С. 872-875.

6. Базенков Н.И. Обзор теоретико-игровых моделей обеспечения безопасности информационных систем // Труды 56-й научной конференции МФТИ. Радиотехника и кибернетика. - 2013. - С. 124-125

7. Базенков Н.И. Рефлексия в задаче управления топологией беспроводной

сети // Труды 55-й научной конференции МФТИ. Радиотехника и кибернетика. - 2012. - Т. 1. - С. 46-47.

Публикации в трудах молодежных научных школ

8. Базенков Н.И. Динамика двойных наилучших ответов в игре формирования топологии беспроводной ad hoc сети // Труды П-й Международной летней школы-семинара по искусственному интеллекту для студентов, аспирантов и молодых ученых «Интеллектуальные системы и технологии: современное состояние и перспективы» (ISyT'2013). - 2013. -С. 111-116

9. Базенков Н.И. Теоретико-игровая постановка задачи контроля эгоистичного поведения узлов в многоагентных сетях передачи данных. // Материалы VIII Всероссийской школы-конференции молодых ученых

«Управление большими системами». - 2011. - С. 130-133.

10. Базенков Н.И. Задача стимулирования кооперации узлов в многоагентных беспроводных сетях в условиях ограниченной пропускной способности // Труды международной летней школы-семинара «Интеллектуальные системы и технологии: современной состояние и перспективы» (ISyT'2011, Тверь). Тверь-Протасово: Издательство Тверского государственного технического университета - 2011. - С. 110-118.

11. Базенков Н.И. Теоретико-игровая модель кооперации узлов в мобильных

Ad Нос сетях. // Аннотации докладов Научной сессии НИЯУ МИФИ 2011.-2011.-Т. 3. -С. 60.

В работе [2] автором проведен обзор программных пакетов для сетевого моделирования, используемых в научных исследованиях. В работе [5] автором получены все основные результаты.

Объем и структура работы

Диссертация имеет следующую структуру. В Главе .1 проведен обзор приложений теории игр к задачам управления беспроводными сетями, описана архитектура ad hoc сетей и проведен обзор задач и алгоритмов управления топологией беспроводных сетей.

В Главе 2 сформулирована задача формирования топологии сети и ее постановка в виде некооперативной игры, описан метод двойного наилучшего ответа, разработанные алгоритмы формирования сети и исследование их эфф