一种多约束电力通信业务最大不相交双路由配置方法

摘要

本发明涉及一种多约束电力通信业务最大不相交双路由配置方法，该方法包括：构建网络拓扑模型；选取r维权值，建立网络Gr；获取网络Gr中请求配置的双路由业务集合，根据实际需求设置业务重要度；按照业务重要度排序，获得当前配置业务信息；通过改进的Bhandari最大不相交算法进行双路由预选取；采用改进的KSP算法获得多组满足多约束条件的最大不相交双路由集合；对所述最大不相交双路由集合进行筛选；输出配置结果。本方法能够在任意电力通信网中为业务分配满足多重约束的最大不相交双路由，最大限度地保障业务正常可靠地运行。

说明书

技术领域

本发明属于电力通信技术领域，涉及一种多约束电力通信业务最大不相交双路由配置方法。

背景技术

电力通信网是服务于电力系统的通信专网，它的通信业务具有高级别的实时性、可靠性和安全性需求。为保障业务安全可靠地运行，电力通信网中部分业务(如继电保护、安全稳定控制等业务)需要配置主备用双路由。当双路由中的主用路由出现故障时，可迅速将业务切换到备用路由，这样可极大程度地减轻突发故障对业务的影响，保障电力通信业务安全可靠地运行。目前电力通信网中的路由算法主要关注单路由分配问题，相关研究主要采用改进的Dijkstra算法、Floyd算法、遗传算法与粒子群算法等方法完成路由的分配工作。但单路由算法无法考虑两条路由间的相互关系，无法为业务配置双路由。

公共通信网中双路由算法主要分为节点不相交双路由算法(NDRA,Node-disjointrouting algorithm)、链路不相交双路由算法(LDRA,Link-disjoint routing algorithm)与最大不相交双路由算法(MDRA,Maximally disjoint routing algorithm)。NDRA要求两路由绝对分离，因此其也被称为不相交双路由算法；LDRA要求两条路由不包含公共链路，与NDRA相比，LDRA的路径约束条件较为松弛；MDRA可为业务分配一组公共节点最少的双路由，在算法间相互的关系上，MDRA包含NDRA。

NDRA要求两条路径绝对分离，在一些特定网络中的特定业务配置中，NDRA无法找到可行解。例如对图2所示网络，分别为A点到Z点和B点到Z点分配双路由，则NDRA均无法实现不相交双路由的分配。LDRA可以为业务配置可能存在多个相交节点的双路由，但这会导致LDRA得到的双路由在可靠性上存在缺陷。例如对图2所示网络，采用LDRA从A点到Z点为业务分配双路由，则图3所示的A-D-E-G-Z和A-C-D-F-H-I-Z与和图4所示的A-D-E-G-Z和A-C-D-F-G-I-Z，均为满足链路不相交条件的双路由。但实际中我们更倾向于选择图3所示公共节点较少的A-D-E-G-Z和A-C-D-F-H-I-Z作为业务主备用路由。进一步地，若采用LDRA从B点到Z点为业务分配双路由，则LDRA无法找到可行解。若采用MDRA分别为A点到Z点与B点到Z点的两条业务分配双路由，则可直接为两条业务分配图3和图4所示具有公共节点最少的双路由。因此，为最大限度地保障电力通信网中业务的可靠性，应采用MDRA完成双路由分配工作。

MDRA仅可以保证两条路由具有最少的公共节点，当网络中存在多组最大不相交双路由时，还应进一步考虑可靠性、丢包率、时延及网络业务的风险均衡等多重约束条件，为业务分配一组满足多重约束条件的最大不相交双路由。在实际的通信网中，多约束双路由算法多为链路不相交双路由算法，且多数算法没有进一步考虑双路由的可靠性与业务风险均衡，这使得现有双路由算法难以满足实际工程的需求。

发明内容

