面向无人机辅助物联网数据采集的双层优化算法

doi:10.3778/j.issn.1002-8331.2503-0342

摘要/Abstract

摘要： 针对基站遭受损坏阻碍物联网设备数据有效传输的问题，提出了一种无人机（unmanned aerial vehicle，UAV）充当移动基站辅助物联网数据采集的方法。以无人机在执行数据收集任务时的最小能耗为优化目标，结合无人机的部署策略与飞行轨迹规划，构建无人机辅助物联网数据采集的数学模型。设计一种双层优化算法来规划无人机的部署位置与飞行轨迹，旨在确保无人机能够高效完成数据收集任务的同时，实现能耗的最小化。在算法的上层部分，利用改进的蒲公英算法来优化无人机的落脚点数量与具体位置。通过一种新颖的编码策略，使每个蒲公英个体代表无人机的一个潜在落脚点，则整个蒲公英种群被视为一个完整的无人机部署方案。同时提出了两种突变策略，即Replace和Remove突变策略，前者用来更新无人机的落脚点位置，后者用来调整无人机落脚点的数量。基于算法上层得到的无人机部署结果（即落脚点的数量与位置），在算法的下层部分将无人机的飞行轨迹规划问题转化为经典的旅行商问题（traveling salesman problem，TSP）。利用迭代贪婪算法来搜索最优的无人机飞行轨迹。最后以10个实例验证双层优化方法的有效性。

关键词: 无人机（UAV）, 物联网, 数据收集, 无人机部署, 飞行轨迹规划

Abstract: Aiming at the problem that the damaged base station hinders the effective transmission of Internet of things (IoT) device data, a method based on unmanned aerial vehicle (UAV) acting as a mobile base station to assist IoT data collection is proposed. Specifically, the mathematical model of UAV-assisted IoT data collection is constructed by taking the minimum energy consumption of the UAV in performing the data collection task as the optimization objective, and combining the deployment strategy and flight trajectory planning of the UAV. A bilevel optimization algorithm (BOA) is designed to finely plan the deployment and flight trajectory of the UAV, aiming to ensure that the UAV can efficiently complete the data collection task while minimizing energy consumption. In the upper-level, an improved dandelion algorithm (IDA) is used to optimize the number of footholds and the locations of the UAV. To this end, a novel coding strategy is designed, in which each individual in dandelion algorithm represents a potential foothold for a UAV, while the entire dandelion population is considered as a complete UAV deployment. In addition, two mutation strategies are proposed, namely Replace and Remove mutation strategies. The former is used to update the locations of the UAV footholds, and the latter is used to adjust the number of UAV footholds. Based on the UAV deployment results (i.e., the number and location of footholds) obtained from the upper-level, the lower-level transforms the UAV trajectory planning problem into the classical traveling salesman problem (TSP). An iterative greedy algorithm (IGA) is used to search for the optimal UAV flight trajectory. Finally, 10 instances are used to verify the effectiveness of the proposed bilevel optimization method.

Key words: unmanned aerial vehicle (UAV), Internet of things, data collection, UAV deployment, flight trajectory planning

韩守飞, 刘晓静. 面向无人机辅助物联网数据采集的双层优化算法[J]. 计算机工程与应用, 2025, 61(16): 292-304.

HAN Shoufei, LIU Xiaojing. Bilevel Optimization Algorithm for Unmanned Aerial Vehicle-Assisted Data Collection in Internet of Things[J]. Computer Engineering and Applications, 2025, 61(16): 292-304.

参考文献

