基于最小溝道的電網通信業務路由優化及應用

秦亞梅，汪 輝，李振偉，張 聞

(1.電子科技大學數學科學學院 成都 611731；2.國網安徽省電力有限公司信息通信分公司 合肥 230022)

電力通信網絡主要由SDH（synchronous digital hierarchy）光傳輸系統和OTN（optical transport network）光傳輸系統組成，其與電力系統的生產、調度、運行、管理、溝通、協調等有著密切的聯系[1]。因此電力通信系統對其使用的業務路由規劃有嚴格的風險管控要求[2]。目前安徽電網業務路由的調整及新增，基本上都是基于業務路由最短路徑原則[3]進行決策，缺乏有效的評估工具和仿真測試條件。上述處理原則給城域光網絡業務的穩定性帶來較大隱患（業務主用路由和備用路由共溝道）。同時，國家相關法律明文規定：公共區域不得隨意破土施工，也導致城區光纜在敷設時存在共溝道（井）現象，因此亟需研究適合城域光網絡SDH 傳輸系統的業務路由優化算法及仿真測試工具，為電力網絡建設與業務運行方式優化提供理論參考和數據支撐。

目前電力通信業務通信方式主要是采用點對點的通信模式，為了使業務可靠穩定地傳輸，通常需要對業務路由（通道）使用相應的保護策略。保護策略主要分為通道保護和復用段保護。業務通道保護配置一般要求其主備路由滿足共享風險鏈路組（shared risk link groups, SRLG）分離原則[4-6]。SRLG物理含義為共享相同傳輸設備、光纜、管道（溝道井）等物理資源的一組鏈路。本文主要研究城域光網絡中業務的主備路由在無法嚴格滿足SRLR 分離原則時，如何最小化其共溝道數量問題。

近年來，電力通信網絡的業務路由規劃及優化問題引起了國內外學者廣泛地關注。文獻[7]提出基于強化學習的多條件約束的業務路由優化算法。雖然考慮了鏈路風險權值、節點風險權值、網絡帶寬狀態，但該模型不能解決物理光路共溝道情況下的業務路由規劃問題。文獻[8]設計出了光網絡規劃及仿真軟件，但該軟件偏向光傳輸的物理特性仿真分析以及網絡建設成本控制。文獻[9]提出了一種基于混合整數線性規劃的多播路由與保護聯合優化算法，在滿足共享風險鏈路組條件約束下，提高了業務通信信道資源利用率，但并不適用于解決本文提出的工程問題。文獻[10]提出了一種高斯-塞德爾迭代（Gauss-Seidel method）算法來解決路由規劃問題，但該算法主要適用于基于TCP/IP 傳輸協議的路由規劃，無法應用于電接口的業務路由規劃。文獻[11]對電力通信SDH 傳輸系統的自愈技術進行了深入研究，設計出一款基于B/S 架構的SDH 傳輸系統的自愈模型仿真系統，但它主要關注于SDH 傳輸系統功能的軟件實現。文獻[12]提出了多重不相交路徑算法（multiple disjoint path algorithm, MDPAlg），該算法相比于迪杰斯特拉算法（Dijkstra）具有更高的運算速度，適合于大型網絡拓撲應用，但是并沒有對電力實際的業務場景進行驗證，只是從理論上證明了其計算復雜度與可行性，并不適用于電接口的業務路由規劃。文獻[13]提出SDH 網絡拓撲單元概念，并從網絡風險值和網絡均衡值等方面來衡量SDH網絡風險與可靠性，但未給出具體的業務路由優化實施算法。文獻[14]提出了基于K 條最短路徑（K-shortest pathes,KSP）的風險均衡的業務路由分配算法，在實施的過程中會使用Dijkstra 算法選擇K條備選路由，但算法選擇的主備路由可能存在共節點或共鏈路風險。文獻[15]提出了基于共享鏈路組與風險均衡的路由優化算法，其算法效果易受業務重要度指標的影響，對于城域光網絡該指標項不易獲取。

