Keywords

1 Introduction

In recent years, microelectromechanical systems (MEMS) technology and wireless communication technology together have drawn global attention due to the invention of tiny, economical wireless sensor nodes. These nodes are well organized to sense, evaluate, and collect data from a particular environment, although they have limited amount of power, processing speed, and memory. From mid-1990s exploration in the field of WSN started and among all the research topics, coverage has got the highest preference since last few years. Coverage quantifies how well an area is sensed by the nodes they are deployed into. In the coverage problem, each sensor has to wrap up some subregion and summing up these entire covered subregions one can have a totally covered region in the WSN. Therefore, it is clear that the random deployment of the sensors in the target area cannot promise an optimal solution at the very first attempt. While discussing the deployment strategies, it is assumed that the sensing field will entirely be covered with sensors. But if we see practically just like Fig. 1, there may be several coverage holes, which are the areas not being covered by any sensor. These coverage holes may be created due to several reasons, for example, when sensors are thrown into a battlefield through some in-flight arrangements, the node deployment becomes random in nature as well as unstructured. Therefore, a few gaps may be created unintentionally in the sensing field which results hole in the coverage area. As a result, a few nodes might fail to sense data or communicate with other nodes and finally performance of sensor network may degrade. The rest of the paper is organized as follows: In Sect. 2, we have identified a few reasons behind the creation of holes and discussed why hole detection is important. In Sect. 3, we discussed the categorization of various types of holes found in sensor network. In Sect. 4, there is an elaborate description about hole detection and healing algorithms, especially on coverage hole detection, with respect to various recent literatures. Summarizations of different algorithms are done in Sect. 5. And finally, we have concluded in Sect. 6.

Fig. 1
figure 1

Coverage hole

Full size image

2 Overview of Hole

The prime job of a sensor node is to sense and communicate with other nodes in the network, but when a sensor fails to do so in an area, then that area in the network produces a hole. There are several causes [1] behind the creation of holes, such as:

  • Drainage of power—a sensor node is meaningless without its power source. If the power source is over-used for sensing or communication purpose, then the node will run out of power and hence causing a hole in the network. Generally, coverage and routing holes are created due to power exhaustion.

  • Adverse environment—an adverse environment (e.g., fire in forest) can destroy the nodes and hole may be created in the network. Routing holes are created under such condition.

  • Incorrect design—while designing the network, if there is some ambiguity in the topology, then it will lead to the formation of the coverage hole.

  • Obstacle—due to some obstacle in the sensing field routing or jamming holes can be formed.

  • Node replacement—in place of a faulty node, if a new node is placed, then the route for communication may change which results in routing hole in the network.

Holes are the reason behind the performance deterioration of sensor network. If there is some hole in the network, then communication becomes weak between the nodes due to the fact that, sensed data is routed along the boundary of the hole repeatedly. Therefore, detection of holes is very essential as follows:

  • Identifies whether a node is fully operational or not.

  • Guarantees elongated network lifetime.

  • Provides sufficient quality of service in network coverage by identifying whether each point in sensing field has the compulsory quantity of coverage or not.

  • With the help of hole detection, we can assess whether extra nodes are required in the region of interest (ROI) or not which results speedy covering the holes.

  • Detection of holes prevents data loss in the network. Also, it helps to identify any substitute communication passage to normalize flow of data.

3 Category of Holes in WSN

In 2005, Ahmed et al. [2] have classified network holes in the following four categories: Coverage holes (shown in Fig. 1) [3] are produced due to random deployment of nodes, drainage of battery and faulty network topology. Routing holes (shown in Fig. 2—i) [4] occur due to adverse environmental conditions, obstacle present in the sensing field or replacement of an old node with a new one. If the radio frequency used for communication between sensor nodes is blocked by a jammer with some high-frequency signals then Jamming holes (shown in Fig. 2—iv, v and vi) arise [5]. This jamming can be either intentional or unintentional. The last category (shown in Fig. 2—ii and iii) [6, 7] of hole defined by Ahmed et al. is the Sink/black holes/Wormholes. Denial of service attacks can originate Sink/black holes [8]. In this case, an alternate route suggestion toward sink is provided by an opponent to mislead the neighboring nodes. Wormhole [9] is also initiated through denial of service that comes under malicious holes category.

