何玉鈞，陳 冉，張文正，劉 毅，周生平

?

一種電力通信網最大不相交雙路由配置方法

何玉鈞，陳 冉，張文正，劉 毅，周生平

(華北電力大學電子與通信工程系，河北 保定 071000)

針對現(xiàn)有電力通信網路由算法不能為業(yè)務分配雙路由的問題，提出一種最可靠環(huán)路策略下的最大不相交雙路由算法(the maximally disjoint routing algorithm under the most reliable loop strategy, MRMLS)。研究了公共通信網中三種類型的雙路由算法，考慮了雙路由算法可能面臨的網絡結構，闡述了采用最大不相交雙路由算法的必要性。分析了最大不相交雙路由的可靠性，并采用最可靠環(huán)路策略完成最大不相交雙路由的分配工作。改進了原有最大不相交雙路由算法，使所提算法充分考慮節(jié)點與鏈路的可靠性。仿真實驗將MRMLS與其他兩種方法進行對比，驗證了MRMLS的可行性與有效性。

電力通信網；雙路由；最大不相交；可靠性；最可靠環(huán)路

0 引言

電力通信網是服務于電力系統(tǒng)的通信專網，它的通信業(yè)務具有高級別的可靠性需求[1]。為保障業(yè)務安全可靠地運行，電力通信網中部分業(yè)務需要配置主備用雙路由，例如：線路繼電保護業(yè)務、安全穩(wěn)定控制等業(yè)務具有高級別的安全等級，通常需要配置雙路由[2]。雙路由的配置可以極大地提高業(yè)務的可靠性，當主用路由出現(xiàn)故障時，可迅速將業(yè)務切換到備用路由，提高業(yè)務應對突發(fā)事件的能力，保障通信業(yè)務安全可靠地運行[3]。目前電力通信網的路由算法主要關注單路由分配問題，相關研究主要采用改進的Dijkstra算法[2]、Floyd算法[4]、K- shortest paths算法[5]、遺傳算法[6-7]與粒子群算法[8-9]等方法完成路由分配工作。但單路由算法無法考慮兩條路由間的相互關系，無法為業(yè)務配置雙路由。

按兩條路徑間的相互關系，公共通信網中雙路由算法主要分為節(jié)點不相交算法[10-11](Node-disjoint routing algorithm, NDRA)、鏈路不相交算法[12-14](Link-disjoint routing algorithm, LDRA)與最大不相交算法[15](Maximally disjoint routing algorithm, MDRA)。相對于單路由算法，三種類型算法所得到的雙路由均可提高業(yè)務的可靠性。但與公共通信網相比，電力通信網對業(yè)務的可靠性要求更高。因此，電力通信網中雙路由算法需要進一步考慮三種雙路由算法的特點，選擇最適合電力通信網的雙路由算法完成雙路由分配工作。

鑒于現(xiàn)有研究的不足，本文提出一種最可靠環(huán)路策略下的最大不相交雙路由算法(MRMLS)。該算法可為業(yè)務分配一組公共元素最少的雙路由，且該雙路由滿足最可靠環(huán)路條件，這能夠進一步保障雙路由具有較高的可靠性。

1 電力通信網雙路由問題描述

1.1 雙路由算法分析

1.1.1 三種雙路由算法比較

NDRA、LDRA與MDRA三種類型的雙路由算法[15]并不都適用于電力通信網。除源節(jié)點與目的節(jié)點，NDRA要求兩條路由絕對分離；因此，NDRA也被稱為不相交雙路由算法。NDRA并不適用于所有網絡結構。圖1為某通信網絡拓撲圖，考慮從A點到Z點，與B點到Z點配置節(jié)點不相交雙路由，由于無法越過公共節(jié)點，兩次NDRA均會失敗。而在實際中，為保障業(yè)務的可靠性，可分別為兩個業(yè)務分配圖2(c)與圖3所示的具有最少公共元素的雙路由。

圖1 某通信網絡拓撲圖

圖2 鏈路分離雙路由

一般情況下，鏈路故障的概率要大于節(jié)點故障概率[6]，因此，LDRA同樣具有較高的可靠性。但電力通信網對業(yè)務的可靠性要求更高，LDRA得到的兩條路徑可能存在多個相交節(jié)點，算法在可靠性上存在缺陷。圖2為從A點到Z點的三組鏈路分離雙路由(兩條路由分別用實線與虛線表示)。如果在圖1中，采用LDRA從A點到Z點分配雙路由，則LDRA可能得到圖2(a)、圖2 (b)、圖2 (c)三種結果，而實際中我們更傾向于選擇圖2(c)中具有最少公共元素的雙路由。若進一步考慮從B點到Z點分配雙路由，則由于LDRA無法越過公共鏈路B-D，LDRA無法找到可行解。

