A homology-based coverage hole detection algorithm in wireless sensor networks

摘要

In wireless sensor networks (WSNs), coverage holes may appear because of sensors' random deployment, sensor destruction or consumption of sensor power. Discovery of boundaries of coverage holes is important for repairing these holes and optimizing the whole network. In this paper, we use Rips complex as system model based on homology knowledge. We adopt a detection algorithm to find non-triangular holes only dependent on the connectivity information between sensors. Rely on the definition promoted, we can find all boundary edges and then initiate the process of finding coverage holes. We prove that our algorithm can reduce computation complexity of coverage holes detection by comparing with another homology-based method. And simulation results show that our algorithm can discover almost all non-triangular holes with the accuracy reaching up to 99.99%.