Aggregation methods for large-scale sensor networks

The ability to efficiently aggregate information - for example compute the average temperature - in large networks is crucial for the successful employment of sensor networks. This article addresses the problem of designing truly scalable protocols for computing aggregates in the presence of faults, protocols that can enable million node sensor networks to work efficiently. More precisely, we make four distinct contributions. First, we introduce a simple fault model and analyze the behavior of two existing protocols under the fault model: tree aggregation and gossip aggregation. Second, since the behavior of the two protocols depends on the size of the network and probability of failure, we introduce a hybrid approach that can leverage the strengths of the two protocols and minimize the weaknesses; the new protocol is analyzed under the same fault model. Third, we propose methodology for determining the optimal mix between the two basic protocols; the methodology consists in formulating an optimization problem, using models of the protocol behavior, and solving it. Fourth, we perform extensive experiments to evaluate the performance of the hybrid protocol and show that it usually performs better, sometimes orders of magnitude better, than both the tree and gossip aggregation.