Space Pruning Based Time Minimization in Delay Constrained Multi-Task UAV-Based Sensing

Due to the inherent mobility and enhanced communication capability of the unmanned aerial vehicle (UAV), it is foreseen that effective UAV-based sensing schemes can achieve faster deployment and flexible observation as compared to the traditional fixed sensing systems. In many sensing applications, multiple geographically distributed tasks need to be executed while satisfying a stringent requirement on the transmission delay of the sensory data, especially for the time-critical sensing tasks, such as disaster rescue and environment monitoring. To minimize the overall mission completion time in such delay constrained multi-task UAV-based sensing applications, it is imperative to properly design the inter-task trajectory, the UAV-BS association, and the sensing order. Nonetheless, finding the optimal sensing scheme is highly non-trivial since these three sub-problems are tightly coupled and involve non-convex constraints. To overcome these challenges, firstly, a novel space pruning based trajectory search (SPTS) algorithm is proposed by exploiting the geometric characteristics of the optimal inter-task UAV trajectory, which can achieve a substantially faster convergence as compared to the Ployblock algorithm. Secondly, a novel optimal UAV-BS association (OUBA) algorithm is presented to quickly identify the best BS for each sensing task. Thirdly, by combining these two proposed algorithms with the Lin-Kernighan-Helsgaun (LKH) algorithm, a lower bound of the mission completion time can be efficiently computed and a near-optimal solution can be obtained. Numerical simulations demonstrate that significant performance improvement can be achieved by the proposed scheme.