基于鏈路失效模型的多級電力業(yè)務(wù)路由規(guī)劃

楊淑娜 許嘉麗 楊鴻珍 趙玉虎 池 灝*

①(杭州電子科技大學(xué)通信工程學(xué)院 杭州 310018)

②(國網(wǎng)浙江省電力有限公司信息通信分公司 杭州 310018)

1 引言

智能電網(wǎng)是一種自動化的綜合應(yīng)用型電力網(wǎng)絡(luò)，相比于傳統(tǒng)網(wǎng)絡(luò)，智能電網(wǎng)在電力業(yè)務(wù)傳輸?shù)母鱾€環(huán)節(jié)都表現(xiàn)得更加自動化、智能化[1]，并且在各個環(huán)節(jié)都引入了大量新業(yè)務(wù)。隨著現(xiàn)代社會的發(fā)展，未來電網(wǎng)將會面臨電力業(yè)務(wù)數(shù)量急劇增長，業(yè)務(wù)種類不盡相同的情況，這對網(wǎng)絡(luò)傳輸?shù)目煽啃蕴岢隽烁叩囊?。目前主流的傳輸技術(shù)是光傳送網(wǎng)(Optical Transmission Network, OTN)技術(shù)，其融合了傳統(tǒng)同步數(shù)字體系(Synchronous Digital Hierarchy, SDH)和波分復(fù)用(Wavelength Division Multiplexing, WDM)的優(yōu)勢[2]，在能夠提供巨大傳輸容量的情況下，依然具有強大的保護和監(jiān)控管理等能力。OTN技術(shù)可以在很大程度上提高電網(wǎng)運行的可靠性[3]，但網(wǎng)絡(luò)資源是有限的，在面對未來龐大的業(yè)務(wù)量和業(yè)務(wù)種類時，必須優(yōu)化業(yè)務(wù)路由規(guī)劃方法，提高網(wǎng)絡(luò)性能。

在未來電網(wǎng)結(jié)構(gòu)復(fù)雜化、業(yè)務(wù)多樣化的發(fā)展趨勢的驅(qū)動下[4]，網(wǎng)絡(luò)可靠性成為網(wǎng)絡(luò)性能評估的關(guān)鍵。影響網(wǎng)絡(luò)可靠性的主要因素包括網(wǎng)絡(luò)節(jié)點失效和光纖鏈路失效，其發(fā)生具有隨機性。相比于網(wǎng)絡(luò)節(jié)點失效，導(dǎo)致光纖鏈路失效的因素更多，如架設(shè)光纜的地理環(huán)境、氣候、光纜的長度以及人為因素等，都有可能導(dǎo)致鏈路失效而發(fā)生業(yè)務(wù)中斷，造成巨大的業(yè)務(wù)損失。因此，現(xiàn)有的提升網(wǎng)絡(luò)性能的方法之一就是基于鏈路失效提出優(yōu)化的電力業(yè)務(wù)路由規(guī)劃方法，通過合理的路由選擇，均衡網(wǎng)絡(luò)負載，提高網(wǎng)絡(luò)整體的可靠性。隨著現(xiàn)代社會的發(fā)展以及各種應(yīng)用的出現(xiàn)，網(wǎng)絡(luò)業(yè)務(wù)多樣性將成為網(wǎng)絡(luò)性能優(yōu)化時需考慮的一項重要問題[5–7]。然而，目前大部分的基于鏈路失效的路由算法均聚焦于失效鏈路的數(shù)量，忽視了網(wǎng)絡(luò)業(yè)務(wù)的多樣性在路由規(guī)劃中的影響[8,9]。面對種類繁多的電力業(yè)務(wù)，網(wǎng)絡(luò)規(guī)劃者需針對不同的業(yè)務(wù)進行規(guī)劃。因此，本文對電力業(yè)務(wù)的可靠性需求進行分析，并提出基于鏈路失效模型的多級電力業(yè)務(wù)路由規(guī)劃方法。本文所提業(yè)務(wù)路由規(guī)劃算法在傳統(tǒng)業(yè)務(wù)路由規(guī)劃算法的基礎(chǔ)上進行了創(chuàng)新，其創(chuàng)新點包括：

(1)采用層次分析法對電力業(yè)務(wù)可靠性需求進行定量分析，為各電力業(yè)務(wù)設(shè)置不同重要度等級；

