基于鏈路失效模型的多級電力業務路由規劃

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

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

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

1 引言

智能電網是一種自動化的綜合應用型電力網絡，相比于傳統網絡，智能電網在電力業務傳輸的各個環節都表現得更加自動化、智能化[1]，并且在各個環節都引入了大量新業務。隨著現代社會的發展，未來電網將會面臨電力業務數量急劇增長，業務種類不盡相同的情況，這對網絡傳輸的可靠性提出了更高的要求。目前主流的傳輸技術是光傳送網(Optical Transmission Network, OTN)技術，其融合了傳統同步數字體系(Synchronous Digital Hierarchy, SDH)和波分復用(Wavelength Division Multiplexing, WDM)的優勢[2]，在能夠提供巨大傳輸容量的情況下，依然具有強大的保護和監控管理等能力。OTN技術可以在很大程度上提高電網運行的可靠性[3]，但網絡資源是有限的，在面對未來龐大的業務量和業務種類時，必須優化業務路由規劃方法，提高網絡性能。

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

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

(2)建立鏈路失效模型，依據業務等級調整模型的目標函數并分別進行路由分配，實現不同電力業務在路由規劃時的分級處理。

2 電力業務可靠性需求分析

2.1 電力業務可靠性需求定性分析

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

2.2 電力業務可靠性需求定量分析

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

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

使用層次分析法量化電力業務可靠性的具體步驟是：

首先，建立層次結構模型。層次結構模型分為3層，最上層是目標層，中間層是指標層，最下層是方案層。此處將目標層設置為電力業務需求權重，將指標層設置為可靠性，將方案層設置為具體電力業務，并給電力業務進行編號。層次結構模型如圖1所示。

圖1 電力業務可靠性需求層次結構模型

其次，確定權重賦值標度并構造判斷矩陣。權重賦值標度根據表1定性分析結果進行取值，常用標度為1/9～9，如表2所示，其中i和j分別代表兩種不同的電力業務的編號。

表1 各電力業務的實時性與可靠性要求

表2 電力業務重要度賦值方法

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

表3 判斷矩陣構造方法

根據經典9種電力業務可靠性需求構造的判斷矩陣，結果如表4所示。

表4 具體電力業務可靠性需求的判斷矩陣

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

表5 可靠性需求權重賦值結果

3 光纖鏈路失效模型

3.1 光纖鏈路失效概率

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

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

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

3.2 基于鏈路失效的函數模型

研究光傳送網路徑規劃問題時，國內外研究手段主要集中于最優化函數建模與規劃優化算法等方面[12–14]。在實際運用中，這兩者通常是結合使用，首先進行最優化函數建模，再將函數作為約束條件加入到規劃優化算法中。最優化函數建模是利用網絡不確定因子，對規劃問題建立數學模型，確立函數關聯與限制條件，并給出相應目標函數，通過優化算法求解使得目標函數最優。

在給電力業務分配波道資源時，電力業務的可靠性需求與鏈路失效情況都是網絡不確定因子，二者需要結合考慮，將可靠性需求高的業務分配到失效風險較低的鏈路上，將可靠性需求較低的業務分配到失效風險相對較高的鏈路上。依據此思想，目標函數設計為

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

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

基于以上的目標函數，結合K最短路徑算法(K-Shortest Pathes algorithm, KSP)設計電力業務規劃算法，以實現均衡網絡負載，提高全網可靠性的目的。

4 算法設計

4.1 算法描述

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

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

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

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

步驟4 在第3步保留下來的路徑中，按照目標函數計算得到使目標函數值最大的路徑。該路徑即為鏈路失效模型下面向可靠性的業務路由規劃方法選取得到的最優路徑。

步驟5 檢查所有接入請求是否都已進行路由規劃。若沒有全部規劃好業務路徑則跳轉到第2步，若已經全部歸好業務路徑則轉到第6步。

步驟6 所有電力業務都完成路由規劃，規劃算法結束。

算法流程圖如圖2所示。

圖2 算法流程圖

4.2 算例分析

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

圖3 NSFNET網絡拓撲結構

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

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

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

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

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

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

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

圖7給出了單鏈路失效情況下，各路由算法在業務數量不同時資源利用率的對比。單鏈路失效情況下的資源利用率變化趨勢與多鏈路情況下基本一致。總體而言，在業務數量相同時，單鏈路失效情況下的資源利用率略高于多鏈路失效情況，這與鏈路失效對網絡阻塞率的影響有關。

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

5 結束語

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