KIT | KIT-Bibliothek | Impressum | Datenschutz

Lifetime Maximization of Monitoring Sensor Networks

Schieferdecker, Dennis; Sanders, Peter ORCID iD icon

Abstract:

We study the problem of maximizing the lifetime of a sensor network assigned to monitor a given area. Our main result is a linear time dual approximation algorithm that comes arbitrarily close to the optimal solution if we additionally allow the sensing ranges to increase by a small factor. The best previous result is superlinear and has a logarithmic approximation ratio. We also provide the first proof of the NP completeness of this specific problem.

Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2010
Sprache Englisch
Identifikator ISBN: 978-3-642-16987-8
ISSN: 0302-9743
urn:nbn:de:swb:90-203768
KITopen-ID: 1000020376
Erschienen in Algorithms for Sensor Systems - 6th International Workshop on Algorithms for Sensor Systems, Wireless Ad Hoc Networks, and Autonomous Mobile Entities, ALGOSENSORS 2010, Bordeaux, France, July 5, 2010; Revised Selected Papers. Ed.: Ch. Scheideler
Auflage 1
Verlag Springer-Verlag
Seiten 134 - 147
Serie Lecture Notes in Computer Science ; 6451

Volltext §
DOI: 10.5445/IR/1000020376
Seitenaufrufe: 296
seit 04.09.2018
Downloads: 514
seit 25.08.2011
Cover der Publikation
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page