Recharging schedules for wireless sensor networks with vehicle movement costs and capacity constraints

Several recent works have studied the schedule for mobile vehicles to recharge sensor nodes via wireless energy transfer technologies. Unfortunately, most of them overlooked the important factors of the vehicles' moving energy consumption and limited recharging capacity. These oversights may lead to problematic schedules or even stranded vehicles. In this paper, we study the recharging schedule that maximizes the recharging profit - the amount of replenished energy less the cost of vehicle movements - under these important constraints. We first derive the minimum number of vehicles needed for energy neutral condition and discover a set of desired network properties. Then we formulate the recharge schedule optimization into a Profitable Traveling Salesmen Problem with capacity and battery deadline constraints, which we prove to be NP-hard. We propose two algorithms to solve the problem. The first one is a greedy algorithm that maximizes the recharge profit at each step; the second one first adaptively partitions the network based on recharge requests, then forms Capacitated Minimum Spanning Tree in each partition followed by route improvements. Finally, we evaluate and compare the performance of proposed algorithms and validate the correctness of theoretical results through extensive simulations. Given a sufficient number of vehicles, the adaptive algorithm can keep the number of nonfunctional nodes at zero. Compared to the greedy algorithm, it reduces the percentage of transient energy depletion by 30-50% with 10-20% energy saving on vehicles.