A Coverage Hole Recovery Method for 3D UWSNs Based on Virtual Force and Energy Balance

Abstract

Underwater wireless sensor networks (UWSNs) have been applied in lots of fields. However, coverage holes are usually caused by complex underwater environment. Coverage holes seriously affect UWSNs’ performance and quality of service; thus, their recovery is crucial for 3D UWSNs. Although most of the current research recovery algorithms demand hole detection, the number of additional mobile nodes is too large, the communication and computing costs are high, and the coverage and energy balance are poor. Therefore, these methods are not suitable for UWSN hole repairing. In order to enhance the performance of hole recovery, a coverage hole recovery method for 3D UWSNs in complex underwater environments based on virtual force guidance and energy balance is proposed. The proposed method closely combines the node energy and considers complex environmental factors. A series of multi-dimensional virtual force models are established based on energy between nodes, area boundaries, zero-energy holes, low-energy coverage holes, underwater terrain, and obstacle forces. Then, a coverage hole recovery method for 3D UWSNs based on virtual force guidance and energy balance (CHRVE) is proposed. In this method, the direction and step size of mobile repairing node movement is guided by distributed computation of virtual forces, and the nodes are driven towards the target location by means of AUV or other carrier devices. The optimal position to improve coverage rate and node force balance is obtained. Simulation experiments show good adaptability and robustness to complex underwater terrain and different environments. The algorithm does not require precise coverage hole boundary detection. Furthermore, it balances network energy distribution significantly. Therefore, this method reduces the frequency of coverage hole emergence and network maintenance costs.

1. Introduction

In recent years, underwater wireless sensor networks (UWSNs) [1] have been applied in lots of fields such as environment monitoring, military surveillance, data collection, etc. [2]. Due to some undesirable reasons, such as complex underwater environment, degradation of node electronic components, water flow, erosion, and underwater life damage, the sensor nodes deployed in UWSNs tend to be invalid or be incomplete of the monitoring perception. Hence, the coverage holes of UWSNs are easy to be caused. The coverage holes seriously affect network performance and quality of service; therefore, coverage hole recovery has become a research hotspot in recent years.

Hole recovery by additional mobile nodes with Autonomous Underwater Vehicles (AUV) is an important type of hole recovery methodology [3,4]. In these methods, when the coverage holes appear, the mobile nodes are added dynamically to form hybrid UWSNs. Then, the mobile nodes are moved to their deterministic locations to repair coverage holes driven by AUV according to the location of the holes [4]. However, in recent years, more research has been done on coverage hole recovery methods for 2D planar networks [5], while little research has been done on coverage hole recovery methods for 3D spatial networks. Moreover, the few current approaches use the target event as the algorithmic coverage objective and do not take enough account of network topology characteristics [6]. In fact, the area coverage of UWSNs has more extensive applications in underwater environment monitoring and security surveillance [2]. Furthermore, the load characteristics of bottom-up multi-hop transmission in UWSNs make the nodes consume energy unevenly. If the network energy consumption is more balanced after coverage hole repairing, it will help to reduce the frequency of hole emergence, further reduce the maintenance cost of keeping the UWSNs working properly, and prolong the life of the network.

In recent years, the virtual force-based network coverage method [7] has received a lot of attention from scholars because of its good performance in terms of coverage and connectivity. However, all these methods require precise location information of nodes and also require that the nodes are all movable nodes. Therefore, these methods cannot really be applied to coverage hole repairing in UWSNs.

To repair coverage holes by adding a limited number of additional mobile nodes, and to quickly improve area coverage, reduce energy consumption, and balance the overall energy of the network to make it suitable for repairing 3D UWSN coverage holes in complex underwater environments, a coverage hole recovery method for 3D UWSNs in complex underwater environments based on virtual force guidance and energy balance (CHRVE) is proposed in this paper. The contributions of this work are the following:

(1) Multi-dimensional virtual force models are established, which consider multi factors such as energy between nodes, area boundaries, zero-energy holes, low-energy coverage holes, underwater complex terrain, and obstacle forces. In these models, some novel concepts such as energy density, zero-energy holes, and low-energy coverage holes are defined to construct more efficient virtual force models. Different from the traditional virtual force model, the proposed virtual force models not only depend on the distance between nodes, but also closely combine the node energy, and consider complex environmental factors. Therefore, the proposed models are closely combined with the characteristics of the underwater environment and are more suitable for repairing UWSN coverage holes. Moreover, the models make the energy distribution of the patched UWSNs more balanced.

(2) The CHRVE algorithm is proposed. In this method, the direction and step size of mobile repairing node movement is guided by the defined virtual forces above distributed, and the nodes are driven towards the target location by means of AUV or other carrier devices. This algorithm does not require precise coverage hole boundary detection, and it has good adaptability and robustness to complex underwater terrain and different environments. The minimum number of additional repairing nodes by theoretical estimation is presented in this algorithm. For different scenarios, the different corresponding mobile node patching schemes are proposed, thus the algorithm has higher node coverage utilization and robustness. Furthermore, the proposed strategy for redundant repairing of low-energy coverage holes significantly balances the network energy distribution; thus, this method reduces the frequency of new coverage hole emergence and network maintenance costs.

The rest of the paper is organized as follows: The related works are addressed in Section 2. Section 3 defines our novel concepts for virtual force models. The proposed virtual force models based on energy for hole coverage of 3D UWSNs is described in Section 4 in detail, and the CHRVE algorithm is proposed in Section 5. Simulation and analysis are provided in Section 6. Finally, conclusions are given in Section 7.

2. Related Work

As mentioned above, hole recovery is some of the most active research in coverage control issue of UWSNs. However, for 2D planar networks coverage hole recovery, more research has been done [5], while little research has been done on coverage hole recovery for 3D UWSNs.

2.1. Coverage Hole Recovery for 2D Planar WSN

Based on the different repair methods, the 2D WSNs coverage hole repair includes five types of repair methods: (1) hole recovery methods based on Voronoi diagrams [8,9,10,11,12,13], (2) hole recovery methods based on virtual forces [14,15,16], (3) hole recovery methods based on geometric calculations [17,18,19,20,21], (4) hole recovery methods based on trees or graphs [22,23,24,25,26], and (5) hole recovery methods based on intelligent algorithms [27,28,29,30,31,32,33].

These hole repair methods have shown better performance in 2D planar space. However, due to the complexity of the 3D underwater space and environment, these 2D hole repair methods are not suitable for 3D UWSN coverage hole repair. For instance, we proposed a fish swarm-inspired holes recovery algorithm for 2D planar space in [34]. It can effectively solve the problem of coverage hole repair for the 2D water surface of UWSNs. However, in the 3D underwater, when the artificial fish searches for the best position, the dimensions of each artificial fish increase from 2k to 3k (k is the number of additional mobile repairing nodes). Then, this problem is converted to a vector extremum problem in 3k high-dimensional space. Therefore, this method is extremely time-consuming, and it is suitable for 3D UWSNs space.

2.2. Coverage Hole Recovery for 3D UWSNs

There is relatively little research on 3D UWSN coverage hole recovery. The existing research can be categorized into three types of methods: hole recovery methods based on AUV mobile node, hole recovery methods based on depth adjustment, and hole recovery methods based on node communication power enhancement.

(1) Hole recovery methods based on AUV mobile node

For the topology healing problem of UWSNs, Liu et al. [4] proposed a topology healing algorithm based on the full Steiner tree with the aid of AUV nodes. He et al. [35] proposed a fish swarm optimization method for network topology healing using AUV nodes. Hao et al. [36] proposed a dynamic detection and repair method for 3D WSN coverage holes. This method detects and recovers 3D coverage holes based on meshing 3D spatial regions. Zhang et al. [37] proposed a three-dimensional iterative enhancement algorithm for UWSN coverage hole recovery using intelligent search followed by virtual force.

