基于策略多播路由的電力通信網路由優化研究

李敏

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

0 引言

策略路由是一種基于業務流策略請求和網絡可用資源進行路由選擇的機制[1]。在這種動態路由過程中，涉及到可用帶寬、丟失率、時延、時延抖動、開銷等等約束參數[2]。多播是一種允許多播源同時發送單一數據包到多個接收者的網絡傳輸技術，可以有效節省網絡帶寬。多播源把數據包發送到特定的多播組，只有該多播組成員才能收到該數據包[3]。電力通信網是現代大型互聯電網的重要組成部分，也是實現電網調度自動化的基礎。

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

本文主要通過改進的量子進化算法來實現電力通信網中的策略多播路由優化，該改進量子進化算法由優化的MST算法即OMST與量子進化算法結合實現，量子進化算法中對其量子門旋轉角選擇采用了一種動態調整的方法。而OMST算法用于實現最小Steiner樹。該策略多播路由優化方案首先根據電力通信業務對通信指標的不同要求進行類別劃分；在多播路由過程中，根據網絡狀態和業務類別調用相應的適應度函數，利用改進量子進化算法實現路由優化。算法充分考慮了電力通信網傳輸指標要求和電力通信網業務需求，尋出滿足電力通信網業務特性的優化多播路徑。并利用仿真實驗對本算法性能進行了驗證。

1 電力通信網策略業務路由模型

1.1 策略業務路由模型

考慮到電力通信網的網絡基礎結構和其業務需求，在通信中應該合理選擇路由，從而滿足電力網業務的要求，并盡量平衡網絡負載，提高網絡整體性能。根據電力通信網中對時延、帶寬、丟包率等指標的要求，電力通信網中的業務分為關鍵運行業務和事務管理業務兩大類，其中關鍵運行業務大類又可以分為安全1類，安全2類，安全3類；事務管理業務大類可分為安全4類，安全5類。

安全1類關鍵運行業務是電力生產中的核心業務，對電力系統的可靠運行起著重要作用。安全2類關鍵運行業務作為電力系統的必要環節，主要負責各類調度和智能管理；安全3類關鍵運行業務負責變電站及配網狀態監控和自動化處理事務管理業務大類從實時性角度出發可以分為安全4類和安全5類，其中安全4類業務為公司經營管理業務，輔助電力系統市場化服務的平穩可靠；安全5類為企業信息化與管理業務，負責電力企業ERP業務。

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

在為電力通信網中的業務進行路由選擇時，必須考慮各類電力業務的具體通信要求。根據其對通信的指標要求構造目標函數，實現符合電力業務通信特性的傳輸路徑。若PTx為第i類業務的一條可用路徑，i∈{1,2,…,5}，則PTx滿足式(1)。

(1)

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

以上路由模型所述問題屬于多目標多約束優化范疇，在多數情況下無法保證3個目標函數均取得最大值，因此可以利用權重法構造一個電力業務綜合目標函數：

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

(2)

其中，w1i，w2i和w3i滿足w1i+w2i+w3i=1，其具體取值取決于各類業務對通信指標的不同要求。

本文結合蚌埠供電公司電力通信網的實際情況，對各類電力通信業務的通信指標要求進行了規定，見表1所示。

表1 各類電力通信業務的指標及目標函數

1.2 策略多播路由模型

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

T(s,D)=

(3)

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

2 策略多播路由模型的量子進化算法

2.1 量子進化算法及路由優化過程

一個由n個量子比特構成的量子比特編碼可以描述為：

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

(4)

(5)

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

(6)

(7)

(8)

(9)

(10)

(11)

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

(12)

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

(13)

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

(14)

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

構造基于量子進化理論的多播樹算法QM步驟如下：

(1) 設源節點s，多播組成員集合{m1,m2,…,mn}，網絡中某條鏈路e(i,j)具有如公式(3)所述的策略約束；建立樹T和候選鏈路集合E1，初始時刻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上的啟發式函數，ε和δ分別是信息啟發因子和期望啟發因子；

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

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

