Name
Abstract | ||
|---|---|---|
We address a classical problem concerning energy efficiency in sensor networks. In particular, we consider the problem of maximizing the lifetime of coverage of targets in a wireless sensor network with battery-limited sensors. We first show that the problem cannot be approximated within a factor less than lnn by any polynomial time algorithm, where n is the number of targets. This provides closure to the long-standing open problem of showing optimality of previously known lnn approximation algorithms. We also derive a new ln n approximation to the problem by showing the lnn approximation to the related maximum disjoint set cover problem. We show that this approach has many advantages over algorithms in the literature, including a simple and optimal extension that solves the problem with multiple coverage constraints. For the 1-D network topology, where sensors can monitor contiguous line segments of possibly different lengths, we show that the optimal coverage lifetime can be found in polynomial time. Finally, for the 2-D topology in which coverage regions are unit squares, we combine the existing results to derive a 1 + € approximation algorithm for the problem. Extensive simulation experiments validate our theoretical results, showing that our algorithms not only have optimal worst case guarantees but also match the performance of the existing algorithms on special network topologies. In addition, our algorithms sometimes run orders of magnitude faster than the existing state of the art. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1109/TNET.2016.2574563 | IEEE/ACM Transactions on Networking (TON) |
Keywords | Field | DocType |
Approximation algorithms,Batteries,Monitoring,Silicon,Network topology,Wireless sensor networks,Schedules | Maximum coverage problem,Maximum disjoint set,Approximation algorithm,Open problem,Computer science,Time complexity,Wireless sensor network,Distributed computing | Journal |
Volume | Issue | ISSN |
25 | 1 | 1063-6692 |
Citations | PageRank | References |
5 | 0.42 | 19 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ashwin Pananjady | 1 | 40 | 9.69 |
| Vivek Kumar Bagaria | 2 | 22 | 3.98 |
| Rahul Vaze | 3 | 463 | 45.64 |