(2) Hole recovery methods based on depth adjustment

Erkay et al. [38] proposed a topology recovery method based on depth adjustment of nodes and presented two topology recovery algorithms: a block movement repair (BMR) algorithm and a distributed underwater repair (DURA) algorithm. The BMR algorithm simply moves all nodes below the failed node upwards to recover network connectivity. However, the energy consumption of the network is accelerated, and the network lifetime is shortened due to the large number of node movements. The DURA algorithm does not take into account the energy of nodes while selecting a node for movement. This may cause the network to be disconnected again shortly after hole recovery. Moreover, this method is time-consuming in hole recovery.

(3) Hole recovery methods based on node communication power enhancement

Wang et al. [39] proposed a strategy to enhance the communication power of neighboring nodes of the failed node, thus increasing the communication radius of neighboring nodes to re-establish network connection and achieve topology recovery. However, in UWSNs, the energy of nodes is limited. Therefore, this approach will increase the energy consumption of neighboring nodes of the failed node. This may lead to new failed nodes appearing quickly and shortening the network lifetime.

2.3. Coverage Control for 3D WSNs Based on 3D Virtual Forces

In recent years, virtual force-based network coverage methods have attracted the attention of many scholars for their good performance in terms of coverage and connectivity [40]. Miao et al. [41] proposed a self-deployment algorithm called 3DSD for deployment of 3D WSNs. In this method, a 3D virtual force model is constructed. A negotiation tactic is utilized to ensure network connectivity, and a density control strategy is used to balance the node distribution. In order to completely cover the 3D region of interest, Boufares et al. [42] proposed a virtual force-based 3D distributed deployment algorithm, 3D-DVFA. This method assumes that the sensor nodes are all mobile nodes, all of which can gradually move towards the specified position. These two methods above belong to the redeployment methods after node failure of WSNs. Although they are regional coverage, the nodes are all required to be mobile nodes. Therefore, these methods are too costly for repairing coverage holes. Hao et al. [43] proposed a three-dimensional curved wireless sensor coverage hole repair algorithm for land hybrid networks called 3D-SCHDR. This approach requires precise positioning information of nodes and also requires that the nodes are all mobile nodes. Thus, this method is not suitable for coverage hole recovery of 3D UWSNs.

3. Preliminaries

3.1. Network Model

In this paper, we adopt the same network model as ref. [44]. The coverage model of sensor nodes is based on the Boolean model with the following assumptions.

(1) The UWSN has been deployed in the monitoring area based on a specific approach. The energy of each sensor node is limited and cannot be replenished. The initial energy of sensor is denoted as E_0i, and its current residual energy is denoted as E_curi. When the node energy is less than the threshold Eᶿ, the node enters a sleep state after sending a failure location and warning to its neighbor nodes.

(2) The communication power for each deployed sensor node is adjustable. The transmit power can be determined according to the distance, and the distance dist(Ns_i,Ns_j) between node Ns_i and Ns_j can be calculated based on the received signal strength. Then, the neighbor nodes of Ns_i can be represented as:

$${\phi }_i=\left\{N{s}_j\right|dist(N{s}_i,N{s}_j)\le 2Rs, i\ne j\}$$

(1)

where Rs is the sensing radius of the sensor.

(3) The additional nodes used for coverage hole recovery are mobile nodes. These mobile sensors can be moved to a designated underwater location in the monitoring area, driven by AUV and supported by the relevant communication protocols.

3.2. Movement Energy Consumption of Nodes Under the Influence of Water Flow

In complex underwater environments, moving sensors to a designated location requires more energy than in land environments. The overall energy consumption of the algorithm in this paper consists of computational energy, communication energy, and node movement energy. Computational energy and communication energy are very small compared to movement energy consumption, so only movement energy consumption is calculated.

Due to water flow and the different physical structures of underwater nodes, the nodes’ energy consumption generated by moving unit distance in different directions is different. Underwater sensor nodes consume more energy per unit distance to float than to sink. Nodes moving against the water flow consume more energy than those moving with the water flow.

Definition 1 [Movement energy consumption].

Let E_x1, E_y1, E_z1 denote the energy consumption of node Ns_i moving in a positive direction per unit distance along the x, y, z axes, respectively. On the contrary, let E_x2, E_y2, E_z2 denote the energy consumption of node Ns_i moving in a negative direction per unit distance along the x, y, z axes, respectively. Let the energy consumption of Ns_i moving unit distance in a certain direction $\overrightarrow{dir}\{di{r}_x,di{r}_y,di{r}_z\}$ be $E_{\phi i}$, and the moving distance of Ns_i in this direction be denoted as d_i. Then, the total movement energy consumption E_i of node Ns_i moving in direction $\overrightarrow{dir}$ is represented as follows:

$$E_i=E_{\phi i}\cdot d_i$$

(2)

where:

$$E_{\phi i}={\displaystyle \frac{{\displaystyle \sum _{j\in \{x_k,y_k,z_k|k=1,2\}}{E}_j\cdot di{r}_j}}{\left|\overrightarrow{dir}\right|}}$$

(3)

3.3. Energy Density

When the coverage holes are generated after the UWSN is running for a while, the residual energy of surviving nodes varies greatly. Similarly, when the coverage holes are patching, the residual energy of the additional repairing nodes is also greatly different when they move different distances to the proper positions. In order to measure the distribution of energy, the energy density is defined as follows.

Definition 2 [Energy density].

Let an arbitrary point in the monitoring area be denoted as Q, the Euclidean distance between Q and node Ns_i be dist(Q, Ns_i), the residual energy of Ns_i be E_curi. The energy density at point Q in the monitoring area is defined by Equation (4):

$${\rho }_{\mathrm{E}}(Q)={\displaystyle \sum _{dist(Q,N{s}_i)\le Rs,\forall N{s}_i\in Ns}\frac{E_{\mathrm{cur}i}}{dist(Q,N{s}_i)+1}}$$

(4)

3.4. Zero-Energy Holes

Because of the great complexity of hole boundary detection in 3D space, most topology methods cannot be extended from 2D WSN to 3D UWSN. Thus, the existing topology-based methods [16] are not suitable for distributed autonomous boundary detection in 3D UWSNs. The proposed algorithm in this paper does not require precise detection of 3D holes boundaries; instead, it only requires coarse-grained detection of the relative spatial grid positions of holes. The monitoring area is divided into several grids. Let the maximum number of grid points that a sensor node can cover be denoted as ξ, which can be calculated using Equation (5). The smaller the granularity of grids is, the larger the value of ξ will be.

$$\xi =card\left(Q_i\right|dist(N{s}_i,Q_i)\le Rs)$$

(5)

Definition 3 [Zero energy hole].

Let the probability that the grid point Q_i(x,y,z) is covered by the sensor node Ns_i be p_cov(x,y,z,Ns_i). The grid points that are not covered by any existing sensing node Ns_i form a zero-energy hole grid point set, which is denoted as holl in Equation (6) and is called a zero-energy hole.

$$holl=\left\{Q_i\right(x,y,z\left)\right|p_{\mathrm{cov}}(x,y,z,N{s}_i)=0,\forall N{s}_i\in Ns\}$$

(6)

3.5. Low-Energy Coverage Holes

