Article Preview
TopIntroduction
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: