Completion Time Minimization for Multi-UAV Information Collection via Trajectory Planning
Open Access
Abstract
Unmanned Aerial Vehicles (UAVs) are widely used as mobile information collectors for sensors to prolong the network time in Wireless Sensor Networks (WSNs) due to their flexible deployment, high mobility, and low cost. This paper focuses on the scenario where rotary-wing UAVs complete information collection mission cooperatively. For the first time, we study the problem of minimizing the mission completion time for a multi-UAV system in a monitoring scenario when considering the information collection quality. The mission completion time includes flying time and hovering time. By optimizing the trajectories of all UAVs, we minimize the mission completion time while ensuring that the information of each sensor is collected. This problem can be formulated as a mixed-integer non-convex one which has been proved to be NP-hard. To solve the formulated problem, we first propose a hovering point selection algorithm to select appropriate hovering points where the UAVs can sequentially collect the information from multiple sensors. We model this problem as a BS coverage problem with the information collection quality in consideration. Then, we use a min-max cycle cover algorithm to assign these hovering points and get the trajectory of each UAV. Finally, with the obtained UAVs trajectories, we further consider the UAVs can also collect information when flying and optimize the time allocations. The performance of our algorithm is verified by simulations, which show that the mission completion time is minimum compared with state-of-the-art algorithms.Keywords
Funding Information
- National Natural Science Foundation of China (61872178, 61827801, 61702545, 61702525, 61631020)
- Fundamental Research Funds for the Central Universities (021014380079)
- Natural Science Foundation of Jiangsu Province (BK20181251)
This publication has 54 references indexed in Scilit:
- A Survey of Channel Bonding for Wireless Networks and Guidelines of Channel Bonding for Futuristic Cognitive Radio Sensor NetworksIEEE Communications Surveys & Tutorials, 2015
- A Connectivity-Aware Approximation Algorithm for Relay Node Placement in Wireless Sensor NetworksIEEE Sensors Journal, 2015
- An Efficient Sensor Deployment Scheme for Large-Scale Wireless Sensor NetworksIEEE Communications Letters, 2014
- Optimal LAP Altitude for Maximum CoverageIEEE Wireless Communications Letters, 2014
- A Framework of Joint Mobile Energy Replenishment and Data Gathering in Wireless Rechargeable Sensor NetworksIEEE Transactions on Mobile Computing, 2014
- A new algorithm for the undesirable 1-center problem on networksJournal of the Operational Research Society, 2002
- The Weighted Euclidean 1-Center ProblemMathematics of Operations Research, 1983
- Linear-Time Algorithms for Linear Programming in $R^3 $ and Related ProblemsSIAM Journal on Computing, 1983
- An extension of Christofides heuristic to the k-person travelling salesman problemDiscrete Applied Mathematics, 1983
- Geometrical Solutions for Some Minimax Location ProblemsTransportation Science, 1972