In the first half of the chapter, the authors provide a comprehensive description of two broad categories of data gathering algorithms for wireless sensor networks: the classical energy-unaware algorithms and the modern energy-aware algorithms, as well as presented an exhaustive performance comparison of representative algorithms from both these categories. While the first half of the chapter focuses on static sink (that is located outside on the network boundary), the second half of the chapter explores the use of mobile sinks that gather data by stopping at the vicinity of the sensor nodes. As a first step, the authors investigate the performance of three different strategies to develop sink mobility models for delay and energy-efficient data gathering in static wireless sensor networks. The three strategies differ on the approach to take to determine the next stop for data gathering: randomly choosing a sensor node that is yet to be covered (Random), choose the sensor node that has the maximum number of uncovered neighbor nodes (Max-Density), and choose the sensor node that has the largest value for the product of the maximum number of uncovered neighbor nodes and the residual energy (Max-Density-Energy). Based on the simulation results, the authors recommend incorporating the random node selection-based strategy to be a better strategy for sink mobility models (with minimal deployment overhead) rather than keeping track of the number of uncovered neighbor nodes per node and the residual energy available at the nodes.
Top1. Introduction
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 chapter, 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). In a related work, we have proposed a benchmarking algorithm to determine a sequence of longest-living stable data gathering trees for mobile sensor networks (Meghanathan & Mumford, 2013a) as well as developed distributed algorithms for energy-efficient minimum distance spanning tree-based data gathering and stability-oriented link expiration time spanning tree-based data gathering for mobile sensor networks (Meghanathan, 2012).
This chapter focuses on data gathering algorithms for static sensor networks. 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. 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 chapter, the terms ‘node’ and ‘vertex’, ‘link’ and ‘edge’, ‘gathering’ and ‘aggregation’ are used interchangeably. They mean the same. The rest of the chapter is organized as follows: