物联网数据收集中基于负载均衡的无人机-车联合轨迹规划

doi:10.11959/j.issn.1000-436x.2024005

摘要/Abstract

摘要：

为了提升大规模物联网数据收集的效率，提出了一种基于负载均衡区域划分的多无人机-车联合轨迹规划算法，其中，无人机作为空中基站收集物联网设备的数据，地面无人车作为移动电池更换站以弥补无人机能量的不足。为了缩短整体任务完成时间，优化目标为最小化所有无人机-车中最长的任务完成时间，将该问题建模为多站点车辆路由问题的一个变种，并从负载均衡的角度对其进行求解。具体来说，首先通过负载均衡区域划分算法将物联网设备分配到无人机-车的服务区，在此基础上，多站点无人机-车的轨迹规划问题退化为多个独立的单站点单组无人机-车的轨迹规划问题，进而设计联合轨迹规划策略优化各个服务区中的路径。数值结果验证了所提算法在任务完成时间和负载均衡度方面优于对比算法。

关键词: 无人机, 数据收集, 轨迹规划, 区域划分, 负载均衡

Abstract:

To improve the efficiency of large-scale Internet of things (IoT) data collection, a coordinated trajectory planning algorithm for multiple aerial and ground vehicles based on load balancing region partitioning was proposed, where unmanned aerial vehicles (UAVs) acting as aerial base stations were dispatched to gather data from IoT devices and unmanned ground vehicles (UGVs) acting as mobile battery swap stations were used to compensate for the shortage of UAV’s energy.Aiming at shortening the mission completion time, the optimization task was to minimize the longest mission time among a fleet of UAV-UGVs, which was formulated as a variant of min-max multi-depot vehicle routing problem and solved from the load-balancing perspective.Specifically, the IoT devices were assigned to the UAV-UGVs’ service zones by a load-balancing region partition algorithm, based on which the trajectory planning problem of multiple UAV and UGV was reduced to several independent route planning problems for each UAV-UGV pair.Then, a cooperative trajectory planning strategy was developed to optimize the route in each service zone.Numerical results validate that the proposed algorithm outperforms the compared algorithms in terms of mission completion time and balancing degree.

Key words: unmanned aerial vehicle, data collection, trajectory planning, region partitioning, load balancing

中图分类号:

TN92

朱雨超, 王少尉. 物联网数据收集中基于负载均衡的无人机-车联合轨迹规划[J]. 通信学报, 2024, 45(1): 41-53.

Yuchao ZHU, Shaowei WANG. Coordinated UAV-UGV trajectory planning based on load balancing in IoT data collection[J]. Journal on Communications, 2024, 45(1): 41-53.

图/表 9

图1

表1

图2

图3

表2

相应的服务区任务完成时间和负载不平衡程度"

方法	均匀分布						非均匀分布
方法	$T (A_{1}) / h$	$T (A_{2}) / h$	$T (A_{3}) / h$	$T (A_{4}) / h$	T_c/h	ζ	$T (A_{1}) / h$	$T (A_{2}) / h$	$T (A_{3}) / h$	$T (A_{4}) / h$	T_c/h	ζ
LB	1.249	1.159	1.156	1.023	1.249	0.006 5	1.032	1.099	1.034	0.963	1.099	0.002 3
NB	1.096	1.156	1.287	0.983	1.278	0.012 0	0.974	0.861	1.442	0.943	1.442	0.064 8
VP	1.073	1.698	0.547	1.141	1.698	0.166 2	0.857	1.782	0.378	1.442	1.782	0.255 6

表2

图4

图5

图6

图7

参考文献 26

[1]	AAD W , BENNIS M , CHEN M Z . A vision of 6G wireless systems:applications,trends,technologies,and open research problems[J]. IEEE Network, 2020,34(3): 134-142.
[2]	MORELLO R , MUKHOPADHYAY S C , LIU Z ,et al. Advances on sensing technologies for smart cities and power grids:a review[J]. IEEE Sensors Journal, 2017,17(23): 7596-7610.
[3]	ANBARASAN M , MUTHU B , SIVAPARTHIPAN C B ,et al. Detection of flood disaster system based on IoT,big data and convolutional deep neural network[J]. Computer Communications, 2020,150: 150-157.
[4]	MOSTAFAEI H , CHOWDHURY M U , OBAIDAT M S . Border surveillance with WSN systems in a distributed manner[J]. IEEE Systems Journal, 2018,12(4): 3703-3712.
[5]	BUSHNAQ O M , CHAABAN A , AL-NAFFOURI T Y . The role of UAV-IoT networks in future wildfire detection[J]. IEEE Internet of Things Journal, 2021,8(23): 16984-16999.
[6]	GUO F X , YU F R , ZHANG H L ,et al. Enabling massive IoT toward 6G:a comprehensive survey[J]. IEEE Internet of Things Journal, 2021,8(15): 11891-11915.
[7]	AL-KARAKI J N , KAMAL A E . Routing techniques in wireless sensor networks:a survey[J]. IEEE Wireless Communications, 2004,11(6): 6-28.
[8]	张希伟, 戴海鹏, 徐力杰 ,等. 无线传感器网络中移动协助的数据收集策略[J]. 软件学报, 2013,24(2): 198-214.
	ZHANG X W , DAI H P , XU L J ,et al. Mobility-assisted data gathering strategies in WSNs[J]. Journal of Software, 2013,24(2): 198-214.
