Minimum Wireless Charger Placement with Individual Energy Requirement

Abstract Supply energy to battery-powered sensor devices by deploying wireless chargers is a promising way to prolong the operation time of wireless sensor networks, and has attracted much attention recently. Existing works focus on maximizing the total received charging power of the network. However, this may face the unbalanced energy allocation problem, which is not beneficial to prolong the operation time of wireless sensor networks. In this paper, we consider the individual energy requirement of each sensor node, and study the problem of minimum charger placement. That is, we focus on finding a strategy for placing wireless chargers from a given candidate location set, such that each sensor node's energy requirement can be met, meanwhile the total number of used chargers can be minimized. We deal with the problem under both omnidirectional and directional charging models, and prove its NP-hardness. For the omnidirectional charging case, we present two approximation algorithms which are based on greedy scheme and relax rounding scheme, respectively. We prove that both of the two algorithms have performance guarantees. For the directional charging case, we first extract the candidate orientation set for each candidate location to reduce the search space from infinite to a limited set, and then propose a greedy algorithm that also has a proved performance guarantee. Finally, we validate the performance of our algorithms by performing extensive numerical simulations. Simulation results show the effectiveness of our proposed algorithms.