Sage Journals: Discover world-class research

Abstract

Limited energy, high mobility, and unsteady acoustic communication links render the underwater acoustic sensor networks subject to performance reduction. To solve this problem, a topology optimization method, also called TO-A algorithm, is developed based on topology reconfiguration. First, the proposed method optimizes the coverage rate of underwater acoustic sensor networks by adjusting the location of sensor nodes through simulating fish behaviors. Second, to optimize the connectivity of underwater acoustic sensor networks, the proposed method, using edge nodes, repairs disconnected positions and eliminates key nodes in underwater acoustic sensor networks. Third, a topology optimization strategy, also called TO-DA algorithm, is developed for Double-autonomous underwater vehicles to improve the robustness and adaptability of the network topology. When the inherent law of underwater acoustic sensor networks topology formation is further found, the method for optimizing network topology is proposed, which based on the triangle principle eliminates those key nodes and can help with the survivability of network regeneration. The method proves reasonable and valid by stimulation and contrast examinations. The comparison of TO-A algorithm and TO-DA algorithm shows that under low energy consumption, TO-A algorithm can keep the network coverage at about 97% for a long time, connectivity rate above 89%, while the TO-DA algorithm can improve the survivability of the network by above 50% at the expense of 8.5% of the network coverage.

Keywords

Underwater acoustic sensor networks Double-autonomous underwater vehicles topology optimization

Introduction

Underwater acoustic sensor networks (UASNs) are capable of underwater environment in real time, accurate and effective monitoring, and can be widely applied to various fields such as underwater military target surveillance,²⁴ marine data collection, monitoring water quality, seabed mineral resources exploration, and assisted navigation.^1,25–30 The quality of communication among the sensor nodes and the reliability of topology of UASNs have been seriously affected due to the factors of complex marine environment, such as the high latency, low bandwidth, and easy attenuation of signal and multipath effects, seriously affecting.^15–23 Currently, optimization for terrestrial sensor networks has some achievements. Fu and Han² solve the sensor node–distributed optimization problems of the terrestrial sensor network by quantum genetic algorithm; Aziz et al.³ consider comprehensively the battery power of sensor and other factors, then employing the distributed topology control technology to optimize the energy consumption of wireless sensor networks; Wang et al.⁴ present a parallel particle swarm optimization (PSO) strategies based on the mobility of sensor node, so that distribution of the node in sensor networks reaches local optimum; Mi and Zhou⁵ proposed a terrestrial wireless sensor network routing algorithm multi-objective optimization. Considering the particularity of UASNs in complex environments and underwater acoustic communication mode, Pioneers’ achievements in the optimization strategy are not fully applicable to UASNs. As adopted in Jafri et al.,⁶ the connectivity of UASNs has been optimized from the aspect of protocol design, but there are key nodes in the UASNs, making the invulnerability of network topology unable to be improved (the key node means all single-hop neighbor nodes of this node belong to subsets which do not communicate with each other with the number of subsets at $k (k \geq 2)$ and these subsets are connected by this node only). As adopted in Xia et al.,⁷ the fish-inspired underwater acoustic sensor node deployment algorithm optimized the coverage of topology of the UASNs. As adopted in Manjula and Sunilkumar,⁸ the particle swarm algorithm achieved optimization for the layout of the underwater acoustic sensor node. Both algorithms make the distribution density of the sensor nodes and the distribution density of the target event to attain a nice match so that the approximate optimal for the coverage of UASNs is realized. However, there are also some limitations as follows:

It cannot ensure the communication between the all sensor nodes;

Throughout the life of UASNs always exist the key nodes, and this problem has not been effectively solved;

The interruption phenomenon happens during data collection of sensor nodes;

On the condition of being difficult to replace the equipment (e.g. the sensor) under water, it cannot maintain effective monitoring during the long-time mission.

This article takes into consideration both relevant features of UASNs and topological reconstruction of the underwater non-uniform coverage of UASNs. Moreover, we use the autonomous underwater vehicles (AUVs) to present two different methods for the topological optimization of two kinds of UASNs based on, respectively, topology reconfiguration (TO-A algorithm) and Double-autonomous underwater vehicle (Double-AUV); a new version of AUVs (TO-DA algorithm) is proposed in this article, which can overcome those limitations mentioned above. TO-A algorithm is divided into two stages: in the first stage, the artificial fish swarm algorithm (AFSA) is adopted to readjust the position of the sensor nodes that are inspired by node deployment algorithm⁷ and then the coverage of the UASNs is optimized; in the second stage, the entire connectivity of the UASNs is restored using edge node in the UASNs to repair the disconnected position and eliminate key nodes to improve the invulnerability of network, so as to made up for the shortage of AFSA in the first stage. Shadow zones cause high bit error rates, loss of connectivity, and dramatical impact,^9,31–33 so this article presents a new version of AUVs, called Double-AUVs (see Figure 1). By this way, (1) the connectivity among UASNs inside the shadow zone is established by Double-AUVs so as to avoid an information collection vacuum period generated by shadow zone while its carrying out mission; (2) a topology optimization mechanism based on Double-AUVs is adopted which is proposed in this article and an UASN’s key node is eliminated by triangle dilute methods to extend the life cycle of UASNs by sacrificing part of the coverage of the UASNs.

Figure 1.

The reason for Double-AUVs.

The remainder of this article is organized as follows. In section “Network model and problem description,” we present our system model and raise the problem that needs solving. In section “The TO-A algorithm,” our new algorithm (TO-A algorithm) is described in detail. In section “The TO-DA algorithm,” we present our mechanism of topology optimization. An empirical evaluation of TO-A algorithms and TO-DA algorithm is provided in section “Experimental study.” The article concludes with recommendations for future work in section “Conclusion.”

Network model and problem description

Network model

m events, to be monitored, are unevenly distributed in the target area D. Monitoring event set is defined as $T = {t_{1}, t_{2}, t_{3}, \dots, t_{m}}$ , $(t_{i} \in D, i = 1, 2, \dots, m)$ ; the UASNs consist of underwater acoustic sensors implemented for coverage of the event. The set of sensors is defined as $S = {s_{1}, s_{2}, s_{3}, \dots, s_{n}}$ ; they are deployed with $k$ AUVs (AUVs denote normal AUVs in TO-A algorithm, and Double-AUVs in TO-DA algorithm). AUVs are defined as $A = {a_{1}, a_{2}, a_{3}, \dots, a_{k}}$ in TO-A algorithm, at the same time Double-AUVs are defined as $A = {a_{1}, a_{2}, a_{3}, \dots, a_{k}}$ and $B = {b_{1}, b_{2}, b_{3}, \dots, b_{k}}$ . B stands for the sensor set installed on Double-AUVs. These two types of AUVs collectively stand for AUV nodes in the model. Sensors and AUVs are selected using an omni-directional Boolean sensing model. $r^{s}$ and $r^{c}$ represent maximum sensing radius and communication radius of sensor nodes, respectively. $r_{a}^{s}$ refers to maximum sensing radius, while $r_{a}^{c}$ denotes the communication radius of AUV nodes.

Definition 1. Coverage is represented as the ratio of the total event monitored by sensor nodes arranged in the monitoring area and the total number of events actually exist in the monitoring area.^34,35

Definition 2. Neighborhood topology is represented as local network topology that is constituted of neighbor nodes directly connected to sensor node $S_{i}$ . It is defined as $Φ (s_{i}) = G (Λ (s_{i}), E (s_{i}))$ , where $Λ (s_{i})$ denotes set of nodes in the neighborhood of $s_{i}$ and $s_{j}$ denotes set of links in the neighborhood of $s_{i}$ .

In order to match with the actual situation, the energy consumption of sensor nodes in coordinate axis (include x, y, and z axes) moving per unit distance is, respectively, defined as $\vec{C_{x}}$ , $\vec{C_{- x}}$ , $\vec{C_{y}}$ , $\vec{C_{- y}}$ , $\vec{C_{z}}$ , and $\vec{C_{- z}}$ . The energy consumption of sensor node move per unit distance in any direction (defined as $\vec{C_{i}}$ ) can be calculated by the vector-calculation.

