基于策略多播路由的電力通信網(wǎng)路由優(yōu)化研究

李敏

(國網(wǎng)蚌埠供電公司 信息通信公司，蚌埠 233000)

0 引言

策略路由是一種基于業(yè)務(wù)流策略請求和網(wǎng)絡(luò)可用資源進(jìn)行路由選擇的機(jī)制[1]。在這種動(dòng)態(tài)路由過程中，涉及到可用帶寬、丟失率、時(shí)延、時(shí)延抖動(dòng)、開銷等等約束參數(shù)[2]。多播是一種允許多播源同時(shí)發(fā)送單一數(shù)據(jù)包到多個(gè)接收者的網(wǎng)絡(luò)傳輸技術(shù)，可以有效節(jié)省網(wǎng)絡(luò)帶寬。多播源把數(shù)據(jù)包發(fā)送到特定的多播組，只有該多播組成員才能收到該數(shù)據(jù)包[3]。電力通信網(wǎng)是現(xiàn)代大型互聯(lián)電網(wǎng)的重要組成部分，也是實(shí)現(xiàn)電網(wǎng)調(diào)度自動(dòng)化的基礎(chǔ)。

隨著電力行業(yè)信息化程度的提高，電力業(yè)務(wù)種類和數(shù)量迅速增加，對通信指標(biāo)的需求也變得多樣化。策略路由選擇除了可達(dá)和最短路徑的衡量指標(biāo)之外，還要考慮電力通信業(yè)務(wù)的具體通信需求和網(wǎng)絡(luò)動(dòng)態(tài)特性。在電力通信網(wǎng)絡(luò)路由算法設(shè)計(jì)中，如何滿足其業(yè)務(wù)通信需求，如何加速算法的求解速度等都是需要重點(diǎn)考慮的問題。目前對路由算法進(jìn)行優(yōu)化的文獻(xiàn)很多，例如在傳統(tǒng)路由算法中加入乘性策略約束參數(shù)來提高搜索可靠性并實(shí)現(xiàn)最佳路由[4]，考慮負(fù)載均衡的路由算法[5]來實(shí)現(xiàn)網(wǎng)絡(luò)資源優(yōu)化和網(wǎng)絡(luò)性能提高的目的等。針對電力通信網(wǎng)可靠性、風(fēng)險(xiǎn)評估、失效自愈、策略路由優(yōu)化等問題。但針對電力通信網(wǎng)中策略多播的路由優(yōu)化尚未有深入研究。而目前策略多播路由是電力通信網(wǎng)中一種主要的路由方式。實(shí)現(xiàn)策略多播路由的主要目標(biāo)有兩點(diǎn)：為每一個(gè)接納的電力通信網(wǎng)業(yè)務(wù)請求找到滿足其策略要求的多播樹[6]；優(yōu)化全局資源利用率，平衡電力通信網(wǎng)負(fù)載，最大化業(yè)務(wù)處理能力[7]。其關(guān)鍵是如何建立滿足多個(gè)約束的最小代價(jià)樹，該問題被稱為最小Steiner樹問題[8]，而多個(gè)不相關(guān)可加度量約束的多播路由問題被證明是一個(gè)NP完全問題，一般要使用智能算法或啟發(fā)式算法來處理。典型的啟發(fā)式算法有MST、RS等[9]。

本文主要通過改進(jìn)的量子進(jìn)化算法來實(shí)現(xiàn)電力通信網(wǎng)中的策略多播路由優(yōu)化，該改進(jìn)量子進(jìn)化算法由優(yōu)化的MST算法即OMST與量子進(jìn)化算法結(jié)合實(shí)現(xiàn)，量子進(jìn)化算法中對其量子門旋轉(zhuǎn)角選擇采用了一種動(dòng)態(tài)調(diào)整的方法。而OMST算法用于實(shí)現(xiàn)最小Steiner樹。該策略多播路由優(yōu)化方案首先根據(jù)電力通信業(yè)務(wù)對通信指標(biāo)的不同要求進(jìn)行類別劃分；在多播路由過程中，根據(jù)網(wǎng)絡(luò)狀態(tài)和業(yè)務(wù)類別調(diào)用相應(yīng)的適應(yīng)度函數(shù)，利用改進(jìn)量子進(jìn)化算法實(shí)現(xiàn)路由優(yōu)化。算法充分考慮了電力通信網(wǎng)傳輸指標(biāo)要求和電力通信網(wǎng)業(yè)務(wù)需求，尋出滿足電力通信網(wǎng)業(yè)務(wù)特性的優(yōu)化多播路徑。并利用仿真實(shí)驗(yàn)對本算法性能進(jìn)行了驗(yàn)證。

1 電力通信網(wǎng)策略業(yè)務(wù)路由模型

1.1 策略業(yè)務(wù)路由模型

考慮到電力通信網(wǎng)的網(wǎng)絡(luò)基礎(chǔ)結(jié)構(gòu)和其業(yè)務(wù)需求，在通信中應(yīng)該合理選擇路由，從而滿足電力網(wǎng)業(yè)務(wù)的要求，并盡量平衡網(wǎng)絡(luò)負(fù)載，提高網(wǎng)絡(luò)整體性能。根據(jù)電力通信網(wǎng)中對時(shí)延、帶寬、丟包率等指標(biāo)的要求，電力通信網(wǎng)中的業(yè)務(wù)分為關(guān)鍵運(yùn)行業(yè)務(wù)和事務(wù)管理業(yè)務(wù)兩大類，其中關(guān)鍵運(yùn)行業(yè)務(wù)大類又可以分為安全1類，安全2類，安全3類；事務(wù)管理業(yè)務(wù)大類可分為安全4類，安全5類。

安全1類關(guān)鍵運(yùn)行業(yè)務(wù)是電力生產(chǎn)中的核心業(yè)務(wù)，對電力系統(tǒng)的可靠運(yùn)行起著重要作用。安全2類關(guān)鍵運(yùn)行業(yè)務(wù)作為電力系統(tǒng)的必要環(huán)節(jié)，主要負(fù)責(zé)各類調(diào)度和智能管理；安全3類關(guān)鍵運(yùn)行業(yè)務(wù)負(fù)責(zé)變電站及配網(wǎng)狀態(tài)監(jiān)控和自動(dòng)化處理事務(wù)管理業(yè)務(wù)大類從實(shí)時(shí)性角度出發(fā)可以分為安全4類和安全5類，其中安全4類業(yè)務(wù)為公司經(jīng)營管理業(yè)務(wù)，輔助電力系統(tǒng)市場化服務(wù)的平穩(wěn)可靠；安全5類為企業(yè)信息化與管理業(yè)務(wù)，負(fù)責(zé)電力企業(yè)ERP業(yè)務(wù)。

電力通信網(wǎng)的路由問題可以表示為加權(quán)圖G(V,E)，其中，V表示節(jié)點(diǎn)集，E表示鏈路集，若源點(diǎn)到目的節(jié)點(diǎn)分別用s和d表示，任意一條路徑PTx={s,i,…,j,d}表示s到d之間的路徑。

在為電力通信網(wǎng)中的業(yè)務(wù)進(jìn)行路由選擇時(shí)，必須考慮各類電力業(yè)務(wù)的具體通信要求。根據(jù)其對通信的指標(biāo)要求構(gòu)造目標(biāo)函數(shù)，實(shí)現(xiàn)符合電力業(yè)務(wù)通信特性的傳輸路徑。若PTx為第i類業(yè)務(wù)的一條可用路徑，i∈{1,2,…,5}，則PTx滿足式(1)。

(1)

其中，fD(xi)、fB(xi)和fL(xi)分別是時(shí)延、帶寬和丟包率的目標(biāo)函數(shù)。D(xi)表示i類業(yè)務(wù)在路徑x上的時(shí)延，Dmax是電力網(wǎng)中該類業(yè)務(wù)最大允許時(shí)延值；B(xi)是第i類業(yè)務(wù)在路徑x上的可用帶寬，Bmax是可行解中的最大可用帶寬，Bmin是可行解中的最小可用帶寬；L(xi)是i類業(yè)務(wù)在路徑x上的丟包率，Lmax為該類業(yè)務(wù)在電力網(wǎng)中可容忍的最大丟包率。