为弥补上述缺陷，本发明提供一种多约束电力通信业务最大不相交双路由配置方法，该方法能够在多重约束条件下寻找多组最大不相交双路由，并为业务分配一组网络风险最均衡的最大不相交双路由。

本发明采取的技术方案是：

一种多约束电力通信业务最大不相交双路由配置方法，所述方法包括下述步骤：

(1)构建网络拓扑模型；

(2)选取r维权值，建立网络G_r；

(3)获取网络G_r中请求配置的双路由业务集合，根据实际需求设置业务重要度；

(4)按照业务重要度排序，获得当前配置业务信息；

(5)通过改进的Bhandari最大不相交算法进行双路由预选取；

(6)采用改进的KSP算法获得多组满足多约束条件的最大不相交双路由集合；

(7)对所述最大不相交双路由集合进行筛选；

(8)输出配置结果。

优选的，所述步骤(1)中构建网络模型包括：依据实际网络架构，构建与该实际网络对应的网络拓扑模型G＝(V,E,W)；

其中，V＝{v₁,v₂,…,v_n}为网络拓扑模型G的节点集合，V中的节点v_i，i∈[1,n]为网络拓扑模型G中第i个节点；E＝{e₁,e₂,…,e_m}为网络拓扑模型G的链路集合，E中的第k个节点e_k＝(v_i,v_j)，k∈[1,m]，表示V中第i个节点v_i和第j个节点v_j的无序对为该网络拓扑中v_i到v_j的链路，j∈[1,n]；n为节点总个数，m为链路总个数，W为网络拓扑模型G中链路与节点的多维权值集合；所述网络拓扑模型G中的第k条链路e_k包含一个q维权值向量W(e_k)＝{w₁(e_k),w₂(e_k),…,w_q(e_k)}，且V中第i个节点v_i包含一个q维权值向量W(v_i)＝{w₁(v_i),w₂(v_i),…,w_q(v_i)}，q＞1。

优选的，所述步骤(2)中选取r维权值，构建网络G_r包括，设置q维权值向量中每一个权值向量的约束条件，根据实际需要选择第r维权值向量的约束条件；其中，所述约束条件包括，可靠性、丢包和时延；

所述第r维权值向量w_r对应的链路和节点的权值分别为w_r(e_k)(1≤r≤q，k∈[1,m])和w_r(v_i)(1≤r≤q，i∈[1,n])，组成网络G_r(V,E)，记为G_r。

优选的，所述步骤(4)包括：将双路由业务集合按照重要度值降序排列；选取其中最重要的业务作为当前配置业务s，获取该业务s的重要度、源点v_s和目的节点v_t信息以及约束向量C(s)。

进一步地，所述约束向量C(s)的获取方法包括：设第k种业务为S_k，k≥0；则在q维约束条件下的约束向量为C(s)＝{c₁(s),c₂(s),…,c_q(s)}。

优选的，所述步骤(5)中通过改进的Bhandari最大不相交算法进行双路由预选取包括，计算当前配置业务s的双路由最大不相交度α_st，即网络G_r中最大不相交双路由Route(A)与Route(B)的公共节点与公共链路的数量和。

进一步地，所述改进的Bhandari最大不相交算法具体包括下述步骤：

5-1在网络G_r中，调用考虑节点权值的Dijkstra算法，获取当前配置业务s的最短路径Route(a)，并将其作为初始路径；

所述考虑节点权值的Dijkstra算法使得Bhandari最大不相交算法可以考虑节点权值；

5-2在网络G_r中，将所述Route(a)进行节点分裂，获取分裂后的节点所对应的链路、节点连接关系和权值，生成新的网络G_rm；

5-3在所述网络G_rm中，调用节点识别的Dijkstra算法，搜索当前配置业务s的源点v_s和目的节点v_t之间的最短路径Route(b₁)；

所述节点识别的Dijkstra算法，用于消除相同节点权值叠加两次而出现错误解；当路径是否抵达某一节点；若抵达，则再次经过时，该节点的权值变为0；

