کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
432721 | 689048 | 2014 | 19 صفحه PDF | دانلود رایگان |
• 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.
Journal: Journal of Parallel and Distributed Computing - Volume 74, Issue 7, July 2014, Pages 2596–2614