綜上所述，開展適合城域光網絡的電網業務路由優化技術研究是非常必要的。目前安徽電力通信網絡的日常運維和業務配置較為簡單，主要基于最短路徑的原則進行業務路由安排，而此原則會導致業務的主備路由經過許多相同的光纜溝道井。同時城市的基礎建設也很容易破壞電纜溝道井，如修建地鐵、修建高架橋、修建道路、修建下水道、修建燃氣溝道、自來水溝道改造、市政綠化施工等，給城域電力通信光纜及其承載的業務帶來了諸多隱患。因此本文提出了基于最小光纜溝道的電網通信業務路由優化算法，算法使用融合排序的DFS 方法，在業務路由無法嚴格滿足SRLG 分離原則時，最小化業務主備路由共溝道的數量。基于SRLG 的深度優先搜索算法（DFS-SRLG）能避免主備路由共鏈路和共節點風險，降低業務中斷次數，對城域光拓撲調整及業務故障定位也具有重要的參考價值。同時，業務路由優化方法有利于提高業務管理人員的辦事效率，提升調控運維人員事故處理能力，降低人工安排業務出錯概率。最后，本算法在安徽電網的行政電話業務進行了應用，相對于默認的KSP 算法，顯著降低了電話業務中斷次數，提高了業務穩定性，對電網系統的穩定、安全、可靠運行具有重要的理論指導意義和實際應用價值。

1 業務路由優化算法

1.1 優化算法建模

1738 年，數學家歐拉解決了柯尼斯堡問題并創立圖論。隨著計算機的快速發展，圖論已成為一門應用十分廣泛的重要學科。人們也逐漸開始使用圖論理論解決生活中遇到的實際生產問題。本文使用圖論模型來解決基于最小溝道的電力通信業務主備路由優化問題。由于市政限制，城市內不能隨意開挖溝道敷設光纜，導致部分光纜同溝道敷設。伴隨著國家經濟的快速發展，城市基礎建設也在加快步伐。城市建設的過程中難免會破壞部分光纜，導致部分電力業務中斷，因此如何盡可能降低業務中斷次數、合理調整光網絡拓撲、科學規劃業務主備路由等問題急需解決。以安徽省內某市城域光網絡傳輸拓撲為例進行說明，如圖1 所示。為了保留拓撲連接關系和計算方便，圖中簡化了實際光纜鋪設走向以及溝道位置坐標情況。圖中，任意兩個頂點之間代表一條完整的光路信息，忽略了兩段光纜纖芯中間跳接情況，通信站代表光傳輸設備及光路傳輸方向。

圖1 城域光路拓撲圖

本文使用無向圖對城域光路拓撲圖進行建模。為了解決多重邊問題即區分通信站3 至通信站10 兩條光路信息、通信站3 至通信站4 兩條光路信息，任選其中一個光路中插入新的頂點信息，即引入虛擬節點方法解決無向圖的多重邊問題，最終簡化后的拓撲模型如圖2 所示。

圖2 光路拓撲圖無向圖模型

假設光網絡拓撲圖使用一個賦權無向圖連通圖G=(V,E,W)描 述，其中，V表示G中所有的頂點集合：V(G)={v1,v2,···v17}。 |V|=17, |E|=32分別表示圖G的頂點和邊數。無向圖G=(V,E,W)邊的集合可以 描 述 成E(G)={v1v3,v1v9,v1v14···,v13v15},vivj=vjvi,i,j∈V,W是G所有邊對應權值的集合，其權值大小表示對應光路編號W={ω1,3,ω1,4,ω1,9,···,ω13,14,ω13,15}， 如 ω1,3=2表示節點1 至節點3 對應的光路編號是2，權值為0 表示該段光路使用尾纖直接連接，因為兩個通信機房距離彼此靠近。每條光路對應的溝道井號是ca, ?a∈E，具體數據格式請參照1.2 節。

