Содержание к диссертации
Введение
Глава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
Список литературы
- Примеры приложений
- Управление топологией беспроводных сетей
- Основные понятия теории игр
- Программный комплекс моделирования формирования сети
Введение к работе
Актуальность темы исследования. В работе рассматриваются децентрализованные беспроводные сети с нефиксированной топологией, к которым относятся сенсорные сети, мобильные 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,
США). В России работы по применению теории игр в беспроводных сетях проводились в Карельском научном центре РАН, Санкт-Петербургском государственном университете, Нижегородском государственном техническом университете им. Р.Е. Алексеева.
Использованный в задачах формирования сетей метод последовательных наилучших ответов имеет недостатки, связанные с тем, что получаемые им равновесия могут сильно отличаться от оптимального. Также при использовании этого метода сохраняют устойчивость недопустимые равновесия. Поэтому актуальной задачей является разработка новых методов поиска равновесий, повышающих эффективность алгоритмов.
Объектом исследования является задача формирования связной сети при минимальной суммарной мощности узлов. На плоскости расположено множество узлов, которые могут изменять мощности своих передатчиков. Необходимо назначить каждому узлу такую мощность, чтобы сеть была связна и сумма всех мощностей была минимальна.
Предметом исследования является новый метод выбора агентами своих действий, названный двойным наилучшим ответом. Изучается эффективность этого метода в алгоритмах формирования сети.
Целью диссертационной работы является разработка алгоритмов формирования сети на основе метода двойного наилучшего ответа.
В ходе достижения поставленной цели были решены следующие задачи:
-
Проведен обзор приложений теории игр к задачам управления и оптимизации в беспроводных сетях, в том числе к задаче формирования эффективной топологии сети. Обзор показал, что разработка новых теоретико-игровых алгоритмов формирования сетей является актуальной научной и практической задачей.
-
Предложен новый метод принятия решения агентами - двойной наилучший ответ. Метод основан на идеях теории рефлексивных игр. Доказано, что в задаче формирования связной сети новый метод делает неустойчивыми все недопустимые равновесия.
-
На основе метода двойного наилучшего ответа разработано два алгоритма формирования сети. Показано, что новые алгоритмы получают в среднем
более эффективные равновесия, чем стандартный метод наилучшего ответа.
-
Предложена схема реализации метода двойного наилучшего ответа, исследована ее вычислительная и коммуникационная сложность.
-
Разработан программный комплекс имитационного моделирования процесса формирования сети. Комплекс использовался для исследования эффективности алгоритмов и визуализации результатов.
Связь с планом. Работа выполнена в соответствии с плановой тематикой Института проблем управления РАН им. В.А. Трапезникова и при поддержке грантов РФФИ№№ 10-07-00104, 13-07-00491.
Методы исследования. В основе методологии исследования лежат методы теории игр, а также имитационное моделирование. Полученные аналитические результаты базируются на методах теории графов и теории некооперативных игр. Исследование эффективности алгоритмов формирования сети проведено с помощью имитационного моделирования, методика проведения экспериментов описана в работе.
Научная новизна работы заключается в следующем:
-
Предложен оригинальный метод двойного наилучшего ответа, основанный на подходе рефлексивных игр. Методы стратегической рефлексии ранее применялись в задачах управления социально-экономическими системами. В технических системах стратегическая рефлексия применялась для повышения эффективности проникновения агентов через линию обороны. В задачах формирования сетей методы рефлексивных игр применены впервые.
-
Получена оценка неэффективности равновесия Нэша в рассматриваемой игре формирования связной сети.
-
Доказано, что для игры формирования сети метод двойного наилучшего ответа делает неустойчивыми все равновесия, в которых сеть не связна. Это эквивалентно тому, что в рассматриваемой игре все равновесия, не оптимальные по Парето, будут неустойчивыми при использовании двойного наилучшего ответа.
-
Разработанные алгоритмы формирования сети показывают лучшие результаты, чем традиционный теоретико-игровой алгоритм. Это позволяет предположить, что они могут быть применены и в других задачах, где используются методы теории игр.
-
Получены оценки сложности разработанных алгоритмов и базового алгоритма наилучшего ответа. Предложенный алгоритм поиска наилучшего ответа для рассматриваемой игры нигде в литературе не описан.
Практическая значимость работы определяется разработанным комплексом имитационного моделирования, а также эффективностью разработанных алгоритмов, что позволит сэкономить мощность и продлить время жизни реальных беспроводных сетей. Разработанные в работе процедуры могут быть адаптированы для различных теоретико-игровых задач, а также для анализа социальных сетей.
Достоверность результатов обусловлена использованными методами теории игр, теории графов и имитационным моделированием. Использованный программный комплекс, исходные тестовые примеры и полученные данные экспериментов находятся в открытом доступе, что обеспечивает достоверность результатов исследования.
Положения, выносимые на защиту:
-
Предложен новый метод принятия решения агентом, названный двойным наилучшим ответом. Доказано, что для рассматриваемой игры формирования сети предложенный метод делает неустойчивыми все неоптимальные по Парето равновесия Нэша. Для рассматриваемой игры получена не встречавшаяся ранее оценка для отношения затрат в наихудшем равновесии Нэша к оптимальному равновесию.
-
На основе предложенного метода разработано два алгоритма формирования беспроводной сети. В первом алгоритме используется статический метод принятия решения, во втором агенты динамически переключаются между обычным наилучшим ответом и двойным наилучшим ответом. Показано, что разработанные алгоритмы позволяют сузить множество получаемых равновесий по сравнению с базовым алгоритмом наилучшего ответа.
-
Исследована эффективность предложенных алгоритмов. Показано, что разработанные алгоритмы формируют более эффективные сети, чем известный теоретико-игровой алгоритм наилучшего ответа.
-
Предложены схемы реализации алгоритмов базового наилучшего ответа и двойного наилучшего ответа. Получены оценки вычислительной и коммуникационной сложности предложенных алгоритмов.
-
Разработан программный комплекс имитационного моделирования, имеющий потенциальные приложения для анализа других теоретико-игровых задач, а также для анализа процессов в социальных сетях.
Апробация работы. Результаты диссертационной работы докладывались на семинарах ИПУ РАН, VII Всероссийской школе-семинаре молодых ученых «Управление большими системами» (Магнитогорск, 2011), I и II Международных школах-семинарах молодых ученых «Интеллектуальные системы и технологии: проблемы и перспективы» (Тверь-Протасово, 2012,2013), VI Международной конференции «Game Theory and Management» (Санкт-Петербург, 2012), Международном семинаре «Networking Games and Management» (Петрозаводск, 2012), VI Всероссийской мультиконференции по проблемам управления (Дивноморское, 2013).
Программный комплекс прошел апробацию и используется в аналитическом агентстве «Новые стратегии», что подтверждается актом о внедрении.
Публикации. По теме диссертационной работы опубликовано 11 печатных работ, в том числе 2 в рецензируемых изданиях, рекомендуемых ВАК.
Личный вклад автора. Все результаты получены автором.
Объем и структура работы. Диссертация состоит из введения, 3 глав, заключения, библиографии, включающей 122 наименования, и приложения. Общий объем диссертации составляет 125 страниц.
Примеры приложений
Управление мощностью. Задача управления мощностью (power control) характерна для сотовых сетей, использующих технологию CDMA (Code Division Multiple Access). В таких сетях все мобильные станции используют одну частоту для передачи данных на базовую станцию, разделение каналов происходит благодаря специальной технологии кодирования. Эта схема используется в стандартах cdmaOne (IS-95), CDMA2000, WCDMA/HSPA, наи 21 большее распространение получивших в США и Западной Европе [42]. Поскольку все устройства передают на одной частоте, каждое устройство создает помехи для других. Для уменьшения этого эффекта используются алгоритмы динамической настройки мощности передающих устройств [119]. Управление мощностью также актуально для сетей femtocell, в которых небольшие соты расположены очень плотно и создают значительные взаимные помехи [34]. В работах [16], [18] также рассматриваются проблемы, возникающие при наличии нескольких базовых станций и переключении устройств между ними. Задачи о регулировке мощности и взаимодействии радиостанций изучались еще в Советском Союзе в работах по коллективному поведению автоматов [12].
В теоретико-игровой постановке передающие устройства являются агентами, устанавливаемая мощность передатчика - их действие. Функция полезности в общем виде характеризует качество связи. Вид функции отличается для передачи данных или голоса и зависит от используемой схемы модуляции [47], [106]. Также может учитываться вероятность отказа в обслуживании [18]. Но общий принцип состоит в том, что функция полезности возрастает по мере снижения отношения сигнал/(помехи+шум) (SINR - Signal to Interference plus Noise Ratio) и убывает по мере увеличения затрачиваемой мощности. При управлении без обратной связи (Open-loop power control) агенты могут измерять только собственный уровень SINR . При управлении с обратной связью функция полезности может включать дополнительный управляющий параметр “цены” увеличения мощности, которая выбирается базовой станцией и сообщается агентам в режиме реального времени. Цена может быть одинаковой для всех агентов или различаться в зависимости от типа передаваемых данных [15]. Агенты также в режиме реального времени выбирают, какую “цену” они готовы заплатить, исходя из требуемого качества связи.
Используются такие функции, при которых в игре существует единственное равновесие Нэша. Базовый алгоритм его поиска состоит в применении динамики наилучших ответов [15], когда в каждый момент времени агент вы 22 бирает действие, максимизирующее его полезность при текущих условиях. Исследуются синхронные и асинхронные модификации алгоритма, все они сходятся к единственному равновесию Нэша. Сходимость к единственному равновесию связана с общим свойством s-модулярности (s-modular), характерном для игр управления мощностью [20]. В [78] используется алгоритм стохастического фиктивного розыгрыша (SFP - Stochastic Fictious Play), из теории повторяющихся игр, в котором намеренно вносятся случайные возмущения в функцию полезности для повышения устойчивости. Аппарат повторяющихся игр также используется в [71], где агент устанавливает рассчитанный заранее оптимальный уровень мощности, а если кто-то из его оппонентов отклоняется от этого плана, использует максимальную мощность как “наказание”. В [70] один из агентов выбирается как “лидер”, а в качестве концепции решения используется равновесие Штакельберга.
Распределение ресурсов радиоканала. Задачи распределения радиоканала между соединениями актуальны для всех типов сетей. В [111] рассматривается временное разделение доступа к каналу (TDMA - Time Division Multiple Access). Центральный передатчик (базовая станция или спутник) распределяет слоты, на которые разбита временная ось, между несколькими приемниками, или пользователями. Перед началом нового слота передатчик выбирает пользователя, который будет обслуживаться в течение данного слота. При этом состояние канала, определяющее качество связи и, соответственно, доступную пропускную способность, отличается для разных пользователей и может изменяться с течением времени. Максимальная пропускная способность достигается, если каждый слот выделять пользователю с наилучшим качеством канала. Однако, это недопустимо, поскольку другие пользователи останутся вообще без связи. Авторы предлагают механизм распределения слотов, основанный на аукционе второй цены.
Тариф, который использует пользователь, определяет объем доступных ему фиктивных “денег”. В начале каждого слота пользователям сообщается состояние их канала, затем каждый делает “ставку”. Слот получает пользователь, поставивший максимальную сумму, но “выплатить” он должен вторую по величине ставку. Такой механизм стимулирует пользователей делать ставки, соответствующие их истинным предпочтениям. В игре существует единственное равновесие Нэша, и распределение ресурсов на его основе обладает следующими привлекательными свойствами. Оно единственно, независимо от вероятностного распределения, которому подчиняется состояние канала. Кроме того, оно обеспечивают использование канала не хуже, чем 3/4 от максимально возможной пропускной способности, при этом Парето-оптимально. Для реальных сетей аукцион имитируется централизованным алгоритмом планирования, чтобы избежать избыточной нагрузки на сеть при передаче информации о ставках.
Управление топологией беспроводных сетей
Сети с допустимыми задержками (DTN – Delay&Disruption Tolerant Network). Сети с задержками серьезно отличаются от вышеперечисленных концепций. В сетях DTN предполагается, что для передачи данных между двумя узлами не обязательно наличие соединения в данный момент. Достаточно ненулевой вероятности образования такой связи в будущем [26]. Сеть использует постоянные или эпизодические социальные контакты между людьми для передачи данных между их мобильными устройствами. Если человек загружает видео или новости, чтобы посмотреть их не в текущий момент, а по пути с работы домой, для него задержки даже в несколько часов не играют большой роли. Тогда файлы могут быть доставлены без использования сотовой сети, а путем постепенной загрузки с устройств его коллег, случайных попутчиков и т.д. Такие решения могут разгрузить сотовые сети за счет кэширования популярных файлов. Поскольку сети с задержками ориентированы в основном на передачу файлов, а не для мгновенной коммуникации, их еще называют ориентированными на данные (data centric) или информационно-центричными (ICN - Information Centric Networks).
Существуют проекты по реализации delayolerant сетей. В частности, известен масштабный проект Haggle [91], в настоящее время завершенный. В рамках этого проекта разработано программное обеспечение по созданию эпизодических коммуникаций с использованием интерфейсов WiFi, Bluetooth, UMTS и т.д. Разработаны прототипы приложений для обмена файлами и фотографиями, электронной почты, сервиса микроблогов и др. На базе архитектуры Haggle предлагается решение для поддержания связи во время чрезвычайных ситуаций – ICEMAN (Information CEntric Mobile Ad-hoc Networking) [114].
Физический и канальный уровень Реализация физического и канального уровней в ad hoc сети зависит от ее области применения. Для военных приложений характерны повышенные требования к надежности и безопасности, поэтому для них обычно разрабатываются специализированные решения, например, DARPA WNaN (Wireless Network after Next) [97].
Если сеть создается на базе обычных пользовательских устройств, то она вынуждена использовать технологии, которые поддерживаются данными устройствами. Большинство mesh сетей используют стандарт IEEE 802.11 (WiFi), который предназначен для работы в нелицензируемом диапазоне частот. При этом для передачи служебной информации выделяется, как правило, отдельный диапазон частот. Для связи между маршрутизаторами часто используются антенны MIMO (Multiple Input Multiple Output) [94], существенно повышающие пропускную способность сети.
Известно, что при использовании обычных приемо-передающих антенн пропускная способность (объем данных, передаваемых в единицу времени) беспроводной сети, даже при оптимальном планировании передачи данных, убывает пропорционально n, где n – число узлов [49]. В настоящее время разрабатываются методы, призванные повысить эффективность использования частот. Устройства, реализующие идеи когнитивного радио (cognitive radio), создают модель окружающей обстановки, точно оценивают и прогнозируют изменения состояния канала, регулируют мощности передатчиков и динамически выбирают свободные частоты [51].
Методы кооперативной передачи данных (cooperative communication) позволяют устройствам с обычными приемо-передающими антеннами сформировать виртуальную MIMO антенну, что существенно повышает качество связи [92]. Возможно, подобные технологии в скором будущем позволят обычным пользователям создавать самоорганизующиеся сети из сотен и тысяч мобильных узлов.
Для сенсорных сетей интенсивность передачи данных обычно невелика, поэтому проблема эффективного использования частот стоит не столь остро. Чаще всего используется либо стандарт Wi-Fi (IEEE 802.11), либо стандарт IEEE 802.15.4, адаптированный для беспроводных персональных сетей (WPAN – Wireless Personal Area Network). В коммерческих продуктах часто используются закрытые протоколы. Например, в радиомодулях компании MeshLogic используется физический уровень стандарта IEEE 802.15.4, а уровень распределения доступа к среде основан на собственных разработках [2].
В DTN сетях данные передаются во время эпизодических контактов между разными мобильными устройствами, поэтому желательно использовать любые доступные технологии. Архитектура Haggle предпогает гибкую интеграцию интерфейсов Bluetooth, WiFi, Ethernet и других, доступных в конкретном устройстве [91].
Сетевой уровень. Способы логической организации сети можно условно разделить на графовые (graph-based), позиционные (location-based) и контекстные, или данно-центричные (data-centric) [39]. Другое основание классификации – одноранговые или иерархические сети. В одноранговых сетях все узлы равноправны и выполняют одинаковые функции. В иерархических сетях выделяются специальные узлы, выполняющие управляющие функции. Типичный пример – сети ZigBee состоят из узлов трех типов: координатора, маршрутизаторов и конечных узлов. Сети MANET, как правило, полностью одноранговые. Большинство mesh сетей состоят из маршрутизаторов, объединенных в одноранговую сеть, и подключающихся к ним конечных узлов. Возможны комбинации перечисленных подходов.
Основные понятия теории игр
Для описания принятия решений рефлексивным агентом в [8] вводится понятие ранга рефлексии. Агенты, обладающие 0-м рангом рефлексии, используют “наивный” наилучший ответ (2.9). Агент, обладающий 1-м рангом рефлексии, считает, что все остальные агенты обладают рангом 0. Агент ранга 2 и выше правильно информирован о всех агентах более низких рангов. Информированность об агентах, чей ранг выше его собственного, может задаваться по-разному. Похожая модель названа в [32] “когнитивной иерархией” (cognitive hierarchy). Авторы показали, что модель когнитивных иерархий лучше классического равновесия Нэша объясняет поведение людей в некоторых экспериментальных играх. Например, “конкурс красоты” (beauty contest game), “охота на оленя” (stag hunt game) и других.
Ранги рефлексии выше 1 мы рассматривать не будем, их примение к анализу прикладных задач теории игр описано в монографии [4]. Здесь идеи рефлексивных игр используются для создания правила выбора мощности, которое бы учитывало изменяющиеся действия других узлов. Оно получило название двойного наилучшего ответа.
Введем несколько новых обозначений. Пусть К С N - некоторое подмножество агентов. Обозначим как BRK{CL) вектор, элементами которого являются наилучшие ответы агентов j є К на соответствующие обстановки a_j. BRK{(I) = (BRj1(a-j1)i..., BRjk(a-jk)), ji, ,jk Є К, к = \K\. Здесь будем считать, что наилучший ответ агента j единственен. Это выполняется для рассматриваемой игры формирования топологии. Далее кратко рассматривается ситуация, когда BRj(a-j) - множество.
Вспомним, что вектор действий можно обозначить как а = (а,п а-і). Замена в векторе а действия агента і на х Є А{ будет обозначаться как ahX = (ж, а-І). Обстановка для узла j в этом новом векторе действий будет обозначаться как
Допустим, агент і выбрал действие з; G і». Пусть каждый другой агент j N, j = i выбирает свой наилучший ответ на новую обстановку ai-, xj = (x, a-i)-j. Тогда вектор всех таких наилучших ответов будет обозначаться как BR-i(ai,x) =(BR1(ai-, x1),...,BRi-1(ai-,x(i-1)), (2.14) BRi+1(ai-,x(i+1)), . . . , BRn(ai-, xn)) Определение 15. Двойным наилучшим ответом (double best response) агента i на обстановку a-i называется действие DBRi(a-i)=arg max ui(x,BR-i(ai,x)), (2.15) xAi где BR-i(ai,x) – вектор одновременных наилучших ответов других агентов на выбор агентом i действия x.
Идея правила двойного наилучшего ответа состоит в следующем: агент перебирает все множество своих действий. Для каждого возможного действия он вычисляет наилучшие ответы других агентов. При этом предполагает, что все агенты одновременно выберут свои наилучшие ответы на изменившуюся обстановку.
В том случае, если наилучшие ответы агентов j = i не единственны, элементами вектора BR-i(ai,x) станут множества возможных действий других агентов. Декартово произведение элементов вектора BR-i(ai,x) будет задавать множество всех ситуаций, которые могут возникнуть, если агент i выберет действие x. Для того, чтобы выбрать определенное действие, агент i может использовать, например, принцип гарантированного результата. Некоторые схемы принятия решения рефлексивным агентом рассматриваются в работах [8], [4]. Далее везде выполняется условие, что наилучший ответ агентов единственен. Насколько известно, в чистом виде правило (2.15) ранее не применялось в теоретико-игровых алгоритмах. В [5] агенты выбирают действие как линейную комбинацию текущего действия и правила, частично напоминающего двойной наилучший ответ. Такой подход обеспечивает устойчивость коллективного поведения, но применим, только если действия выражаются непрерывной величиной.
Вычисление наилучшего ответа (2.9) не требует от агента знания функций полезности других агентов, достаточно знать обстановку а-І. Правило (15) вычислительно намного сложнее, чем “наивный” наилучший ответ. Агент должен уметь вычислять наилучшие ответы других агентов. Это требует информированности об их полезностях и допустимых действиях. В системах с большим количеством агентов реализация двойного наилучшего ответа в чистом виде может представлять сложность. Ограничим множество агентов, чьи действия г может прогнозировать и назовем его рефлексивным множеством. Определение 16. Рефлексивным множеством (reflexive set) Ri агента і назовем
Программный комплекс моделирования формирования сети
Разработанный программный комлекс предназначен для моделирования процессов формирования сетей. В целях исследования теоретико-игровых алгоритмов формирования топологии беспроводных сетей были реализованы соответствующие правила принятия решения агентами. При необходимости данный комплекс может быть расширен и другими правилами поведения агентов.
В мире существует много систем имитационного моделирования беспроводных сетей. Известна открытая система NS (Network Simulator) [89], разработанная университетом Беркли. Специально для моделирования мобильных ad hoc сетей предназначена система MobiREAL [87], разработанная университетом Осаки. Для моделирования сенсорных сетей предназначена система WSNet [117], которая поддерживает MIMO архитектуру узлов, разные алгоритмы распределения частот, несколько моделей распространения сигнала и другие функции. В коммерческих приложениях распространен продукт OPNET Modeler Suite [93]. Для моделирования процессов управления топологией существует симулятор Attaraya [23].
Большинство перечисленных программ предназначено для как можно более тщательного моделирования всех нюансов беспроводной передачи данных. Акцент в них сделан на имитации всех нижних уровней передачи сообщений, от физического до сетевого. Использование этих программ оправдано при разработке промышленных прототипов алгоритмов и протоколов, но требует больших временных затрат. Для первичных исследований алгоритмов больше подходят универсальные среды математического моделирования: MATLAB/Octave, Wolfram Mathematica, R и др.
Исследование эффективности приведенных в работе алгоритмов не тре 98 бует моделирования особенностей беспроводных каналов связи. Поэтому был разработан отдельный комплекс, подходящий для реализации алгоритмов формирования топологии, а при необходимости и для исследования других задач с сетевым взаимодействием агентов. Например, для исследования процессов в социальных сетях.
Комплекс реализован как библиотека функций MATLAB. Среда MATLAB содержит средства интеграции с Java и C++, что позволяет при необходимости использовать данную библиотеку в других проектах. Здесь приводится только общее описание библиотеки. Сама библиотека и документация доступны в описании проекта NetGames на сайте SourceForge.net1.
Функции комплекса можно разделить на следующие группы:
1. Базовые. Находятся в корневой директории. Управляют процессом генерации тестовых примеров, проведением экспериментов и визуализации результатов
2. Чтения и записи тестовых примеров. Находятся в директории ./io. Реализуют чтение с диска и запись тестовых примеров в формате JSON.
3. Моделирование формирования сети. Находятся в директории ./network. Реализуют генерацию тестовых сетей со случайным размещением узлов, создание топологии сети при заданных мощностях, поиск связных компонент и др.
4. Правила поведения агентов. Находятся в директории ./agent. Реализуют правила принятия решений агентами: базовый наилучший ответ и двойной наилучший ответ. Также здесь находятся функции, имитирующие формирование сети описанными алгоритмами.
5. Визуализация результатов. Директория ./plot. Функции визуализации графа сети.
В следующих подразделах описывается методика использования комплекса, а также некоторые доступные функции. 1https://sourceforge.net/projects/netgames/ 3.2.2. Методика проведения экспериментов
На рисунке 3.1 схематично изображен процесс проведения экспериментов. В начале фиксируется набор исходных параметров для эксперимента: число узлов N, максимальная мощность ртах, область расположения узлов region, тип распределения узлов в области seed_type, постоянная затухания а. В данном исследовании изменялся только параметр N. Использовался один тип распределения узлов - случайное равномерное распределение в прямоугольной области. Были реализованы также варианты с распределением узлов на решетке, они рассмотрены в следующем подразделе.
Для заданного набора параметров создается К случайных тестовых примеров. Процесс генерации тестовых примеров реализован в файле gendata.m. Все созданные примеры помещаются в одну директорию, например, data/uniform_50_0.5. Это означает, что в данной директории находятся тестовые примеры, в которых 50 узлов равномерно распределены в квадрате и задана такая максимальная мощность, чтобы радиус действия передатчика составлял 0.5 от стороны квадрата.
Один цикл эксперимента состоит в запуске одного алгоритма на всех тестовых примерах с одним набором параметров. Запуск эксперимента производится скриптом та і п. т. В файле скрипта задается директория, из которой будут считаны тестовые примеры, и директория, в которой будут сохранены результаты эксперимента. Например, результаты исследования алгоритма наилучшего ответа могут быть сохранены в директорию data/results/BestResponse. Для каждого тестового примера алгоритм формирует сеть. Порядок действий узлов задается их номерами. Поскольку узлы располагаются случайным образом, это равносильно случайному порядку ходов.
