胡朝平，易穎

（南京郵電大學 江蘇南京 21003）

0 引言

在電力通信網中引入下一代網絡旨在改革現有電力通信網和信息產業(yè)的基礎設施，以支持更廣泛的業(yè)務。其特點是：基于分組傳輸、呼叫控制與承載相分離、支持各種業(yè)務、可與現有網絡互通。下一代網絡為電力行業(yè)信息化建設的一些急待解決的問題提供了解決方案。ASON的出現代表了光網絡技術發(fā)展的趨勢，能夠解決帶寬快速部署、端對端配置和保護/恢復等問題，提供QoS/SLA和分布式的網絡控制能力。

1 電力特種業(yè)務

電力特種業(yè)務的服務對象是電力輸變電網的保障和控制裝置，業(yè)務本身則由電力通信傳輸網承載。電力特種業(yè)務的承載目標，是確保業(yè)務的傳送質量，不對輸送電系統的控制附加額外異常，確保電力特種業(yè)務裝置正確運行。

電力特種業(yè)務這里特指繼電保護，采用差動縱聯保護，或縱聯差動保護，簡稱縱差保護。其保護利用通信業(yè)務通道，將本側電流或電壓的波形信息，或者代表電流或電壓相位的信號傳送到對側，每側保護均需根據兩側電流/電壓幅值及相位進行比較計算，并在之上判斷是區(qū)內還是區(qū)外故障，進而采取適當的控制措施。數字式電流差動保護是最普通的縱差保護方法，首先將各端電氣量數字化，通過數字通信方式進行傳送，然后利用微處理器進行動作判定。差動保護在算法上要求參加比較的各端電流量必須同步采樣，或者經采樣同步化處理。

2 問題分析及描述

電力SDH傳輸網影響特種業(yè)務性能的因素，主要包括業(yè)務通道延時(Sd)、雙向通道延時差(Sv)。5 ms的通信通道延時可作為電力特種業(yè)務優(yōu)良性能的基礎；7~8 ms是繼電保護業(yè)務的可用指標；延時10 ms以內的通道可用于安全穩(wěn)定業(yè)務，不利于繼保業(yè)務；20 ms以上延時的通信通道，對繼保和安穩(wěn)業(yè)務完全不可用。所以對于單向業(yè)務通道時延，一般要求小于8ms。

縱聯差動裝置之間可采用采樣時間補償或時鐘校準方法實現電氣量采樣數據的同步，也是現網中得到應用最多的采樣同步方法。設M側裝置至N側裝置的通道延時為T1，反向通道延時為T2，上述兩種采樣同步法在假設雙向通道延時相同時測出的通道延時為：

與實際值的偏差則為：

由此可知，M側采樣數據與N側采樣數據在差動計算時，實際的時間差為2Te。，即|T1-T2|。工頻50Hz（對應用360 °相角）的電氣量，采用固定周期采樣，則采樣周期為：

其中，f為一周采樣數，通常為12或24。

進行縱差條件計算的保護裝置，如果正確比對采樣時間的相角差容限為 θ，即大于該相角的兩側數據將可能導致裝置誤動作。顯然，理論上 θ 的最大值為360/2f =180 / f。若f =12, 則 θ = 15；若f =12, 則 θ = 7.5。

實際應用當中，相角差容限的經驗值為4°~6 °。與相角差容限 θ 相對應的時間差為：

可知，縱聯差動保護裝置不發(fā)生誤動作的條件是：2Te< Ts。

依據上式，可以計算出縱聯差動保護對雙向通道延時差的理論容限和經驗容限。針對繼電保護業(yè)務，與雙向通道延時差對相角差，可容納的有效區(qū)間，其經驗值小于4°~6 °；對于一周24點均勻采樣，理論計算有效區(qū)間值小于7.5 °。所以對于雙向通道延時差要求小于0.333ms。

分析了兩個電力特種業(yè)務的要求后，可以將問題描述為：在一個給定權值的有向圖G(V,E)中，給出源節(jié)點S和目的結點T，要求能夠尋找到兩條路徑S-T和T-S。記S-T的時延為Delay1,T-S的時延為Delay2;要求單向時延Delay1和Delay2均小于要單向傳輸時延約束值Dmax(這里取8ms)；雙通道時延差|Delay1- Delay2|小于約束值Dgap(這里取0.333ms)。并且要求兩條路徑不能經過同條鏈路或同個SRLG組。

3 流程圖及算法描述

該路由算法可以理解為一種約束路由算法（CSPF），兩個具體的約束因子：單向路徑時延Delay<8ms,雙向路徑時延差D<0.333ms；具體算法步驟描述為：

步驟1：

獲取相應的拓撲信息和相應邊的權值等，有向圖G；

步驟2：

使用Dijkstra算法求出S-T最小時延路徑。計算其時延值，判斷其是否小于時延約束值Dmax：若大于，則表明無法滿足業(yè)務需求，算法結束；若小于，保存計算所得路徑和相應時延Delay1；

