楊陽(yáng) 汪玉成 劉智威 占永紅

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

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

[中圖分類(lèi)號(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)行對(duì)電力通信網(wǎng)可靠性的依賴(lài)不斷增大㈣。電力通信部門(mén)為了提升電力通信網(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è)一條線路，就需要不斷的增加大量冗余資源來(lái)避免雙通道故障造成的電力通信業(yè)務(wù)中斷問(wèn)題，導(dǎo)致網(wǎng)絡(luò)建設(shè)成本過(guò)大，難以負(fù)擔(dān)。針對(duì)上述問(wèn)題，本文設(shè)計(jì)了一種電力通信網(wǎng)雙通道故障規(guī)避算法，能夠大幅減少冗余資源數(shù)量，具有重要的應(yīng)用價(jià)值。

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

2 問(wèn)題模型

設(shè)傳輸網(wǎng)拓?fù)錇閳DG（V，E），V是節(jié)點(diǎn)集合（代表傳輸設(shè)備集合），E是路徑集合（代表業(yè)務(wù)通道途徑的路徑集合）。F（e_F1、e_F2）為雙業(yè)務(wù)通道同時(shí)故障的路徑對(duì)集合，其中，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ù)量。下面通過(guò)1個(gè)實(shí)例具體說(shuō)明本文所研究的問(wèn)題。

如圖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）中，對(duì)于頂點(diǎn)A，有1條業(yè)務(wù)的通道：B←→A，其保護(hù)通道為：A←→E←→D←→C←→B。如果這兩條通道同時(shí)故障，這時(shí)A與B之間沒(méi)有其他線路可選，業(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)。但是，對(duì)于抗雙通道故障來(lái)講，A←→G←→E←→F←→D←→C←→B這條線路就屬于過(guò)度冗余資源，存在浪費(fèi)，應(yīng)避免這種情況的發(fā)生。為此，本文設(shè)計(jì)了相應(yīng)的算法解決這類(lèi)問(wèn)題，下面對(duì)這部分內(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í)故障的路徑對(duì)集合，其中，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ī)劃問(wèn)題。具體步驟：將式（2）整數(shù)規(guī)劃問(wèn)題稱(chēng)為問(wèn)題A，將其對(duì)應(yīng)的線性規(guī)劃問(wèn)題稱(chēng)為問(wèn)題B。

解問(wèn)題B可能得到情況之一：

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

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

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

用觀察法找問(wèn)題A的一個(gè)整數(shù)可行解x_I={eⁱ_{（u，v）}|i∈{0，…，R-1}，u∈V，v∈V}，試探，求得其目標(biāo)函數(shù)值，并記作z_o以z^*表示問(wèn)題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è)約束，分別加入問(wèn)題B，求兩個(gè)后繼規(guī)劃問(wèn)題B₁和B₂。不考慮整數(shù)條件求解這兩個(gè)后繼問(wèn)題。

定界，以每個(gè)后繼問(wèn)題為一分枝標(biāo)明求解的結(jié)果，與其它問(wèn)題的解的結(jié)果中，找出最優(yōu)目標(biāo)函數(shù)值最大者作為新的上界z₀從已符合整數(shù)條件的各分支中，找出目標(biāo)函數(shù)值為最大者作為新的下界z，若無(wú)作用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)證

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

5 結(jié)束語(yǔ)

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