以上路由模型所述問題屬于多目標(biāo)多約束優(yōu)化范疇，在多數(shù)情況下無法保證3個(gè)目標(biāo)函數(shù)均取得最大值，因此可以利用權(quán)重法構(gòu)造一個(gè)電力業(yè)務(wù)綜合目標(biāo)函數(shù)：

maxf(xi)=w1ifD(xi)+w2ifB(xi)+w3ifL(xi)

(2)

其中，w1i，w2i和w3i滿足w1i+w2i+w3i=1，其具體取值取決于各類業(yè)務(wù)對通信指標(biāo)的不同要求。

本文結(jié)合蚌埠供電公司電力通信網(wǎng)的實(shí)際情況，對各類電力通信業(yè)務(wù)的通信指標(biāo)要求進(jìn)行了規(guī)定，見表1所示。

表1 各類電力通信業(yè)務(wù)的指標(biāo)及目標(biāo)函數(shù)

1.2 策略多播路由模型

多播型電力通信網(wǎng)用有權(quán)無向圖G=(V,E)表示，其中，V是節(jié)點(diǎn)集，E是節(jié)點(diǎn)間鏈路集，|V|和|E|分別是節(jié)點(diǎn)數(shù)和鏈路數(shù)。多播源點(diǎn)設(shè)為s∈V，多播目的節(jié)點(diǎn)集為D?{V-{s}}，對任一節(jié)點(diǎn)n∈V定義5個(gè)參數(shù)，帶寬bw(n)，時(shí)延delay(n)，開銷cost(n)，丟包率ptloss(e)，以及時(shí)延抖動(dòng)dj(e)，其中帶寬和開銷均大于零，丟包率和時(shí)延抖動(dòng)大于等于零；對任一鏈路也定義類似的五個(gè)參數(shù)，帶寬bw(n)，時(shí)延delay(n)，開銷cost(n)，丟包率ptloss(e)，以及時(shí)延抖動(dòng)dj(e)。在給定s、D的情況下，設(shè)T(s,D)是由兩部分共同構(gòu)成的多播樹，s遍歷D的所有成員樹，即T中存在由源節(jié)點(diǎn)s到某一目的節(jié)點(diǎn)的通路pt(s,d)。具有策略優(yōu)化的多播路由算法就是要在網(wǎng)絡(luò)G=(V,E)中從原點(diǎn)s到多播目的節(jié)點(diǎn)集Md?{V-{s}}之間構(gòu)造一棵包含基本節(jié)點(diǎn)的最小開銷多播樹T(s,Md)，即找出min(cost(T(s,D))，且T(s,D)滿足以下關(guān)系，如式(3)。

T(s,D)=

(3)

其中，pt(s,d)為T(s,Md)上s到d的路由；Du、DJu、PLu和Bu分別表示電力通信網(wǎng)業(yè)務(wù)對延遲、延遲抖動(dòng)、丟包率和帶寬的約束值。滿足上述公式(2)中四個(gè)約束條件的多播樹中，cost(T(s,Md))總成本最小。

2 策略多播路由模型的量子進(jìn)化算法

2.1 量子進(jìn)化算法及路由優(yōu)化過程

一個(gè)由n個(gè)量子比特構(gòu)成的量子比特編碼可以描述為：

令α=cosθ，β=sinθ，則量子比特可以表示為[cosθsinθ]T，其中，θ是量子比特的相位，其改變可以由量子旋轉(zhuǎn)門實(shí)現(xiàn)式(4)。

(4)

(5)

為了加快算法收斂，要對種群進(jìn)行變異操作。量子進(jìn)化算法采用量子旋轉(zhuǎn)門對信息素進(jìn)行更新，達(dá)到加速算法收斂的目的如式(6)。

(6)

(7)

(8)

(9)

(10)

(11)

引入控制因子λ∈[0,1]，則適應(yīng)度函數(shù)選取如式(12)。

(12)

其中，fmax和fmin分別表示當(dāng)前一代群體中個(gè)體適應(yīng)度的最大和最小值。原始適應(yīng)度f(x)定義為式(13)。

(13)

由此，信息素的更新規(guī)則將表述為式(14)。

(14)

在為電力通信網(wǎng)業(yè)務(wù)進(jìn)行路由選擇時(shí)，首先根據(jù)各類業(yè)務(wù)對通信指標(biāo)的需求判定所屬類別，確定目標(biāo)函數(shù)及可容忍最大時(shí)延、最小可用帶寬和最大丟包率等約束條件[13]。根據(jù)網(wǎng)絡(luò)中時(shí)延、帶寬和節(jié)點(diǎn)丟包率大小選擇滿足策略約束條件的路徑。多播路由優(yōu)化主要是構(gòu)造一棵多播樹，其核心思想是，首先生成一棵只包含源節(jié)點(diǎn)的樹T，每次選擇一條與T連接且滿足策略約束的鏈路，逐步生成該多播樹。

構(gòu)造基于量子進(jìn)化理論的多播樹算法QM步驟如下：

(1) 設(shè)源節(jié)點(diǎn)s，多播組成員集合{m1,m2,…,mn}，網(wǎng)絡(luò)中某條鏈路e(i,j)具有如公式(3)所述的策略約束；建立樹T和候選鏈路集合E1，初始時(shí)刻T={s}，E1={e(s,i)|e(s,i)∈E}

(2) 從候選集E1中選一條鏈路e(m,n)如式(15)。

(15)

其中，m∈T，n?T，qj為ej上的信息素濃度；η=1/cost(ej)為ej上的啟發(fā)式函數(shù)，ε和δ分別是信息啟發(fā)因子和期望啟發(fā)因子；

(3) 根據(jù)公式(2)計(jì)算鏈路e(m,n)的約束值，滿足要求則將其加入E1中；

(4) 若T尚未覆蓋所有目的節(jié)點(diǎn)，轉(zhuǎn)到第(2)步，否則，對T進(jìn)行刪減，除去所有非目的節(jié)點(diǎn)的葉子節(jié)點(diǎn)及相關(guān)邊，得到最終的多播樹。

基于量子進(jìn)化算法進(jìn)行策略多播路由優(yōu)化算法QEA-MRO如下：

(1) 初始化種群；

(2) 測量初始種群Q(t)中各個(gè)體，得到一組狀態(tài)P(t)；

(3) 對P(t)譯碼并進(jìn)行適應(yīng)度評估；

(4) 記錄當(dāng)前的最佳個(gè)體狀態(tài)及其適應(yīng)度值，作為該種群個(gè)體下一步進(jìn)化的目標(biāo)值；

(5) 驗(yàn)證得到的最佳個(gè)體是否滿足最佳路由條件，且連續(xù)若干次找到的樹是否一致，即算法是否收斂，若兩個(gè)條件都滿足，則結(jié)束并輸出當(dāng)前最優(yōu)解，否則繼續(xù)：

(6) Whilet≤tmaxdo

Begin

t=t+1；

測量種群Q(t-1)，得到狀態(tài)P(t)；

對P(t)進(jìn)行適應(yīng)度評估；

量子變異操作，采用量子旋轉(zhuǎn)門變異操作更新Q(t)，得到下一代種群Q(t+1)；

記錄下最佳個(gè)體狀態(tài)及其適應(yīng)度值；

End

End

2.2 改進(jìn)的量子進(jìn)化算法

在求解多播樹中各個(gè)體的最優(yōu)解時(shí)，可以利用OMST(Optimized Minimum Spanning Tree)算法生成受約束最小的Steiner樹[14]。這種改進(jìn)的量子進(jìn)化算法首先基于量子進(jìn)化算法來選擇Steiner預(yù)備點(diǎn)，而后對這些節(jié)點(diǎn)實(shí)施OMST算法求解最小Steiner樹。量子進(jìn)化算法中的每個(gè)個(gè)體都對應(yīng)一棵Steiner樹，因此由量子交叉和量子門旋轉(zhuǎn)操作可以對個(gè)體進(jìn)行優(yōu)化，從而得到策略多播路由優(yōu)化問題的解。

AQEA(Advanced Evolutionary Algorithm)在量子個(gè)體上實(shí)施量子交叉，可以保留較好的基因段；利用量子門更新和搜索網(wǎng)絡(luò)自適應(yīng)調(diào)整策略能確保種群的多樣性[15]；基于OMST生成最小Stenier樹，使得解在收斂精度高的同時(shí)具有收斂速度快的優(yōu)勢。對MT算法進(jìn)行改造，增加OMST算法步驟，改進(jìn)算法稱為IMT。修改MT其第四步為：

(4) 若T尚未覆蓋所有目的節(jié)點(diǎn)，轉(zhuǎn)到第(2)步，否則，對T的任意兩點(diǎn)使用Floyds算法求出圖T=(MV,ME)的距離圖D(T)，兩節(jié)點(diǎn)間保留最小代價(jià)路徑；

(5) 圖D(T)中構(gòu)造僅含MD(多播目的節(jié)點(diǎn))的子圖T1；

(6) 計(jì)算T1的最小支撐樹(MST)ST1；

(7) 用圖T中相應(yīng)的最短路徑代替ST1中的每條邊，構(gòu)造圖T的子圖T2；

(8) 計(jì)算T2的最小支撐樹ST2；

(9) 對ST2中那些符合mv?s且該點(diǎn)的度deg(mv)=1的節(jié)點(diǎn)逐一進(jìn)行刪除操作，最后得到ST2的最小多播支撐樹TMMSP，該樹即最小Steiner樹。

改進(jìn)的策略多播路由優(yōu)化過程只要對QEA-MRO算法修改如下：

第三步修改為：對P(t)譯碼，用OMST算法求解各個(gè)體的Steiner樹，并進(jìn)行適應(yīng)度評估；

第六步修改為：

(6) Whilet≤tmaxdo

Begin

t=t+1;

測量種群Q(t-1)，得到狀態(tài)P(t)；利用OMST算法求解各個(gè)體的Steiner樹，對P(t)的局部群體中每個(gè)個(gè)體進(jìn)行適應(yīng)度評估；

量子變異操作，采用量子旋轉(zhuǎn)門變異操作更新Q(t)，得到下一代種群Q(t+1)；

對IMT中刪除的必在Steiner樹中的邊，其費(fèi)用加到最優(yōu)解的最小成本上；

記錄下最佳個(gè)體狀態(tài)及其適應(yīng)度值；

End

End

隨著算法循環(huán)的遞進(jìn)，種群將逐步收斂于最優(yōu)解。該算法的搜索空間大，且利用OMST算法可以確保方向性較強(qiáng)的搜索，加快了搜索最優(yōu)解的速度。

3 仿真與分析

為評價(jià)AQEA算法的性能，利用Matlab7.1對算法進(jìn)行了仿真，主要驗(yàn)證該算法在策略多播路由選擇上的有效性和可行性，并與經(jīng)典算法ACO、QEA進(jìn)行性能對比。網(wǎng)絡(luò)拓?fù)錇殡S機(jī)生成的30個(gè)節(jié)點(diǎn)。各鏈路帶寬、時(shí)延和丟包率均為隨機(jī)生成。