在算法間相互的關系上，MDRA包含NDRA。MDRA可越過網絡中的公共節(jié)點或公共鏈路，為雙路由分配一組公共元素最少的雙路由。若采用MDRA分別為A點到Z點，與B點到Z點的兩條業(yè)務分配雙路由，則MDRA可直接分配圖2(c)與圖3所示滿足最大不相交條件的雙路由。

圖3 最大不相交雙路由

相對于NDRA，MDRA擁有更高的網絡適應能力；相對于LDRA，MDRA擁有更高的網絡適應能力且所得到的雙路由具有更高的可靠性。因此，與其他兩種算法相比，MDRA更適用于電力通信網。

1.1.2 最大不相交雙路由

如圖4，從A點到Z點的最大不相交雙路由包含兩條路由的公共部分和兩條路由的分離部分。公共部分由雙路由中無法避開的節(jié)點和鏈路組成，分離部分由多組不相交的雙路由所組成。分離部分中每一組不相交雙路由均可組成環(huán)路。因此，每一組最大不相交雙路由均可由多組環(huán)路和其他公共節(jié)點與公共鏈路組成。

圖4 最大不相交雙路由的組成

最大不相交雙路由必須要滿足最大不相交條件，所以最大不相交雙路由中所包含的任意一組不包含有任何公共節(jié)點與公共鏈路的不相交雙路由相互獨立。例如在圖4所示的最大不相交雙路由(此時雙路由不包含雙路由中的公共節(jié)點)中，環(huán)路1與環(huán)路所對應的兩組不相交雙路由相互獨立。

1.2 最可靠環(huán)路策略

最大不相交雙路由算法僅可保證所得到的雙路由具有最少的公共鏈路與公共節(jié)點，當網絡中存在多組最大不相交雙路由時，采用不同的路由策略會得到不同的路由結果。

1.2.1 最可靠雙路由

設為網絡中的節(jié)點，為網絡中的鏈路，()表示節(jié)點的可靠度，()表示鏈路的可靠度。網絡中的路由P是由網絡中的節(jié)點與鏈路所組成的串接系統(tǒng)[16]，路由P的可靠度可通過公式(1)計算：

雙路由的可靠度計算需要考慮兩條路由間的相互關系，為簡化分析，首先考慮不相交雙路由情況。如圖5所示，設節(jié)點A與節(jié)點Z間的主用路由為AP，備用路由為BP(AP與BP不包含公共節(jié)點A與Z)，主備用路由的可靠度分別為(AP)與(BP)。在實際中，AP與BP并不同時使用，所以兩條路由組成的系統(tǒng)為并接系統(tǒng)[16]。

圖5 主備用路由所組成的并接系統(tǒng)

Fig. 5 Parallel system based on the main route and spare route

AP與BP組成的并接系統(tǒng)可靠度可通過公式(2)計算：

此時A、Z兩點間可靠度可通過公式(3)計算：

(3)

設A點與Z點間最大不相交雙路由包含組不相交雙路由，第組不相交雙路由的主備用路由分別為AP與BP；設A點與Z點間最大不相交雙路由的公共部分可靠度為(public)。則A點到Z點間雙路由的可靠度可通過公式(4)計算：

A點與Z點間所有最大不相交雙路由的公共部分保持不變，且每一組最大不相交雙路由所包含的多組不相交雙路由相互獨立。因此，A點與Z點間滿足最可靠條件的最大不相交雙路由需要滿足公式(5)。

(5)

即當A點與Z點間最大不相交雙路由所包含每一組不相交雙路由可靠度均達到最大值時，此時最大不相交雙路由可靠度最高。

1.2.2 最可靠環(huán)路配置方法

采用最可靠策略分配最大不相交雙路由，需要保證最大不相交雙路由中多組不相交雙路由的可靠度均取得最大值，在實際中很難保證最大不相交雙路由滿足上述條件。

為便于工程實現(xiàn)，本文采取最可靠環(huán)路策略為業(yè)務分配最大不相交雙路由。如圖5所示，當不相交雙路由可靠度乘積(AP)?(BP)的值取得最大值時，此時AP與BP所組成的環(huán)路可靠性最高。

當最大不相交雙路由(AP)?(BP)取得最大值時，此時如公式(6)，最大不相交雙路由所包含的每一個環(huán)路在此時均為最可靠環(huán)路，此時的最大不相交雙路由即為滿足最可靠環(huán)路條件的最大不相交雙路由，此時的配置方法即為最可靠環(huán)路配置方法。

定義1雙路由的主備用路由AP與BP可靠度乘積(AP)?(BP)取得最大值時，此時的雙路由配置方法即為最可靠環(huán)路配置方法。

相對于最可靠雙路由，滿足最可靠環(huán)路條件的雙路由可靠性較低。但在實際中，在最大不相交的限制條件下，在相當多的時候兩種分配策略的結果是一致的。當兩種分配策略的結果產生差異時，滿足最可靠環(huán)路條件的雙路由可保證雙路由中的每一個環(huán)路的可靠度均取得最大值，此時雙路由同樣具有較高的可靠性。

1.3 算法數(shù)學模型

本文在最大不相交雙路由的條件下，采用最可靠環(huán)路策略為電力通信網分配雙路由。

定義2 設P1與P2為同一網絡中的兩條路由，則P1與P2的相交度為P1與P2中公共節(jié)點與公共鏈路的數(shù)量和，其數(shù)學表示方法為(P1∩P2) (cardinality of P1∩P2，集合P1∩P2的基數(shù)，在此表示集合P1∩P2中節(jié)點與鏈路的數(shù)量和)。

因此本文算法可描述為在相交度最小的條件下，為源點與目的節(jié)點分配一組可靠度乘積最高的主備用路由AP與BP。本文算法的目標如公式(7)所示。

2 最大不相交雙路由配置方法

MDRA的研究相對較少，一般比較直接的最大不相交雙路由配置方法可通過RF(Remove-Find)算法與KSP(K-Shortest Paths)算法進行適當改進得到。改進的RF算法(Improved Remove-Find, IRF)首先找到一條最短路徑，再將最短路徑上節(jié)點與鏈路的權值修改為足夠大的權值，最終再次尋找最短路徑，兩條最短路徑即為所求最大不相交雙路由。IRF算法存在所配置的雙路由不一定為最大不相交雙路由的缺陷。

基于KSP(K-shortest path)算法的最大不相交雙路由算法(Maximally disjoint paths algorithm based on KSP, M_KSP)尋找多條源點與目的節(jié)點間的路徑，通過篩選得到多組最大不相交雙路由，最終配置一組可靠度最高的雙路由。一般路徑數(shù)量K設置的越大，得到最優(yōu)解的幾率就會越大。但在實際中，很難為KSP算法提前設定一個適合于本網絡的路徑數(shù)量值K，使M_KSP一定能得到最可靠的最大不相交雙路由；采用KSP算法會產生多條冗余路徑，算法效率較低；KSP算法時間復雜度較高，當路徑數(shù)量K過大或網絡節(jié)點數(shù)量較多時會導致M_KSP運行時間過長。

Bhandri最大不相交雙路徑算法[15](Maximally- disjoint paths algorithm of Bhandari version, MPAB)可為源點與目的節(jié)點分配一組路徑權值和最小且滿足最大不相交條件的雙路由。MPAB不存在理論缺陷，可在任意網絡中為任意節(jié)點對分配權值和最小的最大不相交雙路由。本文的路由算法是基于MPAB算法的改進算法，改進后的算法可為業(yè)務分配滿足最可靠環(huán)路條件的最大不相交雙路由。

2.1 Bhandari最大不相交算法

圖6為MPAB在為A點到Z點分配最大不相交雙路由過程中的網絡拓撲變化示意圖。其中，圖6(a)為某通信網網絡拓撲圖；圖6(b)為采用基于最短路徑的節(jié)點分裂方法對圖6(a)進行網絡拓撲修改所得到的網絡拓撲圖；圖6(c)為MPAB將運算過程中產生的兩條路徑進行組合所產生的網絡拓撲圖；圖6(d)為MPAB利用相關運算結果，對圖6(c)所示網絡進行網絡權值修改所得到的網絡拓撲圖。結合圖6，MPAB的運算過程描述如下。

圖6 MPAB中網絡拓撲的變化

第一步，在圖6(a)網絡中，調用改進的Dijkstra算法，得到最短路徑path1(A-B-D-F-H-Z)。

第二步，采用基于最短路徑的節(jié)點分裂法修改網絡中相應邊與點的連接關系以及它們的權值，得到新的網絡拓撲如圖6(b)所示。

