CN115623512A - Self-adaptive dynamic topology survivability optimization method of wireless self-organizing network - Google Patents
Self-adaptive dynamic topology survivability optimization method of wireless self-organizing network Download PDFInfo
- Publication number
- CN115623512A CN115623512A CN202211011501.0A CN202211011501A CN115623512A CN 115623512 A CN115623512 A CN 115623512A CN 202211011501 A CN202211011501 A CN 202211011501A CN 115623512 A CN115623512 A CN 115623512A
- Authority
- CN
- China
- Prior art keywords
- node
- network
- nodes
- topology
- survivability
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000000034 method Methods 0.000 title claims abstract description 44
- 238000005457 optimization Methods 0.000 title claims abstract description 42
- 238000004891 communication Methods 0.000 claims abstract description 103
- 238000001514 detection method Methods 0.000 claims abstract description 10
- 238000011156 evaluation Methods 0.000 claims abstract description 7
- 239000011159 matrix material Substances 0.000 claims description 18
- 230000003044 adaptive effect Effects 0.000 claims description 15
- 238000004364 calculation method Methods 0.000 claims description 14
- 238000012217 deletion Methods 0.000 claims description 6
- 230000037430 deletion Effects 0.000 claims description 6
- 238000003379 elimination reaction Methods 0.000 claims description 5
- 238000012544 monitoring process Methods 0.000 claims description 5
- 238000010295 mobile communication Methods 0.000 claims description 3
- 238000010586 diagram Methods 0.000 description 4
- 230000008030 elimination Effects 0.000 description 4
- 238000011160 research Methods 0.000 description 3
- 238000013461 design Methods 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
- 238000012545 processing Methods 0.000 description 2
- 238000012163 sequencing technique Methods 0.000 description 2
- 238000013459 approach Methods 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 230000005540 biological transmission Effects 0.000 description 1
- 230000000254 damaging effect Effects 0.000 description 1
- 230000002787 reinforcement Effects 0.000 description 1
Images
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W24/00—Supervisory, monitoring or testing arrangements
- H04W24/02—Arrangements for optimising operational condition
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W40/00—Communication routing or communication path finding
- H04W40/24—Connectivity information management, e.g. connectivity discovery or connectivity update
- H04W40/246—Connectivity information discovery
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W40/00—Communication routing or communication path finding
- H04W40/24—Connectivity information management, e.g. connectivity discovery or connectivity update
- H04W40/248—Connectivity information update
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04W—WIRELESS COMMUNICATION NETWORKS
- H04W84/00—Network topologies
- H04W84/18—Self-organising networks, e.g. ad-hoc networks or sensor networks
Landscapes
- Engineering & Computer Science (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Mobile Radio Communication Systems (AREA)
Abstract
The invention discloses a self-adaptive dynamic topology survivability optimization method of a wireless self-organizing network, which comprises the following steps: joint detection and evaluation: detecting the joint points in the network, calculating and evaluating the size of the damage resistance influence of each joint point on the network by using the splitting coefficient index, and then preferably eliminating the joint points in the network in sequence based on the splitting coefficient index of the joint points; selecting redundant relay nodes: if the algebraic connectivity of the network topology is the maximum after a certain communication relay node is deleted, selecting the communication relay node for topology optimization; determining an optimized deployment position: determining a target position of the optimized deployment of the communication relay node; the relay node moves and locally adjusts: and carrying out mobile deployment on the communication relay node to a target position, and carrying out local adjustment according to the actual communication condition obtained at the target position so as to effectively communicate each communication branch. The invention can enhance the connectivity among the network nodes, thereby improving the survivability of the network.
Description
Technical Field
The invention relates to the technical field of wireless self-organizing network communication, in particular to a self-adaptive dynamic topology survivability optimization method of a wireless self-organizing network.
Background
The wireless self-organizing network is a network which can be deployed quickly and built flexibly, the network topology of the wireless self-organizing network is influenced by the position movement of nodes, the communication environment and the like and can be changed continuously, and the communication relation between the nodes is in a multi-hop mesh connection relation. As nodes move in the network, the network topology is constantly changing due to changes in node neighbor relationships. In the dynamic change process of the network topology, the connectivity and the integrity of the whole network topology are maintained, which is the premise of ensuring the effective transmission of the application information and is the basic requirement of the wireless self-organizing network application.
To ensure the connectivity and integrity of the network, the survivability capability of the network is one aspect that needs to be considered heavily in the design and planning of the network in general. In a wireless ad hoc network, survivability of the network refers to the ability of the network to continue to maintain communications available when a node in the network fails or is destroyed. When a part of nodes in the network are failed or damaged, if one or more communication paths still exist among the rest nodes in the network, the network has certain survivability. In real network applications, especially for military application purposes, if a core key node fails, the network may be split, and the connectivity and integrity of the network may be damaged.
In a wireless self-organizing network with multi-node and multi-hop relay, the topological structure form of the network directly determines the quality of the survivability of the network. The topological structure form of the network can be represented by a graph of graph theory research, and for the network topological graph, the connectivity in the graph theory research is an important index for measuring the survivability of the network. Therefore, the basic approach for improving the survivability of the network is to add link connection between nodes in the network, enrich the topological connection relationship between the nodes, and avoid the situation that the communication path between a node and another node can only pass through a unique and necessary route in the network topology structure. The existing method mainly aims at optimizing and adjusting the node transmitting power, improves the network topology structure and improves the survivability of the network, but can not effectively solve the topology connectivity problem of the wireless self-organizing network when the link is interrupted due to the node failure or the adjacent node exceeds the maximum communication distance in the node moving process.
Disclosure of Invention
In order to solve the problem of network connectivity damage caused by node failure or link interruption, the invention provides a self-adaptive dynamic topology survivability optimization method of a wireless self-organizing network.
The technical scheme adopted by the invention is as follows:
a self-adaptive dynamic topology survivability optimization method of a wireless self-organizing network comprises the following steps:
s1, joint point detection and evaluation: detecting the joint points in the network, calculating and evaluating the size of the damage resistance influence of each joint point on the network by using the splitting coefficient index, and then preferably eliminating the joint points in the network in sequence based on the splitting coefficient index of the joint points;
s2, redundant relay node selection: if the algebraic connectivity of the network topology is the maximum after a certain communication relay node is deleted, the communication relay node has the highest redundancy, and the communication relay node is selected for topology optimization;
s3, determining an optimized deployment position: determining the target position of the optimized deployment of the communication relay node, so that the moved communication relay node can effectively communicate with a communication branch connected with a target joint point;
s4, moving and locally adjusting the relay node: and the communication relay node is moved and deployed to a target position, and local adjustment is carried out according to the actual communication condition obtained at the target position so as to effectively communicate each communication branch, thereby eliminating the joint points which influence survivability in the network.
Further, a network topology obtained by monitoring the communication relay nodes is represented by an undirected graph G = (V, E), where V is a set of nodes in the network, and E is a set of connections between nodes in the network; if the undirected graph G is split into two or more unconnected subgraphs after the node V belongs to the node V and all the edges associated with the node V are deleted from the undirected graph G, the node V is the joint point of the undirected graph G.
Further, in step S1, if N existing in the network is found by the node detection a The individual node is then set as node V a Is expressed and | V a |＝N a (ii) a If the undirected graph G is split into l connected branches after the node is deleted, the kth connected branch is denoted as G k The number of nodes of each connected branch is N 1 、N 2 、…、N l Then, the calculation formula of the splitting coefficient index e is as follows:
in the above formula, N is the number of common nodes in the network, N (N-1) represents a source-destination node communication pair that the undirected graph G can support, N k (N k -1) represents a connecting branch G k The greater the splitting coefficient index e is, the higher the influence degree of the joint on the network survivability is.
Further, the sets V are targeted one by one a Calculating a splitting coefficient index e of each joint point, sequencing the joint points according to the size of the splitting coefficient index e, and sequentially eliminating the joint points according to the sequence of the splitting coefficient index e from large to small.
Further, the step S2 of selecting the redundant relay node includes the following substeps:
step S201. Initializing set
Step S202, aiming at each communication relay node Rv in the network one by one i Deleting node Rv i Thereafter, detecting whether a new joint point is generated in the network, wherein i =1,2,3, \8230;, M; if no new joint point is generated, the node Rv i Join into set V c In, set V c All redundant movable communication relay nodes are contained;
step S203. Selecting a set V c Communication relay node Rv with minimal impact on network topology survivability k The priority scheduling is used for executing topology optimization mobile deployment; for set V c Each node v in i ∈V c Deleting node v i The latter network topology is represented by G i Calculate each graph G i Algebraic connectivity λ (G) i ) Taking the maximum value max [ lambda (G) ] i ),1≤i≤|V c The node v corresponding to | } i As Rv k (ii) a If a plurality of nodes have the same maximum value, selecting the node closest to the target position determined by the optimized deployment.
Further, in step S203, the method for calculating the algebraic connectivity includes:
if a network has n nodes, A (G) is the adjacency matrix representation of the network topology G:
wherein, a ij =1 denotes node v i ,v j There is a link between them; otherwise, a ij ＝0；
A diagonal matrix formed by node degrees of each node of the graph G is represented by D (G):
wherein the node degree
The laplacian matrix of graph G is represented by laplacian matrix L (G), which is calculated as:
L(G)＝D(G)-A(G)
the eigenvalues of the laplacian matrix L (G) are all non-negative real numbers, the smallest eigenvalue is 0, and the n eigenvalues are ordered and represented as 0= λ 1 ≤λ 2 ≤…≤λ n (ii) a The algebraic connectivity λ (G) of the graph G is the second smallest eigenvalue of the laplace matrix L (G), i.e. there are:
λ(G)＝λ 2
the larger the algebraic connectivity λ (G), the better the connectivity of the network, and the better the survivability of the network topology.
Further, if the joint point v a The p connected branches formed after deletion are respectively WG 1 ,WG 2 ,…,WG p Whose node sets are respectively denoted as V 1 ,V 2 ,…,V p Then step S3, i.e. the optimal deployment location determination, comprises the following sub-steps:
s301, recording the target position of optimized deployment of the communication relay node by R (x, y), and recording the target position by D m Recording the sum of the squares of the minimum distances to each connected branch, assigning an initial value D m ＝+∞；
Step S302. WG from the connected branch in turn i One node is selected from the group and is respectively expressed as v 1 ,v 2 ,…,v p Node v i The corresponding coordinate position is (x) i ,y i ) Wherein i is more than or equal to 1 and less than or equal to p; compute node v i Geometric center position A (x) of the formed closed geometric shape d ,y d )；
Step S303, calculating the geometric center position A (x) d ,y d ) To each connected branch node v i The squared sum of euclidean distances of (D):
step S304. Compare D and D m Size, take the minimum value, and update D m Record, i.e. with D m ＝min(D,D m ) (ii) a If D is present after updating m If D is not satisfied, then D is saved m The target position corresponding to the value is the geometric center position A (x) d ,y d ) I.e. with R (x, y) = A (x) d ,y d )；
S305, repeatedly executing the steps S302-S304 until all the connected branches WG are traversed i All the nodes in the network node are selected, combined and calculated, and a final result R (x, y) is output, namely the target position of the optimized deployment of the communication relay node.
Further, in step S302, node v i Geometric center position A (x) of the formed closed geometric shape d ,y d ) Comprises the following steps:
further, step S4, that is, the relay node moves and locally adjusts, includes the following sub-steps:
step S401, communication relay node Rv k Autonomously moving to a target position;
step S402. If not realizing all connected branch WG i The connection of the nodes then communicates with the relay node Rv k To optimally eliminated articulated point objects v a The position is locally adjusted by moving until the WG of all the connected branches is realized i All the nodes are connected; in the lowest limit, the relay node Rv k Will be moving to the joint point v a At the posterior homoarticular point v a Connections are established with all connected branches as well.
Further, after the elimination processing of one joint is completed, if there are joints to be eliminated in the network and there are redundant mobile communication relay nodes, the steps S1 to S4 are iteratively executed, and the network topology is continuously optimized until all joints are eliminated.
The invention has the beneficial effects that:
(1) The invention detects and evaluates each joint point existing in the network by analyzing the network topology in real time, and adaptively selects the most appropriate communication relay node to execute the mobile deployment operation for eliminating the joint point, thereby expanding the connected nodes and links of the key part of the network, avoiding the damage influence of the failure of the key node on the connectivity and integrity of the network, and realizing the dynamic optimization promotion of the survivability of the network topology.
(2) The invention utilizes the splitting coefficient index to calculate and evaluate the influence of each joint point on the network survivability, and preferentially eliminates the joint point with the largest influence on the network survivability, so that the communication relay nodes with limited configuration quantity in the network can play the role of improving the network survivability to the maximum extent.
(3) According to the invention, algebraic connectivity calculation and analysis are carried out on the network topology, and the communication relay node with the highest redundancy in the current network is selected to implement the mobile deployment operation of eliminating the joint point, so that reasonable and efficient utilization of the communication relay node resource can be ensured.
Drawings
Fig. 1 is a flowchart of an adaptive dynamic topology survivability optimization method according to embodiment 1 of the present invention.
Fig. 2 is a network topology connection diagram according to embodiment 2 of the present invention.
Fig. 3 shows an optimized pre-deployment network topology according to embodiment 2 of the present invention.
Fig. 4 shows a network topology after optimized deployment according to embodiment 2 of the present invention.
Fig. 5 is a network topology connection diagram according to embodiment 3 of the present invention.
Fig. 6 shows a network topology before optimized deployment according to embodiment 3 of the present invention.
Fig. 7 shows an optimized deployed network topology according to embodiment 3 of the present invention.
Detailed Description
In order to more clearly understand the technical features, objects, and effects of the present invention, specific embodiments of the present invention will now be described. It should be understood that the detailed description and specific examples, while indicating embodiments of the invention, are given by way of illustration only, not by way of limitation, i.e., the embodiments described are intended as a selection of the best mode contemplated for carrying out the invention, not as a full mode. All other embodiments, which can be derived by a person skilled in the art from the embodiments of the present invention without making any creative effort, shall fall within the protection scope of the present invention.
Example 1
As shown in fig. 1, this embodiment provides an adaptive dynamic topology survivability optimization method for a wireless ad hoc network, which first detects joint points in the network, calculates and evaluates the impact of each joint point on the survivability of the network by using a splitting coefficient index, and then preferentially eliminates the joint points in the network in sequence based on the splitting coefficient index of the joint points. And aiming at each joint point in the network, selecting the optimal communication relay node in the current network one by one for mobile deployment, so that the mobile communication relay node can effectively communicate with the communication branch connected with the target joint point. By moving, deploying and adjusting the communication relay nodes one by one, all the joint points influencing survivability in the network are eliminated in sequence. The method adaptively selects the communication relay node for mobile deployment, optimizes and adjusts the network topology structure in real time, and can dynamically realize the reinforcement of survivability connectivity of the whole wireless self-organizing network.
The planning design wireless self-organizing network is composed of N common nodes and M communication relay nodes. The N common nodes are deployed and work in a certain area according to application or task requirements to form a multi-hop wireless self-organizing network, and the topology of the network is changed dynamically along with the work and movement of each node. In order to realize the real-time adaptive dynamic topology survivability optimization of the network, M communication relay nodes (relay nodes for short) are additionally planned and deployed in the network. The M communication relay nodes can move freely in the network according to the requirement of the whole network topology optimization adjustment, the optimal positions are adaptively selected for deployment, and communication relay service is provided for common nodes in the network.
And the communication relay nodes in the network continuously monitor the network topology in real time, and carry out calculation and analysis according to the monitoring result to implement dynamic topology optimization of the network. For convenience of description, a network topology obtained by monitoring by the communication relay node is represented by an undirected graph G = (V, E), where V is a set of nodes in a network and E is a set of connections between nodes in the network.
Based on the monitoring of the communication relay node on the network topology, the self-adaptive dynamic topology survivability optimization method provided by the embodiment comprises 4 steps: the main working mechanism flow of the method is shown in fig. 1, and comprises joint point detection and evaluation, redundant relay node selection, optimal deployment position determination, relay node movement and local adjustment.
(1) Joint point detection and evaluation
The joint point defines: in the undirected connected graph G = (V, E), if the graph G is split into two or more unconnected subgraphs after the node V ∈ V and all the edges associated with the node V are deleted from the graph G, then the node V is the joint point of the graph G.
The detection of the nodes in the network topological graph can be realized by adopting a naive method of judging the nodes one by one according to the definition, and can also be quickly detected by utilizing a classic Tarjan algorithm provided by related research. The existence of the joint points in the network is the main reason of poor network survivability, once the joint points are in failure or damaged and fail, the network is split into a plurality of connected branches, and all communication nodes do not form a complete connected network any more. Hence, a node is a key node that affects network connectivity. The joint points in the network are eliminated through reasonable deployment of the communication relay nodes, and the survivability of the network can be effectively improved.
Let us assume that the node detects the presence of N in the network a Each joint point is then set as a node V a Is expressed as | V a |＝N a . The impact of different nodes in the network on the survivability of the network is different. When the planning number of the communication relay nodes is limited, the joint nodes with higher influence on the network survivability need to be eliminated preferentially according to the damage degree of the joint nodes on the survivability.
And defining a splitting coefficient index e of the joint point, and expressing the degree of splitting of the network after the joint point is deleted by using the splitting coefficient index e so as to measure the influence of the joint point on the network survivability. Set the undirected graph G split after the node deletionIn l connected branches, the k connected branch is denoted as G k The number of nodes of each connected branch is N 1 、N 2 、…、N l Then, the calculation formula of the splitting coefficient index e is as follows:
in the above formula, N (N-1) represents a source-destination node communication pair that the undirected graph G can support, N k (N k -1) represents a connecting branch G k Source-destination node communication pairs may be supported. It can be seen that, because the node is deleted, the number of source-destination node communication pairs supported by the network is reduced, and the calculation of the splitting coefficient index e reflects the influence of the node deletion on the support number of the communication node. The larger the splitting coefficient index e is, the higher the influence degree of the node on the network survivability is.
Aim at set V one by one a Calculating a splitting coefficient index e of each joint point, sequencing the joint points according to the size of the splitting coefficient index e, and sequentially eliminating the joint points according to the sequence of the splitting coefficient index e from large to small.
(2) Redundant relay node selection
M communication relay nodes in the network can be used for optimizing the network topology, so that the joint points in the network topology graph are eliminated. However, in a network operation process, not every communication relay node can be conditionally used for topology optimization in a certain state. After some communication relay nodes are removed, new joint points can be generated in the network, and new connectivity problems are brought. Only those redundant communication relay nodes can be scheduled for topology-optimized mobile deployment. Therefore, it is necessary to select an appropriate redundant communication relay node to perform topology optimization work.
Preferably, the steps taken for selecting the redundant relay node are as follows:
step S201. Initializing set
Step S202, aiming at each communication relay node Rv in the network one by one i Deleting node Rv i Then, whether a new joint point is generated in the network is detected, wherein i =1,2,3, \8230;, M; if no new joint point is generated, the node Rv i Join into set V c In the set V c All redundant movable communication relay nodes are contained;
step S203. Selecting a set V c Communication relay node Rv with minimal impact on network topology survivability k The priority scheduling is used for executing topology optimization mobile deployment; for set V c Each node v in i ∈V c Delete node v i The latter network topology is represented by G i Calculate each graph G i Algebraic connectivity λ (G) i ) Taking the maximum value max [ lambda (G) ] i ),1≤i≤|V c The node v corresponding to | } i As Rv k (ii) a And if a plurality of nodes have the same maximum value, selecting the node closest to the target position determined by the optimized deployment.
Preferably, the algebraic connectivity calculation method includes:
if a network has n nodes, A (G) is the adjacency matrix representation of the network topology G:
wherein, a ij =1 denotes node v i ,v j There is a link between; otherwise, a ij ＝0；
A diagonal matrix formed by node degrees of nodes of the graph G is represented by D (G):
wherein the node degree
The laplacian matrix of graph G is represented by laplacian matrix L (G), which is calculated as:
L(G)＝D(G)-A(G)
the eigenvalues of the laplacian matrix L (G) are all non-negative real numbers, the smallest eigenvalue is 0, and the n eigenvalues are ordered and represented as 0= λ 1 ≤λ 2 ≤…≤λ n (ii) a The algebraic connectivity λ (G) of the graph G is the second smallest eigenvalue of the laplace matrix L (G), i.e. there are:
λ(G)＝λ 2
the larger the algebraic connectivity λ (G), the better the connectivity of the network, and the better the survivability of the network topology. In the above steps, the communication relay node with the largest algebraic connectivity of the network topology after the node deletion is selected, which means that the communication relay node has the highest redundancy.
(3) Optimizing deployment location determination
The communication relay node Rv selected in the previous step k To the target joint point v to be eliminated optimally a Mobile deployment nearby, enhanced joint point v a Connected respective connected branches WG k . In order to obtain better connection effect, the target position of the mobile deployment of the communication relay node needs to be determined.
For a target joint point v a The p connected branches formed after deletion, and the target position of the optimized deployment of the communication relay node should be a balanced compromise position from the p nodes nearest to the p connected branches, so that the communication relay node can establish good link connection with the p connected branches. Preferably, the geometric center of the coordinate positions of the nearest p nodes is selected as the target position of the optimized deployment.
Suppose a joint point v a The p connected branches formed after deletion are respectively WG 1 ,WG 2 ,…,WG p Whose node sets are respectively denoted as V 1 ,V 2 ,…,V p . In order to find the node nearest to the p connected branches and determine the geometric center position thereof, the present embodimentThe method comprises the following steps:
s301, recording the target position of the optimized deployment of the communication relay node by R (x, y) and recording the target position by D m Recording the sum of the squares of the minimum distances to each connected branch, and assigning an initial value D m ＝+∞；
Step S302. WG from the connected branch in turn i One node is selected from each of them, and is respectively expressed as v 1 ,v 2 ,…,v p Node v i The corresponding coordinate position is (x) i ,y i ) Wherein i is more than or equal to 1 and less than or equal to p; compute node v i Geometric center position A (x) of the formed closed geometric shape d ,y d )：
Step S303, calculating the geometric center position A (x) d ,y d ) To each connected branch node v i The squared sum of the euclidean distances of (D):
step S304. Compare D and D m Size, take the minimum value, and update D m Record, i.e. have D m ＝min(D,D m ) (ii) a If D is present after updating m If D is not satisfied, then D is saved m The target position corresponding to the value is the geometric center position A (x) d ,y d ) I.e. with R (x, y) = A (x) d ,y d )；
Step S305, the steps S302 to S304 are repeatedly executed until all the connected branches WG are traversed i All the nodes in the network node are selected, combined and calculated, and a final result R (x, y) is output, namely the target position of the optimized deployment of the communication relay node.
The above calculation process is described in terms of two-dimensional space coordinates, but the method is equally applicable to three-dimensional space coordinate applications.
(4) Relay node movement and local adjustment
In calculatingAfter the optimal deployment position R (x, y) of the communication relay node, the selected communication relay node Rv k The moving deployment to the target position is executed, local adjustment is carried out according to the actual communication situation obtained at the target position, and effective communication of each communication branch is ensured, and the method comprises the following steps:
step S401, communication relay node Rv k Autonomously moving to a target position;
step S402. If the WG with all the connected branches can not be realized i The connection of the nodes then communicates with the relay node Rv k To optimally eliminated articulated point objects v a The position is locally adjusted by moving until the WG of all the connected branches is realized i All the nodes are connected; in the lowest limit, the relay node Rv k Will be moving to the joint point v a Postero-isoarticular point v a Connections are established with all connected branches as well.
After the elimination processing of one joint point is completed, if joint points to be eliminated exist in the network and redundant movable communication relay nodes exist at the same time, the 4 steps are executed in an iterative mode, and the network topology structure is continuously optimized until all the joint points are eliminated.
Example 2
The present embodiment further describes an adaptive dynamic topology survivability optimization method by combining a network example on the basis of embodiment 1. It should be noted that, the embodiment and the operation process of the adaptive dynamic topology survivability optimization method are specifically described in the context of a network example, but the method of the present invention is not limited to be used in this example network.
Fig. 2 is a schematic diagram of a wireless ad hoc network topology connection, wherein the dotted links represent one-hop links for communication between nodes, and the numbers represent the numbers of the nodes. The example is 7 common nodes organized to form a network of multi-hop mesh topology connections.
For the network shown in fig. 2, through the detection and evaluation of the nodes, there are 2 nodes, namely node 4 and node 5, in the network, and the splitting coefficients of the nodes 4 and 5 are respectively represented as e 4 、e 5 Which calculatesRespectively as follows: e.g. of the type 4 ＝0.71，e 5 =0.52. The larger the splitting coefficient is, the larger the influence of the failure of the corresponding node on the survivability of the network is, and the poorer the communication maintaining capability of the remaining node network is. As is apparent from fig. 2, failure of node 4 has a greater damaging effect on the network than failure of node 5.
2 communication relay nodes are additionally deployed in the network, as shown in fig. 3, which are nodes R1 and R2 respectively. In the current network, new joint points cannot be generated by deleting the nodes R1 and R2, so that the nodes R1 and R2 can be used for mobile deployment of topology optimization in the selection process of redundant relay nodes. Through the calculation of step S203, the algebraic connectivity calculation after the nodes R1 and R2 are deleted has λ (G) respectively 1 )＝0.52，λ(G 2 ) =0.44. And taking the node R1 corresponding to the maximum value to be preferentially scheduled for executing topology optimization mobile deployment, and eliminating the target joint point 4 with the maximum splitting coefficient. Through the operation of optimizing the deployment location determination, the target joint point 4 is deleted to form 2 connected branches, and the 2 nodes closest to the target joint point are the node 3 and the node 5 in the 2 connected branches. Therefore, the target position of the optimized deployment of the communication relay node R1 is the geometric center position of the connecting line of the nodes 3 and 5. Finally, the relay node movement and local adjustment operation is executed, the node R1 moves to the target position, and local movement adjustment is carried out to the position of the joint point 4 according to the actual communication condition with the nodes 3 and 5.
After the optimized elimination of the joint point 4 is completed, the network also has a joint point 5 to be eliminated and a redundant movable communication relay node R2. Therefore, the operation process of dynamic topology survivability optimization is continuously executed, and the node 5 is eliminated through mobile deployment of the node R2. The network topology after the optimization is completed is shown in fig. 4.
Example 3
The present embodiment further describes an adaptive dynamic topology survivability optimization method by combining a network example on the basis of embodiment 1. It should be noted that, the embodiment and the operation process of the adaptive dynamic topology survivability optimization method are specifically described in the context of a network example, but the method of the present invention is not limited to be used in this example network.
Fig. 5 shows another wireless ad-hoc network topology connection diagram, in which 13 general nodes form a network with multi-hop mesh topology connection.
For the network shown in fig. 5, through the detection and evaluation of the nodes, there are 3 nodes, namely node 5, node 10 and node 12, in the network, and the splitting coefficients of the nodes 5, 10 and 12 are respectively represented as e 5 、e 10 、e 12 It is calculated as: e.g. of the type 5 ＝0.77，e 10 ＝0.50，e 12 ＝0.29。
3 communication relay nodes are additionally deployed in the network, as shown in fig. 6, which are nodes R1, R2 and R3 respectively. In the current network, new joint points cannot be generated after the nodes R1, R2 and R3 are deleted, so that the nodes R1/R2/R3 can be used for mobile deployment of topology optimization in the selection process of redundant relay nodes. Through the calculation in step S203, the algebraic connectivity calculation after the nodes R1/R2/R3 are deleted has lambda (G) 1 )＝0.177，λ(G 2 )＝0.204，λ(G 3 ) =0.177. And taking the node R2 corresponding to the maximum value to be preferentially scheduled for executing topology optimization mobile deployment, and eliminating the target joint point 5 with the maximum splitting coefficient. By optimizing the operation of deployment location determination, the target joint point 5 is deleted to form 3 connected branches, and the 3 nodes closest to the target joint point are the node 3, the node 7 and the node 10. Therefore, the target position for optimal deployment of the communication relay node R2 is the geometric center position of the connecting line configuration shape of the nodes 3, 7 and 10. Finally, the relay node movement and local adjustment operation is executed, the node R2 moves to the target position, and local movement adjustment is carried out to the position of the joint point 5 according to the actual communication conditions with the nodes 3, 7 and 10.
After the optimized elimination of the joint 5 is completed, the joint 10 and the joint 12 are also to be eliminated in the network, and the redundant movable communication relay nodes R1 and R3 are also provided. Therefore, the operation process of dynamic topology survivability optimization is continuously executed, the target joint 10 is eliminated through the mobile deployment of the node R1, and the joint 12 is also eliminated at the same time. The network topology after the optimization is completed is shown in fig. 7.
It should be noted that the foregoing method embodiments are described as a series of acts or combinations for simplicity in description, but it should be understood by those skilled in the art that the present application is not limited by the order of acts described, as some steps may occur in other orders or concurrently depending on the application. Further, those skilled in the art should also appreciate that the embodiments described in the specification are preferred embodiments and that the acts and modules referred to are not necessarily required in this application.
Claims (10)
1. A self-adaptive dynamic topology survivability optimization method of a wireless self-organizing network is characterized by comprising the following steps:
s1, joint point detection and evaluation: detecting the joint points in the network, calculating and evaluating the size of the damage resistance influence of each joint point on the network by using the splitting coefficient index, and then preferably eliminating the joint points in the network in sequence based on the splitting coefficient index of the joint points;
s2, selecting redundant relay nodes: if the algebraic connectivity of the network topology is the maximum after a certain communication relay node is deleted, the communication relay node has the highest redundancy, and the communication relay node is selected for topology optimization;
s3, determining an optimized deployment position: determining the target position of the optimized deployment of the communication relay node, so that the moved communication relay node can effectively communicate with a communication branch connected with a target joint point;
s4, moving and locally adjusting the relay node: and the communication relay node is moved and deployed to a target position, and local adjustment is carried out according to the actual communication condition obtained at the target position so as to effectively communicate each communication branch, thereby eliminating the joint points influencing survivability in the network.
2. The adaptive dynamic topology survivability optimization method of the wireless ad hoc network according to claim 1, wherein the network topology obtained by monitoring the communication relay nodes is represented by an undirected graph G = (V, E), where V is a set of nodes in the network and E is a set of connections between nodes in the network; if the undirected graph G is split into two or more unconnected subgraphs after the node V belongs to the node V and all the edges associated with the node V are deleted from the undirected graph G, the node V is the joint point of the undirected graph G.
3. The adaptive dynamic topology survivability optimization method of wireless ad hoc network as claimed in claim 2, wherein in step S1, if N existing in the network is found by the node detection a The individual node is then set as node V a Is expressed and | V a |＝N a (ii) a If the undirected graph G is split into l connected branches after the node is deleted, the kth connected branch is denoted as G k The number of nodes of each connected branch is N 1 、N 2 、…、N l Then, the calculation formula of the splitting coefficient index e is as follows:
in the above formula, N is the number of common nodes in the network, N (N-1) represents a source-destination node communication pair that the undirected graph G can support, N k (N k -1) represents a connecting branch G k The greater the splitting coefficient index e is, the higher the influence degree of the joint on the network survivability is.
4. The adaptive dynamic topology survivability optimization method of wireless ad hoc network according to claim 3, characterized in that it is directed to set V one by one a Each joint in the system is subjected to division coefficient index e calculation, the joint is sorted according to the size of the division coefficient index e, and the joint is eliminated sequentially according to the sequence of the division coefficient index e from large to small.
5. The adaptive dynamic topology survivability optimization method of the wireless ad hoc network according to claim 2, wherein the step S2 of selecting the redundant relay node comprises the following sub-steps:
step S201. Initializing set
Step S202, aiming at each communication relay node Rv in the network one by one i Deleting node Rv i Then, whether a new joint point is generated in the network is detected, wherein i =1,2,3, \8230;, M; if no new joint point is generated, the node Rv i Join into set V c In, set V c All redundant movable communication relay nodes are contained;
step S203. Selecting a set V c Communication relay node Rv with minimal impact on network topology survivability k The priority scheduling is used for executing topology optimization mobile deployment; for set V c Each node v in i ∈V c Delete node v i The latter network topology is represented by G i Calculate each graph G i Algebraic connectivity λ (G) i ) Taking the maximum value of max [ lambda ] (G) i ),1≤i≤|V c The node v corresponding to | } i As Rv k (ii) a And if a plurality of nodes have the same maximum value, selecting the node closest to the target position determined by the optimized deployment.
6. The adaptive dynamic topology survivability optimization method of the wireless ad hoc network according to claim 5, wherein in step S203, the algebraic connectivity calculation method comprises:
if a network has n nodes, A (G) is the adjacency matrix representation of the network topology G:
wherein, a ij =1 denotes node v i ,v j There is a link between them; otherwise, a ij ＝0；
A diagonal matrix formed by node degrees of nodes of the graph G is represented by D (G):
wherein the node degree
The laplacian matrix of graph G is represented by laplacian matrix L (G), which is calculated as:
L(G)＝D(G)-A(G)
the eigenvalues of the laplacian matrix L (G) are all non-negative real numbers, the smallest eigenvalue is 0, and the n eigenvalues are ordered and represented as 0= λ 1 ≤λ 2 ≤…≤λ n (ii) a The algebraic connectivity λ (G) of the graph G is the second smallest eigenvalue of the laplacian matrix L (G), namely:
λ(G)＝λ 2
the larger the algebraic connectivity λ (G), the better the connectivity of the network, and the better the survivability of the network topology.
7. The method of claim 2, wherein the virtual node v is a node a The p connected branches formed after deletion are respectively WG 1 ,WG 2 ,…,WG p Whose node sets are respectively denoted as V 1 ,V 2 ,…,V p Then step S3, i.e. the optimal deployment position determination, comprises the sub-steps of:
s301, recording the target position of optimized deployment of the communication relay node by R (x, y), and recording the target position by D m Recording the sum of the squares of the minimum distances to each connected branch, and assigning an initial value D m ＝+∞；
Step S302, WG is performed on the connected branches in sequence i One node is selected from each of them, and is respectively expressed as v 1 ,v 2 ,…,v p Node v i The corresponding coordinate position is (x) i ,y i ) Wherein i is more than or equal to 1 and less than or equal top; compute node v i Geometric center position A (x) of the formed closed geometric shape d ,y d )；
Step S303, calculating the geometric center position A (x) d ,y d ) To each connected branch node v i The squared sum of euclidean distances of (D):
step S304. Compare D and D m Size, take the minimum value, and update D m Record, i.e. have D m ＝min(D,D m ) (ii) a If D is present after updating m If D is not satisfied, then D is saved m The target position corresponding to the value is the geometric center position A (x) d ,y d ) I.e. with R (x, y) = A (x) d ,y d )；
S305, repeatedly executing the steps S302-S304 until all the connected branches WG are traversed i All the nodes in the network node are selected, combined and calculated, and a final result R (x, y) is output, namely the target position of the optimized deployment of the communication relay node.
8. The adaptive dynamic topology survivability optimization method of wireless ad hoc network as claimed in claim 7, wherein in step S302, node v i Geometric center position A (x) of the formed closed geometric shape d ,y d ) Comprises the following steps:
9. the adaptive dynamic topology survivability optimization method of wireless ad hoc network according to claim 2, wherein the step S4 of moving and locally adjusting the relay node comprises the sub-steps of:
step S401, communication relay node Rv k Autonomously moving to a target position;
step S402If no WG with all connected branches is achieved i The connection of the nodes then communicates with the relay node Rv k To optimally eliminated articulated point objects v a The local position is locally adjusted by moving until WG is realized with all the communication branches i All the nodes are connected; in the lowest limit, the relay node Rv k Will be moving to the joint point v a Postero-isoarticular point v a Connections are established with all connected branches as well.
10. The adaptive dynamic topology survivability optimization method of a wireless ad hoc network according to any one of claims 1 to 9, wherein after the elimination process of one node is completed, if there are nodes to be eliminated in the network and there are redundant mobile communication relay nodes at the same time, the steps S1 to S4 are iteratively executed to continuously optimize the network topology until all nodes are eliminated.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202211011501.0A CN115623512A (en) | 2022-08-23 | 2022-08-23 | Self-adaptive dynamic topology survivability optimization method of wireless self-organizing network |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202211011501.0A CN115623512A (en) | 2022-08-23 | 2022-08-23 | Self-adaptive dynamic topology survivability optimization method of wireless self-organizing network |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN115623512A true CN115623512A (en) | 2023-01-17 |
Family
ID=84857336
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202211011501.0A Pending CN115623512A (en) | 2022-08-23 | 2022-08-23 | Self-adaptive dynamic topology survivability optimization method of wireless self-organizing network |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN115623512A (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN117938543A (en) * | 2024-03-20 | 2024-04-26 | 国网江西省电力有限公司电力科学研究院 | A network dynamic defense method and system based on topology difference measurement |
-
2022
- 2022-08-23 CN CN202211011501.0A patent/CN115623512A/en active Pending
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN117938543A (en) * | 2024-03-20 | 2024-04-26 | 国网江西省电力有限公司电力科学研究院 | A network dynamic defense method and system based on topology difference measurement |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN106054875B (en) | A kind of distributed robots dynamic network connectivity control method | |
| Liu et al. | Restoring connectivity of damaged sensor networks for long-term survival in hostile environments | |
| CN111698728B (en) | Topology control system for dynamic network and control method thereof | |
| CN109889255B (en) | A Satellite Network Reconfiguration Method Based on Improved Bee Colony Algorithm | |
| Wei et al. | Wireless sensor network data collection by connected cooperative UAVs | |
| Senturk et al. | Connectivity restoration in delay–tolerant sensor networks using game theory | |
| CN110225569A (en) | A method of based on the WSNs clustering and multi-hop Routing Protocol for improving particle swarm algorithm | |
| CN103249179A (en) | Multi-objective mother foraging algorithm based optimization method for relay node deployment in wireless sensor network | |
| Hara et al. | Data replication methods based on the stability of radio links in ad hoc networks | |
| CN115623512A (en) | Self-adaptive dynamic topology survivability optimization method of wireless self-organizing network | |
| CN110167097A (en) | Mobile robot transistroute scheme based on weighted metric forwarding and path planning | |
| CN109560972B (en) | A Non-cooperative Inference Method for Ad Hoc Network Physical Topology | |
| CN110958659B (en) | WSN (Wireless sensor network) clustering routing method and device for improving genetic tabu search for deep well tunnel | |
| CN105959912B (en) | Based on the aggregation node localization method for improving discrete differential algorithm | |
| CN111371572B (en) | Network node election method and node equipment | |
| CN110519820A (en) | A kind of method for routing applied in cluster UAV Communication | |
| CN113242525B (en) | Mobile sensor network communication repairing method for cutting point fault | |
| KR101641952B1 (en) | Method of modifying node path according to balancing ratio of multi-hop routing path | |
| CN117915377A (en) | Self-organizing method and system of wireless mesh network | |
| AU2021101571A4 (en) | An efficient coverage management for smart iot application | |
| Mohammadi et al. | A new algorithm inspired by Impala Mexican Wave with variable stride for relay node placement as a nested reverse p-median problem in disjoint wireless sensor networks | |
| CN111601351B (en) | Gateway node selection method, node, device and medium | |
| CN112468963A (en) | Wireless sensor network connectivity repairing method, device, equipment and storage medium | |
| Künzel et al. | A reliable and low-latency graph-routing approach for iwsn using q-routing | |
| Ranganathan et al. | A self-organizing heuristic for building optimal heterogeneous ad-hoc sensor networks |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination |