1 Introduction

Wireless sensor networks (WSNs) have a wide variety of applications for sensing and monitoring physical space, such as environmental monitoring, intrusion detection, biological detection, and battlefield surveillance [1,2,3]. In these applications, a large number of sensor nodes (SNs) are deployed over a geographic area to detect the existence or emergence of a certain event or specific target. Typically, every point in a region of interest (RoI) should be covered by at least one SN. However, each SN has a limited sensing range [4,5,6]. Hence, sensing coverage has become a critical factor to consider when deploying the SNs in WSNs [7,8,9,10,11].

Network coverage can be greatly affected by the geometric distribution of the SNs deployed in the network because of the constraints of SNs with limited sensing ranges. In general, a coverage hole may appear anywhere within the RoI if there exists an area in the RoI where not all points are covered by any SN in the network. Deploying a WSN with 100% sensing coverage (full coverage) can become problematic for many reasons, such as random deployment, the existence of obstacles, and energy depletion of some SNs [8,9,10].

A key factor to maximize the area coverage [12] is sensor placement strategies using mobile SNs. In recent years, with the advance in mobile-capable devices, some SNs, such as Robomote, are able to move automatically [13]. The emerging hardware techniques have also promoted the development of mobile sensors [14]. In addition, SNs embedded in moving devices could also help to reduce cost for deploying a WSN by minimizing the number of randomly deployed sensors. With the ability to move autonomously, mobile sensors within a WSN (mobile sensor networks) are able to self-deploy and self-repair [15,16,17,18].

Note that some researchers have focused on designing deployment algorithms to optimize network coverage, called movement-assisted sensor deployment [19,20,21,22]. In this specific deployment, mobile SNs are able to self-configure after an initial deployment to increase network coverage and achieve the area-coverage goal (optimally full coverage). The common goal of these studies is to solve the specific problems of how and where to move these mobile SNs efficiently so that the final deployment satisfies the coverage goal of the network. The main difference among these studies is how the new positions of the SNs are computed [15] (with the goals of minimizing the total movement to manage energy consumption and to prolong the overall network lifetime of the WSN).

In this paper, our key contribution is minimizing the movement cost of mobile SNs by optimizing a hybrid model of two methods, i.e., computational geometry-based and virtual forces-based approaches. First, we focus on the problem of hole-boundary node detection within an RoI. We construct a topology based on Delaunay triangulation. In computational geometry, a Delaunay triangulation for a given set of SNs in a 2D network area is a triangulation such that there is no SN inside the circumcircle of any triangles. We propose a novel algorithm, called coverage hole-healing algorithm (CHHA), based on the topology and the properties of the circumcircles of the Delaunay triangles to detect coverage holes and hole-boundary SNs. Second, after detecting holes, CHHA also includes a hole-healing component. CHHA implements a distributed deployment algorithm to determine the required movements of SNs to heal all possible coverage holes to improve area coverage while minimizing the moving distance.

The rest of this paper is organized as follows. Section 2 provides a brief survey of related work on hole-boundary-node detection algorithms, including a movement-assisted sensor-deployment algorithm in WSNs. Section 3 describes the preliminaries of our proposed algorithm – CHHA. Section 4 provides details of hole-boundary-node detection and hole-healing algorithms. Section 5 provides details on the simulation configuration, then presents and discusses the results. The performance of our proposed algorithm, evaluated with respect to various metrics, is compared with that of the virtual forces algorithm (VFA) [20], the combination of the Maxmin-edge algorithm (as an edge-based technique) and the Minimax algorithm (as a vertex-based technique) (VEDGE) [21], and hole-detection and healing algorithm (HEAL) [22]. Finally, conclusions and future research directions are discussed in Section 6.

2 Related work

In recent years, WSN research has become a popular topic; many researchers have focused on designing deployment algorithms to improve area coverage for WSNs. In this section, we briefly summarize related work concerning the two aspects of coverage hole detection and movement-assisted sensor deployment in WSNs.

2.1 Coverage hole and boundary detection

The existing approaches to detecting coverage holes and hole-boundary nodes in WSNs can be classified into a few major categories. Here, we focus on investigating the computational geometry approach.

