A distributed collapse of a network´s dimensionality

Algebraic topology has been successfully applied to detect and localize sensor network coverage holes with minimal assumptions on sensor locations. These methods all use a computation of topological invariants called homology spaces. We develop a distributed algorithm for collapsing a sensor network, hence simplifying its analysis. We prove that the collapse is equivalent to a previously developed strong collapse in that it preserves coverage hole locations. In this way, the collapse simplifies the network without losing crucial information about the coverage region. We show that the algorithm requires only one-hop information in a communication network, making it faster than clique-finding algorithms that increase the number of computations necessary for hole localization. This makes it an effective pre-processing step to finding network coverage holes.