Topological and combinatorial coverage hole detection in coordinate-free wireless sensor networks

Abstract

Wireless sensor network WSN coverage completeness is an important quality of service QoS. It is frequently assumed that events occurring in the sensor field can always be detected. However, this is not necessarily the case, particularly if there are holes in the sensor network coverage. This paper introduces a novel centralised method for detection and relative localisation of WSN coverage holes in coordinate-free networks. We identify sensor nodes that surround or bound coverage holes, called 'hole boundary-nodes', by processing information embedded in a communication graph, which is non-planar in general. We create a hole-equivalent planar graph that has the same number and position of holes as the original sensor network graph while preserving the embedding. Finally, we build a plane simplicial complex, called maximal simplicial complex, which contains the information regarding coverage holes. Simulation results are presented to illustrate the proposed method and evaluate its accuracy and run time.