An Algorithmic View on Sensor Networks

The book covers the PhD thesis "An Algorithmic View on Sensor Networks - Surveillance, Localization, and Communication" by Dennis Schieferdecker. It focuses on scalability issues of sensor networks and presents efficient solutions for three distinct problems: First, the optimization of schedules for monitoring areas in an energy-constraint setting is considered. It is shown that it is NP-hard to find optimal activation schedules, and an EPTAS algorithm is provided. Second, the location-free detection of network boundaries is studied, and a distributed algorithm that only requires local connectivity information is proposed. Finally, the efficient computation of optimal routes in a sensor network is considered. An FPTAS for computing shortest paths and an algorithm for determining alternative routes are introduced. Theoretical and simulational results are presented for each problem.