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

• Леонов Алексей Викторович
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Леонов Алексей Викторович

Введение

Глава 1 Анализ состояния и перспективы развития самоорганизующихся сетей беспилотных летательных аппаратов

1.1 Беспилотные летательные аппараты общего пользования

1.1.1 Терминология беспилотных летательных аппаратов

1.1.2 Классификация беспилотных летательных аппаратов

1.1.3 Миниатюризация беспилотных летательных аппаратов

1.2 Самоорганизующиеся сети беспилотных летательных аппаратов

1.2.1 Сеть беспилотных летательных аппаратов

1.2.2 Динамическая маршрутизация в самоорганизующихся сетях беспилотных летательных аппаратов

1.2.3 Классификация протоколов маршрутизации в сетях беспилотных летательных аппаратов

1.2.4 Выбор протоколов маршрутизации для сравнительного анализа

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

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

2.1 Поведение медоносной пчелы в природе

2.2 Оптимизационные алгоритмы пчелиной колонии

2.2.1 Эвристика и роевой интеллект

2.2.2 Общие принципы алгоритма пчелиной колонии

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

2.3.1 Аналогия между методами роевого интеллекта и маршрутизацией в самоорганизующихся сетях

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

2.4 Алгоритм маршрутизации на основе пчелиной колонии

для самоорганизующихся сетей беспилотных летательных аппаратов

2.4.1 Спецификация алгоритма

2.4.2 Модель агента пчелы

2.4.3 Структура алгоритма

2.4.4 Метрики маршрутизации

2.4.5 Формат пакетов

2.4.6 Установление маршрутов и передача данных

2.5 Программная реализация разработанного алгоритма

2.5.1 Среда имитационного моделирования №-2

2.5.2 Архитектура №-2

2.5.3 Описание программной реализации

2.5.4 Исследование и выбор значений настроечных параметров

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

Глава 3 Имитационное моделирование самоорганизующихся сетей БПЛА

3.1 Разработка имитационных моделей типовых сценариев применения самоорганизующихся сетей БПЛА

3.1.1 Генератор сценариев BonnMotion

3.1.2 Сценарии применения самоорганизующихся сетей БПЛА

3.1.3 Принятые допущения и ограничения

3.1.4 Модели мобильности для типовых сценариев применения

3.1.5 Модель распространения радиосигнала

3.1.6 Модель беспроводного модуля

3.1.7 Модель генератора трафика

3.2 Разработка методики оценки эффективности протоколов маршрутизации

3.2.1 Показатели производительности и потоковая передача данных

3.2.2 Выбор показателей эффективности протоколов маршрутизации

3.4 Программа анализа результатов эксперимента для среды имитационного моделирования №-2

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

Глава 4 Экспериментальное исследование разработанного алгоритма и оценка эффективности использования в самоорганизующихся сетях БПЛА

4.1 Оценка эффективности работы метрик маршрутизации

4.2 Оценка эффективности разработанного алгоритма маршрутизации

4.2.1 Коэффициент доставки пакетов

4.2.2 Пропускная способность

4.2.3 Сквозная задержка

4.2.4 Джиттер

4.2.5 Нормализованная нагрузка на маршрутизацию

4.2.6 Накладные расходы на маршрутизацию

4.2.7 Количество переходов

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

Заключение

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

Приложение А. Анализ состояния и перспективы развития самоорганизующихся сетей БПЛА

Приложение Б. Схема работы алгоритма маршрутизации

Приложение B. Схема работы программы анализа результатов эксперимента в симуляторе №-2

Приложение Г. Результаты имитационного моделирования метрик маршрутизации

Приложение Д. Результаты имитационного моделирования

Приложение Е. Акты внедрения

Приложение Ж. Свидетельства о регистрации программ для ЭВМ

Введение

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

Актуальность темы исследования

Высокие темпы распространения беспилотных летательных аппаратов (БПЛА) наряду с динамичным развитием технологий беспроводной связи способствовало появлению сети связи нового типа - самоорганизующейся сети БПЛА (англ. Flying Ad Hoc Network, FANET).

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

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

Сети БПЛА привлекают внимание исследователей и специалистов в качестве универсального инструмента, позволяющего решить широкий круг задач, связанных с обследованием территорий, видеонаблюдением, мониторингом объектов инфраструктуры и организацией беспроводного широкополосного доступа (БШПД). Сети БПЛА - это еще один шаг в направлении создания экономически эффективных самоорганизующихся сетей с широким спектром применения.

Основными отличительными особенностями самоорганизующихся сетей БПЛА являются высокий уровень мобильности, частые изменения топологии и большие расстояния между узлами, в сравнении с сетями на основе мобильных устройств (англ. Mobile Ad Hoc Network, MANET) и транспортных средств (англ. Vehicular Ad Hoc Network, VANET).

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

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

На сегодняшний день не существует универсального протокола, учитывающего все особенности самоорганизующейся сети БПЛА. Исследователи работают над поиском новых решений задачи управления информационными потоками данных в FANET. За последние годы была проделана большая работа по внедрению методов роевого интеллекта (РИ) и созданию протоколов адаптивной маршрутизации для самоорганизующихся сетей. Традиционным, централизованным подходам не хватает масштабируемости и отказоустойчивости, методы РИ предоставляют естественные решения посредством распределенных подходов к адаптивной маршрутизации для самоорганизующихся сетей. Кроме того, межуровневый дизайн (англ. cross layer desing, CLD), многообещающий метод, используемый для обеспечения качества обслуживания (англ. Quality of Service, QoS), мало исследовался при разработке протоколов маршрутизации на основе роевого интеллекта с целью повышения эффективности самоорганизующихся сетей.

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

Степень разработанности темы

Исследованию общих принципов проектирования и построения самоорганизующихся сетей БПЛА посвящено значительное количество работ отечественных и зарубежных ученых, в том числе А. Е. Кучерявого, А.И. Парамонова, Р.В. Киричека, I. F. Akyildiz, O. K. Sahingos, I. Bekmezci, S. Termel и др.

Решению задачи маршрутизации в самоорганизующихся сетях БПЛА посвящены исследования, среди которых наиболее известны работы отечественных ученых Д. С. Васильева, А. В. Абилова и зарубежных - S. Rosati, K. Kruzelecki, G. Heitz, D. Floreano, B. Rimoldi, M. H. Tareque, M. S. Hossain, M. Atiquzzaman и др.

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

Теоретические основы разработки алгоритмов пчелиной колонии описаны в трудах ученых В.В. Курейчика, А.А. Кажарова, В.Б. Лебедева, Е.М. Бронштейна, С.Д. Штовбы, D. Karaboga, G.Zhu, B.Akay, D.T. Pham, D. Teodorovi^

Основной вклад в исследование и разработку алгоритмов маршрутизации для самоорганизующихся сетей на основе пчелиной колонии внесли H.F. Wedde, M. Farooq, T. Pannenbaecker, M. Saleem, I. Ullah.

Наиболее близкой к заявленной теме исследований является опубликованная в 2016 коллективная работа китайских ученых из военно-воздушного инженерного университета: Yu Yunlong, Ru Le, Chi Wensheng, Liu Yaqing, Yu Qiangqiang, Fang Kun, Yu Yunlong, в которой предложен протокол маршрутизации для самоорганизующейся сети БПЛА на основе алгоритма муравьиной колонии.

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

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

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

Объект исследования

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

Предмет исследования

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

Цели и задачи исследования

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

Для достижения поставленной цели, в диссертационной работе последовательно решаются следующие задачи:

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

2. Разработать методику оценки эффективности методов маршрутизации в самоорганизующихся сетях БПЛА, а также разработать реалистичные

имитационные модели типовых сценариев применения самоорганизующихся сетей БПЛА.

3. Разработать программную реализацию предложенного алгоритма маршрутизации для среды имитационного моделирования. Создать ПО для обработки и анализа результатов имитационного моделирования с возможностью использования в учебном процессе.

4. Провести исследование по определению эффективного критерия оптимальности (метрики), используемого в разработанном алгоритме для каждого из моделируемых сценариев. Провести оценку эффективности предложенного алгоритма путем проведения сравнительного анализа результатов имитационного моделирования с существующими протоколами маршрутизации в типовых сценариях применения самоорганизующихся сетей БПЛА.

Методы исследования

Для решения поставленных в исследовании задач использовались общенаучные методы и приемы исследования (анализ, аналогия, абстрагирование), методы дискретной и вычислительной математики, эвристические методы оптимизации, методы математической статистики и имитационное моделирование.

При разработке программной реализации, построении математических и имитационных моделей использовались следующие языки программирования и программные продукты: С/С++, Python, OTcl, NS-2, BonnMotion и MATLAB.

Соответствие паспорту специальности

Диссертационное исследование соответствуют пунктам (областям) паспорта научной специальности 05.12.13 «Системы, сети и устройства телекоммуникаций»:

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

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

Пункт 4: «Исследование путей совершенствования управления информационными потоками».

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

Пункт 11: «Разработка научно-технических основ технологии создания сетей, систем и устройств телекоммуникаций и обеспечения их эффективного функционирования».

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

Пункт 12: «Разработка методов эффективного использования сетей, систем и устройств телекоммуникаций в различных отраслях народного хозяйства».

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

Пункт 14: «Разработка методов исследования, моделирования и проектирования сетей, систем и устройств телекоммуникаций».

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

Научная новизна

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

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

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

