close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
На правах рукописи
ДУГАЕВ ДМИТРИЙ АЛЕКСАНДРОВИЧ
РАЗРАБОТКА АДАПТИВНОГО АЛГОРИТМА МАРШРУТИЗАЦИИ
ДЛЯ БЕСПРОВОДНЫХ МНОГОУЗЛОВЫХ СЕТЕЙ ПЕРЕДАЧИ
ДАННЫХ
Специальность 05.12.13 – Системы, сети и устройства телекоммуникаций
Автореферат диссертации
на соискание ученой степени кандидата технических наук
Новосибирск 2018
2
Работа выполнена в федеральном государственном бюджетном
образовательном
учреждении
высшего
образования
«Сибирский
государственный университет телекоммуникаций и информатики»
Научный
руководитель:
Шувалов Вячеслав Петрович
доктор технических наук, профессор, «Сибирский
государственный университет телекоммуникаций и
информатики», заведующий кафедрой передачи
дискретных сообщений и метрологии
Официальные
оппоненты:
Бычков Евгений Дмитриевич
доктор технических наук, доцент, федеральное
государственное
бюджетное
образовательное
учреждение
высшего
образования
«Омский
государственный
университет
путей
сообщения», кафедра инфокоммуникационных систем
и информационной безопасности
Пономарев Дмитрий Юрьевич
кандидат технических наук, доцент, федеральное
государственное
бюджетное
образовательное
учреждение высшего образования «Сибирский
государственный университет науки и технологий им.
академика М. Ф. Решетнѐва», кафедра электронной
техники и телекоммуникаций
Ведущая
организация:
Федеральное
государственное
бюджетное
образовательное
учреждение
высшего
образования «Санкт-Петербургский государственный
университет телекоммуникаций им. проф. М. А. БончБруевича» (СПбГУТ), Санкт-Петербург
Защита диссертации состоится 13 апреля 2018 г. в 16.00 часов на
заседании
диссертационного
совета
Д 219.005.04
при
Сибирском
государственном университете телекоммуникаций и информатики по адресу:
630102, г. Новосибирск, ул. Кирова, 86.
С диссертацией можно ознакомиться в библиотеке Сибирского
государственного университета телекоммуникаций и информатики и на сайте
https://sibsutis.ru/science/postgraduate/dis_sovets/
Автореферат разослан «___» _____________ 2018 г.
Учѐный секретарь
диссертационного совета,
д.т.н., доцент
Абрамов Сергей Степанович
3
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы исследования.
В настоящее время, доставка информации до обычного пользователя во
многих случаях осуществляется при помощи беспроводных технологий
передачи данных. Скорости передачи данных по беспроводным каналам связи
непрерывно растут, тем самым стимулируя рынок связи предоставлять всѐ
большее количество контента конечным пользователям, расширяя рынок
телекоммуникаций. Только за последние 10 лет, средняя скорость передачи
данных по мобильной сети выросла с 0,02 МБ/с до 300 МБ/с, а текущие
современные стандарты беспроводных сетей Wi-Fi, являющиеся де-факто
основными способами первичного доступа в сеть Интернет для большинства
мобильных устройств, достигают скоростей в несколько гигабит в секунду
(стандарты IEEE 802.11ac/ad).
В связи с этим, именно технологии беспроводной передачи данных
имеют огромный потенциал для развития и постоянно находят всѐ новые ниши
для применения, в числе которых, так называемая концепция интернета вещей
(Internet of Things, IoT) и Industry 4.0, которые подразумевают объединение
различных умных вещей (Smart Things) в единую беспроводную сеть для
передачи различного рода сообщений. Сюда же можно отнести беспроводные
сенсорные сети (Wireless Sensor Networks, WSN), а также беспроводные
ячеистые сети (Wireless Mesh Networks, WMN), используемые в различных
сетевых приложениях, начиная от распределенных мобильных мессенджеров
(например, FireChat), до интеллектуальных систем уличного освещения (проект
SmartLighting). Последний из проектов имеют прямое отношение к данной
работе.
Однако, такие сети имеют недостатки, связанные, прежде всего, с
использованием беспроводных каналов передачи, а именно – с проблемами
обеспечения эффективного множественного доступа (Medium Access Control –
MAC), распределения частотных ресурсов, высокой вероятности битовых и
пакетных ошибок, коллизий, интерференций, а также передачи информации по
открытой беспроводной среде. Все вышеперечисленные проблемы имеют
корни, связанные с физическими характеристиками беспроводного канала, и
имеют решение на первых и вторых (L1 и L2) уровнях модели OSI того или
иного беспроводного стандарта, например, IEEE 802.11, 802.15.1, 802.15.4.
Нужно отметить, что в контексте беспроводных ячеистых сетей, интернета
вещей (IoT) и беспроводных сенсорных сетей, где, помимо ограничений
физического канала, существует проблема эффективной доставки пакетов
данных от узла-источника до узла-получателя через множество промежуточных
узлов данной сети. Так, в большинстве сенсорных сетей существует
необходимость передать накопленные данные из сенсорной сети во внешнюю
сеть через узел-шлюз (Gateway Node), для чего необходимо осуществить
процедуру поиска наилучшего маршрута через соседние узлы-сенсоры.
В настоящий момент, в беспроводных ячеистых сетях повсеместно
используется протокол маршрутизации B.A.T.M.A.N. (Better Approach to Mobile
4
Ad hoc Networking). Прежде всего, это связано с эффективной программной
имплементацией протокола, код которого постоянно поддерживается и
обновляется разработчиками. Протокол B.A.T.M.A.N. базируется на
улучшенном алгоритме проактивной маршрутизации и хорошо использует
ресурсы сети, однако имеет ряд проблем, которые связаны с динамической
топологией сети, а также ненадежными беспроводными каналами передачи, что
приводит к очень высоким процентам потерь пакетов на маршруте. Множество
других протоколов маршрутизации для данных сетей, к сожалению, не имеют
актуальной программной реализации, что делает затруднительным их
применение в реальных сетях. Таким образом, протокол B.A.T.M.A.N. является
де-факто основным протоколом маршрутизации в беспроводных ячеистых
сетях, но имеет ряд проблем с надежностью пересылки данных по маршруту.
Также стоит отметить, что в последнее время идея применения различных
алгоритмов на основе теории машинного обучения для сетевой маршрутизации
трафика находит всѐ большее применение. Это связано с тем, что алгоритмы
машинного обучения (и алгоритмы обучения с подкреплением, в частности)
хорошо подходят для решения задач оптимизации заданных параметров
системы при большом массиве входных данных. Задача маршрутизации
трафика является частным случаем таких задач, так как имеет множество
входных данных в виде набора сетевых узлов и адресов получателей, а также
задачу оптимизации нахождения маршрута (т.е. некоего подмножества узлов) в
сети с заданной метрикой – например, количеством промежуточных узлов в
маршруте, процентом потерь пакетов, уровнем беспроводного сигнала (RSSI),
или комбинацией нескольких метрик и т.д. Работы L.Peshkin и J.Dowling
описывают концепцию применения таких алгоритмов для задачи
маршрутизации в беспроводных многоузловых сетях. Данная диссертационная
работа развивает эту концепцию и предлагает улучшенные алгоритмы
нахождения узла-получателя при минимальном проценте потерь пакетов на
маршруте, по сравнению с существующими протоколами маршрутизации для
таких сетей.
Тема маршрутизации трафика в различных сетях передачи данных всегда
являлась важнейшим объектом для исследований. Среди отечественных
авторов по данной тематике можно выделить работы А.Е. Кучерявого, А.И.
Парамонова, А.В. Прокопьева, Б.С. Гольдштейна, С.Н. Новикова.
Цель работы.
Целью данной диссертационной работы является решение проблемы
эффективной маршрутизации трафика в многоузловых беспроводных сетях
передачи данных. А именно:
- разработка адаптивной схемы маршрутизации, обеспечивающей
приемлемый процент потерь пакетов в маршруте для многоузловых
беспроводных сетей передачи данных, основанной на математическом аппарате
выбора действия с использованием теории машинного обучения с
подкреплением;
5
- разработка механизма первичного обновления весов маршрутов и схемы
передачи пакетов по маршруту с применением обратной связи;
- разработка механизма увеличения/уменьшения награды соответственно
за выбор маршрута с высоким/низким процентом потерь пакетов на маршруте;
- анализ модели адаптивной маршрутизации на основе марковского
процесса принятия решений.
Данная диссертационная работа концентрируется на проблемах
производительности беспроводных многоузловых сетей передачи данных на
3-ем уровне модели OSI, а именно, на проблеме эффективной маршрутизации
трафика в таких сетях. Вопросы, связанные с работой беспроводных
протоколов на уровне 1 и 2 модели OSI в работе рассматриваются кратко.
Методы исследования.
Для решения поставленных задач выполнялся эксперимент на реальной
сети, а также математическое моделирование на основе марковского процесса
принятия решений. Методом статистического анализа, были получены
значения показателей производительности сети при применении разработанной
схемы маршрутизации и выполнено сравнение с традиционной схемой
маршрутизации. Показано преимущество разработанного алгоритма по
показателю процента потерь пакетов (Packet Loss Ratio – PLR) и по времени
восстановления маршрута (Route Recovery Time – RRT).
Соответствие паспорту специальности.
Результаты исследования соответствуют следующим пунктам паспорта
научной
специальности
05.12.13
«Системы,
сети
и
устройства
телекоммуникаций»:
Пункт 2: «Исследование процессов генерации, представления, передачи,
хранения и отображения аналоговой, цифровой, видео-, аудио- и мультимедиа
информации; разработка рекомендаций по совершенствованию и созданию
новых соответствующих алгоритмов и процедур».
В работе предложен новый алгоритм адаптивного выбора маршрута в
беспроводной многоузловой сети для входящего пакета данных, а также схема
передачи пакетов с применением механизма обратной связи.
Пункт 4: «Исследование путей совершенствования управления
информационными потоками».
В работе предложены схемы управления потоками данных в случае
сетевых перегрузок для целей балансировки сетевого трафика.
Пункт 12: «Разработка методов эффективного использования сетей,
систем и устройств телекоммуникаций в различных отраслях народного
хозяйства».
В работе предложен адаптивный метод маршрутизации трафика,
позволяющий эффективно использовать ресурсы сети.
Пункт 14: «Разработка методов исследования, моделирования и
проектирования сетей, систем и устройств телекоммуникаций».
В работе представлена математическая модель разработанной схемы
адаптивной маршрутизации, позволяющая оценивать характеристики
6
производительности маршрутизации в реальной сети, при условии наличия
информации о типе трафика и топологии данной сети.
Научная новизна.
- предложены формулы для вычисления награды за выбор маршрута,
учитывающие в отличие от существующих для алгоритмов машинного
обучения с подкреплением, уровень принимаемого беспроводного сигнала
(RSSI), что позволило включить в оценку качества маршрута текущие
физические характеристики беспроводной многоузловой сети;
- разработан механизм первичного распределения и вычисления весов
маршрутов на основе комбинации параметров уровня сигнала (RSSI) и
количества промежуточных узлов, который позволил точнее оценивать
качество выбранного маршрута в беспроводной многоузловой сети;
- разработан адаптивный алгоритм вычисления весов маршрутов в
зависимости от текущего процента потерь пакетов в канале, который позволил
значительно уменьшить количество потерянных пакетов в маршруте, по
сравнению с существующими решениями (протокол маршрутизации
B.A.T.M.A.N.);
- разработан алгоритм генерации негативной награды при передаче
пакета по ненадежному соединению, который позволил значительно уменьшить
время переключения на альтернативный, более надежный маршрут по
сравнению с традиционными схемами маршрутизации;
- предложен метод оценки вероятностей переходов «пакет отправлен» и
«пакет удален» для анализа производительности реальной сети, работающей по
предлагаемой схеме маршрутизации.
Достоверность.
Достоверность полученных результатов исследований подтверждена:
- результатами экспериментов на реальной сети;
- успешным внедрением разработанных алгоритмов в эксплуатацию.
Практическая ценность работы.
В рамках диссертационной работы был разработан универсальный
протокол маршрутизации для многоузловых сетей передачи данных,
эффективно работающий в сетях с ненадежными беспроводными
соединениями, а также в сетях с быстро меняющимися топологиями.
Разработанный протокол отличается высокой надежностью передачи пакетов
до узла-получателя, а также механизмом адаптации к изменениям топологии за
счѐт обратной связи, что отличает его от существующих имплементаций других
протоколов для подобных сетей, в частности – протокола маршрутизации
B.A.T.M.A.N. Кроме того, разработанный протокол является готовым
программным решением для эксплуатации в реальных сетях.
Внедрение работы.
Разработанный протокол маршрутизации был успешно внедрен в рамках
индустриального
проекта
интеллектуального
уличного
освещения
SmartLighting, разработанного при участии диссертанта в лаборатории FILA
(Future Internet Lab Anhalt), и развернутого в виде беспроводной многоузловой
7
сети с 19 узлами, расположенными на улице Магдебургер Шоссе, в городе
Бернбург, Германия.
Апробация работы.
Основные результаты работы были доложены в рамках следующих
научно-технических конференций:
- Конференция SibCON, Омск, 2015: «A survey and performance evaluation
of ad-hoc multi-hop routing protocols for static outdoor networks»;
- V Научно-практическая конференция «Информационно-измерительная
техника и технологии», Томск, 2014: «A Survey of Multi-Hop Routing Schemes in
Wireless Networks applied for the Smartlighting Scenario»;
- Конференция ICAIIT, Кѐтен, 2014: «A wireless mesh network NS-3
simulation model: implementation and performance comparison with a real test-bed»;
- XXV международная научно-практическая конференция «Инновации в
науке», СибАК, 2013: «Архитектура и гибридный протокол маршрутизации для
беспроводных ячеистых сетей на базе стандарта IEEE 802.11s»;
- Научно-техническая
конференция
«Современные
проблемы
телекоммуникаций», СибГУТИ, 2013: «Моделирование процедуры случайного
доступа в сетях мобильной связи LTE»;
- Научно-техническая конференция «Обработка информации и
математическое моделирование», СибГУТИ, 2013: «Описание симулятора
RACH канала сети LTE, Научно-техническая конференция»;
- V Международная
научно-практическая
конференция
«Телекоммуникационные и вычислительные системы», Москва, 2013: «Обзор
методов предварительного резервирования в WDM сетях»;
- IV Международная
научно-практическая
конференция
«Телекоммуникационные и вычислительные системы», Москва, 2012: «Расчет
коэффициента готовности служебного канала RACH при использовании его в
качестве ресурса для передачи пакетов из внешней сенсорной сети в сеть LTE».
Положения, выносимые на защиту.
- алгоритм адаптивной маршрутизации с применением теории обучения с
подкреплением, позволяющий в отличие от B.A.T.M.A.N. передавать пакеты
данных в беспроводной многоузловой сети с меньшими потерями;
- методика применения теории обучения с подкреплением для адаптивной
маршрутизации пакетного трафика в условиях ненадежной беспроводной среды
передачи;
- алгоритмы вычисления награды за выбор маршрута и обновления веса
маршрута в зависимости от коэффициента потерь пакетов и уровня
беспроводного сигнала (RSSI);
- алгоритм первичного обновления весов маршрутов при начальном
поиске узла-получателя.
8
Личное участие автора в получении научных результатов.
Автору принадлежит основная роль в решении задач и обобщении
результатов, представленных в диссертации.
Публикации.
По результатам проведенных исследований в рамках диссертационной
работы имеется 11 публикаций, 2 из которых опубликованы в изданиях,
рекомендованных ВАК, 1 проиндексирована в базе IEEE, Scopus и WoS.
Структура и объѐм работы.
Диссертация содержит 137 страниц, 32 рисунка, 9 таблиц, и включает
введение, 5 глав и заключение. Список литературы содержит 89 источников.
КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновывается актуальность поставленной задачи,
приведено описание целей и задач исследования, а также изложена основная
идея решения поставленной задачи. Перечислены основные проблемы
обеспечения производительности протоколов маршрутизации беспроводных
многоузловых сетей передачи данных.
В первой главе представлено подробное описание решения
поставленной задачи на основе применения теории машинного обучения с
подкреплением для выбора маршрута в беспроводной многоузловой сети.
Представлена классификация таких сетей (таблица 1), рассмотрены основные
проблемы обеспечения производительности маршрутизации в них, а также дано
обобщѐнное описание предлагаемой математической модели оптимизации
действий согласно теории обучения с подкреплением.
Таблица 1 – Классификация беспроводных многоузловых сетей
Интенсивность
трафика
Скорость передачи
данных
Размер сети
Топология
Степень автономности
L3-протокол
Область применения
Беспроводная
сенсорная сеть,
WSN
Беспроводная
ячеистая сеть,
WMN
Мобильная ad hoc
сеть, MANET
Низкая
Высокая
Средняя
10 – 100 Кбит/с
1 – 300 Мбит/с
0,1 – 1 Мбит/с
Средний – большой,
100 – 1000 узлов
Статическая и
динамическая
Высокая
LEACH, SPIN,
Flooding
Системы
распределенного
мониторинга
Средний, 10 – 100
узлов
Средний – большой,
100 – 1000 узлов
Статическая
Динамическая
Низкая
AODV, OLSR,
B.A.T.M.A.N.
Сеть передачи
данных, сеть
доступа
Средняя
AODV, OLSR, DSR
Сеть мониторинга,
сеть передачи
сообщений
9
Одной из основных задач данной диссертационной работы является
разработка обобщенного алгоритма маршрутизации, а именно, алгоритма
принятия решения об отправке пакета, исходя из сетевого трафика, топологии,
числа узлов, а также физических условий для передачи в данный момент
времени. Предлагается использовать математический аппарат из области
теории машинного обучения, а именно – теорию обучения с подкреплением
(Reinforcement Learning).
В первой главе дано описание теории машинного обучения с
подкреплением и механизм выбора действия на основе получаемой награды
(обратной связи).
Обучение с подкреплением вводит понятия агента, среды и награды
(agent, environment и reward, соответственно), которые описывают процесс
оптимизации по заданному критерию (например, числу успешно переданных
сообщений) при выполнении действий (например, выбора того или иного
маршрута в сети). На рисунке 1 изображѐн обобщенный процесс работы
механизма обучения с подкреплением, где агент А имеет некий набор действий
A, с помощью которых он взаимодействует со средой. Выполняя некое
действие A, агент получает награду от среды, и отталкиваясь от величины
полученной награды, формирует некое представление об оптимальности
сделанного выбора.
С математической точки зрения, такая модель описывается в рамках
марковской модели принятия решения (Markov Decision Process – MDP),
которая определяет 4 основных множества {S, A, P, R}, где:
S – множество состояний, в которых может находиться агент в данный
момент времени;
A – множество действий, которые может выполнить агент в данный
момент времени;
P – множество вероятностей, что, находясь в состоянии S, агент,
выполнив действие A, перейдет в состояние S′ за время t+1;
R – множество наград, получаемых за переход из состояния S в
состояние S′.
Рисунок 1 – Обобщенный механизм обучения с
подкреплением
10
В рамках теории обучения с подкреплением, множества S и P часто
интерпретируются как единое множество расчетных значений (estimation
values) Q, которое зависит от величины получаемой награды, а также от
состояния (шага t), в котором производилось данное действие. Один из авторов
теории, R.Sutton, описывает поставленную задачу следующей формулой:
[
],
(1)
где:
– значение расчетной величины награды Q на предыдущем шаге;
– значение расчетной величины награды Q на текущем шаге;
– значение реальной полученной награды;
– параметр шага;
k – текущий шаг.
Можно выделить две основные задачи обучения с подкреплением:
1) как обновлять множество расчетных значений Q после получения
награды?
Простейший способ – обновлять и хранить среднее значение получаемых
наград от действия A (метод скользящей средней).
2) каким образом, имея множества P и S, выбирать действие из
множества А?
Наиболее часто встречающиеся способы – это выбор действия с
максимальным значением награды (greedy метод), выбор случайного действия с
малой вероятностью ε (e-greedy метод), а также выбор взвешенного действия
(softmax метод).
Следует отметить, что предлагаемая в диссертации идея применения
различных алгоритмов на основе теории машинного обучения для сетевой
маршрутизации трафика содержится также в работах L.Peshkin и J.Dowling. В
работах Z.Qin, Z.Zia и X.Chen предлагаются алгоритмы динамического
программирования, схожие с алгоритмами машинного обучения. Однако,
данные работы содержат лишь описание концепций использования алгоритмов,
а также аналитическое описание их применения на реальных сетях, без
предложения конкретных методик расчета вероятностей выбора того или
иного маршрута, а также четко структурированного алгоритма маршрутизации
на основе выбранной теории.
Во второй главе представлено аналитическое описание задачи
маршрутизации в беспроводных многоузловых сетях передачи данных и
описание классических протоколов маршрутизации, используемых в таких
сетях (AODV, DSDV, OLSR и DSR). Дано описание алгоритмов нахождения
маршрута, а также используемых метрик маршрутизации. Сделаны выводы о
недостатках и достоинствах тех или иных схем в контексте применения в
реальных беспроводных многоузловых сетях передачи данных.
В третьей главе описываются основные элементы теории машинного
обучения с подкреплением. В частности, приводится расчет функции значений,
11
которая используется для вычисления вероятности выбора того или иного
действия.
Одним из наиболее простых, но тем не менее, эффективных методов
расчета функции значений является метод среднего выборочного (sample
average) значения.
Обозначим настоящее значение награды на шаге Т как:
.
Тогда, при
,
.
Простым методом выбора действия является метод, при котором в
большинстве случаев выбирается действие с максимальным значением
награды, однако, с определенной малой вероятностью ε, случайным способом
выбирается другое действие на некотором шаге. Такой метод называется εжадным (ε-greedy), и обеспечивает выполнение условия:
, при
.
Иными словами, при достаточно высоком числе итераций k, каждое
действие будет исследовано, гарантируя оптимальность последующих шагов.
Рисунок 2 – Взаимосвязь задачи маршрутизации (слева) с задачей обучения с
подкреплением (справа)
Задачу маршрутизации в беспроводных многоузловых сетях можно
разделить на два основных режима:
1) режим первичного поиска маршрута до узла-получателя:
Используется в случае, если узел сети не имеет никакой информации о
маршруте до узла-получателя, и инициализирует процедуру поиска маршрута;
2) режим пересылки пакетов:
12
Данный режим используется при нормальном функционировании сети,
когда узел имеет информацию о дальнейшем маршруте входящего пакета. В
данном режиме узел сети принимает решение о передаче пакета следующему
узлу-соседу, который является частью маршрута до узла-получателя.
Протокол маршрутизации в режиме первичного поиска маршрута
использует реактивную схему пересылки служебных сообщений RREQ и RREP,
которые распространяют информацию о сетевой топологии в процессе их
передачи по сети.
В четвертой главе обозначаются основные взаимосвязи задачи
маршрутизации с теорией обучения с подкреплением, которые могут быть
выражены следующим образом:
- узел-источник ↔ агент;
- соседи узла-источника ↔ множество действий А;
- таблица маршрутов ↔ набор значений ожидаемой награды Q;
- узел-источник посылает пакет к узлу-соседу ↔ агент выбрал действие и
выполнил его;
- узел-источник получил ACK сообщение от соседа ↔ агент получил
награду за выполненное действие.
В случае, когда узел сети принимает входящий пакет данных с
определенным адресом назначения (адресом узла-получателя), он выбирает
следующий узел из списка текущих узлов-соседей и пересылает принятый
пакет, ожидая ответное ACK сообщение, содержащее награду за выбранный
узел. В течение данного процесса, может произойти 3 события:
1. Потеря пакета с данными или потеря обратного ACK сообщения.
В таком случае, узел-отправитель не получит сообщение ACK, и через
определенный таймаут, присвоит негативное значение награды за выбранный
маршрут. При потерях пакетов, имеет смысл снизить вероятность выбора
данного соседа для пересылки данных на определенный адрес получателя. Это
обеспечивается путѐм присваивания негативного значения награды за
выбранное действие.
2. Получение ответного ACK сообщения с низкой наградой.
Данная ситуация подразумевает, что выбранный соседний узел успешно
получил пакет с данными и успешно отправил обратное ACK сообщение до
узла-отправителя. Однако, низкое значение награды уменьшит вероятность
выбора данного узла-соседа при следующих передачах.
3. Получение ответного ACK сообщения с высокой наградой.
Если принятое ACK сообщение содержит высокое значение награды, то
это означает, что выбранный узел-сосед имеет хороший маршрут до узлаполучателя, и выбранное действие является хорошим решением для пересылки
пакета далее. Высокая награда увеличит вероятность выбора данного узла на
следующих итерациях.
13
Поиск маршрута производится путем рассылки специального
широковещательного сообщения RREQ (запрос маршрута) в сторону всех
узлов-соседей. Узлы-соседи, приняв сообщение RREQ, пересылают его далее по
сети. Значение ожидаемой награды за выбранное действие (в представляемом
случае, действие – это выбор и пересылка пакета следующему узлу-соседу)
обновляется на каждом шаге (формула (1)).
Первичное распределение значений ожидаемой награды (т.е. веса
маршрутов) предлагается вычислять по следующей формуле:
|
|
(2)
{
где:
– ожидаемый вес маршрута для данного адреса узла-получателя;
RSSI – индикатор уровня входящего беспроводного сигнала (Received
Signal Strength Indicator), в диапазоне [-100, 0] дБм;
– число промежуточных узлов, через которые прошли RREQ/RREP
сообщения.
Таким
образом,
изначально,
короткие
маршруты
имеют
более
высокую вероятность быть
выбранными. Однако, данная
вероятность
может
быть
изменена уже в процессе
передачи пакетов, так как
наикратчайший маршрут не
всегда является оптимальным
из-за непостоянной топологии
и
беспроводной
среды
передачи. Такие изменения в
маршруте
постоянно
отслеживаются при помощи
обратных ACK сообщений –
чем хуже становится линк, тем
меньше
вероятность
его
выбора
при
следующей
передаче пакета.
Рисунок 3 – Обобщенная схема обратной связи с
В режиме пересылки
задержкой
пакетов, узел сети выбирает
следующий узел (next hop node) для отправки текущего пакета в сторону узлаполучателя. Решение о выборе следующего узла из множества узлов-соседей
14
основывается на значении ожидаемой награды за выбор данного конкретного
узла. После того, как узел выбрал следующий адрес соседа из текущего
множества и послал пакет с данными, он ожидает обратное ACK сообщение с
наградой в течение определенного таймаута.
Узел посылает первый пакет в сторону соседа и ожидает в течение
заданного интервала задержки ACK, который предлагается вычислять по
формуле:
,
(3)
где:
– ожидаемое время двусторонней задержки (Round Trip Time)
между отправителем и получателем;
– значение задержки на время генерации ACK сообщения на
приемной стороне;
– значение погрешности во времени передачи, которое зависит от
особенностей работы канального (L2) уровня сети, отвечающего за алгоритм
множественного доступа (например, таймауты CSMA/CA), надежную
пересылку (таймауты канального ARQ) и т.д.
В разработанной схеме маршрутизации, генерация значений награды
осуществляется следующим образом – когда узел получает пакет с данными от
узла-источника, он вычисляет значение награды по предлагаемой формуле:
|
|
(4)
{
где:
∑
– среднее значение ожидаемой награды, посылаемое в
сторону отправителя, и вычисляемое из таблицы маршрутов текущего узла;
– ожидаемая награда при выборе узла-соседа в сторону i-го
адреса-получателя (DST_IP);
– общее количество узлов-соседей в сторону адреса получателя
(количество всех возможных действий).
Диапазон значений наград варьируется от 0 до 100. Значение
отрицательной награды равно -1.
Предлагаемый алгоритм выбора маршрута основывается на методе
взвешенного действия (softmax метод). В основу данного метода положено
вероятностное распределение Гиббса-Больцмана, которое выражается
формулой:
∑
(5)
15
где:
– вероятность выбора действия а на шаге t ;
– ожидаемое значение награды за выбор действия а на шаге t ;
– ожидаемое значение награды за иное действие b на шаге t ;
– положительный параметр, называемый температурой.
В контексте поставленной задачи маршрутизации, параметр
температуры определяет насколько высока вероятность выбора маршрута с
максимальным значением ожидаемой награды. Данный параметр предлагается
динамически изменять его в зависимости от текущего процента потерь
пакетов на линке (PLR), а именно:
{
(6)
где:
– процент потерь пакетов (Packet Loss Ratio),
заданный в диапазоне значений [0, 100];
– параметр температуры из распределения Гиббса-Больцмана;
– предлагаемый коэффициент роста, равный 0,5 по-умолчанию.
Рисунок 4 – Распределение вероятностей выбора узлов 1-5 в зависимости от
PLR; P(0) = {#1 : 0.35, #2 : 0.07, #3 : 0.01, #4 : 0.2, #5 : 0.37}
16
Поставленная задача маршрутизации трафика в беспроводной
многоузловой сети, с точки зрения теории машинного обучения с
подкреплением, может быть представлена в качестве конечного марковского
процесса принятия решения (finite Markov Decision Process – MDP).
Данный процесс может быть описан с помощью двух основных
множеств, отображающих множество действий A = {a1, a2, ... , an}, и множество
состояний S = {s1, s2, ... , sn}, в которых находится система в данный момент
времени. Соответственно, вероятность перехода из текущего состояния s в
состояние s′, после выполнения действия а, можно выразить следующим
образом:
{
|
(7)
Полученные вероятности называют вероятностями перехода (transition
probabilities). Подобным образом, можно выразить ожидаемое значение
награды за выбранное действие а, при переходе из состояния s в состояние s′ :
{
|
(8)
Полученные выражения
и
полностью описывают динамику
переходов марковского процесса принятия решения для данной задачи.
В контексте задачи сетевой маршрутизации и разработанного алгоритма,
в частности, можно выделить следующие состояния:
{
(9)
где:
s1 – пакет успешно передан;
s2 – пакет потерян.
С точки зрения возможных действий, которые может совершить узелотправитель, то можно выделить 2 основных действия:
{
(10)
где:
а1 – отправить пакет;
а2 – удалить пакет.
Согласно выражениям (9) и (10), запишем вероятности переходов из
состояний и величины ожидаемых наград за выбранные действия,
соответственно:
α – вероятность перехода из состояния s1 в s1;
(1 – α) – вероятность перехода из состояния s1 в s2;
β – вероятность перехода из состояния s2 в s2;
(1 – β) – вероятность перехода из состояния s2 в s1.
17
Множество значений ожидаемых наград описывается выражением:
{
(11)
где:
– награда за успешную передачу пакета. Данную награду
предлагается рассчитывать согласно формуле (4);
– награда за единичную неудачную передачу пакета. Данная награда
имеет фиксированное значение по-умолчанию:
,
где:
n – количество неудачных попыток передачи.
– награда за повторные неудачные попытки передачи пакета. Данное
значение награды предлагается понижать по экспоненциальному закону, что
позволяет быстрее переключаться на альтернативный маршрут, уменьшая
вероятность потери пакетов в целом:
(12)
– награда за успешную передачу пакета. Если узел-отправитель смог
успешно передать пакет после неуспешной предыдущей передачи, то ему
присваивается положительная награда, равная
(формула (4)).
На рисунке 5 показан граф переходов между состояниями системы в
зависимости от выбранного действия. Здесь множество состояний изображается
как окружности, а все возможные действия – как стрелки с направлением в
сторону конечного состояния. Каждая стрелка, отображающая то или иное
действие, имеет подпись в виде величины вероятности перехода в заданное
состояние –
, а также значение награды, которое будет получено при
выполнении данного действия –
. Каждая стрелка соответствует набору {A,
,
}, где s′ – следующее состояние. Сумма вероятностей переходов для
каждого действия равна 1.
Рисунок 5 – Вероятностный граф состояний переходов {A,
,
}
18
Таким образом, получаем матрицу вероятностей переходов для действий
а1 и а2 соответственно:
[
]
[
]
(13)
Матрица наград за выполненные действия выглядит следующим образом:
[
]
Значения вероятностей переходов α
экспериментально, по следующим формулам:
[
]
и
β
можно
(14)
определить
(15)
(16)
где:
– число подряд успешно переданных пакетов;
– число подряд потерянных пакетов;
– суммарное число пакетов.
Программная
имплементация
разработанного
алгоритма
маршрутизации реализована на языке программирования Python 2.7 и работает
на вычислительных устройствах на базе операционной системы Линукс,
имеющих либо проводные IEEE 802.3 Ethernet, PLC, либо беспроводные
сетевые интерфейсы IEEE 802.11 Wi-Fi или IEEE 802.15.4. Разработанный
протокол базируется на стандартном стеке сетевых протоколов TCP/IP с
поддержкой IPv4 и IPv6 адресации. Кроме того, протокол независим от
вышестоящих (L4) и нижележащих (L2, L1) уровней модели OSI, что делает его
универсальным решением для маршрутизации пакетного трафика в сетях с
любыми топологиями, типами трафика, а также средами передачи (как
проводными, так и беспроводными).
В пятой главе описывается экспериментальное исследование
разработанной
схемы
маршрутизации.
Целью
экспериментального
исследования является тестирование протокола в реальной беспроводной
многоузловой сети передачи данных, разработанной в рамках проекта
интеллектуального
уличного
освещения
SmartLighting,
в
котором
19
предусмотрено наличие беспроводных узлов передачи данных, расположенных
в статических топологиях вдоль пешеходных зон улиц.
Кроме того, помимо разработанного протокола, в тестирование было
включено широко используемое решение стороннего разработчика – протокол
маршрутизации B.A.T.M.A.N., чтобы иметь возможность сравнения
производительности в одинаковых, заранее известных условиях передачи.
Схема тестовой топологии показана на рисунке 6. При этом, узелисточник и узел-получатель не соединены друг с другом напрямую, а только
через 5 промежуточных узлов-соседей, что обеспечивает реализацию задачи
маршрутизации в поставленных условиях.
Рисунок 6 – Схема тестовой топологии
В условиях заданной тестовой сети и с учетом ее назначения, были
выбраны следующие параметры для тестирования:
- значение RTT (Round Trip Time, двухсторонняя задержка);
- процент потерь ICMP пакетов (Packet Loss Rate, PLR);
- время восстановления маршрута (Route Recovery Time, RRT).
Согласно результатам проведѐнных экспериментов, разработанный
протокол маршрутизации, базирующийся на схеме обратной связи с
адаптивным механизмом обновления весов маршрутов показал лучший
результат по показателю процент потерь пакетов (PLR) (рис. 7). Это позволяет
сделать вывод об эффективности разработанного протокола при применении на
беспроводных многоузловых сетях передачи данных, особенно при
ненадежных условиях передачи. Кроме того, механизм выбора маршрута с
обратной связью позволяет быстрее реагировать на изменения в топологии
сети, без увеличения количества передаваемых служебных сообщений. Так,
показатель времени восстановления маршрута (Route Recovery Time, RRT)
оказался значительно меньше (рис. 8), чем у схем маршрутизации с
проактивным механизмом (как в протоколе B.A.T.M.A.N.).
В рамках данной работы, были проведены эксперименты на реальной
беспроводной многоузловой сети, которые показали эффективность
разработанной схемы маршрутизации в рамках процента потерь пакетов и
времени восстановления маршрута, что позволяет передавать пакеты данных
20
значительно надежнее и с меньшими потерями (в том числе, за счет
существенно меньшего времени восстановления маршрута), чем существующие
аналоги.
Процент потерь пакетов (PLR), %
16
14
12
10
Разработанный
протокол (RLRP)
8
Протокол B.A.T.M.A.N.
6
4
2
0
Рисунок 7 – Средние значения процента потерь пакетов (PLR) в маршруте при
разработанном протоколе и протоколе B.A.T.M.A.N.
Время восстановления маршрута
(RRT), секунды
100
90
80
70
60
50
Разработанный
протокол (RLRP)
Протокол B.A.T.M.A.N.
40
30
20
10
0
Рисунок 8 – Средние значения времени восстановления маршрута для
разработанного протокола маршрутизации (RLRP) и протокола B.A.T.M.A.N.
Перспективы дальнейшей разработки лежат в обновлении
программной имплементации протокола на язык программирования C, что
позволит значительно увеличить пропускную способность маршрута по
сравнению с существующими протоколами.
Сфера применения разработанного протокола маршрутизации лежит в
развѐртывании распределѐнных беспроводных многоузловых сетей передачи
21
данных на объектах промышленности и инфраструктуры – например,
сенсорной сети мониторинга газопроводов, интеллектуальной системы
уличного освещения и так далее.
В заключении представлены результаты исследования и дана оценка
эффективности разработанной схемы маршрутизации в контексте еѐ
применения в реальных сетях.
Основные результаты работы:
- разработан алгоритм адаптивной маршрутизации пакетов на основе
машинного обучения с подкреплением для беспроводных многоузловых сетей
передачи данных;
- разработан алгоритм первичного обновления весов маршрутов при
первичном поиске узла-получателя, а также алгоритм обновления весов
маршрутов на основе обратной связи;
- разработана программная имплементация алгоритма маршрутизации с
адаптивным механизмом выбора маршрутов;
- проведены
экспериментальные
исследования
и
тестирование
разработанного протокола в реальной сети.
Приложение содержит акты внедрения результатов диссертационной
работы.
22
СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ
В рецензируемых журналах из списка ВАК:
1. Д. А. Дугаев, Д. С. Качан, И. С. Федотова Концепция маршрутизации
трафика в мобильных ad-hoc сетях с использованием высокоточных измерений
доступной полосы пропускания // Вестник СибГУТИ №4. – 2015. –
Новосибирск. – С. 90-98.
2. Дугаев Д.А. Исследование времени установления соединения в
восходящем (uplink) направлении в сетях LTE // T-Comm - Телекоммуникации
и Транспорт. – Москва. – № 5, 2013. – С. 25-28.
Индексируемые в базе данных Scopus и WoS:
3. D. Dugaev, S. Zinov, E. Siemens, V. Shuvalov A survey and performance
evaluation of ad-hoc multi-hop routing protocols for static outdoor networks //
International Siberian Conference on Control and Communications (SIBCON-2015),
May 21 - 23, 2015, Omsk, Russia, pp. 1-11.
В других изданиях:
4. D. Dugaev, S. Zinov, E. Siemens A Survey of Multi-Hop Routing Schemes
in Wireless Networks applied for the Smartlighting Scenario // V international
science conference “Technologies and equipment for information measurement”,
Tomsk, Russia, May 2014, pp. 186-190.
5. D. Dugaev A wireless mesh network NS-3 simulation model:
implementation and performance comparison with a real test-bed // 2-nd ICAIIT
conference, Koethen, Germany, March 2014, pp. 1-6.
6. Дугаев Д.А. Архитектура и гибридный протокол маршрутизации для
беспроводных ячеистых сетей на базе стандарта IEEE 802.11s // XXV
международная научно-практическая конференция «Инновации в науке». –
СибАК. – 2013. – С. 39-44.
7. Дугаев Д.А. Моделирование процедуры случайного доступа в сетях
мобильной связи LTE, Научно-техническая конференция «Современные
проблемы телекоммуникаций». – СибГУТИ. – 2013. – С. 81-82.
8. Дугаев Д.А. Описание симулятора RACH канала сети LTE, Научнотехническая конференция «Обработка информации и математическое
моделирование». – СибГУТИ. – 2013.
9. Дугаев Д.А. Исследование зависимости времени установления
соединения от числа абонентов сети LTE // Международная научнопрактическая конференция «Современное общество, образование и наука». –
Тамбов. – 2013.
10. Дугаев Д.А. Обзор методов предварительного резервирования в WDM
сетях
//
V
Международная
научно-практическая
конференция
«Телекоммуникационные и вычислительные системы». – Москва. – 2013.
11. Дугаев Д.А. Расчет коэффициента готовности служебного канала
RACH при использовании его в качестве ресурса для передачи пакетов из
внешней сенсорной сети в сеть LTE // IV Международная научно-практическая
конференция «Телекоммуникационные и вычислительные системы». – Москва.
– 2012.
23
Дугаев Дмитрий Александрович
Автореферат
диссертации на соискание ученой степени
кандидата технических наук
Подписано в печать______
Формат бумаги 62х84/16, отпечатано на ризографе, шрифт №10,
изд. л. 1,3, заказ №___, тираж – 100 экз., СибГУТИ
630102, г. Новосибирск, ул. Кирова, 86.
Документ
Категория
Без категории
Просмотров
10
Размер файла
1 072 Кб
Теги
маршрутизация, данных, беспроводные, алгоритм, разработка, передача, адаптивного, сетей, многоузловых
1/--страниц
Пожаловаться на содержимое документа