Break-and-join tree construction for latency-aware data aggregation in wireless sensor networks

Emerging applications require processing a huge amount of environmental data from wireless sensor networks, and then triggering appropriate actions in response to the detected events. To this end, it is desirable to minimize the time needed for data aggregation. This paper investigates the minimum-latency aggregation scheduling problem in wireless sensor networks. We propose an aggregation tree construction algorithm called Break-and-Join which adjusts any aggregation tree toward a smaller delay one. In order to perform tree adjustments, the algorithm iteratively changes parent of some nodes in the tree, using a novel numerical metric as a tree quality guideline. Each node determines if it can adopt an additional child in the neighborhood in order to relax the aggregation load at some bottleneck node in the network, thereby improving the overall aggregation tree quality. We performed the algorithm on several state-of-the-art aggregation schemes, and the results shows that final aggregation delay is quite indifferent to choice of initial tree and the tree quality can be significantly improved (e.g. 7 times for shortest path tree). Scheduling on the obtained trees also outperforms the best known scheme up to 13% in terms of delay.