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

brief description

Леонов Алексей Викторович. Разработка адаптивного алгоритма маршрутизации на основе роевого интеллекта пчелиной колонии для самоорганизующихся сетей беспилотных летательных аппаратов;[Место защиты: ФГБОУ ВО «Сибирский государственный университет телекоммуникаций и информатики»], 2021

Леонов Алексей Викторович
РАЗРАБОТКА АДАПТИВНОГО АЛГОРИТМА МАРШРУТИЗАЦИИ
НА ОСНОВЕ РОЕВОГО ИНТЕЛЛЕКТА ПЧЕЛИНОЙ КОЛОНИИ
ДЛЯ САМООРГАНИЗУЮЩИХСЯ СЕТЕЙ
БЕСПИЛОТНЫХ ЛЕТАТЕЛЬНЫХ АППАРАТОВ
Специальность 05.12.13 - Системы, сети и устройства телекоммуникаций
Диссертация
на соискание ученой степени
кандидата технических наук
Научный руководитель
доктор технических наук, профессор
Майстренко Василий Андреевич
Омск - 2020
Оглавление
Введение 6
Глава 1 Анализ состояния и перспективы развития самоорганизующихся сетей беспилотных летательных аппаратов 19
1.1 Беспилотные летательные аппараты общего пользования 19
1.1.1 Терминология беспилотных летательных аппаратов 19
1.1.2 Классификация беспилотных летательных аппаратов 20
1.1.3 Миниатюризация беспилотных летательных аппаратов 22
1.2 Самоорганизующиеся сети беспилотных летательных аппаратов 24
1.2.1 Сеть беспилотных летательных аппаратов 24
1.2.2 Динамическая маршрутизация в самоорганизующихся сетях беспилотных
летательных аппаратов 28
1.2.3 Классификация протоколов маршрутизации в сетях беспилотных
летательных аппаратов 30
1.2.4 Выбор протоколов маршрутизации для сравнительного анализа 31
Выводы по главе 1 36
Глава 2 Разработка алгоритма маршрутизации на основе пчелиной колонии для самоорганизующихся сетей беспилотных летательных аппаратов 37
2.1 Поведение медоносной пчелы в природе 37
2.2 Оптимизационные алгоритмы пчелиной колонии 40
2.2.1 Эвристика и роевой интеллект 40
2.2.2 Общие принципы алгоритма пчелиной колонии 42
2.3 Протоколы маршрутизации для самоорганизующихся сетей на основе алгоритма пчелиной колонии
2.3.1 Аналогия между методами роевого интеллекта и маршрутизацией в
самоорганизующихся сетях 43
2.3.2 Протоколы маршрутизации для самоорганизующихся сетей на основе
алгоритма пчелиной колонии 46
2.4 Алгоритм маршрутизации на основе пчелиной колонии 47
для самоорганизующихся сетей беспилотных летательных аппаратов 47
2.4.1 Спецификация алгоритма 48
2.4.2 Модель агента пчелы 49
2.4.3 Структура алгоритма 53
2.4.4 Метрики маршрутизации 56
2.4.5 Формат пакетов 61
2.4.6 Установление маршрутов и передача данных 64
2.5 Программная реализация разработанного алгоритма 65
2.5.1 Среда имитационного моделирования NS-2 66
2.5.2 Архитектура NS-2 67
2.5.3 Описание программной реализации 69
2.5.4 Исследование и выбор значений настроечных параметров 70
Выводы по главе 2 73
Глава 3 Имитационное моделирование самоорганизующихся сетей БПЛА 75
3.1 Разработка имитационных моделей типовых сценариев применения
самоорганизующихся сетей БПЛА 75
3.1.1 Генератор сценариев BonnMotion 76
3.1.2 Сценарии применения самоорганизующихся сетей БПЛА 76
3.1.3 Принятые допущения и ограничения
3.1.4 Модели мобильности для типовых сценариев применения 79
3.1.5 Модель распространения радиосигнала 84
3.1.6 Модель беспроводного модуля 85
3.1.7 Модель генератора трафика 86
3.2 Разработка методики оценки эффективности протоколов маршрутизации 87
3.2.1 Показатели производительности и потоковая передача данных 88
3.2.2 Выбор показателей эффективности протоколов маршрутизации 90
3.4 Программа анализа результатов эксперимента для среды имитационного моделирования NS-2 95
Выводы по главе 3 96
Глава 4 Экспериментальное исследование разработанного алгоритма и оценка эффективности использования в самоорганизующихся сетях БПЛА 98
4.1 Оценка эффективности работы метрик маршрутизации 99
4.2 Оценка эффективности разработанного алгоритма маршрутизации 102
4.2.1 Коэффициент доставки пакетов 102
4.2.2 Пропускная способность 105
4.2.3 Сквозная задержка 107
4.2.4 Джиттер 109
4.2.5 Нормализованная нагрузка на маршрутизацию 110
4.2.6 Накладные расходы на маршрутизацию 111
4.2.7 Количество переходов 113
Выводы по главе 4 115
Заключение 117
Список литературы 
Приложение А. Анализ состояния и перспективы развития самоорганизующихся
сетей БПЛА 147
Приложение Б. Схема работы алгоритма маршрутизации 153
Приложение B. Схема работы программы анализа результатов эксперимента в симуляторе NS-2 163
Приложение Г. Результаты имитационного моделирования метрик маршрутизации 164
Приложение Д. Результаты имитационного моделирования 172
Приложение Е. Акты внедрения 180
Приложение Ж. Свидетельства о регистрации программ для ЭВМ 185

