Fine-Grained Trajectory Optimization of Multiple UAVs for Efficient Data Gathering from WSNs

摘要

The increasing availability of autonomous small-size Unmanned Aerial Vehicles (UAVs) has provided a promising way for data gathering from Wireless Sensor Networks (WSNs) with the advantages of high mobility, flexibility, and good speed. However, few works considered the situations that multiple UAVs are collaboratively used and the fine-grained trajectory plans of multiple UAVs are devised for collecting data from network including detailed traveling and hovering plans of them in the continuous space. In this paper, we investigate the problem of the Fine-grained Trajectory Plan for multi-UAVs (FTP), in which m UAVs are used to collect data from a given WSN, where m >= 1 . The problem entails not only to find the flight paths of multiple UAVs but also to design the detailed hovering and traveling plans on their paths for efficient data gathering from WSN. The objective of the problem is to minimize the maximum flight time of UAVs such that all sensory data of WSN is collected by the UAVs and transported to the base station. We first propose a mathematical model of the FTP problem and prove that the problem is NP-hard. To solve the FTP problem, we first study a special case of the FTP problem when m = 1, called FTP with Single UAV (FTPS) problem. Then we propose a constant-factor approximation algorithm for the FTPS problem. Based on the FTPS problem, an approximation algorithm for the general version of the FTP problem when m > 1 is further proposed, which can guarantee a constant factor of the optimal solution. Afterwards, the proposed algorithms are verified by extensive simulations.