Minimizing the number of mobile chargers for large-scale wireless rechargeable sensor networks

摘要

Traditional wireless sensor networks (WSNs) are constrained by limited battery energy that powers the sensor nodes, which impedes the large-scale deployment of WSNs. Wireless power transfer technology provides a promising way to solve this problem. With such novel technology, recent works propose to use a single mobile charger (MC) traveling through the network fields to replenish energy to every sensor node so that none of the nodes will run out of energy. These algorithms work well in small-scale networks. In large-scale networks, these algorithms, however, do not work efficiently, especially when the amount of energy the MC can provide is limited. To address this issue, multiple MCs can be used. In this paper, we investigate the minimum MCs problem (MinMCP) for two-dimensional (2D) wireless rechargeable sensor networks (WRSNs), i.e., how to find the minimum number of energy-constrained MCs and design their recharging routes in a 2D WRSN such that each sensor node in the network maintains continuous work, assuming that the energy consumption rate for all sensor nodes are identical. By reduction from the Distance Constrained Vehicle Routing Problem (DVRP), we prove that MinMCP is NP-hard. Then we propose approximation algorithms for this problem. Finally, we conduct extensive simulations to validate the effectiveness of our algorithms.