Управление информационными потоками в ad hoc сетях на основе адаптивного алгоритма Q-routing тема диссертации и автореферата по ВАК РФ 05.12.13, кандидат наук Шилова Юлия Александровна

• Шилова Юлия Александровна
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Шилова Юлия Александровна

Введение

Глава 1. Протоколы маршрутизации в беспроводных сетях

1.1 Обзор беспроводных сетей

1.2 Обзор существующих алгоритмов маршрутизации в мобильных ad hoc сетях

1.3 Группа алгоритмов семейства Q-routing, построенных на машинном обучении

1.4 Протоколы и алгоритмы, учитывающие влияние параметра «уровень заряда батареи» при выборе маршрута

1.5 Постановка цели и основных задач исследования

1.6 Выводы по главе

Глава 2. Исследование возможности повышения эффективности алгоритмов маршрутизации семейства Q-routing

2.1 Базовый алгоритм Q-routing

2.2 Новый метод заполнения Q-таблицы

2.3 Алгоритм Adaptive Rate Full Echo

2.4 Постановка математической задачи

2.5 Выводы по главе

Глава 3. Разработка имитационной модели предложенного нового алгоритма Adaptive Rate Full Echo

3.1 Цели и задачи имитационного моделирования

3.2 Аналитический обзор и выбор системы имитационного моделирования.... 67 3.3. Разработка имитационной модели алгоритма Adaptive Rate Full Echo

3.3.1 Процесс построения модели Adaptive Rate Full Echo

3.3.2 Структура модели алгоритма Adaptive Rate Full Echo

3.3.3 Алгоритм формирования и обработки сообщений с данными

3.3.4 Алгоритм формирования и обработки сообщений с управляющей информацией

3.3.5 Событие «снижение заряда батареи»

3.3.6 Разработка пользовательского интерфейса модели

3.4 Результаты имитационного моделирования

3.4.1 Результаты имитационного моделирования по критериям среднего времени доставки пакетов по сети и времени автоконфигурирования сети

3.4.2 Результаты имитационного моделирования по критерию время жизни сети

3.5 Поверка и верификация модели натурными экспериментами

3.5.1 Разработка приложения, реализующего работу алгоритма Adaptive Rate Full Echo

3.6 Выводы по главе

Глава 4. Построение системы «Умный дом»

4.1 Архитектура системы «Умный дом»

4.1.1 Структура системы связи «Умный дом»

4.1.2 Описание параметров системы

4.2 Результаты внедрения разработанного алгоритма Adaptive Rate Full Echo

4.2.1 Оценка параметров среднее время доставки пакетов по сети и время автоконфигурирования сети

4.2.2 Оценка параметра время жизни сети

4.3 Выводы по главе

Заключение

Список литературы

Приложение А

Приложение Б

Приложение В

Введение диссертации (часть автореферата) на тему «Управление информационными потоками в ad hoc сетях на основе адаптивного алгоритма Q-routing»

Введение

Актуальность темы исследования. В современном мире мобильные ad hoc сети являются одной из перспективных технологий, и по многим прогнозам ожидается, что такие сети в ближайшее время будут занимать все большую долю на рынке (ad hoc - означает «для данного случая»). Применительно к сети слово ad hoc предполагает, что сеть состоит из множества узлов свободно перемещающихся друг относительно друга, причём в сети нет единого координирующего центра. В сети отсутствует предварительно выстроенная инфраструктура, поэтому каждый из узлов такой сети одновременно становится и конечным устройством, принимающим и отправляющим пакеты, и устройством, осуществляющим построение возможных маршрутов и передачу данных в этой сети. Сетевая топология и соединения между узлами формируются самими узлами в процессе коммуникации друг с другом. Отсутствие заранее выстроенной инфраструктуры позволяет формировать такие сети для решения различных задач, подбирая наиболее удобную конфигурацию для каждой в отдельности. Самым простым примером таких сетей являются сети смартфонов, выстраивающих взаимодействие между собой для передачи какой-либо информации. В качестве других примеров можно привести сети транспортных средств, мобильные сенсорные сети, сети так называемого «интернета вещей» (Internet of Things), группы взаимодействующих роботов и т.д.

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

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

Степень разработанности темы. Существует множество используемых протоколов маршрутизации для мобильных ad hoc сетей, например, DSR (Dynamic Source Routing) [1, 2], AODV (Ad hoc On-Demand Distance Vector) [3], TORA (Temporally ordered routing algorithm) [4], DYMO (The Dynamic MANET On-demand routing protocol) [5], ZRP (Zone Routing Protocol) [6], HWMP (Hybrid Wireless Mesh Protocol) [7], DSDV (Destination Sequenced Distance Vector) [8], OL SR (Optimized Link State Routing) [9, 10], F SR (Fish eye State Routing) [11], разработкой и возможностями повышения эффективности которых занимались такие отечественные и зарубежные авторы как M. JI. Карманов [12], В. М. Винокуров [13], А. В. Пуговкин [13], И. О. Датьев [14], В. М. Поляков [15], В. Г. Орлов [16], D. Johnson [1, 2, 17], Ch. Perkins [18, 19], Т. Clausen [10], P. Jacquet [9] и др. В реактивных протоколах (Perkins Ch., Roy er E., Johnson D., Maitz D., Hu Yu., Bhagwat P.) [1, 2, 12-15, 18-24] для определения оптимальности маршрута используется алгоритм определения кратчайшего пути на основе одной метрики, а именно, наименьшего числа ретрансляций пакета. В проактивных протоколах (Jacquet P., Muhlethaler P., Guangyu P., Mario G., Tsu-Wei С.) [4, 7-11, 25-29] выполняется комплексная оценка маршрутов по нескольким параметрам. Однако в большинстве вышеперечисленных алгоритмов для определения кратчайшего пути используются алгоритмы Дейкстры [30] и Беллмана-Форда [31]. Недостаток алгоритма Дейкстры заключается в определении кратчайшего пути по количеству хопов, так как в случае высокой нагрузки в сети узлы, попавшие в состав кратчайших маршрутов, будут перегружены. Кроме того, данный алгоритм не имеет возможности выбора маршрута с учетом нескольких факторов. Недостатками алгоритма Беллмана-Форда являются необходимость в большом

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

Зарубежные ученые М. L. Littman [32, 33] и J. A. Boyan [32] разработали алгоритм Q-routing, основанный на машинном обучении (обучении с подкреплением), который частично устраняет недостатки предыдущих алгоритмов. На основе Q-routing было выделено целое семейство алгоритмов Q-routing, авторами которых являются Sh. Kumar [34, 35], В. Rüssel [28], P. Desai [36, 37], D. Y. Yeung [38], D. Kumar [21, 30, 39], D. Subramanian [40], P. Druschel [40] и др. Алгоритмы семейства Q-routing пытаются сбалансировать предлагаемую загрузку сети и минимизировать время прохождения пакета до места назначения для всех маршрутов в данной сети путем расчета разными способами задержек в сети, как самих узлов, так и их соседей, а также изменением количества служебных сообщений.

Однако ни один из алгоритмов семейства Q-routing не учитывает физических характеристик узлов сети, хотя сети, в которых используются эти алгоритмы, формируются, как правило, на беспроводных устройствах. «Уровень заряда батареи» беспроводного устройства является одним из самых важных параметров, который необходимо учитывать, так как он напрямую влияет на связность сети. В беспроводных сетях связность сети является одним из критических параметров, поскольку напрямую влияет на время жизни сети и на функционирование сети в целом.

Объектом исследования являются динамически изменяющиеся сети ad hoc.

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

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

Q-routing при выполнении процесса маршрутизации с использованием принципов обучения с подкреплением.

Задачи исследования. Для достижения поставленной цели в рамках диссертационной работы необходимо решить следующие основные задачи:

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

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

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