[9]	汪成亮, 严君辉 . 大规模无线传感网络数据收集的无人机路径规划[J]. 北京理工大学学报, 2015,35(10): 1044-1049.
	WANG C L , YAN J H . Path planning for UAV to collect sensor data in large-scale WSNs[J]. Transactions of Beijing Institute of Technology, 2015,35(10): 1044-1049.
[10]	付澍, 杨祥月, 张海君 ,等. 物联网数据收集中无人机路径智能规划[J]. 通信学报, 2021,42(2): 124-133.
	FU S , YANG X Y , ZHANG H J ,et al. UAV path intelligent planning in IoT data collection[J]. Journal on Communications, 2021,42(2): 124-133.
[11]	DENG L J , XU W Z , LIANG W F ,et al. Approximation algorithms for the min-max cycle cover problem with neighborhoods[J]. IEEE/ACM Transactions on Networking, 2020,28(4): 1845-1858.
[12]	SHEN K , SHIVGAN R , MEDINA J ,et al. Multidepot drone path planning with collision avoidance[J]. IEEE Internet of Things Journal, 2022,9(17): 16297-16307.
[13]	WANG Y T , SU Z , ZHANG N ,et al. Mobile wireless rechargeable UAV networks:challenges and solutions[J]. IEEE Communications Magazine, 2022,60(3): 33-39.
[14]	LI X W , YAO H P , WANG J J ,et al. Rechargeable multi-UAV aided seamless coverage for QoS-guaranteed IoT networks[J]. IEEE Internet of Things Journal, 2019,6(6): 10902-10914.
[15]	ZHU Y C , WANG S W . Efficient aerial data collection with cooperative trajectory planning for large-scale wireless sensor networks[J]. IEEE Transactions on Communications, 2022,70(1): 433-444.
[16]	ZHU Y C , WANG S W . Data collection in wireless sensor networks:a truck-assisted multi-UAV method[C]// Proceedings of the 2022 IEEE 19th International Conference on Mobile Ad Hoc and Smart Systems (MASS). Piscataway:IEEE Press, 2022: 318-324.
[17]	LIN X S , YAZ?C?O?LU Y , AKSARAY D . Robust planning for persistent surveillance with energy-constrained UAVs and mobile charging stations[J]. IEEE Robotics and Automation Letters, 2022,7(2): 4157-4164.
[18]	AL-HOURANI A , KANDEEPAN S , LARDNER S . Optimal LAP altitude for maximum coverage[J]. IEEE Wireless Communications Letters, 2014,3(6): 569-572.
[19]	ZENG Y , XU J , ZHANG R . Energy minimization for wireless communication with rotary-wing UAV[J]. IEEE Transactions on Wireless Communications, 2019,18(4): 2329-2345.
[20]	HELSGAUN K . General k-opt submoves for the Lin-Kernighan TSP heuristic[J]. Mathematical Programming Computation, 2009,1(2): 119-163.
[21]	BEARDWOOD J , HALTON J H , HAMMERSLEY J M . The shortest path through many points[J]. Mathematical Proceedings of the Cambridge Philosophical Society, 1959,55(4): 299-327.
[22]	COOK W J , APPLEGATE D L , BIXBY R E ,et al. The traveling salesman problem:a computational study[M]. Princeton: Princeton University Press, 2011.
[23]	CARLSSON J G . Dividing a territory among several vehicles[J]. INFORMS Journal on Computing, 2012,24(4): 565-577.
[24]	ZENG Y , ZHANG R . Energy-efficient UAV communication with trajectory optimization[J]. IEEE Transactions on Wireless Communications, 2017,16(6): 3747-3760.
[25]	AURENHAMMER F . Voronoi diagrams—a survey of a fundamental geo metric data structure[J]. ACM Computing Surveys, 1991,23(3): 345-405.
[26]	CARLSSON J G , SONG S Y . Coordinated logistics with a truck and a drone[J]. Management Science, 2018,64(9): 4052-4069.

符号	物理含义
Λ	叶片角速度/(rad·s^-1)
ρ	空气密度/(kg·m^-3)
A_r	旋翼面积/m²
d_r	机身阻力比
P₀	悬停状态叶片轮廓功率/W
P_i	悬停状态诱导功率/W
r	旋翼半径/m
s	旋翼实度/m³
V	前进飞行中的平均旋翼诱导速度/(m·s^-1)