基于最短路徑的節(jié)點分裂方法具體為：規(guī)定路徑中由源點到目的節(jié)點的方向為正向，其相反方向為反向；path1路徑上除去起點和終點外的其他點一分為二，如B分裂為B1與B2，B1與B2間反向邊的權值為0，正向邊的權值設置為0；path1中所有鏈路反向權值變?yōu)樵溌窓嘀档南喾磾?shù)，鏈路正向權值置為0；非path1路徑上的節(jié)點(以C為例)如果之前與該路徑有連接關系，那么將C以單向邊連到B1與B2；單向邊在方向上滿足邊C→B1、B2→C與B1→B2組成單向環(huán)路，邊C→B1、B2→C權值仍為原來雙向邊BC的權值。設圖6(a)中的網絡為，(e)為鏈路的權值，n應大于最終得到的主備用路由所包含的公共鏈路數(shù)(n可設置為path1所包含的鏈路數(shù))，則0與0滿足公式(8)：

第三步，在圖6(b)網絡中，調用改進的Dijkstra算法，得到路徑path2(A-B1-B2-C-D1-D2-E-H1-F2-G- Z)，將path2中分裂節(jié)點還原為原節(jié)點，此時path2變?yōu)锳-B-C-D-E-H-F-G-Z。

第四步，并將path1與path2組成一個簡單網絡如圖6(c)所示，path1與path2所重合得鏈路權值設置為0，如虛線所示，在圖5(c)中執(zhí)行改進的Dijkstra算法，得到AP(A-B-D-E-H-Z)。

第五步，在圖6(c)中將AP所包含的鏈路權值修改為0，得到圖6(d)所示網絡，調用改進的Dijkstra算法，得到BP(A-B-C-D-F-G-Z)。

2.2 滿足最可靠環(huán)路條件的雙路由算法

為解決電力通信網雙路由分配問題，本文將MPAB進行改進，提出一種最可靠環(huán)路策略下的最大不相交雙路由算法(the Maximally Disjoint Routing Algorithm Under the Most Reliable Loop Strategy，MRMLS)。相對于MPAB，MRMLS 有以下4個方面的改進之處：

(1) MPAB在計算過程中沒有考慮到網絡中的節(jié)點權值，應用到電力通信網中應進一步考慮網絡中的節(jié)點權值；

(2) 電力通信網注重業(yè)務的可靠性，雙路由算法應從可靠性出發(fā)，為電力通信業(yè)務分配可靠性的雙路由；

(3) MPAB在計算過程中會對網絡的權值進行修改，算法得到的主備用路由AP與BP的權值為偽權值，最終應再次計算AP與BP的真正路徑權值與此時的雙路由的可靠度；

(4) 為直接反映雙路由的相互關聯(lián)情況并反映源點與目的節(jié)點間網絡拓撲的連接狀況，應計算MPAB所得主備用路由的相交度。

2.2.1 考慮節(jié)點權值的雙路由算法

MPAB沒有考慮到網絡中的節(jié)點權值，可將MPAB中改進的Dijkstra算法進行修改[2]，使其進一步考慮節(jié)點權。但單純考慮節(jié)點權值的改進型Dijkstra算法很可能會導致MPAB在路徑搜索中出現(xiàn)錯誤。例如在圖7中，為1號節(jié)點到5號節(jié)點分配雙路由，采用考慮節(jié)點權值的MPAB算法會得到1-6-7-4-5與1-2-3-8-9-5兩條路由，其權值和為49。而實際中權值和最小的雙路由為1-6-7-4-5與1-2-10-11-5，其權值和為42。這是因為在節(jié)點分裂的網絡中，若從節(jié)點3到節(jié)點2，需要兩次經過3號節(jié)點，導致3號節(jié)點的權值疊加兩次，使MPAB產生錯誤解。

圖7 帶有節(jié)點權值的網絡拓撲圖

在節(jié)點分裂的網絡中不能簡單疊加節(jié)點權值， Dijkstra算法需要進一步識別路徑是否已經抵達此節(jié)點。若Dijkstra算法已經抵達此節(jié)點，則再次經過此節(jié)點時，此節(jié)點的權值變?yōu)?。

MPAB在計算過程中加入了節(jié)點權值，為排除節(jié)點權值對路徑搜索結果產生的影響，應按公式(9)調整0與0的大小。

2.2.2 最可靠環(huán)路雙路由算法

MPAB算法僅可采用鏈路的加性權值進行雙路由搜索，不能計算節(jié)點與鏈路的可靠度乘積。鏈路與節(jié)點的可靠度分布在(0, 1)區(qū)間，可通過取負對數(shù)的方法，將可靠度由乘性參數(shù)變?yōu)榧有詤?shù)。此時的MPAB算法得到的AP權值(AP)與BP權值(BP)的和滿足公式(10)：

