CN109803291B - Robust topology generation method based on underwater acoustic sensor network - Google Patents

Abstract

The invention mainly relates to the technical field of underwater acoustic sensor network, in order to strengthen the monitoring of key monitoring areas, and balance the energy consumption of nodes while improving the robustness of the network. The present invention, based on the robust topology generation method of the underwater acoustic sensor network, the steps are as follows: one, the topology generation stage; two, the data transmission stage: the data collected by the sensor nodes is transmitted according to the optimal path selected by the greedy algorithm, to ensure the transmission of data The energy consumption is the least. When the transmission probability of the path PR _c (i, CH _k )>ζ, it means that the data sent by the node V _i is successfully received, ζ is the threshold constant, CH _k represents the kth cluster head node, PR _c ( i, CH _k ) represents the communication probability of a path from node V _i to cluster head node CH _k ; when the remaining energy of a node in the key area is lower than 0, it means that the node is dead, and the replacement algorithm is used to ensure the key Global coverage of regions. The invention is mainly applied to the underwater acoustic sensor network.

Description

A Robust Topology Generation Method Based on Underwater Acoustic Sensor Networks

technical field

The invention mainly relates to the technical field of underwater acoustic sensor network, especially the technical field of topology control. Specifically, it relates to methods for robust topology generation based on underwater acoustic sensor networks.

Background technique

The transmission network of underwater acoustic communication is an important link in the acquisition of relevant marine data. Efficient, stable and reliable marine information transmission technology will vigorously support various marine scientific scenarios, such as environmental monitoring and ecological protection, resource exploration and development, port management and military Defense, etc., network technology plays a pivotal role in the field of underwater acoustic communication. Among them, network topology control is the basis of data transmission, providing technical support for reliable data transmission. Its main task is to make each node in the network select a suitable logical neighbor node from its physical neighbor nodes according to the given rules under the condition of satisfying the network connectivity and network coverage to form an optimized network structure. To achieve the purpose of optimizing network performance. The topology control technology can effectively balance and reduce network energy consumption, ensure the overall connectivity of the network, reduce network communication interference, and improve the overall reliability of the network, providing a good foundation for the application of the upper layer of the network. Therefore, designing a reasonable and reliable topology control algorithm has important scientific and practical significance for underwater wireless sensor networks.

The complex underwater geographical form, space media form and great limitations of underwater acoustic characteristics have caused underwater networks to face more severe problems and challenges than those on land. Underwater acoustic communication consumes a lot of energy, and energy supply and node replacement are difficult; the Doppler effect of underwater acoustic channels has strong time-space changes, causing frequent network interruptions; underwater sensor networks are often caused by energy exhaustion, hardware failures or Nodes fail due to damage or other reasons, which splits the originally connected network and affects the global connectivity of the network. Therefore, the topology control and optimization problems of underwater networks are far more complex than those of ground sensor networks.

The invention proposes an underwater robust topology generation strategy based on scale-free network and rigid graph theory, which balances energy consumption of nodes while improving network robustness, and designs a replacement algorithm for failed nodes to ensure global coverage of key monitoring areas.

Contents of the invention

In order to overcome the deficiencies of the existing technology, the present invention aims to propose a topology control technical solution, strengthen the monitoring of key monitoring areas, and balance the energy consumption of nodes while improving network robustness. For this reason, the technical scheme that the present invention takes is, based on the robust topology generation method of the underwater acoustic sensor network, the steps are as follows:

1. Topology Generation Phase

In the underwater acoustic sensor network, the nodes close to the cluster head take on more forwarding tasks. In the topology generation stage, the complex network theory is first used to generate the network topology, and then the rigid graph is constructed in the key areas, and finally the isolated nodes or connected subgraphs are connected to the rigid graph. , to generate the initial topology of the underwater sensor network, and the node degree of the network obeys the power law distribution;

2. Data transmission stage

The data collected by sensor nodes is transmitted according to the optimal path selected by the greedy algorithm to ensure the least energy consumption of data transmission. When the path transmission probability PR _c (i, CH _k )>ζ, it means that the data sent by node V _i is Successful reception, ζ is a threshold constant, CH _k represents the kth cluster head node, PR _c (i, CH _k ) represents the communication probability of a certain path from node V _i to cluster head node CH _k ;

Every 10 seconds, adjust the topology of the optimal rigid graph according to the remaining energy of the nodes to balance the energy consumption among nodes;

When the remaining energy of a node in the key area is lower than 0, it means that the node is dead, which affects the coverage and connectivity of the key area, and the replacement algorithm is used to ensure the global coverage of the key area.

further,

1. Edge structure model

According to the edge structure model, the connection probability of edges in the underwater sensor network is calculated:

Where P _ij represents the connection probability between node V _i and node V _j , d(i, j) represents the distance between node V _i and node V _j , P _C (i, j) represents the communication probability between node V _i and node V _j , P _S (i, j) represents the perception probability of node V _i and node V _j , C, α, β, γ, δ are all constants, D is the volume of the water area, expressed as |D|=L*W*H , L is the length of the water area, W is the width of the water area, H is the depth of the water area, and N is the total number of sensor nodes;

2. Optimal Rigid Graph Theory

Define the key underwater monitoring areas of different scales, and select the minimum number of nodes that can cover the key areas globally to construct the optimal rigidity graph. Other nodes in the key areas switch to the dormant state, that is, only forward but do not collect information; optimal The rigidity map is constructed by the stiffness matrix, and the rigidity matrix of the 3D underwater space is defined as follows:

Each row in the matrix represents an edge in the rigid graph, and q represents the 3D coordinates of the vertex;

3. BA growth model

The BA growth algorithm consists of two parts.

■Growth: Determine the number of nodes in the optimal rigid graph as m, connect isolated nodes or vertices of connected subgraphs to m ₀ nodes of the rigid graph, and m ₀ <m:

连接到刚性图节点，其中de表示节点度，N表示节点总数，当连接概率相等时，连接到剩余能量更大的节点；■Priority connection: isolated nodes or vertices of connected subgraphs with probability

Connect to rigid graph nodes, where de represents the node degree, N represents the total number of nodes, when the connection probability is equal, connect to the node with greater residual energy;

4. Replacement algorithm

When the remaining energy of node V _i is lower than 0, calculate the coverage of other remaining nodes and adjacent nodes of V _i , so that enabling the least adjacent nodes can still ensure the global coverage of key areas, and switch the state of the selected least adjacent nodes In the wake-up state, replace the failed node to complete the data collection and transmission functions, and reconstruct the optimal rigidity graph according to the remaining energy of the new node.

The specific steps in the first stage are as follows.

1) Use the edge construction model to calculate the connection probability P _ij of each edge, and connect nodes V _i and V _j according to the probability P _ij to form a network topology that conforms to complex network characteristics;

2) Define key monitoring areas of different scales, and construct optimal rigidity graphs in key monitoring areas to balance node energy consumption;

3) Determine the number of nodes in the optimal rigid graph and the number of isolated nodes and connected subgraphs, and connect the isolated nodes and connected subgraphs to rigid graph nodes according to the growth model of BA (Barabsi-Albert) scale-free network.

Features and beneficial effects of the present invention are:

The invention proposes an underwater robust topology generation strategy based on scale-free network and rigid graph theory, which balances energy consumption of nodes while improving network robustness, and designs a replacement algorithm for failed nodes to ensure global coverage of key monitoring areas. The monitoring of key monitoring areas has been strengthened, and the energy consumption of nodes can be balanced while improving network robustness.

Description of drawings:

Figure 1 is the structural design of the underwater network topology;

Fig. 2 is a flowchart of topology generation;

Fig. 3 is a flow chart of data transmission;

Figure 4 is a histogram of underwater sensor network life comparison;

Figure 5 is a line graph of node density in key areas;

Figure 6 is a broken line diagram of the robustness of the underwater sensor network.

Detailed ways

In order to improve the robustness of the underwater sensor network while reducing node energy consumption, the present invention proposes a robust topology generation strategy based on scale-free network and rigid graph theory, and optimizes network deployment by utilizing the advantages of scale-free network and rigid graph , and designed a replacement algorithm for failed nodes to ensure the global coverage of key areas. The robust topology strategy of the present invention consists of a topology generation phase and an information transmission phase.

