We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Approximation algorithms for deployment of sensors for line segment coverage in wireless sensor networks.
- Authors
Dash, Dinesh; Bishnu, Arijit; Gupta, Arobinda; Nandy, Subhas
- Abstract
The coverage problem in wireless sensor networks deals with the problem of covering a region or parts of it with sensors. In this paper, we address the problem of covering a set of line segments with minimum number of sensors. A line segment ℓ is said to be 1-covered if it intersects the sensing region of at least one among the sensors distributed in a bounded rectangular region R. We assume that the sensing radius of each sensor is uniform. The problem of finding the minimum number of sensors needed to 1-cover each member in a given set of line segments in R is NP-hard. We propose two constant factor approximation algorithms and a PTAS (polynomial time approximation scheme) for the problem for 1-covering a set of axis-parallel line segments. We also show that a PTAS exists for 1-covering a set of arbitrarily oriented line segments in R where the lengths of the line segments are bounded within a constant factor of the sensing radius of each sensor. Finally, we propose a constant factor approximation algorithm for k-covering axis-parallel line segments such that sensors maintain a minimum separation among them.
- Subjects
WIRELESS sensor networks; APPROXIMATION algorithms; POLYNOMIAL time algorithms; DETECTORS; SENSOR placement
- Publication
Wireless Networks (10220038), 2013, Vol 19, Issue 5, p857
- ISSN
1022-0038
- Publication type
Article
- DOI
10.1007/s11276-012-0506-4