MPAB算法得到的兩條最大不相交路徑的權值和(AP)(BP)最小，通過公式(10)可進一步得到此時兩條路由AP與BP的可靠度乘積(AP)?(BP)最大。即此時MPAB算法得到的兩條最大不相交雙路由為滿足最可靠環(huán)路條件的雙路由。

2.2.3 雙路由相交度與業(yè)務可靠度

最大不相交雙路由中的公共元素越多，兩條路由同時出現(xiàn)故障的概率就會越大。因此，可通過計算最大不相交雙路由的相交度(APBP)，直接反映此時主備用路由同時失效的風險。

源節(jié)點與目的節(jié)點間雙路由的最大不相交度由兩個點間的網絡連接狀況所決定，因此可通過最大不相交雙路由的相交度可為進一步分析源節(jié)點與目的節(jié)點間網絡的連接狀況。

為準確反映采用當前最大不相交雙路由的可靠性，需要通過AP與BP按公式(4)重新計算此時最大不相交雙路由的可靠度。

2.2.4 MRMLS的算法流程

本文通過修改MPAB得到MRMLS，圖8為MRMLS的算法流程圖，MRMLS具體步驟為：

圖8 MRMLS算法流程圖

(1) 將網絡中節(jié)點與鏈路的可靠度取負對數(shù)，得到算法網絡；

(2) 獲取當前配置業(yè)務的源點(s)與目的節(jié)點(t)；

(3) 采用考慮節(jié)點權值的MPAB在源點與目的節(jié)點間尋找最大不相交雙路徑；

(4) 分別計算兩條路徑的可靠度，并將可靠度較高的路徑配置為主用路由AP，另一條配置為備用路由BP；

(5) 計算當前雙路由的相交度st；

(6) 計算采用AP與 BP的最大不相交雙路由的可靠度；

(7) 判斷是否有剩余業(yè)務，若有剩余業(yè)務則返回步驟(2)，若無剩余業(yè)務，則算法結束。

設網絡中的節(jié)點數(shù)量為，鏈路數(shù)量為，網絡中路徑的平均節(jié)點數(shù)為，則運行一次MRMLS的時間復雜度為O(?log()log()4?log (2)22)。

3 算法仿真分析

MDRA的研究相對較少，本文采取兩種比較直接的方法IRF與M_KSP算法作為本文所提出的MRMLS的對比算法。其中M_KSP分別采取路徑數(shù)量為50、100與500的M_50SP、M_100SP與M_500SP算法進行仿真。

圖9為我國某地區(qū)電力通信網網絡拓撲圖，其包含101個節(jié)點，141條鏈路。在圖9中，鏈路可靠度在[0.99, 0.999]間自動生成，節(jié)點可靠度在[0.999, 0.9999]間自動生成，分別采用上述方法為網絡中任意節(jié)點對之間分配一組最大不相交雙路由(總業(yè)務數(shù)量為5 050條)，則對比結果如下。

圖9 我國某地區(qū)電力通信網網絡拓撲圖

3.1 雙路由相交度

在雙路由的配置過程中， MRMLS所得到的每一組雙路由均具有最小相交度，這進一步驗證了MRMLS為最大不相交雙路由算法。IRF與M_KSP并不能保證其所配置雙路由具有最小相交度。在部分業(yè)務的配置過程中，相對于最大不相交雙路由，兩種算法得到的雙路由相交度會變大。

表1展示了在不同算法、不同相交度下，雙路由的數(shù)量分布。從表1中可以看出，MRMLS在各個相交度的雙路由數(shù)量均大于等于其他幾種算法；隨著相交度的增大，其他幾種算法的雙路由數(shù)量會逐漸接近MRMLS；但在相交度較小的區(qū)域，其他算法與MRMLS有較大差距。

表1 不同相交度下的雙路由數(shù)量分布表

為突出數(shù)據(jù)的變化趨勢，方便其他算法與MRMLS進行對比，本文采用MRMLS列數(shù)據(jù)對其他4列數(shù)據(jù)進行歸一化，得到圖10所示的雙路由相交度變化曲線。

圖10 雙路由數(shù)量隨雙路由中公共元素數(shù)量的變化情況

從圖10中可看出，IRF的雙路由相交度曲線低于要 MRMLS與M_500SP；M_KSP隨著路徑數(shù)量的增加，其相交度會逐漸接近MRMLS；但與MRMLS相比，即使是采用路徑數(shù)量較多的M_500SP，二者在相交度上依然有較大差距。因此，與IRF、M_KSP相比，MRMLS所得到的雙路由公共元素最少，雙路由同時故障的幾率更小，在可靠性上MRMLS具有顯著優(yōu)勢。