1. Topology generation stage

Nodes close to the cluster head in the underwater acoustic sensor network undertake more forwarding tasks. In the topology generation stage, the complex network theory is used to generate the network topology first, then the rigid graph is constructed in the key areas, and finally the isolated nodes or connected subgraphs are connected to the rigid graph to generate the initial topology of the underwater sensor network, and the node degree of the network obeys the power law distributed. Specific steps are as follows.

1) Use the edge construction model to calculate the connection probability P _ij of each edge, and connect nodes V _i and V _j according to the probability P _ij to form a network topology that conforms to complex network characteristics.

2) Define the key monitoring areas with different scales, and construct the optimal rigidity graph in the key monitoring areas to balance the energy consumption of nodes.

3) Determine the number of nodes in the optimal rigid graph and the number of isolated nodes and connected subgraphs, and connect the isolated nodes and connected subgraphs to rigid graph nodes according to the growth model of BA (Barabsi-Albert) scale-free network.

2. Data transmission stage

The data collected by sensor nodes is transmitted according to the optimal path selected by the greedy algorithm to ensure the least energy consumption of data transmission. When the transmission probability PR _c (i, CH _k )>ζ of the path, it means that the data sent by the node V _i is successfully received. ζ is the threshold constant.

Every 10 seconds, the topology of the optimal rigid graph is adjusted according to the remaining energy of the nodes to balance the energy consumption among nodes.

When the remaining energy of a node in the key area is lower than 0, it means that the node is dead, which affects the coverage and connectivity of the key area. A replacement algorithm is used to ensure global coverage of key areas.

The specific manner, structure, features and functions of the robust topology generation strategy designed according to the present invention are described in detail below in conjunction with the accompanying drawings.

1. Edge structure model

其中P_ij表示节点V_i与节点V_j的连接概率，d(i,j)表示节点V_i与节点V_j的距离，P_C(i,j)表示节点V_i与节点V_j的通信概率，P_S(i,j)表示节点V_i与节点V_j的感知概率，C,α,β,γ,δ皆为常数。根据概率P_ij连接节点对，使得网络具有复杂网络的特性。The present invention calculates the connection probability of edges in the underwater sensor network according to the edge structure model,

Where P _ij represents the connection probability between node V _i and node V _j , d(i, j) represents the distance between node V _i and node V _j , P _C (i, j) represents the communication probability between node V _i and node V _j , P _S (i, j) represents the perception probability of node V _i and node V _j , and C, α, β, γ, δ are all constants. The pairs of nodes are connected according to the probability P _ij so that the network has the characteristics of a complex network.

2. Optimal Rigid Graph Theory

The invention defines key underwater monitoring areas with different scales, and selects the minimum number of nodes that can cover the key areas globally to construct an optimal rigid graph, and other nodes in the key areas switch to a dormant state, that is, only forwarding but not collecting information . The optimal rigidity map can be constructed by using the rigidity matrix, and the rigidity matrix of the 3-dimensional underwater space is defined as follows.

Each row in the matrix represents an edge in the rigid graph.

3. BA growth model

The BA growth algorithm consists of two parts.

■Growth: Determine the number of nodes in the optimal rigid graph as m, connect isolated nodes or vertices of connected subgraphs to m ₀ nodes of the rigid graph, and m ₀ <m.

连接到刚性图节点，其中de表示节点度，N表示节点总数。当连接概率相等时，连接到剩余能量更大的节点。■Priority connection: isolated nodes or vertices of connected subgraphs with probability

Connected to rigid graph nodes, where de is the node degree and N is the total number of nodes. When the connection probability is equal, connect to the node with greater residual energy.

4. Replacement algorithm

When the remaining energy of node V _i is lower than 0, calculate the coverage of other remaining nodes and adjacent nodes of V _i , so that enabling the least adjacent nodes can still ensure the global coverage of key areas, and switch the state of the selected least adjacent nodes In the wake-up state, replace the failed node to complete the data collection and transmission functions, and reconstruct the optimal rigidity graph according to the remaining energy of the new node.

5. Performance curve