Computational geometry approaches use the coordinates of the SNs and standard geometrical tools to detect coverage holes and hole-boundary nodes. Ghosh (2004) proposed a novel approach to estimate the coverage holes of a sensor network under random deployment using Voronoi diagrams [23]. Fang et al. (2006) provided the insight of a distributed algorithm for detecting and building routes around coverage holes based on the locations of SNs [24]. Wang et al. (2007) proposed a novel algorithm for an individual SN to identify whether it is a hole-boundary node of a coverage hole based on localized Voronoi polygons [25].

In 2011, Ma et al. [26] proposed a distributed coverage hole-detection protocol based on a computational geometry approach. Their hole-detection protocol was used for an irregular monitoring region. They considered the SN communication range to be equal to its sensing range. Some randomly selected SNs, called reference nodes, are tasked with executing a hole-detection algorithm. The reference nodes collect the information of two-hop neighbors in the neighbor discovery phase. After obtaining the neighbor list, the reference nodes detect coverage holes via computational geometry.

Li et al. (2015) [27] proposed a novel algorithm to detect coverage holes and identify hole-boundary nodes. Their algorithm consists of two phases: first, the algorithm detects coverage holes and identifies the coarse boundary node; second, the algorithm refines the hole-boundary nodes. In the first phase, they construct the Delaunay triangulation to form the network topology. They proposed an algorithm based on the circumcircle of the Delaunay triangle to detect all the coverage holes. Then, they proposed another algorithm to refine the hole-boundary nodes by removing some SNs that are not exact boundary nodes.

In 2016, Li et al. [28] proposed a novel algorithm using trees and graph theory to detect and localize coverage holes in a monitored area. In their algorithm, every SN detects whether coverage holes exist around it based on a hole-detection algorithm. Then, a method for merging holes is provided to present the global view of a coverage hole by identifying the hole location.

2.2 Movement-assisted sensor deployment

Sensor-deployment problems have been widely studied by the research community to achieve better coverage efficiency in large-scale sensor networks [20,21,22,23,24], [29,30,31,32,33]. Movement-assisted sensor deployment has attracted substantial attention in recent years. The design of a scheme to redeploy mobile SNs depends strongly on the desired performance goal. Most research into SN mobility focuses on designing algorithms to redeploy mobile SNs to enhance the area coverage. Sensor mobility is exploited to obtain a new location after the displacement of SNs to their desired locations, which directly improves the sensing coverage.

Zou et al. [20] proposed a sensor-deployment algorithm, called the VFA, to enhance the area coverage of a sensor network after the initial deployment of SNs. VFA uses a force-directed approach that combines attractive and repulsive forces to relocate SNs to maximize the area coverage of the RoI. The SNs do not move during the execution of the force algorithm. After the VFA has identified the desired locations of the SNs, the SNs are moved to their new locations.

In 2014, Mahboubi et al. [21] proposed new techniques to increase coverage in mobile sensor networks. First, they introduced the Maxmin-vertex and Maxmin-edge algorithms to maximize the minimum distance of every SN from the vertices and edges, respectively, of its Voronoi polygon. Then, they proposed the Minimax-edge algorithm to minimize the maximum distance of every SN from the edges of its Voronoi polygon. The final algorithm (VEDGE) combined the Maxmin-edge algorithm and the Minimax algorithm. Although the algorithm guarantees increased area coverage, the main characteristic of the algorithm is that the SN movement is performed iteratively, resulting in considerable energy consumption for the starting and stopping of the movement.

In the same year, Senouci et al. [22] introduced HEAL, a distributed, localized, and comprehensive two-phase protocol that can effectively estimate and enhance the area coverage in a mobile WSN. The first phase of their algorithm consists of three subtasks: hole identification, hole discovery, and border detection. The second phase consists of two subtasks: hole-healing area determination and node relocation. For coverage hole detection, they use the approach proposed in [24] to detect holes and hole borders. They identify an area with SNs that must be relocated to ensure local repair of the hole and then use virtual forces to relocate the SNs to heal the holes. The simulation results showed that this algorithm improves area coverage but is not efficient in some cases, such as dense deployment.

3 Preliminaries

In this section, we describe the network model, assumptions, and definitions that are used in our proposed algorithm.

We consider a WSN in which SNs are deployed randomly over a 2D region such that some parts of the network have sufficient coverage due to the presence of several redundant SNs, whereas other parts have coverage holes due to absence of SNs. We assume that a WSN consists of nsensor nodes si such that {i| 1, ..n}. Each ith SN is located at a known coordinate (xi, yi), and each SN has a unique identification – id. In addition, we assume that the system model is a multi-hop WSN with SNs having omnidirectional transceivers. Moreover, we assume that for all SNs, the communication range is larger than the sensing range [34, 35]. This assumption is realistic based on the actual sensor motes, such as MICAz, whose communication range is much larger than the sensing range of several typical sensors [35].

