Содержание к диссертации
Введение
1 Введение 7
1.1 Общая характеристика работы 7
1.2 Анализ беспроводных многоузловых сетей связи 16
1.2.1 Проблемы производительности беспроводных многоузловых сетей передачи данных 21
1.3 Теория машинного обучения, обучение с подкреплением 25
1.4 Цель исследования, основная идея 29
2 Анализ алгоритмов маршрутизации в беспроводных многоузловых сетях передачи данных 31
2.1 Основные схемы маршрутизации 31
2.2 Сравнение существующих протоколов маршрутизации, используемых в беспроводных многоузловых сетях 36
2.2.1 Реактивные протоколы маршрутизации 37
2.2.1.1 AODV протокол 37
2.2.1.2 DSR протокол 42
2.2.2 Проактивные протоколы маршрутизации 44
2.2.2.1 DSDV протокол 44
2.2.2.2 OLSR протокол 47
2.3 Выбор метрик маршрутизации 50
3.1 Классификация задач машинного обучения 53
3.2 Машинное обучение с подкреплением 54
3.3 Основные элементы теории машинного обучения с подкреплением 58
3.4 Расчет функции значений 60
3.5 Метод взвешенного выбора действия 64
4 Алгоритм сетевой маршрутизации на основе машинного обучения с подкреплением 65
4.1 Взаимосвязь теории обучения с подкреплением и задачи маршрутизации 66
4.2 Процедура поиска маршрута, алгоритм первичного обновления весов маршрутов 70
4.3 Алгоритм обновления весов маршрутов на основе обратной связи 77
4.4 Алгоритм выбора маршрута 83
4.5 Аналитическое описание разработанного алгоритма 85
4.7 Программная имплементация разработанного алгоритма 93
5 Экспериментальное исследование разработанного алгоритма маршрутизации 101
5.1 Описание тестовой сети, технические характеристики узлов сети 103
5.2 Описание тестовой топологии и пакетного трафика 107
5.3 Описание протокола маршрутизации B.A.T.M.A.N. 108
5.4 Методика оценки производительности протоколов маршрутизации в условиях реальной сети 111
5.5 Результаты экспериментов 115
5.6 Выводы 120
6 Сфера применения разработанного протокола 121
7 Заключение 122
Список использованных источников 124
Список сокращений 132
Приложение А 135
- Анализ беспроводных многоузловых сетей связи
- Машинное обучение с подкреплением
- Аналитическое описание разработанного алгоритма
- Методика оценки производительности протоколов маршрутизации в условиях реальной сети
Анализ беспроводных многоузловых сетей связи
Беспроводные многоузловые сети (Wireless Multihop Networks) являются обобщением беспроводных одноранговых сетей с множеством промежуточных узлов связи. В подмножество таких сетей входят мобильные сети ad hoc (Mobile Ad Hoc Networks – MANET), беспроводные ячеистые сети (Wireless Mesh Networks – WMN) и беспроводные сенсорные сети (Wireless Sensor Networks – WSN). Всех их объединяет общая концепция множества узлов-передатчиков, генерирующих и пересылающих пакетный трафик определенной интенсивности. Такие сети могут иметь узлы-шлюзы (gateway nodes), играющие роль моста во внешние сети передачи данных, а также узлы-точки-доступа (в случае с WMNs), предоставляющие возможность сторонним клиентам получать доступ к узлам беспроводной многоузловой сети.
В таблице 1 представлены основные классы беспроводных многоузловых сетей, с описанием их особенностей в контексте генерируемого и пересылаемого трафика, размера, топологии, области применения и автономности. Приведенные в таблице сетевые протоколы уровня L3 будут подробно описаны во второй части работы.
Область применения беспроводных многоузловых сетей очень широка – начиная от сетей для мониторинга окружающей среды, интернета вещей, и заканчивая сетями быстрого развертывания для военного применения.
В качестве примера использования беспроводной сенсорной сети (WSN), можно представить проект интеллектуальной сети уличного освещения SmartLighting [8], в которой каждый узел сети оснащен микроконтроллером с сенсорами движения, беспроводным интерфейсом передачи данных, а также контроллером включения/выключения лампы (рисунок 2), установленным на столбах уличного освещения. Таким образом, каждый узел такой сети имеет возможность детектировать движение, и передавать информацию соседним лампам для определения вектора и скорости движения пешехода.
Примерами сетей MANET (мобильных ad hoc сетей) являются распределенные мобильные мессенджеры (такие как Firechat) [7], в которых передача текстовых сообщений осуществляется непосредственно между мобильными устройствами (смартфонами), без участия централизованной инфраструктуры (базовых станций, Wi-Fi точек доступа, и т.п.). Таким образом, сервис передачи сообщений остается доступным даже в случае, если доступ во внешнюю сеть отсутствует. По схожему принципу работает система мобильного мониторинга Serval Project [21], которая позволяет пользователям осуществлять звонки, отправлять сообщения, а также осуществлять мониторинг на определенной территории с различными целями, такими как контроль за окружающей средой, и так далее. Как в случае с Firechat, так и в случае с Serval Project, вся коммуникация осуществляется через смартфон пользователя, с использованием стандартных беспроводных интерфейсов, таких как Wi-Fi и Bluetooth. При этом, пользователь может быть мобильным, что вносит изменения в текущую топологию, а также постоянно меняет маршруты соединений в MANET сети.
Одной из разновидностей сетей MANET являются сети VANET (Vehicular Ad hoc Networks) [22], основной функцией которых является передачи сообщений между движущимися автомобилями и дорожной инфраструктурой для осуществления доступа в сеть Интернет, а также реализации сервисов для безопасности дорожного движения посредством обмена соответствующими сообщениями, и для поддержки движения автономных транспортных средств (например, проект Platooning [23]).
К классу беспроводных ячеистых сетей (Wireless Mesh Networks, WMNs) относятся беспроводные сети передачи данных, которые предоставляют первичный доступ пользователям во внешние сети (чаще всего, в сеть Интернет), а также осуществляют маршрутизацию и балансировку трафика пользователей в ячеистой сети. Как правило, такие сети, в отличие от вышеперечисленных, уже имеют некую иерархию узлов, которые можно разделить на:
узлы доступа (mesh points) – осуществляют маршрутизацию трафика, а также предоставляют доступ для конечных пользователя в ячеистую сеть;
узлы-шлюзы (mesh gateways) – осуществляют маршрутизацию трафика, и выполняют функцию узла-шлюза во внешние сети;
узлы ячеистой сети (mesh nodes) – простейшие, промежуточные узлы ячеистой сети, которые выполняют только функцию маршрутизации и перенаправления трафика либо в сторону узлов-доступа, либо в сторону узлов-шлюзов.
Обобщенная схема таких сетей представлена на рисунке 3. В качестве реального и вполне эффективного применения беспроводных ячеистых сетей (WMNs) на практике является проект Freifunk (нем. “свободное радио”) [24], который предоставляет доступ в интернет для пользователей по технологии Wi-Fi, без развертывания проводной инфраструктуры. В данном проекте, беспроводные Wi-Fi роутеры объединяются в одну беспроводную mesh-сеть, покрывающую целые районы таких городов как Гамбург и Берлин, с более чем 300-ми узлов. Маршрутизация пользовательского трафика здесь осуществляется с помощью беспроводных протоколов маршрутизации OLSR и B.A.T.M.A.N [15, 16].
Таким образом, беспроводные многоузловые сети являются крайне востребованной сферой телекоммуникаций с множеством различных ниш для применения. Кроме того, со стремительным развитием концепции интернета вещей, а также постоянным ростом числа беспроводных устройств и скоростей передачи данных, задача поиска эффективного алгоритма маршрутизации и распределения потоков трафика в таких сетях будет становиться вс более актуальной. В связи с этим, вс более остро встает ряд проблем беспроводных многоузловых сетей, которые будут описаны в следующей главе, и подробный анализ которых будет дан в соответствующем разделе второй части работы.
Машинное обучение с подкреплением
Основной задачей обучения с подкреплением является задача сопоставления действий с текущей ситуацией в среде взаимодействия для того, чтобы максимизировать значение получаемой награды. Обучаемая программа не имеет входных данных о том, какое действие выполнить в той или иной момент времени, однако имеет возможность самостоятельно выбирать те или иные действия для получения значений награды. В самых сложных задачах обучения с подкреплением, выполнение определенного действия в данный момент времени может напрямую влиять на значение получаемой награды не только для текущего действия, но и для всех остальных значений награды. Таким образом, можно выделить две основные характеристики обучения с подкреплением – поиск путем проб и ошибок (try and error) [18], и задержанная награда (delayed reward) [52], которые являются двумя наиболее заметными отличительными чертами обучения с подкреплением.
В самом обобщенном случае, идея обучения с подкреплением заключается в определении наиболее важных аспектов задачи (проблемы), для решения которой агент будет взаимодействовать с некой средой путем процесса “действие – награда” [18]. Очевидно, что агент должен иметь возможность слушать среду (получать награду от нее), а также иметь возможность на нее влиять путем выполнения определенных действий. Кроме того, агент должен иметь некую цель, к которой должен привести среду, с которой взаимодействует. Такая обобщнная формулировка определяет наличие трех основных компонентов обучения с подкреплением – ощущение среды, совершение действий со средой, и цель (целевое состояние среды).
Машинное обучение с подкреплением отличается от обучения с учителем (supervised learning) тем, что не ставит задачи найти статистическую функцию, которая подходила бы для входящего массива данных. Наоборот, в машинном обучении с подкреплением внедряется сущность агента, который взаимодействует с данной средой в реальном времени, и корректирует свое поведение на основе полученной обратной связи (награды). В то время как в обучении с учителем, существует сущность учителя, который заранее имеет целевой набор данных. Таким образом, агент постепенно улучшает свое знание об окружающем мире, с которым он взаимодействует и, в конечном итоге, находит универсальную схему поведения, которая является оптимальной или близкой к оптимальной. Более того, часто предполагается, что агент взаимодействует со средой, не имея никакого начального представления о е свойствах, а также о том, как те или иные действия агента влияют на е состояние. В процессе обучения, агент выполняет два основных математических действия: выбор следующего действия, основываясь на текущей информации о наградах, а также анализ / предсказание того, как выбранное действие повлияет на среду и будущее значение награды.
В настоящее время, теория машинного обучения с подкреплением используется далеко за пределами теорий математической статистики и исследования операций [53]. Один из самых больших трендов в исследованиях, в которых обучение с подкреплением является неотъемлемой частью, являются области науки, сопряженные с прикладными инженерными дисциплинами, в частности, телекоммуникации. Примерами задач машинного обучения с подкреплением являются:
- игрок в шахматы делает ход:
Выбор действия, в данной среде, зависит от планирования, т.е. анализа / предсказания того, как сделанный ход повлияет на текущую и будущую игровую ситуацию.
- адаптивный микроконтроллер изменяет компоненты смеси бензина на нефтеперерабатывающей фабрике [18]:
Микроконтроллер оптимизирует соотношение цены/количества/качества бензина, в зависимости от текущих параметров, не привязываясь к фиксированным параметрам топлива, изначально установленных инженерами.
- детеныш газели пытается встать на ноги в первые минуты жизни [18]:
Детеныш, путем активного взаимодействия с окружающей средой, находит и запоминает оптимальный баланс своего тела в пространстве, и уже через полчаса развивает скорость в 35 километров в час. - мобильный робот решает входить ли ему в комнату, убрать мусор, или начать двигаться в сторону стационарного зарядного устройства [18]:
В данной среде, робот может принять решение, основываясь на том, сколько времени потребовалось ему ранее, чтобы добраться до зарядной станции.
- сетевой маршрутизатор принимает решение о дальнейшем маршруте входящего пакета данных:
Сетевой маршрутизатор, основываясь на предыдущей истории отправок пакетов с данной парой адресов «отправитель/получатель», и соответствующих показателях процента потерь и загрузки сети, отправляет пакет далее.
Все вышеперечисленные примеры разделяют между собой основную черту машинного обучения с подкреплением, а именно: процесс взаимодействия между активным, принимающим решение агентом, и средой его нахождения, в ходе которого агент пытается достигнуть цели в условиях неопределенности среды, где он находится. При этом, действия агента могут влиять на состояние среды (например, следующая позиция в шахматной партии, уровень резервуаров в нефтяном хранилище, следующее местоположение робота), таким образом влияя на возможности выбора, доступные агенту на последующих шагах. Поэтому, выбор оптимального действия также зависит от величины неявных (задержанных в проявлении) последствий того или иного действия и, таким образом, нуждается в планировании и анализе доступной информации о среде взаимодействия.
В то же самое время, во всех вышеперечисленных примерах, последствия тех или иных действий не могут быть полностью предсказуемы, поэтому агент должен достаточно часто следить за состоянием среды и реагировать соответственно. Кроме того, данные примеры включают в себя определенные цели в том смысле, что агент имеет возможность соотносить текущую ситуацию и следить за прогрессом в сторону заданной цели. Например, игрок в шахматы знает когда он проиграл или выиграл, микроконтроллер на заводе знает, сколько бензина было уже произведено, а робот-уборщик знает момент времени, когда его батареи разрядятся.
Все вышеперечисленные примеры также показывают, что агент может использовать накопленный опыт для улучшения своей производительности с течением времени. Так, игрок в шахматы пересматривает сво игровое мышление для оценки текущей шахматной позиции, тем самым улучшая свою игру. Знания, которые доступны агенту до начала задания (они получены либо из опыта выполнения предыдущих подобных заданий, либо в зависимости от выходных параметров), влияют на то, какое действие агент будет выбирать в первую очередь (т.е. то, чему легко обучиться), однако последующий процесс взаимодействия со средой является самым важным в аспекте оптимизации поведения агента и нахождения особенностей среды в контексте поставленной задачи.
Аналитическое описание разработанного алгоритма
Поставленная задача маршрутизации трафика в беспроводной многоузловой сети, с точки зрения теории машинного обучения с подкреплением, может быть представлена в качестве конечного марковского процесса принятия решения (finite Markov Decision Process MDP), на котором основано 90 % подобных задач [18].
Как было показано в разделе 1, данный процесс может быть описан с помощью двух основных множеств, отображающих множество действий А = {ah а2, ... , ап}, и множество состояний S = {slt s2, ... , snj, в которых находится система в данный момент времени. Соответственно, вероятность перехода из текущего состояния s в состояние s , выполнив некое действие а, можно выразить следующим образом
Данные вероятности часто называют вероятностями перехода (transition probabilities). Подобным образом, можно выразить ожидаемое значение награды за выбранное действие а, при переходе из состояния s в состояние s :
Выражения Ps% и RsS, полностью описывают динамику переходов марковского процесса принятия решения для данной задачи.
На рисунке 19 показан процесс передачи пакета данных к следующему узлу-соседу, с обратной связью в виде ACK-сообщения, содержащего награду за выполненное действие.
Как можно заметить, с точки зрения узла, переславшего пакет, можно выделить 2 основных состояния:
1) пакет успешно передан:
Данное состояние наступает в случае, если узел передал пакет соседу и успешно принял обратное сообщение ACK.
2) пакет потерян:
Данное состояние наступает, если узел передал пакет данных соседу, но не получил обратное ACK сообщение. Такое событие может наступить в нескольких случаях:
- пакет данных был потерян в процессе передачи по беспроводному каналу;
- пакет данных был принят узлом-соседом, но обратное ACK сообщение было потеряно в процессе передачи;
- узел-сосед стал недоступен в сети (из-за перемещения, отключения, перегрузки и т.п.).
Во всех вышеперечисленных случаях, узел-отправитель считает процесс передачи пакета до соседа неуспешным.
Таким образом, множество состояний узла-отправителя может быть выражено, как где:
s1 – пакет успешно передан;
s2 – пакет потерян.
С точки зрения возможных действий, которые может совершить узел-отправитель, то можно выделить 2 основных действия: 1) узел отправляет пакет:
Это действие означает, что узел-отправитель выбрал следующего узла-соседа для передачи пакета и выполнил процесс передачи. Данное действие выполняется в большинстве случаев, когда отправляющий узел имеет актуальную информацию о маршруте до адреса назначения, указанного в данном пакете, а также не имеет никаких перегрузок трафика.
2) узел удаляет пакет:
Данное действие означает, что узел-отправитель по какой-то причине не имеет возможности выбрать следующий узел для передачи данного пакета. Такое событие может произойти в случае, если:
- узел-отправитель не имеет ни одного узла-соседа в зоне досягаемости;
- узел-отправитель не имеет актуальной информации о маршруте до данного адреса получателя;
- обновление маршрутной информации (например, через процедуру поиска маршрута) заканчивается неудачей – например, адрес получателя больше не существует в сети;
- буфер приема узла-отправителя переполнен – например, из-за высокой интенсивности входящего трафика.
Таким образом, множество действий узла-отправителя может быть выражено, как: где:
а1 – отправить пакет;
а2 – удалить пакет. Согласно выражениям (12) и (13), обозначим вероятности переходов из состояний и величины ожидаемых наград за выбранные действия, соответственно:
а - вероятность перехода из состояния sj в sf,
- награда за успешную передачу пакета. Если узел-отправитель смог успешно передать пакет после неуспешной предыдущей передачи, то ему присваивается положительная награда, равная R±-±, (формула (8)).
Динамическое изменение (уменьшение) награды Д2_2 с увеличением количества неудачных попыток передачи подряд позволяет быстрее реагировать на события неуспешной передачи и более оперативно переключаться на альтернативные маршруты в сети, что особенно целесообразно в беспроводных сетях с неустойчивой топологией и зашумленным каналом передачи.
На рисунке 21 показан граф переходов между состояниями системы в зависимости от выбранного действия. Здесь множество состояний изображается как окружность, а все возможные действия - как стрелки с направлением в сторону конечного состояния. Каждая стрелка, отображающая то или иное действие, имеет подпись в виде величины вероятности перехода в заданное состояние - Ps% , а также значение награды, которое будет получено при выполнении данного действия - R sf . Иными словами, каждая стрелка соответствует набору {A, Ps% , R%t}, где s - следующее состояние. Сумма вероятностей перехода для каждого действия равно 1.
Методика оценки производительности протоколов маршрутизации в условиях реальной сети
Для оценки производительности разработанного протокола маршрутизации, а также для его сравнения с существующим протоколом B.A.T.M.A.N., в реальной тестовой сети были измерены показатели производительности сети а именно:
- средняя двусторонняя задержка на маршруте (RTT);
- среднее значение процента потерь пакетов на маршруте (PLR);
- среднее время восстановления маршрута (RRT, Route Recovery Time).
Для оценки процента потерь пакетов, времени двусторонней задержки (RTT), а также времени восстановления маршрута (RRT), было использовано сетевое приложение ping.
В процессе тестирования была определена сетевая сессия, в ходе которой осуществлялся процесс передачи пакетов от узла-источника до узла-получателя. Каждая сессия имела следующие характеристики:
ICMP трафик:
- длительность сессии: 100 секунд;
- количество сессий (повторений): 100 сессий.
Значение двусторонней задержки (RTT) представляет собой величину времени передачи пакета данных от источника до получателя и обратно. Данная характеристика играет важную роль в оценке качества соединения и является одной из метрик QoS, по которой можно судить о возможности гарантирования заданного качества обслуживания в данной сети передачи данных. Значение RTT вычисляется как разница временных интервалов посылки ICMP-request пакета и получения обратного ICMP-reply сообщения с помощью утилиты ping. Процесс пересылки ICMP пакетов изображен на рисунке 29.
Значение процента потерь пакетов (Packet Loss Ratio – PLR) показывает долю потерянных пакетов из общего числа переданных. Данный показатель рассчитывается без механизма надежной доставки пакетов ARQ, находящегося на L4 уровне (например, в случае с TCP), так как передача пакетов осуществляется по протоколу ICMP, не имеющему ARQ механизмов для повторной передачи потерянных пакетов. Таким образом, полученные значения процента потерь пакетов точнее отражают процессы, происходящие прежде всего на L2 и L1 уровне модели OSI. Данная метрика вычислялась по следующей формуле
Значение времени восстановления маршрута (Route Recovery Time – RRT) показывает важную характеристику производительности протокола маршрутизации, отображающую степень гибкости алгоритма к динамическим изменениям сетевой топологии, что является критически важным для обеспечения заданного уровня качества соединения на маршруте. Время восстановления маршрута определяется как разница во времени между событием изменения топологии (поломки маршрута) и событием установления нового маршрута в изменившейся топологии, и может быть рассчитано как
Стоит отметить, что, в данной работе, время восстановления маршрута (Route Recovery Time – RRT) вычислялось в фазе пересылки пакетов – то есть, сеанс передачи пакетов (ICMP пакетов, в данном случае) был инициализирован по старому пути, после чего топология сети изменялась, но процесс передачи не останавливался. Момент времени выбора установления маршрута (Tnew_route) фиксировался как только ICMP пакеты из текущего сеанса стали пересылаться по новому маршруту.
Исходя из вышеперечисленных условий, была проведена серия экспериментов на реальной сети, в ходе которой были получены значения выбранных параметров на каждой сессии (повторении). Средние значения полученных данных вычислялись по формуле среднего арифметического значения
Собранная статистика значений параметров производительности протокола маршрутизации, полученных в результате эксперимента, их средние значения, а также доверительные интервалы представлены ниже.