Latency-minimizing data aggregation in wireless sensor networks under physical interference model

Minimizing latency is of primary importance for data aggregation which is an essential application in wireless sensor networks. Many fast data aggregation algorithms under the protocol interference model have been proposed, but the model falls short of being an accurate abstraction of wireless interferences in reality. In contrast, the physical interference model has been shown to be more realistic and has the potential to increase the network capacity when adopted in a design. It is a challenge to derive a distributed solution to latency-minimizing data aggregation under the physical interference model because of the simple fact that global-scale information to compute the cumulative interference is needed at any node. In this paper, we propose a distributed algorithm that aims to minimize aggregation latency under the physical interference model in wireless sensor networks of arbitrary topologies. The algorithm uses O(K) time slots to complete the aggregation task, where K is the logarithm of the ratio between the lengths of the longest and shortest links in the network. The key idea of our distributed algorithm is to partition the network into cells according to the value K, thus obviating the need for global information. We also give a centralized algorithm which can serve as a benchmark for comparison purposes. It constructs the aggregation tree following the nearest-neighbor criterion. The centralized algorithm takes O(log n) and O(log(3) n) time slots when coupled with two existing link scheduling strategies, respectively (where n is the total number of nodes), which represents the current best algorithm for the problem in the literature. We prove the correctness and efficiency of our algorithms, and conduct empirical studies under realistic settings to validate our analytical results. (C) 2011 Elsevier B.V. All rights reserved.