Near optimal bounded route association for drone-enabled rechargeable WSNs

This paper considers the multi-drone wireless charging scheme in large scale wireless sensor networks, where sensors can be charged by the charging drone with wireless energy transfer. As existing studies rarely focus on the route association issue with limited energy capacity, we consider this fundamental issue and study how to optimize the route association to maximize the overall charging coverage utility, when charging routes and associated nodes should be jointly selected. We first formulate a bounded route association problem which is proven to be NP-hard. Then we cast it as maximizing a monotone submodular function subject to matroid constraints and devise an efficient and accessible algorithm with a 13α approximation ratio, where α is the bound of Fully Polynomial-Time Approximation Scheme (FPTAS) solving a knapsack problem. Extensive numerical evaluations and trace-driven evaluations have been carried out to validate our theoretical effect, and the results show that our algorithm has near-optimal performance covering at most 85.3% and 70.5% of the surrogate-optimal solution achieved by CPLEX toolbox, respectively.