楊陽 汪玉成 劉智威 占永紅

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

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

[中圖分類號(hào)]TP393 [文獻(xiàn)標(biāo)識(shí)碼]A

1 引言

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

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

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

2 問題模型

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

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

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

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

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

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

設(shè)R為G（V_P，E_P）的最大候選環(huán)數(shù)，i，j為環(huán)的序號(hào)，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)的含義為：求一個(gè)拓?fù)浣Y(jié)構(gòu)G（V_P，E_P），其中的通道數(shù)最少。約束條件的含義為：

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

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

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

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

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

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

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

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

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

用觀察法找問題A的一個(gè)整數(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ù)值：這時(shí)有z≤z^*≤z，進(jìn)行迭代：

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

定界，以每個(gè)后繼問題為一分枝標(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。

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

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

步驟2：設(shè)臨時(shí)節(jié)點(diǎn)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é)點(diǎn)d在r_i上，則P_i=P_i+節(jié)點(diǎn)t和節(jié)點(diǎn)d在環(huán)r_i的最短路徑：

步驟6：t=d；

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

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

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

4 實(shí)例驗(yàn)證

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

5 結(jié)束語

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