Connectivity-Based Distributed Coverage Hole Detection in Wireless Sensor Networks

Coverage is considered as an important measure of quality of service provided by a wireless sensor network (WSN). Yet, coverage holes may appear in the target field due to random deployment, depletion of sensor power or sensor destruction. Discovering the boundaries of coverage holes is important for patching the sensor network. In this paper, we adopt two types of simplicial complexes called Cech complex and Rips complex to capture coverage holes and classify coverage holes to be triangular and non-triangular. A distributed algorithm with only connectivity information is proposed for non-triangular holes detection. Some hole boundary nodes are found first and some of them initiate the process to detect coverage holes. Simulation results show that the area percentage of triangular holes is always below 0.03% when the ratio between communication radius and sensing radius of a sensor is two. It is also shown that our algorithm can discover most non-triangular coverage holes.