Multi-vehicle Coordination for Wireless Energy Replenishment in Sensor Networks

Mobile vehicles equipped with wireless energy transmission technology can recharge sensor nodes over the air. When to recharge which nodes, and in what order, critically impact the network performance. So far only a few works have studied the recharging policy for a single mobile vehicle. In this paper, we study how to coordinate the recharging activities of multiple mobile vehicles, which provide more scalability and robustness than a single vehicle. We leverage concepts and mechanisms from NDN (Named Data Networking) to design energy monitoring protocols that deliver energy status information to mobile vehicles in an efficient manner. Then we study how to minimize the total traveling cost of multiple vehicles while ensuring no node failure. We derive theoretical results on the energy neutral condition and the minimum number of mobile vehicles required for perpetual network operations. We formulate the optimization problem into a Multiple Traveling Salesman Problem with Deadlines (m-TSP with Deadlines), which is NP-hard. To accommodate the dynamic nature of node energy conditions and reduce computational overhead, we present a heuristic algorithm that selects the node with the minimum weighted sum of traveling time and residual lifetime. Our scheme not only improves network scalability but also guarantees the perpetual operation of networks. Finally, we conduct extensive simulations to demonstrate the effectiveness and efficiency of our proposed design, and validate the correctness of theoretical analysis.