4. Разработать новый алгоритм маршрутизации Adaptive Rate Full Echo на основе базового алгоритма Q-routing, отличающийся одновременным учетом существующих критериев среднего времени доставки и длительности процесса автоконфигурирования сети с параметром «уровень заряда батареи» устройства с целью увеличения времени жизни сети, снижения среднего времени доставки пакетов и длительности процесса автоконфигурирования сети.

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

6. Выполнить внедрение разработанного алгоритма маршрутизации на основе практической реализации в составе системы «Умный дом» при участии ООО «ЮНИКОРН».

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

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

2. Разработан новый адаптивный алгоритм Adaptive Rate Full Echo, главными особенностями которого являются учет параметра «уровень заряда батареи», разделение коэффициентов обучения и их динамическое изменение в зависимости от глобальной оценки состояния сети, а также текущей оценки соседних узлов, что привело к увеличению времени жизни сети, снижению среднего времени доставки и уменьшению длительности процесса автоконфигурирования сети.

3. Разработана оригинальная имитационная модель алгоритмов Q-routing и созданного алгоритма в программной среде Anylogic, отличающаяся учетом параметра «уровень заряда батареи» устройства, позволяющая корректно применять математический аппарат для совместной оценки времени жизни сети, среднего времени доставки и длительности процесса автоконфигурирования сети.

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

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

Результаты диссертационного исследования реализованы в рамках системы «Умный дом» при участии ООО «ЮНИКОРН» в общении с беспроводной сетью датчиков. Система размещена в многоквартирном доме из четырех подъездов, по сорок квартир в каждом подъезде, более 2400 датчиков.

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

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

1. Метод вычисления значений Q-таблицы, относительно которых определяется выбор маршрута, позволяющий учитывать дополнительный

параметр «уровень заряда батареи», что дало возможность увеличить время жизни сети (п. 2, 4 паспорта специальности).

2. Новый адаптивный алгоритм Adaptive Rate Full Echo, главными особенностями которого являются учет параметра «уровень заряда батареи», разделение коэффициентов обучения и их динамическое изменение в зависимости от глобальной оценки состояния сети, а также текущей оценки соседних узлов, что привело к увеличению времени жизни сети, снижению среднего времени доставки пакетов по сети и уменьшению длительности процесса автоконфигурирования сети (п. 4 паспорта специальности).

3. Оригинальная имитационная модель алгоритмов Q-routing и разработанного алгоритма Adaptive Rate Full Echo в программной среде Anylogic, отличающаяся учетом параметра «уровень заряда батареи» устройства, позволяющая корректно применять математический аппарат для совместной оценки времени жизни сети, среднего времени доставки пакетов по сети и длительности процесса автоконфигурирования сети (п. 14 паспорта специальности).

4. Результаты внедрения алгоритма маршрутизации в системе «Умный дом» при общении с беспроводной сетью датчиков, показавшие увеличение времени жизни сети на 50%, снижение среднего времени доставки в процессе автоконфигурирования сети на 53,9%, в установившемся режиме - на 30,9%, уменьшение длительности автоконфигурирования сети на 17,5% (п. 14 паспорта специальности).

Достоверность полученных результатов. Полученные в диссертационной работе результаты не противоречат теоретическим положениям, известным из публикаций других авторов. Результаты моделирования подтверждаются результатами апробации и внедрения предложенного в диссертации алгоритма в системе «Умный дом» при участии ООО «ЮНИКОРН».

Апробация результатов. Основные результаты работы обсуждались на XXI Международной научно-технической конференции «Проблемы техники и технологий телекоммуникаций» (ПТиТТ-2019), г. Казань, 2019; Международной

научно-технической конференции «Конференция молодых исследователей России по электротехнике и электронике IEEE (2016, 2017 ElConRus)», г. С-Петербург, 2016, 2017; 20-й Конференции Ассоциации Открытых Инноваций, г. Санкт-Петербург, 2017; на международной конференции SoutheastCon 2017, США, Шарлотта / Конкорд, Северная Каролина, 2017; на всероссийской научно-технической конференции молодых ученых, аспирантов и студентов «Автоматизированные системы управления и информационные технологии», Пермь, 2015 г., в программе «Участник молодежного научно-инновационного конкурса» («УМНИК»), Пермь, 2015 г.; на семинарах кафедры «Автоматика и телемеханика» Пермского национального исследовательского политехнического университета.

Публикации. По материалам диссертации опубликовано 15 печатных работ, из них две - в рецензируемых журналах, рекомендованных ВАК РФ для публикации результатов кандидатских диссертаций, пять - в международных базах цитирования (Scopus и Web of Science), семь - в тезисах и материалах международных и всероссийских конференций. Получено свидетельство на регистрацию программы для ЭВМ по реализации программы моделирования алгоритма маршрутизации Adaptive Rate Full Echo.

Личный вклад автора заключается в выполнении классификации протоколов маршрутизации в беспроводных мобильных самоорганизующихся сетях и используемых в них алгоритмов относительно критериев времени жизни сети, среднего времени доставки пактов в сети и времени автоконфигурации. Автором совместно с научным руководителем предложен метод вычисления значений Q-таблицы, позволяющий учитывать параметр «уровень заряда батареи» устройства в совокупности с параметрами «среднее время доставки пакетов по сети в процессе автоконфигурирования сети и в установившемся режиме» и «время автоконфигурирования сети», учитываемыми известным алгоритмом Q-routing. Автором разработан оригинальный алгоритм маршрутизации Adaptive Rate Full Echo, использующий предложенный метод в процессе маршрутизации, что отображено в списке авторов опубликованных работ. Самостоятельно

автором выполнено построение адекватной оригинальной имитационной модели предложенного алгоритма в среде Anylogic и проведены экспериментальные работы. Кроме того, совместно с ООО «ЮНИКОРН» автором было выполнено внедрение разработанного алгоритма маршрутизации на основе практической реализации в составе системы «Умный дом», в частности, автором были предоставлены исходные коды разработанного алгоритма.

Структура работы. Диссертация состоит из введения, четырех глав, заключения, списка используемой литературы и приложений. Содержит 136 страниц машинописного текста, из которых основной текст составляет 131 страницу, 23 рисунка и 25 таблиц, список литературы из 142 наименований, приложения на 5 страницах.

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

В первой главе диссертационной работы приведена классификация беспроводных самоорганизующихся сетей и определены их основные особенности. Выполнен анализ протоколов маршрутизация для беспроводных мобильных самоорганизующихся сетей (MANET - mobile ad hoc network). В рассмотренных протоколах маршрутизации выделены алгоритмы, реализующие выбор маршрута, и выполнен сравнительный анализ этих алгоритмов, который обосновывает переход к изучению алгоритмов, построенных на машинном обучении с подкреплением, с целью повышения эффективности маршрутизации в сетях указанного вида. Поэтому отдельным направлением рассматривается применение алгоритмов семейства Q-routing, использующих принципы обучения с подкреплением, в частности, Q-обучение (Q-learning).

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

Вторая глава диссертационной работы включает в себя подробное описание базового алгоритма Q-routing и разработку нового алгоритма Adaptive Rate Full Echo, постановку и решение многокритериальной задачи.

Третья глава работы включает в себя постановку задачи имитационного моделирования, обоснование выбора среды моделирования, построение имитационной модели разработанного алгоритма Adaptive Rate Full Echo, процесс верификации разработанной имитационной модели и оценивание результатов, полученных в ходе проведения экспериментов.

Четвертая глава включает в себя результаты апробации предложенных алгоритмов маршрутизации в системе «Умный дом», расположенной в многоквартирном доме, при участии ООО «ЮНИКОРН».

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

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

Глава 1. Протоколы маршрутизации в беспроводных сетях

