Charging Utility Maximization in Wireless Rechargeable Sensor Networks by Charging Multiple Sensors Simultaneously

摘要

Wireless energy charging has been regarded as a promising technology for prolonging sensor lifetime in wireless rechargeable sensor networks (WRSNs). Most existing studies focused on one-to-one charging between a mobile charger and a sensor that suffers charging scalability and efficiency issues. A new charging technique - one-to-many charging scheme that allows multiple sensors to be charged simultaneously by a single charger can well address the issues. In this paper, we investigate the use of a mobile charger to charge multiple sensors simultaneously in WRSNs under the energy capacity constraint on the mobile charger. We aim to minimize the sensor energy expiration time by formulating a novel charging utility maximization problem, where the amount of utility gain by charging a sensor is proportional to the amount of energy received by the sensor. We also consider the charging tour length minimization problem of minimizing the travel distance of the mobile charger if all requested sensors must be charged, assuming that the mobile charger has sufficient energy to support all requested sensor charging and itself travelling. Specifically, in this paper, we first devise an approximation algorithm with a constant approximation ratio for the charging utility maximization problem if the energy consumption of the mobile charger on its charging tour is negligible. Otherwise, we develop an efficient heuristic for it through a non-trivial reduction from a length-constrained utility maximization problem. We then, devise the very first approximation algorithm with a constant approximation ratio for the charging tour length minimization problem through exploiting the combinatorial property of the problem. We finally evaluate the performance of the proposed algorithms through experimental simulations. Simulation results demonstrate that the proposed algorithms are promising, and outperform the other heuristics in various settings.