龍致遠， 鄭丁， 黃美琴， 馮斯德， 朱明斯

(海南電網有限責任公司 信息通信分公司， ?？?570203)

0 引言

隨著智能電網技術的發(fā)展和成熟，融合了同步數(shù)字體系(Synchronous Digital Hierarchy，SDH)和傳統(tǒng)密集波分復用(Wavelength Division Multiplexing，WDM)技術優(yōu)勢的光傳送網(Optical Transmission Networks，OTN)技術越來越廣泛地應用于電力通信場景中[1]。OTN具有大顆粒調度、大容量傳輸、適配多種業(yè)務等特點[2]，不僅催生了諸多新的電力通信業(yè)務，也使得網絡中對大容量高速率業(yè)務的處理性能大幅提升[3]。電力通信OTN業(yè)務關系到電力系統(tǒng)的生產調度和管理控制，對業(yè)務可靠性、服務質量和傳輸穩(wěn)定性都有特定的要求。但由于網絡在進行業(yè)務路由分配時缺乏全局考慮和長遠規(guī)劃，隨著業(yè)務量的急劇增加，影響OTN可靠性的主要問題已不是突發(fā)性擁塞，而是業(yè)務分布的不均衡導致的網絡運行風險提高。因此，限制高風險事件的發(fā)生，將風險差異化的業(yè)務均衡地分布到網絡中，對提高OTN的可靠性及風險運行水平有重要意義。

針對電力OTN業(yè)務路由優(yōu)化問題，現(xiàn)階段主要采用經典尋路算法或啟發(fā)式算法來解決。文獻[4]提出了一種KSP多路徑綜合代價算法，利用Dijkstra找出兩點間K條最短路徑，從中選出最優(yōu)的一條進行業(yè)務部署。由于KSP只能對業(yè)務進行單次輪流部署，部署次序不同導致結果差異較大，無法適用于全局路由優(yōu)化問題；文獻[5]將路由選擇轉化成一個整數(shù)線性規(guī)劃問題，通過遺傳算法解決多目標的路由優(yōu)化。雖然實現(xiàn)了多目標優(yōu)化，但算法收斂性和隨機性較差，受限于局部最優(yōu)，不能有效地尋找最優(yōu)解；文獻[6]使用蟻群算法解決路由與資源分配問題，但在考慮路由可用性時并未涉及OTN中特有的光信噪比約束，并且僅從資源角度實現(xiàn)業(yè)務的負載均衡，未考慮業(yè)務重要度和鏈路風險本身對可靠性的影響，不適用于解決電力OTN中基于風險均衡的業(yè)務路由優(yōu)化問題。

針對上述算法存在的問題，本文提出了一種面向可靠性的路由優(yōu)化算法，算法以全網業(yè)務風險均衡度為優(yōu)化目標，綜合考慮網絡傳輸時延以及光信噪比約束。在算法的實現(xiàn)上，以遺傳算法原理為基礎，在進化過程中融合模擬退火和小生境演化思想，旨在提升算法運行效率并獲取較高的求解質量，從而對網絡中已有業(yè)務的業(yè)務路由進行全局規(guī)劃和重新部署。通過仿真驗證了算法的可靠性及路由優(yōu)化能力，該算法在大規(guī)模網絡拓撲中能夠有效優(yōu)化全網業(yè)務風險均衡度，提升OTN網絡運行的可靠性。

1 問題描述

電力OTN網絡架構基于電力通信網網架，電力通信網架構又基于電網網架[7]，因此電力OTN拓撲結構相對穩(wěn)定。并且電力OTN屬于靜態(tài)網絡[8]，網絡中的業(yè)務在建立后數(shù)據流基本保持不變，網絡業(yè)務運行風險由傳統(tǒng)的突發(fā)性擁塞轉變?yōu)闃I(yè)務在傳輸鏈路上的過度集中分布[9]。因此，與傳統(tǒng)增加資源冗余的方法不同，對電力通信OTN可靠性的優(yōu)化更偏向從業(yè)務路由角度探索能夠均衡網絡風險、提高網絡運行安全性和可靠性的路由分配機制。

