Minimizing the Maximum Charging Delay of Multiple Mobile Chargers Under the Multi-Node Energy Charging Scheme

Wireless energy charging has emerged as a very promising technology for prolonging sensor lifetime in Wireless Rechargeable Sensor Networks (WRSNs). Existing studies focused mainly on the one-to-one charging scheme that a sensor can be charged at each time by a single mobile charger, this charging scheme however suffers from poor charging scalability and inefficiency. Recently, another charging scheme, the multi-node charging scheme that allows multiple sensors to be charged simultaneously by a single charger becomes dominant and can mitigate charging scalability and improve charging efficiency. In this paper we first formulate a novel longest delay minimization problem for sensor charging under this multi-node charging scheme, and we show that the problem is NP-hard. We then devise the very first approximation algorithm with a provable approximation ratio for the problem. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithm is promising, and outperforms the other heuristics in various settings.