An Algorithmic View on Sensor Networks - Surveillance, Localization, and Communication
Institut für Theoretische Informatik
- Date: July 2014
This thesis focuses on scalability issues of diverse problems on sensor networks and present 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 connectivy information. Finally, we introduce an FPTAS for computing shortest paths and describe an algorithm for determining alternative routes.