電力通信網(wǎng)雙通道故障規(guī)避算法

楊陽 汪玉成 劉智威 占永紅

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

[關(guān)鍵詞]電力通信網(wǎng)；雙通道故障；整數(shù)規(guī)劃

[中圖分類號]TP393 [文獻標(biāo)識碼]A

1 引言

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

然而，隨著電力通信網(wǎng)規(guī)模的不斷擴大，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)也更加復(fù)雜。每建設(shè)一條線路，就需要不斷的增加大量冗余資源來避免雙通道故障造成的電力通信業(yè)務(wù)中斷問題，導(dǎo)致網(wǎng)絡(luò)建設(shè)成本過大，難以負(fù)擔(dān)。針對上述問題，本文設(shè)計了一種電力通信網(wǎng)雙通道故障規(guī)避算法，能夠大幅減少冗余資源數(shù)量，具有重要的應(yīng)用價值。

在電力通信網(wǎng)規(guī)劃過程中，如何使網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)能夠滿足抗雙通道故障的條件是電力通信部門的重要工作，同時也是電力通信業(yè)務(wù)的重要指標(biāo)。本文重點研究電力通信網(wǎng)結(jié)構(gòu)抗雙通道故障的相關(guān)理論，建立了該優(yōu)化問題的數(shù)學(xué)模型，并設(shè)計了相應(yīng)求解算法。最后，利用實例對本算法的有效性進行了驗證。

2 問題模型

設(shè)傳輸網(wǎng)拓?fù)錇閳DG（V，E），V是節(jié)點集合（代表傳輸設(shè)備集合），E是路徑集合（代表業(yè)務(wù)通道途徑的路徑集合）。F（e_F1、e_F2）為雙業(yè)務(wù)通道同時故障的路徑對集合，其中，e_F1，e_F2∈F，F(xiàn)為業(yè)務(wù)通道故障的路徑集合。

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

如圖1所示中的電力通信網(wǎng)拓?fù)浣Y(jié)構(gòu)為G（V、E），節(jié)點A，B，C，D，E，F(xiàn)，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條業(yè)務(wù)的通道：B←→A，其保護通道為：A←→E←→D←→C←→B。如果這兩條通道同時故障，這時A與B之間沒有其他線路可選，業(yè)務(wù)就會發(fā)生中斷。而在圖1（b）中，還存在A←→D←→C←→B這條線路，在節(jié)點A發(fā)生雙通道故障時，仍能保持通信，網(wǎng)絡(luò)結(jié)構(gòu)更應(yīng)該設(shè)計為圖1（b）這種結(jié)構(gòu)。但是，對于抗雙通道故障來講，A←→G←→E←→F←→D←→C←→B這條線路就屬于過度冗余資源，存在浪費，應(yīng)避免這種情況的發(fā)生。為此，本文設(shè)計了相應(yīng)的算法解決這類問題，下面對這部分內(nèi)容進行詳細(xì)介紹。

3 電力通信網(wǎng)雙通道故障規(guī)避算法

設(shè)傳輸網(wǎng)拓?fù)錇閳DG（V、E），V是節(jié)點集合（代表傳輸設(shè)備集合），E是路徑集合（代表業(yè)務(wù)通道途徑的路徑集合）。F（e_F1、e_F2）為雙業(yè)務(wù)通道同時故障的路徑對集合，其中，e_F1，e_F2∈F，F(xiàn)為業(yè)務(wù)通道故障的路徑集合。

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

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

優(yōu)化目標(biāo)的含義為：求一個拓?fù)浣Y(jié)構(gòu)G（V_P，E_P），其中的通道數(shù)最少。約束條件的含義為：

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

第二個約束：表示每條通道路徑在一個環(huán)上最多出現(xiàn)一次，不存在環(huán)路；

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

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

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

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

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

b.B有最優(yōu)解，并符合問題A的整數(shù)條件，B的最優(yōu)解即為A的最優(yōu)解，則停止；

c.B有最優(yōu)解，但不符合A的整數(shù)條件，記它的目標(biāo)函數(shù)值為z。

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

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

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

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

至此，計算出G（V_P，E_P）的拓?fù)浣Y(jié)構(gòu)，下面給出求解保護通道路徑的算法。

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

步驟2：設(shè)臨時節(jié)點t=s；

步驟3：如果t≠d。從環(huán)集合中找出t所在的環(huán)集合R_f；否則，轉(zhuǎn)步驟8；

步驟4：如果r_i∈R_f，轉(zhuǎn)步驟5；否則，轉(zhuǎn)步驟7；

步驟5：如果目的節(jié)點d在r_i上，則P_i=P_i+節(jié)點t和節(jié)點d在環(huán)r_i的最短路徑：

步驟6：t=d；

步驟7：t=t的鄰節(jié)點：

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

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

4 實例驗證

對于一個具有11個頂點的網(wǎng)絡(luò)拓?fù)洌绻捎脗鹘y(tǒng)保護方法，將得到如圖2所示的拓?fù)浣Y(jié)構(gòu)，其中包含26條線路。而采用本文所提算法得到的拓?fù)浣Y(jié)構(gòu)見圖3，其中包含17條通道路徑，大幅減少了冗余線路的數(shù)量，并且該拓?fù)浣Y(jié)構(gòu)滿足在抗雙業(yè)務(wù)通道故障的條件，即在任意兩條業(yè)務(wù)通道同時故障時，電力通信業(yè)務(wù)不發(fā)生中斷。

5 結(jié)束語

本文有效地解決了電力通信網(wǎng)拓?fù)浣Y(jié)構(gòu)的規(guī)劃問題，并通過實例驗證了算法的有效性。為將該算法應(yīng)用到電力通信網(wǎng)規(guī)劃過程中奠定了基礎(chǔ)。本文首先將建立了抗雙通道故障問題的數(shù)學(xué)模型，深入分析了問題的本質(zhì)；隨后，將該問題轉(zhuǎn)化為整數(shù)規(guī)劃問題，并設(shè)計了啟發(fā)式求解算法；最后，通過具體實例進行檢驗，驗證了本算法的有效性。