4. Разработаны реалистичные имитационные модели типовых сценариев применения самоорганизующихся сетей БПЛА, позволяющие проводить широкий диапазон исследований, направленных на повышение эффективности функционирования сети. Для каждого сценария определены численные характеристики и параметры, проведено их обоснование. Сформулированы допущения и ограничения, используемые при разработке имитационных моделей.

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

Теоретическая значимость диссертационной работы заключается в разработке и исследовании нового алгоритма адаптивной маршрутизации на основе роевого интеллекта пчелиной колонии. Алгоритм относится к реактивным методам многопутевой маршрутизации от источника и может рассматриваться в качестве универсального решения задачи маршрутизации в самоорганизующихся сетях БПЛА. Он позволяет выбрать подходящую метрику и оптимизировать настроечные параметры для эффективного использования сетевых ресурсов, выполнения требований QoS и предотвращения перегрузки сети в выбранном

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

Практическая значимость

По результатам проведенного имитационного моделирования разработанный алгоритм продемонстрировал высокие результаты в каждом из используемых типовых сценариев применения самоорганизующейся сети БПЛА превосходя по многим показателям протоколы AODV и OLSR. Наилучшие результаты были продемонстрированы по показателям: коэффициент доставки пакетов увеличился на 2-11%, средняя пропускная способность возросла на 3-12%, нормализованная нагрузка на маршрутизацию снизилась на 22-82%, накладные расходы на маршрутизацию сократились на 33-79% в зависимости от сценария. В отношении показателей сквозной задержки и джиттера предложенный алгоритм уступает протоколу OLSR и превосходит AODV.

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

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

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

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

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

1. Универсальный адаптивный алгоритм многопутевой маршрутизации от источника для самоорганизующейся сети БПЛА на основе роевого интеллекта пчелиной колонии.

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

3. Методика оценки эффективности методов маршрутизации в самоорганизующейся сети БПЛА, включающая в себя взаимодополняющие показатели: коэффициент доставки пакетов, среднюю пропускную способность, нормализованную нагрузку на маршрутизацию, накладные расходы на маршрутизацию, сквозную задержку и джиттер.

4. Комплекс реалистичных имитационных моделей типовых сценариев применения самоорганизующихся сетей БПЛА.

Степень достоверности результатов

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

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

Апробация результатов

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

- VI международная научно-техническая конференция «Инфокоммуникационные технологии в науке, производстве и образовании (ИНФОКОМ-6)», г. Ставрополь, 2014.

- Международная научно-практическая конференция «Управление инновационной деятельностью экономических систем (ИНПРОМ-2014)», г. Санкт-Петербург, 2014.

- Международная научно-практическая конференция «Инновационная экономика и промышленная политика региона (ЭКОПРОМ-2014)», г. Санкт-Петербург, 2014.

- Научно-практическая конференция с зарубежным участием «Реструктуризация экономики России и промышленная политика (INDUSTRY-2015)», г. Санкт-Петербург, 2015.

- Международная научно-практическая конференция «Современные проблемы и задачи обеспечения информационной безопасности (СИБ - 2015)», г. Москва, 2015.

- International Siberian Conference on Control and Communications (SIBCON), Moscow, Russia, 2016.

- 17th, 19th International Conference of Young Specialists on Micro/Nanotechnologies and Electron Devices (EDM), Erlagol, Altai, Russia, 2016, 2018.

- 13th, 14th International Scientific-Technical Conference on Actual Problems of Electronics Instrument Engineering (APEIE), Novosibirsk, Russia, 2016, 2018.

- Российская научно-техническая конференция аспирантов и молодых ученых, посвященная 20-летию СО МАИ «Перспективные информационные и телекоммуникационные технологии», г. Новосибирск, 2016.

- Российская научно-техническая конференция «Современные проблемы телекоммуникаций» г. Новосибирск, 2016, 2017, 2018.

- International Conference on Information Technologies in Business and Industry, Tomsk, Russia, 2018.

- Systems of Signals Generating and Processing in the Field of on Board Communications (ITBI), Moscow, Russia, 2018.

- Systems of Signal Synchronization, Generating and Processing in Telecommunications (SYNCHROINFO), Minsk, Belarus, 2018.

- 12th International IEEE Scientific and Technical Conference on Dynamics of Systems, Mechanisms and Machines (Dynamics), Omsk, Russia, 2018.

Внедрение результатов

Основные результаты диссертационного исследования были получены в процессе выполнения научно-исследовательских работ (НИР), выполняемых ФГБОУ ВО «ОмГТУ», в которых автор являлся руководителем и исполнителем:

1. «Исследование эффективности доставки данных в беспроводных самоорганизующихся сетях MANET», государственный регистрационный № 215020350053, ОмГТУ, 2014.

2. «Надежность доставки данных в беспроводных мобильных самоорганизующихся сетях», государственный регистрационный № АААА-Б15-215121030073-7, ОмГТУ, 2015.

3. «Моделирование биоподобных алгоритмов BeeAdHoc и AntHocNet для летающих Ad Hoc сетей (FANET)», государственный регистрационный № АААА-Б17-217021470113-5, ОмГТУ, 2016.

4. «Экспериментальная оценка возможности использования алгоритма муравьиной колонии AntHocNet для решения задачи маршрутизации в самоорганизующихся сетях БПЛА», государственный регистрационный № АААА-А17-117092840101-8, ОмГТУ, 2017.

5. «Применение протокола на основе алгоритма пчелиной колонии BeeAdHoc для решения задачи маршрутизации в самоорганизующихся сетях беспилотных

летательных аппаратов», государственный регистрационный № АААА-А18-118091790025-5, ОмГТУ, 2018.

Результаты работы внедрены в инженерно-сервисной компании ООО «Автоматика-сервис» при выполнении НИР «Разработка прототипа системы мониторинга хода строительства промышленного объекта», государственный регистрационный № АААА-Б16-216120740066-1, подтверждены актом о внедрении.

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

Научные результаты используются при чтении лекций, проведении практических занятий и лабораторного практикума бакалавров и магистров по направлениям 11.03.02 и 11.04.02 «Инфокоммуникационные технологии и системы связи» в ФГБОУ ВО «ОмГТУ», что подтверждается соответствующим актом об использовании в учебном процессе.

Публикации

Материалы, отражающие основные положения и результаты диссертационного исследования, изложены в 30 публикациях:

- 5 статей в ведущих научных журналах из перечня, рекомендованного ВАК для опубликования основных научных результатов, полученных при подготовке диссертации;

- 14 научных работ опубликовано в журналах и трудах конференций, индексируемых ведущими международными реферативными базами Web of Science, Scopus, IEEE;

- 11 публикаций в научных журналах и материалах научных, научно-практических, научно-технических конференций, индексируемых в РИНЦ.

За период выполнения научного исследования диссертантом были разработаны программы для ЭВМ (свидетельства о государственной регистрации программы для ЭВМ № 2018615563 и № 2018618457).

Личный вклад автора

Все основные результаты диссертационного исследования получены автором самостоятельно.

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

В работах, опубликованных в соавторстве, диссертанту принадлежит ключевая роль.

Структура и объем диссертационного исследования

Диссертационное исследование объемом 186 страниц состоит из оглавления, введения, основной части (поделённой на 4 главы), заключения, списка литературы из 238 цитируемых источников, 7 приложений, а также 16 таблиц и 32 рисунка.

Глава 1 Анализ состояния и перспективы развития самоорганизующихся сетей беспилотных летательных аппаратов

1.1 Беспилотные летательные аппараты общего пользования 1.1.1 Терминология беспилотных летательных аппаратов

Прежде чем перейти к рассмотрению беспилотных летательных аппаратов, необходимо сделать ряд уточнений. На сегодняшний день для БПЛА существует большое количество различных определений.

Наиболее точным определением БПЛА, является следующее: беспилотный летательный аппарат - это летательный аппарат многоразового или условно-многоразового использования, не имеющий на борту экипажа (человека-пилота) и способный самостоятельно целенаправленно перемещаться в воздухе для выполнения различных задач в автономном режиме (с помощью собственной управляющей программы) или посредством дистанционного управления (осуществляемого человеком-оператором со стационарного или мобильного пульта управления) [1].

Основные термины и аббревиатуры, касающиеся БПЛА, приведены в таблице 1.1 [1].

Таблица 1.1 - Основные англоязычные термины в области БПЛА и их русскоязычные эквиваленты

Англоязычный термин Русскоязычный эквивалент

UAV - Unmanned Aerial Vehicle, Uninhabited Aerial Vehicle БПЛА (БЛА) - беспилотный летательный аппарат

Drone Дрон, беспилотный летательный аппарат

Flying robot Воздушный робот

ROA - Remotely Operated Aircraft, RPA - Remote Piloted Aircraft ДПЛА - дистанционно-пилотируемый летательный аппарат

UAS - Unmanned Aerial System БАС - беспилотная авиационная система

Термины БАС (беспилотная авиационная система) и БАК (беспилотный авиационный комплекс) учитывают не только летательный аппарат, но также инфраструктуру и средства обеспечения (наземный пункт управления, средства связи и пр.) [2, 3]. Как правило, БАС и БАК считают синонимами, однако БАК является наиболее широким понятием, так как включает в себя помимо элементов, устанавливающих связь между структурными компонентами системы, еще и технический персонал, протоколы обмена информацией, нормативно-регламентирующую документацию, механизмы интеграции с другими системами [4].

1.1.2 Классификация беспилотных летательных аппаратов

В зависимости от принципа полета все БПЛА можно разделить на несколько типов. На рисунке 1.1 показана общая классификация, начиная с разделения по массе, и далее для БПЛА «тяжелее воздуха» представлено разделение по типам крыла и несущего винта [5].

Рисунок 1.1 - Общие типы БПЛА

Необходимо отметить, что кроме групп, представленных на рисунке 1.1, существуют различные гибридные подклассы БПЛА, которые затруднительно однозначно отнести к какой-либо из перечисленных групп.

На рисунке 1.2 изображен упрощенный вариант классификации, предложенной Флореано и Вудом, позволяющей разделить БПЛА по двум параметрам - время полета и масса [6].

БПЛА с

БПЛА-дерижабль/ неподвижным

БПЛА-воздушный крылом

шар

БПЛА с БПЛА с

машущим несущим

крылом винтом

Масса БПЛА

Рисунок 1.2 - Классификация БПЛА по времени полета и массе

Международная неправительственная организация «UVS International», занимающаяся формированием концепций, сертификацией, а также регулированием полетов БПЛА, разработала и предложила универсальную классификацию. C приведением англоязычных эквивалентов категорий и аббревиатур эта классификация представлена в Приложении А.1 [7]. Эта классификация распространяется как на уже существующие, так и на перспективные разрабатываемые БПЛА. В основном она сформировалась в начале 2000-х годов [8, 9], но с тех пор много раз пересматривалась, поэтому ее нельзя считать окончательно устоявшейся [10].

Список литературы диссертационного исследования кандидат наук Леонов Алексей Викторович, 2021 год

источники

НЕКТАРА

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

Как уже отмечалось, алгоритмы обладают такими ключевыми свойствами для самоорганизующихся сетей, как, адаптивность, самоорганизация, масштабируемость, высокая производительность, надежность. Кроме того, интеллектуальность, многопутевая маршрутизация, быстрое восстановление маршрутов, распределенная нагрузка, отказоустойчивость и быстрая сходимость, простота проектирования и настройки также являются преимуществами протоколов маршрутизации на основе РИ. Существует множество теоретических моделей для доказательства надежности и эффективности этих алгоритмов [117, 118, 119, 120].

Оптимизация по алгоритму муравьиной колонии (англ. Ant Colony Optimization, ACO) [121] является одним из самых популярных эвристических методов РИ, послуживших основой для разработки и внедрения ряда протоколов, а также алгоритмов, применяемых при решении проблемы маршрутизации в самоорганизующихся сетях [122, 123].

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

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

основанные на поведении социальных насекомых (парадигме РИ), могут сыграть важную роль в расширении возможностей самоорганизующихся сетей.

Таблица 2.1 - Основные характеристики алгоритмов маршрутизации для самоорганизующихся сетей._

Свойства алгоритмов/протоколов AntHocNet Termite BeeAdHoc AODV OLSR

Адаптивная маршрутизация в условиях динамики топологии сети д д д д д

Адаптивная маршрутизация в условиях динамики трафика сети д д д ч ч

Адаптивная интеллектуальная маршрутизация д д н д д

Многопутевая маршрутизация д д д н н

Локальное представление о топологии сети д д д д н

Иерархическая кластеризация н н н н н

Конструктивный алгоритм д д д д н

Защита от петель н н д н н

Проактивный алгоритм д д н н д

Реактивный алгоритм д д д д н

Стохастическая разведка д д н н н

Стохастическая маршрутизация данных н н д н н

Формальные свойства алгоритма н ч ч ч ч

Физическая реализация алгоритма ч н н д д

Энергосберегающий/ энергоэффективный н н д н н

* «д» - означает «да», «н» - означает «нет», «ч» - означает, что алгоритм частично обладает свойством

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

2.3.2 Протоколы маршрутизации для самоорганизующихся сетей на основе

алгоритма пчелиной колонии

На протяжении последних десятилетий ведутся активные разработки в области роевого интеллекта. Основной акцент сделан на создание адаптивных, децентрализованных, гибких и надежных систем, способных решать широкий спектр задач в различных отраслях народного хозяйства. Исследования в этой области, в основном сосредоточены на использовании принципов работы муравьиных колоний при разработке новых алгоритмов для эффективного решения задач комбинаторной оптимизации [124, 125, 126, 127]. При этом, мало внимания уделяется разработке и применению принципов работы, лежащих в основе поведения медоносных пчел.

С начала 2000-х годов, проделана большая работа по внедрению методов РИ, разработаны первые алгоритмы и протоколы маршрутизации для телекоммуникационных сетей на основе пчелиной колонии [128, 129]. Поскольку централизованным подходам к решению задачи маршрутизации в FANET не хватает масштабируемости и отказоустойчивости, алгоритм пчелиной колонии предоставляет естественные решения посредством распределенных подходов к адаптивной маршрутизации.

Кроме того, межуровневый дизайн (англ. cross layer desing, CLD), -перспективный метод, используемый для обеспечения QoS, мало исследовался при разработке протоколов маршрутизации на основе РИ. В частности, пчелиного алгоритма для повышения эффективности самоорганизующихся сетей. Необходимо отметить, что алгоритмы маршрутизации на основе пчелиной колонии, существенно отличаются как от большинства традиционных протоколов, так и от других алгоритмов роевого интеллекта. Наиболее известные и популярные представлены в таблице 2.2.

Идея пчелиного алгоритма, предложенного в данной работе, основывается на моделировании поведения пчел во время поиска и сбора нектара. Наблюдая за колониями пчел в природе, исследователи обнаружили ряд уникальных

особенностей, послуживших основой для разработки эффективных решений задачи маршрутизации в самоорганизующихся сетях [127, 130, 131].

Таблица 2.2 - Алгоритмы маршрутизации на основе ABC для самоорганизующихся сетей

MANET VANET WSN

BeeAdHoc [132] Bee Life Algorithm [133] BeeSensor [134]

BeelP [135] QoSBeeVanet [136] Bee-Sensor-C [137]

BeeAIS [138] HyBR [139] ICWAQ [140]

Bee-MANET [141] MQBV [143] Artificial Bee Colony [131]

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

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

Протоколы маршрутизации, вдохновленные природой, становятся активной областью исследований, поскольку агенты в таких алгоритмах позволяют узлу принимать децентрализованные решения о маршрутизации без каких-либо знаний о топологии сети. Кроме того, алгоритмы быстро адаптируются к изменениям в топологии и трафике сети [144].

Новый реактивный алгоритм маршрутизации для FANET, базируется на идеях предложенных в протоколе BeeAdHoc, классическая реализация которого рассматривалась в работе [145], а модифицированная версия - в работе [146]. По сравнению с другими популярными классическими протоколами, такими как AODV, DSR и DSDV, он показывает хорошую производительность в относительно небольших сетях (около 50 узлов).

Основными функциональными задачами разрабатываемого алгоритма являются:

- исключение перегрузки сети;

- повышение эффективности использования сетевых ресурсов.

В качестве критериев для оптимизации информационного потока предлагается использовать: пропускную способность, сквозную задержку, уровень заряда батареи узла и время жизни сети.

2.4.1 Спецификация алгоритма

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

Руководствуясь поставленной целью, предыдущим разделом и разделом 1.2.2 «Динамическая маршрутизация в самоорганизующихся сетях беспилотных летательных аппаратов», был составлен перечень требований к разрабатываемому алгоритму маршрутизации:

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

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

- Конвергентность (сходимость) - процесс согласования узлами сети оптимальных маршрутов. Для борьбы со сбоями в работе сети алгоритм

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

- Гибкость - способность алгоритма быстро адаптироваться к изменениям сетевых условий (топологии сети, пропускной способности, задержке и др).

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

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

- Адаптивность к изменениям в сети с высокой мобильностью узлов и интенсивностью трафика.

Из этого следует, что для передачи большого количества разнородного трафика в самоорганизующихся сетях БПЛА, особенно, трафика реального времени (критичного к задержкам и/или другим показателям качества обслуживания, QoS) необходимо обеспечить высокую пропускную способность, сократить время на установление маршрута, увеличить вероятность доставки пакетов и уменьшить задержку. Поскольку скорость перемещения узлов может достигать 60 м/с, в сети происходят частые и быстрые изменения топологии, повышающие вероятность возникновения обрывов связи. Перспективным вариантом решения поставленной задачи является разработка многопутевого алгоритма маршрутизации.

2.4.2 Модель агента пчелы

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

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

Модель агентов очень похожа на свой аналог в природе, как и в протоколе BeeAdHoc [146] включает в себя 4 типа агентов: упаковщики (англ. packers), разведчики/скауты, фуражиры и рои (англ. swarms) (Приложение Б.1). При этом, модель является адаптивной - способна изменять скорость сбора и обработки нектара. Каждый узел выступает в роли улья, а маршрут - источника пищи.

Упаковщики

Упаковщики копируют функции пчел-заготовителей в улье. Их основная задача - получение данных с транспортного уровня и передача фуражирам. Сразу после этого они «умирают» (Приложение Б.2).

Упаковщик Рd, попадая в очередь на отправку L#, инициирует поиск танцующего фуражира Fsd из списка фуражиров Ld узла-источника s, для доставки пакета данных Dsd узлу-получателю ). Следует отметить, что выбор фуражира осуществляется случайным образом (по аналогии с поведением в живой природе), при условии, что у Fsd не истекло время жизни Т% и время танца Td. В противном случае, инициализируется немедленная отправка разведчика Ssd.

Разведчики

Разведчик используется для нахождения новых маршрутов к узлу назначения ), посредством широковещательной (англ. broadcast) рассылки в многошаговом режиме (рисунок 2.5) [147].

После получения транзитным узлом скаута Ssd он пересылается всем своим соседям узла i, при условии, что ранее не была получена его копия от другого узла и время жизни Ssd (англ. Time-to-Live, TTL) не было превышено. С помощью TTL ограничивается радиус распространения, т.е. количество разрешенных ретрансляций/прыжков через промежуточные узлы, прежде чем он «умрет» в поисках узла-назначения ). У каждого скаута есть свой уникальный идентификатор (англ. identifier, ID), сгенерированный узлом-отправителем s. Идентификатор используется для устранения зацикливания маршрута и предотвращения множественных передач одного и того же Ssd промежуточным узлом i если он получил его по разным каналам от соседних узлов.

Рисунок 2.5 - Поиск маршрута от узла-отправителя ' до узла-назначения ).

Широковещательная рассылка скаутов

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

Фуражиры

Фуражир - агент, играющий ключевую роль в процессе определения маршрута, применяется для доставки до узла назначения ) пакетов данных ,

полученных от упаковщиков . Фуражиры делятся на следующие 4 типа: задержка, пропускная способность, время жизни сети и уровень заряда батареи. Первый тип доставляет пакет по маршрутам с минимальной задержкой, второй с максимальной пропускной способностью, третий отправляет пакеты таким образом, чтобы максимально увеличить время жизни сети, а четвертый строит маршруты через узлы с наибольшим уровнем заряда батареи. В результате обеспечивается использование маршрута с учетом требований к качеству обслуживания - QoS-маршрутизация [148].

Фуражир получает полный маршрут в виде последовательности промежуточных узлов , до узла назначения ) от разведчика или другого фуражира. Передача осуществляется в режиме «точка-точка» (одноадресная, англ. unicast), при этом по пути до узла-получателя фуражир собирает информацию о сети в соответствии с его типом. После достижения узла ) фуражир помещается во временное хранилище Тй$ для отправки узлу-отправителю я (рисунок 2.6).

Рисунок 2.6 - Одноадресная передача данных Dsd фуражиром Fsd между узлом-отправителем s и узлом-получателем )

Если используется транспортный протокол TCP (англ. Transmission Control Protocol), фуражиры доставляются обратно после получения от узла s сегмента с флагом FIN (англ. Final) с помощью специального фуражира FsdFIN/ACK, содержащего сегмент подтверждения ACK (англ. Acknowledgement), в

соответствии с RFC 793 [149]. В качестве FsdFIN/ACK, используется произвольно выбранный из Tds, фуражир Fsd для узла s с одинаковым ISN (Приложение Б.3). Если используется UDP (англ. User Datagram Protocol), фуражиры будут отправлены узлу s по окончании определенного периода времени или при достижении порогового значения Fsd в Tds, посредством специального пакета -рой, SWds.

Когда Fsd возвращаются к своему исходному узлу s, они используют метафору танца также, как и разведчики. Этот механизм позволяет сократить сократить количество служебного трафика.

Рои

Так как протокол UDP (RFC 768) [150] не отправляет подтверждения успешного получения данных, он не имеет встроенного механизма, который можно было бы задействовать для возвращения фуражиров Fsd узлу-отправителю s. Поэтому, данная проблема была решена при помощи специальных служебных пакетов - роев, SWds (Приложение Б.4).

Как только разница между прибывающими фуражирами из узла-отправителя s и исходящими фуражирами из того же узла s достигает порогового значения или истекает интервал ожидания отправки в узле-получателе ), инициируется отправка SWds. В качестве роя, случайным образом из Tds выбирается фуражир Fsd узла-отправителя s, при этом остальные фуражиры помещаются в поле полезных данных SWds. Когда рой прибывает в узел-назначения, фуражиры извлекаются также, как и в случае с TCP.

2.4.3 Структура алгоритма

В каждом узле есть улей, состоящий из 3-х уровней (рисунок 2.7): уровень упаковки FP, (англ. packing floor), вход FE (англ. entrance) и танцпол F( (англ. dance floor). Вход - это интерфейс взаимодействия с MAC уровнем (англ. Medium Access

Control), а уровень упаковки является интерфейсом для транспортного уровня (TCP, UDP). Танцпол используется в качестве таблицы маршрутизации, где пчелы-агенты (скауты Ssd и фуражиры Fsd) обмениваются информацией о качестве маршрутов посредством метафоры танца.

MAC уровень

Рисунок 2.7 - Структурная схема алгоритма

Уровень упаковки

Приложения Б.2, Б.3 и Б.4 изложены принцип работы и последовательность действий, выполняемых на уровне упаковки F&.

Как только Dsd поступает с транспортного уровня, создается упаковщик Pd. На танцпол F( отправляется запрос поиска подходящего фуражира Fsd. Если он найден, тогда Dsd инкапсулируется в фуражира, а Pd «умирает». В противном случае Pd может ждать некоторое время в очереди (возможно, возвращающийся фуражир Fsd находится на пути к текущему узлу '), если в течение этого периода не прибывает ни один фуражир Fsd, запускается разведчик Ssd, который отвечает за обнаружение новых маршрутов к месту назначения ) для пакета данных Dsd. Если по истечении определенного интервала не удалось найти соответствующего фуражира, пакет отбрасывается (англ. dropped).

55 Вход

Вход является интерфейсом для MAC уровня, FE обрабатывает все входящие/исходящие пакеты (Приложение Б.5). Разведчик Ssd, полученный на входе, пересылается hnest, если его время жизни (таймер TTL) не истек или если он не прибыл в пункт назначения ). Информация об идентификаторе ID разведчика и его исходном узле s хранится в списке %ss. Если на танцполе уже существует фуражир Fj" с тем же пунктом назначения ), что и у разведчика Ssi, маршрут к пункту назначения передается разведчику путем добавления маршрута известного фуражиру к текущему маршруту Ssd. Фуражиры Fid содержат в заголовке полную информацию о маршруте от i до ).

Если текущий узел является для Fsd, узлом-назначения ), тогда он пересылается на уровень упаковки FP, иначе он пересылается на MAC уровень следующего узла hnes+ в направлении ).

Танцпол

В Приложениях Б.6 и Б.7 детально описан принцип работы алгоритма на уровне танцпола.

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

С танцпола F( осуществляется отправка подходящего фуражира на FP в ответ на запрос от Pd. Если на F( находится несколько Fsd соответствующих заданным критериям, тогда выбор одного из них производится стохастически (по аналогии с поведением пчел-фуражиров в живой природе). При этом копия выбранного Fsd отправляется на уровень упаковки FP, а исходный фуражир сохраняется на танцполе с уменьшением количества танцев DN. Если число DN равно нулю, исходный Fsd отправляется на FP, а его запись удаляется с танцпола. Фуражиры,

время жизни которых Т% истекает, исключаются из процесса выбора. Используя вышеупомянутый принцип, осуществляется процесс обновления Fsd, т.е. замены «старых» на более «молодых», содержащих обновленные/актуальные маршруты. Также этот подход помогает в распределении фуражиров Fsd по нескольким маршрутам, что позволяет избегать перегрузок, увеличивает надежность, повышает отказоустойчивость и стабильность работы сети, а также оптимальное использование ресурсов (например, равномерная скорость разряда батареи).

Если последний Fsd для узла-назначения ) покидает улей, тогда у узла-отправителя s не остается маршрута до получателя. Предполагается, что если маршрут до назначения ) существует, то вскоре фуражир вернется обратно в s, если же ни один Fsd не вернется в течение некоторого времени, то узел-отправитель s, вероятно, потерял маршрут к узлу-назначения ). Применение этого механизма устраняет необходимость явного мониторинга достоверности/актуальности маршрутов с помощью специальных пакетов приветствия HELLO и последующего информирования других узлов с помощью сообщений об ошибках маршрутов (англ. Route error, RERR) [151]. Как следствие этого, уменьшается объем служебного трафика, а также снижаются затраты энергии.

2.4.4 Метрики маршрутизации

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

Выбор метрики маршрутизации один из ключевых факторов для обеспечения эффективного функционирования самоорганизующейся сети БПЛА. На выбор метрики оказывают влияние множество факторов: сценарий использования (определяет количество БПЛА, модель и степень мобильности), интенсивность и тип трафика, среда передачи и пр. Особенно важное значение при выборе метрики маршрутизации бывает в случае, если протокол осуществляет балансировку

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

Поэтому, актуальным остается вопрос проведения оптимизации информационных потоков внутри сети. Загруженность узлов информационными потоками является основным фактором при повышении качества обслуживания. Поэтому, применение механизмов QoS к отдельным узлам без учета реальных маршрутов следования трафика через сеть не гарантирует того, что поток будет обслужен с заданным уровнем качества. В связи с этим, целесообразно резервировать ресурсы сети на всем протяжении пути следования потока, «из конца в конец» (англ. end-to-and) [152].

В результате проведенного обзорного исследования литературных источников по информационному обмену и критериям оптимизации (метрикам), было установлено следующее. Для самоорганизующихся сетей в качестве критерия оптимизации, как правило, используют длину маршрута, задержку и пропускную способность [153]. Также одной из ключевых задач в работе FANET является уменьшение энергопотребления узлов и увеличение времени жизни сети, поэтому в качестве основы для критерия оптимальности целесообразно использовать уровень заряда источников питания БПЛА [154, 155].

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

(англ. Traffic Engineering). Другими словами, управление маршрутами передачи данных обеспечивает выполнение определенных условий: резервирование каналов, распределение загрузки всех ресурсов сети, балансировку, предотвращение перегрузок и образования длинных очередей.

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

Расчет метрики на основе задержки

