CN108011817B - Method and system for redeploying power communication private network service route - Google Patents

Abstract

The invention discloses a method for redeploying service routes of a power communication private network. The method includes: acquiring a network topology structure of the power communication private network service routing; Service importance, source point information, destination node information and constraint vector corresponding to the service; arrange the services in the service set affected by the faulty link in descending order according to the service importance; initialize the data; use the improved Dijkstra algorithm to configure The shortest path from the source point to the destination node, and determine the new network topology; add 1 to the number of cycles, and compare the number of cycles with the routing threshold; determine the first shortest path and the alternate path, and calculate each The route intersection degree of the alternate path and the first shortest path; the routes corresponding to each service are arranged in ascending order according to the route intersection degree; the sequence of the paths is determined, and the service distribution is updated.

Description

A method and system for redeploying service routing of power communication private network

technical field

The present invention relates to the field of power communication private network business routing management, and more particularly, to a method and system for redeploying power communication private network business routes.

Background technique

As an important communication component in the power system, the power communication private network mainly provides a guarantee for the stable operation of the power system. Therefore, the reliability of the power communication private network is directly related to the reliability of the power system. For the power communication private network carrying key control services such as stability control and pump storage control, establishing a highly reliable route is an important aspect to ensure the reliability of the power communication private network.

At present, the research on the routing problem of the power communication private network mainly focuses on the theoretical research of the method. Considering the particularity of the power communication system industry, it is necessary to deploy dual routing for some important services that are likely to have a major impact in the event of a failure, such as relay protection and stability control. Considering the randomness of optical fiber and network equipment failures, after a failure occurs on any link, how to quickly switch the services carried on the link to other routes, and ensure the availability of alternative routes and the balance of risks in the entire network sexuality has become an urgent issue. The routing allocation methods for power communication networks in the existing invention patents are all traditional service-oriented routing configuration methods. When routing configuration, some only consider service risk factors, some only consider service QoS constraints, and few combine the two.

In terms of single-route deployment methods, the current routing deployment algorithms in power communication private networks include improved Dijkstra algorithm, Floyd algorithm, particle swarm algorithm, etc. These algorithms are all based on the single-source shortest path algorithm, which can be based on different objective functions. The service is allocated by a single route, but the disadvantage is that it cannot provide an alternative routing scheme for services with multiple constraints.

In the deployment method of dual routing, commonly used methods include RF algorithm and KSP algorithm. The RF algorithm adopts the idea of deleting paths and obtains dual routes based on the Dijkstra algorithm. KSP obtains the top k shortest paths of two points and then filters them. The problem with these methods is that conditions such as network load balancing are not considered.

The above methods are all methods that consider routing deployment from a planning perspective, and do not consider the service redeployment solution in the event of a failure. At the same time, due to the particularity of the power system, it is not allowed to perform operations such as routing configuration directly on the power communication private network. Therefore, it is necessary to simulate the routing of the private power communication network to determine the problem of redeployment of the routing in the private power communication network.

SUMMARY OF THE INVENTION

The present invention provides a method and system for redeploying service routes in a power communication private network, so as to solve the problem of how to determine the redeployment of routes in the power communication private network.

In order to solve the above problems, according to one aspect of the present invention, a method for redeploying service routes of a private power communication network is provided, wherein the method includes:

Step 1: Obtain the network topology structure of the service routing of the power communication private network, and determine the parameter data of the network topology structure, wherein the parameter data includes: the weight value of each node and the weight value of each link;

Step 2, according to the fault information, obtain the service set affected by the faulty link, the service importance corresponding to each service, the source point information, the destination node information and the constraint vector;

Step 3, arranging the services in the service set affected by the faulty link in descending order according to the service importance;

Step 4: Set the routing threshold according to the number of services affected by the faulty link, and set the initial value of the number of cycles to 1;

Step 5, according to the network topology structure, use the improved Dijkstra algorithm to configure the shortest path from the source point to the destination node, establish a backup node according to each intermediate node of the shortest path, determine a new node set, and according to the new node set Determine the new network topology;

Step 6, increase the number of cycles by 1, and compare the number of cycles with the routing threshold, if the number of cycles is less than the routing threshold, return to step 5; otherwise, enter step 7;

Step 7, setting the shortest path corresponding to the current faulty route as the first shortest path, and obtaining other shortest paths as alternate paths, respectively, and calculating the route intersection degree of each alternate path and the first shortest path;

Step 8, arrange the routes corresponding to each service in ascending order according to the degree of intersection of the routes;

Step 9: Calculate the average service risk degree, service risk balance degree and delay value of the entire network in the current network topology structure respectively, and arrange them in ascending order of route intersection degree, shortest path length, service average risk degree, service risk balance degree and delay value. Determine the sequence of alternate paths and update the service distribution.

Preferably, the fault information includes: fault node information and fault link information.