Fig. 2
figure 2

Different types of holes in sensor network (i) Routing Holes: GPSR—Greedy Perimeter Stateless Routing for WSN (ii) Black Hole attack problem (iii) Wormhole attack to location and neighbor discovery (iv), (v), and (vi) Jamming Holes: Overview of Collaborative mapping of nodes in a jammed region in the network

Full size image

In 2013, Jabeur et al. [10] introduced PLMS (physical/logical/malicious/semantic), a cause-based taxonomy. Physical holes occur due to the limited capacity of processing, overuse of energy or inappropriate sensor nodes. Coverage holes and Routing holes fall into this category. Cluster-based approach, where a sensor node cannot be sustained from its neighboring nodes, initiates Logical holes. Jamming hole, sinkhole, and wormhole belong from the category of Malicious holes and they can occur when a few sensors in the network behaves abnormally. Semantic holes are caused due to processing and routing of data. The authors in [7] also suggested that further categorization of holes can be done on the basis of mobility (static or moving), lifetime (temporary or permanent), purpose (intentional or accidental), and affected function (functional or non-functional).

4 Algorithms for Hole Detection

In this section, we are going to discuss various hole detection algorithms, particularly, coverage hole detection, as numerous works are done on this topic. In 2005, Ghrist and Muhammad [11] have proposed a centralized algorithm that detects holes via homology without prior knowledge of sensor locations. This algorithm detects only single-level coverage holes but unable to detect boundary holes. In 2008, Li and Hunter [12] proposed one distributed algorithm named 3MeSH (Triangle Mesh Self-Healing) that detects the existence of holes and also recover them. This static approach can recover large holes produced by accidental node failure or topology changes in networks. Recovery of trivial holes is also possible depending upon the availability of node location information and the distances between nodes. Kanno et al. [13] in 2009 proposed a distributed method that determines the number of holes along with their location in a non-planar sensor network with a given communication graph. From this non-planar graph, a planar graph is obtained and further divided into subgraphs with the help of ‘partition network’ algorithm. If a subgraph contains no holes, it is eliminated from the list; otherwise, graph is further divided into subgraphs until the holes are adequately bounded. In 2010, Yang and Fei [14] proposed a hole detection and adaptive geographical routing (HDAR) algorithm to detect holes and to deal with local minimum problem. If the angle between two adjacent edges of a node is greater than 120°, then hole detection algorithm is initiated. If for some node the value of hole detection ratio is greater than a pre-defined threshold, then it is on the boundary. Yan et al. [15] in 2011 used the concepts of Rips complex and Cech complex to discover coverage holes and classify coverage holes to be triangular or non-triangular. This is based on topological approach. A distributed algorithm with only connectivity information was proposed for non-triangular holes detection. In 2012, Zeadally et al. [16] proposed a hop-based approach to find holes in sensor networks. There are three phases, namely information collection phase, path construction phase, and finally path checking phase. If the communication path of x-hop neighbors of a node is broken, then it is boundary node. Algorithm works for a node of degree of 7 or higher. Senouci et al. [17], in 2013, proposed a hole detection and healing (HEAL) algorithm. This allows a local healing using hole detection Algorithm (HDA) for detecting the holes and another boundary detection algorithm (BDA) is proposed to identify the boundary holes within the RoI. Moreover, they have used a virtual force-based hole healing algorithm. This algorithm relocates only the adequate nodes within the shortest range.

In the most recent literatures, Ghosh et al. [18] in 2014 has proposed two novel distributed algorithms as DVHD (distance vector hole determination) and GCHD (Gaussian curvature-based hole determination). DVHD uses Bellman–Ford algorithm to calculate the shortest distance path between a pair of nodes in a weighted Delaunay graph. If the distance is less than k, which is a constant greater than number of nodes in the graph, the nodes are treated to be in the same boundary. Otherwise, nodes are in different boundaries and thus resulting holes. GCHD uses Gauss–Bonnet theorem to calculate the distributed curvature to detect the no. of holes.

Li and Zhang [19] in 2015 proposed a novel algorithm to detect coverage holes using ‘empty circle property’ by forming Delaunay triangulation of the network. If empty circle radius Rc is greater than sensing radius Rs, there exists some hole. The holes are further clustered by connecting the center of empty circles of each Delaunay triangle with its neighbor by a line segment.