Definition 3. The total energy consumption of movement of sensor nodes in UASNs is measured as follows

$C = \sum_{i = 1}^{n} \sum_{\forall d} | {\vec{C}}_{i} \times {\vec{d}}_{i} |$ (1)

where $| \vec{d_{i}} |$ represents moving distance of node $S_{i}$ in a certain direction during the process of optimization, and $di s_{i}$ represents the total distance of node $S_{i}$ moves. In other word, $di s_{i}$ is the total value of moving distance of node $S_{i}$ in all directions, measured as $di s_{i} = \sum_{\forall d} | \vec{d_{i}} |$ .

In this article, sensor nodes are divided into three categories: key nodes, edge nodes and ordinary nodes.

Definition 4. If the sensor nodes are removed to increase the number of connectivity of UASNs branch, such kinds of nodes are called key nodes.

Definition 5. Peripheral node (or the importance of node is low), in the other word, removing the sensor nodes causes neither increasing the number of connectivity of UASNs branch nor generating a key node, is called edge node.

Definition 6. In addition to the edge nodes and the key nodes, other nodes are known as the ordinary nodes.

Hypothesis 1. Underwater acoustic sensors have function about auxiliary locating. The node can exchange information between adjacent nodes to get the set $Λ (s_{i})$ . Through the set $Λ (s_{i})$ , we can know the location of their own and other nodes.

Hypothesis 2. AUVs node can communicate directly with the base station on the water.

Hypothesis 3. In the process of mission, the energy of AUVs node approximates infinitely large (represent $+ \infty$ ).^36–38

Hypothesis 4. There will be no new failure while topology optimization is performed by AUVs.

Hypothesis 5. There is no data loss when communication occurs among nodes.

Hypothesis 6. $r^{c} < r_{a}^{c}$ . Meanwhile, AUVs can adjust the radius of perception and the radius of communication to the maximum range according to actual requirements.

Given the high cost of AUVs, the number of AUVs should be much smaller than the number of sensors, namely $K < < N$ .

Relevant judgment

Calculation of neighborhood topology of nodes

According to the Hypothesis 1, the sensor node $s_{i}$ knows its own location and location of the sensor in its neighborhood, so we can compute the corresponding neighborhood topology as follows

$Φ (s_{i}) = G (Λ (s_{i}), E (s_{i}))$ (2)

There is an example (see Figure 2): node $S_{7}$ knows location of node $S_{6}$ , node $S_{8}$ , and node $S_{9}$ , and node $S_{6}$ knows location of node $S_{2}$ , node $S_{5}$ , and node $S_{7}$ ; so, we know the length of link $e_{7, 8} (s_{7}, s_{8})$ , the length of link $e_{7, 9} (s_{7}, s_{9})$ and the angle between link and link, set as; then, we can calculate the angle between link $e_{7, 8} (s_{7}, s_{8})$ and link $e_{7, 9} (s_{7}, s_{9})$ and set as $α$ according to cosine theorem and sine theorem; finally, we can know clearly the angle between link $e_{7, 9} (s_{7}, s_{9})$ and link $e_{8, 9} (s_{8}, s_{9})$ , set as $γ$ . Meanwhile, we can judge whether a communications link exists between node $s_{8}$ and node $s_{9}$ by equation (3). We can obtain their neighborhood topology $Φ (s_{7})$ according to the state in equation (3)