Перед разработкой оригинальных изделий в любой из областей исследования необходимо обладать наиболее полной картиной о сделанных открытиях в этой области и ведущихся разработках. Поэтому в первой главе диссертационного исследования выполнен обзор перспективных в настоящее время беспроводных сетей, и определены их основные особенности. Представлено определение мобильной сети ad hoc (МАКЕТ - mobile ad hoc network), и описан принцип работы и построения такого вида сетей. Выделены два свойства, присущих сетям данного вида, из-за которых маршрутизация в таких сетях является проблемой. Выполнен анализ протоколов маршрутизации для беспроводных мобильных самоорганизующихся сетей MANET, на основе которого сформулированы достоинства и недостатки алгоритмов, применяемых для определения пути в данных протоколах. Обозначен алгоритм Q-routing, в основе которого лежит машинное обучение, позволяющий компенсировать существующие недостатки. Выполнен обзор алгоритмов, порожденных от базового алгоритма Q-routing, направленных на усовершенствование показателей, получаемых при использовании Q-routing. Проведен анализ алгоритмов семейства Q-routing, на основе которого выполнена развёрнутая постановка цели и задач для достижения сформулированной цели.

1.1 Обзор беспроводных сетей

В настоящее время появляются новые типы сетей, как по топологии, так и по видам обмена информацией между участниками сети. Ранее с точки зрения топологии существовали такие топологии, как кольцевая, древовидная, шинная, звезда и другие [41, 42]. Однако в настоящее время наибольшую популярность приобретает так называемая ячеистая топология - mesh, для которой характерно соединение большого количества узлов на большие расстояния с использованием кластеризации [43-46]. С точки зрения вида обмена одним из первых появился peer to peer (точка-точка) обмен, когда компьютеры соединяли между собой

физически с использованием кабеля. Затем с появлением и распространением новых технологий появились такие виды обмена, как клиент-серверный обмен, многоуровневый клиент-серверный обмен, широковещательный обмен, обмен, построенный на взаимодействии одного клиента с группой клиентов и другие. В настоящее время современные сети всё чаще возвращаются к per to peer обмену, однако, в данном случае не на физическом уровне модели ISO OSI, а, например, на сетевом и прикладном уровнях. Кроме того, в настоящее время наиболее популярными становятся беспроводные технологии, независимые от месторасположения. В результате вышеописанных тенденций начинают формироваться сети, имеющие mesh топологию, беспроводные и тяготеющие к peer to peer обмену, которые являются самыми перспективными и активно развивающимися сетями в настоящее время. Примерами таких сетей можно выделить Wireless HART, 6L0WPAN, LoRa, ZigBee и другие. [47-54].

Одним из частных случаев таких сетей являются беспроводные мобильные сети MANET [55-57]. MANET (Mobile Ad Hoc NET works) сети - радиосети со случайными мобильными абонентами, реализующие полностью децентрализованное управление при отсутствии базовых станций или опорных узлов. Для сетей данного типа характерна быстро меняющаяся топология со случайным соединением узлов. Согласно [7, 58] данная технология сетей изначально была создана в военной области более 20 лет назад, однако развитие современных технологий и потребностей общества дали возможность распространения данной технологии в область общего пользования.

Мобильная сеть ad hoc (MANET) представляет собой сеть, состоящую из произвольного числа произвольно перемещающихся (мобильных) узлов, основной особенностью которой является отсутствие централизованной координации или фиксированной инфраструктуры [55-57]. Каждый узел является не только конечным пользователем системы, но и, при необходимости, выступает в качестве маршрутизатора для пересылки пакетов других узлов. Такие сети позволяют оперативно организовать сетевое взаимодействие между

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

1.2 Обзор существующих алгоритмов маршрутизации в мобильных ad hoc сетях

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

В настоящее время по принципу работы можно выделить три класса протоколов, осуществляющих маршрутизацию в беспроводных мобильных ad hoc сетях: проактивные, реактивные и гибридные [1-29, 59-64].

Проактиеные (табличные) протоколы маршрутизации

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

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

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

К табличным протоколам относятся такие протоколы, как DSDV (Destination Sequenced Distance Vector), OLSR (Optimized Link State Routing), FSR (Fish eye State Routing) [4, 7-11, 25-29].

Реактивные протоколы маршрутизации

Данный тип протоколов - так называемые «протоколы по требованию». Постоянное хранение маршрутной информации не входит в обязанности узлов при использовании в сети реактивных протоколов. Когда узлу поступает запрос на предоставление сообщения определенному конечному пункту, узел активизирует механизм построения маршрута, принцип действия которого заключается в следующем: узел-отправитель с помощью рассылки широковещательных запросов, отправляет запросы на построение маршрута всем своим соседям, которые в свою очередь пересылают их своим соседям. Таким образом, путем повтора вышеописанных действий другими участниками сети выстраивается маршрут до узла-получателя. Соответственно полученный маршрут записывается в таблицах маршрутизации, чтобы в дальнейшем при передаче пакета с данными тому же узлу-получателю можно было не тратить дополнительное время на построение маршрута, а воспользоваться уже имеющейся информацией. Пропускная способность сети, обслуживание которой

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

Примером реактивных протоколов являются такие протоколы, как DSR (Dynamic Source Routing), AODV (Ad-hoc On-demand Distance Vector), TORA (Temporally Ordered Routing Algorithm), DYMO (Dynamic MANET On-demand routing protocol) [1-5, 7, 12-15, 17-29, 59-62].

Гибридные протоколы маршрутизации

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

Список литературы диссертационного исследования кандидат наук Шилова Юлия Александровна, 2020 год

Список литературы

1. Johnson, D. The dynamic source routing protocol for mobile ad hoc networks (DSR) / D . Johnson, D. Maltz, Yu. Hu // Internet Draft. - 2004.

2. Johnson, D. RFC 4738 - the dynamic source routing protocol (dsr) for mobile ad hoc networks for IPv4 / D . Johnson, D. Maltz, Yu. Hu // Internet Draft. - 2007.

3. Perkins, C. Request for comments: 3561 ad hoc on-demand distance vector (aodv) routing / C. Perkins, E. Belding-Royer, S. Das // Internet Engineering Task Force-Network Working Group: Fremont, CA, USA. - 2003. - P. 1-13.

4. Broch, J. A performance comparison of multi-hop wireless ad hoc network routing protocols / J. Broch //MobiCom. - 1998. - Vol. 98. - P. 85-97.

5. Billington, J. On modelling and analysing the dynamic MANET on-demand (DYMO) routing protocol / J. Billington, C. Yuan // Transactions on Petri Nets and Other Models of Concurrency III. - Springer, Berlin, Heidelberg, 2009. - C. 98-126.

6. Haas, Z. A new routing protocol for the reconfigurable wireless networks / Z. Haas // Proceedings of the IEEE International Conference on Universal Personal Communications. - August 2001.

7. Conti, M. Multi-hop ad hoc networks from theory to reality / M. Conti, J. Crowcroft, A. Passarella // Nova Publishers. - 2007. - P. 150.

8. Perkins, Ch. Highly dynamic destination-sequenced distancevector routing (DSDV) for mobile computers / Ch. Perkins, P. Bhagwat // ACM SIGCOMM'94 Conference on Communications Architectures, Protocols and Applications. - 1994. - P. 234-244.

9. Jacquet, P. Optimized link state routing protocol for ad hoc networks / P. Jacquet, P. Muhlethaler // IETF MANET Internet Draft. - 2002. - P. 1-8.

10. Clausen, T. IETF Request for Comments: 3626 / T. Clausen, P. Jacquet // Optimized Link State Routing Protocol OLSR. - 2003.

11. Guangyu, P. Fisheye state routing in mobile Ad Hoc networks / P. Guangyu, G. Mario, C. Tsu-Wei // Proceedings of ICC. - 2000. - №. s 1. - P. 71-78.

12. Карманов, M.JI. Протокол маршрутизации для ad-hoc сетей / M.JI. Карманов // Вестник Южно-Уральского государственного университета. Серия: Компьютерные технологии, управление, радиоэлектроника. - 2009. - №. 26 (159). -с. 47-51.

13. Винокуров, В.М. Маршрутизация в беспроводных мобильных Ad hoc-сетях / В.М. Винокуров, А.В. Пуговкин // Доклады ТУСУРа, № 2 (22), часть 1. -декабрь 2010. - С. 288-292.

14. Павлов, А. А. Протоколы маршрутизации в беспроводных сетях / А. А. Павлов, И.О. Датьев // Труды Кольского научного центра РАН. - 2014. - № 5 (24). - С. 64-75.

15. Махмуд, А. Ш. Оценка производительности протоколов маршрутизации мобильных ad-hoc сетей (MANET) / А. Ш. Махмуд, В. М. Поляков // Научный результат. Информационные технологии. - 2016. - Т. 1. -№. 4. - С. 64-71.

16. Орлов, В. Г. Протоколы маршрутизации в мобильных Ad-Нос-сетях / В. Г.Орлов, А. Н. Фадеев // Фундаментальные проблемы радиоэлектронного приборостроения. - 2012. - Т. 12. - №. 6. - С. 208-212.

17. Johnson, D. В. Dynamic source routing in ad hoc wireless networks / D. B. Johnson, D. A. Maltz // Mobile computing. - Springer, Boston, MA, 1996. - C. 153-181.

18. Perkins Ch. RFC 3561 - Ad-hoc on-demand distance vector (AODV) routing / Ch. Perkins- July 2003.

19. Perkins, С. E. Ad-hoc on-demand distance vector routing / С. E. Perkins, E. M. Royer // Proceedings WMCSA'99. Second IEEE Workshop on Mobile Computing Systems and Applications. - 1999. - P. 90-100.

20. Шувалов, В. П. Классификация методов многопутевой маршрутизации / В. П. Шувалов, И. Ю. Вараксина // Т-Сотт-Телекоммуникации и Транспорт. -2014.-Т. 8. -№. 1.-С. 29-32.

21. Kumar, J. Comparative performance analysis of AODV, DSR, DYMO, OLSR and ZRP routing protocols in MANET using varying pause time / J. Kumar //

International Journal of Computer Communications and Networks (IJCCN). - 2012. -Vol. 3. - No. 1. - P. 43-51.

22. Glabbeek, R. Modelling and verifying the AODV routing protocol / R. Glabbeek // Distributed Computing. - 2016. - T. 29. - №. 4. - P. 279-315.

23. Gupta, S. K. Performance metric comparison of AODV and DSDV routing protocols in MANETs using NS-2 / S. K. Gupta, R. K. Saket // International Journal of Research and Reviews in Applied Sciences. - 2011. - T. 7. - №. 3. - P. 339-350.

24. Yadav, N. S. Performance comparison and analysis of table-driven and on-demand routing protocols for mobile ad-hoc networks / N. S. Yadav, R. P. Yadav // International Journal of Information Technology. - 2007. - T. 4. - №. 2. - P. 101-109.

25. Ehsan, H. Performance comparison of ad hoc wireless network routing protocols / H. Ehsan, Z. A. Uzmi // Multitopic Conference. - IEEE, 2004. - P. 457-465.

26. Akkaya, K. A survey on routing protocols for wireless sensor networks / K. Akkaya, M. Younis //Ad hoc networks. - 2005. - Vol. 3. - No. 3. - P. 325-349.

27. Siraj, M. A survey on routing algorithms and routing metrics for wireless mesh networks / M. Siraj //World Applied Sciences Journal. - 2014. - Vol. 30. - No. 7. -P. 870-886.

28. Russell, B. Learning-based route management in wireless ad hoc networks / B. Russell // ProQuest. - 2008. - P. 19-38.

29. Nayak, P. Impact of random mobility models for reactive routing protocols over MANET / P. Nayak, B. Vathasavai // International Journal of Simulation Systems, Science & Technology. - 2016. - Vol. 17. - No. 34. - P. 112-115.

30. Kumar, S. Confidence based dual reinforcement Q-routing: an on-line adaptive network routing algorithm : dis \ S. Kumar. - University of Texas at Austin, 1998.

31. Чертков, А. А. Автоматизация выбора кратчайших маршрутов судов на основе модифицированного алгоритма Беллмана-Форда / А. А. Чертков // Вестник государственного университета морского и речного флота им. адмирала С.О. Макарова. -2017. - Т. 9, №. 5. - С. 1113-1122.

32. Boyan J. A., Littman M. L. Packet routing in dynamically changing networks: A reinforcement learning approach //Advances in neural information processing systems. - 1994. - P. 671-679.

33. Kaelbling, L. P. Reinforcement learning: A survey / L. P. Kaelbling, M. L. Littman, A. W. Moore // Journal of artificial intelligence research. - 1996. - T. 4. - C. 237-285.

34. Kumar, S. Dual Reinforcement Q-routing: An On-Line Adaptive routing Algorithm / S. Kumar, R. Miikkulainen // In Proceedings of the Artificial Neural Networks in Engineering Conference (St. Louis), 1997. - P. 231-238.

35. Kumar, S. Confidence-based q-routing: An on-line adaptive network routing algorithm / S. Kumar, R. Miikkulainen // Proceedings of Artificial Neural Networks in Engineering. - 1998. - P. 1-6.

36. Desai, R. Analysis of Reinforcement Based Adaptive Routing in MANET / R. Desai, B. P. Patil // Indonesian Journal of Electrical Engineering and Computer Science. - 2016. - T. 2. - №. 3. - C. 684-694.

37. Desai, R. Reinforcement learning for adaptive network routing / R. Desai, B.P. Patil // Computing for Sustainable Global Development, 2014 International Conference on. - IEEE, 2014. - P. 815-818.

38. Choi, S. Predictive Q-routing: A memory-based reinforcement learning approach to adaptive traffic control / S. Choi, D.Y. Yeung // Advances in Neural Information Processing Systems. - 1996. -T. 8. - P. 945-951.

39. Kumar, D. Securing MANETs by Q routing protocol / D. Kumar, D. B. Ojha, A. Kumar // International Journal of Engineering Research and Applications. - 2012. -T. 2. - №. 6. - P. 884-889.

40. Subramanian, D. Ants and reinforcement learning: A case study in routing in dynamic networks / D. Subramanian, P. Druschel, J. Chen // IJCAI (2). - 1997. - P. 832-839.

41. Монахов, M. Ю. Модели обеспечения достоверности и доступности информации в информационно-телекоммуникационных системах: монография /

Ю. М. Монахов, Д. А. Полянский, И. И. Семенова // Владим. гос. ун-т им. А. Г. и Н. Г. Столетовых. - Владимир : Изд-во ВлГУ, 2015. - 208 с.

42. Шварц М. Сети ЭВМ: анализ и проектирование / М. Шварц. - М.: Радио и связь, 1981.-400 с.

43. Вишневский, В. Маршрутизация в широкополосных беспроводных mesh-сетях стандарта IEEE 802.11 s / В. Вишневский, Д. Лаконцев, А. Сафонов, С. Шпилев // Электроника: Наука, технология, бизнес. - 2008. - №. 6. - С. 64-71.

44. Вишневский, В. Mesh-сети. В ожидании стандарта IEEE 802.11 s / В. Вишневский, Д. Лаконцев, А. Сафонов, С. Шпилев // Электроника: Наука, технология, бизнес. - 2008. - №. 3. - С. 98-107.

45. Аблялимова, 3. С., Уразалиева, Д. М. Маршрутизация в mesh сетях на основе хаотических радиоимпульсов // IV Всероссийская конференция «Радиолокация и радиосвязь. - 2010. -№. 4. - С. 457-461.

46. Perkins, С. Е. Ad hoc networking / С. Е. Perkins // Addison-wesley. - 2001. -Т. 1. - P. 363.

47. Chen, D. Why wirelesshart / D. Chen, M. Nixon, A. Mok // WirelessHAR, Springer, Boston, MA. -2010. - P. 195-199.

48. Gungor, V.C. Industrial wireless sensor networks: Challenges, design principles, and technical approaches / V. C. Gungor, G. P. Hancke // IEEE Transactions on industrial electronics. - 2009. - Vol. 56. - No. 10. - P. 4258-4265.

49. Zheng, L. ZigBee wireless sensor network in industrial applications / L. Zheng // 2006 SICE-ICASE International Joint Conference. - 2006. - P. 1067-1070.

50. Lennvall, T. A comparison of WirelessHART and ZigBee for industrial applications / T. Lennvall, S. Svensson, F. Hekland // 2008 IEEE International Workshop on Factory Communication Systems. - 2008. - P. 85-88.

51. Gustafsson, D. Wirelesshart-implementation and evaluation on wireless sensors / D. Gustafsson // Masters's Degree Project, KTH University, Electrical Engineering. -2009. - P. 1-39.

52. Shelby, Z. 6L0WPAN: The wireless embedded Internet / Z. Shelby, C. Bormann // 1st ed. London, U.K.: Wiley. - 2009. - P. 244.

53. Mulligan, G. The 6L0WPAN architecture / G. Mulligan // Proceedings of the 4th workshop on Embedded networked sensors. - 2007. - P. 78-82.

54. Технология LoRa. - [Электрон, ресурс]. URL: http://lo-ra.ru/ (дата обращения 17.08.2018).

55. Basagni, S. Mobile ad hoc networking / S. Basagni // John Wiley & Sons. -2004. - P. 480.

56. Frodigh, M. Wireless ad hoc networking: the art of networking without a network / M. Frodigh, P. Johansson, P. Larsson // Ericsson Review. - 2000. - Vol. 4. -No. 4. - P. 249.

57. Bruzgiene, R. MANET network in internet of things system / R. Bruzgiene // Ad Hoc Networks. - 2017. - P. 89-114.

58. Conti, M. Multihop ad hoc networking: The reality / M. Conti, S. Giordano // IEEE Communications Magazine. - 2007. - Vol. 45. - No. 4. - P. 88-95.

59. Maurya, S. K. Evaluation of LANMAR and DSR ad hoc routing protocol for various battery models in MANET using QualNet / S. K. Maurya, S. Rahul, Y. Rajvanshi // International Journal of Computer Networks and Wireless Communications. - 2012. - T. 2. - №. 6. - C. 709-716.

60. Johnson, D. The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4 / D. Johnson, Y. Hu, D. Maltz // Request for Comments 4728. -February 2007.

61. Казаков, М.Ф. Построение самоорганизующейся сети мобильных устройств / М.Ф. Казаков // Молодежь и наука: сборник материалов X Юбилейной Всероссийской научно-техн. конф. студентов, аспирантов и молодых ученых с международным участием, посвященной 80-летию образования Красноярского края . - Красноярск: Сиб. федер. ун-т. - 2014. - С. 13-17.

62. Pei, G. LANMAR: landmark routing for large scale wireless ad hoc networks with group mobility / G. Pei, M. Gerla, X. Hong // Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing. - IEEE Press, 2000. -C. 11-18.

63. Gupta, S. Performance Comparison of Proactive Routing Protocols: OLSR, DSDV, WRP / S. Gupta, B. S. Dhaliwal, R. Malhotra // International Journal of Advanced Research in Computer Science. - 2015. - Vol. 6. - No. 8. - P. 73-77.

64. Климов, И. А. Сравнение протоколов маршрутизации для беспроводных мобильных AD-НОС сетей / И. А. Климов, Н. В. Червинская // Автоматизация технологических объектов и процессов. Сборник научныхработ XIII научно-технической конференции аспирантов и студентов в г. Донецк 14-17 мая 2013 г. -Донецьк, ДонНТУ, 2013. - С. 76-80.

65. Haraty, R. A. MANET with the Q-Routing Protocol / R. A. Haraty, B. Traboulsi // Proceedings of the 11th International Conference on Networks. - 2012. - P. 187-192.

66. Kitsuwan, N. Performance of throughput-based Q-routing / N. Kitsuwan, T. Neda, E. Oki // IEICE Communications Express. - 2017. - T. 6. - №. 3. - C. 137-141.

67. Shanbhagh, S. R. Reinforcement learning Algorithms in Routing:" Q Routing" implementation and analysis in NS-2 / S. R. Shanbhagh, Y. V. Potdar, M. S. Phatak // Fr. Conceicao Rodrigues College of Engineering. - 2006. - P. 70.

68. Alharbi, A. A Mobile Ad hoc Network Q-Routing Algorithm: Self-Aware Approach / A. Alharbi, A. Al-Dhalaan, M. Al-Rodhaan // International Journal of Computer Applications. -2015. -T. 127. -№. 7. - P. 1-6.

69. Sutton, R. Reinforcement Learning: An Introduction / R. Sutton, A.G. Barto // MIT Press, Cambridge, MA. - 1998. - 328 p.

70. Kudelski, M. Learning methods in ad-hoc networks: a review / M. Kudelski, A. Pacut // Evolutionary Computation and Global Optimization, Prace Naukowe Politechniki Warszawskiej, Elektronika. - 2007. - №. 160. - P. 153-163.

71. Yau, K. L. Reinforcement learning for context awareness and intelligence in wireless networks: Review, new features and open issues / K. L. Yau, P. A. Komisarczuk, P. D. Teal // Journal of Network and Computer Applications. - 2012. - T. 35.-№. l.-P. 253-267.

72. Olsson, R. Reinforcement Learning Routing Algorithm for Bluetooth Mesh Networks / R. Olsson, J. Egeland. - 2018. - P. 67.

73. Caarls, W. Q-caching: an integrated reinforcement-learning approach for caching and routing in information-centric networks / W. Caarls, E. Hargreaves, D. S. Menasche // arXiv preprint arXiv: 1512.08469. - 2015. - P. 1-15.

74. Tao, N. A multi-agent, policy-gradient approach to network routing / Tao N, J. Baxter, L. Weaver // In Proceedings of the 18th Int. Conf. on Machine Learning. -2001.-P. 553-560.

75. Hoceini, S. Average-bandwidth delay Q-routing adaptive algorithm / S. Hoceini, A. Mellouk, B. Smail // 2008 IEEE International Conference on Communications. - IEEE, 2008. - C. 1840-1844.

76. Yap, S. T. An Adaptive Routing Algorithm: Enhanced Confidence-Based Q Routing Algorithm in Network Traffic / S. T. Yap, M. Othman // Malaysian Journal of Computer Science. - 2004. - T. 17. - №. 2. - C. 21-29.

77. Бройдо, В. JI. Вычислительные системы, сети и телекоммуникации: Учебник для вузов. 4-е изд / В. Л. Бройдо, О. П. Ильина. - Издательский дом" Питер", 2010. - С. 560.

78. Вихрова, О. Г. К анализу показателей качества обслуживания в современных беспроводных сетях / О. Г. Вихрова // Информатика и её применения. - 2015. - Т. 9. - №. 4. - С. 48-55.

79. Датьев, И. О. Маршрутные метрики многошаговых беспроводных самоорганизующихся сетей / И. О. Датьев // Труды Кольского научного центра РАН. - 2015. - №. 3 (29). - С. 115-136.

80. Тихвинский, В. О. Параметры качества услуг в сетях WiMAX / В. О. Тихвинский, С. В. Терентьев // Т-Сотт-Телекоммуникации и Транспорт. - 2007. -№. 5-6.-С. 41-47.

81. Туркин, И. Б. Метрики для принятия решения о передаче обслуживания в гетерогенных беспроводных сетях мобильных коммуникационных устройств / И. Б. Туркин, Д. С. Игнатьев // Зб1рник наукових праць Харювського ушверситету Повпряних Сил. - 2015. -№. 3. - С. 64-69.

82. Кирьянов, А. Анализ механизмов построения логической топологии в сетях MANET / А. Кирьянов // Информационные процессы. - 2015. - Т. 15. - №. 2. -С. 183-197.

