DOI: 10.22184/2070-8963.2023.114.6.46.52

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

sitemap
Наш сайт использует cookies. Продолжая просмотр, вы даёте согласие на обработку персональных данных и соглашаетесь с нашей Политикой Конфиденциальности
Согласен
Поиск:

Вход
Архив журнала
Журналы
Медиаданные
Редакционная политика
Реклама
Авторам
Контакты
TS_pub
technospheramag
technospheramag
ТЕХНОСФЕРА_РИЦ
© 2001-2025
РИЦ Техносфера
Все права защищены
Тел. +7 (495) 234-0110
Оферта

Яндекс.Метрика
R&W
 
 
Вход:

Ваш e-mail:
Пароль:
 
Регистрация
Забыли пароль?
Книги по связи
Другие серии книг:
Мир связи
Библиотека Института стратегий развития
Мир квантовых технологий
Мир математики
Мир физики и техники
Мир биологии и медицины
Мир химии
Мир наук о Земле
Мир материалов и технологий
Мир электроники
Мир программирования
Мир строительства
Мир цифровой обработки
Мир экономики
Мир дизайна
Мир увлечений
Мир робототехники и мехатроники
Для кофейников
Мир радиоэлектроники
Библиотечка «КВАНТ»
Умный дом
Мировые бренды
Вне серий
Библиотека климатехника
Мир транспорта
Мир фотоники
Мир станкостроения
Мир метрологии
Мир энергетики
Книги, изданные при поддержке РФФИ
Выпуск #6/2023
Навар Мохаммад, Л.И.Воронова, В.И.Воронов
МОДЕЛИРОВАНИЕ МАРШРУТИЗАЦИИ В КЛАСТЕРИЗОВАННОМ РОЕ БПЛА С ИСПОЛЬЗОВАНИЕМ ГЕНЕТИЧЕСКОГО АЛГОРИТМА
Просмотры: 926
DOI: 10.22184/2070-8963.2023.114.6.46.52

Исследование посвящено проблеме маршрутизации данных, полученных от наземной беспроводной сенсорной сети, через рой беспилотных летательных аппаратов (БПЛА) на базовую станцию. Использованы генетические методы для реализации быстрого и надежного статического и динамического алгоритма маршрутизации. Алгоритм маршрутизации данных обеспечивает моделирование в трехмерной среде роя БПЛА, предварительно кластеризованного с использованием алгоритма K-средних в среде Anaconda. В качестве показателей эффективности используются зона покрытия, радио­видимость и местоположение БПЛА.
МОДЕЛИРОВАНИЕ
МАРШРУТИЗАЦИИ
В КЛАСТЕРИЗОВАННОМ РОЕ БПЛА
с использованием генетического алгоритма

Навар Мохаммад, аспирант МТУСИ / nawar.info@gmail.com,
Л.И.Воронова, д.ф.-м.н., заведующая кафедрой МТУСИ / voronova.lilia@ya.ru,
В.И.Воронов, к.т.н., доцент МТУСИ / vorvi@mail.ru
УДК 621.391, DOI: 10.22184/2070-8963.2023.114.6.46.52

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