Preferably, a backup node is established according to each intermediate node of the shortest path, a new node set is determined, and a new network topology is determined according to the new node set, including:

Establish a backup node v _i ' according to each intermediate node of the shortest path, determine a new node set V'=V∪{v ₁ ',v ₂ ',...v' _l-1 }, set the node {v _i-1 ,v _i } are connected, the predecessor nodes of v _i that are not on the shortest are connected to each node v' _i , and the arc (v _i-1 ,v _i ) is moved to (v _i-1 ',v _i ), determine the new network topology.

Preferably, the calculating the route intersection degree of each alternate path and the first shortest path includes:

D _IR =D _Intersection (AP∩BP _i ),i=1,2,...k-1,

Among them, D _IR is the route intersection degree; (AP∩BP _i ) is the common node of the shortest path and the i-th alternate path, and k is the number of paths.

Preferably, the average risk degree of the network-wide service includes: the average risk degree corresponding to the node and the average risk degree corresponding to the link, and the calculation formula of the average risk degree of the network-wide service is:

是链路l_ij的失效概；I_m是链路l_ij上所承载业务集合中第m个业务的重要度。Among them, D _ARS is the average risk degree of the whole network service; D _ARS ^t is the average risk degree corresponding to the node t; D _ARS ^Iij is the average risk degree corresponding to the link l _ij ; N is the set of nodes t in the network topology structure; D _t is the node risk degree, which refers to the degree of impact on the business due to the failure of the node equipment, and the sum of the risk degrees of all services carried on each node; D _Iij is the link risk degree, which refers to the degree of impact on the business due to the failure of the link. is the sum of the business risk degrees carried on the links; L is the set of links in the network topology; l _ij is a link from node i to node j, l _ij ∈ L, i, j∈N ; P _t is the failure probability of node t; Im is the importance of the _mth service in the set of services carried on node t;

is the failure probability of the link l _ij ; Im is the importance of the _mth service in the set of services carried on the link l _ij .

Preferably, the calculation formula of the risk balance degree of the whole network service is:

表示链路l_ij的风险度；D_t是节点t的风险度。Among them, D _BRS is the business risk balance of the whole network;

represents the risk degree of the link l _ij ; D _t is the risk degree of the node t.

According to another aspect of the present invention, there is provided a system for redeploying service routes of a private power communication network, wherein the system includes:

A parameter data determination unit, configured to acquire the network topology structure of the service routing of the power communication private network, and determine the parameter data of the network topology structure, wherein the parameter data includes: the weight value of each node and the weight of each link value;

a service set data determination unit, configured to obtain the service set affected by the faulty link, the service importance corresponding to each service, the source point information, the destination node information and the constraint vector according to the fault information;

a first sorting unit, configured to sort the services in the service set affected by the faulty link in descending order according to the service importance;

The routing threshold setting unit is used to set the routing threshold according to the number of services affected by the faulty link, and set the initial value of the number of cycles to 1;

The new network topology determination unit is configured to use the improved Dijkstra algorithm to configure the shortest path from the source point to the destination node according to the network topology structure, establish a backup node according to each intermediate node of the shortest path, and determine a new node set, and determine the new network topology according to the new node set;

A comparison unit, for adding 1 to the number of cycles, and comparing the number of cycles with the routing threshold, if the number of cycles is less than the routing threshold, the new network topology determines the unit; otherwise, enter the routing intersection degree calculation unit;

The route intersection degree calculation unit is used to set the shortest path corresponding to the current faulty route as the first shortest path, and the other shortest paths obtained are respectively backup paths, and calculate the route intersection degree of each backup path and the first shortest path respectively. ;

The second sorting unit is used to arrange the routes corresponding to each service in ascending order according to the degree of intersection of the routes;

The path determination unit is used to calculate the average risk degree, service risk balance degree and delay value of the entire network service in the current network topology structure, and calculate the average service risk degree, service risk balance degree and delay value according to the route intersection degree, shortest path length, service average risk degree, service risk balance degree and The ascending order of delay determines the order of alternate paths and updates the service distribution.

Preferably, the fault information includes: fault node information and fault link information.

Preferably, wherein the new network topology determination unit establishes a backup node according to each intermediate node of the shortest path, determines a new node set, and determines a new network topology structure according to the new node set, including:

Establish a backup node v _i ' according to each intermediate node of the shortest path, determine a new node set V'=V∪{v ₁ ',v ₂ ',...v' _l-1 }, set the node {v _i-1 ,v _i } are connected, the predecessor nodes of v _i that are not on the shortest are connected to each node v' _i , and the arc (v _i-1 ,v _i ) is moved to (v _i-1 ',v _i ), determine the new network topology.

Preferably, wherein the route intersection degree calculation unit calculates the route intersection degree of each alternate path and the first shortest path, including:

D _IR =D _Intersection (AP∩BP _i ),i=1,2,...k-1,

Among them, D _IR is the route intersection degree; (AP∩BP _i ) is the common node of the shortest path and the i-th alternate path, and k is the number of alternate paths.

Preferably, the average risk degree of the network-wide service includes: the average risk degree corresponding to the node and the average risk degree corresponding to the link, and the calculation formula of the average risk degree of the network-wide service is:

是链路l_ij的失效概；I_m是链路l_ij上所承载业务集合中第m个业务的重要度。Among them, D _ARS is the average risk degree of the whole network service; D _ARS ^t is the average risk degree corresponding to the node t; D _ARS ^Iij is the average risk degree corresponding to the link l _ij ; N is the set of nodes t in the network topology structure; D _t is the node risk degree, which refers to the degree of impact on the business due to the failure of the node equipment, and the sum of the risk degrees of all services carried on each node; D _Iij is the link risk degree, which refers to the degree of impact on the business due to the failure of the link. is the sum of the business risk degrees carried on the links; L is the set of links in the network topology; l _ij is a link from node i to node j, l _ij ∈ L, i, j∈N ; P _t is the failure probability of node t; Im is the importance of the _mth service in the set of services carried on node t;

is the failure probability of the link l _ij ; Im is the importance of the _mth service in the set of services carried on the link l _ij .

Preferably, the calculation formula of the risk balance degree of the whole network service is:

表示链路l_ij的风险度；D_t是节点t的风险度。Among them, D _BRS is the business risk balance of the whole network;

represents the risk degree of the link l _ij ; D _t is the risk degree of the node t.

The method and system for redeploying the service routing of the power communication private network provided by the present invention firstly clarify the simulation scene and process of redeploying the power communication private network service, and then find the source and destination nodes in the network by improving the KSP algorithm. Multiple shortest routing groups that satisfy multiple constraints; finally, multiple routing schemes are determined according to the evaluation indicators such as routing intersection, shortest path, delay, average risk degree of the entire network service, and risk balance degree, and the one with all the approximate minimum values is selected. The group is the optimal routing scheme, so that all risk-differentiated services carried on the faulty route can be quickly switched to the link corresponding to the optimal scheme at the same time, reducing the waiting time for service recovery, improving the transmission efficiency, and ensuring the power communication system. reliability.

Description of drawings

Exemplary embodiments of the present invention may be more fully understood by reference to the following drawings:

FIG. 1 is a flowchart of a method 100 for redeploying service routes of a private power communication network according to an embodiment of the present invention;

2 is a schematic diagram of a simulated network topology according to an embodiment of the present invention; and

FIG. 3 is a schematic structural diagram of a system 300 for redeploying service routes of a private power communication network according to an embodiment of the present invention.

Detailed ways

Exemplary embodiments of the present invention will now be described with reference to the accompanying drawings, however, the present invention may be embodied in many different forms and is not limited to the embodiments described herein, which are provided for the purpose of this thorough and complete disclosure invention, and fully convey the scope of the invention to those skilled in the art. The terms used in the exemplary embodiments shown in the drawings are not intended to limit the invention. In the drawings, the same elements/elements are given the same reference numerals.

Unless otherwise defined, terms (including scientific and technical terms) used herein have the commonly understood meanings to those skilled in the art. In addition, it is to be understood that terms defined in commonly used dictionaries should be construed as having meanings consistent with the context in the related art, and should not be construed as idealized or overly formal meanings.

FIG. 1 is a flowchart of a method 100 for redeploying service routes of a private power communication network according to an embodiment of the present invention. As shown in FIG. 1 , the method for redeploying service routes of a private power communication network according to an embodiment of the present invention first defines the simulation scenario and process of redeploying services of a private power communication network, and then by improving the KSP algorithm, it is the source point in the network. and the destination node to find multiple shortest routing groups that satisfy multiple constraints; finally, multiple routing schemes are determined according to the evaluation indicators such as routing intersection, shortest path, delay, average risk degree and risk balance degree of the whole network service, and all values are selected from them. The group with the smallest approximate is the optimal routing scheme, so that all risk-differentiated services carried on the faulty route can be quickly switched to the link corresponding to the optimal scheme at the same time, reducing the waiting time for service recovery, improving transmission efficiency, and ensuring reliability of the power communication system. The method 100 for redeploying service routes of a private power communication network according to the embodiment of the present invention starts from step 101. In step 101, the network topology structure of the service routes of the private power communication network is obtained, and the parameter data of the network topology structure is determined. , wherein the parameter data includes: the weight value of each node and the weight value of each link.

In the embodiment of the present invention, the simulation process of the redeployment of the power communication private network service mainly includes several processes: data source acquisition, simulation triggering, simulation execution, and simulation result output. In the data acquisition stage, the network resources and configuration parameter information required by the service redeployment simulation are acquired in various ways. The data acquisition source can be the interface of the network management system or the offline data file. The data and definitions that need to be obtained include:

G is a schematic diagram of the network topology of service routing in the power communication transfer network, which is an abstraction of the physical structure of the network; N is a collection of network nodes, which is an abstraction of switching equipment installed in factories, stations, dispatch centers, etc.; L is the network chain A set of paths; R is a set of constraints; l _ij is a link from node i to node j, l _ij ∈ L, i, j ∈ N; D _i is the node risk degree, which refers to the The degree of influence of the failure on the business, and the sum of all business risk degrees carried on each node. The formula for calculating node risk is:

Among them, P _t is the failure probability of node t, which is derived from operation and maintenance data, and Im is the importance of the _mth service in the set of services carried on node t, which can be set in the system.

为链路风险度是指由于链路失效对业务的影响程度，用每条链路上所承载的业务风险度值来衡量。链路风险度的计算公式是：

The risk degree of the link refers to the degree of influence on the service due to the failure of the link, which is measured by the service risk degree value carried on each link. The formula for calculating link risk is:

是链路l_ij的失效概率，通过系统获取，I_m是链路l_ij上所承载业务集合中第m个业务的重要度。in,

is the failure probability of the link l _ij , obtained through the system, and Im is the importance of the _mth service in the set of services carried on the link l _ij .

Preferably, in step 102, the set of services affected by the faulty link, the service importance corresponding to each service, the source point information, the destination node information and the constraint vector are obtained according to the fault information.

Preferably, the fault information includes: fault node information and fault link information.

In the embodiment of the present invention, the simulation trigger is the data of the basic network topology. By selecting a link or node on the topology map and setting it to a faulty state, the network topology displays the faulty link and the affected service, and prompts for a restart. Deployment simulation triggers. After the simulation is triggered, in the simulation execution stage, according to the acquired data, for the service carried on the faulty link, the service redeployment is implemented according to the routing method of service redeployment.

Preferably, in step 103, the services in the service set affected by the faulty link are arranged in descending order according to the service importance.

Preferably, in step 104, the routing threshold is set according to the number of services affected by the faulty link, and the initial value of the number of cycles is set to 1. For example, if the number of affected services is 5, k0 can be set to 7.

Preferably, in step 105, according to the network topology structure, use the improved Dijkstra algorithm to configure the shortest path from the source point to the destination node, establish a backup node according to each intermediate node of the shortest path, determine a new node set, and A new network topology is determined according to the new set of nodes.

Preferably, a backup node is established according to each intermediate node of the shortest path, a new node set is determined, and a new network topology is determined according to the new node set, including:

Establish a backup node v _i ' according to each intermediate node of the shortest path, determine a new node set V'=V∪{v ₁ ',v ₂ ',...v' _l-1 }, set the node {v _i-1 ,v _i } are connected, the predecessor nodes of v _i that are not on the shortest are connected to each node v' _i , and the arc (v _i-1 ,v _i ) is moved to (v _i-1 ',v _i ), determine the new network topology.

Preferably, in step 106, the number of cycles is increased by 1, and the number of cycles is compared with the routing threshold. If the number of cycles is less than the routing threshold, return to step 105; otherwise, go to step 107.

Preferably, in step 107, the shortest path corresponding to the current faulty route is set as the first shortest path, the other shortest paths obtained are respectively backup paths, and the route intersection degree of each backup path and the first shortest path is calculated respectively.

Preferably, the calculating the route intersection degree of each alternate path and the first shortest path includes:

D _IR =D _Intersection (AP∩BP _i ),i=1,2,...k-1,

Among them, D _IR is the route intersection degree; (AP∩BP _i ) is the common node of the shortest path and the i-th alternate path, and k is the number of alternate paths.

Preferably, in step 108, the routes corresponding to each service are arranged in ascending order according to the degree of intersection of the routes.

Preferably, in step 109, the average service risk, service risk balance, and delay value of the entire network in the current network topology are calculated respectively, and the average service risk, service risk balance, and service risk balance are calculated according to the route intersection, the shortest path length, the service average risk, and the service risk balance. and delay ascending order to determine the order of the alternate paths, and update the service distribution.

Preferably, the average risk degree of the network-wide service includes: the average risk degree corresponding to the node and the average risk degree corresponding to the link, and the calculation formula of the average risk degree of the network-wide service is:

是链路l_ij的失效概；I_m是链路l_ij上所承载业务集合中第m个业务的重要度。Among them, D _ARS is the average risk degree of the whole network service; D _ARS ^t is the average risk degree corresponding to the node t; D _ARS ^Iij is the average risk degree corresponding to the link l _ij ; N is the set of nodes t in the network topology structure; D _t is the node risk degree, which refers to the degree of impact on the business due to the failure of the node equipment, and the sum of the risk degrees of all services carried on each node; D _Iij is the link risk degree, which refers to the degree of impact on the business due to the failure of the link. is the sum of the business risk degrees carried on the links; L is the set of links in the network topology; l _ij is a link from node i to node j, l _ij ∈ L, i, j∈N ; P _t is the failure probability of node t; Im is the importance of the _mth service in the set of services carried on node t;

is the failure probability of the link l _ij ; Im is the importance of the _mth service in the set of services carried on the link l _ij .

Preferably, the calculation formula of the risk balance degree of the whole network service is:

表示链路l_ij的风险度；D_t是节点t的风险度。Among them, D _BRS is the business risk balance of the whole network;

represents the risk degree of the link l _ij ; D _t is the risk degree of the node t.

In the embodiment of the present invention, when redeploying power communication private network services, first establish the following redeployment routing mathematical model:

The objective function is: min(D _IR ), min(D _ARS ), min(D _BRS ),

The constraints are:

Among them, min(D _IR ), min(D _ARS ), and min(D _BRS ) in the objective function represent the minimum intersection degree of any two routes, business average risk degree and business risk balance degree, respectively.

D _ARS is the degree on Average Risk of service of the entire network. It consists of two parts: the average risk corresponding to node t and the average risk corresponding to link I _ij . The calculation formula is:

D _BRS is the Degree on Balancing Risk of Service of the entire network, and the calculation formula is:

表示链路l_ij的风险度；D_t是节点t的风险度。Among them, D _BRS is the business risk balance of the whole network;

represents the risk degree of the link l _ij ; D _t is the risk degree of the node t.

D _IR is the degree on Intersection Routing, which indicates the number of common elements (nodes or links) in the two routes. Assuming that there are k (k≥2) maximum disjoint routes, select one of them as the main switching route, denoted as AP, and the other as backup routes, denoted as BP ₁ , BP ₂ , ... BP _k-1 , the calculation formula is: D _IR =D _Intersection (AP∩BP _i ), i=1,2,...k-1.

In order to simplify the problem, the QoS constraint mainly considers the shortest distance and delay of the additive constraint, because the multiplicative constraint can be converted into an additive constraint by taking the negative logarithm, and other constraints can be preprocessed at the beginning, and R _i is corresponding to each Constraint threshold.

In the configuration of redeployment of power communication private network service routing based on reliability, according to the characteristics of the objective function and constraint conditions, the improved KSP algorithm can be used to obtain k paths at a time, and all services on the faulty link can be calculated. In order to improve the transmission efficiency of services and ensure the reliability of the system, the strategy we adopted is to perform routing switching for all services at the same time. The specific algorithm is as follows:

Initialize the network G(N,L,W) information, input the weight matrix W(n _i )={w ₁ (n _i ),w ₂ (n _i )} of the nodes in the network and the weight matrix W( l _j )={w ₁ (l _j ),w ₂ (l _j )};

Enter the service distribution set S _m affected by the faulty node on the network and the corresponding constraint vector:

R(S _m )={r ₁ (S _m ),r ₂ (S _m )};

Obtain the service distribution set Sf affected by the faulty link, the corresponding service importance, the source point information and destination node information, and the constraint vector R(S _f )={r ₁ (S _f ), r ₂ ( S _f )};

Arrange the business in Sf in descending order of importance;

Set the routing threshold k0 according to the number of services f affected by the faulty link, and initialize the number of cycles k to 1;

Call the improved Dijkstra algorithm in the network topology graph G to configure the first shortest path AP from the source point to the destination node;

Create a backup node v _i ' for each intermediate node v _i (1<i<l) of the path AP, and generate a new node set V'=V∪{v ₁ ',v ₂ ',...v' _{l- 1} } Connect the nodes {v _i-1 ,v _i }, connect the predecessor nodes of v _i that are not on the path p to each node v' _i , move the arc (v _i-1 ,v _i ) to ( v _i-1 ',v _i ), get a new graph G';

In the new graph G', set k=k+1, if k<k0, return to call the improved Dijkstra algorithm to configure the first shortest path AP step from the source point to the destination node, calculate the first k shortest paths, otherwise continue ;

Assuming that the current faulty route is the first shortest path AP, set the remaining k-1 paths as BP ₁ , BP ₂ ... BP _k-1 in turn, and calculate the intersection degree of AP and BP _k-1 ;

Arrange each service in the service set S _f (0≤f≤k) in ascending order of route intersection, and determine f routes;

Calculate the average service risk D _ARS of the entire network, the business risk balance D _BRS and the delay value in the network at this time; according to the intersection degree, the shortest path length, the business average risk D _ARS and the business risk balance D _BRS and the delay value are determined in ascending order Approximate optimal path scheme Pk1 and alternate path schemes Pk2, Pk3...Pkf, output Pk1, and update the service distribution in the network.

In order to verify the effectiveness of the method proposed in this patent, the simulation of the existing power communication private network is carried out. FIG. 2 is a schematic diagram of a simulated network topology according to an embodiment of the present invention. As shown in Figure 2, there are 8 nodes and 12 links (optical cables). The failure probability of the node is randomly generated within [0.0001 0.001], and the failure probability of the link is randomly generated within [0.0010.01]. The service distribution in the network at a certain moment is shown in Table 1. The information of the shortest path group composed of the first four shortest paths is calculated by using the improved KSP algorithm, as shown in Table 2 below.

Table 1 Service distribution in the network

Table 2 The shortest path group information calculated by the improved KSP algorithm

Assuming that the l4 link in the network fails at a certain moment, the services carried on the AP path are switched to other shortest paths according to the improved KSP algorithm. The configuration results are shown in Table 3.

Table 3 Configuration result table

According to the importance of the business, the most important business should choose the route with the smallest intersection with the original route as much as possible. At the same time, the average risk degree, risk balance degree and QoS constraint of the corresponding business are also approximately the smallest. Scheme 2 is the optimal scheme, and the others are backup schemes.

FIG. 3 is a schematic structural diagram of a system 300 for redeploying service routes of a private power communication network according to an embodiment of the present invention. As shown in FIG. 3 , the system 300 for redeploying service routes of a private power communication network according to an embodiment of the present invention includes: a parameter data determination unit 301 , a service set data determination unit 302 , a first sorting unit 303 , and a routing threshold setting unit 304 , a new network topology structure determination unit 305 , a comparison unit 306 , a route intersection degree calculation unit 307 , a second sorting unit 308 and a path determination unit 309 .

Preferably, in the parameter data determination unit 301, the network topology structure of the service routing of the power communication private network is obtained, and the parameter data of the network topology structure is determined, wherein the parameter data includes: the weight value of each node and the value of each chain Road weight value.

Preferably, in the service set data determination unit 302, the service set affected by the faulty link, the service importance corresponding to each service, the source point information, the destination node information and the constraint vector are obtained according to the fault information. Preferably, the fault information includes: fault node information and fault link information.

Preferably, in the first sorting unit 303, the services in the service set affected by the faulty link are sorted in descending order according to the service importance.

Preferably, in the routing threshold setting unit 304, the routing threshold is set according to the number of services affected by the faulty link, and the initial value of the number of cycles is set to 1.

Preferably, in the new network topology structure determining unit 305, according to the network topology structure, use the improved Dijkstra algorithm to configure the shortest path from the source point to the destination node, and establish a backup node according to each intermediate node of the shortest path, A new node set is determined, and a new network topology is determined according to the new node set.

Preferably, the new network topology determining unit 305 establishes a backup node according to each intermediate node of the shortest path, determines a new node set, and determines a new network topology structure according to the new node set, including:

Establish a backup node v _i ' according to each intermediate node of the shortest path, determine a new node set V'=V∪{v ₁ ',v ₂ ',...v' _l-1 }, set the node {v _i-1 ,v _i } are connected, the predecessor nodes of v _i that are not on the shortest are connected to each node v' _i , and the arc (v _i-1 ,v _i ) is moved to (v _i-1 ',v _i ), determine the new network topology.

Preferably, in the comparison unit 306, the number of cycles is increased by 1, and the number of cycles is compared with the routing threshold, if the number of cycles is less than the routing threshold, a new network topology structure determination unit; otherwise, enter the routing intersection degree calculation unit .

Preferably, in the route intersection degree calculation unit 307, the shortest path corresponding to the current faulty route is set as the first shortest path, the other shortest paths obtained are respectively backup paths, and the difference between each backup path and the first shortest path is calculated respectively. Route intersection degree.

Preferably, wherein the route intersection degree calculation unit 307 calculates the route intersection degree of each alternate path and the first shortest path, including:

D _IR =D _Intersection (AP∩BP _i ),i=1,2,...k-1,

Among them, D _IR is the route intersection degree; (AP∩BP _i ) is the common node of the shortest path and the i-th alternate path, and k is the number of alternate paths.

Preferably, in the second sorting unit 308, the routes corresponding to each service are sorted in ascending order according to the degree of intersection of the routes.

Preferably, in the path determination unit 309, the average risk degree of the entire network service, the service risk balance degree and the delay value in the current network topology structure are calculated respectively, and the average service risk degree, service risk Equilibrium and delay ascending order determine the order of alternate paths, and update service distribution.

Preferably, the average risk degree of the network-wide service includes: the average risk degree corresponding to the node and the average risk degree corresponding to the link, and the calculation formula of the average risk degree of the network-wide service is:

是链路l_ij的失效概；I_m是链路l_ij上所承载业务集合中第m个业务的重要度。Among them, D _ARS is the average risk degree of the whole network service; D _ARS ^t is the average risk degree corresponding to the node t; D _ARS ^Iij is the average risk degree corresponding to the link l _ij ; N is the set of nodes t in the network topology structure; D _t is the node risk degree, which refers to the degree of impact on the business due to the failure of the node equipment, and the sum of the risk degrees of all services carried on each node; D _Iij is the link risk degree, which refers to the degree of impact on the business due to the failure of the link. is the sum of the business risk degrees carried on the links; L is the set of links in the network topology; l _ij is a link from node i to node j, l _ij ∈ L, i, j∈N ; P _t is the failure probability of node t; Im is the importance of the _mth service in the set of services carried on node t;

is the failure probability of the link l _ij ; Im is the importance of the _mth service in the set of services carried on the link l _ij .

Preferably, the calculation formula of the risk balance degree of the whole network service is:

表示链路l_ij的风险度；D_t是节点t的风险度。Among them, D _BRS is the business risk balance of the whole network;

represents the risk degree of the link l _ij ; D _t is the risk degree of the node t.

The system 300 for redeploying service routes of a private power communication network according to the embodiment of the present invention corresponds to the method 100 for redeploying service routes of a private power communication network according to another embodiment of the present invention, and details are not described herein again.

The present invention has been described with reference to a few embodiments. However, as is known to those skilled in the art, other embodiments than the above disclosed invention are equally within the scope of the invention, as defined by the appended patent claims.

Generally, all terms used in the claims are to be interpreted according to their ordinary meaning in the technical field, unless explicitly defined otherwise herein. All references to "a/the/the [means, component, etc.]" are open to interpretation as at least one instance of said means, component, etc., unless expressly stated otherwise. The steps of any method disclosed herein do not have to be performed in the exact order disclosed, unless explicitly stated.

Claims (6)

1. A method for redeploying service routing of a power communication private network is characterized by comprising the following steps:

step 1, acquiring a network topology structure of a power communication private network service route, and determining parameter data of the network topology structure, wherein the parameter data comprises: a weight value for each node and a weight value for each link;

step 2, acquiring a service set influenced by a fault link, corresponding service importance, source point information, destination node information and a constraint vector under a constraint condition according to the fault information;

step 3, arranging the services in the service set influenced by the fault link in a descending order according to the service importance;

step 4, setting a routing threshold according to the number of services influenced by the fault link, and setting an initial value of the cycle number to be 1;

step 5, according to the network topological structure, utilizing an improved Dijkstra algorithm of DixTel to configure a shortest path from a source node to a destination node, establishing a backup node according to each intermediate node of the shortest path, determining a new node set, and determining a new network topological structure according to the new node set;

step 6, adding 1 to the cycle number, comparing the cycle number with a routing threshold value, and returning to the step 5 if the cycle number is smaller than the routing threshold value; otherwise, entering step 7;

step 7, setting the shortest path corresponding to the current fault route as a first shortest path, respectively taking the other shortest paths as standby paths, and respectively calculating the route intersection degree of each standby path and the first shortest path;

8, arranging the routes corresponding to each service in an ascending order according to the route intersection degree;

step 9, respectively calculating the average risk degree, the average risk degree and the time delay value of the whole network service in each new network topology structure, determining an approximate optimal path scheme and a standby path scheme according to the ascending sequence of the route intersection degree, the shortest path length, the average risk degree and the time delay of the whole network service, the average risk degree and the time delay value of the whole network service, outputting the approximate optimal path scheme, and updating service distribution;

wherein the calculating the route intersection degree of each backup path and the first shortest path comprises:

D_IR＝D_Intersection(AP∩BP_i),i＝1,2,...k-1，

wherein D is_IRRepresenting the number of common nodes in two routes for the intersection degree of the routes; (AP. andgate BP_i) K is the number of the standby paths;

the average risk degree of the whole network service comprises the following steps: the average risk degree corresponding to the node and the average risk degree corresponding to the link, wherein the calculation formula of the average risk degree of the whole network service is as follows:

wherein D is_ARSThe average risk degree of the whole network service is obtained; d_ARS ^tThe average risk degree corresponding to the node t; d_ARS ^IijIs a link l_ijA corresponding average risk; n is a set of nodes t in the network topology structure; d_tThe node risk degree is the sum of the risk degrees of all the services borne by each node due to the influence degree of the node equipment failure on the services; d_IijThe link risk degree refers to the influence degree of the link failure on the service and the sum of the service risk degrees borne by each link; l is a set of links in the network topology; l_ijFor a link from node i to node j, l_ij∈L，i,j∈N；P_tIs the failure probability of node t; i is_mThe importance of the mth service in the service set carried on the node t is determined;

is a link l_ijThe failure probability of (2); i is_mIs a link l_ijThe importance of the mth service in the loaded service set;

the calculation formula of the risk balance degree of the whole network service is as follows:

wherein D is_BRSThe risk balance degree of the whole network service is obtained;

represents a link l_ijThe risk level of (c); d_tIs the risk of node t.

2. The method of claim 1, wherein the fault information comprises: failed node information and failed link information.

3. The method of claim 1, wherein establishing a backup node from each intermediate node of the shortest path, determining a new set of nodes, and determining a new network topology from the new set of nodes comprises: establishing a backup node v according to each intermediate node of the shortest path_i', determining a new node set V' ═ VU { V₁',v₂',...v'_l-1} node { v_i-1,v_iConnect v to each other_iAnd v 'of each node'_iAre connected to each other, arc (v)_i-1,v_i) Move to (v)_i-1',v_i) And determining a new network topology.

4. A system for redeploying power communication private network service routes, the system comprising:

the device comprises a parameter data determining unit, a parameter data determining unit and a processing unit, wherein the parameter data determining unit is used for acquiring a network topology structure of a power communication private network service route and determining parameter data of the network topology structure, and the parameter data comprises: a weight value for each node and a weight value for each link;

the service set data determining unit is used for acquiring a service set influenced by a fault link, corresponding service importance, source point information, destination node information and a constraint vector under a constraint condition according to the fault information;

the first sequencing unit is used for carrying out descending sequencing on the services in the service set influenced by the fault link according to the service importance;

a routing threshold setting unit, configured to set a routing threshold according to the number of services affected by the failed link, and set an initial value of the cycle number to 1;

a new network topology structure determining unit, configured to configure a shortest path from a source point to a destination node according to the network topology structure by using an improved Dijkstra algorithm, establish a backup node according to each intermediate node of the shortest path, determine a new node set, and determine a new network topology structure according to the new node set;

the comparison unit is used for adding 1 to the cycle number, comparing the cycle number with a routing threshold value, and determining a new network topology structure if the cycle number is smaller than the routing threshold value; otherwise, entering a route intersection calculation unit;

the route intersection calculation unit is used for setting the shortest path corresponding to the current fault route as a first shortest path, respectively using the obtained other shortest paths as standby paths, and respectively calculating the route intersection of each standby path and the first shortest path;

the second sorting unit is used for carrying out ascending sorting on the route corresponding to each service according to the route intersection degree;

the path determining unit is used for respectively calculating the average risk degree, the average risk degree and the time delay value of the whole network service in each new network topology structure, determining an approximate optimal path scheme and a standby path scheme according to the ascending sequence of the route intersection degree, the shortest path length, the average risk degree of the whole network service, the average risk degree and the time delay value of the whole network service, outputting the approximate optimal path scheme and updating the service distribution;

wherein, the route intersection calculation unit calculates the route intersection of each backup path and the first shortest path, and includes:

D_IR＝D_Intersection(AP∩BP_i),i＝1,2,...k-1，

wherein D is_IRRepresenting the number of common nodes in two routes for the intersection degree of the routes; (AP. andgate BP_i) K is the number of the standby paths;

the average risk degree of the whole network service comprises the following steps: the average risk degree corresponding to the node and the average risk degree corresponding to the link, wherein the calculation formula of the average risk degree of the whole network service is as follows:

wherein D is_ARSThe average risk degree of the whole network service is obtained; d_ARS ^tThe average risk degree corresponding to the node t; d_ARS ^lijIs a link l_ijA corresponding average risk; n is a set of nodes t in the network topology structure; d_tThe node risk degree is the sum of the risk degrees of all the services borne by each node due to the influence degree of the node equipment failure on the services; d_lijThe link risk degree refers to the influence degree of the link failure on the service and the sum of the service risk degrees borne by each link; l is a set of links in the network topology; l_ijFor a link from node i to node j, l_ij∈L，i,j∈N；P_tIs the failure probability of node t; i is_mThe importance of the mth service in the service set carried on the node t is determined;

is a link l_ijThe failure probability of (2); i is_mIs a link l_ijThe importance of the mth service in the loaded service set;

the calculation formula of the risk balance degree of the whole network service is as follows:

wherein D is_BRSThe risk balance degree of the whole network service is obtained;

represents a link l_ijThe risk level of (c); d_tIs the risk of node t.

5. The system of claim 4, wherein the fault information comprises: failed node information and failed link information.

6. The system of claim 4, wherein the new network topology determining unit, which establishes a backup node according to each intermediate node of the shortest path, determines a new node set, and determines a new network topology according to the new node set, comprises:

establishing a backup node v according to each intermediate node of the shortest path_i', determining a new node set V' ═ VU { V₁',v₂',...v'_l-1} node { v_i-1,v_iConnect v to each other_iIs not on the shortest route from the predecessor node to each node v'_iAre connected to each other, arc (v)_i-1,v_i) Move to (v)_i-1',v_i) And determining a new network topology.

Images