bibliography

Заключение
Основные результаты и выводы, полученные в ходе проведения диссертационного исследования, заключаются в следующем:
1. Проведен анализ текущего состояния научных исследований самоорганизующихся сетей БПЛА, приведена терминология в области БПЛА, рассмотрены различные подходы к классификации и систематизации БПЛА. Показано, что наиболее популярным и перспективным является класс мини-БПЛА, особенно квадрокоптеры, работающие на электрической силовой установке. Отмечено, что сеть на основе БПЛА является перспективной телекоммуникационной системой связи, подходящей для использования в гражданских, коммерческих целях. При этом, наиболее предпочтительным и перспективным решением для организации сетей на основе БПЛА является использование децентрализованной самоорганизующейся сетевой топологии, получившей название Flying Ad Hoc Network (FANET). Выделены общие и частные (специальные) особенности самоорганизующихся сетей БПЛА. Показано, что разработка новых и адаптация существующих алгоритмов, удовлетворяющих требованиям и учитывающим особенности FANET, является актуальным направлением научных исследований. Представлена классификация методов маршрутизации для самоорганизующихся сетей БПЛА, а также рассмотрены протоколы маршрутизации OLSR и AODV являющиеся наиболее популярными и широко использующимися среди исследователей.
2. Показано, что алгоритмы маршрутизации на основе принципов роевого интеллекта, обладают ключевыми для самоорганизующихся сетей свойствами. Представлено обоснование превосходства алгоритмов на основе роевого интеллекта над большинством детерминированных классических алгоритмов маршрутизации. Исследованы существующие алгоритмы роевого интеллекта на основе пчелиной колонии, изучены их особенности и модификации разработанные для эффективного решения задачи маршрутизации в различных типах самоорганизующихся сетей.
3. Разработан новый адаптивный алгоритм маршрутизации на основе роевого интеллекта пчелиной колонии, с использованием алгоритма поиска по «расширяющемуся кольцу» для самоорганизующейся сети БПЛА. Алгоритм относится к реактивным методам многопутевой маршрутизации от источника. Предложенный алгоритм позволяет учитывать требования и особенности самоорганизующихся сетей БПЛА.
Для обеспечения оптимальной маршрутизации потоков данных, в предложенном алгоритме применяется многокритериальный подход, обеспечивающий поддержку нескольких метрик маршрутизации. Создана программная реализация предложенного алгоритма для среды имитационного моделирования с возможностью использования в учебном процессе. Исследовано влияние настроечных параметров на поведение алгоритма, определен диапазон возможных значений и значений по умолчанию.
4. Разработаны реалистичные имитационные модели типовых сценариев применения для самоорганизующихся сетей БПЛА. Для каждого сценария определены численные характеристики и параметры, проведено их обоснование. Сформулированы допущения и ограничения, используемые при разработке имитационных моделей.
5. Разработана методика оценки методов маршрутизации в самоорганизующихся сетях БПЛА позволяющая получить комплексную, разностороннюю оценку эффективности протокола маршрутизации.
6. Разработана программа для автоматизации процесса проведения имитационного моделирования и анализа полученных результатов с возможностью применения в учебном процессе, позволяющая получить числовые значения показателей, использующихся в предложенной автором методике.
7. Проведено исследование по определению лучшего критерия оптимальности (метрики) для разработанного алгоритма в каждом сценарии применения.
8. Проведен сравнительный анализ, результаты которого подтвердили эффективность предложенного алгоритма, его превосходство над популярными протоколами маршрутизации AODV и OLSR по многим показателям, в зависимости от используемого сценария применения самоорганизующейся сети БПЛА:
- коэффициент доставки пакетов увеличился на 2-11%;
- средняя пропускная способность возросла на 3-12%;
- нормализованная нагрузка на маршрутизацию снизилась на 22-82%;
- накладные расходы на маршрутизацию сократились на 33-79%.
В отношении показателей сквозной задержки и джиттера предложенный алгоритм уступает протоколу OLSR и превосходит AODV.
Сделан вывод о том, предложенный алгоритм может рассматриваться в качестве универсального решения задачи маршрутизации в самоорганизующихся сетях БПЛА. Разработанный адаптивный алгоритм маршрутизации позволяет эффективно управлять потоками данных и сетевыми ресурсами, расширяет возможности использования в различных отраслях народного хозяйства и сценариях использования. Полученные результаты могут быть использованы прикладными специалистами для проектирования и разработке самоорганизующихся сетей беспилотных летательных аппаратов (БПЛА). Кроме того, указанные результаты позволяют сократить затраты на проведение натурных испытаний. Разработанные имитационные модели, программная реализация алгоритма, методика оценки эффективности методов маршрутизации, а также программа автоматизации процесса проведения имитационного моделирования и анализа полученных результатов успешно используются в учебном процессе.
Таким образом, цель диссертационного исследования достигнута, поставленные задачи решены в полном объеме.
Дальнейшим направлением исследований является решение задачи разработки метода оптимизации настроечных параметров предложенного алгоритма маршрутизации для выбранного сценария применения самоорганизующейся сети БПЛА. Основными проблемами, возникающими при разработке метода, являются многокритериальность (задача многокритериальной оптимизации) и большое пространство поиска. Поэтому, необходимо разработать метод позволяющий определить значения настроечных параметров разработанного алгоритма за приемлемое время. Также, для оценки эффективности использования предложенного алгоритма в реальной сети, будет выполнена имплементация в операционную систему на базе ядра Linux