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

Authors: Saba Ramazani; Jinko Kanno; Rastko R. Selmic; Matthias R. Brust

Addresses: Center for Secure Cyberspace, Louisiana Tech University, Ruston, LA 71272, USA ' Center for Secure Cyberspace, Louisiana Tech University, Ruston, LA 71272, USA ' Center for Secure Cyberspace, Louisiana Tech University, Ruston, LA 71272, USA ' Center for Secure Cyberspace, Louisiana Tech University, Ruston, LA 71272, USA

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.

Keywords: coverage holes; WSNs; wireless sensor networks; network coverage; simplicial complex; coverage hole detection; quality of service; QoS; coordinate-free networks; planar graphs; simulation.

DOI: 10.1504/IJSNET.2016.076860

International Journal of Sensor Networks, 2016 Vol.21 No.1, pp.40 - 52

Received: 19 Apr 2015
Accepted: 15 May 2015

Published online: 04 Jun 2016 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article