Efficient Topology Design in Time-Evolving and Energy-Harvesting Wireless Sensor Networks

Recent advances in ambient energy-harvesting technologies have made it possible to power wireless sensor networks (WSNs) from the environment for long durations. However, the energy availability in an energy-harvesting WSN varies with time and thus may cause the network topology to evolve over time. In this paper, we study the topology design problem in a time-evolving and energy-harvesting WSN where the time-evolving topology and dynamic energy cost are known a priori or can be predicted. We model such a network as a node-weighted space-time graph which includes both spacial and temporal information. To reduce the cost of supporting time-evolving networks with limited harvesting energy sources, we propose a new efficient topology design problem which aims to put more sensors into sleep while still maintaining the network connectivity over time. We prove that the optimization problem of finding the optimal awake sensor set with the minimum total cost is NP-hard. Thus, we propose several topology design algorithms which can significantly reduce the total cost of topology while maintaining the connectivity over time. Simulation results from random time-evolving and energy-harvesting WSNs demonstrate the efficiency of the proposed methods.