We assume that each SN knows its position (via low-cost GPS or other location information system) [17, 19], but we also consider possible localization and positioning inaccuracies bounded by a maximum error ε [36]. Therefore, we assume that the actual sensing radius rs of an SN is equal to the minimum of the sensing radius rmin minus the maximum error ε, i.e., rs = rmin − ε. For any point P at (xP, yP), we denote the Euclidean distance between si and P as d(si, P). Equation (1) shows the binary sensing model [37, 38] that expresses the coverage cP(si) of point P by SN si.

$$ {c}_P\left({s}_i\right)=\left\{\begin{array}{c}1,\mathrm{if}\ d\left({s}_i,P\right)<{r}_s\\ {}0,\mathrm{otherwise}\kern1.5em \end{array}\right. $$
(1)

Definition 1. Beside-node (BN): sjis said to be a beside-node of si if and only if the distance between si and sj is less than 2rs.

We assume that the communication range of an SN is a circular disk of radius rc centered at its location. An SN can directly communicate with other SNs within the communication range.

Definition 2. Neighbor node (NN): sj is said to be a neighbor node of si if and only if the Euclidean distance between si and sj is less than rc. In other words, si can directly communicate with sj.

Definition 3. Coverage hole: A coverage hole is an area that is not covered by any SN.

Definition 4. Hole-boundary node: A hole-boundary node is an SN that is located adjacent to a coverage hole.

Definition 5. Hole manager (HM): An HM is a hole-boundary node that is selected to determine the movement required to heal its coverage hole (similar to the concept of a cluster head [39]).

We use a method based on Delaunay triangulation to detect hole-boundary nodes. In mathematics and computational geometry, the Delaunay triangulation for a given set P of discrete points in a plane is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P).

Definition 6. Circumcircle: The notion “circumcircle” in this paper is used to express the circumcircle of a Delaunay triangle.

The following messages are used to achieve coverage of a specific area of interest with hole-boundary node detection and coverage hole healing:

  • Info-Msg (node id, node location): Each SN broadcasts this message to its neighbor nodes.

  • BD-Msg (node id, message id, node location, HM probability): Each SN broadcasts this message to its neighbor nodes. The HM probability is the probability that an SN will become an HM node.

  • BDFull-Msg (node id, HM node id, list of node id and location): A hole-boundary node sends this message to another hole-boundary node who has the highest HM probability.

  • HM2-Msg (HM node id, set of hole-boundary nodes): An HM node sends this message to another HM node.

  • HM-Msg (HM node id, node location): An HM node broadcasts this message to corresponding neighbor nodes.

  • Join-Msg (node id, HM node id): This message is sent by an SN to notify an HM node that it wants to become a group member.

  • Move-Msg (HM node id, node id, new location): An HM node sends this message to its member nodes to notify the member nodes that these nodes must move to the new location.

4 Coverage hole-healing algorithm (CHHA)

The coverage hole-healing algorithm will be discussed in detail in this section. Our algorithm is a collaborative mechanism that consists of two phases, i.e., detection of hole-boundary nodes and healing of coverage holes. Once the hole-boundary nodes and the effective sensor positions with moving cost constraints are identified, a one-time movement is performed to redeploy the SNs at these positions.

4.1 Hole-boundary node detection phase

In this phase, we propose a self-organized algorithm to detect coverage holes and boundary nodes. At the beginning of this phase, each SN broadcasts an Info-Msg message that contains its location information to its neighbor nodes. We assume that SNs decide to broadcast and receive the location information of one- or two-hop neighbor nodes depending on the size of the network area and its communication range.

Once each SN obtains the list of its neighbor nodes, it constructs the localized Delaunay triangulation by using the method provided by Li et al. 2003 [40]. Then, each SN as a vertex of one or more Delaunay triangles calculates the center and radius of the circumcircle of the triangles. An example of SN deployment and the Delaunay triangulation is shown in Fig. 1. To exactly detect hole-boundary nodes, we provide two important theorems in the following.

Fig. 1
figure 1

a. An example of sensor deployment; b. The Delaunay triangulation

Full size image

Theorem 1