Введение
Рой БПЛА является типом летающей Ad-Hoc-сети (англ. Flying Ad-Hoc Network − FANET), состоящей из летающих узлов, таких как дроны, или БПЛА [1, 2]. Сеть роя БПЛА характеризуется динамической топологией, ограниченными дальностью связи и пропускной способностью. Информационная связь в рое дронов осуществляется беспроводным способом.
Маршрутизация в составе роя БПЛА относится к процессу определения оптимального маршрута для передачи данных между дронами в рое. Эффективная маршрутизация важна для успешной работы роя, позволяя БПЛА в рое общаться и передавать данные между собой [3].
Динамический характер топологии сети, связанный с постоянным движением дронов в рое и ограниченностью используемых ресурсов, таких как зона покрытия отдельного узла, делает рассматриваемую маршрутизацию сложной задачей. Проблеме маршрутизации данных в рое беспилотных летательных аппаратов и беспроводных сенсорных сетей посвящено много исследований, проведенных на кафедре ИСУиА в МТУСИ [4, 5, 6, 7, 8] и в других организациях [9, 10, 11, 12, 13, 14].
Концептуальная модель
В горной местности, не входящей в зону покрытия БПЛА, на площади 25 кв. км распределены датчики наземной сенсорной сети, считывающие данные, связанные с характеристиками погоды и почвы, такими как температура воздуха, атмосферное давление, влажность, интенсивность света, рН почвы, влажность почвы, а также обнаруживающие углекислый газ и дым. Информация, собранная в наземной сети, передается через источник/базовую станцию к рою БПЛА, в котором происходит маршрутизация и дальнейшая передача данных к шлюзу/базовой станции.
Для покрытия территории 5 × 5 кв. км случайным образом распределяется 25 БПЛА на высоте от 500 до 600 м, при этом БПЛА перемещаются в фиксированных непересекающихся областях размером 1000 × 1000 × 100 м. Каждый БПЛА оснащен блоком GPS (Global Positioning System) для определения своего местоположения во время полета и имеет радиус радиовидимости 2000 м [17].
В табл.1 приведена информация о дальности действия и цене БПЛА нескольких типов. Анализ данных таблицы показывает, что лучшим выбором будет дрон JJRC X12 Pro Aurora, поскольку он может подниматься на высоту 500 м и его цена приемлема.
Для передачи данных между сенсорами наземной сети на расстояние до 100 м используется технология стандарта IEEE 802.14 (ZigBee). Этот стандарт характеризуется низким энергопотреблением и высокой надежностью.
Для передачи данных между роем БПЛА и базовыми станциями (источником и шлюзом) на расстояние до 5 км применяется технология стандарта IEEE 802.16e (WiMax).
Математическая модель
Имеется m БПЛА с координатами (Xбпла, Yбпла, Zбпла), распределенных в заданной области. Выполняется кластеризация с использованием алгоритма K-средних, в результате формируется N кластеров, в каждом из которых определяется головной кластерный узел (ГКУ) БПЛА с координатами (Xгку, Yгку, Zгку). В полученном массиве ГКУ необходимо определить последовательность БПЛА, с помощью которых будет формироваться оптимальный путь для передачи данных от источника с координатами (Xисточник, Yисточник, Zисточник) до шлюза с координатами (Xшлюз, Yшлюз, Zшлюз) c использованием генетического алгоритма [23, 24]. Первоначально, для нахождения кратчайшего пути должно быть сформировано потенциальное решение "хромосома", на основании которого строится начальная популяция, содержащая все возможные пути/хромосомы из ГКУ БПЛА.
Метод К-средних
Метод К-средних основан на вычислении евклидовых расстояний между парами БПЛА и формированием кластеров, с последующим определением ГКУ каждого кластера.
В качестве меры близости используется евклидово расстояние:
P(x, y) = |x–y| = √(xp – yp)2, p = 1 … n, x, y ∈ Rn,
(x(1), x(2),… x(i),…, x(m)), x(i) ∈ Rn. (1)
Алгоритм K-средних реализуется следующим образом:
инициализировать K-центры кластеров;
повторить
{For i = 1 to m
c(i) = индекс (от 1 до K) центра кластера,
ближайшего к x(i).
For k = 1 to K
µk = среднее количество точек, отнесенных к кластеру K};
определить значение функции стоимости J как сумму квадратов расстояний между текущей точкой и ближайшими центрами кластеров. Минимизация функции стоимости выполняется путем поиска нового набора центров кластеров на каждой итерации:
J(c(1),…, c(m), µ1, µK)= 1/m ∑ |x(i)- µc(i) | 2, i=1…m; (2)
выбрать кластеризацию с наименьшей стои­мостью J;
алгоритм завершается, когда центры кластеров не изменяются.
Генетический алгоритм
Для работы с генетическим алгоритмом необходимо учитывать три матрицы: радиовидимости, расстояний, стоимости.
Матрица радиовидимости P должна иметь размерность (N x N), где N – количество головных кластерных узлов (ГКУ), и может быть представлена в виде:
, (3)
где Pij = 1 означает, что между двумя узлами (i и j) есть соединение,
Pij = 0 означает, что соединения нет.
Матрица расстояний также должна иметь размерность (N x N), которая рассчитывается с использованием евклидова расстояния по формуле (1). Эта матрица может быть представлена следующим образом:
, (4)
где dij − расстояние между узлом i и соответствующим узлом j.
Для отбора наилучших маршрутов в методе используется функция пригодности G, которая определяет способность маршрута конкурировать с другими маршрутами. Это так называемая "фитнес-оценка" или "стоимость" каждого маршрута. Вероятность того, что маршрут будет выбран для размножения, зависит от его фитнес-оценки.
Функцию пригодности G можно построить на основе матрицы стоимости F, которая яв­ляется произведением матрицы радиовидимости на матрицу расстояний. F содержит ненулевые значения только в тех ячейках, где записаны расстояния между узлами (ГКУ БПЛА), имеющи­ми связь. Матрица стоимости F может быть представлена следующим образом:
F = D x P. (5)
Поскольку лучший путь в популяции выби­рается по наименьшему значению функции пригодности, то используется классический прием увеличения стоимости для "негодных" маршрутов. К таким относятся маршруты/хромосомы, включающие нулевые элементы, то есть такие, где между узлами i, j нет связи или это ячейка с индексами i, j. В этом случае в матрице стои­мости применяют штрафы с целью увеличения значений функций пригодности. В итоге матрица стоимости может быть представлена следующим образом:
F = Fij, если Pij ≠ 0,
F = Fij+штраф, если Pij = 0, (6)
F = 0, в случае i = j,
где штраф применяется к любым двум ГКУ БПЛА, которые не имеют связи или связаны "сами с собой", и должен быть большим.
Кодирование хромосомы
Код хромосомы представляют в виде последовательности генов, где каждый ген − это целое число, которое указывает на ГКУ БПЛА, участ­вующий в построении пути. Таким образом, длина последовательности – это количество ГКУ БПЛА, составляющих кратчайший путь от источника до шлюза.
На рис.1 для примера показан путь, сформированный при маршрутизации. В этом примере значения гена в позициях от 0 до 1 – это ГКУ БПЛА, формирующие путь от источника в позиции 0 (БПЛА 15) до шлюза в позиции 9 (БПЛА 16) [15].
В зависимости от набора и позиции генов в хромосоме устанавливается маршрутизация в сети БПЛА. С помощью такого представления можно генерировать различные маршруты случайным образом для начальной популяции путем выбора нескольких возможных путей между источником и шлюзом. Количество путей, которые можно получить перебором, очень велико, и поэтому для выбора кратчайшего пути за короткое время предлагается использовать генетический алгоритм [16].
В данной работе используется турнирный метод для отбора родительских особей при формировании новых путей, который включает скрещивания, мутации и отбор наилучших путей с помощью функции пригодности.
Скрещивания
Для улучшения качества отбора кратчайшего пути используется скрещивание для формирования нового пути. В этом случае у каждой пары маршрутов случайным образом выбирается одна точка скрещивания (фактор одноточечного скрещивания), в которой между ними происходит обмен генами. Повторяющиеся гены удаляются.
Мутации
Этот процесс используется для изменения значения гена в хромосоме на случайно выбранное значение от 0 до N-1, где N – количество ГКУ БПЛА, образующих путь. Мутация позволяет включить новый ГКУ БПЛА в маршрут, а другой ГКУ БПЛА удалить с пути.
Функция пригодности
Функция пригодности G – это критерий, определяющий качество сформированного пути. В этой работе G(m) зависит от радиовидимости каждого ГКУ БПЛА и его зоны покрытия относительно остальных ГКУ БПЛА, а также расстояния между каждыми двумя узлами ГКУ БПЛА.
G(m) = ∑ Fij, (7)
i, j узлы ∈ маршруту m,
где G(m) – пригодность маршрута m,
Fij – стоимость ячеек между узлом i и узлом j.
Эксперименты
Авторами проведено исследование маршрутизации в рое 25 БПЛА, случайно распределенных в трехмерном пространстве заданного объема с ограничениями, описанными в статье [5].
Эксперименты проводились в два последовательных момента времени t0, t1, во время которых БПЛА изменили свое местоположение. В результате кластеризации роя БПЛА с помощью алгоритма K-средних в каждый момент времени формируется массив из 10 кластеров, содержащий информацию о номерах и координатах (x, y, z) БПЛА, являющихся ГКУ.
На основании этой информации рассчитывается матрица расстояний между БПЛА, являющихся центрами кластеров (ГКУ), содержащая 40 неповторяющихся значений.
Затем рассчитывается матрица стоимости, используемая в функции пригодности после применения штрафа, указанного в формуле (6), где штраф составляет 100.
Для нахождения кратчайшего пути между источником и шлюзом применен генетический алгоритм, работающий в течение 100 поколений, а используемая начальная популяция состоит из 20 хромосом. Поскольку рабочая среда является динамичной и изменяющейся, формирование хромосом вручную нецелесообразно. Авторами разработана программа, формирующая хромосомы автоматически. На рис.2. приведены последовательности генов в каждой из 20 хромосом, а также рассчитана функция пригодности для каждой хромосомы в начальных популяциях в момент времени t0 и t1.
В процессе работы алгоритма в каждом поколении получены функции пригодности маршрутов и на их основе найдены лучшие хромосомы в популяциях. В результате работы алгоритма в момент времени t0 получена лучшая хромосома/кратчайший путь {1, 5, 4, 3}, которая состоит из последовательности индексов ГКУ БПЛА, составляющих путь, то есть 1 − индекс ГКУ БПЛА, который равен UAV 15, и 5 − индекс БПЛА ГКУ, который равен UAV 7 и т.д. UAV15 – это ближайший ГКУ к источнику, а UAV16 – ближайший ГКУ к шлюзу. Также в момент времени t1 получена лучшая хромосома/кратчайший путь {7, 4, 0, 6} (см. рис.3).
Маршрут интегрированного пакета с данными, полученными от наземной сети, начинается от источника (0, 0, 0), который передает данные в ближайший кластер главному узлу (UAV15 в момент времени t0 и t1) и последовательно до узла (UAV16 в момент времени t0 и UAV19 в момент времени t1), который передает данные на шлюз (5, 5, 0), как показано на рис.4.
На рис.5 можно наблюдать изменение эффективности функции пригодности популяции, с довольно быстрым уменьшением при изменении поколений и выходом на плато фиксированного значения, которое не меняется и при котором формируется кратчайший путь в момент времени t0 и t1.
Заключение
С помощью методов интеллектуального анализа проведено компьютерное моделирование маршрутизации данных, полученных от наземной беспроводной сенсорной сети, через рой БПЛА на базовую станцию. По результатам кластеризации с помощью генетического алгоритма идентифицированы БПЛА, играющие роль главных кластерных узлов, участвующих в процессе формирования кратчайшего пути при маршрутизации в рое дронов.
В качестве показателей эффективности использовались зона покрытия, радиус радиовидимости и местонахождение БПЛА в процессе кластеризации и маршрутизации. Путем расчета эффективности функции пригодности для начальной популяции в два разных периода времени t0 и t1 обнаружено, что поиск или формирование кратчайшего пути выполнено менее чем за 100 поколений.
На основе полученных результатов можно сделать вывод о хорошей применимости генетического алгоритма для решения задачи маршрутизации в меняющейся динамической среде.
ЛИТЕРАТУРА
Аблец А.А., Стребков А.Н., Завгородняя Е.В. Опыт создания роя БПЛА в вооруженных силах иностранных государств // Военная мысль. 2022. № 6. С. 137−146.
Киричек Р.В. Разработка и исследование комплекса моделей и методов для летающих сенсорных сетей: дисс. ... докт. техн. наук: 05.12.13. Самара, 2018. 316 c.
Леонов А.В. Разработка адаптивного алгоритма маршрутизации на основе роевого интеллекта пчелиной колонии для самоорганизующихся сетей беспилотных летательных аппаратов: дисс. ... канд. техн. наук: 05.12.13. Омск, 2020. 186 c.
Mohammad N., Voronova L.I. and Voronov V.I. Development of a simulation model for using a swarm of UAVs in agriculture // Proc. SPIE 12296, International Conference on Remote Sensing of the Earth: Geoinformatics, Cartography, Ecology and Agriculture (RSE 2022). 2022. PP. 174−180.
Воронова Л.И., Мохаммад Н. Беспроводные Сенсорные Сети Как Основа Интернета Вещей // Сборник материалов XI Молодежного научного форума МТУСИ, 2020. С. 155−161.
Мохаммад Н., Воронова Л.И. Моделирование кластеризации беспроводной сенсорной сети нейросетевым конструктивным методом // Системы синхронизации, формирования и обработки сигналов. 2021. № 12 (3). С. 4−19.
Voronova L.I. et al. Modeling the Clustering of Wireless Sensor Networks Using the K-means Method // 2021 International Conference on Quality Management, Transport and Information Security, Information Technologies (IT&QM&IS). PP. 740−745.
Мохаммад Н., Воронова Л.И., Воронов В.И. Разработка имитационной модели использования роя беспилотных летательных аппаратов в сельском хозяйстве // Наукоемкие технологии в космических исследованиях Земли. 2022. Т. 14. № 3. С. 55−61.
Wei Xing, Hua Yang and Wentao Huang. A Genetic-Algorithm-Based Optimization Routing for FANETs // Frontiers in Neurorobotics. 2021. No. 15. P. 81.
Федина А.А., Нургалиев А.И., Скворцовая Д.А. Сравнение результатов применения различных эволюционных алгоритмов для решения задачи оптимизации маршрута беспилотных аппаратов // Компьютерные исследования и моделирование. 2022. № 1. С. 45–62.
Иванов С.В. Методика построения субоптимальных маршрутов для группы беспилотных летательных аппаратов на основе биоинспирированных алгоритмов при наличии препятствий // Системы управления, связи и безопасности. 2022. № 2. С. 1−23.
Rajab A. Genetic Algorithm-Based Multi-Hop Routing to Improve the Lifetime of Wireless Sensor Networks // Engineering, Technology & Applied Science Research. 2021. Vol. 11. No. 6. PP. 7770−7775.
Хазиев Н.Н., Волков В.В., Зятинин А.А., Чекалина Е.А. Оптимизация алгоритмов гибкой маршрутизации в сети передачи данных БПЛА // Информационная безопасность регионов России (ИБРР-2021): Материалы XII Санкт-Петербургской межрегиональной конференции. СПб.: Региональная общественная организация "Санкт-Петербургское Общество информатики, вычислительной техники, систем связи и управления", 2021. С. 203−205.
Ефремова А.Е., Паращинец А.В. Протокол маршрутизации RASeR для беспроводных самоорганизующихся сенсорных сетей // Доклады Томского государственного университета систем управления и радиоэлектроники. 2020. Т. 23. № 1. С. 40−46.
Кудр Л.А., Скобцов Ю.А. Генетический алгоритм маршрутизации беспроводных сенсорных сетей // ПИ. Т. 2014. № 1. С. 85−91.
Chakraborty A., Mitra S.K., Naskar M.K. A genetic algorithm inspired routing protocol for wireless sensor networks // International Journal of Computer Intelligence − Theory and Practice. 2011. No. 6.
Лучшие квадрокоптеры с большим радиу­сом действия и камерой. [Электронный ресурс]. URL: https://mirquadrocopterov.ru/blog/top-luchshih/luchshie-kvadrokoptery-s-bolshim-radiusom-dejstviya-i-kameroj (дата обращения: 23.01.2023).
 
 Отзывы читателей
Разработка: студия Green Art