${\begin{matrix} dis (s_{8}, s_{9}) = \\ \sqrt{len {(e_{7, 8})}^{2} + len {(e_{7, 9})}^{2} - 2 len (e_{7, 8}) len (e_{7, 9}) \cos α} \\ dis (s_{8}, s_{9}) \leq r^{c}, state : connected \\ dis (s_{8}, s_{9}) > r^{c}, state : disconnected \end{matrix}$ (3)

Figure 2.

Local network topology: (a) the local topology.

Judgment for the key node and the edge node

Uneven characteristics of actual network are reflected in the network model, so there are key nodes and non-key nodes. In this article, we have a more detailed classification of the non-key nodes, the ordinary nodes, and the edge nodes. In order to prevent the network topology from breaking off after the node has been removed, the neighborhood topology of the node is supposed to be connected. That neighborhood topology of the node is connected is the sufficient condition to ensure that the network topology is still connected after the node was removed. We can obtain neighborhood topology $Φ (s_{i})$ of node $s_{i}$ by the above method and then we can get the reachability matrix according to neighborhood topology $Φ (s_{i})$ . As shown in Figure 3, (a) represents the neighborhood topology of node $s_{7}$ ; (b) represents the reachable matrix in the neighborhood of node $s_{7}$ . The reachable matrix formalism describes the reachable relation among the nodes in the neighborhood topology of certain nodes.

Figure 3.

Neighborhood topology of $s_{7}$ and the neighborhood node reachability matrix: (a) the neighborhood topology of node $S_{7}$ and (b) the reachable matrix in the neighborhood of node $S_{7}$ .

The set of neighbor of the node $S_{i}$ is represented as $Λ (s_{i}) = {s_{j} | d (s_{j}, s_{i}) \leq r^{c}, j = 1, 2, \dots, n}$ and a judgment set is established as $P (s_{i}) = \emptyset$ , according to reachable matrix of nodes in neighborhood of node $s_{i}$ , and the elements of the reachable matrix of the node $s_{i}$ are represented by $A_{ij}$ :

Node $s_{j}$ , that matrix elements satisfy $A_{ij} = 1$ is added to the set $P (s_{i})$ ;

Check the values of $A_{kj}$ in the set $P (s_{i})$ where the node $s_{k}$ exists in the reachable matrix $Φ (s_{i})$ . If $A_{kj} = 1$ , add node $s_{j}$ to the set $P (s_{i})$ ;

Repeat above procedure until all nodes in the set $Λ (s_{i})$ are visited;

Compare the set $P (s_{i})$ and the set $Λ (s_{i})$ . If $P (s_{i}) = Λ (s_{i})$ , it indicates that the neighborhood topology of node $s_{i}$ still remains connected after the node $s_{i}$ is removed and the node $s_{i}$ is a non-key node. Then continue to judge whether the node $s_{i}$ is the edge node; if $P (s_{i}) / = Λ (s_{i})$ , it proves that the node $s_{i}$ is a key node, marked the node as $s_{i}$ .

For example (see Figure 2), the set of neighbor of the node $s_{7}$ is $Λ (s_{7}) = {s_{6}, s_{8}, s_{9}}$ , yet $P (s_{7}) = {s_{8}, s_{9}}$ , so it is obviously $P (s_{i}) \neq Λ (s_{i})$ . We know node $s_{8}$ and node $s_{9}$ belong to the same connected branch, but node $s_{6}$ is an isolated node. As a result, the node $s_{7}$ is judged to be the key node and the failure of node $s_{7}$ leads to large probability of network topology segmentation.

After determining the node $s_{i}$ is not the key node, make judgment about edge node. Assuming node $s_{j}$ as the neighbor node of node $s_{i}$ , its neighborhood topology is $Φ (s_{j})$ , delete $s_{i}$ from $Φ (s_{j})$ , and then determine whether the node $s_{j}$ is the key node by the method of judging the key nodes. If the node $s_{j}$ is the key node, it is shown that the removal of $s_{i}$ will generate a new key node. So, $s_{i}$ is not an edge node; otherwise, $s_{i}$ is the edge node, which is marked.

A method of localization of underwater sensor network is proposed by Heidemann et al.,¹⁰ and its effectiveness is verified by experiments on the sea. In this article, we use AUVs to patrol the mission area, gathering information about the marine environment, and the location of the nodes. And the location of the disconnected position is located by the method mentioned above.¹⁰

Goal description

The UASNs topology changes frequently, resulting in the decrease of network performance due to the complex ocean environment. In order to improve the performance of UASNs topology and prolong the network lifetime, the network topology optimization mechanism based on AUVs is proposed (for both TO-A and TO-DA algorithms). Two optimization processes of the algorithm are shown in the following figure. Figure 4 is a schematic diagram of the optimization process of two algorithms.

Figure 4.

The flowchart of topology optimization.

The TO-A algorithm

Coverage optimization for UASNs inspired by fish swarm

In the process of UASNs coverage optimization inspired by fish swarm, the sensor nodes are treated as artificial fish, events in the target monitoring area are used as food, the process of sensor nodes tending to events is equivalent to the process of artificial fish looking for food, and the sensor node simulates fish foraging, rear-end collision, and clustering behavior in order to complete the adjustment of positions. The perception of artificial fish is greater than its communication range (because the perception of sensor nodes is greater than its communication range), set to visual (the sphere range that artificial fish itself is regarded as the center of the sphere and $r^{s}$ as the radius), the step size of maximum movement is $l_{step}$ , $\vec{L_{i}}$ represents the current position of the artificial fish $s_{i}$ , and the number of iterations is MaxIter.

Definition 7. Fitness is the number of targets covered by a sphere with a radius $r^{s}$ for a sensor in the target monitoring area. The fitness can be expressed by equation (4)

$N_{sensor} (s_{i}) = | {t_{j} | d (s_{i}, t_{j}) \leq r^{s}, j = 1, 2, \dots, m} |$ (4)

Definition 8. The number of sensors that covers target event $t_{j}$ is called covering multiplicity of $t_{j}$ , covering multiplicity can be expressed by equation (5)

$K_{e_{j}} = \sum_{i = 1}^{n} J (d (s_{i}, t_{j}) \leq r^{s})$ (5)

where $J (\cdot)$ represents the indicator function. When the condition in brackets is satisfied, its value was 1, otherwise, its value was 0.

Definition 9. The allowable degree of crowding around a location in a target monitoring area is called congestion factor.

The allowable degree of crowding is known as the congestion factor, around a location in the target monitoring area. The congestion factor of the sensor A is expressed as

$δ (s_{i}) = {\bar{K}}_{\deg} \times N_{sensor} (s_{i})$ (6)

where the constant ${\bar{K}}_{\deg}$ is the expected covering multiplicity of a single event and $N_{sensor} (s_{i})$ represents the number of events in the coverage of sensor $s_{i}$ .

$N_{neigh} (s_{i})$ represents the number of sensor nodes in the neighborhood of the sensor $s_{i}$ and $N_{near} (s_{i})$ represents the number of sensor nodes in the sensing range of sensor $s_{i}$ .

The process of coverage optimization of UASNs inspired by fish swarm is as follows:

Step 1 $N_{sensor} (s_{i}) = 0$ can be divided into three cases.

Step 1.1 $N_{neigh} (s_{i}) = 0$ , then perform foraging operations: randomly chosen to move in any direction when the step size does not exceed $l_{step}$ in the perception range visual of the artificial fish and the new position is expressed as

$\vec{{L'}_{i}} = \vec{L_{i}} + rand (l_{step}) \frac{\vec{{L'}_{i}} - \vec{L_{i}}}{| \vec{{L'}_{i}} - \vec{L_{i}} |}$ (7)

where $rand (l_{s tep})$ represents a random number from 0 to the maximum step size $l_{s tep}$ . If the artificial fish is moved, which means that the sensor node to $\vec{{L'}_{i}}$ makes the $N_{sensor} (s_{i})$ increase, the foraging operation was successful. Otherwise, the foraging operation failed.

Step 1.2 $N_{neigh} (s_{i}) > 0$ , then perform rear-end collision operation: find the optimal neighbor nodes $s_{b}$ , that is to say, $s_{b} = \arg ma x_{s_{j} \in Λ (s_{i})} {N_{sensor} (s_{j})}$ , if $N_{sensor} (s_{b}) > N_{sensor} (s_{i})$ and $N_{near} (s_{b}) < δ (s_{b})$ , it is proved that the number of covering events of sensor node $s_{b}$ is more than the number of covering events of sensor node $s_{i}$ , and the location of the sensor node $s_{b}$ is not crowded, then move sensor node $s_{i}$ to the location of sensor node $s_{b}$ at a step, the following operation is performed

$\vec{{L'}_{i}} = \vec{L_{i}} + rand (l_{step}) \frac{\vec{L_{b}} - \vec{L_{i}}}{| \vec{L_{b}} - \vec{L_{i}} |}$ (8)

If sensor node $s_{i}$ moves to $\vec{{L'}_{i}}$ , making the $N_{sensor} (s_{i})$ increased, the rear-end collision operation was successful; otherwise, the rear-end collision operation failed.

Step 1.3 $N_{neigh} (s_{i}) > 1$ , then perform clustering operation: determine the location of the neighbor node center $s_{c}$ by equation (9)

$\vec{L_{c}} = \frac{\sum_{s_{j} \in Λ (s_{i})} \vec{L_{j}}}{N_{neigh} (s_{i})}$ (9)

Respectively, the values of $N_{sensor} (s_{c})$ and $N_{near} (s_{c})$ of the center position $s_{c}$ are calculated by equations (10) and (11)

$N_{sensor} (s_{c}) = \frac{\sum_{s_{j} \in Λ (s_{i})} N_{sensor} (s_{j})}{N_{neigh} (s_{i})}$ (10)

$N_{near} (s_{c}) = \frac{\sum_{s_{j} \in Λ (s_{i})} N_{near} (s_{j})}{N_{neigh} (s_{i})}$ (11)

If $N_{sensor} (s_{c}) > N_{sensor} (s_{i})$ and $N_{near} (s_{c}) < δ (s_{c})$ , it proves the number of covering events of sensor node $s_{c}$ is more than the number of covering events of sensor node $s_{i}$ , and the location of the sensor node $s_{c}$ is not crowded. Then, move sensor node $s_{i}$ to the location of sensor node $s_{c}$ at a step. The following operation is performed

$\vec{{L'}_{i}} = \vec{L_{i}} + rand (l_{step}) \frac{\vec{L_{c}} - \vec{L_{i}}}{| \vec{L_{c}} - \vec{L_{i}} |}$ (12)

If the sensor node $s_{i}$ moves to $\vec{{L'}_{i}}$ , making the $N_{sensor} (s_{i})$ increased, the clustering operation was successful; otherwise, the clustering operation failed.

Step 2 $N_{sensor} (s_{i}) = 0$ , the sensor node $s_{i}$ moves to the center position of the event covered. Then, perform Steps 1.

Each sensor node in the target area performs the steps mentioned above. After a total of 100 iterations, the process of UASNs coverage optimization is over.

In this process, each node can control itself, in accordance with the rules of the algorithm to get the global optimal value. It requires the step size of each time node to randomly move a size not exceeding its own perceptual range, so as to ensure that any event during the process of foraging operation is not skipped, and when rear-end collision or clustering occurs, there will not be too crowded among sensor nodes.

Connectivity optimization for UASNs based on edge nodes

After coverage optimization for UASNs inspired by fish swarm is completed, though the network coverage has been optimized, there are disconnected positions and key nodes existing in the UASNs. Repair the disconnected position and eliminate the key nodes by edge nodes, so that the connectivity of UASNs can be optimized.

Selection of the repair node

The repair node is selected from edge nodes, which is used to repair the disconnected position and remove the key nodes in the UASNs. The process of the selection of repair node is shown in Figure 5.

1. Initiating the request of repair operation, that is, Request messages

Figure 5.

Schematic diagram of the process of repair node selection.

Broadcast the $Request (s_{i}, L_{i}, hops)$ message by the key node, including key node’s ID, location, hops of search, and other information, where hops is the counter for counting the number of hops and the initial value of hops is set by $s_{i}$ , the $Request (s_{i}, L_{i}, hops)$ message is sent each time, and the hops minus 1, until the hops becomes 0, and the $Request (s_{i}, L_{i}, hops)$ message is no longer being delivered.

2. The edge node processes the Request message

Edge node $s_{j}$ within the number of hops receives the Request message, the distance between $s_{i}$ and $s_{j}$ is calculated according to the position information $L_{i}$ of $s_{i}$ and its own position information $L_{j}$ , and then calculate the $C' = k \cdot d (s_{i}, s_{j}) \cdot | \vec{C_{i}} |$ , where $| \vec{C_{i}} |$ represents the energy consumption moving per unit distance along the direction of $s_{j}$ to $s_{i}$ , $d (s_{i}, s_{j}) | \vec{C_{i}} |$ represents estimation of energy consumption of moving, and k represents the adjustment coefficient, used to control the remaining energy while edge node $s_{j}$ is moving to $s_{i}$ . $s_{j}$ is compared with $C'$ regarding the current value of their own energy. If $C'$ is greater than the current own energy, it is indicated that $s_{j}$ does not have enough energy to move to $s_{i}$ , or even if it can move to the C, it cannot continue to work properly, then do not save the Request message and forward it; if $C'$ is less than the current own energy, then check the list of messages. If the list has received the same $Request (s_{i}, L_{i}, hops)$ message before, then forward it. Otherwise, it shall be added to the list and forwarded, until hops of $Request (s_{i}, L_{i}, hops)$ message was reduced to 0 when the message would be discarded.

Edge nodes need to establish the queue of Request messages and set timer of Request message. The queue of the Request messages is constructed with each key node further away from $s_{j}$ . The shorter the distance that $s_{j}$ moves to each key node, the lesser the time that edge node spends to arrive at the key node, and then the less the time spent on local topology restoration. We use the following equation (13) to calculate the time that is required to complete the local topology restoration by the edge node $s_{j}$

$T_{repair} = T_{comput} D + \frac{\sum_{i = 1}^{D} l_{i}}{v}$ (13)

where D represents the total number of steps that the edge node $s_{j}$ moves; $T_{comput}$ represents the time for the edge node $s_{j}$ to calculate the cost of moving direction each time; v represents the moving speed of the edge node $s_{j}$ ; $l_{i}$ represents the ith step size of the edge node $s_{j}$ ; $\sum_{i = 1}^{D} l_{i}$ represents the total movement distance of the edge node $s_{j}$ .

While the timer of the Request message expires, the edge node $s_{j}$ selects a Request message from the queue of Request messages and replies the $Response (s_{i}, s_{j}, L_{j})$ message to its sponsors $s_{i}$ , including the key node ID, the edge node ID, and location information of the edge node.

3. The key node processes the Response message

The key node takes into account energy, movement distance, and utilization of coverage of the edge node. In this way, it can construct the queue of Response messages and selects a number of edge nodes from the queue to send the Take message to itself.

The key node sets the timer of the Response message after the Request message is sent. If the key node has not received any Response message that is returned by the edge node during a certain period of time measured by the timer, then the key node expands the search range, increases the initial value of hops, and broadcasts the Request message again.

4. The edge node processes the Take message

The timer of the Take message is set at the same time as the edge node sends the Response message. If the edge node has received the Take message during a certain period measured by the timer, the edge node is selected as the node for repairing the key node that has sent the Take message and started the process of moving; when the timer expires and the edge node does not receive the Take message, the next key node from the queue of the Request messages will be selected to send the Response message and the timer of the Take message will be started.

The process of the selection of the repair node for repairing the disconnected position is similar to the above process, but the request of repair (namely the Request message) is initiated by the AUVs that discover the disconnected position and information interaction between the AUVs and edge nodes.

The movement of the repair node oriented by virtual force

In the following description, we define the disconnected position of UASNs and the position of the key node as the target position. When the repair node is selected, the repair node begins to move to the target position. We assume that the nodes will be affected by four kinds of virtual force in the process of moving. They are the gravitation of the target position, repulsion among neighboring nodes, repulsion of obstacles, and random disturbance force.

The target position will generate gravitation based on Hooke’s law for the repair node to attract the repair node to move it; the repulsion will be generated among single-hop neighboring nodes based on Coulomb’s law; in order to avoid a collision during the movement, the obstacle on the movement route of the repair node will generate repulsion based on Coulomb’s law; random disturbance force is used to adjust the operator for avoiding the repair node to fall into motion trap, and it is in the condition of long-term stop or reciprocating motion. Assuming that o represents the target position, $s_{j}$ denotes the repair node, and each virtual force is expressed as

$\vec{F_{g} (o, s_{j})} = - k_{g} \vec{d (o, s_{j})}$ (14)

$\vec{F_{r} (s_{i}, s_{j})} = {\begin{matrix} \frac{k_{r} m_{i} m_{j}}{{\vec{d (s_{i}, s_{j})}}^{2}}, 0 < d (s_{i}, s_{j}) < r^{c} \\ 0, d (s_{i}, s_{j}) \geq r^{c} \end{matrix}$ (15)

$\vec{F_{o} (s_{i}, s_{j})} = {\begin{matrix} \frac{k_{o} m_{i} m_{j}}{{\vec{d (s_{i}, s_{j})}}^{2}}, 0 < d (s_{i}, s_{j}) \leq r^{c} \\ 0, d (s_{i}, s_{j}) > r^{c} \end{matrix}$ (16)

$\vec{F_{w} (s_{j})} = rand (0, Q] rand (0, 360]$ (17)

where $k_{g}$ , $k_{r}$ , and $k_{o}$ represent the coefficient of proportional; $m_{i}$ and $m_{j}$ represent the quality of the sensor node and $m_{i} = m_{j}$ ; $\vec{d (o, s_{j})}$ represents Euclidean distance between the repair node and the target position, $\vec{d (s_{i}, s_{j})}$ represents Euclidean distance between the two sensor nodes; Q represents disturbance amplitude of random disturbance force.

The resultant force acted by the repair node is expressed by equation (18). When the resultant force is 0 or in the opposite direction of the last resultant force, the node does not move. If it does not move $k_{w}$ times in a row, then a random disturbance occurs, and the step size and direction of the movement are generated randomly

$\vec{F} = {\begin{matrix} \sum_{s_{j} \in Λ (s_{i})} \vec{F_{r} (s_{i}, s_{j})} + \sum_{s_{j} \in Δ (s_{i})} \vec{F_{o} (s_{i}, s_{j})} + \vec{F_{a} (o, s_{j})} \\ \vec{F_{w} (s_{j})}, k_{w} = 3 \end{matrix}$ (18)

The movement of the repair node is represented as follows

$P (t + Δ t) = l \frac{\vec{F}}{| \vec{F} |} + P (t)$ (19)

where $P (t)$ represents the position coordinate of the repair node at time t, $P (t + Δ t)$ denotes the position coordinate of the repair node after $Δ t$ , $\vec{F} / | \vec{F} |$ represents the unit vector of the moving direction of the repair node, and l represents step size of movement. The maximum unit step size of the movement oriented by virtual force is set to $l_{\max}$ , then absolutely $l \leq l_{\max}$ . The repair node is in constant motion oriented by virtual force until it gets into the communication range of the target position and the mission of local topology restoration is completed.

The selection of several important parameters such as $k_{g}$ , $k_{r}$ , $k_{o}$ , and $l_{\max}$ is described as follows: $k_{g}$ represents the gravitational coefficient of the target position. In order to ensure that the repair node, in a relatively short time, could move into the communication range of the target location, $k_{g}$ should be set to the maximum of the proportional coefficient (i.e. $k_{g}$ , $k_{r}$ , and $k_{o}$ ); $k_{r}$ and $k_{o}$ , respectively, indicate the repulsion among the single-hop neighboring nodes and the repulsion generated by the obstacle. The obstacle is still the sensor node. In order to make the repair node successfully avoiding obstacles, it is set as $k_{o} > k_{r}$ . The setting of the maximum step size of the repair node is similar to that of the maximum moving step size of the artificial fish. If the setting is too small, it will increase the number of mobile, which leads to increased energy consumption; if the setting is too large, it will cause the node to move back and forth in the process of moving; because it is the movement of the sensor nodes and in order to facilitate unified throughout the optimization, we set $l_{\max} = l_{step}$ .

The method for supplying the coverage

Although there is no impact on the connectivity of the network topology, it may lead to individual events unable to be covered and affect the coverage of UASNs. In order to fill up the gaps that may be left after the repair node is removed and ensure the network topology unchanged, the position of original neighbor nodes of the repair node can be fine adjusted by virtual force. In this process, the original neighbor nodes of the repair node are affected by two kinds of virtual force: (1) the gravitation of the original location of the repair node based on Hooke’s law; (2) the force among the neighbor nodes based on Coulomb’s law (whether it is the gravitation or the repulsion depends on the distance among the nodes). Two kinds of virtual force are expressed as equations (20) and (21). If the conditions of $d_{opt} = 1.78 r^{s}$ and $r^{c} > 1.78 r^{s}$ are satisfied, the distance among the sensor nodes is $d_{opt}$ , which can ensure the connectivity and achieve the optimal coverage¹¹

$\vec{F_{b} (o', s_{i})} = - k_{b} \vec{d (o', s_{i})}$ (20)

$\vec{F_{c} (s_{i}, s_{j})} = {\begin{matrix} \frac{k_{c} m_{i} m_{j}}{{\vec{d (s_{i}, s_{j})}}^{2}}, 0 < d (s_{i}, s_{j}) \leq d_{opt} \\ - \frac{k_{c} m_{i} m_{j}}{{\vec{d (s_{i}, s_{j})}}^{2}}, d_{opt} < d (s_{i}, s_{j}) \end{matrix}$ (21)

where $k_{b}$ and $k_{c}$ are the coefficient of proportionality. In order to move the original neighborhood node of the repair node to the position of the original repair node, we should set $k_{b} > k_{c}$ . Because the range of the movement of the node in the process is smaller, $k_{b}$ and $k_{c}$ are set to smaller order of magnitude.

The resultant force acted by the original neighbor nodes of the repair node is expressed as follows

$\vec{F_{i}} = \vec{F_{b} (o', s_{i})} + \sum_{s_{j} \in Λ (s_{i})} \vec{F_{c} (s_{i}, s_{j})}$ (22)

The position of nodes in the original neighborhood of the repair node is adjusted under the action of the resultant force, which fills up the gaps caused by removing the repair node to prevent the coverage of UASNs from being lowered.

The TO-DA algorithm

The process of repair

The reasons why we present the TO-DA algorithm for optimizing the topology of the UASNs are as follows:

The underwater acoustic sensor has limited energy and the frequent topology evolution for maintaining the connectivity of the network topology leads to the energy of sensor nodes greatly reduced in complex ocean environment;

The shadow zone still exists in the process of mission execution, and the communication signal attenuation among the underwater acoustic sensors or the signal-to-noise ratio (SNR) is large, which cannot maintain stable/effective communication. This is because the acoustic wave cannot penetrate the shadow zone with much signal distortion.

The number of AUVs is limited because of its expensive cost contrast to the sensor node. Replacing the key nodes with AUVs leads to the weakening of the ability about global monitoring, data acquisition, and so on. Sometimes the implementation of topology reconfiguration is caused by the energy deficiency of individual underwater acoustic sensors or the poor communication caused by suspended matter in sea water.

In the view of the above, we present the TO-DA algorithm. It is the improvement of the TO-A algorithm. Each AUV carries a underwater acoustic sensor. They exchange the information and fix position by a wire. The wire can penetrate shadow zone without much signal distortion. The AUV can clean or charge the sensor that is connected to the AUV for avoiding the frequent topology evolution. When the sensor nodes in the monitoring area are monitored by Double-AUVs, the information about the failure node is also recorded for statistics. If the disconnected node is found, then $b_{i}$ that the sensor attached to the Double-AUVs moves to the $Λ (S_{i})$ for repairing. Then, set the state of $b_{i}$ as busy.

On this basis, if Double-AUVs find the disconnected position of the UASNs, proceed as follows:

Case 1: The disconnected node does not belong to set B.

Step 1 According to Hypothesis 1.The node $b_{i}$ knows its own location information and the location information of the nodes in the neighborhood. Then, the whole network is divided into smaller network topology, and the failure node $s_{i}$ is judged to belong to the ith part of topology of the network.

Step 2 In the ith part of topology of the network, according to the method mentioned above, the method of classification is used to determine the classification of the node $b_{i}$ (the key node or the edge node). Then, Double-AUVs find the disconnected position by the method is mentioned in section “Network model and problem description.”

Step 2.1 If $b_{i}$ is the edge node

Double-AUV $A_{i}$ initiates the request of requirement which means that $A_{i}$ sends the Request message with information about disconnected position to $b_{i}$ . After $b_{i}$ received the Request message, $b_{i}$ returns the Response message that is used to answer the request of repair. The time of repair is calculated by equation (23)

$T_{repair} = T_{comput} \cdot D + \frac{\sum_{i = 1}^{D} l_{i}}{v}$ (23)

where D represents the needed moving steps of the node $b_{i}$ , $T_{comput}$ represents the time for the node $b_{i}$ to calculate the cost of moving direction each time, v represents the moving speed of the node $b_{i}$ , $l_{i}$ represents the ith step size of the node $b_{i}$ , and $\sum_{i = 1}^{D} l_{i}$ represents the total movement distance of the node $b_{i}$ .

Step 2.2 If $b_{i}$ is the key node

In the ith part of topology of the network, local topology reconstruction is carried out relatively to the whole topology network. After $b_{i}$ turns into the edge node, jump to Step 2.1. The process of the local topology reconstruction is as follows or shown in Figure 6:

Figure 6.

The process of selecting node for reconstruction.

The key node $b_{i}$ sends Find message

In the ith part of network topology of the key node $b_{i}$ , $b_{i}$ sends the $Find (b_{i}, L_{i}, hops, Links)$ message to all nodes in the topology network i in addition to itself. The $Find (b_{i}, L_{i}, hops, Links)$ message includes key node’s ID, location, hops of search, and other information, where hops is the counter for counting the number of hops, and the initial value of hops is set by $b_{i}$ . Every time the Find message passes by, the hops minus 1. The Find message is no longer being passed after hops becomes 0.

The edge node $s_{j}$ processes the Find message

After the edge node $s_{j}$ in the i part of topology of the network received the Find message $s_{j}$ , calculate the distance $d (b_{i}, s_{j})$ between the $b_{i}$ and the $s_{j}$ according to the position information $L_{i}$ about $b_{i}$ and the position information $L_{j}$ about itself and then calculate the total energy $C' = k \cdot d (b_{i}, s_{j}) \cdot | C_{i} |$ . The edge node $s_{j}$ is compared with $C'$ regarding the remaining energy of itself. If $C'$ is more than the remaining energy of $s_{j}$ , it is indicated the edge node $s_{j}$ does not have enough energy for moving to the position of $b_{i}$ or even if the edge node $s_{j}$ can move to the position of $b_{i}$ , it cannot do its work, so $s_{j}$ does not save the Find message and forward it. If $C'$ is less than the remaining energy of $s_{j}$ , then check the list of messages. If the list has received the same Find message, then forward it. Otherwise, the edge node $s_{j}$ sends the $Answer (s_{j}, L_{j}, sLink)$ message to $b_{i}$ , including ID number of $s_{j}$ , the position of $s_{j}$ , the nodes number connected to the edge node $s_{j}$ , and change node’s own information by the information in Links.

The key node $b_{i}$ processes the Answer message

After the key node $b_{i}$ received the Answer message that returned by $s_{j}$ , then send the $Restructure (b_{i}, new_key, hops)$ . message to all nodes in the topology network i in addition to itself, the message includes the ID number of the $b_{i}$ , the new key node number, and the hops that are used for traversing. The value of hops is set by $b_{i}$ . Every time the Restructure message passes by, the hops minus 1. If $hops = 0$ , the Restructure message is no longer being passed. If the node in the topology network i has received the Restructure message, then the $b_{i}$ from the Restructure message shall be compared with the order number of self-connected nodes. If they are consistent, the node that has been compared changes the order number of nodes connected to itself by the information of $new_key$ (i.e. the node changes the self-connected node). Meanwhile, reply the $Run (num)$ message to $b_{i}$ , including its own number that represents the node, which has changed the order number of self-connected nodes. If they are not consistent, it indicates the node did not connect with the key node. Then, forward the Restructure message.

The key node $b_{i}$ processes the Run message

When the key node $b_{i}$ has received Run message, the key node $b_{i}$ compares the num with the order number of self-connected nodes. If all nodes connected with the key node $b_{i}$ replied the Run message, the key node $b_{i}$ changes the order number of self-connected nodes by sLink in the Answer message (i.e. the key node changes the self-connected node) and sends the Move message to $s_{j}$ . Meanwhile, the key node $b_{i}$ moves to the position of $s_{j}$ according to $L_{j}$ in the Answer message.

The edge node $s_{j}$ processes the Move message

After the edge node $s_{j}$ received the Move message, $s_{j}$ moves to the position of the key node $b_{i}$ according to $L_{i}$ in the Find message that the edge node $s_{j}$ has received. Meanwhile, $b_{i}$ is moving to the position of the node $s_{i}$ that needs to be repaired.

Step 3 Use the method mentioned in section “The method for supplying the coverage” to avoid the coverage loss.

Case 2: The disconnected node belongs to set B.

The Double-AUVs can directly repair the connectivity of UASNs.

Step 1 The Double-AUVs just send the information to sensor node $b_{i}$ attached to the Double-AUVs and ask the sensor node for returning. Then, clean the sensor node $b_{i}$ or charge the sensor node $b_{i}$ , because the location and path of the sensor have been recorded in the Double-AUVs when the sensor node $b_{i}$ has been dispatched.

Step 2 When the sensor node $b_{i}$ has been cleaned or charged, the Double-AUVs send $b_{i}$ back to the original location according to the information that has been recorded in the AUV node $A_{i}$ .

Step 3 When the sensor node $b_{i}$ returns to the original position and communicates with the neighbor nodes, $b_{i}$ sends a confirmation message to the $A_{i}$ through the wire.

The process of eliminating key nodes

Frequent repairs will decrease the lifetime of the entire network, and lead to gaps in information collection, and so on. In order to improve the performance of UASNs, it is required to first eliminate key nodes after the repair is finished. By Definition 5, after the edge of the node is removed, neither the communication branch is increased, nor new node key nodes is formed. After the optimal node is selected, the information about other sensor nodes in the connected branch can be known by Hypothesis 1. Then, select the nearest edge node from the key node in random and reconstruct the neighborhood topology of the key node through the triangular mechanism.

Eliminating the key node requires three nodes at least due to the stability of the triangular structure and the limited energy of the underwater acoustic sensor. Then, we introduce the concept of triangle mechanism. At least select the nodes in the neighborhood of the key node that can be connected with the key node for establishing a connection (see $e_{5, 10} (s_{5}, s_{10})$ and $e_{7, 10} (s_{7}, s_{10})$ in Figure 7(b)) with the key node according to the cosine theorem and the sine theorem. After the key node was eliminated, the neighborhood topology can be re-established by the method for determining theneighborhood topology mentioned above (see the dotted line $e_{6, 10} (s_{6}, s_{10})$ and $e_{9, 10} (s_{9}, s_{10})$ in Figure 7(b)). The above process is shown in Figure 7.

Figure 7.

The process of eliminating the key nodes: (a) the local topology and (b) the local topology after the key node was eliminated.

After the process mentioned above is finished, the nodes $s_{6}$ , $s_{7}$ , and $s_{10}$ are not the key nodes. Although removing the edge node will cause the loss of coverage, the optimization of invulnerability of the network topology performance is greater than the loss of coverage.

Experimental study

In this section, we conduct simulation experiments repeatedly to demonstrate the effectiveness and efficiency of the proposed algorithm by the Monte Carlo method. The experimental environment is as follows: there are 50 events required to be monitored, which are unevenly distributed in the $400 m \times 400 m \times 400 m$ underwater monitoring area. The UASNs composed of 20 sensors in use for monitoring the events and there are five AUVs added to the UASNs. The locations of sensors and target events influenced by the ocean current¹² model have changed. Table 1 shows the experimental parameters. The coefficient of proportionality $k_{g}$ , $k_{r}$ , $k_{o}$ , $k_{b}$ , and $k_{c}$ are set as $10^{6}$ , $10^{2}$ , $10^{4}$ , $10^{4}$ , and $10^{2}$ , respectively, and unit energy consumption in each direction $\vec{C_{x}}$ , $\vec{C_{- x}}$ , $\vec{C_{v}}$ , $\vec{C_{- v}}$ , $\vec{C_{z}}$ , and $\vec{C_{- z}}$ are set as $\vec{C_{x}} = \vec{C_{- y}} = 5 \times 10^{- 2}$ J, $\vec{C_{- x}} = \vec{C_{y}} = 2 \times 10^{- 2}$ J, $\vec{C_{z}} = 8 \times 10^{- 2}$ J, and $\vec{C_{- z}} = 1 \times 10^{- 2}$ J, respectively.

Table 1.

The experimental parameters.

Symbol	Description	Value
$r^{s}$	Sensing radius of the sensor	40 m
$r^{c}$	Communication radius of the sensor	60 m
$V^{t}$	Propagation velocity of sound underwater	1500 m/s
v	Speed of sensor	3 m/s
e	The initial energy of sensor	30 J
Q	Disturbance amplitude	18 m
lstep	The largest moving step size of artificial fish	15 m
$l_{\max}$	The largest moving step size of repair node	15 m
Interval	The timer of optimization period	60 min
Interval	The timer of optimization period	60 min

The TO-A algorithm analysis

Compared with the PSO algorithm mentioned by Bhavya and Nithya¹³, we carry on three comparison experiments.

Experiment 1

A comparison experiment about coverage optimization. Figure 8 shows the change curve of the degree of coverage with time gradually after the optimization algorithm is carried out. Solid line represents the effect of TO-A algorithm. Dashed line represents the effect of PSO algorithm. It can be seen that the final value of the coverage after PSO algorithm is less than that of the TO-A algorithm in this article, because the TO-A algorithm inspired by fish swarm in this article is capable of global search so that the global extremum can be realized. But both of them can achieve nearly optimal in the coverage and guarantee the coverage over 95%. We also find PSO algorithm can achieve the optimal in the coverage earlier, because PSO algorithm obtains the value of local optimal quickly. So, the curve can be earlier convergent.

Figure 8.

The change of coverage in the optimization process.

Experiment 2

Compare the number of the key node after coverage optimization. The experimental scenario is set as follows: the number of events increased from 50 to 70 and the number of sensors distributed in the UASNs is 20, 25, and 30, respectively. The TO-A algorithm and PSO algorithm are carried out in these three scenarios. We have statistics on experimental times of key nodes exist in the 100th round experiment (see Figure 9). It can be seen that with the increase in the number of events, there is a significant reduction in the number of experiments of the existence of key nodes, because during the execution of the two algorithms, sensors always move toward the place where the density of events is high. The events distributed are more even so that sensors deployed are more even after the events in the sparse area are increased. But the PSO algorithm is easy to fall into local optimum so that the overall result is worse than the TO-A algorithm (inflection point as shown in Figure 9).

Figure 9.

The number of experiments that exists the key nodes.

In addition, as shown in Figure 9, when the sensor node is set to 25, the overall effect after the implementation of the algorithm is optimal. The number of sensor nodes is less difficult to uniformly cover the events when the number of events is constant. The number of sensor nodes is increased too much and events are distributed unevenly, leading to sensor nodes deployed unevenly and the key nodes are easily generated.

Experiment 3

A comparison experiment about recovery of the connectivity. First, we verify the optimization of the connectivity by executing the TO-A algorithm proposed in this article. We set the number of events to 50 and the number of sensor nodes to 20. The connectivity of network is repaired by the edge nodes (this method is mentioned in section “Connectivity optimization for UASNs based on edge nodes”). The connectivity of UASNs was recovered in 100 repeated experiments. Figure 10 shows the connectivity recovery curves of 4 experiments were randomly selected from the 100 repeated experiments.

Figure 10.

The curve of recovering connectivity that is randomly selected from 100 experiments.

Figure 11 shows the change curve of the experimental results through performing two kinds of algorithms during 500 s.

Figure 11.

The change of connectivity through the algorithm: (a) the TO-A algorithm and (b) the PSO algorithm.

As said by Bhavya and Nithya,¹³ eight self-moving nodes (the AUVs) were deployed in the above experimental background. When the network is not connected, the self-moving node is used to repair. Figure 11(a) shows clearly, in addition to initializing repair operation that takes nearly 40 s, and others only take 10 s. It is indicated that the PSO algorithm achieves the connectivity of UASNs quickly. But it is easy to generate the disconnected network because in the work by Bhavya and Nithya,¹³ the key nodes were not eliminated, which leads to weaken the invulnerability of UASNs. Even the deviation of the location of AUVs nodes that is influenced by ocean currents will occur and leads to the disconnected UASNs and the UASNs need to be repaired again (as it has been shown time in Figure 8(a) around 240 s). Although the TO-A algorithm proposed in this article spends a longer time to initialize the repair operation (the average cost is about 55 s in 100 repeated experiments), the TO-A algorithm will enhance the invulnerability of UASNs through eliminating the key nodes and it is not easy to disconnect the network under the influence of ocean currents and all kinds of biology. Figure 11(b) shows the connectivity of UASNs which was repaired by the TO-A algorithm within 500 s that the experiment starts. In the process of the experiment in 500 s, after the PSO algorithm mentioned by Bhavya and Nithya¹³ is carried out, we can calculate the connectivity rate of UASNs is 372/500=74% and the connectivity rate of UASNs after the TO-A algorithm proposed in this article is carried out is 445/500=89%. We can also find a phenomenon that the longer experiment time is, the advantages of the TO-A algorithm more obvious is, so the TO-A algorithm has better scalability.

The TO-DA algorithm analysis

Compare with the PSO algorithm mentioned by Bhavya and Nithya¹³ and the fish swarm optimization algorithm mentioned by Pandey and Pompili¹⁴ (called Fish Swarm optimization algorithm [FSO]).

Experiment 1: a comparative experiment about repairing the connectivity

When the failure node occurs in the topology of the network, the number of connected nodes decreases sharply. Figure 12 shows the change of the number of connected nodes with the time after the implementation of three algorithms, which are TO-DA algorithm, the PSO algorithm, and the FSP algorithm, respectively. It can be seen the curve of PSO algorithm is relatively stable, because the PSO algorithm is the local optimum; the curve of FSP algorithm is fluctuated, because large number of sensors were selected to move when the FSP algorithm is executed. After performing the above two algorithms, the number of connected sensor nodes is less than the result from the TO-DA algorithm proposed in section ” The TO-DA algorithm.” We can also see that the start points of three curves in Figure 12 are different, because the method of deployed node is different in three algorithms. During the execution process of TO-DA algorithm, there is a larger changein the number of connected nodes, because the process of repairing node happens always in the implementation of the operation of eliminating the key nodes. In the process of eliminating the key nodes, on one hand, it will speed up the covering of all nodes in UASNs; on the other hand, there will be the inevitable decline in performance of the connectivity of UASNs when the edge node in the mobile, but the time of declining in performance is short. So, we just need a very short period of time to achieve the overall optimization of the repair.

Figure 12.

The change of connectivity when disconnected location is restored by the algorithm.

Experiment 2: the analysis of coverage and performance of survivability

Figure 13 is the change of the survivability and the coverage after the algorithm is executed. The left ordinate, solid blue line (representing PSO algorithm (1) in Figure 13) and blue circles line (representing TO-DA algorithm (1) in Figure 13) represent a change of the coverage in PSO optimization algorithm and the TO-DA algorithm over time, respectively; the right ordinate, solid green line (representing PSO algorithm (2) in Figure 13) and green circles line (representing TO-DA algorithm (2) in Figure 13) represent a change of the survivability in PSO optimization algorithm and the TO-DA algorithm over time, respectively. It can be seen in Figure 13 that though the coverage of the UASNs after the TO-DA algorithm is carried out is less than the effect by implementation of the PSO algorithm, the survivability after the TO-DA algorithm is executed is far beyond the effect after the implementation of the PSO algorithm. Through statistical analysis, although at the expense of coverage of approximately 8.5% in the optimization process, survivability performance is improved by about 50%. Because the process of TO-DA algorithm execution is always accompanied with the operation of eliminating the key nodes, which makes the topology change, the coverage is reduced, but the key nodes are eliminated, and the network lifetime is prolonged. This method is more suitable for long-time underwater missions.

Figure 13.

The comparison of coverage and survivability.

Experiment 3: the performance analysis of the network after the end of the process of optimization

Figure 14 shows the connectivity and the overall energy consumption of the UASNs during the process of the optimization. In the optimization phase, the line slope of the energy consumption is larger because there are lots of moving nodes. In the whole UASNs network, the energy consumption of the nodes gradually tends to be stable and the growth is stopped at 110 s. This situation indicates the process of the implementation of FSP algorithm is finished. As we can see from Figure 14, the connectivity curve shows an upward trend with time, the curve reaches the peak near the 60 s. There is a clear advantage compared with the FSP algorithm. It reaches the peak at about 43 s, then the curve about TO-DA algorithm drops to 0.9 in a short period of time, then backs to the peak near 85 s and maintain stably, because the implementation of the TO-DA algorithm is finished near the 60 s, and the connectivity of UASNs has been optimized, but during the following processes of eliminating the key nodes, there is inevitable decline in local connectivity. So, the overall connectivity of the network decreased slightly due to the edge nodes leaving its original location; however, the connectivity of UASNs is restored immediately with the completion of eliminating the key nodes. At the same time, as it is seen from Figure 14, when the time is at 120 s and curve of the energy consumption of the topology of UASNs does not leveled off, there is still a small slope. It indicates the energy consumption continues to increase, and the repair process of connectivity of UASNs is still in progress.

Figure 14.

The comparison of connectivity and energy consumption.

The above three experiments about TO-DA algorithm are not difficult to be found in the UASNs. As the time passed, the automatic repairing and restructuring of the sensor nodes makes an increase in the density of the sensor nodes. This enables the connectivity among the nodes turn better and the survivability of local topology of network has been improved, but the coverage occurs redundant phenomenon in a certain extent.

Conclusion

In this article, we propose a topology optimization scheme based on reorganization, namely, TO-A algorithm that maintains connectivity and coverage, and a topology optimization mechanism based on Double-AUVs, namely, TO-DA algorithm that prolongs the life cycle and connectivity of UASNs. To be more specific, the TO-A algorithm’s purpose is to address the problem about topology affected by ocean currents and other environmental factors that leads to the dynamic evolution of network and generates gradual reduction in the performance of UASNs; the TO-A algorithm not only adjusts the location of sensor nodes by simulating the fish swarm behavior so as to optimize the coverage, but also uses the edge nodes to repair the disconnected position in the UASNs so as to eliminate the key nodes and optimize the connectivity. Although the TO-A algorithm presented above, compared with other algorithms can effectively improve the connectivity of the network and optimize the coverage with lower energy consumption, the TO-DA algorithm is a further research for executing the underwater long-term missions. We redefine the Double-AUVs and propose the TO-DA algorithm. The TO-DA algorithm not only repairs the failed node by Double-AUVs, but also takes into account the frequent topology repair, which leads to a reduction in the lifetime of the network. So, after the repair is completed, the algorithm begins to carry out the operation that eliminates the key nodes, which will improve regeneration and survivability of UASNs in uncertain ocean environment.

The simulation results, respectively, demonstrate the performance of UASNs after the algorithms are executed; all the algorithms can restore the connectivity of UASNs, but the TO-A algorithm is more efficient in coverage, and the TO-DA algorithm is more efficient in survivability. The TO-A algorithm can guarantee the network coverage is maintained at about 97%, connectivity rate above 89% with lower energy consumption and the TO-DA algorithm can improve survivability of the network effectively above 50% with lose of 8.5% of the network coverage.

Research results have certain contributions to the research of topology of UASNs and have extensive application value.

In the near future, on one hand, we plan to make reasonable assumptions about the AUVs own energy, control threshold value of AUVs’ energy, and further ensure the efficiency of the network, because the energy of AUVs is infinite in the hypothesis of this article; on the other hand, the uncertainty factors that affect the performance of UASNs also include the dynamic nature of the boundary of different temperature water layers, the mesoscale vortex, and other factors such as human factor; so, we will consider these factors in the follow-up study.

Footnotes

Academic Editor: Hongyi Wu

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research,authorship,and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research,authorship,and/or publication of this article: This work was supported by the National Natural Science Foundation of China under Grant Nos 61301159 and 61303267,Natural Science Foundation of Jiangsu Province under Grant Nos BK20150721 and BK20161469,China Postdoctoral Science Foundation under Grant Nos 2015M582786 and 2016T91017,Engineering Research Center of Jiangsu Province under Grant No. BM2014391,and Primary Research & Development Plan of Jiangsu Province under Grant No. BE2015728.

References

Erol-Kantarci

Mouftah

Oktug

A survey of architectures and localization techniques for underwater acoustic sensor networks. IEEE Commun Surv Tutor 2011; 13(3): 487–502.

Han

Optimal sensor node distribution based on the new quantum genetic algorithm. J Sens Actuator 2008; 21(7): 1259–1263.

Aziz

Sekercioglu

Fitzpatrick

. A survey on distributed topology control techniques for extending the lifetime of battery powered wireless sensor networks. IEEE Commun Surv Tutor 2013; 15(1): 121–144.

Wang

Parallel particle swarm optimization based mobile sensor node deployment in wireless sensor networks. J Comput 2007; 30(4): 563–568.

Zhou

A multi-object optimization routing algorithm with constraint for wireless sensor networks. J Appl Sci-Electron Inf Eng 2008; 26(3): 239–243.

Jafri

Ahmed

Javaid

. AMCTD: adaptive mobility of courier nodes in threshold-optimized DBR protocol for underwater wireless sensor networks. In: Proceedings of the 2013 eighth international conference on broadband, wireless computing, communication and applications (BWCCA), Compiegne, 28–30 October 2013, pp.93–99. IEEE.

Xia

Wang

Zheng

. Fish swarm inspired underwater sensor deployment. Acta Autom Sin 2012; 38(2): 295–302.

Manjula

Sunilkumar

SM.

Coverage optimization based sensor deployment by using PSO for anti-submarine detection in UWASNs. Ocean Electron (SYMPOL) 2013; 2013: 15–22.

Nguyen

Cayirci

Yang

. A shadow zone aware routing protocol for acoustic underwater sensor networks. IEEE Commun Lett 2009; 13: 366–368.

10.

Heidemann

Stojanovic

Zorzi

Underwater sensor networks: applications, advances and challenges. Philos T R Soc A 2012; 370(1958): 158–175.

11.

Luo

Guo

Dong

. LDB: localization with directional beacons for sparse 3D underwater acoustic sensor network. J Netw 2010; 5(1): 28–38.

12.

Caruso

Paparella

Vieira

LFM

. The meandering current mobility model and its impact on underwater mobile sensor networks. In: Proceedings of INFOCOM 2008, Phoenix, AZ, 13–18 April 2008, pp.221–229. Piscataway, NJ: IEEE.

13.

Bhavya

Nithya

. Efficient hierarchical route allocation for underwater sensor network. Int J Emerg Sci Eng (IJESE) 2014; 2(4): 2319.

14.

Pandey

Pompili

Region of feasibility of interference alignment in underwater sensor networks. IEEE J Oceanic Eng 2014; 39(1): 189–202.

15.

Masiero

Azad

Favaro

. DESERT underwater: an NS-Miracle-based framework to Design, Simulate, Emulate and Realize Test-beds for underwater network protocols. In: Proceedings of OCEANS, Yeosu, South Korea, 21–24 May 2012, pp.1–10. New York: IEEE.

16.

Najeeb

Khan

Qasim

. A new advanced energy efficient routing protocol for UWSNs. J Basic Appl Sci Res 2014; 4(2): 43–53.

17.

Peng

Wang

Shi

. Containment control of networked autonomous underwater vehicles with model uncertainty and ocean disturbances guided by multiple leaders. Inform Sciences 2015; 316: 163–179.

18.

Xia

Wang

Zheng

. Study on localizability judgment in underwater sensor networks based on skeleton extraction and rigidity theory. Chin J Comput 2014; 37(26): 1–14.

19.

Shen

Tan

Wang

. A novel routing protocol providing good transmission reliability in underwater sensor networks. J Internet Technol 2015; 16(1): 171–178.

20.

Coutinho

RWL

Boukerche

Vieira

LFM

. A novel void node recovery paradigm for long-term underwater sensor networks. Ad Hoc Netw 2015; 34: 144–156.

21.

Alam

Haas

Coverage and connectivity in three-dimensional networks. In: Proceedings of the 12th annual ACM international conference on mobile computing and networking (MobiCom’06), Los Angeles, CA, 24–29 September 2006.

22.

Caiti

Grythe

Hovem

. Linking acoustic communications and network performance: integration and experimentation of an underwater acoustic network. IEEE J Oceanic Eng 2013; 38(4): 758–771.

23.

Liu

Zhou

Key technologies and applications of internet of things. In: Proceedings of the fifth international conference on intelligent computation technology and automation (ICICTA), Zhangjiajie, China, 12–14 January 2012, pp.197–200. New York: IEEE.

24.

Yoon

Azad

. AURP: an AUV-aided underwater routing protocol for underwater acoustic sensor networks. Sensors 2012, 12: 1827–1845.

25.

Chen

. Fish swarm inspired Ad hoc networks node random mobility optimization model in 3D environment. Chin J Sci Instrum 2014; 35(12): 2826–2834.

26.

Sanchez

Blanc

Yuste

. Advanced acoustic wake-up system for underwater sensor networks. Commun Inf Sci Manage Eng 2012; 2(2): 1–10.

27.

Mitsche

Resta

Santi

The random waypoint mobility model with uniform node spatial distribution. Wirel Netw 2014; 20(5): 1053–1066.

28.

Xie

Wang

Construction of tree network with limited delivery latency in homogeneous wireless sensor networks. Wirel Pers Commun 2014; 78(1): 231–246.

29.

Yang

. Segmentation-based image copy-move forgery detection scheme. IEEE T Inf Foren Sec 2015; 10(3): 507–518.

30.

Sheng

Tay

. Incremental support vector learning for ordinal regression. IEEE Trans Neural Netw Learn Syst 2015; 26: 1403–1416.

31.

Xia

Wang

Sun

. A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data. IEEE T Parall Distr 2015; 27: 340–352.

32.

Pan

Zhang

Kwong

Efficient motion and disparity estimation optimization for low complexity multiview video coding. IEEE T Broadcast 2015; 61: 166–176.

33.

Xia

Wang

Sun

. Steganalysis of LSB matching using differences between nonadjacent pixels. Multimed Tools Appl 2014; 75: 1947–1962.

34.

Xia

Wang

Sun

. Steganalysis of least significant bit matching using multi-order differences. Secur Commun Netw 2014; 7(8): 1283–1291.

35.

Sun

Liu

. Achieving efficient cloud search services: multi-keyword ranked search over encrypted cloud data supporting parallel computing. IEICE T Commun 2015; E98-B(1): 190–200.

36.

Chen

Shu

Coatrieux

. Color image analysis by quaternion-type moments. J Math Imaging Vis 2015; 51(1): 124–144.

37.

Wen

Shao

Xue

. A rapid learning algorithm for vehicle classification. Inf Sci 2015; 295(1): 395–406.

38.

Zheng

Jeon

. Image segmentation by generalized hierarchical fuzzy C-means algorithm. J Intell Fuzzy Syst 2015; 28(2): 961–973.

A mechanism of topology optimization for underwater acoustic sensor networks based on autonomous underwater vehicles

Abstract

Keywords

Introduction

Network model and problem description

Network model

Relevant judgment

Calculation of neighborhood topology of nodes

Judgment for the key node and the edge node

Goal description

The TO-A algorithm

Coverage optimization for UASNs inspired by fish swarm

Connectivity optimization for UASNs based on edge nodes

Selection of the repair node

The movement of the repair node oriented by virtual force

The method for supplying the coverage

The TO-DA algorithm

The process of repair

The process of eliminating key nodes

Experimental study

The TO-A algorithm analysis

Experiment 1

Experiment 2

Experiment 3

The TO-DA algorithm analysis

Experiment 1: a comparative experiment about repairing the connectivity

Experiment 2: the analysis of coverage and performance of survivability

Experiment 3: the performance analysis of the network after the end of the process of optimization

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References