Constructing Maximum-Lifetime Data-Gathering Forests in Sensor Networks
- 22 April 2010
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 18 (5), 1571-1584
- https://doi.org/10.1109/tnet.2010.2045896
Abstract
Energy efficiency is critical for wireless sensor networks. The data-gathering process must be carefully designed to conserve energy and extend network lifetime. For applications where each sensor continuously monitors the environment and periodically reports to a base station, a tree-based topology is often used to collect data from sensor nodes. In this work, we first study the construction of a data-gathering tree when there is a single base station in the network. The objective is to maximize the network lifetime, which is defined as the time until the first node depletes its energy. The problem is shown to be NP-complete. We design an algorithm that starts from an arbitrary tree and iteratively reduces the load on bottleneck nodes (nodes likely to soon deplete their energy due to high degree or low remaining energy). We then extend our work to the case when there are multiple base stations and study the construction of a maximum-lifetime data-gathering forest. We show that both the tree and forest construction algorithms terminate in polynomial time and are provably near optimal. We then verify the efficacy of our algorithms via numerical comparisons.Keywords
This publication has 20 references indexed in Scilit:
- A Learning-based Adaptive Routing Tree for Wireless Sensor NetworksJournal of Communications, 2006
- On the Construction of Efficient Data Gathering Tree in Wireless Sensor NetworksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Simultaneous Optimization for Concave Costs: Single Sink Aggregation or Single Source Buy-at-BulkAlgorithmica, 2005
- A wireless sensor network For structural monitoringPublished by Association for Computing Machinery (ACM) ,2004
- Maximum Lifetime Routing in Wireless Sensor NetworksIEEE/ACM Transactions on Networking, 2004
- Rate allocation in wireless sensor networks with network lifetime requirementPublished by Association for Computing Machinery (ACM) ,2004
- Sensor and actuator networks - Query processing in sensor networksIEEE Pervasive Computing, 2004
- Taming the underlying challenges of reliable multihop routing in sensor networksPublished by Association for Computing Machinery (ACM) ,2003
- Wireless sensor networks for habitat monitoringPublished by Association for Computing Machinery (ACM) ,2002
- An algorithm for distributed computation of a spanningtree in an extended LANPublished by Association for Computing Machinery (ACM) ,1985