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.
Type de document :
Communication dans un congrès
Pacific Rim International Symposium on Dependable Computing, Nov 2009, Shanghai, China. 2009
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00432380
Contributeur : Chrsitopher Thraves Caro <>
Soumis le : lundi 16 novembre 2009 - 12:47:22
Dernière modification le : jeudi 15 novembre 2018 - 11:57:35
Document(s) archivé(s) le : mardi 16 octobre 2012 - 14:10:15

Fichier

PRDC09.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00432380, version 1

Citation

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. 2009. 〈inria-00432380〉

Partager

Métriques

Consultations de la notice

298

Téléchargements de fichiers

201