83. Patel, V. S. Survey on Sensor Protocol for Information via Negotiation (SPIN) protocol / V. S. Patel, C. R. Parekh // IJRET: International Journal of Research in Engineering and Technology. - 2014. - T. 3. - №. 03. - P. 1453-1456.

84. Shin, K.Y. Reliable Energy Aware Routing Protocol (REAR) / K.Y. Shin, J. Song, J. W. Kim // Advanced CommunicationTechnology, The 9th International Conference, 2007. - No. 1. - P. 525-530.

85. Yahya, B. REER: Robust and Energy Efficient Multipath Routing Protocol for Wireless Sensor Networks / B. Yahya, J. Ben-Othman // Global Telecommunications Conference. - 2009. - P. 1-7.

86. Пустохайлова, E. А. Энергоэффективный многопутевой протокол маршрутизации в беспроводной сенсорной сети, основанный на решетке с использованием нечеткого подхода / Е. А. Пустохайлова, В. Д. Семейкин // Вестник Астраханского государственного технического университета. Серия: Управление, вычислительная техника и информатика. - 2016. - №. 4. - С. 65-73.

87. Yadav, М. Power Aware Routing in Ad Hoc Wireless Networks / M. Yadav, S. Verma, S. K. Bajapai // Journal of Computer Science and Technology. - 2009. -Vol. 9. - No. 2. - PP. 101-109.

88. Rajaram, A. Power aware routing for MANET using on-demand multipath routing protocol / A. Rajaram, J. Sugesh // International Journal of Computer Science Issues (IJCSI). -2011. - Vol. 8. - No. 4. - PP. 517-522.

89. 89. Шилова, Ю. А. Исследование влияния параметра скорости обучения на результаты работы алгоритма маршрутизации Q-Routing / Ю. А. Шилова, М. В. Кавалеров // Инновационные технологии теория, инструменты, практика. Сб. трудов международн. конф. - Пермь, ПНИПУ, 2015. - С. 172-179.

90. Шилова Ю. А. Алгоритм маршрутизации семейства Q-routing, основанный на динамическом изменении коэффициентов обучения за счет оценки

средней задержки в сети / Ю. А. Шилова // Вестник Пермского научного центра. -2015. -№ 2. - С. 79-93.

91. Шилова, Ю. А. Разработка алгоритмов маршрутизации семейства Q-ROUTING для мобильных AD НОС сетей / Ю. А. Шилова, М. В. Кавалеров // Автоматизированные системы управления и информационные технологии : материалы всерос. науч.-техн. конф., (г. Пермь, 15 мая 2015 г.). / М-во образования и науки Рос. Федерации, Перм. нац. исслед. политехи, ун-т. - Пермь : Изд-во ПНИПУ. - 2015. - С. 441-446.

92. Shilova, Y. Full Echo Q-Routing with Adaptive Learning Rates: A Reinforcement Learning Approach to Network Routing / Y. Shilova, M. Kavalerov, I. Bezukladnikov // Proceedings of the 2016 IEEE North West Russia Section Young Researchers in Electrical and Electronic Engineering Conference (2016 ElConRusNW) [Electronic resource] : [St. Petersburg], February 2-3, 2016. / St. Petersburg Electrotechn. Univ. LETI, IEEE Russia North-West section. - St. Petersburg : St. Petersburg Electrotechnical Univ. LETI. - 2016. - 1 Electronic optical disc (CD-ROM): p. 365-368.

93. Kavalerov, M. Improving Predictability of Adaptive Q-Routing / M. Kavalerov, S. Rybnikova, Y. Shilova // Work-in-Progress [Electronic resource] : Proc. [29th Euromicro Conference on Real-Time Systems (ECRTS-WiP 2017)], June 28th, 2017, Dubrovnik, Croatia / Ed. P. Meumeu Yomsi Proc. [29th Euromicro Conference on Real-Time Systems (ECRTS-WiP 2017)], June 28th, 2017, Dubrovnik, Croatia. - [S. 1.] : [s. п.]. - 2017. - P. 25-27.

94. Kavalerov, M. V. Preventing instability in full echo Q-routing with adaptive learning rates / M. V. Kavalerov, Y. A. Shilova, I. I. Bezukladnikov // 2017 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus) : Proc. of the 2017 IEEE Russia Section Young Researchers in Electrical and Electronic Engineering Conference (2017 ElConRus), [St. Petersburg, Moscow], Febr. 1-3, 2017. / St. Petersburg Electrotechn. Univ. LETI, National Research Univ. of Electronic Technology MIET. - [S. 1.] : IEEE, 2017. - P. 155-159.

95. Kavalerov, M. Reinforcement learning approach to network routing based on adaptive learning rates and route memory / M. Kavalerov, Y. Likhacheva, Y. A Shilova // SoutheastCon 2017 [Electronic resource] : Conf. Proc., Charlotte, NC, March 30-Apr. 2, 2017 : [annual IEEE Region 3 Technical, Professional and Student Conf.]. / IEEE Region 3, IEEE North Carolina Council. - [S. 1.] : IEEE, 2017. - 6 p.

96. Kavalerov, M. Adaptive Q-Routing with random echo and route memory / M. Kavalerov, Y. A Shilova, Y. Likhacheva //2017 20th Conference of Open Innovations Association (FRUCT) [Electronic resource] : [Proc.], Saint Petersburg, Russia, 3-7 April 2017. / FRUCT Oy, EwerestMD LLC, St. Petersburg Electrotechn. Univ. LETI, Dell EMC Research Center, Russia, IEEE Russia North-West section, Technopark of ITMO University, Chair of Secure Information Technologies of ITMO University. -[Helsinki] : FRUCT Oy. - 2017. - P. 138-145.

97. Дмитриев, M. Г. Оценка чувствительности линейной свертки частных критериев при экспертном определении весовых коэффициентов / М. Г. Дмитриев, В. А. Ломазов // Искусственный интеллект и принятие решений. -2014. -№. 1. - С. 52-56.

98. Ногин, В. Д. Линейная свертка критериев в многокритериальной оптимизации / В. Д. Ногин // Искусственный интеллект и принятие решений. -2014.-№. 4.-С. 73-82.

99. Лотов, А. В. Конспект лекций по теории и методам многокритериальной оптимизации / А. В. Лотов, И. И. Поспелова. - М.: МГУ, 2014. - 127 с.

100. Кравцов, М. К. Линейная свертка критериев в бикритериальной оптимизации / М. К. Кравцов, О. А. Янушкевич // Известия высших учебных заведений. Математика. - 1998. -№. 12. - С. 63-70.

101. Ногин, В. Д. Принятие решений в многокритериальной среде. Количественный подход / В. Д. Ногин. - М. : Физматлит, 2002. - С. 144.

102. Плющенков, Б. Д. Пошаговая св ёртка / Б. Д. Плющенков, В. И. Турчанинов // Препринты Института прикладной математики им. MB Келдыша РАН. - 2009. - №. 0. - С. 1-24.

103. Banks, J. Discrete-Event System Simulation / J. Banks, J.S. Carson II, B.L. Nelson, D.M. Nicol // Prentice Hall, fourth edition. - 2005. - P. 639.

104. Law, A.M. Simulation Modeling and Analysis / A.M. Law // McGrawHill, fourth edition. - 2007. - 155 P.

105. Wehrle, K. Modeling and tools for network simulation / K. Wehrle, M. Gunes, J. Gross // Springer Science & Business Media. - 2010. - 566 P.

106. Даденков, С.А. Разработка алгоритмов проектирования подсистем сбора и передачи информации автоматизированных систем управления технологическими процессами с требуемыми временными характеристиками [Текст]: дис. / С.А. Даденков. - Пермский национальный исследовательский политехнический университет, Пермь. - 2016. - 200 с.

107. Алиев, Т. И. Основы моделирования дискретных систем / Т. И. Алиев // СПб: СПбГУ ИТМО. - 2009. - С. 363.

