Approximation algorithms for deployment of sensors for line segment coverage in wireless sensor networks

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.

Authors and Affiliations

1. Department of Computer Science and Engineering, Indian Institute of Technology, Kharagpur, India

   Dinesh Dash & Arobinda Gupta

2. Advanced Computing and Microelectronics Unit, Indian Statistical Institute, Kolkata, India

   Arijit Bishnu & Subhas C. Nandy

Corresponding author

Correspondence to Arobinda Gupta.

Appendix: O(n log n) Time 8-approximation algorithm

We employ a plane sweep for finding the maximal independent set for the horizontal segments. A similar technique would be employed for the vertical segments.

A vertical line sweeps from left to right. There are two types of event points per line segment—the left endpoint and right endpoint. The endpoints are sorted from left to right and are stored in a list L. The top to bottom order (in terms of y-coordinates) of the line segments intersecting the vertical sweep line is maintained in a balanced binary search tree, T ₁. Whenever the left endpoint of a line segment is encountered by the sweep line, the line segment is deleted from L and inserted into T ₁ based on its y-coordinate. Whenever the sweep line encounters the right endpoint of a line segment ℓ, the line segment is deleted from T ₁ and the following actions are performed. We need to also delete all other line segments which are at a distance 2 ρ from ℓ. Let the y-coordinate of ℓ be y(ℓ). We do an interval query on T ₁ with the interval [y(ℓ) − 2ρ, y(ℓ) − 2ρ ] and delete all line segments that lie within this interval. There may be other line segments which are at a distance 2 ρ from ℓ. The left endpoints of such line segments lie within a half-circle of radius 2 ρ centered at the right endpoint of ℓ (see the half-circle \({{\mathcal C}}\) in Fig. 9a). As circular range queries are costly, we do it using rectangular range queries. Specifically, we keep a fractional cascading based range searching structure [13] T ₂ on the endpoints of the line segments. T ₂ needs O(n log n) space. We query T ₂ with a query rectangle \({{\mathcal D}}\) (see Fig. 9(a)) of size \({4\rho \times 2 \rho;\, {\mathcal D}}\) is hinged at the right endpoint of ℓ. This reporting query takes O(log n + k) time where k is the number of points inside \({{\mathcal D}.}\) We test these k points for inclusion in \({{\mathcal C}.}\) Line segments whose left endpoints lie inside \({{\mathcal C}}\) are deleted from T ₁ and L. The line segments whose left endpoints lie within the region \({{\mathcal D} \setminus {\mathcal C}}\) (see the shaded region in Fig. 9 and the line segments whose left endpoints lie in \({{\mathcal D} \setminus {\mathcal C}}\)) lie at a distance greater than 2 ρ from the right endpoint of ℓ and as such cannot be deleted. We call such a line segment as a false line. A line segment can be a false line if its left endpoint lies in \({{\mathcal D} \setminus {\mathcal C}}\) for a rectangular range query initiated on encountering a right endpoint of a line segment during the plane sweep. The following lemma shows that a line segment can be a false line at most twice.

(a) The query in the line sweep algorithm; \({{\mathcal C}}\) denotes the half-circle of radius \({2 \rho, \,{\mathcal D}}\) denotes the query rectangle of size 4 ρ × 2 ρ; line segments whose left endpoints are in \({{\mathcal D} \setminus {\mathcal C}}\) (the shaded region) are false lines; (b) an example showing that false reporting is O(1)

Full size image

Lemma 12

A line segment can be a false line at most twice.

Proof

Consider a line segment ℓ′ that is a false line. ℓ′ can be reported as a false line by a rectangular range query initiated on encountering a right endpoint of a line segment that has to be at a distance greater than 2 ρ from the left endpoint of ℓ′ (and hence, outside the half-circle \({{\mathcal C}'}\) of radius 2 ρ as in Fig. 9(b)) but inside the query rectangle of size 4 ρ × 2ρ (and hence, inside \({{\mathcal D}'}\) of size 4 ρ × 2ρ as in Fig. 9(b)). Thus, ℓ′ can be a false line for line segments whose right endpoints lie inside the region \({{{\mathcal D}'} \setminus {{\mathcal C}'}. }\) As our algorithm deletes line segments within a vertical distance of 2 ρ, there can be only two such lines as shown in Fig. 9(b).\(\square\)

Theorem 8

The plane sweep algorithm for the 8-approximation algorithm takes O(n log n) time and space.

Proof

We focus on a line segment and try to find the time spent per line segment. As any line segment in L can be a false line at most twice (because of Lemma 12), the total time spent for all line segments in this regard is O(n). A line segment once deleted from L because of the range query never appears in the plane sweep. As deletion would take O(log n) time, the total time taken in this regard is O(n log n). Apart from these, the operations per line segment are—(1) insertion into T ₁ and (2) a range query on T ₂ and subsequent deletion of that line segment from T ₁ and L. All these operations take O(log n) time per line segment. Thus, the total time taken is O(n log n). The space needed for L and T ₁ is O(n), but T ₂ takes O(n log n), thus making the space complexity also O(n log n). \(\square\)

Reprints and permissions