• KSII Transactions on Internet and Information Systems
    Monthly Online Journal (eISSN: 1976-7277)

A Lifetime-Preserving and Delay-Constrained Data Gathering Tree for Unreliable Sensor Networks

Vol. 6, No.12, December 31, 2012
10.3837/tiis.2012.12.011, Download Paper (Free):

Abstract

A tree routing structure is often adopted for many-to-one data gathering and aggregation in sensor networks. For real-time scenarios, considering lossy wireless links, it is an important issue how to construct a maximum-lifetime data gathering tree with delay constraint. In this work, we study the problem of lifetime-preserving and delay-constrained tree construction in unreliable sensor networks. We prove that the problem is NP-complete. A greedy approximation algorithm is proposed. We use expected transmissions count (ETX) as the link quality indicator, as well as a measure of delay. Our algorithm starts from an arbitrary least ETX tree, and iteratively adjusts the hierarchy of the tree to reduce the load on bottleneck nodes by pruning and grafting its sub-tree. The complexity of the proposed algorithm is O(N 4 ). Finally, extensive simulations are carried out to verify our approach. Simulation results show that our algorithm provides longer lifetime in various situations compared to existing data gathering schemes.


Statistics

Show / Hide Statistics

Statistics (Cumulative Counts from December 1st, 2015)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article

[IEEE Style]
Yanjun Li, Yueyun Shen and Kaikai Chi, "A Lifetime-Preserving and Delay-Constrained Data Gathering Tree for Unreliable Sensor Networks," KSII Transactions on Internet and Information Systems, vol. 6, no. 12, pp. 3219-3236, 2012. DOI: 10.3837/tiis.2012.12.011

[ACM Style]
Li, Y., Shen, Y., and Chi, K. 2012. A Lifetime-Preserving and Delay-Constrained Data Gathering Tree for Unreliable Sensor Networks. KSII Transactions on Internet and Information Systems, 6, 12, (2012), 3219-3236. DOI: 10.3837/tiis.2012.12.011