[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

CN105978711B - A kind of best exchange side lookup method based on minimum spanning tree - Google Patents

A kind of best exchange side lookup method based on minimum spanning tree Download PDF

Info

Publication number
CN105978711B
CN105978711B CN201610286714.2A CN201610286714A CN105978711B CN 105978711 B CN105978711 B CN 105978711B CN 201610286714 A CN201610286714 A CN 201610286714A CN 105978711 B CN105978711 B CN 105978711B
Authority
CN
China
Prior art keywords
node
edge
spanning tree
optimal
minimum spanning
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.)
Active
Application number
CN201610286714.2A
Other languages
Chinese (zh)
Other versions
CN105978711A (en
Inventor
王宇虹
陈志�
岳文静
陈雨诗
卜杰
田思明
龚凯
杨天明
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Nanjing Post and Telecommunication University
Original Assignee
Nanjing Post and Telecommunication University
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Nanjing Post and Telecommunication University filed Critical Nanjing Post and Telecommunication University
Priority to CN201610286714.2A priority Critical patent/CN105978711B/en
Publication of CN105978711A publication Critical patent/CN105978711A/en
Application granted granted Critical
Publication of CN105978711B publication Critical patent/CN105978711B/en
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04LTRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L41/00Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
    • H04L41/14Network analysis or design
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22Indexing; Data structures therefor; Storage structures
    • G06F16/2228Indexing structures
    • G06F16/2246Trees, e.g. B+trees
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04LTRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L41/00Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
    • H04L41/14Network analysis or design
    • H04L41/145Network analysis or design involving simulating, designing, planning or modelling of a network
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04LTRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L41/00Arrangements for maintenance, administration or management of data switching networks, e.g. of packet switching networks
    • H04L41/50Network service management, e.g. ensuring proper service fulfilment according to agreements
    • H04L41/508Network service management, e.g. ensuring proper service fulfilment according to agreements based on type of value added network service under agreement
    • H04L41/5096Network service management, e.g. ensuring proper service fulfilment according to agreements based on type of value added network service under agreement wherein the managed service relates to distributed or central networked applications

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

The present invention provides a kind of best exchange side lookup method based on minimum spanning tree, and best exchange side is searched problem and is defined as graph model by this method, solves failure in corresponding best exchange from global angle, obtains solution space by the strategy such as distributed algorithm.The present invention is capable of forming in the global situation of solution failure lookup scheme in corresponding best exchange in graph model, so that the best exchange side Solve problems in graph model are optimized on Time & Space Complexity during solution, and can be avoided Premature Convergence.The invention solves best exchange side search problem and refer to a given communication network, certain side failure on minimum spanning tree in the network, cause temporary communication failure, a best exchange side is searched in the network with distributed algorithm, replace the failure side, so that communication is kept unimpeded as far as possible, and can reach such as communication network and restore that the purpose of minimum, minimum spanning tree diameter is as small as possible is lost.

Description

Optimal exchange edge searching method based on minimum spanning tree
Technical Field
The invention relates to a method for solving an optimal exchange edge in a minimum spanning tree of a communication network, which mainly solves the optimal exchange edge corresponding to a failure edge in a graph model from a global angle by using a distributed algorithm and belongs to the technical field of computer technology, information technology, graph mining and distributed processing intersection.
Background
A distributed system refers to all computer applications on several computers or processors that cooperate in some manner. The distributed processing is a computer system which connects a plurality of computers in different places, or with different functions, or with different data through a communication network and coordinately completes large-scale information processing tasks under the unified management control of a control system. Distributed processing utilizes networking technology to enable many small computers or microcomputers to be connected into a high performance computer system with the ability to solve complex problems.
The distributed algorithm is that when the multiply-add function is completed, the operation results generated by each corresponding bit of each input data are added in advance to form corresponding partial products, and then the partial products are accumulated to form the final result. The research of the distributed algorithm is derived from basic research in the development activity of the distributed system, and the content of the distributed algorithm forms the core technology of distributed computing.
Disclosure of Invention
The technical problem is as follows: the invention aims to solve the problem of finding the optimal exchange edge in the minimum spanning tree, which is to give a communication network, namely a graph model, give the minimum spanning tree and a failure edge in the graph model, select an optimal exchange edge from the graph model to replace the failure edge, recover the communication fault caused by the failure edge as soon as possible and minimize the diameter of the newly generated minimum spanning tree.
The technical scheme is as follows: the optimal exchange edge lookup problem in the minimum spanning tree is described as follows: a communication network is given, a failure edge is given, the optimal exchange edge in the graph model is found based on the optimal exchange edge searching method of the minimum spanning tree to replace the failure edge, so that the communication network can recover to operate as soon as possible, and the diameter of the newly generated minimum spanning tree is minimum. We assume that the communication network is organized in graph model G ═ (V, E), which is a weighted undirected graph. Each node may be connected to a plurality of or 0 other nodes, the nodes are connected to the nodes to form an edge, and each edge is regarded as an object to be queried. Our goal is to find an optimal exchange edge from the graph model G ═ V, E to replace the failed edge, so that the newly generated minimum spanning tree diameter is minimized.
The optimal exchange edge searching method based on the minimum spanning tree defines the optimal exchange edge searching problem in the communication network into an image model and obtains a solution space by adopting a distributed algorithm.
The invention discloses an optimal exchange edge query method based on a minimum spanning tree, which comprises the following steps:
step 1) according to information input by a user, constructing a graph model G (V, E) of an optimal exchange edge query problem in a network, wherein V is a node set, E is an edge set, n (V), m (E), n is the number of nodes in the graph model, and m is the number of edges in the graph model G (V, E). The method comprises the following specific steps:
step 11) user input comprises a group of node sets, an edge set, a minimum spanning tree and a failure edge. The above-mentionedThe node set input by the user is denoted as V ═ d1,d2,d3,…,dnH, set of edges E ═ E1,e2,e3,…,emN ═ V |, m ═ E |, each edge E corresponding to a non-negative length l (x), path p ═ E |, and<d1,d2,d3,…,dr>is represented by node d1,d2,d3,…,drA path is formed, | p | represents the length of the path, i.e. the sum of the lengths of all edges, and the minimum spanning tree is denoted as T. The n refers to the number of nodes in the node set; the m is the number of edges in the edge set.
Step 12) setting the node set V as { d ═ d1,d2,d3,…,dnAll nodes in the graph model G ═ nodes in (V, E).
Step 13) regarding a path between the node u and the node V as a graph model G ═ an arc between two nodes (V, E), taking a distance d (u, V) between the two nodes as a weight of the arc between the node u and the node V, and the d (u, V) is a weight of the shortest path between the node u and the node V in the graph model G ═ a (V, E).
Step 14) given the minimum spanning tree T ═ (V, e (T)), define D ═ D<d1,d2,d3,…,dk>And | D | is the diameter of the minimum spanning tree T ═ (V, e (T)), i.e., the longest path length in T. Central node D defining DcDefinition of DL=<d1,d2,d3…dc>Definition of DR=<dc,dc+1,dc+2…dk>And the nodes meet the following conditions: i DL|≥|DRL. D is the node D in the minimum spanning tree1,d2,d3,…,dkA path formed, said DLRefers to the node d in the minimum spanning tree1,d2,d3,…,dcForm a path, said DRRefers to the node d in the minimum spanning treec,dc+1,dc+2,…,dkForm a path, said | DLI means path DLDiameter of said | DRI means path DROf (c) is measured.
Step 15) let dcAs the center of the minimum spanning tree T ═ (V, e (T)), x ∈ V and x ≠ d for each nodecA parent node p (x) of node x is defined, and a child node set c (x) of node x is defined. Definition of Tx=(V(Tx),E(Tx) A sub-tree representing the smallest spanning tree T with node x as the root node. Definition VLIs represented by node dc-1For subtrees of the root node, define VRIs represented by node dc+1For subtrees of the root node, define VcRepresents except VL、VRAll other nodes.
Step 16) after the user inputs the failure edge e ═ x ', p (x')), the minimum spanning tree T ═ V, e (T)) is divided into two subtrees Tx′And T \ Tx′The said T \ Tx′Node x' is not included. The T \ Tx′Means composed of a set of nodes V (T)/V (T)x′) And the edge set E (T)/E (T)x′) A diagram consisting of/{ (x ', p (x')) }. Our task is to find an edge f for the failing edge e ═ (x ', p (x')) to replace this failing edge. F is any one of E \ E (T) which can enable two subtrees Tx′And T \ Tx′The edges that are reconnected together are called switched edges. Definition S (e ') represents a set of exchange edges corresponding to edge e'. For the failing edge e ' (x ', p (x ')), an optimal swap edge f ' is e (e '), which is the | D (T) of the minimum spanning tree that can be newly generated after adding the swap edgee′/f′) And | is minimal. The e ═ represents (x ', f (x ')) a given failing edge, and f ═ represents (z, z ') a swap edge. Said z is at TxOne node in (1); the z' is at T \ TxOne node in (b).
And 2) obtaining a solution space of the optimal exchange edge searching problem in the communication network on the graph model G (V, E) by adopting a distributed algorithm. The method comprises the following specific steps:
step 21) for a given failed edge e ' ((x ', f (x '))Traversing subtree T rooted at xx′Each node z in (a).
Step 22) wait for available information from the parent node, calculate | L (T)x′Z) l, while calculating available information for all child nodes and sending the information. The | L (T)x′Z) |, means starting with node z and at graph Tx′The length of the longest path in (1).
Step 23) for each local exchange edge f ═ z, z', for | L (T \ T)x′Z') | distributed computation. The local exchange edge is an edge in the edge set S (e') and adjacent to the node z; the | L (T \ T)x′Z ') is from node z' and at graph T \ Tx′The length of the longest path in (1). Wherein,
|L(T\Tx′,z′)|=max{d(z′,dk),d(z′,dc)+γ,d(z′,dc)+λ(p(x′)),
d(z′,u′)+d(u′,ρR)+μR-d(dkR)}
d (z', d)k) Means with node z' and node dkAn edge being an end point; d (z', d)c) Means with node z' and node dcAn edge being an end point; d (z ', u') refers to an edge with the node z 'and the node u' as endpoints; the d (u', p)R) Refers to the node u' and the node ρRAn edge being an end point; d (d) iskR) Means with node dkAnd node ρRAn edge being an end point; λ (p (x'))) refers to node dcStarting and entering into the vertex set VLBut does not pass the length of the longest path under node p (x'); u ' is the node closest to z ' on the longest path starting with node z ' on D (T); the rhoRMeans at node dkStarting and at node set VROn the longest path of (1), into VRA root node on a subtree; the gamma is the node dcStarting and containing only nodesCollection VCThe length of the longest path of the middle node; the V isCIs a finger node dcA node set formed by all the other nodes; the muRMeans with node dkStarting and at node set VRThe length of the longest path in (1).
Step 24) for each local exchange edge f ═ z, z', pair | D (T)e′/f) L, performing distributed computation: i D (T)e′/f)|=max{|D(T)|,|L(Tx′,z)|+l(f)+|L(T\Tx′Z') |. The L (T)x′Z) means starting at node z and in graph TxThe length of the longest path in (1); the L (T \ T)x', z ') refers to a graph starting at node z ' and being at T \ TxThe length of the longest path in (1); the term l (f) refers to the length of the local exchange edge f ═ z, z'.
Step 25) of selecting a temporary optimal exchange edge from among said local exchange edgesAnd stores the new diameter that will be generated after adding the swap edgeIf no local exchange edge exists, a dummy candidate edge is created and its new diameter is set to ∞.
Step 26) for each child node q ∈ C (z), according to the distance information obtained in the above step, selecting an optimal exchange edge candidate for each child nodeAnd stores the new diameter that will be generated after adding the swap edgeThen, the second temporary optimal exchange edge is selected from the optimal exchange edges corresponding to the child nodesThe above-mentioned
Step 27) defining a target optimal exchange edge fbest. Comparing the first temporary optimal switched edgeAnd a second optimal switching edgeThe exchange edge with the corresponding new smaller diameter is selected and added. If it isThen will beAs a target optimal switched edge fbest(ii) a If it isThen will beAs a target optimal switched edge fbest(ii) a If it isThen will beOrAs a target optimal switched edge fbestAll can be used.
Step 28) subtree T if x' is rootx′Is not traversed in its entirety, repeating steps 22) -27).
Step 29) determining the final solution space SolutionThe solution space contains a failure edge e' (x ', f (x ')) corresponds to the best exchange edge.
Has the advantages that: the invention forms an efficient optimal exchange edge searching method by utilizing a distributed algorithm. The method has the following beneficial effects:
1) the invention provides an optimal exchange edge searching method based on a minimum spanning tree, and the complete method process comprises the steps of defining an optimal exchange edge searching problem in a communication network into an image model and obtaining a solution space by adopting a distributed algorithm.
2) In the modeling process, one or one set of relatively abstract graph models are provided, and a correlation solving method in an actual problem can be converted into a mathematical model form.
3) The model of the invention searches the optimal exchange edge method from the global angle, so that the optimal exchange edge searching problem can finally obtain the optimal accurate solution.
4) The invention adopts node information pre-storage and distributed algorithm, thereby effectively reducing the time complexity and space complexity of the algorithm.
Drawings
Fig. 1 is a flowchart corresponding to the optimal exchange edge search method based on the minimum spanning tree.
Fig. 2 is an exemplary diagram corresponding to the minimum spanning tree model.
FIG. 3 is an example of an optimal exchange edge lookup.
Detailed Description
Some embodiments of the invention are described in more detail below with reference to the accompanying drawings.
According to the flowchart corresponding to the minimum spanning tree-based optimal exchange edge searching method shown in fig. 1 and the exemplary diagram corresponding to the minimum spanning tree model shown in fig. 2, the specific embodiment of the present invention is as follows:
1) defining an optimal switch edge finding problem in a communication network as a graph model.
11) The user input comprises a set of nodes, a set of edges, a minimum spanning tree, and a failing edge. As shown in fig. 3, a node set V is {1,2,3,4,5,6}, where node 1 is connected to node 2, and a distance d (1,2) } is 1; node 1 is connected to node 6, and the distance d (1,6) is 3; node 2 and node 3 are connected, and the distance d (2,3) is 1; node 3 and node 4 are connected, and the distance d (3,4) is 3; node 4 and node 5 are connected, and the distance d (4,5) is 2; node 4 and node 6 are connected, and the distance d (4,6) is 3; node 5 is connected to node 6 by a distance d (5,6) of 2, which has a total of 7 edges. All the nodes are connected with the edges between the nodes to form a graph model G ═ V, E. The minimum spanning tree T is a new graph generated by removing an edge between the nodes 4 and 6 and an edge between the nodes 5 and 6 in the graph model G ═ V, E. Wherein, the edge between the node 2 and the node 3 is a failure edge, the node 3 represents the lower end node of the failure edge, and the node 2 represents the father node of the node 3.
The failing edge is denoted as e ═ 3, 2.
12) Consider all nodes in node set V ═ {1,2,3,4,5,6} as nodes in graph model G ═ V, E).
After the attribute graph model G is established, the shortest circuit between any two vertexes has a corresponding weight value, and the proximity of the two vertexes is represented.
2) And obtaining a solution space of the optimal switching edge search problem in the communication network on the graph model G ═ V, E by adopting a distributed algorithm. The method comprises the following specific steps:
21) for a given failing edge e ═ 3,2, the subtree T rooted at node 33Composed of nodes 4,5 and the edges between nodes 4 and 5, subtree T3There are two nodes in total, node 4 and node 5, respectively, with node 4 denoted as z and node 5 denoted as q. For the subtree T3Is traversed.
22) The first traversal, the operand is node z. At this time, the local exchange edge is f (4,6), and L (T) is paired3Z) L is distributed calculated to obtain L (T)3,z)|=|L(T34) | 3. For | L (T \ T)3Z') L is calculated in a distributed manner to obtain L (T \ T)3,z′)|=|L(T\T36) | max {0,3+1,3+7,3} -, 10. For local exchange edge f (4,6), for | D (T)e/f) Carrying out distributed calculation to obtain | D (T)e/f) Max {10,3+3+10} -, 16. Recording temporary optimal switched edgesAnd stores the new diameter that will be generated after adding the swap edge
Next, z is traversed for child node q ∈ C (z), where node 4 has only one child node, node 5. At this time, the local exchange edge is f (5,6), and L (T) is paired3Q) L is distributed calculated to obtain L (T)3,q)|=L(T35) | 5. For | L (T \ T)3Z') L is calculated in a distributed manner to obtain L (T \ T)3,z′)|=|L(T\T36) | max {0,3+1,3+7,3} -, 10. For local exchange edge f (5,6), for | D (T)e/f) Carrying out distributed calculation to obtain | D (T)e/f) Max {10,5+2+10} ═ 17. Recording the second temporary optimal switched edgeAnd stores the new diameter that will be generated after adding the swap edge
23) Define the target optimal switch edge fbest. Comparing the first temporary optimal switched edgeAnd a second optimal switching edgeThe new smaller diameter side is selected for addition. Due to the fact thatSo willAs a target optimal switched edge fbestI.e. fbest=f(z,z′)=f(4,6)。
24) The second traversal, the operand is node q, the local exchange edge is f (5,6), and pair | L (T)3Q) L is distributed calculated to obtain L (T)3,q)|=|L(T35) | 5. For | L (T \ T)3Z') L is calculated in a distributed manner to obtain L (T \ T)3,z′)|=|L(T\T36) | max {0,3+1,3+7,3} -, 10. For local exchange edge f (5,6), for | D (T)e/f) Carrying out distributed calculation to obtain | D (T)e/f) Max {10,5+2+10} ═ 17. Recording the second temporary optimal switched edgeAnd stores the new diameter that will be generated after adding the swap edgeNode q has no child nodes, so there is no need to search for the best possible switching edge from the child nodes. Since the local exchange edge is f (5,6) corresponds to a larger diameter than f (4,6), the target optimal exchange edge fbestAnd remains unchanged as f (4, 6).
25) Determining the final solution space SolutionThe solution space includes an optimal switching edge f (4,6) corresponding to the failure edge e ═ 3, 2.

