# An Efficient Distributed Coverage Hole Detection Protocol for Wireless Sensor Networks
## 1 Introduction  
With the advance of microelectromechanical systems (MEMS) technology, wireless sensor networks (WSNs) [1] play an important role in transportation, infrastructures and forest monitoring for animals or fire [2; 3], with its inexpensive, small size and multi-functional abilities. Normally, a wireless sensor network is composed of a large number of sensors deployed over the monitoring region regularly or randomly, and the deployed sensors are self-organized [4] to form the network. Since a random deployment is usually used in WSNs, the study of coverage issues is very important, which should be studied deeply in addition to the localization, target tracking and time synchronization in WSNs. However, a sensor node is severely constrained by the resources, such as limited memory, battery power, computation and communication capabilities. The energy consumption of each sensor is a function of its own sensing and communication range, and designing algorithms for deployment, localization, duty cycle, coverage and other issues is most important in WSNs. The sensors are deployed randomly over a monitoring region with a high degree of density of nodes. Due to the random deployment strategy, certain areas of the monitoring region may have coverage holes [5; 6] or serious coverage overlapping, which significantly degrade the network performance. Besides, the failure of electronic components, software bugs and destructive agents could lead to the random death of the nodes, and also, nodes may die due to the exhaustion of batterypower, which may cause the network to be uncovered and disconnected. Since sensors are deployed in remote or hostile environments, such as a battlefield or desert, it is impossible to recharge or replace the battery. However, the data gathered by the sensors are highly critical and may be of scientific or strategic importance. Hence, the coverage provided in the sensor networks is a critical criterion of their effectiveness, and its maintenance is highly essential to form a robust network. The study of such coverage issues means summing of the sensing and communication range, which should be ideal in the monitoring area to provide good QoS for different applications. Sensing coverage is a fundamental problem in WSNs and has been well studied over the past few years. However, most of the previous works address only one kind of redundancy, _i.e._, sensing or communication alone. The authors in [7] address how to combine coverage and connectivity maintenance in a single activity scheduling. In this work, it is proven that the communication range is at least twice the sensing range, which is the sufficient condition to ensure that a full coverage of a convex area implies connectivity among active nodes. In WSNs, nodes are deployed randomly, and it is hard or impossible to guarantee complete coverage of the monitored region, even if the node density is very high. Based on the deployment nature of the wireless sensor networks, the authors in [8] consider the communication range to be twice the sensing range, which is the sufficient condition and tight lower bound to ensure that the complete coverage preservation implies connectivity among active nodes, if the original network topology is connected. In WSNs, due to the random deployment of the nodes, some areas cannot be covered [9; 10; 11] or have no connectivity. If a coverage region is sensed by at least \(k\) nodes, this sensing method is called \(k\)-covered, and the maintenance of a \(k\)-covered region is discussed in [12; 13; 14]. The coverage probability plays a fundamental role in coverage hole detection and other applications of WSNs, because of existing errors in the sensing and communication range [15; 16]. Holes are hardly avoided in WSNs due to the various geographical environments of the monitoring region, such as the presence of ponds, obstacles or even due to physical destruction of the nodes.