Line coverage measures in wireless sensor networks

• The paper measures a quality of sensor deployment.
• The smallest kk-covered line segment computation problem considers the intruders’ perspective.
• The largest kk-uncovered line segment computation problem considers the defenders’ perspective.

The coverage problem in wireless sensor networks addresses the problem of covering a region with sensors. Many different definitions of coverage are there in the literature depending on the goal of the coverage. In this paper, we address the problem of determining the quality of a sensor deployment against an intruder who can walk along a straight line. A line segment ℓℓ is said to be k-covered   if it intersects the sensing regions of at least kk sensors distributed in RR. Similarly, it is said to be k-uncovered   if it intersects the sensing regions, that is assumed to be circular, of at most k−1k−1 sensors. We introduce two new metrics, smallest  kk-covered line segment and longest  kk-uncovered line segment, for measuring the quality of line coverage achieved by a sensor deployment. The intruder can walk a distance less than the smallest  kk-covered line segment   without ever being detected by kk sensors. So, this metric gives an estimate on the distance an intruder can walk in a straight line path before being detected by kk sensors. On the other side, the defender would want to deploy sensors so that the length of the longest  kk-uncovered line segment   is minimized. Given a deployment of nn sensors, we propose deterministic algorithms to determine the smallest  kk-covered line segment and longest  kk-uncovered line segment   where the line segments can be of the following types: (i) axis-parallel (horizontal and vertical) line segments, (ii) line segments whose one endpoint is fixed and is of arbitrary orientation and (iii) arbitrary line segments. The time complexities for the first and second types of line segments are O((n+χ)logn)O((n+χ)logn) for both smallest  kk-covered line segment and longest  kk-uncovered line segment  , where χχ is the number of intersections among nn circles. For the arbitrary line segment case, the smallest  kk-covered segment   can be determined in O(χ2logn+n113+ϵ) time, whereas, the longest  kk-uncovered segment   can be determined in O(χ2logn+n2+β+ϵ)O(χ2logn+n2+β+ϵ) time, where β=log2(1+5)−1 and ϵϵ is a small value greater than or equal to 00. All our algorithms take linear space.