Skip to Main content Skip to Navigation
Conference papers

An Early-stopping Protocol for Computing Aggregate Functions in Sensor Networks

Abstract : In this paper, we study algebraic aggregate com- putations in Sensor Networks. The main contribution is the presentation of an early-stopping protocol that computes the average function under a harsh model of the conditions under which sensor nodes operate. This protocol is shown to be time-optimal in presence of unfrequent failures. The approach followed saves time and energy by relying the computation on a small network of delegate nodes that can be rebuilt fast in case of node failures and communicate using a collision- free schedule. Delegate nodes run simultaneously two protocols, namely, a collection/dissemination tree-based algorithm, which is shown to be optimal, and a mass-distribution algorithm. Both algorithms are analyzed under a model where the frequency of failures is a parameter. Other aggregate computation algo- rithms can be easily derived from this protocol. To the best of our knowledge, this is the first optimal early-stopping algorithm for aggregate computations in Sensor Networks.
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download
Contributor : Chrsitopher Thraves Caro Connect in order to contact the contributor
Submitted on : Monday, November 16, 2009 - 12:47:22 PM
Last modification on : Thursday, January 20, 2022 - 4:20:10 PM
Long-term archiving on: : Tuesday, October 16, 2012 - 2:10:15 PM


Files produced by the author(s)


  • HAL Id : inria-00432380, version 1


Antonio Fernández Anta, Miguel Mosteiro, Christopher Thraves-Caro. An Early-stopping Protocol for Computing Aggregate Functions in Sensor Networks. Pacific Rim International Symposium on Dependable Computing, Nov 2009, Shanghai, China. ⟨inria-00432380⟩



Record views


Files downloads