胡朝平，易穎

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

0 引言

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

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

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

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

2 問(wèn)題分析及描述

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

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

與實(shí)際值的偏差則為：

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

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

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

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

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

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

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

3 流程圖及算法描述

該路由算法可以理解為一種約束路由算法（CSPF），兩個(gè)具體的約束因子：?jiǎn)蜗蚵窂綍r(shí)延Delay<8ms,雙向路徑時(shí)延差D<0.333ms；具體算法步驟描述為：

步驟1：

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

步驟2：

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

步驟3：

修改相應(yīng)圖的權(quán)值，使用Dijkstra算法計(jì)算T-S的最短路徑,記錄路徑和時(shí)延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則用背離路徑方法計(jì)算T-S下一條路徑（該路徑是時(shí)延僅大于Delay2的次短路徑），若結(jié)果非空，則轉(zhuǎn)步驟3；若結(jié)果為空，則轉(zhuǎn)步驟5。若Delay1

步驟5：

圖1 算法流程圖

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

在這個(gè)算法中，求解次短時(shí)延路徑時(shí)運(yùn)用了背離路徑的思想。假設(shè)vi為源節(jié)點(diǎn),vj為目的節(jié)點(diǎn).(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é)點(diǎn)相同，在vn+1處開(kāi)始不同，則稱路徑vi,v1,v2,,…vn,vj由vi,v’1,v’2,…n,vj在vn+1處背離得到, vn+1為被背離節(jié)點(diǎn), v’n+1為背離節(jié)點(diǎn)。背離路徑的定義:路徑vi,v1,v2,v3,…vn,vj以vn+1為被背離節(jié)點(diǎn),以v’n+1為背離節(jié)點(diǎn)的所有背離路徑中有一條最短,它由vi,v1,v2,v3,…vn,+鏈路vn,vn+1,vn+2,…vj的最短路徑得到。以v’n+1為背離節(jié)點(diǎn)的路徑專指這條最短路徑，而非以為v’n+1背離節(jié)點(diǎn)的其它路徑。在求v’n+1到vj的最短路徑時(shí),應(yīng)刪除與節(jié)點(diǎn)vi,v1,v2,v3,…vn有關(guān)的鏈路,再利用Dijkstra 算法求最短路徑,以避免拼接而成的背離路徑產(chǎn)生環(huán)路。

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

4 仿真結(jié)果

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

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

圖3 節(jié)點(diǎn)屬性圖

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

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

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