108. Darmont, J. Desp-cpp: a discrete-event simulation package for cpp / J. Darmont // Software:Practice and Experience. □ 2000. □ P. 37-60.

109. Cooper, J. W. Design Pattarn Java Companion / J. W. Cooper // Addison Wesley, 2017.-P. 801.

110. Verhoef, C. Discrete event simulation in Java with the use of frameworks / C. Verhoef. -2017. - P. 57.

111. Шрайбер, Т. Дж. Моделирование на GPSS / Т. Дж. Шрайбер; пер. с англ.; под ред. М.А. Файнберга. -М.: Машиностроение, 1980. - С. 592.

112. Девятков, В.В. Методология и технология имитационных исследований сложных систем: современное состояние и перспективы развития / В. В. Девятков. - М.: Вузовский учебник: ИНФРА-М, 2013. - С. 448.

113. Campbell, D. A MATLAB simulation of' shoebox" room acoustics for use in research and teaching / D. Campbell, K. Palomaki, G. Brown //Computing and Information Systems. - 2005. - T. 9. - №. 3. - C. 48.

114. Liu, J. Radial Basis Function (RBF) neural network control for mechanical systems: design, analysis and Matlab simulation / J. Liu // Springer Science & Business Media. -2013. - P. 365.

115. Zimmerman, R. D. MATPOWER: A MATLAB power system simulation package / R. D. Zimmerman, С. E. Murillo-Sánchez, D. Gan // Manual, Power Systems Engineering Research Center, Ithaca NY. - 1997. - Vol. 1. - P. 1-10.

116. Kelton, W. D. Simulation with ARENA / W. D. Kelton. - McGraw-hill, 2002. - P. 656.

117. Altiok, T. Simulation modeling and analysis with Arena / T. Altiok, B. Melamed. - Elsevier, 2010. - P. 456.

118. Borshchev, A. Distributed simulation of hybrid systems with AnyLogic and HLA / A. Borshchev, Y. Karpov, V. Kharitonov // Future Generation Computer Systems. - 2002. - T. 18. - №. 6. - C. 829-839.

119. Garifullin, M. Using AnyLogic and agent-based approach to model consumer market / M. Garifullin, A. Borshchev, T. Popkov // Proceedings of the 6th EUROSIM Congress on Modelling and Simulation. - 2007. - C. 1-5.

120. Якимов, И. M. Моделирование сложных систем в имитационной среде AnyLogic / И. М. Якимов, А. П. Кирпичников, В. В. Мокшин // Вестник Казанского технологического университета. - 2014. - Т. 17. - №. 13. - С. 352-357.

121. Мезенцев, К. Н. Практикум «Моделирование систем в среде AnyLogic 6.4. 1» Часть 1 / К. Н. Мезенцев // Московский Автомобильно-Дорожный Государственный Технический Университет (МАДИ). - 2011. - С. 109.

122. Chan, W. К. V. Agent-based simulation tutorial-simulation of emergent behavior and differences between agent-based simulation and discrete-event simulation / W. К. V. Chan, Y. J. Son, С. M. Macal // Proceedings of the 2010 Winter Simulation Conference. - IEEE, 2010. - C. 135-150.

123. Области применения системы имитационного моделирования AnyLogic [Электрон, ресурс]. - Режим доступа: http://www.anylogic.ru/application-areas (дата обращения: 28.09.2016).

124. Алексеев, С. И. Среда имитационного моделирования anylogic-эффективное средство повышения качества высшего образования / С. И. Алексеев, Р. И. Сорока // Сборник научных статей. Книга З/Труды Всероссийской научно-практической конференции с международным участием

«Информационные технологии в обеспечении нового качества высшего образования (14-15 апреля 2010 г., Москва, НИТУ «МИСиС»)». - М.: Исследовательский центр проблем качества подготовки специалистов. - 2010. -С. 138-142.

125. David, N. Opnet based simulation for rural educational ICT connectivity / N. David, C. Anyakoha, H. Agbo // International Journal of Scientific & Engineering Research. - 2016. - Vol. 7. - №. 4. - P. 1499-1504.

126. Lu, Z. Unlocking the power of OPNET modeler / Z. Lu, H. Yang. -Cambridge University Press, 2012. - P. 253.

127. Sethi, A. S. The practical OPNET user guide for computer network simulation / A. S. Sethi, V. Y. Hnatyshin. - Chapman and Hall CRC, 2012. - P. 527.

128. Jonsson, A. Modeling, implementation and evaluation of IEEE 802.11 ac in NS-3 for enterprise networks / A. Jonsson //2016 Wireless Days (WD). - IEEE, 2016. -P. 1-6.

129. ns-3 Tutorial. - [Электрон. ресурс]. URL: https://www.nsnam.0rg/d0cs/release/3.18/tutorial/ns-3-tutorial.pdf (дата обращения 01.08.2016).

130. Lattimore, Т. Asymptotically optimal agents / T. Lattimore, M. Hutter // Algorithmic Learning Theory. - Springer, 2011. - P. 368-382.

131. Муршед, Ф. А. Имитационная модель многоканальной системы массового обслуживания с равномерным законом обслуживания / Ф. А. Муршед, Н. К. Нуриев // Вестник Казанского технологического университета. - 2017. - Т. 20. - №. 8. - С. 90-94.

132. Шилова, Ю. А. Моделирование базового протокола Q-Routing в среде Anylogic / Ю. А. Шилова, Е. JI. Кон // Проблемы техники и технологий телекоммуникаций (ПТиТТ-2016) [Электронный ресурс] : [тезисы] XVII Междунар. науч.-техн. конф., Самара, 22-24 нояб. 2016 г. / Поволж. гос. ун-т телекоммуникации и информатики, Казан, нац. исслед. техн. ун-т им. А. Н. Туполева - КАИ, Уфим. гос. авиац. техн. ун-т. - Самара : [б. и.], 2016. - С. 131-132.

133. Shilova, Y. A. Q-routing algorithm simulation in Anylogic // Инновационные процессы в исследовательской и образовательной деятельности = Innovations in Research and Education Activities : материалы VI регион, науч.-практ. конф. молодых ученых, (г. Пермь, 24 февр. 2017 г.) / Перм. нац. исслед. политехи, ун-т. - Пермь : Изд-во ПНИПУ, 2017. - С. 57-62.

134. Шилова, Ю.А. Влияние коэффициента «скорость распространения эхо» на эффекивность маршрутизации алгоритма Adaptive Rate Full Echo / Ю.А. Шилова, А.А. Южаков, И.И. Безукладников, М.В. Кавалеров // Вестник ИжГТУ, г. Ижевск. -2019. - С. 48-59.

135. Pacut, A. Ant-routing vs q-routing in telecommunication networks / A. Pacut, M. Gadomska, A. Igielski // Proceedings of the 20-th ECMS Conference. -2006. - P. 67-72.

136. Shilova, Y. A. Influence of the battery life parameter on the Q-routing algorithm results / Y. A. Shilova, I. I. Bezukladnikov // 2017 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus): Proc. of the 2017 IEEE Russia Section Young Researchers in Electrical and Electronic Engineering Conference (2017 ElConRus), [St. Petersburg, Moscow], Febr. 1-3, 2017. / St. Petersburg Electrotechn. Univ. LETI, National Research Univ. of Electronic Technology MIET. - [S. 1.] : IEEE, 2017. - P. 213-217.

137. Находки программиста. - [Электрон. ресурс]. URL: http://findevelop.blogspot.eom/2013/l 1/udp-android.html (дата обращения 11.07.2017).

138. Шилова, Ю.А. Верификация имитационной модели алгоритма маршрутизации Adaptive Rate Full Echo, разработанной в среде имитационного моделирования Anylogic / Ю.А. Шилова // Моделирование, оптимизация и информационные технологии, г. Воронеж. - 2019. - С. 1-11.

