Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication

3.2 COVERAGE AND CONNECTIVITY CRITERIA

Coverage and connectivity criteria serve as building blocks in area coverage algorithms by providing computationally efficient ingredients. The choice of criteria depends on the ratios of SR and transmission radius and their uniformity.

If the SR and transmission radius are equal, the coverage property can be tested by verifying whether or not the whole perimeter of the sensing circle is covered by other circles. In the example in Figure 3.2a, sensing area of node O is not fully covered by two other circles since there are two uncovered segments. The correctness of the criterion follows from the following observation: If two sensing circles intersect, then each center is inside the other circle. If point A on the perimeter of circle O is covered by a circle centered at P, all points on the line segment from A to center O are covered by the same circle since both O and A are inside the circle centered at P and the sensing area of any circle is convex. Therefore, instead of testing the whole line segment OA for inclusion in an other circle, only endpoint A on the circle perimeter needs to be checked. Note that this (and the following) criteria assume that no two sensors are placed at the same location.

Figure 3.2 Perimeter-based coverage test.

This criterion can be generalized to the case of k-coverage. The monitoring region is k-covered if and ...