Maintaining Large-Scale Rechargeable Sensor Networks Perpetually via Multiple Mobile Charging Vehicles

• Published in: ACM transactions on sensor networks 2016-05, Vol.12 (2), p.1-26
• Main Authors: Liang, Weifa, Xu, Wenzheng, Ren, Xiaojiang, Jia, Xiaohua, Lin, Xiaola
• Format: Article
• Language: English
• Subjects: Algorithms; Approximation; Charging; Mathematical analysis; Networks; Scheduling; Sensors; Vehicles
• ISSN: 1550-4859; 1550-4867
• DOI: 10.1145/2898357

Wireless energy transfer technology based on magnetic resonant coupling has been emerging as a promising technology for wireless sensor networks (WSNs) by providing controllable yet perpetual energy to sensors. In this article, we study the deployment of the minimum number of mobile charging vehicles to charge sensors in a large-scale WSN so that none of the sensors will run out of energy, for which we first advocate a flexible on-demand charging paradigm that decouples sensor energy charging scheduling from the design of sensing data routing protocols. We then formulate a novel optimization problem of scheduling mobile charging vehicles to charge life-critical sensors in the network with an objective to minimize the number of mobile charging vehicles deployed, subject to the energy capacity constraint on each mobile charging vehicle. As the problem is NP-hard, we instead propose an approximation algorithm with a provable performance guarantee if the energy consumption of each sensor during each charging tour is negligible. Otherwise, we devise a heuristic algorithm by modifying the proposed approximation algorithm. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results demonstrate that the proposed algorithms are very promising, and the solutions obtained are fractional of the optimal ones. To the best of our knowledge, this is the first approximation algorithm with a nontrivial approximation ratio for a novel scheduling problem of multiple mobile charging vehicles for charging sensors.