[1] 钱志鸿, 王义君. 物联网技术与应用研究[J]. 电子学报, 2012, 40(5): 1023-1029.
QIAN Z H, WANG Y J. IoT technology and application[J]. Acta Electronica Sinica, 2012, 40(5): 1023-1029.
[2] 王基策, 李意莲, 贾岩, 等. 智能家居安全综述[J]. 计算机研究与发展, 2018, 55(10): 2111-2124.
WANG J C, LI Y L, JIA Y, et al. Survey of smart home security[J]. Journal of Computer Research and Development, 2018, 55(10): 2111-2124.
[3] 李钦豪, 张勇军, 陈佳琦, 等. 泛在电力物联网发展形态与挑战[J]. 电力系统自动化, 2020, 44(1): 13-22.
LI Q H, ZHANG Y J, CHEN J Q, et al. Development patterns and challenges of ubiquitous power Internet of things[J]. Automation of Electric Power Systems, 2020, 44(1): 13-22.
[4] 朱茂盛, 王宝晗, 康曼聪, 等. 智能物联网技术赋能算网一体数据库的效能优化[J]. 计算机研究与发展, 2024, 61(11): 2835-2845.
ZHU M S, WANG B H, KANG M C, et al. Efficiency optimization for computer network integrated database empowered by artificial intelligence of things technology[J]. Journal of Computer Research and Development, 2024, 61(11): 2835-2845.
[5] 罗小娟, 胡鹏昊. 基于深度学习的农场虫情检测算法研究及实现[J]. 华东理工大学学报(自然科学版), 2024, 50(5): 732-739.
LUO X J, HU P H. Research and implementation of farm insect detection algorithm based on deep learning[J]. Journal of East China University of Science and Technology (Natural Science Edition), 2024, 50(5): 732-739.
[6] 曹慧娟, 余庚花, 陈志刚. 协作处理任务的多无人机辅助移动边缘计算[J]. 计算机工程与应用, 2024, 60(4): 298-305.
CAO H J, YU G H, CHEN Z G. Cooperative task processing in multi-UAV assisted mobile edge computing[J]. Computer Engineering and Applications, 2024, 60(4): 298-305.
[7] 黄泽丰, 李涛. RISE-D3QN驱动的多无人机数据采集路径规划[J]. 计算机工程与应用, 2024, 60(20): 328-338.
HUANG Z F, LI T. RISE-D3QN-based path planning for multi-UAV data collection[J]. Computer Engineering and Applications, 2024, 60(20): 328-338.
[8] 朱江, 肖津. 考虑无人机飞行时间的能耗与数据量联合优化[J]. 计算机工程与应用, 2024, 60(1): 271-280.
ZHU J, XIAO J. Joint optimization of energy consumption and data volume based on UAV flight time[J]. Computer Engineering and Applications, 2024, 60(1): 271-280.
[9] HUANG P Q, WANG Y, WANG K Z, et al. Differential evolution with a variable population size for deployment optimization in a UAV-assisted IoT data collection system[J]. IEEE Transactions on Emerging Topics in Computational Intelligence, 2020, 4(3): 324-335.
[10] ZHANG X, CHANG Z, H?M?L?INEN T, et al. AoI-energy tradeoff for data collection in UAV-assisted wireless networks[J]. IEEE Transactions on Communications, 2024, 72(3): 1849-1861.
[11] WU Q Q, LIU Q, ZHU W L, et al. Energy efficient UAV-assisted IoT data collection: a graph-based deep reinforcement learning approach[J]. IEEE Transactions on Network and Service Management, 2024, 21(6): 6082-6094.
[12] WANG Y, GAO Z, ZHANG J, et al. Trajectory design for UAV-based Internet of things data collection: a deep reinforcement learning approach[J]. IEEE Internet of Things Journal, 2022, 9(5): 3899-3912.
[13] ZHANG H Y, LI B, RONG Y, et al. Joint optimization of transmit power and trajectory for UAV-enabled data collection with dynamic constraints[J]. IEEE Transactions on Communications, 2025. DOI:10.1109/TCOMM.2025.3543221.
[14] ZHANG Y Y, HUANG Y, HUANG C, et al. Joint optimization of deployment and flight planning of multi-UAVs for long-distance data collection from large-scale IoT devices[J]. IEEE Internet of Things Journal, 2024, 11(1): 791-804.
[15] DONIPATI M, JAISWAL A, HAZRA A, et al. Optimizing UAV-based data collection in IoT networks with dynamic service time and buffer-aware trajectory planning[J]. IEEE Transactions on Network and Service Management, 2025, 22(2): 1450-1460.
[16] PAN J N, LI Y, CHAI R, et al. Multiobjective trajectory planning for UAV-assisted IoT networks based on DRL approach[J]. IEEE Internet of Things Journal, 2025, 12(11): 15840-15852.
[17] GUO Y Y, XU G, ZHANG Z C, et al. Resource block-based co-design of trajectory and communication in UAV-assisted data collection networks[J]. IEEE Transactions on Intelligent Transportation Systems, 2024, 25(12): 21585-21596.
[18] CAI Y X, WEI Z Q, LI R D, et al. Joint trajectory and resource allocation design for energy-efficient secure UAV communication systems[J]. IEEE Transactions on Communications, 2020, 68(7): 4536-4553.
[19] WANG L Y, ZHANG H X, GUO S S, et al. Deployment and association of multiple UAVs in UAV-assisted cellular networks with the knowledge of statistical user position[J]. IEEE Transactions on Wireless Communications, 2022, 21(8): 6553-6567.
[20] MOZAFFARI M, SAAD W, BENNIS M, et al. Mobile unmanned aerial vehicles (UAVs) for energy-efficient Internet of things communications[J]. IEEE Transactions on Wireless Communications, 2017, 16(11): 7574-7589.
[21] LI X G, HAN S F, ZHAO L, et al. New dandelion algorithm optimizes extreme learning machine for biomedical classification problems[J]. Computational Intelligence and Neuroscience, 2017(1): 4523754.
[22] HAN S F, ZHU K, WANG R. Improvement of evolution process of dandelion algorithm with extreme learning machine for global optimization problems[J]. Expert Systems with Applications, 2021, 163: 113803.
[23] HAN S F, ZHU K. Fusion with distance-aware selection strategy for dandelion algorithm[J]. Knowledge-Based Systems, 2020, 205: 106282.
[24] ZHU H H, LIU G J, ZHOU M C, et al. Dandelion algorithm with probability-based mutation[J]. IEEE Access, 2019, 7: 97974-97985.
[25] HAN S F, ZHU K, ZHOU M C. Competition-driven dandelion algorithms with historical information feedback[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2022, 52(2): 966-979.
[26] LIU X J, QIN X L. A probability-based core dandelion guided dandelion algorithm and application to traffic flow prediction[J]. Engineering Applications of Artificial Intelligence, 2020, 96: 103922.
[27] ZHU H H, LIU G J, ZHOU M C, et al. Optimizing weighted extreme learning machines for imbalanced classification and application to credit card fraud detection[J]. Neurocomputing, 2020, 407: 50-62.
[28] GAO S C, YU Y, WANG Y R, et al. Chaotic local search-based differential evolution algorithms for optimization[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2021, 51(6): 3954-3967.
[29] DONG W Y, ZHOU M C. A supervised learning and control method to improve particle swarm optimization algorithms[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2017, 47(7): 1135-1148.
[30] YU Y, LEI Z Y, WANG Y R, et al. Improving dendritic neuron model with dynamic scale-free network-based differential evolution[J]. IEEE/CAA Journal of Automatica Sinica, 2022, 9(1): 99-110.
[31] ZHANG Y H, GONG Y J, GU T L, et al. Flexible genetic algorithm: a simple and generic approach to node placement problems[J]. Applied Soft Computing, 2017, 52: 457-470.
[32] AB WAHAB M N, NAZIR A, KHALIL A, et al. Improved genetic algorithm for mobile robot path planning in static environments[J]. Expert Systems with Applications, 2024, 249: 123762.
[33] OSABA E, CARBALLEDO R, LOPEZ-GARCIA P, et al. Comparison between golden ball meta-heuristic, evolutionary simulated annealing and tabu search for the traveling salesman problem[C]//Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion. New York: ACM, 2016: 1469-1470.
[34] GAO W. Modified ant colony optimization with improved tour construction and pheromone updating strategies for traveling salesman problem[J]. Soft Computing, 2021, 25(4): 3263-3289.
[35] WANG L J, CAI R Y, LIN M, et al. Enhanced list-based simulated annealing algorithm for large?scale traveling salesman problem[J]. IEEE Access, 2019, 7: 144366-144380.
[36] AL-BETAR M A, AWADALLAH M A, BRAIK M S, et al. Elk herd optimizer: a novel nature-inspired metaheuristic algorithm[J]. Artificial Intelligence Review, 2024, 57(3): 48.
[37] BRAIK M, AL-HIARY H, ALZOUBI H, et al. Tornado optimizer with Coriolis force: a novel bio-inspired meta-heuristic algorithm for solving engineering problems[J]. Artificial Intelligence Review, 2025, 58(4): 123.