.png){kind=icon}
.png){kind=icon}
Return
Line coverage measures in wireless sensor networks
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jpdc.2014.03.004.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 l is said to be k-covered if it intersects the sensing regions of at least k sensors distributed in R. Similarly, it is said to be k-uncovered if it intersects the sensing regions, that is assumed to be circular, of at most k - 1 sensors. We introduce two new metrics, smallest k-covered line segment and longest k-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 k-covered line segment without ever being detected by k sensors. So, this metric gives an estimate on the distance an intruder can walk in a straight line path before being detected by k sensors. On the other side, the defender would want to deploy sensors so that the length of the longest k-uncovered line segment is minimized. Given a deployment of n sensors, we propose deterministic algorithms to determine the smallest k-covered line segment and longest k-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 + x) log n) for both smallest k-covered line segment and longest k-uncovered line segment, where x is the number of intersections among n circles. For the arbitrary line segment case, the smallest k-covered segment can be determined in O(chi(2) log n+ n(11/3+is an element of))In time, whereas, the longest k-uncovered segment can be determined in O(chi(2) log n + n(2+beta+is an element of)) time, where beta = log(2)(1+,root 5) - 1 and is an element of is a small value greater than or equal to O. All our algorithms take linear space. (C) 2014 Elsevier Inc. All rights reserved.
Keywords:
Wireless sensor network
Coverage measures
Line coverage
Geometry
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K