In 2016, Zhao et al. [20] proposed an algorithm which has two phases namely: distributed sector cover scanning (DSCS), that is, used to identify the nodes on hole borders and the outer boundary of WSN and directional walk (DW) that can locate the coverage holes based on the boundary nodes identified with DSCS.

Sahoo et al. [21] in 2016 proposed a distributed coverage hole detection (DCHD) algorithm to detect the bounded or non-bounded coverage holes in the sensor network. This method uses critical intersection point (CIP) to resolve the faults of the perimeter-based coverage hole detection by reducing the time complexity of coverage hole detection. At first, each sensor finds out its CIP set and then verifies if any point belongs to a covered points (CP) set or not. Finally, each sensor in the clock-wise direction collaborates with its one-hop neighbors and unites to its CIP to detect the occurrence of a coverage hole.

Again in 2016, Beghdad and Lamraoui [22] proposed an algorithm is based on connected independent sets (BDCIS) and is divided into three steps. At first, each node collects connectivity information by sending and receiving messages toward its neighbors and constructs its one-hop neighbors’ graph only. In the second step, independent sets (IS) of cardinality α are established with the help of the minimum or maximum id in the graph Gi, which will be the first element of the IS1. Then by removing all the neighbors of this node from Gi, another node having the minimum id among the remaining nodes is chosen and this process continues to build all other possible ISs. Finally, the independent sets are connected in order to search for the closed path to detect holes based on some rules.

In 2017, Amgoth and Jana [23] proposed an algorithm having two phases namely: coverage hole detection (CHD) and coverage restoration (CR). In CHD, each sensor node separately detects hole by updating certain information with its neighbor nodes. For this information update, a sensor node searches for cells with their coordinates inside its sensing range and then covering the maximum sensing range R*. For CR, a sensor node with comparatively high residual energy is given priority to cover up the hole closer to it by increasing its sensing range up to a maximum limit.

5 Summarization

In the previous section, we have done an extensive review of the most recent literature on coverage hole. In this section, we are going to summarize the literature in a tabular format for the interest of the research community. In Table 1, the final summarization is provided which is primarily carried out with the Distributed Algorithm. Only [11] is from centralized type of algorithm. From this, we can suggest that distributed algorithms for coverage hole detection are much more efficient than centralized one.

Table 1 Summarization of coverage hole detection on the basis of distributed algorithm
Full size table

Also, we have found that maximum of these algorithms follows computational geometry-based approach and topology-based approach. A few also follow other approaches like virtual force based, perimeter based, or mathematical model based. Hence, computational geometry-based approach or graph-based approach may be treated to be the best approach to use for algorithm design. In the table, we have put the algorithms in chronological order according to their year of publishing. Besides that, from all algorithms we have taken a few fields, given in the table, to highlight each algorithm more specifically. The fields are chosen as follows: if any pre-requisites or criteria are required before applying the algorithm, the main characteristics, i.e., the key features of each algorithm, the level of detection of hole and its type, if there is any disadvantage of the given algorithm and finally the simulator required to test the effectiveness of the algorithm. On the basis of these fields, we can have the observation that node location information and connectivity information are two most important prerequisites for algorithm. Also, we have noticed that most of the algorithms face the drawback of failure of detection of holes that fall in boundary locations. Therefore, further research can be done on detection of holes which fall in boundary location. Finally, we can conclude this summarization saying that till date MATLAB may be the best simulator to be used to test the proposed coverage hole detection algorithm.

6 Conclusion

Unlike other networks, WSN is very much application specific and for supporting those multidisciplinary applications, deployment of the nodes should explicitly be defined. While designing the coverage of the sensing field, quality can be jeopardized at the occurrence of hole. Hence, in this paper, we have wrapped up different types of holes and their characteristics, cause of creation of particular hole and reason behind their detection. Among different types of network holes, coverage holes are treated to be the most important to detect, as they play a key position in QoS assurance in WSN. Also, we have shown an elaborate review with respect to the extremely recent literature of coverage hole detection in wireless sensor network. In addition to that, we have reviewed special issues from the available coverage hole detection algorithms from different angles like approach, features, prerequisites, types of algorithm.