算法參數(shù)設(shè)定如下：AQEA最大迭代次數(shù)200，種群大小為40，節(jié)點(diǎn)的最大鄰接數(shù)為7，量子比特為60，量子門旋轉(zhuǎn)時(shí)，初始旋轉(zhuǎn)角為0，進(jìn)化過程中根據(jù)公式(6)動(dòng)態(tài)調(diào)整，最后穩(wěn)定于0.01π。

隨機(jī)生成的30個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)鋱D,如圖1所示。

圖1 30節(jié)點(diǎn)拓?fù)鋱D

執(zhí)行AQEA后生成的多播樹如圖2和3所示。

圖2 源節(jié)點(diǎn)為5的多播樹

圖3 源節(jié)點(diǎn)為13的多播樹

圖2的源節(jié)點(diǎn)為5，目的節(jié)點(diǎn)為18，21，25，27；圖3的源節(jié)點(diǎn)為13，目的節(jié)點(diǎn)為1，21，25，29。

假設(shè)有業(yè)務(wù)要求帶寬12 Mbps，最大時(shí)延要求0.08 s，丟包率低于1%，根據(jù)表1可以判斷該業(yè)務(wù)屬于安全3類，對應(yīng)目標(biāo)函數(shù)為f(x3)=0.6fB(x3)+0.3fD(x3)+0.1fL(x3)。將AQEA算法和ACO算法進(jìn)行對比。取兩個(gè)不同源點(diǎn)(5和13)時(shí)，兩種算法的適應(yīng)度比較,如圖4和圖5所示。

