Decentralized detection and patching of coverage holes in wireless sensor networks

Abstract

Detection and patching of coverage holes in Wireless Sensor Networks (WSNs) are important measures of Quality of Service (QoS) for security and other applications that emphasize sensor network coverage. In this paper, we model a WSN using simplicial complexes based on its communication graph by which the network can be represented as connections of sensor nodes without knowing exact locations of nodes. Thus, the coverage problem is converted to a connectivity problem under some assumptions presented in the paper. We discuss two major topics in this paper, namely sensor network coverage hole detection and patching. We present a novel, decentralized, coordinate-free, node-based coverage hole detection algorithm. The algorithm can be implemented on a single node with connectivity information gathered from one-hop away neighbors. Thus, the coverage hole detection algorithm can be run on individual nodes and does not require time-consuming, centralized data processing. The hole-patching algorithm is based on the concept of perpendicular bisector line. Every hole-boundary edge has a corresponding perpendicular bisector and new sensor nodes are deployed on hole-boundary bisectors. Deployment of new sensor nodes maintains network connectivity, while reduces coverage holes.