步驟3：

修改相應圖的權值，使用Dijkstra算法計算T-S的最短路徑,記錄路徑和時延Delay2,比較Delay2是否小于Dmax。若Delay2小于Dmax,則比較|Delay1-Delay2|是否小于Dgap，若小于則算法成功，記錄相應路徑及路由，結束；若大于Dgap則轉步驟4。若Delay2大于Dmax,則轉步驟5；

步驟4：

比較Delay1是否大于Delay2,若Delay1>Delay2則用背離路徑方法計算T-S下一條路徑（該路徑是時延僅大于Delay2的次短路徑），若結果非空，則轉步驟3；若結果為空，則轉步驟5。若Delay1

步驟5：

圖1 算法流程圖

用背離路徑方法計算下一條S-T路徑（該路徑是時延僅大于Delay1的次短路徑）若結果為空，則算法失敗，無法找到相應的路徑，算法結束；若結果非空，則轉步驟3；

在這個算法中，求解次短時延路徑時運用了背離路徑的思想。假設vi為源節(jié)點,vj為目的節(jié)點.(vi,vj)間的兩條路徑vi,v1,v2,,…vn,vj和vi,v’1,v’2,…vn,vj,，如果vi,v1,v2,…vn, 和vi,v’1,v’2, …v’n節(jié)點相同，在vn+1處開始不同，則稱路徑vi,v1,v2,,…vn,vj由vi,v’1,v’2,…n,vj在vn+1處背離得到, vn+1為被背離節(jié)點, v’n+1為背離節(jié)點。背離路徑的定義:路徑vi,v1,v2,v3,…vn,vj以vn+1為被背離節(jié)點,以v’n+1為背離節(jié)點的所有背離路徑中有一條最短,它由vi,v1,v2,v3,…vn,+鏈路vn,vn+1,vn+2,…vj的最短路徑得到。以v’n+1為背離節(jié)點的路徑專指這條最短路徑，而非以為v’n+1背離節(jié)點的其它路徑。在求v’n+1到vj的最短路徑時,應刪除與節(jié)點vi,v1,v2,v3,…vn有關的鏈路,再利用Dijkstra 算法求最短路徑,以避免拼接而成的背離路徑產生環(huán)路。

算法的流程圖如圖1所示。

4 仿真結果

為了驗證算法的可行性和正確性，取一個典型的5節(jié)點全連通圖進行測試，如圖2所示。設置每條光鏈路的主要屬性（時延、距離）為圖3所示。

圖2 網絡拓撲圖

圖3 節(jié)點屬性圖

利用文中算法計算點0至點3的雙向鏈路，其結果如圖4所示。計算得到了兩條路徑，分別為0-2-3和3-1-0，滿足要求。

圖4 路由計算后結果

現修改其中一條光通路0-2的屬性，修改其距離為10km，相應時延也比原來增加了10倍，如圖5所示。

圖5 修改后的節(jié)點屬性

重新計算點0-點3的雙向鏈路，其結果如圖6所示。重新計算得到的結果為0-4-3和3-1-0，算法沒有選擇那條時延較大的路徑，證明了其正確性。

圖6 重新計算后的結果

5 結束語

目前文中的路由算法，應用到電力ASON系統，能有效解決電力特種業(yè)務對于搜索雙向鏈路的要求。在提高路徑搜索效率方面，借鑒了“背離路徑”的思想，來解決第K短路徑問題，大大降低了時間復雜度。

[1] 王明中,謝劍英,陳應麟. 一種新的 Kth 最短路徑搜索算法[J].計算機工程與應用, 2004（30）.

[2] 傅俊偉,李興明,陳捷. 基于背離路徑的 Kth最短路徑實用搜索算法[J].計算機技術 與發(fā)展,2009,19(2).

[3] Ricardo Martínez, Ramon Casellas, Raül Mu?oz, Takehiro Tsuritani.Experimental Translucent-Oriented Routing for Dynamic Lightpath Provisioning in GMPLS-Enabled Wavelength Switched Optical Networks[J].LIGHTWAVE TECHNOLOGY,2010,28(8).

[4] Pei Luo, Shanguo Huang, Weihua Lian, Bin Li, Wanyi Gu.Novel Routing Algorithms for Hierarchical Architecture in ASON[C].2009 WASE International Conference on Information Engineering,2009.

[5] G Maier, F Mizzotti, A Pattavina.Multi-domain routing techniques in ASON networks[C].Proc of ECOC, 33rd European Conference and Exhibition of Optical Communication,2007.

[6] Seyed Reza Ehsani, Valiallah Ghorbani, Sadegh Abbasi Shahkooh.Hierarchical routing in optical networks[C].2008 3rd International Conference on Information and Communication Technologies: From Theory to Applications,2008.