KIT | KIT-Bibliothek | Impressum

An Algorithmic View on Sensor Networks - Surveillance, Localization, and Communication

Schieferdecker, Dennis

Abstract:
This thesis focuses on scalability issues of diverse problems on sensor networks and presents efficient solutions. First, we show that it is NP-hard to find optimal activation schedules for monitoring areas and provide an EPTAS algorithm. Second, we present a distributed algorithm for the detection of network boundaries that only requires local connectivity information. Finally, we introduce an FPTAS for computing shortest paths and describe an algorithm for determining alternative routes.


Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Jahr 2014
Sprache Englisch
Identifikator URN: urn:nbn:de:swb:90-431413
KITopen ID: 1000043141
Verlag Karlsruhe
Abschlussart Dissertation
Fakultät Fakultät für Informatik (INFORMATIK)
Institut Institut für Theoretische Informatik (ITI)
Prüfungsdaten 17.07.2014
Referent/Betreuer Prof. P. Sanders
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page