Robust Fault-Tolerant Placement of Wireless Chargers for Directional Charging
Jia Xu, Zhou Kai-jun, Sixu Wu, Haipeng Dai, Lijie Xu, Linfeng Liu
Abstract
Wireless Power Transmission (WPT) has been widely used to replenish energy for wireless rechargeable sensor networks. This paper concerns the fundamental issue of robust fault-tolerant placement of wireless chargers for directional charging. Following the general directional charging model, we formulate the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Charger Placement for Robust Coverage (CPRC)</i> problem, which has continuous and infinite constraints, for resisting the wireless charger failure. We transform the problem to the equivalent integer program problem without performance loss by area partition and dominating strategy extraction. We show that the greedy algorithm achieves the logarithmic approximation ratio. We further formulate the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Charger Placement for Robust Utility (CPRU)</i> problem for resisting the sensor node failure. This problem also has continuous and infinite constraints. We transform the problem to the combinational optimization problem with finite strategy space through the techniques of charging power approximation, area discretization and dominating strategy extraction. We present the algorithm, which utilizes the combination of binary search and greedy algorithm, to solve the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">CPRU</i> problem. We conduct both simulations and field experiments to validate our theoretical results. The simulation results show that the proposed algorithms for <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">CPRC</i> and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">CPRU</i> can outperform comparison algorithms by at least 17.48% and 21.15%, respectively.