本文所設計的面向可靠性的路由優(yōu)化算法，主要針對網絡中業(yè)務分布不合理問題，從全局角度進行現(xiàn)網業(yè)務路由的重分配，通過將風險差異化的業(yè)務均衡地分布到網絡中，降低網絡風險，提高電力OTN可靠性。本章在算法設計過程中，基于遺傳算法，以風險均衡度為目標，綜合考慮網絡傳輸時延和OTN光信噪比約束，保證算法在路由選擇過程中趨向于選擇滿足時延約束且光信噪比參數(shù)指標好的光通道，將重要度高的業(yè)務分布到風險值低的傳輸鏈路上，均衡網絡局部之間的風險差異，使網絡可靠性得到提升。

2 模型建立

為了抽象面向可靠性的電力OTN的路由優(yōu)化問題，首先定義電力光傳輸網拓撲為無向帶權圖G(V,E)，其中V={v1,v2,…,vn}為網絡中節(jié)點集合，E={e1,e2,…,em}為網絡中的無向邊集合，ek表示網絡中第k條邊。圖中任意一條連接節(jié)點vi和vj的邊eij上定義了一個二元組(Pe,Le)，Pe表示鏈路風險度(即光纖鏈路的失效概率)，Le表示鏈路的長度，根據鏈路的長度，可以相應地計算該光纖段的傳輸時延和信號功率衰減。然后定義網絡中的業(yè)務請求集合為S={S1,S2,…,SM}，對于每一個業(yè)務請求Sk(k=1,2,…,M)定義了一個四元組(Vs,Vd,Ts,Q)，分別表示該業(yè)務請求的起始節(jié)點、終止節(jié)點、時延約束和光信噪比約束。構造上述網絡模型的目的是根據電力OTN業(yè)務請求，獲取一個滿足該業(yè)務請求的路徑集合，保證業(yè)務路由可用的同時滿足該業(yè)務的QoS約束。

信號在網絡中傳輸時，傳輸距離的長度、通道媒介的種類、途徑交換網絡設備的數(shù)量都會對信號的傳輸時延產生影響。若節(jié)點vi到節(jié)點vj之間經過網絡跳數(shù)為m，傳輸路徑總長度為lij，節(jié)點交換設備的交換延時為tv，信號總時延Tij表示如式(1)。

(1)

其中，c為信號在通道中的傳輸速度，Δt為隨機延時抖動。

(2)

(3)

若已知網絡中業(yè)務分布，可知邊eij上承載的業(yè)務集合Seij是S的子集。定義綜合業(yè)務風險度為OTN中某一光纖段上承載的所有業(yè)務的風險度總和，表達式如式(4)。

(4)

其中，M表示集合S中的業(yè)務請求總數(shù)，α表示邊eij是否承載某一業(yè)務，若承載有該業(yè)務則α為1，反之為0。

全網業(yè)務風險均衡度能夠反映網絡中各邊所承載的業(yè)務風險均衡分布情況。該指標值越低，說明網絡中每條通道的綜合業(yè)務風險度差異越小，網絡中業(yè)務分布越均衡，網絡整體的可靠性較好，網絡運行風險較??；該指標值越高，說明網絡中業(yè)務的分布均衡性較差，部分鏈路上承載的業(yè)務數(shù)量過多或者關鍵業(yè)務集中，而部分鏈路負載少。全網風險均衡度可表示為式(5)。

(5)

3 算法基本流程

本文提出一種面向可靠性的電力OTN路由優(yōu)化算法，該算法以遺傳算法[11]的原理為基礎，在種群進化過程中融合模擬退火[12]和小生境演化[13]思想。算法主要步驟概括如下：

步驟1：參數(shù)初始化。初始化待優(yōu)化的業(yè)務請求集合，設置算法最大迭代次數(shù)(即終止條件)、個體適應度函數(shù)f(x)及相關計算因子、模擬退火機制中的初始溫度T0和和降溫因子Δ。

步驟2：樣本空間初始化。通過某種路由求解策略隨機生成初代種群并計算其適應度。根據適應度大小對初代種群進行排序，按照f(x)梯度將初代種群劃分為N個子集合(即小生境數(shù)量為N)。對各子集合中適應度最大的個體xk(k=1,2,…,N)進行標記。

