電力通信網雙通道故障規避算法

楊陽 汪玉成 劉智威 占永紅

[摘要]針對傳統電力通信網規劃算法存在線路過度冗余的問題，論文重點研究電力通信網的雙通道故障保護方法，設計了啟發式優化算法，有效控制冗余線路的數量和建設成本，并通過實例對算法有效性進行了驗證，結果表明本文所提算法具有較高的理論和應用價值。首先，論文分析了雙通道故障可能出現的情況，在此基礎上建立問題模型；隨后，論文將問題轉化為整數規劃問題，并給出了啟發式求解算法；最后，通過實例檢驗了算法性能，驗證了本算法可以防止雙通道故障導致的電力通信業務中斷，并且使用更少線路，有效控制了建設成本。

[關鍵詞]電力通信網；雙通道故障；整數規劃

[中圖分類號]TP393 [文獻標識碼]A

1 引言

隨著智能電網的快速發展。電力系統間的協同通信日漸頻繁，大量電力通信業務部署在電力通信網上，電網的穩定運行對電力通信網可靠性的依賴不斷增大㈣。電力通信部門為了提升電力通信網的可靠性，為網絡中的每個節點和每條線路建設了多個冗余備份，用以在故障出現時，確保電力通信業務能夠及時切換到其保護通道之上，避免業務發生中斷，進而不影響電力系統的穩定運行。

然而，隨著電力通信網規模的不斷擴大，網絡拓撲結構也更加復雜。每建設一條線路，就需要不斷的增加大量冗余資源來避免雙通道故障造成的電力通信業務中斷問題，導致網絡建設成本過大，難以負擔。針對上述問題，本文設計了一種電力通信網雙通道故障規避算法，能夠大幅減少冗余資源數量，具有重要的應用價值。

在電力通信網規劃過程中，如何使網絡拓撲結構能夠滿足抗雙通道故障的條件是電力通信部門的重要工作，同時也是電力通信業務的重要指標。本文重點研究電力通信網結構抗雙通道故障的相關理論，建立了該優化問題的數學模型，并設計了相應求解算法。最后，利用實例對本算法的有效性進行了驗證。

2 問題模型

設傳輸網拓撲為圖G（V，E），V是節點集合（代表傳輸設備集合），E是路徑集合（代表業務通道途徑的路徑集合）。F（e_F1、e_F2）為雙業務通道同時故障的路徑對集合，其中，e_F1，e_F2∈F，F為業務通道故障的路徑集合。

本文意在圖G中建立一個保護結構G（V_P、E_P），其中V_P是節點集合（代表傳輸設備集合），E_P是路徑集合（代表業務通道途徑的路徑集合）。圖G（V_P、E_P）中的業務在發生雙業務通道同時故障后，仍不發生中斷，并且減少業務通道所需的路徑數，即減少冗余網絡資源數量。下面通過1個實例具體說明本文所研究的問題。

如圖1所示中的電力通信網拓撲結構為G（V、E），節點A，B，C，D，E，F，G∈G（V，E），邊E_AB，E_BC，E_CD，E_DE，E_EF，E_FG，E_AG，E_AD，E_AE∈E。在圖1（a）中，對于頂點A，有1條業務的通道：B←→A，其保護通道為：A←→E←→D←→C←→B。如果這兩條通道同時故障，這時A與B之間沒有其他線路可選，業務就會發生中斷。而在圖1（b）中，還存在A←→D←→C←→B這條線路，在節點A發生雙通道故障時，仍能保持通信，網絡結構更應該設計為圖1（b）這種結構。但是，對于抗雙通道故障來講，A←→G←→E←→F←→D←→C←→B這條線路就屬于過度冗余資源，存在浪費，應避免這種情況的發生。為此，本文設計了相應的算法解決這類問題，下面對這部分內容進行詳細介紹。

3 電力通信網雙通道故障規避算法

設傳輸網拓撲為圖G（V、E），V是節點集合（代表傳輸設備集合），E是路徑集合（代表業務通道途徑的路徑集合）。F（e_F1、e_F2）為雙業務通道同時故障的路徑對集合，其中，e_F1，e_F2∈F，F為業務通道故障的路徑集合。