Одним из наиболее простых и широко применяющихся показателей оптимизации маршрутов является сквозная задержка (англ. delay) [156]. Метрика направлена на снижение сквозной задержки (англ. end-to-and delay) во время коммуникационного процесса. Для расчета этого показателя, использовалась методика, описанная в работах [122, 146].

Фактическое значение сквозной задержки * для Fsd рассчитывается по формуле:

* = *d -*s, (2.1)

где *d - время получения пакета Fsd узлом-получателем ), *s - время

отправления пакета Fsd узлом-отправителем s. Показатель D. вычисляется по формуле:

, (r т )

D. = 7 * ф(" W, (2.2)

где 7 - весовой коэффициент, определяет максимальное значение количества танцев для Fsd, ; - номинальное значение сквозной задержки, < - весовой коэффициент [157, 124], й - количество переходов (хопов), совершаемых Fsd между s и ), = е [1; 9], йеМ.

Расчет метрики на основе пропускной способности

Другим широко используемым показателем, является пропускная способность сети [158]. Воспользуемся модификацией формул расчета пропускной способности предложенной в работах [159, 146]. В представленных исследованиях на каждом промежуточном узле , осуществляется расчет фактического значения пропускной способности , по пути от ' до ) определяется следующим образом:

Е3 = -3(4 (2.3) 2 ¿-1

где - размер пакета данных, * - время получения текущим транзитным узлом ¿. Показатель рассчитывается, как:

^„г В5 а ,Л ..

(. = -*-, (2.4)

6 8

где 53 = тт#3 - минимальное значение для , 8 - максимально

I

возможное значение канальной скорости, ^ - количество на для узла ).

Расчет метрики на основе уровня заряда батареи

В условиях ограниченности вычислительных и энергетических ресурсов, вопрос обеспечения энергоэффективности относится к числу приоритетных. В самоорганизующихся сетях часто применяется метрика остаточного уровня заряда батареи (остаточной энергии) [160]. Основными преимуществами этого показателя является возможность перераспределения потребления энергии, а следовательно, снижение нагрузки на маршруты. Эта метрика, рассчитывается на основе оценки остаточной энергии каждого из транзитных узлов ¿, на пути от ' до ). Поэтому, передача данных осуществляется по маршрутам, состоящим из узлов с наибольшим уровнем заряда батареи. Таким образом, с точки зрения энергоэффективности, обеспечивается устойчивая передача данных.

Для расчета показателя используется модификация формулы расчета качества маршрута, предложенная в исследовании [161]. Согласно указанного исследования, значение метрики вычисляется следующим образом: на каждом промежуточном узле , определяется значение остаточного заряда батареи К. Тогда определяется выражением:

(.= 7* 9, (2.5)

где K = min Kj - минимальное значение заряда батареи ¿-го узла на маршруте

от s до Kj е [0; 1].

Расчет метрики на основе времени жизни сети

Другим подходом к оптимизации информационных потоков на основе энергоэффективности является использование метрики - время жизни сети [162, 163]. Учитывая различные сценарии применения и требования приложений к качеству обслуживания, для расчета метрики возможно использование разных показателей времени жизни. В работе [146] авторами представлен подход, согласно которому в качестве показателя для расчета метрики используется остаточная емкость энергии источников питания узлов. Благодаря распределению пакетов по нескольким маршрутам, батареи узлов будут разряжаться с одинаковой скоростью, как следствие этого, будет увеличено время жизни сети. По мнению многих исследователей, этот показатель во многом определяет качество работы приложений и сети в целом, а также обладает четкой практической применимостью. Воспользуемся предложенной методикой расчета времени жизни. Тогда для каждого ¿-го транзитного узла, являющегося звеном цепи между s и ), определяется уровень остаточной емкости источника питания Q по формуле:

0, 1 е [0; 0.09]

1, 1 е (0,09; 0,14]

2, 1 е (0,14; 0,20] _ .3, 1 е (0,20; 0,27]

1 ' 4, 1 е (0,27; 0,35^ (2 6)

5, 1 е (0,35; 0,45]

6, 1 е (0,45; 0,65] . 7, 1 е (0,65; 1]

где 1 - остаточная емкость энергии источника питания текущего транзитного узла ¿. Полученные данные агрегируются в , затем используются узлом-отправителем s для вычисления (.. Формула для расчёта показателя (. имеет вид:

nju {;xp-(R-l))*Cmin*Cavg) + l

= 7*---—, (2.7)

A 4 7

где y - масштабирующий коэффициент, Cavg - среднее значение уровня остаточной емкости энергии источника питания на маршруте между s и ), Cmin =

min Cj - минимальное значение уровня остаточной емкости энергии источника i

питания. Коэффициент масштабирования y рассчитывается по формуле:

Y = Cmax * Cmax * Z + 1 (2.8)

Cmax = max Cj - максимальное значение уровня остаточной емкости энергии i

источника питания на маршруте между s и ), Z - максимальное количество переходов (хопов) между s и ), в текущей реализации алгоритма Z = 9.

2.4.5 Формат пакетов

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

В каждый пакет с единым унифицированным заголовком инкапсулируется одно или несколько сообщений, благодаря чему узлы получают возможность обрабатывать пакеты с неизвестными типами данных. Для этого используются поля заголовка определенные в RFC 791 [164]. Формат стандартного заголовка IPv4 показан на рисунке 2.8.

Алгоритм основан на маршрутизации от источника (англ. source routing), следовательно, в заголовке пакета содержится весь маршрут от отправителя до получателя. Поэтому задействованы дополнительные услуги IP протокола по обработке пакетов - поле «Опции» (англ. Options), имеющее максимальный размер 40 байт (при этом значение должно быть кратным 4 байтам). Опции обеспечивают специальные средства маршрутизации и позволяют разместить только девять записей по 4 байта на каждый IPv4 адрес. Оставшиеся 4 байта используются для

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

0 1 2 3

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

|Version| IHL |Type of Service| Total Length |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| Identification |Flags| Fragment Offset |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| Time to Live | Protocol | Header Checksum |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| Source Address |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| Destination Address |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| Options | Padding |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Рисунок 2.8 - Заголовок пакета IPv4

Bit 7 6 5 4 3 2 1 0

| Copy | Option class| Option number |

Рисунок 2.9 - Структура октета «Тип опции»

Документ RFC 791 содержит две опции для маршрутизации от источника:

- Не строгая маршрутизация от источника (англ. Loose Source and Record Route, LSRR) (тип 131) - маршрут не жестко задан отправителем.

- Строгая маршрутизация от источника (англ. Strict Source and Record Route, SSRR) (тип 137) - маршрут жестко задан отправителем.

Так как полный маршрут задается и записывается узлом-отправителем, то используется SSRR (рисунок 2.10). Другими словами, каждый промежуточный узел маршрута до получателя должен быть достигнут за 1 переход/хоп. Как уже

отмечалось ранее, самый длинный маршрут равняется 9 переходам/хопам или 10 1Р-адресам в поле заголовка пакета IPv4.

|10001001| length | pointer Type=137

+-

-+-

-+-

-+-

-+-

-+-

-+-

route data

-+

-+

Рисунок 2.10 - Структура SSRR

В дополнение к этому Fsd необходимо собирать дополнительную информацию от каждого промежуточного узла, чтобы оценить качество пройдённого маршрута в соответствии с выбранным типом фуражира. Поскольку поле опций ограничено 40 байтами, то первые три байта зарезервированы под 137 опцию (8x4) = 32 байта для хранения маршрута, а оставшиеся 5 байт доступны для хранения информации полученной Fsd.

Руководствуясь решением, предложенным в работах [146, 165] для собранных фуражиром данных была введена новая опция, совместимая с RFC 791 и RFC 1700 [166], которой был присвоен номер 162 (рисунок 2.11). При этом, для октета «Тип опции» установлены значения: класс 1, номер 2.

byte: 1 | 2 | 3 | 4 | 5 |

+-+//+-+-+//+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

| 162 | 5 |0 0 0|0 0 0|0 0 0|0 0 0|0 0 0|0 0 0|0 0 0|0 0 0| +-+//+-+-+//+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

type |length| | | | | | | | |

host: 8 7 6 5 4 3 2 1

Для того чтобы записать свои данные в , каждый узел делает трехбитный сдвиг влево в 24-битном поле данных и вставляет значение с правой стороны.

Резюмируя вышеизложенное, и можно рассматривать как

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

Рисунок 2.11 - Структура IP-опции № 162

дальнейшей обработке. Поэтому каждый пакет содержит информацию о типе пчелы/пакета, которая указывается в поле «Тип обслуживания» (англ. Type of Service, ToS) [167]. Сообщения +$" и рои +3"$ отправляются через порт 1124 и 1125 с использованием UDP.

2.4.6 Установление маршрутов и передача данных

Установление маршрута

Отправка широковещательных запросов +$" инициализируется в случае, если необходимо найти маршрут до узла-назначения ), т.е. адресат неизвестен узлу-источнику ' или ранее существовавший маршрут неактивен.

Перед широковещательной рассылкой +$", узел-источник буферизует /( и IP-адрес узла-источника (т.е. свой собственный адрес) на время PACKER_WAITINGTIME. Таким образом, когда узел принимает пакеты от своих соседей, он не перенаправляет эти пакеты. Если маршрут не создается в течении SCOUT_BROADCAST_DELAY_PER_HOP миллисекунд, узел инициализирует новую попытку создать маршрут широковещательной рассылкой +$", количество ограничено 4 попытками. В каждой из них необходимо контролировать значение TTL для управления временем жизни запроса +$". Если не был построен маршрут и/или получен удовлетворяющий требованиям в течении времени

