Generic Coverage Verification without Location Information Using Dimension Reduction

Wireless Sensor Networks (WSNs) have recently emerged as a key sensing technology with diverse civilian and military applications. In these networks, a large number of small sensors or nodes perform distributed sensing of a target field. Each node is capable of sensing events of interest within its sensing range and communicating with neighboring nodes. The target field is said to be k-covered if every point in it is within the sensing range of at least k sensors, where k is any positive integer. We present a comprehensive framework for verifying k-coverage of a d-dimensional target field for arbitrary positive integers k, d. Our framework uses a divide and conquer approach based on the technique of dimension reduction, in which the k-coverage verification problem in d-dimensions is reduced to a number of coverage verification problems in (d-1) dimensions, which are then recursively solved. Our framework leads to a distributed polynomial-time coverage verification algorithm that does not require knowledge of the locations of nodes or directional information, which is difficult to obtain in WSNs. Each node can execute the algorithm using only the distances between adjacent nodes within its transmission range and their sensing radii. We analytically prove that the scheme detects a coverage hole if and only if the target field has a coverage hole.