139. Бондарик, В. Н. Прогнозирование развития Интернета Вещей на горизонте планирования до 2030 года / В. Н. Бондарик, А. Е. Кучерявый // Труды Московского физико-технического института. - 2013. - Т. 5. - №. 3 (19). - С. 92-96.

140. Li, M. Smart Home: Architecture, Technologies and Systems / M. Li, W. Gu, W. Chen, Y. He, Y. Wu, Y. Zhang // Procedia computer science. - 2018. - Vol. 131. - P. 393-400.

141. Шилова, Ю.А., Южаков, A.A., Безукладников, И.И. Апробация результатов алгоритма Adaptive Rate Full Echo в системе «Умный дом» ООО «Сапфир» / Ю.А. Шилова, A.A. Южаков, И.И. Безукладников // Проблемы техники и технологий телекоммуникаций (ПТиТТ-2019) [Электронный ресурс] : [тезисы] XXI Междунар. науч.-техн. конф., Казань, 18-22 нояб. 2019 г. / Поволж. гос. ун-т телекоммуникации и информатики, Казан, нац. исслед. техн. ун-т им. А. Н. Туполева - КАИ, Уфим. гос. авиац. техн. ун-т. - Казань : [б. и.], 2019. - С. 217-218.

142. Шилова, Ю.А., Южаков, A.A., Безукладников, И.И. Анализ протоколов маршрутизация для беспроводных мобильных самоорганизующихся сетей / Ю.А. Шилова, A.A. Южаков, И.И. Безукладников // Проблемы техники и технологий телекоммуникаций (ПТиТТ-2019) [Электронный ресурс] : [тезисы] XXI Междунар. науч.-техн. конф., Казань, 18-22 нояб. 2019 г. / Поволж. гос. ун-т телекоммуникации и информатики, Казан, нац. исслед. техн. ун-т им. А. Н. Туполева - КАИ, Уфим. гос. авиац. техн. ун-т. - Казань : [б. и.], 2019. - С. 219-220.

Приложение А

Графическая визуализация модели

MyNetwork: Simulation - AnyLogic Professional 1 = | В ifc^-]

вНвН| ► T M ■ | {?„ xl П^НЧ" I sSk I М0% I Qt [□] I Cr « . эксперимент: MyNetwork: Simulat... ж %

MyNetwork

| Поехали | @ Статика О Динамика

101 Установить

Прогон: О О Готов Время: - Шаг: - | [> событий/с 0 кадров/с: 0.0 | Память: \г |jj | 0,0 се

Рисунок А. 1 - Форма инициации модели

Рисунок А.2 - Статическая структура сети

] Структура сообщения с управляющей информацией

Ю пакета Ю источника Юприемника

Длина пакета Ю передающего узла СЗ-значение передающего узла

Рисунок А.4 - Структура сообщения с управляющей информацией

] Структура сообщения с данными

Ю пакета Ю источника Ю приемника

Длина пакета Ю передающего узла Означение передающего узла

Данные

Рисунок А. 5 — Структура сообщения с данными

| Посмотеть р-таблицы

0 I 1 2 3 4 5

6 7 8 9 10 11

12 13 И 15 16 17

1В 19 20 21 22 23

24 25 26 27 2В 29

30 31 -32 33 34 35

Рисунок А. 6 - Форма представления О-таблиц

Ш QTaЫe of nc.de 14

(н)

8 13 15 20 А-

0 0Г000 0,172 0,000 0,000 и

1 0,000 2,875 0,000 0,000

2 0Г000 0,000 -7,424 0,000

3 0Г000 -13,302 0,000 -11,900

4 0Г155 0,000 0,000 0,000

5 0Г000 0,000 0,000 -1,794

6 0Г000 0,000 0,151 0,000

7 0,000 0,000 0,000 0,000 --

Рисунок А. 7 - С)-таблица одного из узлов сети

Приложение Б

Свидетельство о регистрации программы для ЭВМ

шмтШжш фвдшращшш

Й Й Й Ж й Й

й

й й Й й й

й й Й

й й Й Й Й Й Й Й Й

Й

Й Й й Й Й Й 'й Й Й Й Й Й Й

СВИДЕТЕЛЬСТВО

о государственной регистрации программы для ЭВМ

№ 2017661169

«Программа моделирования алгоритма маршрутизации Adaptive Rate Full Echo»

Правообладатель: Шилова Юлия Александровна (RU)

Автор: Шилова Юлия Александровна (RU)

Заявка № 2017615716

Дата поступления 15 ИЮНЯ 2017 Г.

Дата государственной регистрации

в Реестре программ для ЭВМ 05 Октября 201 7 г.

Руководитель Федеральной службы по интеллектуальной собственности

Г.П. Ивлиев

$£>ЙЙЙЙЙЙЙЙЙЙЙЙЙЙЙЙЙЙЙЙЙЙЙЙЙЙЙЙЙЙЙЙ§$

Й Й Й Й й Й Й Й

Й Й Й

Й Й Й Й Й Й Й Й Й Й Й

Й Й Й Й

Приложение В

Акт внедрения диссертационного исследования

UUU »rvnriKUrn*

U|in

«ENSE

OF TECHNOLOGY

Адрес: 121205. г. Москва. Большой бульвар, 42, стр. 1 оф. 167 Твл: в 800 775 05 1» Сайт: ujln.tach

Электронная почта: InfoQujln.tach

•i/

У УТВЕРЖДАЮ / Директор «KJHHKOPH»» г. Пермь ,—jC.C. Перминова kfldt_ 20/í?г.

Акт

о внедрении результатов кандидатской диссертационной работы Шиловой Юлии Александровны

Комиссия в составе председателя: Перминовой С.С Членов комиссии:

Игошева Д.С. Шаякбарова Н.Ф.

Составила настоящий акт в том. что результаты диссертационной работы «Управление информационными потоками в ad hoc сетях на основе адаптивного алгоритма Q-routing»

использовались в рамках разработки системы «умный дом» общества с ограниченной ответственностью «ЮНИКОРН».

При проектировании системы «умный дом» ООО «ЮНИКОРН». были использованы и внедрены следующие результаты диссертационной работы:

1. Процесс передачи информации в одной из подсетей сетевой инфраструктуры системы «Умный дом» выполняется с использованием разработанного Шиловой Ю.А. адаптивного алгоритма Adaptive Rate Full Echo, особенностями которого являются учет параметра «уровень заряда батареи», разделение коэффициентов обучения и их динамическое изменение в зависимости от глобальной и текущей оценок состояния сети. Использование предложенного алгоритма, встроенного в датчики, снимающие и передающие показания в квартирах системы, позволило увеличить время жизни сети, уменьшить время автоконфигурации сети и среднее время доставки пакетов по сети.

2. Кроме того, для увеличения времени жизни сети разработанный алгоритм использует предложенный Шиловой Ю.А. метод вычисления значений Q-таблицы, относительно которых определяется выбор маршрута, позволяющий учитывать дополнительный параметр «уровень заряда батареи.

3. В процессе проектирования инфраструктуры использовалась разработанная Шиловой Ю.А. оригинальная имитационная модель алгоритмов Q-routing и Adaptive Rate Full Echo, позволившая выполнить совместную оценку времени жизни сети, среднего времени доставки и длительности процесса автоконфигурирования сети, а также сократить время проектированя инфраструктуры системы «Умный дом».

4. Использование указанных результатов позволило спроектировать систему «Умный дом» отвечающую вероятностно-временным характеристикам сбора и передачи информации, что обеспечило необходимое качество функционирования системы сбора и управления параметрами жилых помещений требуемого качества и количества. При этом применение указанных результатов диссертационной работы позволило решить существующую проблему низкой эффективности датчиков, работающих на батарейках при увеличении пропускной способности передаваемого трафика и обеспечить: 1) увеличение времени жизни сети на 50%; 2) снижение среднего времени доставки в процессе автоконфигурирования сети на 53,9%, в установившемся режиме - на 30,9%, уменьшение длительности автоконфигурирования сети на 26%.