Building Maximum Lifetime Shortest Path Data Aggregation Trees in Wireless Sensor Networks

In wireless sensor networks, the spanning tree is usually used as a routing structure to collect data. In some situations, nodes do in-network aggregation to reduce transmissions, save energy, and maximize network lifetime. Because of the restricted energy of sensor nodes, how to build an aggregation tree of maximum lifetime is an important issue. It has been proved to be NP-complete in previous works. As shortest path spanning trees intuitively have short delay, it is imperative to find an energy-efficient shortest path tree for time-critical applications. In this article, we first study the problem of building maximum lifetime shortest path aggregation trees in wireless sensor networks. We show that when restricted to shortest path trees, building maximum lifetime aggregation trees can be solved in polynomial time. We present a centralized algorithm and design a distributed protocol for building such trees. Simulation results show that our approaches greatly improve the lifetime of the network and are very effective compared to other solutions. We extend our discussion to networks without aggregation and present interesting results.