The present invention needs to be carried out on the premise that the initial nodes conform to a uniform random distribution. Figures 4, 5, and 6 are three common performance comparison curves. The robust topology generation strategy designed by the invention effectively strengthens the monitoring of key areas, and balances energy consumption of nodes while improving network robustness.

Claims (2)

1. A robust topology generation method based on a underwater acoustic sensor network is characterized by comprising the following steps:

1. topology generation phase

Nodes close to cluster heads in the underwater acoustic sensor network bear more forwarding tasks, network topology is firstly generated by utilizing a complex network theory in a topology generation stage, then a rigid graph is constructed in a key area, and finally isolated nodes or connected subgraphs are connected to the rigid graph to generate an initial topology of the underwater sensor network, and the node degree of the network obeys power rate distribution;

2. data transmission stage

The data collected by the sensor nodes are transmitted according to the optimal path selected by the greedy algorithm, so that the minimum transmission energy consumption of the data is ensured, and when the transmission probability PR of the path is the same _c (i,CH _k )>ζ represents node V _i The transmitted data is successfully received, ζ is a threshold constant, CH _k Represents the kth cluster head node, PR _c (i,CH _k ) Representing slave node V _i To the cluster head node CH _k The communication probability of a path of (a);

every 10 seconds, the topological structure of the optimal rigid graph is adjusted according to the residual energy of the nodes so as to balance the energy consumption among the nodes;

when the residual energy of a certain node in the key area is lower than 0, the node is dead, the coverage and connectivity of the key area are affected, and the global coverage of the key area is ensured by using a replacement algorithm, wherein the specific steps in the first stage are as follows:

1) Calculating the connection probability P of each edge by using an edge construction model _ij According to probability P _ij Connection node V _i And V is equal to _j Forming a network topology conforming to the complex network characteristics;

2) Defining key monitoring areas with different scales, and constructing an optimal rigidity graph in the key monitoring areas so as to balance node energy consumption;

3) And determining the number of nodes in the optimal rigid graph and the number of the isolated nodes and the nodes of the connected subgraphs, and connecting the isolated nodes and the connected subgraphs to the nodes of the rigid graph according to a growth model of the BA scaleless network.

2. The method of generating a robust topology based on an underwater acoustic sensor network of claim 1, further comprising,

1. edge construction model

Calculating the connection probability of edges in the underwater sensor network according to the edge construction model:

wherein P is _ij Representing node V _i And node V _j D (i, j) represents node V _i And node V _j Distance, P _C (i, j) represents node V _i And node V _j Communication probability, P of _S (i, j) represents node V _i And node V _j Wherein D is the volume of the water area, expressed as |d|=l×w×h, L is the water area length, W is the water area width, H is the depth of the water area, and N is the total number of sensor nodes;

2. theory of optimal stiffness map

Defining underwater key monitoring areas with different scales, selecting the minimum node number capable of globally covering the key areas to construct an optimal rigid graph, and switching other nodes of the key areas to a dormant state, namely forwarding only but not collecting information; the optimal stiffness map is constructed using a stiffness matrix, which is defined as follows for a 3-dimensional underwater space:

each row in the matrix represents an edge in the rigid graph, q represents the 3-dimensional coordinates of the vertex;

3. BA (BA) growth model

The BA growth algorithm consists of two parts;

■ Growth: determining the number of nodes in the optimal rigid graph as m, and connecting the vertices of the isolated nodes or connected subgraphs to the m of the rigid graph ₀ Each node, and m ₀ <m；

■ Priority connection: probability of vertices of isolated nodes or connected subgraphs

Connecting to nodes of the rigid graph, wherein de represents node degree, N represents total number of nodes, and connecting to nodes with larger residual energy when connection probabilities are equal;

4. substitution algorithm

When node V _i When the residual energy of (2) is lower than 0, calculating other residual nodes and V _i The coverage area of the adjacent nodes is enabled to ensure that the minimum adjacent nodes can still ensure the global coverage of the key areas, the state of the minimum adjacent nodes is switched to the wake-up state, the functions of collecting and transmitting data are completed by replacing the failure nodes, and the optimal rigidity graph is reconstructed according to the residual energy of the new nodes.

Images