We define the aggregation delay as the minimum number of time slots it takes for the data to be aggregated in a Data Gathering tree (DG tree) spanning all the nodes of the sensor network; the diameter of a DG tree is the maximum distance (number of hops) from a leaf node to the root node of the tree. We assume that intermediate nodes at the same level or different levels of a DG tree could simultaneously aggregate data from their respective child nodes using different CDMA (Code Division Multiple Access) codes; but, an intermediate node has to schedule non-overlapping time slots (one for each of its child nodes) to aggregate data from its own child nodes. We employ an algorithm to determine the minimum aggregation delay at every intermediate node of the Bottleneck Node Weight (BNW) and Bottleneck Link Weight (BLW)-based DG trees. We observe the BNW-DG trees to incur a smaller tree diameter, but a significantly larger aggregation delay; on the other hand, the BLW-DG trees incur a larger tree diameter and a relatively lower aggregation delay, especially with increase in node density.
TopIntroduction
Wireless Sensor Networks (WSNs) are typically deployed for monitoring environmental data such as temperature, pressure, humidity, etc. Sensor nodes operate under limited battery charge and transmission range. Hence, the data sensed at one or more sensor nodes cannot be directly propagated to the control center (a.k.a. sink); multi-hop data propagation is the norm. Various algorithms for determining communication topologies: like cluster (Heinzelman et. al., 2004), grid (Meghanathan, 2010a), chain (Lindsey et. al., 2002), connected dominating set (Meghanathan, 2010b), tree (Meghanathan, 2012a), etc that support the many-to-one reporting style have been proposed in the literature. Among these, the data gathering trees (DG trees) have been considered energy-efficient due to the use of the minimum number of links for data transmission and reception (Lindsey et. al., 2001; Liang et. al., 2010; Meghanathan, 2012a). A data gathering tree is a rooted spanning tree that covers all the vertices of the graph, comprising of leaf nodes (having no child nodes) and intermediate nodes (having one or more child nodes). The leaf nodes of a DG tree spend energy only to transmit the data packets, while an intermediate node spends energy to receive and aggregate data from its immediate child nodes with its own data and forward the data to its own upstream intermediate node.
In this research, we focus on the delay incurred for data aggregation along the edges of a DG tree. We define the aggregation delay as the minimum number of time slots it takes for the data to be aggregated in a data gathering tree (DG tree) spanning all the nodes of the network. Various algorithms (e.g., Huang et. al., 2007; Wan et. al., 2009; Yu et. al., 2009; Li et. al., 2010a; Xu et. al., 2011; Yu & Li, 2011) have been proposed to determine the aggregation delay for DG trees and all of these assume limited availability of the communication channels and focus on scheduling the channels for the different nodes to minimize the aggregation delay. We consider a channel availability model such that the intermediate nodes at the same level or different levels could simultaneously aggregate data from their respective child nodes using different CDMA (Code Division Multiple Access) codes (Viterbi, 1995); but, an intermediate node has to schedule non-overlapping time slots (one for each of its child nodes: Time Division Multiple Access, TDMA) to aggregate data from its child nodes. Given a DG tree with sufficient availability of communication channels with unique CDMA codes, we employ a benchmarking algorithm to determine the minimum aggregation delay at every intermediate node (including the root node) of the DG tree. To the best of our knowledge, we have not come across a benchmarking algorithm that gives the minimum aggregation delay for any intermediate node vis-a-vis its position in the DG tree.