(2)建立鏈路失效模型，依據(jù)業(yè)務(wù)等級調(diào)整模型的目標(biāo)函數(shù)并分別進行路由分配，實現(xiàn)不同電力業(yè)務(wù)在路由規(guī)劃時的分級處理。

2 電力業(yè)務(wù)可靠性需求分析

2.1 電力業(yè)務(wù)可靠性需求定性分析

智能電網(wǎng)中的電力業(yè)務(wù)主要分為生產(chǎn)信息類業(yè)務(wù)和管理業(yè)務(wù)。生產(chǎn)業(yè)務(wù)主要包括繼電保護業(yè)務(wù)[10]、安全穩(wěn)定裝置業(yè)務(wù)以及調(diào)度電話業(yè)務(wù)等，這些業(yè)務(wù)的作用是通過監(jiān)測電網(wǎng)的實時狀態(tài)以指導(dǎo)電網(wǎng)的運行，保障電網(wǎng)運作的可靠性，因此，生產(chǎn)類業(yè)務(wù)的實時性需求與可靠性需求都較高。管理業(yè)務(wù)主要包括會議電視業(yè)務(wù)、行政電話業(yè)務(wù)等，其作用是傳輸網(wǎng)絡(luò)的管理控制信息，相比于生產(chǎn)業(yè)務(wù)，管理業(yè)務(wù)的實時性需求與可靠性需求相對較低。本文選取線路保護、保護管理系統(tǒng)、調(diào)度電話、調(diào)度自動化、視頻會議、會議電視、行政電話、配電自動化、國家電網(wǎng)資源計劃系統(tǒng)(State Grid-Enterprise Rescource Planning, SG-ERP)業(yè)務(wù)等9種具有代表性的電力業(yè)務(wù)進行可靠性分析，表1給出了針對該9種業(yè)務(wù)可靠性需求的定性分析。

2.2 電力業(yè)務(wù)可靠性需求定量分析

電力業(yè)務(wù)可靠性需求的定性分析只能作為業(yè)務(wù)間可靠性相互比較的參考依據(jù)，某種程度上，定性分析是為了后續(xù)更為準(zhǔn)確地進行定量分析。通過量化手段將定性分析的結(jié)果量化為直觀的數(shù)據(jù)，更有利于電力業(yè)務(wù)可靠性需求與路徑規(guī)劃算法的結(jié)合。

本文采用層次分析法作為量化手段。層次分析法是一種常用的定性與定量結(jié)合的決策手段，該方法根據(jù)決策者的經(jīng)驗判斷方案層中各個方案針對同一指標(biāo)的相對重要程度，并合理地給出相應(yīng)的重要度權(quán)重值，最后根據(jù)權(quán)重值求出各個方案的優(yōu)劣次序。層次分析法具有系統(tǒng)性、簡便性以及實用性的特點，其中，系統(tǒng)性是指層次分析法將對象視作一個系統(tǒng)，對該系統(tǒng)通過分解、比較、判斷等操作完成決策；實用性是指層次分析法的應(yīng)用范圍十分廣泛，可以比較有效地處理許多難以直接用定量方法解決的實際問題；簡便性是指層次分析法計算簡便，容易被決策者了解和掌握。

使用層次分析法量化電力業(yè)務(wù)可靠性的具體步驟是：

首先，建立層次結(jié)構(gòu)模型。層次結(jié)構(gòu)模型分為3層，最上層是目標(biāo)層，中間層是指標(biāo)層，最下層是方案層。此處將目標(biāo)層設(shè)置為電力業(yè)務(wù)需求權(quán)重，將指標(biāo)層設(shè)置為可靠性，將方案層設(shè)置為具體電力業(yè)務(wù)，并給電力業(yè)務(wù)進行編號。層次結(jié)構(gòu)模型如圖1所示。

圖1 電力業(yè)務(wù)可靠性需求層次結(jié)構(gòu)模型

其次，確定權(quán)重賦值標(biāo)度并構(gòu)造判斷矩陣。權(quán)重賦值標(biāo)度根據(jù)表1定性分析結(jié)果進行取值，常用標(biāo)度為1/9～9，如表2所示，其中i和j分別代表兩種不同的電力業(yè)務(wù)的編號。

