A sensor network consists of sensing devices which may exchange data through wireless communication; sensor networks are highly energy constrained since they are usually battery operated. Data aggregation is a possible way to save energy consumption: nodes may delay data in order to aggregate them into a single packet before forwarding them towards some central node (sink). However, many applications impose constraints on the maximum delay of data; this translates into latency constraints for data arriving at the sink. We study the problem of data aggregation to minimize maximum energy consumption under latency constraints on sensed data delivery, and we assume unique communication paths that form an intree rooted at the sink. We prove that the offline problem is strongly NP-hard and we design a 2-approximation algorithm. The latter uses a novel rounding technique. Almost all real-life sensor networks are managed online by simple distributed algorithms in the nodes. In this context we consider both the case in which sensor nodes are synchronized or not. We assess the performance of the algorithm by competitive analysis. We also provide lower bounds for the models we consider, in some cases showing optimality of the algorithms we propose. Most of our results also hold when minimizing the total energy consumption of all nodes. © 2009 ACM.

Latency-constrained aggregation in sensor networks / Becchetti, Luca; MARCHETTI SPACCAMELA, Alberto; Vitaletti, Andrea; P., Korteweg; M., Skutella; L., Stougie. - In: ACM TRANSACTIONS ON ALGORITHMS. - ISSN 1549-6325. - 6:1(2009), pp. 1-20. [10.1145/1644015.1644028]

Latency-constrained aggregation in sensor networks

BECCHETTI, Luca;MARCHETTI SPACCAMELA, Alberto;VITALETTI, Andrea;
2009

Abstract

A sensor network consists of sensing devices which may exchange data through wireless communication; sensor networks are highly energy constrained since they are usually battery operated. Data aggregation is a possible way to save energy consumption: nodes may delay data in order to aggregate them into a single packet before forwarding them towards some central node (sink). However, many applications impose constraints on the maximum delay of data; this translates into latency constraints for data arriving at the sink. We study the problem of data aggregation to minimize maximum energy consumption under latency constraints on sensed data delivery, and we assume unique communication paths that form an intree rooted at the sink. We prove that the offline problem is strongly NP-hard and we design a 2-approximation algorithm. The latter uses a novel rounding technique. Almost all real-life sensor networks are managed online by simple distributed algorithms in the nodes. In this context we consider both the case in which sensor nodes are synchronized or not. We assess the performance of the algorithm by competitive analysis. We also provide lower bounds for the models we consider, in some cases showing optimality of the algorithms we propose. Most of our results also hold when minimizing the total energy consumption of all nodes. © 2009 ACM.
2009
data aggregation; competitive analysis; wireless sensor networks; distributed algorithms
01 Pubblicazione su rivista::01a Articolo in rivista
Latency-constrained aggregation in sensor networks / Becchetti, Luca; MARCHETTI SPACCAMELA, Alberto; Vitaletti, Andrea; P., Korteweg; M., Skutella; L., Stougie. - In: ACM TRANSACTIONS ON ALGORITHMS. - ISSN 1549-6325. - 6:1(2009), pp. 1-20. [10.1145/1644015.1644028]
File allegati a questo prodotto
File Dimensione Formato  
VE_2009_11573-226570.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 222.7 kB
Formato Adobe PDF
222.7 kB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/226570
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 25
  • ???jsp.display-item.citation.isi??? 19
social impact