Spanning tree based algorithms for low latency and energy efficient data aggregation enhanced convergecast (DAC) in wireless sensor networks

Many wireless sensor networks (WSNs) employ battery-powered sensor nodes. Communication in such networks is very taxing on its scarce energy resources. Convergecast - process of routing data from many sources to a sink - is commonly performed operation in WSNs. Data aggregation is a frequently used energy-conversing technique in WSNs. The rationale is to reduce volume of communicated data by using in-network processing capability at sensor nodes. In this paper, we address the problem of performing the operation of data aggregation enhanced convergecast (DAC) in an energy and latency efficient manner. We assume that all the nodes in the network have a data item and there is an a priori known application dependent data compression factor (or compression factor), gamma, that approximates the useful fraction of the total data collected. The paper first presents two DAC tree construction algorithms. One is a variant of the Minimum Spanning Tree (MST) algorithm and the other is a variant of the Single Source Shortest Path Spanning Tree (SPT) algorithm. These two algorithms serve as a motivation for our Combined algorithm (COM) which generalized the SPT and MST based algorithm. The COM algorithm tries to construct an energy optimal DAC tree for any fixed value of x (= 1 - gamma), the data growth factor. The nodes of these trees are scheduled for collision-free communication using a channel allocation algorithm. To achieve low latency, these algorithms use the beta-constraint, which puts a soft limit oil the maximum number of children a node can have in a DAC tree. The DAC tree obtained from energy phase of tree construction algorithms is restructured using the beta-constraint (in the latency minimizing phase) to reduce latency (at the expense of increasing energy cost). The effectiveness of these algorithms is evaluated by using energy efficiency, latency and network lifetime as metrics. With these metrics, the algorithms' performance is compared with an existing data aggregation technique. From the experimental results, for a given network density and data compression factor gamma at intermediate nodes, one call choose an appropriate algorithm depending upon whether the primary goal is to minimize the latency or the energy consumption. (C) 2006 Elsevier B.V. All rights reserved.