Skip to Main content Skip to Navigation

Homology theory for coverage hole detection in wireless sensor networks

Abstract : Homology theory provides new and powerful solutions to address the coverage hole problem in wireless sensor networks (WSNs). They are based on two combinatorial objects named Cech complex and Rips complex. Cech complex can fully characterize coverage properties of a WSN (existence and locations of holes), but it is very difficult to construct. Rips complex is easy to construct but it may miss some coverage holes. In the first part of this thesis, we choose the proportion of the area of holes missed by Rips complex as a metric to evaluate the accuracy of homology based coverage hole detection. Closed form expressions for lower and upper bounds of the proportion are derived. Simulation results are well consistent with the analytical lower and upper bounds, with maximum differences of 0.5% and 3%. In addition, we extend the analysis to the sphere case. In the second part, we first propose a graph based distributed algorithm to detect non-triangular holes. This algorithm exhibits high complexity. We thus propose another efficient homology based distributed algorithm. This algorithm only requires 1- and 2-hop neighbour nodes information and has the worst case complexity O(n3) where n is the maximum number of 1-hop neighbour nodes. It can accurately detect the boundary cycles of about 99% coverage holes in about 99% cases.
Keywords : Simplicial homology
Complete list of metadata

Cited literature [104 references]  Display  Hide  Download
Contributor : ABES STAR :  Contact
Submitted on : Friday, November 27, 2015 - 11:52:14 AM
Last modification on : Friday, July 31, 2020 - 10:44:08 AM
Long-term archiving on: : Sunday, February 28, 2016 - 11:41:13 AM


Version validated by the jury (STAR)


  • HAL Id : tel-01234691, version 1



Feng Yan. Homology theory for coverage hole detection in wireless sensor networks. Networking and Internet Architecture [cs.NI]. Télécom ParisTech, 2013. English. ⟨NNT : 2013ENST0049⟩. ⟨tel-01234691⟩



Record views


Files downloads