表1 各電力業(yè)務(wù)的實時性與可靠性要求

表2 電力業(yè)務(wù)重要度賦值方法

構(gòu)造判斷矩陣時要滿足Cij>0；Cij=1/Cji；Cii=1 ， 判斷矩陣構(gòu)造如表3所示，其中Ci(i=1,2,...,n)和Cj(j=1,2,...,n)分別代表兩種不同的電力業(yè)務(wù)，Bk代表可靠性重要度比較結(jié)果。

表3 判斷矩陣構(gòu)造方法

根據(jù)經(jīng)典9種電力業(yè)務(wù)可靠性需求構(gòu)造的判斷矩陣，結(jié)果如表4所示。

表4 具體電力業(yè)務(wù)可靠性需求的判斷矩陣

最后，對判斷矩陣進行計算得到業(yè)務(wù)可靠性權(quán)重賦值結(jié)果。具體的計算方法為：對判斷矩陣進行列向歸一化，對得到的新矩陣進行求和。最后再次進行列向歸一化即可得到各電力業(yè)務(wù)的可靠性需求權(quán)重，權(quán)重計算結(jié)果如表5所示。

表5 可靠性需求權(quán)重賦值結(jié)果

3 光纖鏈路失效模型

3.1 光纖鏈路失效概率

目前骨干網(wǎng)中的光纜大致分為3種，分別是光纖復(fù)合架空地線(OPtical fiber composite overhead Ground Wire, OPGW)、全介質(zhì)自承式光纜(All Dielectric Self-Supporting optical fiber cable,ADSS)以及其他普通光纜。這3種光纜的可靠性性能略有差異，OPGW的可靠性略高于ADSS光纜的可靠性，普通光纜的可靠性相對最低，因此目前光傳輸網(wǎng)中主要使用OPGW光纜。在大多數(shù)已有的研究中都將鏈路失效概率設(shè)置為固定值[11]，實際上，鏈路失效概率是動態(tài)的，由鏈路長度、光纖失效概率及光纖修復(fù)概率共同決定。由于鏈路發(fā)生故障后可以進行修復(fù)以恢復(fù)至正常工作狀態(tài)，因此計算鏈路失效概率實際上等同于計算鏈路的可用性?？捎眯允侵缚删S修產(chǎn)品在規(guī)定的條件下使用時具有或維持其功能的能力，常用A來表示，其計算表達式為

其中，平均失效前時間(Mean Time To Failure,MTTF)表示系統(tǒng)無故障運行的平均值，平均恢復(fù)前時間(Mean Time To Restoration, MTTR)表示系統(tǒng)從故障發(fā)生到維修結(jié)束時間段的平均值，平均故障間隔時間(Mean Time Between Failures, MTBF)表示兩次故障發(fā)生時間之間的時間段的平均值

其中，表達式(3)中的λ表示每千米光纜的平均失效概率，表達式(4)中的μ表示每千米光纜的平均修復(fù)概率。因此，長度為L的第k條光纖的失效概率計算公式為

3.2 基于鏈路失效的函數(shù)模型

研究光傳送網(wǎng)路徑規(guī)劃問題時，國內(nèi)外研究手段主要集中于最優(yōu)化函數(shù)建模與規(guī)劃優(yōu)化算法等方面[12–14]。在實際運用中，這兩者通常是結(jié)合使用，首先進行最優(yōu)化函數(shù)建模，再將函數(shù)作為約束條件加入到規(guī)劃優(yōu)化算法中。最優(yōu)化函數(shù)建模是利用網(wǎng)絡(luò)不確定因子，對規(guī)劃問題建立數(shù)學(xué)模型，確立函數(shù)關(guān)聯(lián)與限制條件，并給出相應(yīng)目標(biāo)函數(shù)，通過優(yōu)化算法求解使得目標(biāo)函數(shù)最優(yōu)。

在給電力業(yè)務(wù)分配波道資源時，電力業(yè)務(wù)的可靠性需求與鏈路失效情況都是網(wǎng)絡(luò)不確定因子，二者需要結(jié)合考慮，將可靠性需求高的業(yè)務(wù)分配到失效風(fēng)險較低的鏈路上，將可靠性需求較低的業(yè)務(wù)分配到失效風(fēng)險相對較高的鏈路上。依據(jù)此思想，目標(biāo)函數(shù)設(shè)計為

其中，i是業(yè)務(wù)編號，p為業(yè)務(wù)數(shù)量，R(i)為業(yè)務(wù)i的可靠性重要度，由層次分析法得到；S(vi)為鏈路j失效前業(yè)務(wù)i所經(jīng)過路徑的可用性的乘積，其計算公式為

R(vj)為失效鏈路j在全網(wǎng)中的可靠性權(quán)重，其計算公式為

基于以上的目標(biāo)函數(shù)，結(jié)合K最短路徑算法(K-Shortest Pathes algorithm, KSP)設(shè)計電力業(yè)務(wù)規(guī)劃算法，以實現(xiàn)均衡網(wǎng)絡(luò)負載，提高全網(wǎng)可靠性的目的。

4 算法設(shè)計

4.1 算法描述

電力通信OTN的業(yè)務(wù)路由規(guī)劃是在網(wǎng)絡(luò)基本配置、光纖鏈路失效概率、電力業(yè)務(wù)可靠性需求等參數(shù)已知的情況下進行的。鏈路失效模型下面向可靠性的業(yè)務(wù)路由規(guī)劃方法分為以下6個步驟：

步驟1 網(wǎng)絡(luò)預(yù)處理。初始化網(wǎng)絡(luò)拓撲圖參數(shù)，根據(jù)OTN網(wǎng)絡(luò)中的實際情況，分別對網(wǎng)絡(luò)拓撲中每條鏈路所包含的波長按順序標(biāo)號，采用層次分析法計算接入網(wǎng)絡(luò)的業(yè)務(wù)的可靠性需求。

步驟2 接收業(yè)務(wù)連接請求，并采用基于物理鏈路長度最短的K-SP算法為到達的電力業(yè)務(wù)預(yù)選出K條(K>1)候選路徑。此處鏈路長度隨著K的增大而增加，因此K的取值取決于實際成本預(yù)算。K=1時為最短路徑算法取得的最優(yōu)路徑。

步驟3 對第2步所找到的K條最短路徑，用波長分配路由算法取最優(yōu)路徑。用首次命中法判斷鏈路中可用波長，保留能完全建立連接的路徑，拋棄不能完全建立連接的路徑。若K條路徑都不能完全連接，則阻塞該業(yè)務(wù)并跳轉(zhuǎn)至第2步。

步驟4 在第3步保留下來的路徑中，按照目標(biāo)函數(shù)計算得到使目標(biāo)函數(shù)值最大的路徑。該路徑即為鏈路失效模型下面向可靠性的業(yè)務(wù)路由規(guī)劃方法選取得到的最優(yōu)路徑。

步驟5 檢查所有接入請求是否都已進行路由規(guī)劃。若沒有全部規(guī)劃好業(yè)務(wù)路徑則跳轉(zhuǎn)到第2步，若已經(jīng)全部歸好業(yè)務(wù)路徑則轉(zhuǎn)到第6步。

步驟6 所有電力業(yè)務(wù)都完成路由規(guī)劃，規(guī)劃算法結(jié)束。

算法流程圖如圖2所示。

圖2 算法流程圖

4.2 算例分析

本算例采用的網(wǎng)絡(luò)拓撲結(jié)構(gòu)是由21條鏈路、14個節(jié)點組成的國家科學(xué)基金會網(wǎng)絡(luò)(National Science Foundation NETwork, NSFNET)，如圖3所示，其中標(biāo)注了網(wǎng)絡(luò)中每條鏈路的長度(單位為km)。

圖3 NSFNET網(wǎng)絡(luò)拓撲結(jié)構(gòu)

在該網(wǎng)絡(luò)中對第2節(jié)選取的9種經(jīng)典電力業(yè)務(wù)進行路由規(guī)劃。本文中，K-SP算法的K取值為5，所有光纖鏈路具備雙向傳輸能力，假設(shè)每條光纖包含32個波長，每種業(yè)務(wù)的帶寬需求均為1個波長。并且，每千米光纜的MTBF取值為 8 .761×105h，每千米光纜的MTTR取值為13.8 h，即每千米光纜失效 率λ 為 1.1416×10?6(1/h) ，光 纜修 復(fù) 率μ為0.0725(1/h)。網(wǎng)絡(luò)中失效鏈路、連接請求中的業(yè)務(wù)種類、源節(jié)點和目的節(jié)點均由隨機函數(shù)生成，業(yè)務(wù)種類的選取滿足均勻分布。本文對Dijkstra算法、路由與波長分配(Routing and Wavelength Assignment, RWA)算法、文獻[15]中的基于網(wǎng)絡(luò)風(fēng)險的路由分配(Risk-Routing and Wavelength Assignment, R-RWA)算法、文獻[16]中的跨接鏈路算法(Straddling Link Algorithm, SLA)以及所提出算法分別進行仿真。其中，Dijkstra算法是一種經(jīng)典的單源最短路徑算法，該算法以源點為中心向外層層擴展，直到擴展到終點，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑，現(xiàn)有的許多路由規(guī)劃算法都是在該算法的基礎(chǔ)加以優(yōu)化；RWA算法是一種經(jīng)典的路由與波長分配算法，通常分解為選路和波長分配兩個子問題，選路問題又可以分為尋找路由和選擇路由問題，波長分配問題也可以分為尋找波長和選擇波長問題；R-RWA算法是一種基于網(wǎng)絡(luò)風(fēng)險的RWA算法，該算法通過降低網(wǎng)絡(luò)的最大風(fēng)險，抑制鏈路失效對全網(wǎng)業(yè)務(wù)的影響；SLA算法是一種經(jīng)典啟發(fā)式P圈構(gòu)造算法，可以快速構(gòu)造基本圈，該算法用于研究鏈路失效情況下網(wǎng)絡(luò)的生存性問題。以上4種算法均可用于研究鏈路失效情況下的電力業(yè)務(wù)路由規(guī)劃問題，并且都具有一定的代表性，本文將通過網(wǎng)絡(luò)阻塞率、資源利用率[17]兩個指標(biāo)來衡量4種算法以及本算法的優(yōu)劣性，驗證本算法的有效性。

圖4給出了多鏈路失效情況下，各路由算法在業(yè)務(wù)數(shù)量不同時阻塞率的對比。由圖4可見，5種算法的阻塞率均隨著業(yè)務(wù)數(shù)量的增大而上升。在業(yè)務(wù)數(shù)量小于等于50個時，Dijkstra算法、RWA算法以及R-RWA算法阻塞率非常低，SLA算法與本算法的阻塞率為0。這是由于在業(yè)務(wù)數(shù)量較少時，網(wǎng)絡(luò)中的可用資源十分豐富，各算法的約束條件對路由選擇的限制表現(xiàn)得并不明顯。當(dāng)業(yè)務(wù)數(shù)量大于50個時，由于個別鏈路出現(xiàn)波長資源用盡的情況，SLA算法與本算法也開始發(fā)生阻塞。當(dāng)業(yè)務(wù)數(shù)量大于100個時，5種算法的阻塞率呈現(xiàn)出明顯的差別，本算法阻塞率持續(xù)處于最低，這是由于在前期網(wǎng)絡(luò)可用資源比較豐富時，本算法考慮了鏈路失效情況，合理避免了因鏈路故障而發(fā)生的阻塞事件，并且根據(jù)不同種類電力業(yè)務(wù)對網(wǎng)絡(luò)的具體需求為其分配路徑，使電力業(yè)務(wù)在網(wǎng)絡(luò)中較為均勻地分布，因此本算法在對可用資源進行合理利用的同時，也將阻塞率控制在較低水平。SLA算法的阻塞率略高于本算法的阻塞率，這是由于SLA算法沒有均衡負載策略，對所有接入請求進行無差別處理，雖然SLA算法有備份策略，但備份路徑僅與工作路徑有關(guān)，與業(yè)務(wù)類型無關(guān)，因此網(wǎng)絡(luò)負載較大時，容易出現(xiàn)負載不均衡的情況，導(dǎo)致阻塞率略高于本算法阻塞率。RRWA算法在RWA算法的基礎(chǔ)上，考慮了網(wǎng)絡(luò)業(yè)務(wù)與鏈路工作狀態(tài)的依賴關(guān)系，但沒有備份策略和多級業(yè)務(wù)路由分配策略，因此R-RWA算法的阻塞率介于RWA算法與SLA算法之間。對于阻塞率較高的Dijkstra算法和RWA算法，兩者僅考慮了在資源分配時最簡單的影響因素，分別是路徑長度和可用波長資源，因此在網(wǎng)絡(luò)規(guī)劃時容易出現(xiàn)負載集中于某條鏈路或某個節(jié)點的情況，導(dǎo)致阻塞率較大。

