Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/ | Intelligent Sensors, Sensor Networks and Information Processing |
Keywords | Field | DocType |
optimisation,tree searching,trees (mathematics),wireless sensor networks,NP-complete problem,PEDAP,branch and bound technique,maximum lifetime data-gathering tree,spanning trees,wireless sensor networks | Data collection,Heuristic,Branch and bound,Mathematical optimization,Distributed minimum spanning tree,Heuristic (computer science),Computer science,Spanning tree,Fractal tree index,Wireless sensor network | Conference |
Citations | PageRank | References |
1 | 0.35 | 9 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sharmila Baksi | 1 | 1 | 0.35 |
| Anupama Sinha | 2 | 1 | 0.35 |
| Sunirmal Khatua | 3 | 120 | 15.00 |
| Rajib K. Das | 4 | 35 | 8.94 |