A Coverage Hole Identification Scheme for Wireless Sensor Networks Based on Elfes Model

Coverage is an important metric for evaluating quality of service provided by wireless sensor networks (WSNs). Due to random deployment of nodes, events such as node energy exhaustion or node failure will lead to emergence of coverage holes in the sensing field and affect quality of service provided by wireless sensor networks. This paper proposes an efficient coverage hole identification algorithm under the Elfes model by a given threshold detection probability. The idea of the proposed algorithm is to first construct candidate coverage holes within the maximum sensing range around a faulty node by eliminating redundant area within it formed by its neighbors. Given the candidate coverage holes and specified threshold detection probability, coverage holes are identified under the Elfes model by random sampling. Compared with the existing work under the Elfes model, simulation results show that the presented algorithm significantly reduce the number of random points to be sampled when identifying coverage holes. In addition, when there are no coverage holes around a faulty node, no random sampling is necessary for our scheme. Hence efficiency of coverage hole identification is improved.