5-4还原Route(b₁)中的分裂节点获得路径Route(b)，其包括：将Route(b₁)中包含的分裂节点还原为原节点，若还原后相邻节点为同一节点则将这两个节点合并；

5-5将Route(a)和Route(b)组成网络G_rs，将G_rs中Route(a)与Route(b)所重合的双向链路与节点的权值分别修改为a₀与b₀，再次执行考虑节点权值的Dijkstra算法，搜索获得最短路径，记为Route(A)；

所述b₀与a₀分别满足不等式b₀>∑w(v_i)+∑w(e_k)和a₀≥n·b₀；其中，b₀大于网络中节点与链路的权值和，n为节点总数。

5-6在网络G_rs中将Route(A)所对应的双向链路与节点的权值分别修改为a₀与b₀，调用考虑节点权值的Dijkstra算法，搜索获得最短路径Route(B)；

根据Route(A)和Route(B)计算双路由最大不相交度α_st，其表达式为：α_st＝card(Route(A)∩Route(B))，并获取Route(A)和Route(B)公共节点权值。

进一步地，所述步骤(5-2)中将Route(a)进行节点分裂包括：定义路径中由源点v_s到目的节点v_t的方向为正向，相反方向为反向；将Route(a)上除起点和终点外的其他点一分为二，二者之间反向链路权值为0，正向链路权值为b₀；

将路径中所有链路的反向权值变为原链路权值的相反数，正向链路权值为a₀；

所述b₀与a₀分别满足不等式b₀>∑w(v_i)+∑w(e_k)，a₀≥n·b₀；其中，b₀大于网络中节点与链路的权值和，n为节点总数。

优选的，所述步骤(6)采用改进的KSP算法获得多组满足多约束的最大不相交双路由集合具体包括：

6-1设初始路径数量为K；

6-2利用KSP算法在网络G_r中逐一搜索源点v_s到目的节点v_t的路径；

设当前路径为第L(1≤L≤K)条路径，在第r维约束条件下的权值向量为w_r(Route(L))；

当w_r(Route(L-1))<c_r(s)≤w_r(Route(L))时，终止计算，转至步骤6-4；

当w_r(Route(K))＜c_r(s)时，转至步骤6-3；其中，c_r(s)为业务s在第r维约束条件下的约束值；

6-3设定阈值增量为ΔK，ΔK＞0；K_N＝K_N-1+ΔK，N＞0；循环步骤(6-1)至步骤(6-3)，对新增的ΔK个路径逐一搜索，直到满足w_r(Route(L-1))<c_r(s)≤w_r(Route(L))进入下一步骤；其中，N的为增加阈值增量的次数；

6-4将任意两个满足约束的路径进行组合，生成多组最大不相交双路由集合；若该集合中每一组双路由Route(x)与Route(y)皆满足：min(Route(x)∩Route(y)-2)＝α_st(1≤x≤K_N,1≤y≤K_N,x≠y)即达到最大不相交度α_st；则进入下一步；

6-5所述多组最大不相交双路由集合中的每一组双路由Route(x)与Route(y)还满足：min(card(Route(x)∩Route(y)))＝min(card(Route(x₁)∩Route(y₁)))(1≤x≤K_N,1≤y≤K_N,x≠y,1≤x₁≤K_N-1,1≤y₁≤K_N-1,x₁≠y₁)，且w_r(Route(K_N))≥max(w_r(Route(A))，w_r(Route(B)))；其中，Route(A)与Route(B)为改进的Bhandari算法获得的最大不相交路径。

优选的，所述步骤(7)对最大不相交双路由集合进行筛选包括，计算双路由集合中每一组双路由的网络业务风险均衡度，获得业务风险最均衡的双路由；并将风险最均衡双路由中跳数较小的一条定义为当前业务s的主用路由MR，另一条为备用路由SR。

进一步地，所述网络业务风险均衡度的计算方法为：

