Approximation Algorithms for Charging Reward Maximization in Rechargeable Sensor Networks Via a Mobile Charger
Wireless energy transfer has emerged as a promising technology for wireless sensor networks to power sensors with controllable yet perpetual energy. In this paper, we study sensor energy replenishment by employing a mobile charger (charging vehicle) to charge sensors wirelessly in a rechargeable sensor network, so that the sum of charging rewards collected from all charged sensors by the mobile charger per tour is maximized, subject to the energy capacity of the mobile charger, where the amount of reward received from a charged sensor is proportional to the amount of energy charged to the sensor. The energy of the mobile charger will be spent on both its mechanical movement and sensor charging. We first show that this problem is NP-hard. We then propose approximation algorithms with constant approximation ratios under two different settings: one is that a sensor will be charged to its full energy capacity if it is charged; another is that a sensor can be charged multiple times per tour but the total amount of energy charged is no more than its energy demand prior to the tour. We finally evaluate the performance of the proposed algorithms through experimental simulations. The simulation results demonstrate that the proposed algorithms are very promising, and the solutions obtained are fractional of the optimum. To the best of our knowledge, the proposed algorithms are the very first approximation algorithms with guaranteed approximation ratios for the mobile charger scheduling in a rechargeable sensor network under the energy capacity constraint on the mobile charger.
W. Liang et al., "Approximation Algorithms for Charging Reward Maximization in Rechargeable Sensor Networks Via a Mobile Charger," IEEE/ACM Transactions on Networking, vol. 25, no. 5, pp. 3161-3174, Institute of Electrical and Electronics Engineers (IEEE), Oct 2017.
The definitive version is available at https://doi.org/10.1109/TNET.2017.2723605
Intelligent Systems Center
Second Research Center/Lab
Center for High Performance Computing Research
Keywords and Phrases
Combinatorial optimization; Energy transfer; Heuristic algorithms; Inductive power transmission; Mobile computing; Mobile telecommunication systems; Optimization; Reinforcement; Scheduling; Wireless sensor networks; Wireless telecommunication systems; Combinatorial optimization problems; Mobile chargers; Mobile communications; Wireless communications; Wireless energy transfers; Approximation algorithms; Rechargeable wireless sensor networks; Sensor energy replenishments; Wireless energy transfer
International Standard Serial Number (ISSN)
Article - Journal
© 2017 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
01 Oct 2017