PACKER_TIMEOUT_VALUE, упаковщик , для узла-получателя ) удаляется из буфера , а приложению отправляется сообщение «получатель недоступен» (Приложение Б.8).

Для организации и управления данными используется тип буферизации - FIFO (англ. First In, First Out - «первый пришёл - первый ушёл»). Размер буфера равен значению параметра FORAGER_CAPACITY (Приложение Б.8).

Когда узел-источник ' создает новый маршрут, каждый транзитный узел i отвечает за подтверждение того, что данные могут передаваться от текущего узла к следующему. Подтверждение готовности к передаче данных (наличие связности

т.е. связи между узлами) осуществляется с помощью квитирования (подтверждения приема). Квитирование поддерживается в виде «пассивного подтверждения» или стандартным MAC-протоколом на канальном уровне IEEE 802.11.

Управление распространением широковещательных сообщений

Адресом назначения сообщения Ssd может быть либо IP-адрес следующего перехода, либо адрес отправителя, если разведчик возвращается обратно в узел-источник ' или широковещательный адрес (255.255.255.255) или в случае, когда разведчик на пути к определенному узлу-назначения ). На пакет с таким ограниченным широковещательным (англ. limited broadcast) адресом назначения должны ответить все узлы в пределах широковещательного домена. Радиус распространения Ssd ограничен установленным значением поля TTL в заголовке IP.