其中，R_G表示网络业务风险均衡度，R_G越小代表网络风险越均衡；m为网络链路数，n为网络节点数；R(e_ij)与R(e)_avr分别表示链路e_ij的业务风险值与网络所有链路的业务风险值均值；R(v_k)与R(v)_avr分别表示节点v_k的业务风险值与网络所有节点的业务风险值均值；S(e_ij)与S(v_k)分别表示链路e_ij与节点v_k所对应的可靠度；SW(s_p)与SW(s_q)分别表示业务s_p与业务s_q的业务重要度；该业务重要度根据实际需要设定；公式s_p∈e_ij表示业务s_p为链路e_ij上所承载的业务，公式s_q∈v_k表示业务s_q为节点v_k上所承载的业务。

所述步骤(8)包括，输出当前配置业务s的双路由结果，更新网络分布，若存在剩余业务则返回步骤(3)。

与最接近的现有技术相比，本发明的有益效果：

本发明可在任意网络中为电力通信业务分配双路由，分配的双路由具有最大不相交特性，能最大程度地降低因公共节点或链路故障而导致主备用路由同时失效的概率；允许设置多种路由约束指标，能够根据发明使用者的不同要求寻找满足不同约束的双路由；在保证每组双路由服务质量的情况下，考虑网络风险均衡因素，可有效降低网络中因业务分布不均衡而导致网络风险过高的状况，使网络负载更加均衡，提高网络资源的利用率。

附图说明

图1是本发明提供的电力通信业务双路由配置流程图；

图2为背景技术提供的某网络的网络拓扑图；

图3为在图2网络中，由A节点向Z节点所分配的相交度为1的链路不相交双路由示意图；

图4为在图2网络中，由A节点向Z节点所分配的相交度为2的链路不相交双路由示意图；

图5为在图2网络中，由B节点向Z节点所分配的最大不相交双路由示意图；

图6为本发明提供的电力通信业务双路由配置详细流程图；

图7为本发明提供的节点分裂变化示意图；

图8为本发明提供的组合网络G_rs拓扑示意图；

图9为本发明提供的修改后的G_rs网络拓扑示意图。

具体实施方式

下面结合附图和具体实施方式对本发明的技术方案作进一步详细地说明。

图1和图6所示，一种多约束电力通信业务最大不相交双路由配置方法，包括：

(1)构建网络拓扑模型；依据实际网络架构，构建与该实际网络对应的网络拓扑模型G＝(V,E,W)；

其中，V＝{v₁,v₂,…,v_n}为网络拓扑模型G的节点集合，V中的节点v_i，i∈[1,n]为网络拓扑模型G中第i个节点；E＝{e₁,e₂,…,e_m}为网络拓扑模型G的链路集合，E中的第k个节点e_k＝(v_i,v_j)，k∈[1,m]，表示V中第i个节点v_i和第j个节点v_j的无序对为该网络拓扑中v_i到v_j的链路，j∈[1,n]；n为节点总个数，m为链路总个数，W为网络拓扑模型G中链路与节点的多维权值集合；所述网络拓扑模型G中的第k条链路e_k包含一个q维权值向量W(e_k)＝{w₁(e_k),w₂(e_k),…,w_q(e_k)}，且V中第i个节点v_i包含一个q维权值向量W(v_i)＝{w₁(v_i),w₂(v_i),…,w_q(v_i)}，q＞1。

(2)选取r维权值，建立网络G_r；选取r维权值，构建网络G_r包括，设置q维权值向量中每一个权值向量的约束条件，根据实际需要选择第r维权值向量的约束条件；其中，所述约束条件包括，可靠性、丢包和时延；

所述第r维权值向量w_r对应的链路和节点的权值分别为w_r(e_k)(1≤r≤q，k∈[1,m])和w_r(v_i)(1≤r≤q，i∈[1,n])，组成网络G_r(V,E)，记为G_r。

