Finding the maximum lifetime data-gathering tree in sensor networks

In this work, we study the construction of a data gathering tree to maximize the network lifetime, which is defined as the minimum of the lifetime of all the nodes in the sensor network. The problem of finding the optimal data gathering tree is known to be NP-complete [9]. Most works in this area aim to give an heuristic to find a data gathering tree and compare the lifetime obtained with other existing solutions. But it is beyond doubt that best tree with respect to lifetime could be obtained if we can generate all possible spanning trees and choose among them the one giving maximum lifetime. With a sensor network consisting of large number of nodes this approach becomes computationally prohibitive. We have adopted an algorithm to generate all possible spanning trees and modified it to generate only the optimal spanning tree using a branch and bound technique. Here, whenever a partial tree has a node with lifetime less than or equal to the lifetime of a tree generated earlier, that tree is discarded. Simulation results show that the number of complete trees checked by our method is only a small fraction of the total number of possible spanning trees. That way it becomes feasible to find a solution in reasonable time even for large sensor network. We have considered that transmission range of each sensor can be adjusted to be just enough to send a message to its parent. The lifetime obtained by our method is also shown to be better than that obtained by other heuristic algorithm like PEDAP.