Collaborative Mobile Charging for Sensor Networks

The limited battery capacity of sensor nodes has become the biggest impediment to wireless sensor network (WSN) applications. Two recent breakthroughs in the areas of wireless energy transfer and rechargeable lithium batteries promise the use of mobile vehicles, with high volume batteries, as mobile chargers that transfer energy to sensor nodes wirelessly. In this paper, for the first time, we envision a novel charging paradigm: collaborative mobile charging, where mobile chargers are allowed to charge each other. We investigate the problem of scheduling multiple mobile chargers, which collaboratively recharge sensors, to maximize the ratio of the amount of payload energy to overhead energy, such that every sensor will not run out of energy. We first consider the uniform case where all sensors consume energy at the same rate, and propose a scheduling algorithm, PushWait, which is proven to be optimal in this case and can cover a one-dimensional WSN of infinite length. Then, in the non-uniform case, which is conjectured to be NP-hard, we first present two observations from space and time aspects to remove some impossible scheduling choices, and we propose our heuristic algorithm, ClusterCharging(a), which clusters sensors into groups and divides a scheduling cycle into charging rounds. Its approximation ratio is also presented. Extensive evaluations confirm the efficiency of our algorithms.