In the grid points collection of the monitoring area, with the energy consumption of nodes in the network running, there will be more grid point areas with low residual energy of surrounding nodes, which is defined as low-energy coverage holes. The node residual energy in this type of coverage hole is usually very low, which easily leads to the generation of new zero-energy holes.

Definition 4 [Low-energy coverage holes].

Let the probability that the grid point Q_i(x,y,z) is covered by the sensor node Ns_i be p_cov(x,y,z,Ns_i). The low-energy coverage hole is defined by Equation (7):

$$Lowholl=\left\{Q_i(x,y,z)\left|{\displaystyle \sum _{p_{\mathrm{cov}}(x,y,z,N{s}_i)=1}{E}_{\mathrm{cur}i}}<E_{\mathrm{thlow}},\forall N{s}_i\in Ns\right.\right\}$$

(7)

where E_curi is the residual energy of node Ns_i, E_thlow is the threshold value of energy, which is calculated using Equation (8).

$$E_{\mathrm{thlow}}={\displaystyle \frac{mean\left(E_{\mathrm{cur}i}\right)}{2}}$$

(8)

4. The Virtual Force Models Based on Energy for Hole Recovery of 3D UWSNs

The parameters related to this method are defined as shown in

Table 1. Parameter description table.

Parameter	Definition
Cth	The threshold value of coverage rate
Addmin	The minimum number of additional repairing nodes by theoretical estimation
Addnode	The actual number of additional repairing nodes
η	The coverage rate of UWSNs
μ	The correction factor for node utilization rate
Stepmax	The maximum movement step
E0	The initial value of energy
Ecur	The current residual energy
Eᶿ	The minimum energy threshold
Eth	The energy threshold for repairing nodes
Iter	The maximum number of iterations
Fmin	The minimum force threshold for node movement
krep	The repulsive force coefficient
katt	The attractive force coefficient
ksix	The boundary repulsion coefficient
kholl	The attractive force coefficient of hole grid points
klowholl	The attractive force coefficient of low-energy hole grid points
kf	The coefficient of force acting on the bottom surface or obstacle

.

4.1. Calculation of the Number of Additional Nodes for Holes Recovery

The structure of underwater sensors is more complex than those used on land. The underwater sensors require a variety of treatments such as corrosion protection. They also have higher energy requirements and much higher prices. Therefore, using the minimum number of repairing nodes to maximize the coverage effect is the primary consideration.

The number of additional mobile repairing nodes is closely related to the size and shape of coverage holes. When coverage holes are in the center of the area, the coverage utilization of additional nodes is higher, which results in fewer repairing nodes being required to significantly increase coverage. However, if the holes are scattered or located more at the boundary of the area, the coverage utilization of the additional nodes is significantly reduced. Thus, more repairing nodes are required to achieve the same network coverage for these holes’ recovery.

Alam et al. [45] researched 3D network coverage and connectivity problem with the deterministic deployed nodes. In [45], they demonstrated that the truncated regular octahedron requires fewer cells to cover a given 3D space. In this case, $Rc/Rs\ge 4/\sqrt{5}$, the volume of this truncated octahedron is $8\sqrt{2}{a}^3$, and the volume of the circum-sphere is ${\displaystyle \frac{4}{3}}\pi {({\displaystyle \frac{\sqrt{10}}{2}}a)}^3$. Therefore, the effective coverage utilization of the node-sensing sphere is up to $8\sqrt{2}{a}^3/{\displaystyle \frac{4}{3}}\pi {\left({\displaystyle \frac{\sqrt{10}}{2}}a\right)}^3=0.68329$. In this case, the least number of nodes is required for filling the same volume of space.

Based on the above analysis, considering the monitoring area boundaries, the number of additional nodes for holes recovery can be calculated as follows by theoretical estimation:

$$Ad{d}_{\min }={\displaystyle \frac{V(1-\eta )}{0.68329\times \mu \times \frac{4}{3}\pi R{s}^3}}$$

(9)

where μ is the correction factor, taking the value (0, 1). Its value is related to the size and shape of the monitoring area, as well as the node-sensing radius. In the case of the same monitoring area, the value of μ is larger when the node-sensing radius is smaller, and, conversely, the value of μ is smaller when the node sensing radius is larger. In the simulation of this paper, its values are taken by experimental verification under this principle. V is the volume of the monitoring area.

4.2. The Virtual Force Models Based on Energy

(1) The inter-node forces based on energy

The distance between sensor nodes within communication range 0 < dist(Ns_i,Ns_j) < 2Rs; thus, the area of sensing overlap will be formed. In order to avoid over-densification of nodes and improve node coverage utilization, the virtual repulsion force, denoted as $\overrightarrow{F_{\mathrm{rep}}}$, between nodes is defined to guide the neighbor nodes away from each other. The closer the distance between node Ns_i and node Ns_j, the higher the virtual repulsion force is.

In order to improve the energy balance of UWSNs after hole repair, the residual energy of nodes is considered when defining the virtual repulsion force in this paper. The more residual energy Ns_j has, the more repulsive it is to Ns_i. When the residual energy of a node is very small, it is about to die of energy depletion; thus, there is almost no repulsion.

Therefore, in the Ns_i repulsive force field U₁ defined by Equation (10), the virtual repulsive force $\overrightarrow{F_{\mathrm{rep}i}}$ to which Ns_i is subjected is calculated as Equation (11):

$$U_1=\left\{N{s}_j\right|dist(N{s}_i,N{s}_j)\le 2Rs\}$$

(10)

$$\overrightarrow{F_{\mathrm{rep}i}}=\left\{\begin{array}{l}\left(-k_{\mathrm{rep}}\left({\displaystyle \frac{E_{\mathrm{cur}j}}{dis{t}^2(N{s}_i,N{s}_j)}}-{\displaystyle \frac{E_{\mathrm{cur}j}}{d_{\mathrm{opt}}^2}}\right), {\alpha }_{ij}\right),\hspace{1em}0<dist(N{s}_i,N{s}_j)<d_{\mathrm{opt}}\\ 0\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}, dist(N{s}_i,N{s}_j) >d_{\mathrm{opt}} \end{array}\right.$$

(11)

where k_rep is the repulsive force coefficient, E_curj is the current residual energy of node Ns_j, α_ij is the direction of the force, d_opt is the optimal distance between nodes, which is calculated as Equation (12). The residual energy E_curj in Equation (11) is obtained from the sensor nodes via UWSNs communication.

$$d_{\mathrm{opt}}=\left\{\begin{array}{l}2Rs,\hspace{1em}\hspace{1em}Ad{d}_{\mathrm{node}}<Ad{d}_{\min }\\ {\displaystyle \frac{4Rs}{\sqrt{5}}},\hspace{1em}\hspace{1em}Ad{d}_{\mathrm{node}}\ge Ad{d}_{\min }\end{array}\right.$$

(12)

where Add_min is the minimum number of additional repairing nodes by theoretical estimation, and Add_node is the actual number of additional repairing mobile nodes.

The virtual repulsive force $\overrightarrow{F_{\mathrm{rep}i}}$ to which Ns_i is subjected in force field U₁ is depicted in Figure 1.

When Add_node ≥ Add_min, not only should the zero-energy hole be patched, but also, redundant nodes should be added moderately to the area around the low-energy node where the residual energy E_cur is lower than the threshold Eth, which is set with engineering requirements. These redundant nodes assist in carrying the communication data transit load of other nodes to reduce the frequency of re-patching.

In this paper, we set the low energy nodes to generate a virtual attractive force on the additional nodes to attract the additional nodes towards the low energy nodes. These low-energy nodes form a low-energy area, and this area creates a large resultant force on the nodes, guiding the additional nodes to move to repair this area.

Based on the above analysis, the less residual energy of the nodes within the communication range, the greater the virtual attractive force. Similarly, the greater the distance between nodes, the greater the virtual attractive force. Therefore, in the Ns_i gravitational field U₂ defined by Equation (13), the virtual attractive force $\overrightarrow{F_{\mathrm{att}i}}$ on Ns_i is calculated by Equation (14):

$$U_2=\left\{N{s}_j\right|E_{\mathrm{cur}j}<E_{\mathrm{th}}\&\&dist(N{s}_i,N{s}_j)\le Rc\}$$

(13)

$$\overrightarrow{F_{\mathrm{att}i}}=(k_{\mathrm{att}}\left(\right(E_0-E_{\mathrm{cur}j})\times dist(N{s}_i,N{s}_j\left)\right),{\alpha }_{ij}),Ad{d}_{\mathrm{node}}\ge Ad{d}_{\min }$$

(14)

where k_att is the attractive force coefficient between nodes, E₀ is the initial energy value of node Ns_j, E_curj is the current residual energy of node Ns_j, α_ij is the direction of the force.

The virtual attractive force $\overrightarrow{F_{\mathrm{att}i}}$ on Ns_i in field U₂ is depicted in Figure 2.

Then, the node Ns_i is subjected to energy-based forces in the field U₁ and U₂, as shown in Equation (15).

$$\overrightarrow{F_{\mathrm{E}i}}={\displaystyle \sum _{N{s}_j\in U_1}\overrightarrow{F_{\mathrm{rep}i}}}+{\displaystyle \sum _{N{s}_j\in U_2}\overrightarrow{F_{\mathrm{att}i}}}$$

(15)

(2) The forces at the boundary of monitoring area

In UWSNs, the boundaries of the monitoring area have a great impact on the coverage utilization of nodes. In order to improve the effectiveness of hole recovery with a limited number of additional nodes, based on Hooke’s law, we assume that there is a virtual force $\overrightarrow{F_{\mathrm{bor}}}$ on the sensor node at the area boundary, which guides the node moderately away from the boundary. This force consists of the repulsive force generated by the boundary of the hexahedral area of the 3D space. Assuming that the 3D monitoring space is a cubic region, this force consists of the repulsive force generated by the boundary of the cubic region on the sensor node. Let the six boundaries of the cubic region be $\delta =\{x_0,x_l,y_0,y_w,z_0,z_h\}$. Then, the virtual repulsion of boundary ${\delta }^{*}\in \delta$ on node Ns_i is shown in Equation (16):

$$\overrightarrow{F_{\mathrm{box}i(\delta *)}}=\left\{\begin{array}{l}(-k_{\mathrm{six}}(d_{\delta *}-d_{\mathrm{opt}1}),{\alpha }_{ij}), \hspace{1em}0<dist(N{s}_i,{\delta }^{*})\le d_{opt1}\\ 0,\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}dist(N{s}_i,{\delta }^{*})>d_{opt1}\end{array}\right.$$

(16)

where k_six is the boundary repulsion coefficient, $d_{\delta *}$ is the distance of node Ns_i from boundary ${\delta }^{*}$, α_ij is the direction of the force, d_opt1 is the optimal distance between the node and the boundary, which is calculated using Equation (17).

$$d_{\mathrm{opt}1}=\left\{\begin{array}{l}{\displaystyle \frac{\sqrt{3}Rs}{2}},\hspace{1em}Ad{d}_{\mathrm{node}}<Ad{d}_{\min }\\ {\displaystyle \frac{\sqrt{3}Rs}{3}},\hspace{1em}Ad{d}_{\mathrm{node}}\ge Ad{d}_{\min }\end{array}\right.$$

(17)

When Add_node ≥ Add_min, the distance of the node from the boundary is $\sqrt{3}Rs/3$, which guarantees that the boundary area is all within the node’s sensing range.

Then, the resultant force of the six boundaries on the node Ns_i is depicted in Figure 3, and it is calculated using Equation (18).

$$\overrightarrow{F_{\mathrm{bor}i}}={\displaystyle \sum _{{\delta }^{*}\in \delta }\overrightarrow{F_{\mathrm{box}i(\delta *)}}}$$

(18)

(3) Energy-based hole forces

In order to improve node movement speed and the effectiveness of hole recovery, we set the hole to generate a virtual attractive force on the additional node to guide the node to move to the center of the hole quickly. In the presented hole recovery strategy, the zero-energy holes are repaired preferentially under conditions of insufficient additional nodes. On the contrary, the low-energy coverage holes are redundantly repaired under conditions of sufficient additional nodes.

(a) Zero-energy hole recovery

The set of neighboring hole grid points of any grid point Q_i in holl is denoted as H(Q_i), where holl represents the grid points of zero-energy holes. Its number of neighboring hole grid points is denoted as N_neighbor(Q_i). Then, H(Q_i) and N_neighbor(Q_i) are calculated as follows.

$$H\left(Q_i\right)=\left\{Q_j\right|dist(Q_i,Q_j)\le Rs,Q_i,Q_j\in holl\}$$

(19)

N_neighbor(Q_i) = card(H(Q_i))

(20)

The average number of neighboring hole grid points $\overline{N}$ for all grid points in holl is as follows.

$$\overline{N}=mean\left(N_{\mathrm{neighbor}}\right(Q_i\left)\right)$$

(21)

During hole repairing, the mobile node preferentially moves to the hole grid point Q_i whose number of neighboring hole grid points is larger than the average value $\overline{N}$. A higher number of neighbor hole grid points of the hole grid point indicates a larger range of holes in this area and a greater virtual attractive force on the nodes generated by the center of this hole grid points set. Thus, the additional mobile node Ns_i within the communication range is attracted to move towards this location so that the node coverage utilization is large. In the later stages of hole repairing, all large holes have been repaired, and the mean value of neighboring hole grid points around the hole grid points has been reduced accordingly. The more neighboring hole grid points Q_i has, the farther away it is from the mobile node in the communication range, and the more attractive force it generates. In this way, the nodes are attracted to move quickly towards the larger hole area, always maintaining the optimal coverage utilization of the nodes.

Based on the above analysis, the attractive force field of zero-energy holes that the node Ns_i is subject to is defined by Equation (22).

$$U_3=\left\{Q_j\right|N_{neighbor}\left(Q_j\right)>\overline{N}\&\&dist(N{s}_i,Q_j)\le Rc,Q_j\in holl\}$$

(22)

The virtual attractive force of the hole grid point Q_j on Ns_i in U₃ is calculated as follows:

$$\overrightarrow{F_{\mathrm{holl}(Q_j)}}=(k_{\mathrm{holl}}(N_{\mathrm{neighbor}}(Q_j)\times dist(N{s}_i,Q_j)),{\alpha }_{ij}),\hspace{1em}{Q}_j\in U_3$$

(23)

where k_holl is the attractive force coefficient of hole grid points, α_ij is the direction of the force.

In Figure 4, the virtual attractive force of the hole grid point Q_j on Ns_i is shown. The red points, green points, and blue points form the hole grid point set. The brown point represents the mobile node Ns_i. The green points represent the grid points in U₃, which is obtained by Equation (22).

Then, the attractive force on the node Ns_i by holl is calculated using Equation (24), where holl represents the zero-energy hole.

$$\overrightarrow{F_{\mathrm{h}i}}={\displaystyle \sum _{Q_j\in U_3}\overrightarrow{F_{\mathrm{holl}\left(Q_j\right)}}}$$

(24)

(b) Low energy coverage holes recovery

Redundant repair of low-energy coverage holes can reduce the frequency of new coverage hole emergence due to node energy exhaustion. This redundant recovery strategy guarantees that the network maintains high coverage for a longer period of time and avoids frequent coverage hole patching. Furthermore, it reduces the variance of the network energy density and makes the energy of the patched network more balanced.

The attractive force field of low-energy holes that the node Ns_i is subject to is defined by Equation (25).

$$U_4=\left\{Q_j|dist(N{s}_i,Q_j)\le Rc,Q_j\in Lowholl\right\}$$

(25)

Then, the virtual attractive force of the hole grid point Q_j on Ns_i in U₄ is calculated as follows:

$$\overrightarrow{F_{\mathrm{lowholl}(Q_j)}}=(k_{\mathrm{lowholl}}(N_{\mathrm{neighbor}}(Q_j)\times dist(N{s}_i,Q_j)),{\alpha }_{ij}),\hspace{1em}{Q}_j\in U_4$$

(26)

where k_lowholl is the attractive force coefficient of low energy hole grid points, α_ij is the direction of the force.

Then, the attractive force on the node Ns_i by Lowholl is as Equation (27), where Lowholl represents the low energy coverage hole.

$$\overrightarrow{F_{\mathrm{l}i}}={\displaystyle \sum _{Q_j\in U_4}\overrightarrow{F_{\mathrm{Lowholl}\left(Q_j\right)}}}$$

(27)

(4) The forces of the water bottom or the obstacle

In oceans or lakes, it is common for the water bottom to be very undulating or for there to be large reefs. The algorithm in this paper considers two scenarios in order to better fit the real-world environment. One is the case where the bottom surface of the monitoring area is flat; the other is the case where the bottom surface shows an irregular curved surface or obstacle. For the former case, the nodes are only subjected to the water bottom boundary repulsive force, calculated using Equation (16). For the latter case, the nodes cover the irregular surface and cannot touch or traverse the bottom surface.

The irregular bottom surfaces or obstacles are mesh discretized. The set of grid points with an irregular bottom or obstacles is denoted as Bottom. Their force fields U₅ that the node Ns_i is subject to is defined by Equation (28).

$$U_5=\left\{Q_j\right|dist(N{s}_i,Q_j)\le Rs, Q_j\in Bottom\}$$

(28)

That is, each grid point Q_j generates the virtual force on the nodes within the sensing radius. When the distance between node and grid point is less than or equal to dth, which is a threshold, an infinite force will be generated to keep the node away from the bottom surface or obstacles, guaranteeing that the node will not touch the bottom surface. The virtual force of the grid point Q_j on Ns_i in U₅ is calculated using Equation (29):

$$\overrightarrow{F_{\mathrm{flo}(Q_j)}}=\left\{\begin{array}{l}\infty \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}dist(N{s}_i,Q_j)\le d_{\mathrm{th}}\\ (k_{\mathrm{f}}\times (d_{\mathrm{opt}2}-dist(N{s}_i,Q_j\left)\right), {\alpha }_{ij})\hspace{1em}\hspace{1em} d_{\mathrm{th}}<dist(N{s}_i,Q_j)\le Rs\\ 0\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}dist(N{s}_i,Q_j)>Rs\end{array}\right.$$

(29)

where k_f is the coefficient of force acting on the bottom surface or obstacle, α_ij is the direction of the force, d_opt2 is the same as d_opt1.

Figure 5 shows the force of the mesh point Q_j on the node Ns_i in U₅, and it is calculated using Equation (30).

$$\overrightarrow{F_{\mathrm{f}i}}={\displaystyle \sum _{Q_i\in U_5}\overrightarrow{F_{\mathrm{flo}(Q_i)}}}$$

(30)

(5) Calculation of total virtual force on nodes

Based on the above analysis, the resultant force acting on node Ns_i is calculated by Equation (31).

$$\overrightarrow{F_{N{s}_i}}=\left\{\begin{array}{l}\overrightarrow{F_{\mathrm{E}i}}+\overrightarrow{F_{\mathrm{bor}i}}+\overrightarrow{F_{\mathrm{h}i}}+\overrightarrow{F_{\mathrm{l}i}}+\overrightarrow{F_{\mathrm{f}i}}\hspace{1em}\hspace{1em}Ad{d}_{\mathrm{node}}\ge Ad{d}_{\min }\\ \overrightarrow{F_{\mathrm{E}i}}+\overrightarrow{F_{\mathrm{bor}i}}+\overrightarrow{F_{\mathrm{h}i}}+\overrightarrow{F_{\mathrm{f}i}} \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\mathrm{otherwise}\end{array}\right.$$

(31)

That is, when Add_node ≥ Add_min, the attractive force of the low-energy coverage hole is considered; otherwise, this force is not considered. In the simulation, the values of all force coefficients are obtained by experimental tuning with reference to the comparative literature.

4.3. Calculation of Node Movement Direction and Step Size

By acquiring information around the sensor node, the resultant force $\overrightarrow{F_{N{s}_i}}$ on the node Ns_i and the distance the node has moved D_i determine the position of the node at the next moment in time. In the initial phase, the move step size should be larger, in order for the node to reach the balance position faster. In the later phase, to avoid repeated oscillations of the nodes at the equilibrium position, the step size should decrease with time or the number of iterations until it finally converges to zero. In this paper, the sigmoid function is applied for variable step size calculation.

Let the modulus of $\overrightarrow{F_{N{s}_i}}$ be denoted as $\overrightarrow{\left|F_{N{s}_i}\right|}$, F_min be the minimum force threshold for node movement, Step_max be the maximum movement step, and the coordinate position of node Ns_i at moment t be X(Ns_i,t) =(x_i(t),y_i(t),z_i(t)). When $\overrightarrow{\left|F_{N{s}_i}\right|}\ge F_{\min }$, the position of node Ns_i at moment t + 1 is updated as X’(Ns_i,t+1) =(x_i(t+1),y_i(t+1),z_i(t+1)). When $\overrightarrow{\left|F_{N{s}_i}\right|}<F_{\min }$, the node position is not updated, thus reducing the consumption of repeated movement energy.

The movement distance of node is calculated with Equation (32):

$$D_i=\left\{\begin{array}{l}Ste{p}_{\max }\times \left({\displaystyle \frac{2}{1+e^{-\alpha \left|\overrightarrow{F_{N{s}_i}}\right|}}}-1\right)\hspace{1em}\hspace{1em}\hspace{1em}\left|\overrightarrow{F_{N{s}_i}}\right|\ge F_{\min }\\ 0\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em} \left|\overrightarrow{F_{N{s}_i}}\right|<F_{\min } \end{array}\right.$$

(32)

where α is the step adjustment factor.

Then, the node position at the moment t+1 is calculated with Equation (33).

$$X^{\prime }(N{s}_i,t+1)=X(N{s}_i,t)+D_i{\displaystyle \frac{\overrightarrow{F_{N{s}_i}}}{\left|\overrightarrow{F_{N{s}_i}}\right|}}$$

(33)

In order to improve the node coverage utilization, when the node moves outside the network boundary region according to Equation (33), the node position is corrected to within the region.

5. Description of the CHRVE Algorithm

After initial UWSN deployment, the coverage rate is tested periodically. When a large coverage hole emerges due to some node movement, damage, energy depletion, etc., and the coverage rate falls below the threshold Cth, according to the current state of UWSNs, the appropriate repair strategy is adopted.

In the first scenario, if the UWSN has a sufficient number of redundant and sleep mobile nodes, a certain number of these nodes are woken up to move to repair the hole. In the second scenario, if the UWSN does not have a sufficient number of redundant and sleep mobile nodes, all of these sleep mobile nodes are woken up, and then a certain number of additional mobile nodes are randomly deployed on the water surface.

Both of these scenarios are suitable for launching the proposed hole recovery algorithm in this paper. Based on the virtual force model mentioned in Section 4, the direction and step size of node movement is guided by the distributed computation of virtual forces on the additional nodes, and the nodes are driven towards the target location by means of AUV or other carrier devices. The optimal position for improving coverage rate and node force balance is obtained. Finally, the nodes are secured by ropes and anchors to establish communications.

The CHRVE is described as follows. Algorithm 1 gives the detailed description of the pseudo code.

Step 1. Initialization. The monitoring area is gridded, and the coverage rate is tested periodically. When ƞ < Cth_, where ƞ is the coverage rate of UWSNs, compute the hole grid points Q_i to form the hole grid point set holl_1. The number of neighbor hole grid points N_neighbor(Q_i) for each hole grid point is calculated with Equation (20), and the average number of neighboring hole grid points $\overline{N}$ is calculated with Equation (21). Let the number of iterations k = 1.

Step 2. Sleep nodes in the fixed position are woken up. Monitor whether the coverage rate ƞ now meets coverage requirements of UWSNs. If the coverage rate reaches coverage requirements, the process enters the sleep scheduling procedure, which can be based on the method in [46]. If the awakened nodes are movable and insufficient, and, moreover, the coverage rate ƞ does not meet the monitoring requirements, Add_min is calculated on the water surface with Equation (9), based on which the number of Add_node additional mobile nodes are deployed in monitoring area.

Step 3. Calculate the current existing holes, denoted as holl₂, with Equation (6), and the number of neighboring hole grid points for each existing hole grid point, denoted as ${N^{\prime }}_{\mathrm{neighbor}}\left(Q_i\right)$, with Equation (20). Calculate the number of grid points cnum_i for each mobile node covering the grid points of holl₁.

Step 4. When k < Iter and Equation (34) is satisfied, where Iter is the maximum number of iterations, the virtual resultant force is calculated by Equation (31) acting on $cnu{m}_i<\theta \cdot \xi$ mobile nodes only, where θ and σ are the two threshold coefficients and ξ is the maximum number of grid points that a sensor node can cover, calculated with Equation (5). Then, move the node to the new position calculated with Equation (33).

$$\underset{Q_i\in hol{l}_2}{\max }({N^{\prime }}_{\mathrm{neighbor}}(Q_i))>\sigma \cdot \xi$$

(34)

When k ≥ Iter, go to step 6.

Step 5. When ƞ > β and cnum_i < γ, where ƞ is the coverage rate, cnum_i is the number of grid points for mobile node covering the grid points of holl₁, and β and γ are preset thresholds, in order to avoid nodes falling into local equilibrium and oscillating back and forth, inspired by the fish-swarming algorithm, let the nodes move randomly by one step within the sense range [−αRs, αRs], where α represents the random move step adjust factor. Calculate the virtual force of low-energy coverage holes on the nodes with Equation (26) to guide the nodes to redundantly repair the low-energy holes. Further, the virtual attractive force of the low-energy nodes on the nodes within the communication range is calculated by Equation (14), so that the additional nodes are guided towards the low-energy nodes by the virtual force to balance the energy distribution of the repaired UWSNs. When the node is located outside the network boundary area after moving, correct the node position to be within the area to improve node coverage utilization. k = k + 1 and go to step 3.

Step 6. End of the algorithm.

The pseudo-code for CHRVE is described as follows.

Algorithm 1. Pseudo-code for CHRVE

Initialization of CHRVE parameters (shown as Table 1) Return: The position of additional mobile repairing nodes 1.  The monitoring area is gridded. 2.  Compute the hole grid points $Q_i \mathrm{to} \mathrm{form} \mathrm{the} \mathrm{hole} \mathrm{grid} \mathrm{point} \mathrm{set} {\mathrm{holl}}_1, N_{\mathrm{neighbor}}\left(Q_i\right) \mathrm{with} \mathrm{Equation} \left(20\right), \overline{N}$ with Equation (21), k ← 1 3. If (ƞ < Cth) 4.  Calculate Addmin with Equation (9). Set the value of Addnode based on Addmin. 5.  Deploy Addnode additional mobile nodes in monitoring area. 6. End if 7. While (k < Iter and Equation (34)) 8.   Calculate ${\mathrm{holl}}_2 \mathrm{with} \mathrm{Equation} \left(6\right), {N^{\prime }}_{\mathrm{neighbor}}\left(Q_i\right)$, with Equation (20) and cnumi 9.   Calculate the virtual resultant force with Equation (31) acting on ${cnum}_i<\theta \cdot \xi$ mobile nodes only. 10.   If (Addnode > Addmin) 11.    Calculate the virtual force of low-energy coverage holes on the additional mobile nodes with Equation (26). 12.    Calculate the virtual attractive force of the low energy nodes on the additional mobile nodes within the communication 13.    range is by Equation (14). 14.   End if 15.   Move the mobile node to the new position calculated with Equation (33). 16.   k ← k+1 17.  End while

6. Simulation and Experimental Analysis

6.1. Simulation Scenario and Parameter Settings

The proposed CHRVE algorithm is implemented and simulated by MATLAB 2020 program. The parameters are set as follows: The monitoring area underwater is set to 100 m × 100 m × 100 m, Rs = 20 m, Rc = 2Rs = 40 m. The base station Sink is located on the water surface with coordinates (50, 50, 100) m.

The parameter settings of the algorithm are shown in

Table 2. Simulation parameter settings.

Parameter Names	Definition	Value
Cth	The threshold value of coverage rate	75%
α	The random move step adjustment factor	0.6
β	The preset thresholds for redundancy repairing low-energy node coverage	90%
γ	The preset thresholds for coverage hole points	5
μ	The correction factor for node utilization rate	0.7
Stepmax	The maximum movement step	6 (m)
E0	The initial value of energy	rand [1, 20] J
E′0	The initial value of energy for the additional nodes	rand [18, 20] J
Eth	The energy threshold for repairing nodes	3 J
Fmin	The minimum force threshold for node movement	10
krep	The repulsive force coefficient of inter-node	106
katt	The attractive force coefficient of inter-node	105
ksix	The repulsive force coefficient of boundary surface	200
kholl	The attractive force coefficient of grid point	10
kf	The repulsive force coefficient of obstacle	10
klowholl	The attractive force coefficient of low-energy coverage holes	10
σ, θ	The threshold factor	0.1, 0.8
Ex1, Ey1, Ez1	The energy consumption of node moving in positive direction per unit distance along the x, y, z axes	0.02 J, 0.05 J, 0.08 J
Ex2, Ey2, Ez2	The energy consumption of node moving in negative direction per unit distance along the x, y, z axes	0.05 J, 0.02 J, 0.01 J

. In this simulation, when the coverage rate falls below 75%, it will be very poor coverage and connectivity performance, possibly due to the emergence of coverage holes, and then launch the CHRVE algorithm. Thus, Cth is set with 75% in the following simulation. The energy consumption of node moving in different directions per unit distance along the x, y, z axes is set with reference to [35]. The other parameters are set with experiments based on the current literature [35,36,37,38,39,40,41,42,43].

In order to fully validate the performance of the CHRVE algorithm, the hole repair simulation experiments are performed under the different coverage hole scenarios generated by different deployment modes for various situations, such as random deployment, static deployment of truncated regular octahedron, and specific deployment, with different coverage hole shapes and locations.

In order to verify the adaptability and robustness of the algorithm to the shape, number, and size of coverage holes, a series of simulation experiments is carried out for a variety of scenarios with only one central closure hole, multiple non-closed holes and different holes shapes, respectively. Some verification experiments and analyses are also performed for the impact of the number of additional nodes on the coverage rate and the impact of the different initial positions of additional nodes on the performance of the algorithm. The parameter settings for these verification experiments are the same as in Table 1. The hole recovery situations that the water bottom surface is curved or there are obstacles are simulated and analyzed. Furthermore, for the case Add_node > Add_min, the balance of energy distribution after hole recovery by the CHRVE algorithm is analyzed based on the energy density variance of Definition 2, and the node movement energy consumption in the case of water movement is also simulated.

In the experiments, the additional repairing nodes take two random scattering patterns to deploy in UWSNs. One is to randomly spread the additional repairing nodes in the monitoring area and then randomly dive down to a certain depth as their initial position. For convenience of description, this scattering pattern is called RDHPM (random diving hole patching mode). The other is to randomly spread the additional repairing nodes on the water surface as their initial position, which is called RSWFHPM (random scattering for water surface hole patching mode). The robustness of the CHRVE algorithm to the initial position of the additional nodes is verified through experiments and analyses of the two patching modes.

6.2. Experiments and Analyses on Holes Repair with Different Hole Sizes, Numbers, and Shapes

(1) Experiment and analyses on repairing irregular coverage holes after random deployment

The coverage hole formed by the remaining 34 nodes of the random deployment network in Figure 6a is taken as the initial state for hole recovery, where the blue grid spheres indicate the coverage area of the remaining nodes, the coverage rate of which is 57.5%. Calculate Add_min = 27 using Equation (9) and set Add_node = 27. The additional repairing nodes are deployed with RDHPM mode, with an initial coverage rate of 75.9%. As shown in Figure 6b, for the initial simulation of 27 additional mobile nodes to repair the holes, the red solid spheres indicate the coverage area of the additional node. Figure 6c shows the coverage of the CHRVE algorithm after 11 iterations, and the coverage rate after hole recovery is 93.3%.

Figure 7 shows the average coverage rate variation for 30 runs of this algorithm with the additional repairing nodes. As can be seen from Figure 7, the CHRVE algorithm converges fast. In this experiment, the coverage rate can reach more than 92% after 11 iterations and tends to converge stably.

(2) Experiment and analyses on repairing multiple non-closed holes after static deployment

Figure 8a shows the boundary non-closed coverage holes after the static deployment of a truncated regular octahedron. The coverage rate before repairing is 70.34% initially. Calculate Add_{min =} 19 using Equation (9) and set Add_node = 19 in the actual experiment. The additional repairing nodes are deployed with RDHPM mode, with an initial coverage rate of 81.91%. Its coverage simulation is shown in Figure 8b. The coverage rate is 94.94% after eight iterations of the CHRVE algorithm. If the additional repairing nodes are deployed with RSWFHPM mode as shown in Figure 8c, the initial coverage rate is 74.23%. The coverage rate reaches 93.44% after running the CHRVE algorithm for 20 iterations.

Figure 9 shows the variation of the average coverage rate with the number of iterations for running the experiment 30 times using two patching modes with different numbers of additional repairing nodes.

(3) Experiment and analyses on repairing central closure holes after static deployment

The simulation experiments are performed for repairing the central closure holes after the fixed static deployment network shown in Figure 10a. The initial number of nodes before hole repairing is 39, and the coverage rate before repairing is 69.1%. Calculate Add_min = 20 using Equation (9). Figure 10b shows the initial hole repair situation after the 20 additional repairing nodes deployed with RDHPM mode, at which the initial coverage rate is 83.22%. After 10 iterations of the CHRVE algorithm, the coverage rate is 94.72%. If the additional repairing nodes are deployed with RSWFHPM mode as shown in Figure 10c, the initial coverage rate is 69.99%. The coverage rate is 93.15% after running the CHRVE algorithm for 25 iterations.

Figure 11 shows the variation of the average coverage rate with the number of iterations for running the experiment 30 times using two patching modes.

As can be seen from Figure 9 and Figure 11, although the difference in coverage rate between the RDHPM and RSWFHPM patching modes is large at the beginning, this difference in coverage rate between them decreases as the number of iterations increases. Both patching modes can achieve high coverage rates of over 95% after 40 iterations. This validates the robustness of the CHRVE algorithm to the initial position of the additional repairing nodes. Furthermore, when Add_min > Add_node, there is little difference in coverage rate across iterations between the two patching modes. This suggests that after the number of additional nodes has reached the theoretical number of nodes to repair the holes, further additional nodes to repair the holes have a limited effect on further improving the network coverage rate. Therefore, based on the proposed algorithm in this paper, these extra additional nodes can be used for redundant repair of low-energy coverage holes. This redundant repair strategy is used to improve the balance of energy distribution after repairing holes, increase network reliability, and reduce the frequency of coverage holes that occur again when nodes run out of energy in a short period of time.

6.3. Experiments and Analyses on Energy Density Distribution for Coverage Holes Recovery

According to the energy density and variance calculated by Definition 2, the energy distribution balance is measured and analyzed in this experiment. Figure 12 shows the coverage holes formed by the remaining 38 nodes. The coverage rate before repairing is 70.24% initially, in which six nodes have residual energy below the threshold value of 3 J, and the rest of the nodes have residual energy in the range of [10, 20] J, with an average energy of 15.17J. Calculate Add_min = 19 using Equation (9) and set the actual number of additional nodes Add_node = 25. Since Add_node > Add_min, a redundant repair of low-energy coverage holes is required based on the repair strategy of the CHRVE algorithm.

Figure 13a shows the variation of coverage rate, energy density variance with the number of iteration rounds. Figure 13b shows the comparison of the energy density variance between enabling redundant repair and not enabling redundant repair for the coverage hole recovery shown as Figure 12. The calculation results are the average for running experiments 30 times in respective conditions.

As can be seen in Figure 13a, both patching modes obtain a significant increase in coverage rate as the number of iterations increases. The RDHPM mode converges quickly and achieves a high coverage rate of over 90% in four iterations, and the RSWFHPM mode achieves an over-90% coverage rate in sixteen iterations. The energy density variance, which reflects the energy balance of the nodes in UWSNs, decreases significantly with the increasing number of iterations for both patching modes. Therefore, the redundant repair of low-energy coverage holes by the CHRVE algorithm effectively balances the network energy, which can reduce the frequency of new coverage hole emergence due to node energy exhaustion. Thus, the CHRVE algorithm can guarantee that the network maintains a high coverage rate for a longer period of time and avoids frequent coverage hole repairing. As can be seen from Figure 13b, when Add_node > Add_min, enabling node redundant repair effectively reduces energy density variance compared to not enabling node redundant repair. This furtherly demonstrates that the redundant repair strategy in the CHRVE algorithm can effectively repair low energy coverage holes and balance the network energy distribution.

6.4. Experiments and Analyses on Coverage Hole Recovery with Water Bottom Curved Surfaces and Obstacles

In order to verify the performance of the CHRVE algorithm for coverage hole recovery in the scenarios where the water bottom has complex terrain or obstacles, the simulation experiments for holes recovery are carried out on the monitoring area shown in Figure 14a, in which the bottom is an irregularly curved surface and contains complex underwater terrain such as reefs and crustal uplifts. The sensors are deployed in the monitoring area shown in Figure 14b, which contains the complex underwater terrain and obstacles of Figure 14a. The simulation experiments are performed for the coverage holes in this scenario, as shown in Figure 14b, and the initial coverage rate before hole repairing is 66.3%. Calculate Add_min = 21 using Equation (9). Figure 14c shows the initial hole repair situation after the 26 additional nodes deploying with RDHPM mode, at which the initial coverage rate is 76.8%. Figure 14d shows the coverage state after 11 iterations of the CHRVE algorithm, at which the coverage rate achieves 94.9%. As shown in the figure, the nodes not only cover the holes in the network but also provide good coverage of complex environments such as underwater surfaces (including obstacles).

Similarly, for the monitoring area shown in Figure 14a, the 26 additional nodes are deployed with RSWFHPM mode to perform the simulation experiments. Figure 15 shows the variation of node coverage rate and energy density variance with the number of iteration rounds. As can be seen from this figure, with the number of iterations increasing, the overall trend of the energy density variance keeps decreasing while the coverage rate of the two repair modes RDHPM and RSWFPM gradually increases. This validates that, for the case of coverage hole recovery in underwater complex terrain, the redundant repair strategy of the CHRVE algorithm for low-energy coverage holes can also effectively balance the network energy distribution.

6.5. Experiments and Analyses on Movement Energy Consumption of Additional Nodes in Complex Underwater Environments

The structure of the additional underwater sensor nodes is quite different from that of land-based sensors. Due to the water flow, nodes consume different amounts of energy per unit of distance movement in different directions. The experiments and analyses are also performed on movement energy consumption when hole repairing in complex underwater environments.

Figure 16 shows the variation of movement energy consumption with the number of iterations by the two patching modes for the examples in Section 6.3 and Section 6.4, respectively, when the number of iterations is 40. Let the algorithm be ended when the preset coverage rate p₀ ≥ 92%. Then, for the example of Section 6.3, the hole repairing with RDHPM mode requires four iterations on average to achieve the preset coverage rate. The total movement energy consumption, including the random sinking and each iteration of movement for each mobile node, is 50.3 J. In contrast, the hole repairing with RSWFHPM mode requires 20 iterations to achieve the preset coverage rate, and its movement energy consumption is 119.1J. For the example of Section 6.4, the hole repairing with RDHPM mode requires nine iterations to reach the preset coverage rate, and its total energy consumption is 49.5J. The hole repairing with RSWFHPM mode requires 26 iterations to reach the preset coverage rate, and its total energy consumption is 257.2J.

Although both patching modes can eventually achieve the preset coverage rate, the number of iterations and movement energy consumption of the RDHPM mode is less than that of the RSWFHPM mode. Therefore, the experimental analyses show that the RDHPM is more suitable for hole repairing in water flow if the actual conditions allow. Under the actual patching mode, the nodes are randomly sunk to a certain depth by node gravity, and then the virtual force on the nodes is calculated and the nodes are moved. This repair approach not only improves network coverage rate faster but also consumes less energy for node movement.

6.6. Comparative Experiments on Different Algorithms

In order to fully validate the performance of the CHRVE algorithm in terms of coverage rate, energy balance, and so on, taking the central closure coverage hole shown in Figure 10a as the scenario, the CHRVE algorithm is compared with 3D-SCHDR [43], 3D-DVFA [42], and 3DSD [41] algorithms, which have been investigated in recent years for 3D coverage and hole repair based on virtual forces. The 3D-DVFA and 3DSD algorithms are redeployment algorithms that require all nodes to be mobile nodes, and, in this paper, the simulation is performed using its virtual force calculation method only for the additional mobile nodes.

The comparison of coverage rates using each algorithm with different numbers of additional repairing nodes is shown in Figure 17, where the number of additional repairing nodes is incremented from 10 to 28 in steps of three. As can be seen from the figure, the four algorithms have the lowest coverage rate at the minimum number of additional repairing nodes. With the increase in the number of additional repairing nodes, the coverage rate of each algorithm increases gradually, and the coverage performance of the CHRVE algorithm is better than that of the other three algorithms. In addition, when the number of additional repairing nodes is greater than 19, the growth of the coverage rate of the CHRVE algorithm will gradually become flat as the number of additional repairing nodes continues to increase. This is due to the redundant repair strategy of low-energy coverage hole in this paper. In this experiment, Add_{min =} 20 is calculated with Equation (9). After the number of additional repairing nodes reaches Add_min, the extra additional nodes will be mainly used for redundant repair of low-energy coverage holes, which will have limited effect on further improvement of the coverage rate.

Figure 18 shows the distribution of energy density variance for the four algorithms at different numbers of additional repairing nodes. The energy density variance values of the 3D-SCHDR, 3D-DVFA, and 3DSD algorithms in the figure are calculated after the hole repairing according to Definition 2. As can be seen from the figure, the energy density variance of the CHRVE algorithm is lower than that of the other three algorithms at each number of additional repairing nodes. In particular, the energy density variance of the CHRVE algorithm is even more significantly lower than that of the other three algorithms after the number of additional repairing nodes reaches 19. This is due to the redundant repair strategy of low-energy coverage holes, which guarantees that the hole repair can achieve a good energy balance.

From these experiments, we can see that the CHRVE algorithm in this paper has good adaptability to the underwater environment, regardless of whether the initial coverage is random deployment or static deployment based on some rules, whether the coverage holes are large single holes, multiple non-closed holes or irregular coverage holes, whether the initial additional repairing nodes are deployed at the water surface or randomly sunk to a certain depth, and whether the terrain of the water bottom surface is flat, curved, or there are large obstacles. The CHRVE algorithm has a high node-utilization rate, so it requires a small number of additional repairing nodes for hole recovery. In addition, the algorithm has a great effect in improving the coverage rate, fast convergence speed, and strong robustness. Furthermore, the algorithm significantly improves the network energy balance under the premise of guaranteeing the network coverage quality, which can reduce the frequency of new coverage holes emergence due to node energy depletion and reduce the number of holes to repair. Therefore, the CHRVE algorithm effectively improves network reliability and reduces the cost of maintaining the network.

7. Conclusions

In this paper, a coverage hole recovery method based on virtual force guidance and energy balance is proposed. Some new concepts such as energy density, zero-energy holes, and low-energy coverage holes are defined to improve the energy balance. The energy-based virtual force model is constructed considering complex environmental factors such as water flow, complex underwater terrain and obstacles, and energy balance of sensor nodes, etc. Based on this model, the CHRVE algorithm for UWSNs is proposed.

The simulation experiments verify the performance of the CHRVE algorithm. They are analyzed in terms of coverage rate and energy density variance in comparison with the recent 3D coverage algorithms 3D-SCHDR, 3D-DVFA, and 3DSD. The simulation results show that the CHRVE algorithm has very good adaptability and robustness to the form of network deployment, the number, shape, size, and location of 3D coverage holes, as well as the initial scattering location of the additional repairing nodes. The algorithm requires fewer repairing nodes with a high node utilization rate, and it has fast convergence and significantly improves the coverage rate. Moreover, the proposed redundant repair strategy of low-energy coverage holes significantly improves the network energy balance under the premise of guaranteeing the network coverage quality, which can reduce the frequency of new coverage holes emerging. Thus, it can reduce the hole repair frequency. Therefore, the methodology proposed in this paper is of great significance for further improving the network service quality and extending the network life cycle.

In some special underwater situations, if the boundary position of the underwater coverage holes can be accurately detected, more efficient and precise methods can be used for coverage hole repair. Therefore, as future work, we plan to study the detection of underwater 3D coverage holes boundaries. We also plan to study the node clustering and node sleep scheduling strategies in the future.