在圖論中，頂點vi的 度是與vi直接關聯的邊的數目，記為：TD(vi)。 從頂點vi到頂點vj的路徑是一個頂點序列，路徑（路由）的長度等于從一個頂點vi到另一個頂點vj所經過邊的數量。第一個頂點到最后一個頂點相同的路徑稱為回路或環。序列中頂點不重復出現的路徑稱為簡單路徑。除了第一個頂點和最后一個頂點之外，其余頂點不重復出現的回路，稱為簡單回路或簡單環。本文研究的問題是：當新開通的業務主備路由無法嚴格滿足SRLR分離原則時，如何使業務主備路由經過相同編號的溝道井數量最少，其數學表達模型[16]為：

式中， ||表示求集合中元素數量。業務主備路由標簽集K={1,2}，表示由主用路由和備用路由組成的集合。當k=1時 ，默認是主用路由編號；k=2時，則是備用路由編號。 δ+(i)代表是所有從點出發的邊（弧）。由于頂點 { 16,17}是插入的虛擬頂點，所以圖中物理真實節點N={1,2,3,···,15}，N表示圖1 中通信機房組成的集合。 δ-(i)代 表所有進入頂點vi的邊。是 決策變量：路由k經過邊a，則為1，否則為0。o表示新開通業務的起始站點，d表示業務終止站點d∈N,o≠d≠i。δ+(S):{(i,j)|(i,j)∈E,i∈S,j∈S,i≠j}（是點集合）。式(2)表示主備路由不能同時經過相同的邊，即每個邊只能遍歷一次；式(3)表示如果頂點vi既不是起始點又不是終止點，那么進入該頂點流與出去流相等； 式(4)和式(5)表示主備路由必須從頂點o出 發，回到頂點d，不能停留在某個頂點（節點）；式(6)表示消除子回路，避免主用路由或者備用路由形成環路。式(7)表示整數約束。式(8)表示G中任意頂點至少有兩個直接關聯的邊。

定理 1 若一個無向連通圖G=(V,E)存在一個最大簡單環，且除最大簡單環上的其他頂點均與最大環相交，則在圖G=(V,E)中任意兩個頂點至少存在兩條路徑。

證明：除去最大簡單環包括的頂點，其余頂點的邊與最大環上的頂點可以組成新的環并與最大簡單環相交或者相切，由于環上任意兩點一定存在順時針和逆時針的兩條路徑，所以圖G=(V,E)中任意兩個頂點至少存在兩條路徑。

為了方便討論式(1)解的存在性，現對圖2 進行簡單處理，結果如圖3 所示，其中粗線是最大簡單環。下面對式(1)解的存在性進行討論。

圖3 包含最大環的光路拓撲圖

1）唯一解：如果無向連通圖G=(V,E)存在哈密頓圈[17]，且圖的頂點數量等于邊的數量 |V|=|E|，則式(1)只存在唯一解。

2）無解：如果無向連通圖G=(V,E)存 在|V|>|E|，則式(1)無解。

3）非唯一解：如果無向連通圖G=(V,E)存在最大簡單環，且經過除最大環上的頂點的環與最大環相交或者相切，則式(1)的解可能不唯一。當式(1)存在非唯一解時，由于主用路由和備用路由都是按照路徑長度進行升序排列的（默認情況下圖G=(V,E)中所有邊對應的長度是1），所以式(1)的解是基于主用路由和備用路由的路徑長度之和最小原則，選擇出合適的解。

1.2 數據預處理

由于網絡拓撲中光路以及光路對應光纜走向的電纜溝道井的數據都是使用文字進行描述，不利于算法數據處理，所以需要對光路和電纜溝道井建立一種專用的數據映射（全局編碼，使用Excel 的IFERROR(VLOOKUP(A2,IF({1,0},A $1 :A1,E $1:E1),2,0), MAX(E $1:E1)+1)函數嵌套進行處理，其功能是第一次出現的名稱按順序編號，非第一次出現的名稱使用第一次出現時所編的編號），即相同的數據（光路、溝道井）使用相同的編號。每段光路對應的溝道井編號最終映射成集合ca,?a∈E。拓撲之間的關聯信息使用鄰接矩陣Mnb進行表示。數據的存儲使用矩陣格式，光路與溝道位置具體的映射關系如圖4 所示。

圖4 數據預處理圖

1.3 算法描述

本文提出的DFS-SRLG 算法主要思想是：業務的主用路由和備用路由，在無法嚴格滿足SRLG分離原則時，最小化主備路由共溝道的數量。即使用DFS-SRLG 算法選出業務從起始點（通信站）到終止點（通信站）的所有路徑（路由），然后基于共溝道井數量最小化原則，選擇2 條路由分別作為業務的主用路由和備用路由。此算法不僅適用于電力通信城域網的業務路由規劃，也適用于光路網絡布局合理性的驗證，并以此作為優化的理論依據。DFS-SRLG 算法具體流程圖如圖5 所示。

圖5 DFS-SRLG 算法流程圖

DFS-SRLG 算法能在從起始點到終止點的所有路徑中，選擇出光路共溝道數量最少的2 條路由，并把第一條路徑作為主用路由，第二條路徑作為備用路由，同時展示出主備路由承載的光纜信息和經過的溝道井信息。此算法不僅極大地降低了整體業務中斷風險，還避免了工作路由優先[18]（active path first, APF）算法的缺陷，提升了網絡穩定性。

2 算法分析

2.1 算法仿真參數分析

本文基于安徽某個城市的城域電力網絡進行仿真實驗，具體光路拓撲圖如圖1 所示，其對應的圖模型如圖2 所示。該網絡包含15 個實際存在的中心站節點和30 條真實存在的光纜鏈路，并且每個節點的度大于等于2，所以從起始點至終止點肯定存在兩條路由。仿真分兩種情況進行討論：一是主備路徑最短優化（KSP 算法，網管運維人員默認使用的算法）；二是盡量滿足SRLG 分離原則，使主備路由所共溝道井數量最小化算法（DFS-SRLG）。選擇起始點通信站1 至終止點通信站3 的行政電話業務進行理論仿真分析，其主備路由信息的仿真結果如圖6 和圖7 所示。

圖7 DFS-SRLG 算法求解主備路由圖

使用KSP 算法主備路由共井數量為11 個，而使用DFS-SRLG 算法主備路由共井數量為1 個，業務主備路由對應的光纜信息如圖8 所示。從仿真結果可以看出使用DFS-SRLG 算法可以顯著降低主備路由共溝道數量，降低業務中斷風險。同時該結果也對光路拓撲進行合理規劃具有一定的指導意義，可根據業務主備路由共溝道井情況，結合檢修計劃調整共溝道井光路。

圖8 主備路由對應的光纜信息

由圖3 可知：基于行政電話業務優化可能存在多解。當存在非唯一解時，本文基于主備路由所對應的路徑長度之和最小原則，選擇出一組解作為行政電話業務的主備路由。同時，基于所有業務重要度相同的原則下進行研討，雖然未考慮業務重要度的差異性，但本文在求解最小值時，保留了所有主備路由共溝道數量DN,N，也可通過求解次小值來簡單處理不同重要度業務的路由安排，下一步將對于業務重要度有差異進行深入研究。

2.2 算法應用分析

本文算法是為了解決實際問題而提出的，下面需要對算法實際應用效果進行分析。由于2019 年新型冠狀病毒暴發后，行政電話及視頻會議對辦公人員起到了很大的作用，于是把算法首先應用到行政電話業務上，表1 是現場運維人員對2020 年至2022 年行政電話業務中斷次數進行統計的結果。2022 年1 月使用DFS-SRLG 算法對行政電話業務進行了優化改造，截至2022 年7 月行政電話業務中斷只發生了4 次。

表1 行政電話業務中斷次數統計表

從表1 統計的結果可以看出：行政電話業務在使用DFS-SRLG 算法后能顯著降低其中斷次數，說明DFS-SRLG 能有效地降低整體業務中斷風險，解決了實際生產問題。

2.3 算法復雜度分析

3 結 束 語

本文提出的業務路由規劃算法可以實現業務路由的動態規劃，在一定程度上簡化網絡業務管理，降低運營成本，提高整體業務的安全性。DFSSRLG 算法不僅可以降低平均整體業務中斷風險，提高網絡的穩定性，還為光纜拓撲調整和業務故障定位提供了理論指導。