本文意在圖G中建立一個保護結構G（V_P、E_P），其中V_P是節點集合（代表傳輸設備集合），E_P是路徑集合（代表業務通道途徑的路徑集合）。圖G（V_P、E_P）中的業務在發生雙業務通道同時故障后，仍不發生中斷，并且減少業務通道所需的路徑數，即減少冗余網絡資源數量。

設R為G（V_P，E_P）的最大候選環數，i，j為環的序號，i，j∈{0，0，2，…，R-1}，eⁱ_（u，v）∈{0，1}表示通道（u，v）在環i上，即（u，v）∈R_i。

優化目標的含義為：求一個拓撲結構G（V_P，E_P），其中的通道數最少。約束條件的含義為：

第一個約束：表示V_P中任意節點u至少在3個環上，該節點的度d（u）≥3；

第二個約束：表示每條通道路徑在一個環上最多出現一次，不存在環路；

第三個約束：表示每條通道路徑至少被兩個環共用：

第四個約束：表示兩個環至多共用一條通道路徑。

本文采用分枝定界法求解上述整數線性規劃問題。具體步驟：將式（2）整數規劃問題稱為問題A，將其對應的線性規劃問題稱為問題B。

解問題B可能得到情況之一：

a.B沒有可行解，這時A也沒有可行解，則停止；

b.B有最優解，并符合問題A的整數條件，B的最優解即為A的最優解，則停止；

c.B有最優解，但不符合A的整數條件，記它的目標函數值為z。

用觀察法找問題A的一個整數可行解x_I={eⁱ_（u，v）|i∈{0，…，R-1}，u∈V，v∈V}，試探，求得其目標函數值，并記作z_o以z^*表示問題A的最優目標函數值：這時有z≤z^*≤z，進行迭代：

步驟一：分枝，在B的最優解中任選一個不符合整數條件的變量x_j，其值為b_j，以[b_j]小于b_j的最大整數。構造兩個約束條件：x_j≤<[b_j]和x_j≥[b_j]+1，將這兩個約束，分別加入問題B，求兩個后繼規劃問題B₁和B₂。不考慮整數條件求解這兩個后繼問題。

定界，以每個后繼問題為一分枝標明求解的結果，與其它問題的解的結果中，找出最優目標函數值最大者作為新的上界z₀從已符合整數條件的各分支中，找出目標函數值為最大者作為新的下界z，若無作用z不變。

步驟二：比較與剪枝，各分枝的最優目標函數中若有大于z者，則剪掉這枝，即以后不再考慮。若小于z，且不符合整數條件，則重復第一步驟。一直到最后得到z^*=z為止。得最優整數解x^*_j，j=1，…，n。

至此，計算出G（V_P，E_P）的拓撲結構，下面給出求解保護通道路徑的算法。

步驟1：遍歷e_Fi∈F，找到e_Fi的起始節點s和目的節點d：

步驟2：設臨時節點t=s；

步驟3：如果t≠d。從環集合中找出t所在的環集合R_f；否則，轉步驟8；

步驟4：如果r_i∈R_f，轉步驟5；否則，轉步驟7；

步驟5：如果目的節點d在r_i上，則P_i=P_i+節點t和節點d在環r_i的最短路徑：

步驟6：t=d；

步驟7：t=t的鄰節點：

步驟8：返回P（p₁，p₂）；

P（p₁，p₂）為所求業務通道的路徑，本算法的時間復雜度為O（E），Dijkstra算法的時間復雜度為：O（V*IgV+E）。

4 實例驗證

對于一個具有11個頂點的網絡拓撲，如果采用傳統保護方法，將得到如圖2所示的拓撲結構，其中包含26條線路。而采用本文所提算法得到的拓撲結構見圖3，其中包含17條通道路徑，大幅減少了冗余線路的數量，并且該拓撲結構滿足在抗雙業務通道故障的條件，即在任意兩條業務通道同時故障時，電力通信業務不發生中斷。

5 結束語

本文有效地解決了電力通信網拓撲結構的規劃問題，并通過實例驗證了算法的有效性。為將該算法應用到電力通信網規劃過程中奠定了基礎。本文首先將建立了抗雙通道故障問題的數學模型，深入分析了問題的本質；隨后，將該問題轉化為整數規劃問題，并設計了啟發式求解算法；最后，通過具體實例進行檢驗，驗證了本算法的有效性。