A S O N路由算法在電力系統(tǒng)中的研究

胡朝平，易穎

（南京郵電大學(xué) 江蘇南京 21003）

0 引言

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

1 電力特種業(yè)務(wù)

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

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

2 問題分析及描述

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

縱聯(lián)差動裝置之間可采用采樣時間補償或時鐘校準(zhǔn)方法實現(xiàn)電氣量采樣數(shù)據(jù)的同步，也是現(xiàn)網(wǎng)中得到應(yīng)用最多的采樣同步方法。設(shè)M側(cè)裝置至N側(cè)裝置的通道延時為T1，反向通道延時為T2，上述兩種采樣同步法在假設(shè)雙向通道延時相同時測出的通道延時為：

與實際值的偏差則為：

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

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

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

實際應(yīng)用當(dāng)中，相角差容限的經(jīng)驗值為4°~6 °。與相角差容限 θ 相對應(yīng)的時間差為：

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

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

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

3 流程圖及算法描述

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

步驟1：

獲取相應(yīng)的拓?fù)湫畔⒑拖鄳?yīng)邊的權(quán)值等，有向圖G；

步驟2：

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

步驟3：

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

步驟4：

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

步驟5：

圖1 算法流程圖

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

在這個算法中，求解次短時延路徑時運用了背離路徑的思想。假設(shè)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的最短路徑時,應(yīng)刪除與節(jié)點vi,v1,v2,v3,…vn有關(guān)的鏈路,再利用Dijkstra 算法求最短路徑,以避免拼接而成的背離路徑產(chǎn)生環(huán)路。

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

4 仿真結(jié)果

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

圖2 網(wǎng)絡(luò)拓?fù)鋱D

圖3 節(jié)點屬性圖

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

圖4 路由計算后結(jié)果

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

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

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

圖6 重新計算后的結(jié)果

5 結(jié)束語

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

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

[2] 傅俊偉,李興明,陳捷. 基于背離路徑的 Kth最短路徑實用搜索算法[J].計算機(jī)技術(shù) 與發(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.