(3)获取网络G_r中请求配置的双路由业务集合，根据实际需求设置业务重要度；

(4)按照业务重要度排序，获得当前配置业务信息；

将双路由业务集合按照重要度值降序排列；选取其中最重要的业务作为当前配置业务s，获取该业务s的重要度、源点v_s和目的节点v_t信息以及约束向量C(s)。

所述约束向量C(s)的获取方法包括：设第k种业务为S_k，k≥0；则在q维约束条件下的约束向量为C(s)＝{c₁(s),c₂(s),…,c_q(s)}。

(5)通过改进的Bhandari最大不相交算法进行双路由预选取；

计算当前配置业务s的双路由最大不相交度α_st，即网络G_r中最大不相交双路由Route(A)与Route(B)的公共节点与公共链路的数量和。

所述改进的Bhandari最大不相交算法具体包括下述步骤：

5-1在网络G_r中，调用考虑节点权值的Dijkstra算法，获取当前配置业务s的最短路径Route(a)，并将其作为初始路径；

所述考虑节点权值的Dijkstra算法使得Bhandari最大不相交算法可以考虑节点权值；

5-2在网络G_r中，将所述Route(a)进行节点分裂，获取分裂后的节点所对应的链路、节点连接关系和权值，生成新的网络G_rm；如图7所示，结合为A与Z两个节点分配最大不相交双路由说明Bhandari最大不相交算法流程，在一般网络中，认为链路的正向权值和反向权值相同。通过改进的Dijkstra算法得到最短路径Route(a)：A-B-D-F-H-Z。进行节点分裂得到网络G_rm，此时按照Bhandari算法会存在单向边与正反方向权值不同的边，此时会涉及到正向链路权值与反向链路权值。

步骤(5-2)中将Route(a)进行节点分裂包括：定义路径中由源点v_s到目的节点v_t的方向为正向，相反方向为反向；将Route(a)上除起点和终点外的其他点一分为二，二者之间反向链路权值为0，正向链路权值为b₀；

将路径中所有链路的反向权值变为原链路权值的相反数，正向链路权值为a₀；

所述b₀与a₀分别满足不等式b₀>∑w(v_i)+∑w(e_k)，a₀≥n·b₀；其中，b₀大于网络中节点与链路的权值和，n为节点总数。

5-3在所述网络G_rm中，调用节点识别的Dijkstra算法，搜索当前配置业务s的源点v_s和目的节点v_t之间的最短路径Route(b₁)；

所述节点识别的Dijkstra算法，用于消除相同节点权值叠加两次而出现错误解；当路径是否抵达某一节点；若抵达，则再次经过时，该节点的权值变为0；

5-4还原Route(b₁)中的分裂节点获得路径Route(b)，其包括：将Route(b₁)中包含的分裂节点还原为原节点，若还原后相邻节点为同一节点则将这两个节点合并；

5-5如图8所示，将Route(a)和Route(b)组成网络G_rs，将G_rs中Route(a)与Route(b)所重合的双向链路与节点的权值分别修改为a₀与b₀，再次执行考虑节点权值的Dijkstra算法，搜索获得最短路径，记为Route(A)；如图9所示，此时的网络与节点分裂网络G_rm不同，在G_rs中正反向链路的权值是一样且不会有单向边，因此不会涉及正向与反向问题，直接修改双向链路与节点的权值即可。

通过改进的Dijkstra算法为A点Z点分配路由，得到Route(A)：A-B-C-E-H-Z,在G_rs将Route(A)对应链路权值修改为a₀，节点权值修改为b₀，得到图9所示修改的G_rs网络。

所述b₀与a₀分别满足不等式b₀>∑w(v_i)+∑w(e_k)和a₀≥n·b₀；其中，b₀大于网络中节点与链路的权值和，n为节点总数。

5-6在网络G_rs中将Route(A)所对应的双向链路与节点的权值分别修改为a₀与b₀，调用考虑节点权值的Dijkstra算法，搜索获得最短路径Route(B)；

