A Comprehensive Review and Performance Analysis of Data Gathering Algorithms for Wireless Sensor Networks

A Comprehensive Review and Performance Analysis of Data Gathering Algorithms for Wireless Sensor Networks

Natarajan Meghanathan (Jackson State University, USA)
DOI: 10.4018/jitn.2012040101
OnDemand PDF Download:
No Current Special Offers


Wireless sensor networks comprise of vast numbers of sensor nodes deployed to monitor a particular event (fire, intrusion, etc.) or measure a parameter (like temperature, pressure) value representative of the physical condition of the ambient environment. There is a growing need of using energy-efficient data gathering algorithms that can effectively aggregate the monitored/measured data from the individual sensor nodes through a properly constructed communication topology and transmit a single representative data to a control center (sink) that is typically located far away from the network field. In order to maximize node lifetime and be fair to all nodes in the network, such a communication topology has to be dynamically constructed for every round of data gathering by taking into consideration available energy levels of sensor nodes. This paper presents a comprehensive description of two broad categories of data gathering algorithms for wireless sensor networks – the classical algorithms that are not energy-aware and modern energy-aware data gathering algorithms. These algorithms can also be classified based on the communication topology they choose to construct and use for data gathering. The authors also present an extensive simulation study that demonstrates the individual as well as the comparative performance of these data gathering algorithms.
Article Preview


A wireless sensor network encompasses several smart sensor nodes that can gather data about the surrounding environment as well as process them before propagating to a control center called the sink, typically located far away from the network field. End users of the application access the network nodes as well as the gathered data through the sink. The sensor nodes are constrained with limited battery charge, memory and processing capability as well as operate under a limited transmission range. Two sensor nodes that are outside the transmission range of each other cannot directly communicate. A wireless sensor network also has a limited bandwidth and the communication medium is shared by the sensor nodes that are in the transmission range of each other. Due to all of the above resource and operating constraints, it will not be a viable solution to require every sensor node to directly transmit their data to the sink over a longer distance. Also, if several signals are transmitted at the same time over a longer distance, it could lead to lot interference and collisions. Thus, there is a need for employing energy-efficient data gathering algorithms that can effectively combine the data collected at these sensor nodes and send only the aggregated data (that is a representative of the entire network) to the sink.

In this paper, we consider the problem of periodically gathering the data from the sensor nodes in the network. Accordingly, the data gathering algorithms operate in several rounds, and during each round, data from the sensor nodes are collected, aggregated and forwarded to the sink through a communication topology determined on an underlying network graph based on the transmission range of the sensor nodes. The data gathering algorithms differ in the communication topology used for data aggregation and forwarding: clusters (Heinzelman et al., 2000), chain (Lindsey et al., 2002), grid (Meghanathan, 2010a), connected dominating set (Meghanathan, 2010b) and spanning trees (Meghanathan, 2010c). The data gathering algorithms target to optimize one or more of these performance metrics: (i) Node lifetime, (ii) Delay per round, (iii) Energy per round, and (iv) Energy * Delay per round. In this paper, the node lifetime will be referred to as the number of rounds the network can run before sustaining the first node failure due to exhaustion of battery charge; this definition for node lifetime is also sometimes interpreted as the network lifetime in the literature. Throughout the paper, the terms ‘node’ and ‘vertex,’ ‘link,’ and ‘edge,’ ‘gathering’ and ‘aggregation’ are used interchangeably. They mean the same. The rest of the paper is organized as follows:

Complete Article List

Search this Journal:
Open Access Articles
Volume 14: 4 Issues (2022): 1 Released, 3 Forthcoming
Volume 13: 4 Issues (2021)
Volume 12: 4 Issues (2020)
Volume 11: 4 Issues (2019)
Volume 10: 4 Issues (2018)
Volume 9: 4 Issues (2017)
Volume 8: 4 Issues (2016)
Volume 7: 4 Issues (2015)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing