KIT | KIT-Bibliothek | Impressum | Datenschutz

Lifetime Maximization of Monitoring Sensor Networks

Schieferdecker, Dennis; Sanders, Peter


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.

Volltext §
DOI: 10.5445/IR/1000020376
Cover der Publikation
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
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
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page