根据Route(A)和Route(B)计算双路由最大不相交度α_st，其表达式为：α_st＝card(Route(A)∩Route(B))，并获取Route(A)和Route(B)公共节点权值。

6)采用改进的KSP算法获得多组满足多约束条件的最大不相交双路由集合；

具体包括以下步骤：

6-1设初始路径数量为K；

6-2利用KSP算法在网络G_r中逐一搜索源点v_s到目的节点v_t的路径；

设当前路径为第L(1≤L≤K)条路径，在第r维约束条件下的权值向量为w_r(Route(L))；

当w_r(Route(L-1))<c_r(s)≤w_r(Route(L))时，此时算法为精确算法，终止计算转至步骤6-4；

当w_r(Route(K))＜c_r(s)时，转至步骤6-3执行近似算法；其中，c_r(s)为业务s在第r维约束条件下的约束值；

6-3设定阈值增量为ΔK，ΔK＞0；K_N＝K_N-1+ΔK，N＞0；循环步骤(6-1)至步骤(6-3)，对新增的ΔK个路径逐一搜索，直到满足w_r(Route(L-1))<c_r(s)≤w_r(Route(L))进入下一步骤；其中，N的为增加阈值增量的次数；

6-4将任意两个满足约束的路径进行组合，生成多组最大不相交双路由集合；若该集合中每一组双路由Route(x)与Route(y)皆满足：min(Route(x)∩Route(y)-2)＝α_st(1≤x≤K_N,1≤y≤K_N,x≠y)即达到最大不相交度α_st；则进入下一步；

6-5所述多组最大不相交双路由集合中的每一组双路由Route(x)与Route(y)还满足：min(card(Route(x)∩Route(y)))＝min(card(Route(x₁)∩Route(y₁)))(1≤x≤K_N,1≤y≤K_N,x≠y,1≤x₁≤K_N-1,1≤y₁≤K_N-1,x₁≠y₁)，且w_r(Route(K_N))≥max(w_r(Route(A))，w_r(Route(B)))；其中，Route(A)与Route(B)为改进的Bhandari算法获得的最大不相交路径。

(7)对所述最大不相交双路由集合进行筛选：

计算双路由集合中每一组双路由的网络业务风险均衡度，获得业务风险最均衡的双路由；并将风险最均衡双路由中跳数较小的一条定义为当前业务s的主用路由MR(Main route)，另一条为备用路由SR(Spare route)。

所述网络业务风险均衡度的计算方法为：

其中，R_G表示网络业务风险均衡度，R_G越小代表网络风险越均衡；m为网络链路数，n为网络节点数；R(e_ij)与R(e)_avr分别表示链路e_ij的业务风险值与网络所有链路的业务风险值均值；R(v_k)与R(v)_avr分别表示节点v_k的业务风险值与网络所有节点的业务风险值均值；S(e_ij)与S(v_k)分别表示链路e_ij与节点v_k所对应的可靠度；SW(s_p)与SW(s_q)分别表示业务s_p与业务s_q的业务重要度；该业务重要度根据实际需要设定；公式s_p∈e_ij表示业务s_p为链路e_ij上所承载的业务，公式s_q∈v_k表示业务s_q为节点v_k上所承载的业务。

(8)输出配置结果。

输出当前配置业务s的双路由结果，更新网络分布，若存在剩余业务则返回步骤(3)。

本发明中的相关符号含义如表1所示：

表1相关符号说明

最后应当说明的是：以上实施例仅用以说明本申请的技术方案而非对其保护范围的限制，尽管参照上述实施例对本申请进行了详细的说明，所属领域的普通技术人员应当理解：本领域技术人员阅读本申请后依然可对申请的具体实施方式进行种种变更、修改或者等同替换，这些变更、修改或者等同替换，其均在其申请待批的权利要求范围之内。