Для ограничения неконтролируемого распространения broadcast-запросов, используется алгоритм поиска по «расширяющемуся кольцу», описанный в RFC 922 [168] и применяющийся в протоколах AODV и DSR [169]. В соответствии с алгоритмом устанавливается значение = /./*/0%_ГГ% заголовка Ssd пакета. При этом интервал ожидания скаута устанавливается равным SCOUT_BROADCAST_DELAY_PER_HOP (в миллисекундах). Если по истечении времени ожидания скауту не удалось найти маршрут до ), узел-источник повторно формирует запрос Ssd, увеличивая значение времени TTL на величину TTL_INCREASE. Этот процесс продолжается до тех пор, пока не будет достигнуто TTL значение MAX_TTL. Если узел-назначения ) находится на расстоянии, превышающем MAX_TTL, то такой узел считается недоступным (Приложение Б.8).

2.5 Программная реализация разработанного алгоритма

Поскольку проведение натурных экспериментов для исследования алгоритмов, протоколов, методов и т.д. в сетях FANET является задачей очень трудоемкой и дорогостоящей, то в качестве основного метода исследования использовалось имитационное моделирование, основанное на использовании сетевого симулятора. На сегодняшний день доступно несколько сетевых симуляторов, таких как NS-2, NS-3, OMNeT++, NetSim и др [170, 171, 172]. Текущая версия алгоритма была разработана для работы в среде имитационного моделирования NS-2. Этот симулятор имеет все необходимые инструменты и функции для полноценного моделирования [173, 174]. Опишем наиболее важные особенности программной реализации предложенного алгоритма в NS-2.

2.5.1 Среда имитационного моделирования NS-2

NS-2 - это дискретный симулятор событий, предназначенный для исследований телекоммуникационных сетей, занимающий одно из лидирующих мест и пользующийся широкой популярностью. Эта среда моделирования обеспечивает полную поддержку протоколов прикладного и транспортного уровней, маршрутизацию, многоадресную передачу данных по проводным и беспроводным (локальным и спутниковым) сетям [175].

Возможность моделирования самоорганизующихся сетей FANET появилась в NS-2 с выходом версии 2.31 после добавления программной поддержки спецификации IEEE 802.11 [176, 177].

Выделим наиболее важные достоинства NS-2, нашедшие свое применение в рамках данного исследования [178, с. 2]:

- открытый исходный код, симулятор распространяется под лицензией GNU GPLv2 (General Public License);

- отсутствие ограничений на разработку новых и модификацию существующих протоколов, лицензионное соглашение дает право на модификацию программы;

- поддержка протоколов транспортного уровня (TCP, UDP, RTP, SRM);

- генерация трафика на прикладном уровне (CBR, VBR, FTP, HTTP, stochastic, telnet);

- визуализация моделируемой сети, потоков трафика и результатов моделирования (Network Animator (NAM), Xgraph и др.);

- поддержка стека протоколов IEEE 802.11;

- поддержка протокола определения адреса (ARP);

- поддержка протоколов маршрутизации для самоорганизующихся сетей: DSR, DSDV, TORA, AODV и OLSR (опционально, устанавливается из дополнительного пакета);

- моделирование интерфейса беспроводной сети;

- моделирование задержки пакетов, затухания, ошибок, коллизий, перехвата сигнала;

- реализована энергетическая модель, позволяющая моделировать расход энергии батареи автономных устройств;

- встроенный генератор сетевых топологий;

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

Необходимо отметить, что адекватность моделей построенных в NS-2, а также достоверность результатов моделирования неоднократно подтверждались множеством практических исследований.

2.5.2 Архитектура NS-2

Для работы в среде моделирования NS-2 используется подход, состоящий из двух частей: первая часть - это ядро, оно написано на языке C++, поэтому в случае внесения изменений и дополнений в код его необходимо перекомпилировать, а вторая на интерпретируемом объектно-ориентированном расширении скриптового языка высокого уровня Tcl, получившем название OTcl (Object oriented Tool Command Language), не требующим компиляции [179]. Взаимодействие между

частями, осуществляется в соответствии со спецификацией, при обращении из части С++ к методу описанному в Тс1 скрипте, интерпретатор языка Тс1 вызывается из С++ как функция и наоборот, из скрипта Тс1 обращается к любому методу классов компилируемой иерархии с возвращением полученных результатов. Отметим, что иерархии классов в обеих частях содержит совпадающие части, которые называются по принятой в NS-2 терминологии компилируемой и интерпретируемой иерархиями соответственно (рисунок 2.12).

Благодаря такому подходу, программная реализация алгоритма на языке С++ обладает высоким быстродействием и эффективностью. А в случае, когда в угоду производительности на первое место выходит простота и быстрота разработки, используется ОТс1. Кроме того, Тс1-скрип расширяет возможности симулятора, позволяет быстро описать и построить модель исследуемой сети. Это облегчает процесс настройки и управления моделированием без необходимости глубокого понимания структуры компилируемой части №-2.

Рисунок 2.12 - Архитектура сетевого симулятора NS-2

В NS-2 абстракцией на сетевом уровне является узел представляющий собой составной объект, способный принимать и классифицировать пакеты на основе информации, содержащейся в полях IP-заголовка. В NS-2 составные объекты формируются с помощью объединения простых объектов. Симулятор имеет большой набор готовых описаний классов составных объектов: узлы (англ. nodes),

линии связи (англ. links), локальные сети (проводные IEEE 802.3 Ethernet, беспроводные IEEE 802.11) и пр. Кроме того, функциональность системы может быть улучшена и расширена за счет добавления новых классов сетевых объектов описанных на языке C++ либо OTcl.

Структура сетевого узла симулятора NS-2 представлена в Приложении Б.9.

2.5.3 Описание программной реализации

В соответствии с рекомендациями по разработке новых методов в NS-2, а также ввиду необходимости обеспечения высокой производительности с сохранением возможности модификации и расширения функционала компилируемой части, программная реализация алгоритма была написана на языке C++. Текущая версия алгоритма разработана для симулятора NS-2 версии 2.34 и включает в себя следующие программные модули и файлы:

- badhoc_beeDefinitions.h, определяет константы и структуру агентов. Для удобства большая часть констант доступна для иерархии TCL в качестве переменных;

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

- hdr_beeadhoc.cc и hdr_beeadhoc.h связывают заголовки пакетов BeeAdHoc со структурами NS-2, которые являются полями данных для параметров IP и маршрутизации от источника;

- beeadhoc.h - это файл определения глобальной структуры данных и классов BeeAdHoc;

- beeadhoc.tcl устанавливает переменные TCL BeeAdHoc со значением по умолчанию;

- beeadhoc_entrance.cc - класс, отвечающий за реализацию входа;

- beeadhoc_packingfloor.cc - класс, отвечающий за реализацию уровня упаковки;

- beeadhoc_dancefloor.cc и beeadhoc_dancefloor.h - класс, отвечающий в BeeAdHoc за реализацию танцпола.

Для того чтобы интегрировать BeeAdHoc в NS-2, были модифицированы исходники симулятора:

- Makefile.in - набор инструкций(правил) для утилиты make, необходим для того, чтобы скомпилировать версию NS-2 с поддержкой BeeAdHoc.

- packet.h добавляет к ядру NS-2 все заголовки пакетов, определенные в hdr_beeadhoc.cc, необходимые BeeAdHoc для обмена между узлами в сети.

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

- cmu-trace.cc и cmu-trace.h - содержат описание аргументов функции отбрасывания пакетов. Аргументы являются указателями на сам пакет, а константы описывают причину отбрасывания (удаления).

- tcl/lib/ns-lib.tcl добавляет агент маршрутизации BeeAdHoc в иерархию TCL. Класс предоставляет процедуры для создания и управления топологией, а также хранит ссылки на каждый элемент топологии.

- tcl/lib/ns-packet.tcl делает доступными имена заголовков пакетов BeeAdHoc.

Как уже упоминалось, класс beeadhoc.cc предоставляет интерфейс для

сетевого симулятора. Он используется при создании уровней (упаковка, вход, танцпол) и связывает переменные TCL. Также он содержит вспомогательные функции для преобразования пакетов NS-2 в агентах BeeAdHoc и наоборот.

Приложение Б.8 содержит листинг файла beeadhoc.tcl, включающего в себя перечень основных переменных TCL - значения настроечных параметров и их краткое описание.

2.5.4 Исследование и выбор значений настроечных параметров

Ранее отмечалось, что эффективность работы алгоритмов роевого интеллекта зависит от настроечных параметров, значения которых могут быть определены в ходе метаоптимизации [180]. В случае выбора неоптимальных значений качество получаемых решений может снизиться от нескольких десятков процентов до 2-3 раз. К сожалению, данная особенность алгоритма пчелиной колонии не позволяет выработать единые рекомендации по выбору универсальных значений настроечных параметров.

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

Найти оптимальные значения параметров и изучить их влияние на поведение алгоритма является нетривиальной задачей. Кроме того, зачастую настраиваемые параметры определяются без четких значений по умолчанию и могут быть определены в очень широком диапазоне. Для решения этой задачи, с помощью процедуры моделирования были проведены широкомасштабные экспериментальные исследования. Процедура моделирования - это способ присвоения количественного значения качества (пригодности) параметрам, регулирующим разработанный алгоритм, позволяющий получить его оптимальные конфигурации с учетом конкретного сценария FANET. Эта процедура выполнялась с помощью сетевого симулятора №-2, который был модифицирован для данного исследования и программной модели предложенного метода маршрутизации для выбранной среды имитационного моделирования.

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

Таблица 2.3 - Основные параметры разработанного алгоритма маршрутизации

Параметр Значения по Диапазон

умолчанию возможных значении

RATING MAX DANCES 10 L e [1,10]

FORAGER CAPACITY 50 L e [1,100]

FORAGER LIFETIME 10 s R e [1.0,100.0]

FORAGER DANCETIME 10 s R e [1.0,100.0]

PACKER WAITINGTIME 0.15 s R e [0.01,0.2]

SEENSCOUTLIST SIZE 100 L e [10,100]

SWARM SIZE 100 L e [10,100]

PACKER TIMEOUT VALUE 5.0 s R e [1.0,20.0]

SCOUT BROADCAST DELAY PER HOP 0.002 s R e [0.001,0.1]

INITIAL TTL 1 L e [1,5]

TTL INCREASE 3 L e [1,5]

MAX TTL 10 L e [1,10]

Выбор значений нижеследующих параметров, обусловлен прежде всего накопленным научно-практическим опытом в области применения алгоритма пчелиной колонии при решении задачи маршрутизации в самоорганизующихся сетях. Для параметров 7, <, используются значения, полученные в исследованиях [145] [146]. Далее, с использованием этих значений настроечных параметров был проведен ряд вычислительных экспериментов, в результате которых было получено значение коэффициента масштабирования ш, которое равняется 442. Значение задержки ; из формулы (2.2) является постоянным. Размер ее величины зависит от сценария использования, протоколов транспортного уровня, используемых приложений, скорости передачи и размера данных, а также вероятности ошибок при передаче. Величина параметра I, из формулы (2.4), также является величиной постоянной и определяется особенностями конкретной

аппаратной реализации сетевого устройства (модели Wi-Fi адаптера и используемого стандарта беспроводной связи IEEE 802.11) (Приложение Б.8).

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

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

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

3. Разработан новый реактивный алгоритм многопутевой маршрутизации от источника для самоорганизующихся сетей БПЛА на основе роевого интеллекта пчелиной колонии, с использованием алгоритма поиска по «расширяющемуся кольцу». Предложенный алгоритм обеспечивает поддержку следующих показателей (метрик) при построении маршрута: пропускная способность, задержка, уровень заряда батареи, время жизни сети.

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

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

краткое описание программной реализации алгоритма и среды имитационного моделирования №-2.

6. Для проведения серии экспериментов по исследованию поведения алгоритма и определению значений его настроечных параметров, в среде моделирования №-2 была разработана программная реализация предложенного алгоритма маршрутизации.

7. Исследовано влияние настроечных параметров на поведение алгоритма, для каждого параметра определен диапазон возможных значений и значения по умолчанию.

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

самоорганизующихся сетей БПЛА

В FANET возможны самые разнообразные сценарии взаимодействия как внутри группировки БПЛА, так и между наземным и воздушными сегментами [181, 182]. Развертывание реальной самоорганизующейся сети БПЛА требует большого количества ресурсов, времени и людей, поэтому в качестве метода исследования выбрано имитационное моделирование.

Для проведения исследований разработаны имитационные модели типовых сценариев применения FANET [183], в соответствии с принципом «разумной достаточности», т.е. степень приближенности к реальным условиям функционирования позволяет получить стабильные ранговые результаты моделирования (обеспечивает воспроизводимость результатов измерений). Достоверность результатов, полученных в ходе моделирования, зависит от степени приближения имитируемых условий к условиям эксплуатации в реальной жизни. Поэтому, при разработке реалистичных моделей должны учитываться особенности топологии сети и мобильности узлов, характерные для каждого сценария, параметры и характеристики исследуемого типа БПЛА, воздействие различных внешних факторов и пр. Для подготовки сценария моделирования необходимо решить следующие основные задачи:

- выбрать модель мобильности, учитывающую особенности сценария и тип БПЛА, а также определить значения ее настроечных параметров;

- выбрать модель распространения радиосигнала;

- выбрать модель приложения или генератор трафика на прикладном уровне;

- в зависимости от выбранного приложения или генератора трафика, выбрать протокол транспортного уровня;

- выбрать протокол маршрутизации;

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

- написать код сценария моделирования на основе выбранных моделей мобильности, распространения сигнала, приложения и т.д.

3.1.1 Генератор сценариев BonnMotion

Особенности выбранных сценариев применения обуславливают необходимость использования корректных и адекватных моделей мобильности. В качестве инструмента для решения этой задачи автором исследования был сделан выбор в пользу специализированного программного обеспечения ВоппМойоп, позволяющего генерировать код сценария на основе реалистичных моделей мобильности и совместимого с симулятором №-2 [184]. Продукт является результатом совместной работы научно-исследовательской группы ученых из Боннского университета (Германия), Оснабрюкского университета (Германия), Колорадской горной школы (США).

ВоппМойоп получил широкое распространение и признание, что подтверждается активным использованием в научных работах, посвященных исследованию самоорганизующихся сетей БПЛА [185]. Генератор сценариев относится к свободно распространяемому программному обеспечению с открытым исходным кодом и предоставляет гибкую возможность расширения функционала.

3.1.2 Сценарии применения самоорганизующихся сетей БПЛА

В рамках данного диссертационного исследования для разработки реалистичных имитационных моделей были выбраны следующие типовые сценарии применения самоорганизующихся сетей БПЛА [186, 187]:

- Рой, - классический пример работы самоорганизующейся сети. Каждый БПЛА совмещает функции оконечного устройства и маршрутизатора.

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

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

Для каждого из сценариев используется зона обслуживания прямоугольной формы со сторонами 3600*1200 м2 [188]. Благодаря этому становится возможным построение более длинных маршрутов по сравнению с квадратной формой, при этом плотность узлов на единицу площади остается неизменной. Все узлы сети однородны, имеют одинаковые характеристики взаимодействия на физическом, канальном, сетевом и транспортных уровнях. В зависимости от сценария, сеть может состоять из следующих типов узлов:

- БПЛА, - как уже отмечалось ранее (раздел 1.1.3), в исследовании имитируется поведение квадрокоптеров с эклектической силовой установкой, относящихся к классу мини-БПЛА. Исходя из сценария, они могут выполнять функции: генератора трафика, транзитных узлов или выполнять одновременно обе.

- Наземная базовая станция (НБС), - является стационарным узлом. Геометрическое положение в зоне обслуживания, количество, а также функции и направление приема и/или передачи данных определяются исходя из контекста решаемой задачи и сценария использования.

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

При разработке имитационных моделей были приняты следующие допущения:

1. Будем полагать, что связность сети зависит от расстояния между узлами, оборудованными всенаправленными (omni) антеннами, дальность связи которых, определяется в виде диска радиусом (рисунок 3.1).

Несвязный БПЛА

Рисунок 3.1 - Пример топологии самоорганизующейся сети БПЛА с одним

несвязным узлом

Тогда, два узла сети являются связными, если они могут передать и получить данные друг от друга непосредственно или через транзитные узлы. В противном случае передача данных между этими узлами невозможна [189]. Помимо этого, на маршрутизацию оказывает существенное влияние плотность размещения узлов, так как наряду с моделью мобильности и диапазоном радиосвязи, она определяет количество соседей узла [190]. Если плотность узлов недостаточна, сеть становится разреженной, следовательно связь между узлами также невозможна [191].

2. Используется упрощенная модель движения БПЛА в двумерном пространстве, т.к. было сделано предположение, что БПЛА летают примерно на одной высоте.

3. Сделано предположение, что модули беспроводной связи на всех сетевых узлах (БПЛА, НБС) настроены одинаково, каждый осуществляет уверенный прием и передачу данных.

4. Каждый БПЛА оснащен системой предотвращения столкновений.

5. Полеты БПЛА выполняются только в благоприятных погодно-климатических условиях (температура воздуха, сила ветра и др.).

6. Продолжительность полета БПЛА для выполнения миссии моделируется без учета времени необходимого на взлет и посадку, т.е. сделано допущение, что в предложенных моделях эти этапы полета происходят мгновенно.

7. Количество БПЛА во время выполнения мисси остается неизменным, т.е. на узлы сети не оказывается никакого негативного воздействия (радиоэлектронное подавление, блокировка каналов связи и пр.), а заряда батареи достаточно для обеспечения непрерывного полета.

3.1.4 Модели мобильности для типовых сценариев применения

Модели мобильности применяются для имитации реалистичного движения различных типов узлов сети. Важно отметить, что разработка реалистичных моделей мобильности для FANET является открытой научной проблемой, которая выходит за рамки данного исследования [53]. Поэтому, автором диссертационной работы было принято решение использовать существующие модели мобильности доступные для сетевых симуляторов [192]. На подготовительном этапе, каждая модель была адаптирована с учетом типа БПЛА и выбранных сценариев применения.

Рой БПЛА

Моделируется сценарий выполнения группой БПЛА полностью автономной операций без какого-либо централизованного контроля. Взаимодействие узлов сети осуществляется по принципу «каждый с каждым». Пара узел-источник и узел-

назначения выбирается случайным образом, при этом источник выполняет функцию генератора пакетов данных, а узел-назначения их получателя [193].

Сеть состоит из 50 БПЛА, мобильность узлов обеспечивается с помощью детерминированной модели случайной путевой точки (англ. Randow Way Point, RWP): каждый узел случайным образом выбирает скорость и точку назначения в области моделирования, затем перемещается в эту точку. Как только узел прибывает в точку назначения, он остается стационарным в течение определенного периода времени (время паузы), а затем снова он случайным образом выбирает новую точку назначения и движется к ней с новой скоростью, далее этот процесс повторяется. На рисунке 3.2 показан пример траектории движения узла с использованием модели мобильности RWP.

6001 I I I I I I

500 -400 ■ 300 ■ 200 ■ 100 -

О -О

Рисунок 3.2 - Пример траектории движения узла на основе RWP

Скорость выбирается из стационарного распределения между минимальной скоростью vmin = 0 м/с и максимальной vmax = 60 м/с, с шагом 10 м/с. В этом сценарии имитируется высокомобильная сеть БПЛА, поэтому время паузы принимается равным 0, т.е. узлы двигаются безостановочно [194, 195].

Тогда в соответствии с работой [196] стационарное распределение скорости узла /('), определяется уравнением:

/(') = { (3.1)

,0, во всех остальных случаях

где ' - скорость узла.

Поскольку узел движется по прямой линии с постоянной скоростью и местоположение узла выбирается равномерно из множества точек и при условии, что конечными точками пути являются (!,,#,) и (х2,у2), функцию плотности вероятности местоположения для координаты х задается формулой [196]:

Я(!) = /О /1 /с1 )#1 )У-)х,)х2 (3.2)

где и = 1,9179 - это константа, значение выбирается таким образом, чтобы получить общую плотность равную 1.

Использование в этом сценарии модели RWP является распространённой практикой при проведении научных исследований самоорганизующихся сетей БПЛА, в соответствии с концепцией «от простого к сложному». Такой подход позволяет упростить интерпретацию результатов моделирования, выявить особенности функционирования предложенных решений и устранить недостатки на ранних этапах исследования.

Транзитная сеть

Рассмотрим сценарий транзитной сети на основе автономной группы БПЛА [197]. Предположим, что в силу различных причин (технические отказы узлов, радиопомехи, перегрузка каналов связи, особенности рельефа местности и пр.) невозможно обеспечить связность узлов наземного сегмента, т.е. сеть разбита на несколько несвязных между собой подсетей. Применение БПЛА позволит оперативно решить проблему и обеспечить связность между разрозненными сегментами. Каждый БПЛА выполняет функцию неподвижного транзитного узла (ретранслятора), входящего в состав группировки, образующей самоорганизующуюся сеть. Как правило, мобильность такой сети очень низкая или

вовсе отсутствует, т.к. чем меньше перемещаются БПЛА, тем выше производительность сети [198].

В этом сценарии, сеть состоит из 52 узлов, 50 из которых имитируют поведение БПЛА выполняющих функцию ретрансляторов и двух наземных базовых станций, представляющих несвязные наземные сегменты. Координаты взаимодействующих наземных станций: узел-источник (900, 400) и узел-получатель (2700, 800) соответственно. БПЛА распределены случайным образом в зоне обслуживания, все узлы сети стационарны, для данного сценария используется статическая модель мобильности (англ. Static) [187].

Мониторинг осуществляется группой БПЛА в количестве 50 шт., сканирующих заранее определенную территорию. Для этого, было сделано предположение, что БПЛА оснащены бортовыми видеокамерами позволяющими использовать их в качестве источника данных. Полученный с камер поток видео передается в режиме реального времени на стационарную наземную базовую станцию, расположенную в центре зоны обслуживания с координатами (1800, 600)

Для этого сценария используется модель мобильности Гаусса-Маркова (ГМ), позволяющая имитировать реалистичное движение БПЛА [200], при этом скорость движения узлов изменяется в диапазоне от 0 до 10 м/с. Модель ГМ была разработана для адаптации к различным уровням случайности с помощью одного настроечного параметра. На первоначальном этапе каждому узлу сети задаются начальные значения скорости и направления. Через фиксированные интервалы времени п происходит обновление направления движения путем изменения скорости и направления, описываемое следующими уравнениями [201]:

Мониторинг

[199].

(3.3)

)п = а)„_1 + (1-а)) + X (1 7 2))х-_1 (3.4)

где 5п и )п - скорость и направление узла на временном интервале п, 7, -настроечный параметр для изменения уровня случайности 5 и ), 0 < 7 < 1. Константы 5 и ) являются средними значениями скорости и направления, а 'х + и )х + - случайные величины гауссового распределения. Отметим, что при 7 = 0 движение будет полностью случайным (броуновское движение), а при 7 = 1 движение будет прямолинейным. На рисунке 3.3 изображена траектория движения узла полученная с помощью модели ГМ при 7 = 0,85. В таблице 3.1 указаны параметры модели ГМ для сценария «Мониторинг» [202, 203].

600 г

500400 -

зоо -200 -100 -

0|-1-1-1-1-1-

О 50 100 150 200 250 300

Рисунок 3.3 - Пример модели мобильности Гаусса-Маркова

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

хп = хп_ 1 + 'п_ 1 с°5 ^п-1 (3.5)

#п = #п_1 + 'п-1 БШ ¿п-1 (3.6)

где хп, #п, хп-1 и #п-1 - это координаты узла х и # в п-й и п-1 интервалы времени. При этом, 5п-1 и )п-1 - это скорость и направление узла в интервале времени п-1.

Параметр Значение

Интервал времени, 0.5 с

Параметр, 0.85

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

3.1.5 Модель распространения радиосигнала

Сетевые узлы находятся в пределах прямой видимости (англ. line-of-sight, LOS) [204, 205]. Среда распространения радиосигнала считается идеальной, т.е. отсутствуют препятствия, отражения и возможность передачи сигнала по нескольким путям.

Реалистичность моделируемых сценариев обеспечивалась применением модели среды распространения радиосигнала в свободном пространстве (формула Г. Фрииса), встроенной в сетевой симулятор NS-2 [173, 207].

&r _ Pt Pr Я2 (3 7)

Pt~ (4 s ")2 L ( . )

где Рг, - мощность приемной и передающей антенн, Gr, Gt - коэффициенты усиления приемной и передающей антенн, - расстояние между передающей и приемной антеннами, - длина волны, - потери распространения в свободном пространстве, по умолчанию в симуляторе NS-2 значение .

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

коэффициента затухания среды передачи и расстояния между передающей и принимаемой антеннами.

Дальности связи по радиоканалу при которой обеспечивается уверенный прием и передача данных составляет около 600 м.

3.1.6 Модель беспроводного модуля

На сегодняшний день при развертывании самоорганизующихся сетей БПЛА распространены три семейства стандартов беспроводной связи: IEEE 802.11, IEEE 802.15.4 и IEEE 802.16 [59, 34, 208]. Однако наиболее широкое применение получило стандартов IEEE 802.11, способное обеспечить высокую скорость передачи данных, энергоэффективность, относительную простоту установления соединения и подключения к сети, наличие механизмов защиты данных и обеспечения гарантированного качества обслуживания (QoS) для определенного типа трафика.

В рамках данной работы был выбран стандарт Wi-Fi (IEEE 802.11g). Несмотря на то, что он вытесняется более современными и высокоскоростными версиями 802.11n и 802.11ac [209], данный стандарт по-прежнему находит свое активное применение при проведении натурных экспериментов и имитационного моделирования в FANET [210, 211]. Параметры стандарта IEEE 802.11g, использованные при моделировании, представлены в таблице 3.2.

При моделировании стандарта IEEE 802.11g на MAC уровне используется метод случайного доступа (англ. Carrier Sense Multiple Access With Collision Avoidance, CSMA/CA) совместно с базовым протоколом канального уровня DCF (Distributed Coordination Function) без применения дополнительного механизма отправки сообщений RTS/CTS (англ. Request To Send/Clear To Send) [212, 213, 214]. В качестве метода модуляции сигнала на физическом уровне используется ERP-OFDM (англ. Extended Rate Physical - Orthogonal Frequency Division Multiplexing) [215].

Параметр Значение

PHY-заголовок 20 мкс

MAC-заголовок 28 байт

RTS 20 байт

CTS 14 байт

ACK 14 байт

SIFS 10 мкс

DIFS 28 мкс

PIFS 19 мкс

Временной интервал (тайм слот, }) 9 мкс

Количество повторных попыток передачи пакета, m 6

Минимальный размер окна конкуренции, 3min 15

Максимальный размер окна конкуренции, Зпах 1023