圖4 源節(jié)點(diǎn)為5時(shí)AQEA算法和ACO算法適應(yīng)度比較

結(jié)果表明，兩種算法在種群大小和螞蟻數(shù)量一致時(shí)，AQEA的收斂特性顯然更好，最優(yōu)多播路徑的收斂速度更快，且其多播路徑更優(yōu)化。

圖5 源節(jié)點(diǎn)為13時(shí)AQEA算法和ACO算法適應(yīng)度比較

兩種算法在不同源點(diǎn)時(shí)求解最優(yōu)多播樹的過程中得到的路徑時(shí)延、帶寬、丟包率和目標(biāo)函數(shù)值,如表2所示。

表2 不同節(jié)點(diǎn)ACO&AQEA路由比較

從表2中數(shù)據(jù)可以看出AQEA算法可以實(shí)現(xiàn)滿足電力通信網(wǎng)業(yè)務(wù)要求的多播路由，且最優(yōu)解要優(yōu)于ACO得到的最優(yōu)解。即便在兩種算法求得的最優(yōu)解相近時(shí)，AQEA中獲得的最優(yōu)解的時(shí)延和丟包率性能要更好，表明本算法既能夠滿足電力通信業(yè)務(wù)要求，又可以實(shí)現(xiàn)負(fù)載均衡，提高網(wǎng)絡(luò)資源利用率。

