Latency constrained aggregation in sensor networks

L. Becchetti, P. Korteweg, A. Marchetti Spaccamela, M. Skutella, L. Stougie, A. Vitaletti

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

22 Citaten (Scopus)


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 data freshness; 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 transmission paths that form a tree rooted at the sink. We prove that the off-line 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 on-line by simple distributed algorithms in the nodes. In this context we consider both the case in which sensor nodes are synchronized or not. We consider distributed on-line algorithms and use competitive analysis to assess their performance.
Originele taal-2Engels
TitelAlgorithms - ESA 2006 (Proceedings 14th Annual European Symposium, Zürich, Switzerland, September 11-13, 2006)
RedacteurenY. Azar, T. Erlebach
Plaats van productieBerlin
ISBN van geprinte versie3-540-38875-3
StatusGepubliceerd - 2006

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743


Duik in de onderzoeksthema's van 'Latency constrained aggregation in sensor networks'. Samen vormen ze een unieke vingerafdruk.

Citeer dit