步驟3：當代種群中，適應度最大的個體xk直接進入下一代候選種群，對小生境中其余個體進行選擇、交叉及變異等一系列標準遺傳操作，生成下一代候選種群。需要注意的是，小生境意味著種群隔離，不同小生境中種群的處理過程相互獨立，互不影響。

步驟4：在各小生境的下一代候選種群中，選取適應度最優(yōu)個體進入模擬退火流程：對個體xk(k=1,2,…,N)產生隨機擾動Δx(類似遺傳算法變異過程)，生成新的個體xk，計算兩個個體之間適應度函數(shù)的差值Δf=f(xk)-f(xk-1)。當Δf≤0時，接受個體xk，即對其予以保留；當Δf>0時，令接受概率為式(6)。

(6)

產生在[0,1]區(qū)間上均勻分布的偽隨機數(shù)r，若P(Δf)≥r，則用新生成個體xk替換個體xk-1，否則仍然接受個體xk并對其予以保留。

步驟5：重新評價適應度函數(shù)，從各小生境候選種群中選取最優(yōu)個體形成新一代種群，并取各小生境中適應度最大的個體xk(k=1,2,…,N)進行標記。

步驟6：若迭代次數(shù)達到最高限制，則滿足終止條件算法結束，輸出目標結果；否則更新退火溫度T=ΔT，迭代次數(shù)加1，跳轉到步驟3。

4 算法詳細設計

對所提算法進行詳細設計和說明，包括遺傳算法的具體實現(xiàn)、模擬退火機制的運用以及小生境的控制等。

4.1 編碼與種群初始化

本文首先采用基于路徑表示法的染色體編碼方式，分別為每個業(yè)務獨立地進行染色體編碼，從而形成染色體編碼段。每個染色體段中基因的位置表示業(yè)務路由經過的節(jié)點，所有染色體段拼接成一條染色體，代表網絡中一套完整的業(yè)務路由分配方案。其次，采用以下路徑求解的思路生成初始種群：

步驟1：確定當前網絡拓撲狀態(tài)和業(yè)務請求，將具有相同源匯節(jié)點的業(yè)務請求綁定為一組。

步驟2：根據每一個電力OTN業(yè)務請求的源匯節(jié)點，利用路徑搜索算法獲取端到端之間的所有路徑作為候選路徑。

步驟3：計算候選路徑集中各路徑的光信噪比OSNRJk和信號延時TJk，同時根據光信噪比和時延約束條件將不符合兩者要求的路徑從候選路徑中刪除。針對每個業(yè)務請求，保留最多k條路徑作為備選路由，在此基礎上構建一個備選路徑集合J(S)。

步驟4：對每個業(yè)務Sk(k=1,2,…,M)，從其對應的備選路徑集J(Sk)中隨機選取一條路徑形成個體。由此方式生成不同的個體從而形成初始種群。

4.2 適應度函數(shù)的選取

算法的目標是均衡網絡運行風險，因此把全網風險均衡度作為適應度函數(shù)的重要組成部分，當全網風險均衡度越小，網絡業(yè)務的分布趨于分散，一定程度上體現(xiàn)網路風險低可靠性好。此外，針對多重QoS約束條件下的尋優(yōu)問題[14]，還應當結合相關QoS性能參數(shù)來設計適應度函數(shù)。所以，我們的算法中定義個體X的適度函數(shù)表示如式(7)。

(7)

其中，RB(X)為個體X的全網風險均衡度，ψ(Δ)是懲罰函數(shù)，當某條業(yè)務路由滿足約束時(時延約束或者光信噪比約束)，ψ(Δ)取值為1,否則值域屬于(0,1)。λ和μ分別為信號時延和光信噪比的懲罰函數(shù)的正加權系數(shù)。

4.3 種群的迭代

為了算法能收斂于最優(yōu)解，在選擇個體進行種群迭代時，需要保證適應度高的個體以較大概率被選中。通?？梢圆捎煤唵屋啽P賭機制[15]進行個體的選擇，即樣本空間中個體的選擇概率與其適應度成正比。對于適度函數(shù)值為f(xi)的個體，其選擇概率Pc如式(8)，其中，Nk為組成當代種群的第k個小生境中的個體個數(shù)。特別指出，父代群體中適應度最高的若干個體可直接進入子代樣本空間，不需經過交叉和變異過程如式(8)。

(8)

為了提高算法搜索能力，選取兩個個體作為父母個體，把父母個體中的部分結構進行替換和重組，生成新的個體，并將新生成的個體加入到子代種群中，這一過程稱為交叉。本文采用如下交叉規(guī)則：對選定的父母個體xm和xf，對應的適應度為f(xm)和f(xf)，針對某一業(yè)務請求，以選擇概率如式(9)所示，選取父親個體或母親個體相應染色體段，組合生成新個體xc為式(9)。

(9)

若新個體適應度f(xc)大于父母個體任一方，則接受新個體并進入子代種群；若f(xc)僅大于父母個體一方，則以一定概率接受新個體；若f(xc)小于父母個體任一方，則重新進行交叉過程生成另一新個體xc。

變異過程能夠保證遺傳算法的隨機搜索能力[16]，保證樣本空間物種的多樣性，避免算法過早收斂。算法變異規(guī)則設計如下：完成交叉過程后，新生成的子代個體以某一變異概率隨機對其中某一個染色體段進行變異。若變異操作確定發(fā)生，則從子代業(yè)務路由集合{JS1,JS2,…,JSM}中條選擇JSk作為變異點，將其與業(yè)務Sk的備選路徑集J(Sk)中的某一條備選路徑進行置換，形成新的子代業(yè)務路由集合并進入子代群體。

4.4 模擬退火機制

模擬退火有良好的局部搜索性能。本文所提算法在每代種群進化完成之后，對各小生境的最優(yōu)個體施行退火操作，以降低算法陷入局部最優(yōu)的概率。

首先進行初始溫度T0的設置，T0設置過低時，退火操作無法有效進行，算法很可能迅速進入局部最優(yōu)陷阱；而當T0設置過高時，出現(xiàn)冗余的迭代，降低算法執(zhí)行效率。本文將T0設為式(10)。

(10)

其中，fmax和fmin分別表示初始種群中適應度的最大和最小值，0

4.5 小生境的控制

通過將種群劃分為若干小生境并進行獨立的遺傳操作，一方面細分樣本空間能更好地發(fā)揮模擬退火機制的局部搜索優(yōu)勢，另一方面，將遺傳算法的的單峰尋優(yōu)轉變?yōu)槎喾鍖?yōu)，加快了算法的收斂[17]。本文算法為了簡化分析，僅對種群的小生境劃分問題作出說明。給出業(yè)務路由優(yōu)化算法流程圖如1所示。

圖1 業(yè)務路由優(yōu)化算法流程圖

首先對初始化種群時產生的N個體進行適應度排序，即{x1,x2,…,xN}。其次采用首尾交替等分法對排序結果進行劃分。若劃分為M個小生境，則每組小生境的個體數(shù)為N/M，每組個體依次從序列頭尾交替選取。這樣做能夠保持多樣性，避免小生境之間種群差異過于顯著，并為后續(xù)的局部尋優(yōu)創(chuàng)造條件。

5 實驗仿真與結果分析

運用上述仿真算法，分別在經典實驗網絡拓撲即NSFnet網絡以及某省電力通信公司所提供的現(xiàn)網數(shù)據上進行仿真。首先給拓撲如圖2所示：

圖2 NSFnet網絡拓撲圖

圖3 某省現(xiàn)網OTN網絡拓撲圖

假設網絡中的業(yè)務請求都是單向業(yè)務。用于算法仿真的業(yè)務請求集合都是通過業(yè)務生成程序隨機均勻生成的，為了簡化分析，將業(yè)務時延約束均設置為10，OSNR約束設置為18 dB，業(yè)務重要度隨機取[1,5]之間的整數(shù)值。同時網絡拓撲中的鏈路的風險度也由程序隨機產生，均勻分布在區(qū)間[0,0.3]內。對于算法中各項參數(shù)，將λ和μ均設為0.5，P0為0.8，降溫因子Δ設為0.9。此外，令小生境數(shù)目N為5，設置業(yè)務備選路徑集合大小k為8，路由解搜索在200次迭代內完成，即算法終止條件為迭代次大于等于200。

5.1 基于NSFnet網絡拓撲的實驗分析