當(dāng)節(jié)點(diǎn)數(shù)量從30逐步增加到150，多播組成員占總節(jié)點(diǎn)數(shù)的15%時(shí)，比較AQEA, QEA,ACO3種算法搜索解的開銷和收斂時(shí)間，得到的實(shí)驗(yàn)效果,如圖6和圖7所示。

圖6 AQEA,QEA,ACO三種算法搜索解的開銷

圖7 AQEA,QEA,ACO三種算法搜索收斂時(shí)間

仿真結(jié)果表明，AQEA得到的多播樹開銷和收斂時(shí)間要優(yōu)于ACO和QEA算法，且隨著拓?fù)湟?guī)模的增大，優(yōu)越性越明顯。實(shí)驗(yàn)同時(shí)也說明本算法中動(dòng)態(tài)調(diào)整旋轉(zhuǎn)角、利用最小Steiner樹來獲得多播樹的策略是有效的，前者確保信息素及時(shí)有效更新，使得螞蟻選擇多播樹全局開銷更優(yōu)的鏈路機(jī)會(huì)更大，更有可能與其他目標(biāo)節(jié)點(diǎn)共享該鏈路，從而節(jié)省搜索時(shí)間，加快收斂速度；利用后者得到的最優(yōu)多播樹具有高精度優(yōu)勢，可以實(shí)現(xiàn)更好的路由性能。

4 總結(jié)

量子進(jìn)化算法具有速度快、魯棒性強(qiáng)的優(yōu)點(diǎn)，能夠較好地完成電力通信網(wǎng)的策略多播路由優(yōu)化。本文提出一種基于策略多播路由的電力通信網(wǎng)絡(luò)路由優(yōu)化的改進(jìn)的量子進(jìn)化算法，利用動(dòng)態(tài)方式調(diào)整量子選擇門旋轉(zhuǎn)角，同時(shí)將量子進(jìn)化算法和OMST算法結(jié)合生成最小Steiner樹，不僅增強(qiáng)了種群多樣性，也加快了種群的收斂速度。實(shí)驗(yàn)表明本算法有較好的收斂特性，在多播路由開銷和收斂時(shí)間上都比傳統(tǒng)量子進(jìn)化算法、蟻群算法更優(yōu)化。本算法既能夠滿足電力通信業(yè)務(wù)要求，在較短的時(shí)間內(nèi)收斂到最優(yōu)多播樹，又可以實(shí)現(xiàn)負(fù)載均衡，提高網(wǎng)絡(luò)資源利用率。且對不同的通信業(yè)務(wù)類別，對應(yīng)的多播路由也有差異，表明本算法具有業(yè)務(wù)路由自適應(yīng)性。