基于量子進化算法進行策略多播路由優化算法QEA-MRO如下：

(1) 初始化種群；

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

(3) 對P(t)譯碼并進行適應度評估；

(4) 記錄當前的最佳個體狀態及其適應度值，作為該種群個體下一步進化的目標值；

(5) 驗證得到的最佳個體是否滿足最佳路由條件，且連續若干次找到的樹是否一致，即算法是否收斂，若兩個條件都滿足，則結束并輸出當前最優解，否則繼續：

(6) Whilet≤tmaxdo

Begin

t=t+1；

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

對P(t)進行適應度評估；

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

記錄下最佳個體狀態及其適應度值；

End

End

2.2 改進的量子進化算法

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

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

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

(5) 圖D(T)中構造僅含MD(多播目的節點)的子圖T1；

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

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

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

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

改進的策略多播路由優化過程只要對QEA-MRO算法修改如下：

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

第六步修改為：

(6) Whilet≤tmaxdo

Begin

t=t+1;

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

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

對IMT中刪除的必在Steiner樹中的邊，其費用加到最優解的最小成本上；

記錄下最佳個體狀態及其適應度值；

End

End

隨著算法循環的遞進，種群將逐步收斂于最優解。該算法的搜索空間大，且利用OMST算法可以確保方向性較強的搜索，加快了搜索最優解的速度。

3 仿真與分析

為評價AQEA算法的性能，利用Matlab7.1對算法進行了仿真，主要驗證該算法在策略多播路由選擇上的有效性和可行性，并與經典算法ACO、QEA進行性能對比。網絡拓撲為隨機生成的30個節點。各鏈路帶寬、時延和丟包率均為隨機生成。

算法參數設定如下：AQEA最大迭代次數200，種群大小為40，節點的最大鄰接數為7，量子比特為60，量子門旋轉時，初始旋轉角為0，進化過程中根據公式(6)動態調整，最后穩定于0.01π。

隨機生成的30個節點的網絡拓撲圖,如圖1所示。

圖1 30節點拓撲圖

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

圖2 源節點為5的多播樹

圖3 源節點為13的多播樹

圖2的源節點為5，目的節點為18，21，25，27；圖3的源節點為13，目的節點為1，21，25，29。

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

圖4 源節點為5時AQEA算法和ACO算法適應度比較

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

圖5 源節點為13時AQEA算法和ACO算法適應度比較

兩種算法在不同源點時求解最優多播樹的過程中得到的路徑時延、帶寬、丟包率和目標函數值,如表2所示。

表2 不同節點ACO&AQEA路由比較

從表2中數據可以看出AQEA算法可以實現滿足電力通信網業務要求的多播路由，且最優解要優于ACO得到的最優解。即便在兩種算法求得的最優解相近時，AQEA中獲得的最優解的時延和丟包率性能要更好，表明本算法既能夠滿足電力通信業務要求，又可以實現負載均衡，提高網絡資源利用率。

當節點數量從30逐步增加到150，多播組成員占總節點數的15%時，比較AQEA, QEA,ACO3種算法搜索解的開銷和收斂時間，得到的實驗效果,如圖6和圖7所示。

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

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

仿真結果表明，AQEA得到的多播樹開銷和收斂時間要優于ACO和QEA算法，且隨著拓撲規模的增大，優越性越明顯。實驗同時也說明本算法中動態調整旋轉角、利用最小Steiner樹來獲得多播樹的策略是有效的，前者確保信息素及時有效更新，使得螞蟻選擇多播樹全局開銷更優的鏈路機會更大，更有可能與其他目標節點共享該鏈路，從而節省搜索時間，加快收斂速度；利用后者得到的最優多播樹具有高精度優勢，可以實現更好的路由性能。

4 總結

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