We analyze the impact of the structure of the Data Gathering (DG) trees on node lifetime (round of first node failure) and network lifetime (minimum number of rounds by which the network gets either disconnected due to node failures or the fraction of coverage loss reaches a threshold) in wireless sensor networks through extensive simulations. The two categories of DG trees studied are: the Bottleneck Node Weight-Based (BNW-DG) trees and Bottleneck Link Weight-Based (BLW-DG) trees. The BNW-DG trees incur a smaller diameter and a significantly larger fraction of nodes as leaf nodes: thus, protecting a majority of the nodes in the network from simultaneously being exhausted of the energy resources (contributing to a significantly larger network lifetime); nevertheless the nodes that serve as intermediate nodes in the first few instances of the BNW-DG trees are bound to lose their energy more quickly than the other nodes, leading to a smaller node lifetime compared to that of the BLW-DG trees (that incur a larger diameter and a relatively lower fraction of nodes as leaf nodes).
Top1. Introduction
Wireless Sensor Networks (WSNs) are used to monitor environmental parameters of interest such temperature, pressure, humidity, etc. by deploying several sensor nodes that sense these data and report to a control center (sink). The sensor nodes are battery charged and operate with a limited transmission range. It would be too energy-draining for the sensor nodes to individually report their data to the sink. For applications that would require only an aggregate of the data (like average temperature of a region) to be known to the sink, it would suffice to let the sensor nodes to aggregate the data among themselves through a communication topology that spans all the nodes and have only an aggregate value of the data reported from the network to the sink. Several such network-wide communication topologies, like clusters (Heinzelman et. al., 2004), chain (Lindsey et. al., 2002), grid (Luo et. al., 2005), connected dominating sets (Meghanathan, 2010), trees (Meghanathan, 2012a), etc have been proposed and analyzed in the literature; among these the data gathering trees (DG trees) have been observed to be the most energy-efficient (Lindsey et. al., 2001; Dietrich & Dressler, 2009; Meghanathan, 2012a). In this research, our focus is restricted to DG trees.
The data gathering algorithms proposed for WSNs could be broadly classified into two categories: bottleneck node weight-based data gathering (BNW-DG) and bottleneck link weight-based (BLW-DG). We define a BNW-DG tree as the one for which the minimum node weight (or the maximum node weight) for a path from any node to the root node of the tree is the maximum (or the minimum); a BLW-DG tree is the one for which the minimum weight (or the maximum weight) of the constituent links for a path from any node to the root node is the maximum (or the minimum). We could map several data gathering algorithms proposed in the literature to one of these two categories. For example, the algorithm for maximizing the residual energy levels of the nodes in the network (Liang et. al., 2010) could be modeled as a BNW-DG problem of maximizing the bottleneck node weight; whereas, the algorithm to maximize the predicted link expiration time of the links in a mobile sensor network (Meghanathan, 2012b) could be modeled as a BLW-DG problem of maximizing the bottleneck link weight. In this chapter, we use maximum bottleneck node-weight based data gathering (MaxBNW-DG) and maximum bottleneck link weight-based data gathering (MaxBLW-DG) as representatives of the bottleneck node weight and bottleneck link weight-based data gathering strategies respectively.
The common theme among the data gathering algorithms proposed in the literature is to construct a network-wide data gathering tree (a rooted spanning tree) that spans all the nodes and have data aggregated across the tree in terms of rounds. We define a round as the process of aggregation of data from all the nodes in the network once along the data gathering tree (i.e., the sensed data is transferred upstream from the leaf nodes towards the root node, aggregated and forwarded by the intermediate nodes). During the process of data gathering, nodes lose energy to transmit the aggregated data to their upstream node as well as lose energy to receive the aggregated data from each of their immediate downstream child nodes. We define node lifetime as the round of first node failure due to exhaustion of energy and network lifetime as the minimum of the number of rounds by which the network gets disconnected (due to node failure) or the number of rounds by which the fraction of coverage loss in the network reaches a threshold.