圖4 多鏈路失效時各算法阻塞率

圖5給出了單鏈路失效情況下，各路由算法在業(yè)務(wù)數(shù)量不同時阻塞率的對比。在單鏈路情況可以看作多鏈路失效情況的一種特例，因此單鏈路失效情況下5種算法阻塞率變化的情況和引起變化的原因與多鏈路失效時相同。二者的區(qū)別在于單鏈路失效時不同算法在不同業(yè)務(wù)數(shù)量下的阻塞率略低于多鏈路失效時不同算法的阻塞率，原因在于多鏈路失效情況下由鏈路失效引起阻塞的可能性略高于單鏈路失效情況。

圖5 單鏈路失效時各算法阻塞率

圖6給出了多鏈路失效情況下，各路由算法在業(yè)務(wù)數(shù)量不同時資源利用率的對比。這項指標(biāo)代表當(dāng)前網(wǎng)絡(luò)中已占用的波長資源在網(wǎng)絡(luò)中整體波長資源的占有率。圖6中顯示，5種算法的資源利用率隨業(yè)務(wù)量的增大而上升，這是由于隨著業(yè)務(wù)請求數(shù)量的增多，網(wǎng)絡(luò)需要提供更多的可用通道資源。當(dāng)業(yè)務(wù)數(shù)量大于等于175個時，5種算法的資源利用率上升趨勢逐漸平緩，因為當(dāng)業(yè)務(wù)數(shù)量較大時，網(wǎng)絡(luò)中的可用資源減少，并且網(wǎng)絡(luò)流量未能及時疏導(dǎo)，導(dǎo)致業(yè)務(wù)發(fā)生阻塞，能夠成功建立連接的請求逐漸減少。本算法在不同的業(yè)務(wù)數(shù)量下，資源利用率高于其余4種算法，這是由于本算法根據(jù)不同種類業(yè)務(wù)的具體需求來分配路由，使網(wǎng)絡(luò)中的業(yè)務(wù)較為均勻地分布，減少阻塞的發(fā)生，提高連接的成功率，并且由于本算法中業(yè)務(wù)種類的選取符合均勻分布，在業(yè)務(wù)數(shù)量較大時本算法的有效性更為突出。

圖6 多鏈路失效時各算法資源利用率

圖7給出了單鏈路失效情況下，各路由算法在業(yè)務(wù)數(shù)量不同時資源利用率的對比。單鏈路失效情況下的資源利用率變化趨勢與多鏈路情況下基本一致?？傮w而言，在業(yè)務(wù)數(shù)量相同時，單鏈路失效情況下的資源利用率略高于多鏈路失效情況，這與鏈路失效對網(wǎng)絡(luò)阻塞率的影響有關(guān)。

圖7 單鏈路失效時各算法資源利用率

5 結(jié)束語

本文基于鏈路失效情況提出一種面向可靠性的多級電力業(yè)務(wù)路由規(guī)劃算法，給出了鏈路失效下的函數(shù)模型，利用該模型以及多級業(yè)務(wù)分配策略對規(guī)劃路徑進行約束，均衡網(wǎng)絡(luò)負載，降低網(wǎng)絡(luò)阻塞率，提高資源利用率，實現(xiàn)全網(wǎng)可靠性的提高。在電力業(yè)務(wù)數(shù)量急劇增多，業(yè)務(wù)種類不盡相同的發(fā)展趨勢下，本文所提出的電力業(yè)務(wù)路徑規(guī)劃策略對網(wǎng)絡(luò)性能的提升具有一定的參考價值，未來可以從業(yè)務(wù)不同需求的角度出發(fā)，基于鏈路失效構(gòu)建多種需求的函數(shù)模型，使電力業(yè)務(wù)路由規(guī)劃更具有區(qū)分性，網(wǎng)絡(luò)能夠可靠傳輸更多的業(yè)務(wù)。