Consider a Delaunay triangle. If the radius of the circumcircle of the Delaunay triangle is greater than the sensing radius, there definitely exists a coverage hole in the circumcircle.

Proof

If the radius of the circumcircle of a Delaunay triangle is greater than the sensing radius, the center of the circumcircle is clearly out of the sensing range of any SN. Hence, there definitely exists an uncovered region in the circumcircle, as shown in Fig. 2.

Fig. 2
figure 2

Example of a coverage hole in the circumcircle: solid line = sensing range, dashed line = circumcircle

Full size image

Theorem 2

Consider two-neighbor Delaunay triangles that share one or two common vertexes. If there exists an uncovered region in their circumcircles (according to Theorem 1) and the line segment between two circumcircle centers does not cross any edge of a Delaunay triangle, which is less than 2rs, then the two circumcircles contain the same uncovered region (in other words, the same coverage hole).

Proof

If the line segment of the two circumcircle centers does not cross any edge (less than 2rs) of a Delaunay triangle, there definitely exists a line segment or a curve segment that connects two circumcircle centers so that all points on that segment are not covered by any SN. Therefore, the two circumcircles contain the same coverage hole. Figures 3 and 4 show examples where the two circumcircles do or do not contain the same coverage hole.

Fig. 3
figure 3

Two examples of two circumcircles containing the same coverage hole

Full size image
Fig. 4
figure 4

Two examples of two circumcircles that do not contain the same coverage hole

Full size image

Based on the two theorems, the algorithm to detect the hole-boundary nodes is as follows:

  • Consider Theorem 1. Each SN calculates the radius of the Delaunay triangle circumcircles and compares the value with its sensing radius. If a radius of a circumcircle is greater than the sensing radius, then the SN is a boundary node of a coverage hole.

  • Consider Theorem 2. Each SN can determine its beside-nodes as the boundary nodes of the same coverage hole. At this time, each boundary node knows only local information about the hole. It cannot know all the boundary nodes around the hole. Thus, each hole-boundary node has to perform a process to exchange the information.

  • Each hole-boundary node creates a BD-Msg (boundary-discovery) message that contains a message id (same value of its id), its id, its location information, and its probability to become a HM node and then sends BD-Msg to its beside-nodes that are hole-boundary nodes of the same coverage hole.

  • When a hole-boundary node receives BD-Msg, it inserts its id, its location information, and its probability to become an HM node and forwards this message to another beside-node that is the hole-boundary node of the same coverage hole. It should be noted that to minimize the number of forwarded messages, a hole-boundary node does not create its BD-Msg if it has previously received and forwarded BD-Msg. This process is completed when a BD-Msg has traveled around the hole. In other words, if a hole-boundary node receives two BD-Msg with the same message id from its two beside-nodes, the forwarding of BD-Msg is complete.

  • Then, the hole-boundary node extracts the information from the two messages, combines the information into one message (BDFull-Msg) and forwards the message to the hole-boundary node with the highest probability to become an HM node. Once the hole-boundary node with the highest probability to become an HM node has received the message with full information of all boundary nodes of the coverage hole, it becomes the HM node of its coverage hole. It should be noted that a hole-boundary node with a large number of neighbor nodes will have higher probability to become the HM node. Note that each hole-boundary node determines the probability to become the HM node based on the following formula.

    $$ {p}_i={b}_i+{\alpha}_i $$
    (2)

    where pi is the probability of SN si to become an HM node, bi is the number of neighbor nodes of si, and αi is a real random value distributed in the range of 0 to 1. αi helps to avoid the situation in which two or more hole-boundary nodes fall into the same probability.

Once the HM of a hole is determined, the hole-boundary node detection phase is complete. Note that each hole has an id that is the same value as the HM node id. The second phase of CHHA is conducted on the HM node. Figure 5 shows an example of hole-boundary nodes and the HM node of the hole. The pseudo code shown in algorithm 1 provides the details of the hole-boundary nodes detection and the HM node selection.

figure d
Fig. 5
figure 5

The hole-boundary nodes and the HM

Full size image

4.2 Hole-healing phase

After the hole-boundary nodes are detected and the HM nodes are chosen, CHHA begins the hole-healing phase. In this phase, the HM nodes determine the movement of SNs within a group to heal coverage holes. The process includes three steps.

First, the HM nodes calculate the size of the hole according to the following formula.

$$ {h}_{HM_l}=\left|\left(\sum \limits_{k=1}^{m-1}{x}_k\cdot {y}_{k+1}+{x}_k\cdot {y}_1\right)-\left(\sum \limits_{k=1}^{m-1}{y}_k\cdot {x}_{k+1}+{y}_k\cdot {x}_1\right)\right|\div 2 $$
(3)

where \( {h}_{HM_l} \) is the size of the hole of the HMl node, which has the set of boundary nodes {b1, b2, …, bm}, and (xk, yk) is the coordinates of hole-boundary node bk.

The HM node of each hole will choose another HM node of the same hole. The first HM node selects the farthest hole-boundary node from it to become the second HM node by sending a notification (HM2-Msg) to that node. The boundary nodes of each hole are divided into two groups and managed by the two HM nodes. Then, each HM broadcasts HM-Msg with its location information to its neighbor nodes. If an SN receives HM-Msg from an HM node, it continues to wait to determine whether it has received HM-Msg from the other HM nodes. Each SN maintains a table containing the information of all HM nodes from which it has received HM-Msg and the distance to each HM node. The information about the distance to each HM node is used by the SN to select the closest HM node. The SNs then send Join-Msg to their selected HM nodes. Note that an SN will become a member of an HM node after sending Join-Msg as an acknowledgment.

Second, the midpoint of line segment between two HM nodes of a hole is chosen as the hole center (HC). The HC point is changed depending on the number of members in the two groups managed by the two HM nodes. Each hole is divided into two sub-holes by a line segment through the HC and perpendicular to the line segment between the two HM nodes. The new HC point is determined according to the number of neighbor nodes of each HM node, which helps to minimize the movement distance for relocation of a sensor network in which the initial sensor deployment contains many coverage holes or a non-uniform node distribution. Let the force acting on the initial HC point be denoted as \( \overrightarrow{F_{HC}} \). The force on the HC point is expressed as follows.

$$ \overrightarrow{F_{HC}}=\left\{\begin{array}{c}\left(\frac{d\left({m}_1,{m}_2\right)}{2}-{u}_{M_2}\cdot \frac{d\left({m}_1,{\mathrm{m}}_2\right)}{h_l},\beta \left({m}_1,{\mathrm{m}}_2\right)\right),\kern1.5em \mathrm{if}\ \left({u}_{m_1}>\frac{u_l}{2}\right)\ \mathrm{and}\ \left({u}_{m_2}<\frac{u_l}{2}\right)\\ {}\left(\frac{d\left({m}_1,{\mathrm{m}}_2\right)}{2}-{u}_{M_1}\cdot \frac{d\left({m}_1,{\mathrm{m}}_2\right)}{h_l},\beta \left({m}_1,{\mathrm{m}}_2\right)+\pi \right),\mathrm{if}\ \left({u}_{m_1}<\frac{u_l}{2}\right)\ \mathrm{and}\ \left({u}_{m_2}>\frac{u_l}{2}\right)\\ {}0,\kern18.25em \mathrm{otherwise}\kern7.5em \end{array}\right. $$
(4)
$$ {u}_l=\frac{h_l}{2{r_s}^2} $$
(5)

where d(m1, m2) is the distance between two HM nodes HM1 and HM2; \( {u}_{m_1} \) and \( {u}_{m_2} \) are the number of members of HM1 and HM2, respectively; β(m1, m2) is the angle of a line segment from HM1 and HM2; and ul is the number of SNs required to heal the hole. Figures 6 and 7 show examples of a selecting an HC point and the division of holes into two sub-holes.

Fig. 6
figure 6

The selection of HM2 and the initial HC

Full size image
Fig. 7
figure 7

The selection of the new HC

Full size image

Third, we describe a virtual force calculation. Let \( \overrightarrow{F_i} \) denote the total force acting on si. The total force \( \overrightarrow{F_i} \) is a vector whose orientation is determined by the vector sum of all the forces acting on si. Let \( \overrightarrow{F_{iS}} \) denote the total force exerted on si by another SN in the same group. In addition to the attractive and repulsive forces of other SNs, an SN si is also subjected to the forces exerted by the boundary of the two sub-holes. The total force exerted on si by another SN in the same group is expressed as follows.

$$ \overrightarrow{F_{iS}}=\sum \limits_{j=1,j\ne i}^u\overrightarrow{F_{ij}} $$
(6)
$$ \overrightarrow{F_{ij}}=\left\{\begin{array}{c}\left({\delta}_a\left(d\left({s}_i,{s}_j\right)-{d}_s\right),\beta \left({s}_i,{s}_j\right)\right),\kern1.5em \mathrm{if}\ d\left({s}_i,{s}_j\right)>{d}_s\\ {}\left({\delta}_r\left({d}_s-d\left({s}_i,{s}_j\right)\right),\beta \left({s}_i,{s}_j\right)+\pi \right),\mathrm{if}\ d\left({s}_i,{s}_j\right)<{d}_s\\ {}0,\kern12.5em \mathrm{otherwise}\kern1.75em \end{array}\right. $$
(7)

where \( \overrightarrow{F_{ij}} \) is the force exerted on si by another node sj, d(si, sj) is the Euclidean distance between si and sj, ds is the threshold distance that determines how close SNs get to each other, β(si, sj) is the angle of a line segment from si to sj, and δa and δr are the measure of the attractive and repulsive forces. δa and δr should be selected based on the computing capability of the SNs and the network scenario.

Because each HM node manages and decides the movement for its group, in our virtual force model, we assume that obstacle is the boundary of two sub-holes (a line segment that divides a hole into two sub-holes, see also Fig. 7). Let \( \overrightarrow{F_{iB}} \) be the total force on si due to the boundary of two sub-holes; it is expressed as follows.

$$ \overrightarrow{F_{iB}}=\left\{\begin{array}{c}\left({\delta}_a\left(d\left({s}_i, ls\right)-{d}_{ls}\right),\beta \left({s}_i, ls\right)\right),\kern1.5em \mathrm{if}\ d\left({s}_i, ls\right)>{d}_{ls}\\ {}\left({\delta}_r\left({d}_{ls}-d\left({s}_i, ls\right)\right),\beta \left({s}_i, ls\right)+\pi \right),\mathrm{if}\ d\left({s}_i, ls\right)<{d}_{ls}\\ {}0,\kern12.5em \mathrm{otherwise}\kern1.75em \end{array}\right. $$
(8)

where d(si, ls) is the Euclidean distance between si and the line segment of the boundary of two sub-holes, dls is the threshold distance that determines how close the SNs get to the line segment ls, and β(si, ls) is the angle of the line segment from si to the line segment ls.

The total force \( \overrightarrow{F_i} \) on si is expressed as follows.

$$ \overrightarrow{F_i}=\overrightarrow{F_{iS}}+\overrightarrow{F_{iB}} $$
(9)

Note that the hole-healing algorithm is executed on the HM node only. Each HM node uses the virtual forces moving to find appropriate SN locations to heal the hole. Note that an SN has to move if and only if its beside-nodes move and create a hole. Finally, when each HM node has completed the virtual forces moving and achieved the coverage requirement, a Move-Msg include the new locations (if any) are sent to its members. Figure 8 shows an example of the relocation to heal a coverage hole. The pseudocode shown in algorithm 2 provides the details of the hole healing phase.

Fig. 8
figure 8

The relocation to heal a coverage hole

Full size image

5 Performance evaluation

In this section, we perform an intensive simulation to confirm the performance of our proposed algorithm (CHHA) in terms of the moving cost (moving distance) of the SNs in a network. To strengthen our performance evaluation, CHHA is compared with three other algorithms, VFA [20], VEDGE (21), and HEAL [22].

5.1 Simulation setup

A MATLAB simulator is used to evaluate the performance of the algorithms. In these simulations, for comparison purposes, 150 SNs are randomly distributed across a plain area of 200 × 200 m2 with the existence of a coverage hole due to the absence of SNs. We set the sensing radius rs to 15 m and the communication radius to 80 m [35]. Note that to determine the energy consumption of the movement, we follow the energy models defined in [17, 19, 36], i.e., the energy consumed when moving 1 m is 1 unit and starting or stopping a movement costs the equivalent of 1 m movement [36].

We evaluate the performance of CHHA by comparison with three other algorithms, namely, VFA [20], VEDGE [21], and HEAL [22]. The evaluations consider three main metrics: the number of SNs that are moved, the total moving distance of all the SNs, and the total energy consumption of the movement. The presented results of all the simulations are the averages of twenty-five simulation runs in each configuration.

5.2 Simulation results and discussion

To evaluate the performance of the four algorithms, we simulate an experiment that consists of two scenarios: different hole radii and different numbers of holes. In the simulation, the four algorithms (CHHA, VFA, VEDGE, and HEAL) achieve full coverage (100%) after relocating the SNs. Therefore, we focus on evaluating only the movement metrics. In the first scenario, the hole radius is varied from 40 m to 80 m, as shown in Fig. 9.

Fig. 9
figure 9

The SN deployment under different hole radii

Full size image

Figure 10 compares the numbers of SNs that are required to move to a new location. The VFA algorithm applies a force-directed approach to improve coverage; the forces exerted on all SNs result in VFA moving all the SNs. VEDGE and HEAL move approximately 12 to 37% and 19 to 50% of the SNs when the hole radius is increased from 40 to 80 m, respectively. As shown in Fig. 10, CHHA moves fewer SNs than do the other algorithms. CHHA moves only approximately 9 to 27% of the SNs under different hole radii.

Fig. 10
figure 10

Number of moving nodes under different hole radii

Full size image

Figure 11 depicts the total moving distance of the SNs for each algorithm. As the hole radius increases, the total moving distances of the four algorithms also increase. We observe a similar trend of the total moving distance for the four algorithms, in which our CHHA algorithm results in the lowest total distance of only approximately 18 to 35%, 72 to 89%, and 69 to 83% of that of VFA, VEDGE, and HEAL, respectively.

Fig. 11
figure 11

Total moving distance under different hole radii

Full size image

Figure 12 shows the total energy consumption. In CHHA, VFA, and HEAL, the SNs move only once, whereas VEDGE performs movement in each round. Therefore, VEDGE consumes more energy for starting and stopping movement. As the hole radius increases, the number of rounds of VEDGE also increases, resulting in greater energy consumption. The total energy consumption of CHHA is the best, i.e., approximately 16 to 34%, 54 to 74%, and 67 to 79% of that of VFA, VEDGE, and HEAL, respectively.

Fig. 12
figure 12

Energy consumption of movement under different hole radii

Full size image

In the second scenario, we simulate the four algorithms with various number of holes (1 to 5 holes). Figure 13 shows the SN deployment under different numbers of holes.

Fig. 13
figure 13

The SNs deployment under different numbers of holes

Full size image

Figure 14 shows the numbers of moving SNs. In this scenario, as the number of holes increases, the number of SNs moved by HEAL increases substantially. As shown in the chart, CHHA moves fewer SNs than do the other algorithms.

Fig. 14
figure 14

Number of moving nodes under different numbers of holes

Full size image

Figure 15 compares the total SN moving distance of each algorithm under different numbers of holes. CHHA outperforms the other algorithm, with a total moving distance of only approximately 18 to 27%, 60 to 87%, and 56 to 79% of that of VFA, VEDGE, and HEAL, respectively.

Fig. 15
figure 15

Total moving distance under different numbers of holes

Full size image

The amount of energy used during the movement is another important parameter to consider. Figure 16 compares the total energy consumption of movement for each algorithm. Again, CHHA is superior. The total energy consumption of CHHA is only approximately at 18 to 26%, 54 to 73%, and 54 to 78% of that of VFA, VEDGE, and HEAL, respectively. These results clearly illustrate the effectiveness of CHHA in relocating SNs to maximize the coverage area.

Fig. 16
figure 16

Energy consumption of movement under different numbers of holes

Full size image

6 Conclusion

In this research, we proposed a distributed deployment algorithm to improve WSN area-coverage, namely, the coverage hole-healing algorithm (CHHA). Our contributions are two-fold. We proposed a novel algorithm to detect hole-boundary nodes based on the Delaunay triangulation topology and the property of circumcircles of the Delaunay triangle to detect coverage holes and hole-boundary-nodes. We then proposed a hole-healing algorithm to determine the movement of the SNs required to heal all possible coverage holes to improve area coverage while minimizing the moving distance.

To evaluate the performance of our proposed scheme, we compared the number of SNs moved, the total movement distance, and the total energy consumption of movement with those of the VFA, VEDGE, and HEAL algorithms. Through intensive simulation experiments, the four algorithms are shown to improve the area coverage by moving the SNs to the optimal locations, thereby achieving full coverage. However, our algorithm outperforms the others on all three metrics. We can confirm that CHHA is suitable for minimizing the total movement distance while moving fewer SNs.

Furthermore, although CHHA can improve area coverage, additional modifications can produce further enhancements. Our future work will solve the area-coverage deployment problem by applying soft-computing algorithms to achieve global optimization.