The dynamic routing algorithm for renewable wireless sensor networks with wireless power transfer

Wireless power transfer is recently considered as a potential approach to remove the lifetime performance bottleneck for wireless sensor networks. By using a wireless charging vehicle (WCV) to periodically recharge each sensor node’s battery, a wireless sensor network may remain operational forever. In this paper, we aim to jointly optimize a dynamic multi-hop data routing, a traveling path (for the WCV to visit all the sensor nodes in a cycle), and a charging schedule (charging time for each sensor node) such that the ratio of the WCV’s vacation time over the cycle time can be maximized. The key challenge of this problem (caused by time-varying data routing) is the integration and differentiation terms in problem formulation, which yields a very challenging non-polynomial program. To remove these non-polynomial terms, we introduce the concept of (N+1)(N+1)-phase solution, which adopt a special dynamic routing scheme. We prove that an optimal (N+1)(N+1)-phase solution can achieve the same objective value as that by an optimal time-varying solution. We further prove that the optimal traveling path must follow the shortest Hamiltonian cycle. Finally, we linearize the problem for data routing and charging schedule and thus obtain an optimal solution in polynomial-time.