Claims (2)

1. A method for searching an optimal exchange edge based on a minimum spanning tree is characterized by comprising the following steps:
step 1) according to information input by a user, constructing a graph model G (V, E) of an optimal exchange edge query problem in a network, wherein V is a node set, E is an edge set, n (V), m (E), n is the number of nodes in the graph model, and m is the number of edges in the graph model G (V, E);
step 2) obtaining a solution space of the optimal exchange edge searching problem in the communication network on a graph model G (V, E) by adopting a distributed algorithm;
wherein, the step 1) comprises the following steps:
step 11) user input comprises a group of node sets, an edge set, a minimum spanning tree and a failure edge, wherein the node set input by the user is marked as V ═ d1,d2,d3,…,dnH, set of edges E ═ E1,e2,e3,…,emN | V | m | E | each edge E corresponds to a non-negative length l (y), and the path P ═ E |, where<d1,d2,d3,…,dr>Is represented by node d1,d2,d3,…,drForming a path, | P | represents the length of the path, namely the sum of the lengths of all edges, the minimum spanning tree is marked as T, and n refers to the number of nodes in the node set; the m refers to the number of edges in the edge set;
step 12) setting the node set V as { d ═ d1,d2,d3,…,dnAll nodes in the graph model G are regarded as nodes in (V, E);
step 13) regarding a path between the node u and the node V as a graph model G ═ an arc between two nodes (V, E), taking a distance d (u, V) between the two nodes as a weight of the arc between the node u and the node V, wherein d (u, V) is the weight of the shortest circuit between the node u and the node V in the graph model G ═ a (V, E);
step 14) given the minimum spanning tree T ═ (V, e (T)), define D ═ D<d1,d2,d3,…,dk>And | D | is the diameter of the minimum spanning tree T ═ (V, e (T)), i.e. the longest path length in T, defining the central node D of DcDefinition of DL=<d1,d2,d3…dc>Definition of DR=<dc,dc+1,dc+2…dk>And the nodes meet the following conditions: i DL|≥|DRL, D means the distance D from the node in the minimum spanning tree1,d2,d3,…,dkA path formed, said DLRefers to the node d in the minimum spanning tree1,d2,d3,…,dcForm a path, said DRRefers to the minimum spanning tree formed byNode dc,dc+1,dc+2,…,dkForm a path, said | DLI means path DLDiameter of said | DRI means path DRDiameter of (d);
step 15) let dcAs the center of the minimum spanning tree T ═ (V, e (T)), x ∈ V and x ≠ d for each nodecDefining parent node p (x) of node x, defining child node set C (x) of node x, defining Tx=(V(Tx),E(Tx) V) a sub-tree representing the minimum spanning tree T with node x as the root node, and defining VLIs represented by node dc-1For subtrees of the root node, define VRIs represented by node dc+1For subtrees of the root node, define VcRepresents except VL、VRAll other nodes;
step 16) after the user inputs the failure edge e ═ x ', p (x')), the minimum spanning tree T ═ V, e (T)) is divided into two subtrees Tx′And T \ Tx′The said T \ Tx′Excluding node x', the T \ Tx′Means composed of a set of nodes V (T)/V (T)x′) And the edge set E (T)/E (T)x′) In a graph of/{ (x ', p (x ')) }, the task is to find an edge f for the failing edge E ' (x ', p (x ')) to replace the failing edge, where f is any one of E \ E (T) that enables two subtrees Tx′And T \ Tx′The edges to be reconnected together are called exchange edges, S (e ') is defined to represent a set of exchange edges corresponding to the edge e ', and for a failed edge e ' (x ', p (x ')), an optimal exchange edge f ' belongs to S (e '), which means | D (T) of a minimum spanning tree newly generated after the exchange edge is addede′/f′) Where l is minimum, e ═ represents a given failing edge, f ═ represents a swap edge, and z is at TxOne node in (1); the z' is at T \ TxOne node in (b).
2. The method according to claim 1, wherein the step 2) adopts a distributed algorithm to obtain a solution space of the optimal switched edge search problem in the communication network on the graph model G ═ V, E, and specifically comprises the following steps:
step 21) for a given failing edge e '═ x', f (x '), the subtree T rooted at x' is traversedx′Each node z in (a);
step 22) wait for available information from the parent node, calculate | L (T)x′Z) L, while calculating available information for all child nodes and sending that information, the L (T)x′Z) |, means starting with node z and at graph Tx′The length of the longest path in (1);
step 23) for each local exchange edge f ═ z, z', for | L (T \ T)x′Z ') l, the local exchange edge is an edge in the edge set S (e') and adjacent to the node z; the | L (T \ T)x′Z ') is from node z' and at graph T \ Tx′Of the length of the longest path in (b), wherein,
|L(T\Tx′,z′)|=max{d(z′,dk),d(z′,dc)+γ,d(z′,dc)+λ(p(x′)),
d(z′,u′)+d(u′,ρR)+μR-d(dkR)}
d (z', d)k) Means with node z' and node dkAn edge being an end point; d (z', d)c) Means with node z' and node dcAn edge being an end point; d (z ', u') refers to an edge with the node z 'and the node u' as endpoints; the d (u', p)R) Refers to the node u' and the node ρRAn edge being an end point; d (d) iskR) Means with node dkAnd node ρRAn edge being an end point; λ (p (x'))) refers to node dcStarting and entering into the vertex set VLBut does not pass the length of the longest path under node p (x'); u ' is the node closest to z ' on the longest path starting with node z ' on D (T); the rhoRMeans at node dkStarting and at node set VROn the longest path of (1), into VROn the sub-treeA root node of; the gamma is the node dcStarting and containing only a set of nodes VCThe length of the longest path of the middle node; the V isCIs a finger node dcA node set formed by all the other nodes; the muRMeans with node dkStarting and at node set VRThe length of the longest path in (1);
step 24) for each local exchange edge f ═ z, z', pair | D (T)e′/f) L, performing distributed computation: i D (T)e′/f)|=max{|D(T)|,|L(Tx′,z)|+l(f)+|L(T\Tx′Z') | }, said L (T)x′Z) means starting at node z and in graph TxThe length of the longest path in (1); the L (T \ T)x', z ') refers to a graph starting at node z ' and being at T \ TxThe length of the longest path in (1); (f) is the length of the local exchange edge f ═ z, z');
step 25) of selecting a temporary optimal exchange edge from among said local exchange edgesAnd stores the new diameter that will be generated after adding the swap edgeIf no local exchange edge exists, a dummy candidate edge is created and its new diameter is set to ∞;
step 26) for each child node q ∈ C (z), according to the distance information obtained in the above step, selecting an optimal exchange edge candidate for each child nodeAnd stores the new diameter that will be generated after adding the swap edgeThen, the second temporary optimal exchange edge is selected from the optimal exchange edges corresponding to the child nodesThe above-mentioned
Step 27) defining a target optimal exchange edge fbestComparing the first temporary optimal switched edgeAnd a second optimal switching edgeOptionally adding a corresponding exchange edge with smaller diameterThen will beAs a target optimal switched edge fbest(ii) a If it isThen will beAs a target optimal switched edge fbest(ii) a If it isThen will beOrAs a target optimal switched edge fbestAll can be used;
step 28) subtree T if x' is rootx′Is not traversed completely, repeating the steps 22) -22Step 27);
step 29) determining the final solution space SolutionThe solution space includes an optimal swap edge corresponding to the failed edge e ═ x ', f (x')).
CN201610286714.2A 2016-04-29 2016-04-29 A kind of best exchange side lookup method based on minimum spanning tree Active CN105978711B (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201610286714.2A CN105978711B (en) 2016-04-29 2016-04-29 A kind of best exchange side lookup method based on minimum spanning tree

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201610286714.2A CN105978711B (en) 2016-04-29 2016-04-29 A kind of best exchange side lookup method based on minimum spanning tree

Publications (2)

Publication Number Publication Date
CN105978711A CN105978711A (en) 2016-09-28
CN105978711B true CN105978711B (en) 2019-04-19

Family

ID=56994587

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201610286714.2A Active CN105978711B (en) 2016-04-29 2016-04-29 A kind of best exchange side lookup method based on minimum spanning tree

Country Status (1)

Country Link
CN (1) CN105978711B (en)

Families Citing this family (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN106681920B (en) * 2016-12-27 2020-11-03 河南理工大学 Ground distance measurement-based concurrent system model detection method
CN109614978A (en) * 2018-09-29 2019-04-12 阿里巴巴集团控股有限公司 Data processing method, device, equipment and computer readable storage medium
CN109474476B (en) * 2018-12-07 2021-04-30 天津津航计算技术研究所 Wireless sensor network fault recovery system based on minimum spanning tree
CN109474519B (en) * 2018-12-07 2021-04-30 天津津航计算技术研究所 Wireless sensor network fault recovery method based on minimum spanning tree
CN109889440B (en) * 2019-02-20 2021-02-02 哈尔滨工程大学 Erasure code failure node reconstruction path selection method based on maximum spanning tree
CN111131028B (en) * 2019-10-16 2021-09-21 河南工程学院 Inter-domain route recovery method based on minimum spanning tree of degree constraint

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101925100A (en) * 2010-09-03 2010-12-22 东华大学 Fault-tolerant routing recovery method of heterogeneous wireless sensor network
CN103268280A (en) * 2013-04-16 2013-08-28 西安电子科技大学 Distance measurement and statistical analysis combination-based software failure positioning system and method

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN101925100A (en) * 2010-09-03 2010-12-22 东华大学 Fault-tolerant routing recovery method of heterogeneous wireless sensor network
CN103268280A (en) * 2013-04-16 2013-08-28 西安电子科技大学 Distance measurement and statistical analysis combination-based software failure positioning system and method

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
无线Mesh网络恢复方案的一种通用替代路径算法;吕磊,罗惠琼;《中国科技信息》;20070315(第6期);全文
移动自组网的自适应智能路由策略研究;张丽云;《中国优秀硕士学位论文全文数据库 信息科技辑》;20080215(第2期);全文

Also Published As

Publication number Publication date
CN105978711A (en) 2016-09-28

Similar Documents

Publication Publication Date Title
CN105978711B (en) A kind of best exchange side lookup method based on minimum spanning tree
WO2019238109A1 (en) Fault root cause analysis method and apparatus
WO2016078368A1 (en) Community search algorithm based on k-kernel
CN107480694B (en) Weighting selection integration three-branch clustering method adopting two-time evaluation based on Spark platform
CN108038183A (en) Architectural entities recording method, device, server and storage medium
US10191998B1 (en) Methods of data reduction for parallel breadth-first search over graphs of connected data elements
CN109919172A (en) A kind of clustering method and device of multi-source heterogeneous data
Souravlas et al. Probabilistic community detection in social networks
US20200257684A1 (en) Higher-order data sketching for ad-hoc query estimation
US8392393B2 (en) Graph searching
CN109543114A (en) Heterogeneous Information network linking prediction technique, readable storage medium storing program for executing and terminal
Barger et al. k-means for streaming and distributed big sparse data
CN116611527B (en) Quantum circuit processing method and device and electronic equipment
CN108712278A (en) A kind of network community discovery method based on integrated study
WO2023088288A1 (en) Bipartite graph construction method, and display method and apparatus
CN116151381B (en) Quantum circuit processing method and device and electronic equipment
CN116974249A (en) Flexible job shop scheduling method and flexible job shop scheduling device
WO2011016281A2 (en) Information processing device and program for learning bayesian network structure
Ufimtsev et al. An extremely fast algorithm for identifying high closeness centrality vertices in large-scale networks.
CN109522954A (en) Heterogeneous Information network linking prediction meanss
Rashmi et al. A review on overlapping community detection methodologies
CN112579831B (en) Network community discovery method, device and storage medium based on SimRank global matrix smooth convergence
CN111723246B (en) Data processing method, device and storage medium
CN106789285B (en) Online social network multi-scale community discovery method
JP2014229110A (en) Retrieval device, retrieval method and retrieval program

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant