SCIENCE@home

Optimally Approximating the Coverage Lifetime of Wireless Sensor Networks

A. Pananjady,V. Bagaria,R. Vaze

Published 2013 in IEEE/ACM Transactions on Networking

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 <inline-formula> <tex-math notation="LaTeX">$\ln n$ </tex-math></inline-formula> by any polynomial time algorithm, where <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> is the number of targets. This provides closure to the long-standing open problem of showing optimality of previously known <inline-formula> <tex-math notation="LaTeX">$\ln n$ </tex-math></inline-formula> approximation algorithms. We also derive a new <inline-formula> <tex-math notation="LaTeX">$\ln n$ </tex-math></inline-formula> approximation to the problem by showing the <inline-formula> <tex-math notation="LaTeX">$\ln n$ </tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">$1+\epsilon $ </tex-math></inline-formula> 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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-32 of 32 references · Page 1 of 1

CITED BY

Showing 1-39 of 39 citing papers · Page 1 of 1