Ordered Submodularity-Based Value Maximization of UAV Data Collection in Earthquake Areas
Jixian Zhang, Zhemin Wang, Hao Wu, Weidong Li
Abstract
UAV data collection problems have been a popular research topic in many fields, and the use of UAV-assisted rescue in earthquake-affected areas can significantly increase the rescue success rate. In this paper, we model the UAV data collection problem for earthquake disaster areas based on the mobile crowdsensing point of interest (POI) model, with the goal of maximizing the value of the collected data, and we transform the problem into an integer programming model with ordered submodularity properties and constraints. Additionally, we design an evolutionary algorithm (Max-UDC) to solve the problem; this algorithm iteratively computes new UAV sequences and eliminates inferior sequences using mutation to obtain a sequence of length <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</i> with the maximum data value. Through theoretical analysis and experimental proof, we demonstrate that the Max-UDC algorithm can obtain an approximation ratio related to forward curvature and backward curvature with an expected number of iterations. In the experimental section, the superior performance of Max-UDC is shown by comparing it with the OPT, G-Greedy, and Greedy algorithms.