為了充分驗證本文所設計的面向可靠性業(yè)務路由優(yōu)化算法的業(yè)務路由配置能力和業(yè)務風險均衡能力，本文基于NSFnet拓撲進行了15組對比實驗。在每個實驗組中，隨機生成M個業(yè)務請求，M在區(qū)間[15,30]內以等概率隨機取值。15組實驗分別對應的業(yè)務請求數(shù)量如下表所示：

在每一組實驗中，分別應用最短路徑算法、遺傳算法以及本文所提的路由優(yōu)化算法，為M個業(yè)務請求進行路由選擇。實驗仿真結果如下圖4所示，柱狀圖橫坐標為實驗組號，對應于15個包含不同業(yè)務請求集合的實驗組；柱狀圖縱坐標為路由選擇方案的風險均衡度。

表1 15組實驗的業(yè)務請求數(shù)量

圖4 算法風險均衡度對比圖

根據對比結果可以看出，在上述仿真場景下，應用最短路徑算法時的全網業(yè)務風險均衡度高，業(yè)務分布不均衡的問題較為嚴重；應用遺傳算法和本文所提方法所獲取的風險均衡度相對較低，業(yè)務路由分布集中的問題在一定程度上得到改善，兩者的目標函數(shù)計算結果基本一致，后者略優(yōu)于前者。其根本原因在于，最短路徑算法雖然在解決最短距離問題以及求解效率上有極大優(yōu)勢，但未考慮業(yè)務分布過于集中的風險，因此求解路由時趨向于選擇少數(shù)看似“性能好”的路徑為業(yè)務路由，導致業(yè)務分布較為擁擠，網絡局部運行風險大。遺傳算法和本文所提方法均從全局角度控制風險過度集中，而本文所提算法結合了遺傳算法和模擬退火機制，相比簡單的遺傳算法，能夠考察更為豐富的樣本空間，并且兼具了良好的全局和局部尋優(yōu)能力。

此外，在仿真中還隨機選取了一個實驗組來驗證算法的效率，仿真結果如圖5所示。

圖5 算法收斂曲線

不難看出，由于本文設計算法利用小生境思想，將遺傳進化的單峰尋優(yōu)轉化為多峰尋優(yōu)，在一定程度上加快了算法的收斂速度，同時也能夠獲取更高質量的解空間。

5.2 基于某省電力通信OTN的實驗分析

在已知某省電力通信OTN的網絡拓撲、業(yè)務分布以及節(jié)點/鏈路物理參數(shù)的情況下，根據前述內容，可以計算當前網絡狀態(tài)下的風險均衡度、平均OSNR值、業(yè)務平均時延等指標。本實驗基于某省電力通信OTN網絡拓撲和業(yè)務分布，利用所設計算法對網絡中現(xiàn)有業(yè)務路由進行全局優(yōu)化，仿真對比結果如下表2所示。

表2 路由算法優(yōu)化前后性能對比

由對比結果可以看出，利用該算法對網絡現(xiàn)有業(yè)務進行優(yōu)化，可以有效均衡網絡風險，提高電力OTN業(yè)務運行的可靠性。此外，由于本文所設計算法針對多重QoS約束條件下(主要是光信噪比和信號時延)的尋優(yōu)問題，算法也會對業(yè)務路由的平均時延和平均OSNR造成影響。算法中適應度函數(shù)的設計，使業(yè)務路由分配時更趨向于選擇光信噪比參數(shù)值高的光通道，因此經過該路由優(yōu)化算法，平均OSNR值得到提高；而不同于最短路徑算法，該算法趨向于將業(yè)務分散部署，因此路由的選擇未必是最短距離，在一定程度上也就導致業(yè)無信號的傳輸時延增加。

6 總結

針對網絡風險不均衡的問題，以網絡風險均衡度為優(yōu)化目標，綜合考慮時延約束和OTN網絡所特有的光信噪比約束，本文提出了一種面向可靠性的電力OTN業(yè)務路由優(yōu)化算法。算法在實現(xiàn)上將遺傳算法的全局搜索能力與模擬退火機制的局部尋優(yōu)能力有機結合，并利用小生境思想，可以以較快的收斂速度獲取一組全網風險均衡度較好的業(yè)務路由解。最后通過仿真實驗，驗證了算法能夠有效降低對全網業(yè)務路由進行優(yōu)化，達到最佳風險均衡目標，同時也具有較好的算法效率和收斂性。