eng
TS_pub
technospheramag
technospheramag
ТЕХНОСФЕРА_РИЦ
Выпуск #6/2023
Навар Мохаммад, Л.И.Воронова, В.И.Воронов
МОДЕЛИРОВАНИЕ МАРШРУТИЗАЦИИ В КЛАСТЕРИЗОВАННОМ РОЕ БПЛА С ИСПОЛЬЗОВАНИЕМ ГЕНЕТИЧЕСКОГО АЛГОРИТМА
МОДЕЛИРОВАНИЕ МАРШРУТИЗАЦИИ В КЛАСТЕРИЗОВАННОМ РОЕ БПЛА С ИСПОЛЬЗОВАНИЕМ ГЕНЕТИЧЕСКОГО АЛГОРИТМА
Просмотры: 1058
DOI: 10.22184/2070-8963.2023.114.6.46.52
Исследование посвящено проблеме маршрутизации данных, полученных от наземной беспроводной сенсорной сети, через рой беспилотных летательных аппаратов (БПЛА) на базовую станцию. Использованы генетические методы для реализации быстрого и надежного статического и динамического алгоритма маршрутизации. Алгоритм маршрутизации данных обеспечивает моделирование в трехмерной среде роя БПЛА, предварительно кластеризованного с использованием алгоритма K-средних в среде Anaconda. В качестве показателей эффективности используются зона покрытия, радиовидимость и местоположение БПЛА.
Исследование посвящено проблеме маршрутизации данных, полученных от наземной беспроводной сенсорной сети, через рой беспилотных летательных аппаратов (БПЛА) на базовую станцию. Использованы генетические методы для реализации быстрого и надежного статического и динамического алгоритма маршрутизации. Алгоритм маршрутизации данных обеспечивает моделирование в трехмерной среде роя БПЛА, предварительно кластеризованного с использованием алгоритма K-средних в среде Anaconda. В качестве показателей эффективности используются зона покрытия, радиовидимость и местоположение БПЛА.
Теги: drone genetic algorithm k-means algorithm routing terrestrial wireless sensor network uav uav swarm алгоритм k-средних бпла генетический алгоритм дрон маршрутизация наземная беспроводная сенсорная сеть рой бпла
МОДЕЛИРОВАНИЕ
МАРШРУТИЗАЦИИ
В КЛАСТЕРИЗОВАННОМ РОЕ БПЛА
с использованием генетического алгоритма
Навар Мохаммад, аспирант МТУСИ / 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).
МАРШРУТИЗАЦИИ
В КЛАСТЕРИЗОВАННОМ РОЕ БПЛА
с использованием генетического алгоритма
Навар Мохаммад, аспирант МТУСИ / 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).
Отзывы читателей
