An Approximation Algorithm for the Maximum-Lifetime Data Aggregation Tree Problem in Wireless Sensor Networks
- 28 March 2017
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Wireless Communications
- Vol. 16 (6), 3787-3798
- https://doi.org/10.1109/twc.2017.2688442
Abstract
This paper studies the problem of constructing maximum-lifetime data aggregation trees in wireless sensor networks for collecting sensor readings. This problem is known to be NP-hard. Wireless sensor networks in which transmission power levels of sensors are adjustable and heterogeneous are considered. An approximation algorithm is developed to construct a data aggregation tree whose inverse lifetime is guaranteed to be within a bound from the optimal one. Adjustable transmission power levels of the sensors introduce an additional term in the bound compared with the bound for networks in which transmission power levels of all sensors are fixed. The additional term is proportional to the difference between the maximum and minimum amounts of energy for a sensor to transmit a message using respectively its maximum and minimum transmission power levels. The proposed algorithm is further enhanced to obtain an improved version. Simulation results show that properly adjusting transmission power levels of the sensors yields higher lifetime of the network than keeping their transmission power levels at the maximum level.Funding Information
- National Science Council (NSC102-2221-E-007-014)
This publication has 61 references indexed in Scilit:
- Workload-Aware Tree Construction Algorithm for Wireless Sensor NetworksInternational Journal on Applications of Graph Theory In wireless Ad Hoc Networks And sensor Networks, 2012
- Efficient algorithm for maximum lifetime many-to-one data aggregation in wireless sensor networksInternational Journal of Sensor Networks, 2011
- Near-lifetime-optimal data collection in wireless sensor networks via spatio-temporal load balancingACM Transactions on Sensor Networks, 2010
- A combinatorial algorithm for the maximum lifetime data gathering with aggregation problem in sensor networksComputer Communications, 2009
- RT-Link: A global time-synchronized link protocol for sensor networksAd Hoc Networks, 2008
- A combinatorial algorithmic approach to energy efficient information collection in wireless sensor networksACM Transactions on Sensor Networks, 2007
- Maximum Lifetime Routing in Wireless Sensor NetworksIEEE/ACM Transactions on Networking, 2004
- Optimal Information Extraction in Energy-Limited Wireless Sensor NetworksIEEE Journal on Selected Areas in Communications, 2004
- Power efficient data gathering and aggregation in wireless sensor networksACM SIGMOD Record, 2003
- Approximating the Minimum-Degree Steiner Tree to within One of OptimalJournal of Algorithms, 1994