Reusing Delivery Drones for Urban Crowdsensing

Abstract

Thanks to the increasing number and massive coverage, delivery drones, equipped with various sensors, have demonstrated significant but unexplored potentials for large-scale and low-cost urban sensing during package delivery. In this paper, we propose novel studies on the reutilization of such delivery drone resources to fill this void in urban crowdsensing. Accounting for interdependency between flying/sensing and drone delivery weight, we jointly optimize route selection, sensing time, and delivery weight allocation, to maximize delivery and sensing utility under drones’ energy constraints. This problem is formulated as a non-convex mixed-integer non-Linear programming problem, which is proved to be NP-hard. To address this intricate problem, we propose near-optimal algorithms that leverage the equivalent objective function construction, the local search scheme, and the alternating iteration technique. Theoretical analysis indicates that our algorithms can achieve <inline-formula><tex-math notation="LaTeX">$\frac{1}{4+\varepsilon }$</tex-math></inline-formula> -approximation ratio (where <inline-formula><tex-math notation="LaTeX">$\varepsilon$</tex-math></inline-formula> is an arbitrarily small positive parameter) and the convergence guarantee in polynomial time, for the scenarios of fixed and adjustable delivery weights, respectively. Extensive trace-based simulations, field experiments, and the real-world application demonstrate that ours can significantly improve the delivery & sensing utility by <inline-formula><tex-math notation="LaTeX">$124.7\%$</tex-math></inline-formula> and the energy utilization rate by <inline-formula><tex-math notation="LaTeX">$72.2\%$</tex-math></inline-formula> on average, compared with the drone delivery without reusing.

Topics & Concepts