3.2 路由可靠度

IRF不能保證所得到的雙路由為最可靠雙路由。M_KSP通過篩選多條源點目的節(jié)點間路徑，得到相交度最小的最可靠雙路由；在任意網絡中，當M_KSP的路徑數(shù)量上限K→∞時，M_KSP所得到的雙路由即為相交度最小且可靠性最高的雙路由。在實際中，M_KSP很難得到源節(jié)點到目的節(jié)點的所有路徑。在本次仿真中，M_500SP的路徑數(shù)量遠遠高于網絡中節(jié)點數(shù)量與鏈路數(shù)量，本文采用M_500SP來近似估測最可靠的最大不相交雙路由。

本文采取MRMLS、M_500SP、與最可靠單路由(Most Reliable Single Route, MRSR，可通過KSP篩選得到)進行對比。相交度的變化會對雙路由的可靠性產生影響，因此，在進行可靠性分析時需要保證MRMLS與M_500SP所得到的雙路由具有相同的相交度。在5 050條業(yè)務中，MRMLS與M_500SP具有相同相交度的業(yè)務共有4 628條。為便于人眼分析，將三組數(shù)據(jù)按M_500SP的可靠度進行升序排序，得到圖11所示曲線圖。

圖11 路由可靠度比較

圖11中，M_500SP對應的可靠度曲線為圖11中頂部的一條平滑曲線；MRMLS的曲線與M_500SP的曲線近似重合；MRMLS與 M_500SP所得到的雙路由可靠度均遠高于最可靠單路由(MRSR)的可靠度。由此可見，最大不相交雙路由的可靠性要優(yōu)于最可靠單路由的可靠性。

進一步求三種算法的可靠度的平均值，MRMLS、M_500SP與MRSR的可靠度平均值分別為0.994 575、0.994 569與0.971 184。MRMLS所得到的雙路由可靠度平均值要略微高于M_500SP。若想進一步提高M_500SP得到的雙路由可靠度，需要進一步提高M_500SP的路徑數(shù)量。因此，相對于最可靠單路由MRSR與M_500SP，MRMLS得到的最大不相交雙路由具有更高的可靠性。

3.3 路由跳數(shù)分析

路由的跳數(shù)越多，其所占用的節(jié)點與鏈路的資源量就會越大，其完成相應工作的效率就會越低。若算法單純從最可靠環(huán)路或最可靠雙路由角度出發(fā)，可能會造成雙路由的跳數(shù)和(兩條路由的節(jié)點數(shù)之和)過大。為分析雙路由所占用的網絡資源量，在MRMLS與M_500SP所得的雙路由具有相同相交度的情況下，本文采取MRMLS與M_500SP兩種算法的雙路由結果與跳數(shù)和最少的最大不相交雙路由(The Maximally Disjoint Routes with Least Hops, MDRLH，可通過KSP篩選得到)作對比，分析三種雙路由的跳數(shù)和的分布情況。

圖12 不同路由策略下的雙路由跳數(shù)和

從圖12中可以看出，三種路由策略下的雙路由跳數(shù)和的分布區(qū)間與變化趨勢大體一致。進一步求雙路由跳數(shù)和的平均值，得到MRMLS、M_500SP與MDRLH的跳數(shù)和平均值分別為19.01、18.6、17.42。相對于MDRLH，在路由跳數(shù)和上MRMLS與M_500SP分別提高了9.1%與6.8%。這說明不同路由策略下的雙路由跳數(shù)和變化并不明顯，MRMLS得到的雙路由并不會占用過多的網絡資源。

3.4 算法時間復雜度分析

本文采用2.6 GHz四核心處理器，4 GB內存， WIN7系統(tǒng)的主機對算法進行仿真；仿真軟件為VS2010，采用C++語言實現(xiàn)五種算法。本文的M_KSP算法采用的KSP算法為刪除路徑算法。

為分析五種算法的運行時間，本文選取節(jié)點數(shù)量為100, 200, … , 800且鏈路數(shù)量為節(jié)點數(shù)量1.6倍的網絡進行仿真；在每個網絡中隨機選取100條業(yè)務，分別采用五種算法為業(yè)務分配雙路由；在不同節(jié)點數(shù)量的網絡中，分別計算不同算法的平均運行時間。

五種算法的平均運行時間隨節(jié)點數(shù)量變化的曲線如圖13(a)所示；為了進一步清晰顯示圖13(a)中軸附近的曲線，將圖13(a)中M_100SP與M_500SP所對應的曲線刪去，并將圖13(a)進行放大，得到圖13(b)所示曲線圖。

從圖13(a)中可以看出三種M_KSP算法的平均運行時間均高于IRF與MRMLS，且M_KSP曲線更為陡峭，若節(jié)點數(shù)量進一步增加，則M_KSP與IRF、MRMLS的運行時間差會進一步增加。

進一步地，圖13(b)中IRF的平均運行時間要略小于MRMLS；MRMLS與IRF的運行時間要遠小于M_50SP的運行時間。

在上文所述我國某地區(qū)電力通信網中(對應于節(jié)點數(shù)量為100的網絡)，采用MRMLS、IRF、M_50SP、M_100SP與M_500SP分別為5 050條業(yè)務分配雙路由的時間分別為17.51 s、6.32 s、1 598.3 s、1.05 h與8.5 h。

IRF的平均運行時間最短，但得到滿足最大不相交條件的雙路由數(shù)量較少；而算法效果相對較好的M_KSP的運行時間較長，當路徑數(shù)量與網絡節(jié)點數(shù)量增多時，其運行時間會大幅增加，且M_KSP同樣很難保證其所得到的雙路由為最大不相交雙路由。

因此， MRMLS不僅在算法效果上要優(yōu)于其他幾種算法，同時MRMLS也擁有較小的時間開銷。

圖13 算法運行時間比較

4 結束語

針對電力通信網的雙路由分配問題，本文提出一種最可靠環(huán)路策略下的最大不相交雙路由算法(MRMLS)。該算法可為業(yè)務分配一組公共元素最少的雙路由，且該雙路由滿足最可靠環(huán)路條件，這能夠進一步提高雙路由的可靠性。仿真結果表明，MRMLS具有較小的時間開銷，并可保證所得到的雙路由具有較高的可靠性。

[1] 金鑫. 高壓直流輸電系統(tǒng)極控信號通信網絡可靠性分析[J]. 電力系統(tǒng)保護與控制, 2015, 43(12): 110-116.

JIN Xin. Reliability analysis on HVDC pole control signal transmission network[J]. Power System Protection and Control, 2015, 43(12): 110-116.

[2] 高會生, 王慧芳. 基于安全性的繼電保護光纖迂回通道路徑選擇[J]. 電力系統(tǒng)保護與控制, 2014, 42(14): 25-31.

GAO Huisheng, WANG Huifang.Path selection based on security measure for relay protection services of fiber circuitous channel[J]. Power System Protection and Control, 2014, 42(14): 25-31.

[3] 倪明放, 王曦, 武欣嶸, 等. 多約束最優(yōu)路由選擇和不相交路由選擇問題[J]. 軍事通信技術, 2010, 31(4): 71-76.

NI Mingfang, WANG Xi, WU Xinrong, et al. Multi- constrained optimal path selection and disjoint path selection[J]. Journal of Military Communications Technology, 2010, 31(4): 71-76.

[4] 吳潤澤, 祁宏鵬, 唐良瑞. 新一代電力ICT網絡中基于DiR保護環(huán)的生存性路由算法[J]. 電力系統(tǒng)保護與控制, 2011, 39(16): 25-29.

WU Runze, QI Hongpeng, TANG Liangrui. Survival routing algorithm based on DiR protection ring in novel power ICT network[J]. Power System Protection and Control, 2011, 39(16): 25-29.

[5] 曾慶濤, 邱雪松, 郭少勇, 等. 電力通信業(yè)務路由分配算法[J]. 北京郵電大學學報, 2013, 36(3): 79-82, 87.

ZENG Qingtao, QIU Xuesong, GUO Shaoyong, et al. Routing algorithm for power communications service assignment[J]. Journal of Beijing University of Posts and Telecommunications, 2013, 36(3): 79-82, 87.

[6] 蔡偉, 楊洪, 熊飛, 等. 考慮電力通信網可靠性的業(yè)務路由優(yōu)化分配方法[J]. 電網技術, 2013, 37(12): 3541-3545.

CAI Wei, YANG Hong, XIONG Fei, et al.An optimized service routing allocation method for electric power communication network considering reliability[J]. Power System Technology, 2013, 37(12): 3541-3545.

[7] 曾瑛, 蔣康明, 楊嬌, 等. 基于量子遺傳算法的電力通信網路由選擇策略[J]. 太原理工大學學報, 2013, 44(4): 501-505.

ZENG Ying, JIANG Kangming, YANG Jiao, et al. Power communication network routing selection strategy based on quantum genetic algorithm[J]. Journal of Taiyuan University of Technology, 2013, 44(4): 501-505.

[8] 張銘泉, 胥鳴, 秦文韜. 基于改進粒子群算法的電力通信網最佳搶修路徑問題的研究[J]. 科學技術與工程, 2008, 22(8): 5990-5995.

ZHANG Mingquan, XU Ming, QIN Wentao.Research of the best repair path based on an improved particle swarm optimization in power communication network[J]. Science Technology and Engineering, 2008, 22(8): 5990- 5995.

[9] 曾瑛, 李偉堅, 陳媛媛, 等. 基于業(yè)務優(yōu)先級的電力調度數(shù)據(jù)網擁塞規(guī)避算法[J]. 電力系統(tǒng)保護與控制, 2014, 42(2): 49-55.

ZENG Ying, LI Weijian, CHEN Yuanyuan, et al.A congestion avoidance algorithm based on the service priority for electric power dispatching data network[J]. Power System Protection and Control, 2014, 42(2): 49-55.

[10] SUURBALLE J W. Disjoint paths in a network[J]. Networks, 1974, 4(2): 125-145.

[11] BHANDARI R. Optimal diverse routing in telecommunication fiber networks[C] // INFOCOM'94. Networking for Global Communications, 13th Proceedings IEEE: IEEE, 1994: 1498-1508.

[12]張品, 張堅武, 李樂民, 等. QoS約束下的鏈路分離問題的研究[J]. 通信學報, 2006, 27(6): 37-42.

ZHANG Pin, ZHANG Jianwu, LI Lemin, et al. Researches on the problem of link disjoint paths pair with QoS constraints[J]. Journal on Communications, 2006, 27(6): 37-42.

[13]熊軻, 裘正定, 郭宇春, 等. 多約束最短鏈路分離路徑精確算法[J]. 軟件學報, 2010, 21(7): 1744-1757.

XIONG Ke, QIU Zhengding, GUO Yuchun, et al.Exact algorithm for multi-constrained shortest link-disjoint paths[J]. Journal of Software, 2010, 21(7): 1744-1757.

[14]倪明放, 高石云, 武欣嶸, 等. 求不相交QoS路由的一種整數(shù)線性規(guī)劃方法[J]. 控制與決策, 2012, 27(10): 1597-1600.

NI Mingfang, GAO Shiyun, WU Xinrong, et al. Integer linear program method of finding link-disjoint paths for QoS routing[J].Control and Decision, 2012, 27(10): 1597-1600.

[15]BHANDARI R. Physical diversity versus cost algorithm for networks[J]. Simulation Series, 1996, 28: 258-264.

[16]周炯槃, 張琳, 望育梅, 等. 通信網理論基礎[M]. 北京: 人民郵電出版社, 2009: 166-187.

(編輯 周金梅)

A maximally disjoint routing algorithm for power communication networks

HE Yujun, CHEN Ran, ZHANG Wenzheng, LIU Yi, ZHOU Shengping

(Dept of Electronics and Communication Engineering, North China Electric Power University, Baoding 071000, China)

Since the existing routing algorithms for power communication network could not be used for finding a pair of routes, the maximally disjoint routing algorithm under the most reliable loop strategy (MRMLS) is proposed. Three types of double routing algorithms for the public communication network are discussed. Considering the diversity of the network topology, the maximally disjoint routing algorithm is adopted. The reliability of maximally disjoint routes is studied, and the maximally disjoint routes with the characteristic of the most reliable loop are put to use. The original maximally disjoint routing algorithm is improved, and the reliability of nodes and links is considered in the proposed algorithm. Simulation experiment compares MRMLS with another two available routing algorithms. The experiment results show the feasibility and validity of MRMLS. This work is supported by Fundamental Research Funds for the Central Universities (No. 13MS64).

power communication network; double routes; maximally disjoint; reliability; the most reliable loop

10.7667/PSPC150818

中央高?；究蒲袠I(yè)務費專項資金資助(13MS64)

2015-05-14；

2015-07-09

何玉鈞(1974-)，男，副教授，碩士生導師，研究領域為電力通信網管理、安全風險評估； 陳 冉(1989-)，男，通信作者，碩士研究生，主要研究方向為電力通信業(yè)務路由配置方法；E-mail: crncepu@163.com 張文正(1990-)，男，碩士研究生，主要研究方向為電力通信網通信資源管理。