一種基于ACO的光網(wǎng)絡(luò)RWA優(yōu)化方法及應(yīng)用

孫媛媛，盧利鋒，周 靜，胡紫巍，翟明岳，劉國軍

（1.華北電力大學(xué)電氣與電子工程學(xué)院，北京 102206； 2.全球能源互聯(lián)網(wǎng)研究院，北京 102211）

一種基于ACO的光網(wǎng)絡(luò)RWA優(yōu)化方法及應(yīng)用

孫媛媛1，盧利鋒2，周 靜2，胡紫巍2，翟明岳1，劉國軍2

（1.華北電力大學(xué)電氣與電子工程學(xué)院，北京 102206； 2.全球能源互聯(lián)網(wǎng)研究院，北京 102211）

針對光傳輸網(wǎng)絡(luò)中由于光纖和波長資源有限而導(dǎo)致的RWA（路由波長分配）問題，基于ACO（蟻群算法）框架提出了一種優(yōu)化算法SS-ACO（服務(wù)選擇ACO），在蟻群探索方案空間過程中增加了業(yè)務(wù)選擇機(jī)制，改進(jìn)了螞蟻轉(zhuǎn)移概率和信息素更新方法，有利于提高算法的尋優(yōu)能力，能有效降低網(wǎng)絡(luò)業(yè)務(wù)阻塞率。結(jié)合網(wǎng)格網(wǎng)絡(luò)和實際網(wǎng)絡(luò)進(jìn)行了仿真實現(xiàn)。

蟻群算法；信息素；阻塞率；路由波長分配；電力通信網(wǎng)

0 引 言

WDM（波分復(fù)用）技術(shù)以不同的波長作為傳輸信道來傳遞信息，因此波長資源是WDM光網(wǎng)絡(luò)中最重要的資源［1-2］。由于RWA（路由波長分配）問題本身是NP-C問題，網(wǎng)絡(luò)規(guī)模越大，算法的復(fù)雜度越高。在工程上，一般將RWA問題分為路由子問題和波長子問題串行解決，由于這類方法一般采用最短路徑尋路，采用首次命中方式分配波長，可能出現(xiàn)多條光通道占用同一鏈路，導(dǎo)致網(wǎng)絡(luò)需要的波長數(shù)較多，在網(wǎng)絡(luò)波長資源有限的情況下阻塞率較高。因此，有必要研究新的啟發(fā)式算法以期得到更優(yōu)化的規(guī)劃方案。

本文基于ACO（蟻群算法）的啟發(fā)式思想，結(jié)合分層圖方法，提出一種優(yōu)化算法SS-ACO（服務(wù)選擇ACO），增加了業(yè)務(wù)選擇機(jī)制，引入業(yè)務(wù)信息素，改進(jìn)了螞蟻選路和信息素更新環(huán)節(jié)，能有效提高算法的尋優(yōu)能力，降低網(wǎng)絡(luò)業(yè)務(wù)阻塞率。然后，結(jié)合網(wǎng)格網(wǎng)絡(luò)和某省電力骨干通信網(wǎng)絡(luò)進(jìn)行仿真實現(xiàn)，將算法結(jié)果與現(xiàn)有算法進(jìn)行了比較。

1 SS-ACO數(shù)學(xué)模型

給定網(wǎng)絡(luò)G=（V，E），其中，V=｛v1，…，v|V|｝為網(wǎng)絡(luò)節(jié)點集合，E=｛e1，…，e|E|｝為節(jié)點間的光纖鏈路集合。每條光纖能夠使用|Λ|個不同波長進(jìn)行并行無干擾傳輸，Λ=｛λ1，…，λ|Λ|｝。對于任一節(jié)點v，有鄰節(jié)點預(yù)備集N｛n1，…｝，其每一個元素與v直接相鄰。網(wǎng)絡(luò)鏈路e上分布的信息素τqe表示q的路由包含鏈路e的可能性。

設(shè)需求空間Q=｛q1，…，q|Q|｝，其中，qi=（si，di）（si、di∈V，si≠di）表示節(jié)點si到di的連接請求。對于同一源-宿節(jié)點對，可能有多個連接請求，這種情況對應(yīng)于實際網(wǎng)絡(luò)中帶寬需求較大的業(yè)務(wù)。對于任一請求q，有相應(yīng)信息素τq和啟發(fā)式信息ηq，其中，τq表示最佳方案能應(yīng)答q的可能性，ηq與q的最短路徑長度成反比。

A=｛a1，…，a|A|｝為解決方案，其中ai=（rj，λk），包括為請求q=（s，d）∈Q分配的波長λk（λk∈Λ）和路由其中，vj1，…，vjn∈V，ej0，…，ejn∈E。

此外，本文遵循以下原則:（1）對于光通路（sn→dn），在所分配路由包含的每條鏈路上都使用相同波長λk傳遞信息。這是由于在中繼節(jié)點變換波長需要實現(xiàn)光/電/光轉(zhuǎn)換，成本過高。（2）對于經(jīng)過同一鏈路的不同光通道，必須采用不同波長承載信息。即對于?e∈E，?λ∈Λ，不存在e∈ri，e∈rj，且ai=（ri，λ），aj=（rj，λ）∈A。

本文中RWA的優(yōu)化目標(biāo)是使解決方案A能滿足盡量多的業(yè)務(wù)需求。

2 SS-ACO描述

基于ACO框架，利用螞蟻群體覓食過程中的正反饋機(jī)制，派出多只螞蟻獨立探索方案空間，經(jīng)過多次迭代得到最佳方案。本文所提SS-ACO的框架如圖1所示。

圖1 SS-ACO框架

SS-ACO的主要步驟如下:

步驟1:初始化。初始化是設(shè)置ACO計算參數(shù)、方案空間中初始信息素和啟發(fā)式信息的重要過程，關(guān)系到算法最終解決方案性能的優(yōu)劣。ACO計算參數(shù)包括阻塞迭代次數(shù)Niter、螞蟻數(shù)Nants、信息素蒸發(fā)速率ρ和信息素邊界比γ等。

步驟2:派出新螞蟻ai搜索方案空間。

步驟3:選擇可用波長，其原則是使用一個波長響應(yīng)盡可能多的請求。即將波長資源進(jìn)行編號后，按一定順序依次選擇，判斷當(dāng)前波長不能再滿足任一業(yè)務(wù)時，再啟用新波長。

步驟4:基于選定的波長圖，螞蟻ai按照業(yè)務(wù)選擇機(jī)制從需求空間選取請求q。

步驟5:為連接請求q尋路，按照蟻群尋路規(guī)則在步驟3選定的波長圖上尋找最優(yōu)路徑。

步驟6:判斷網(wǎng)絡(luò)波長資源是否用盡:否，則轉(zhuǎn)至步驟3；是，則得到螞蟻ai的解決方案Ai。

步驟7:判斷是否所有螞蟻都找到解決方案:否，則轉(zhuǎn)至步驟2；是，則從蟻群方案中選出本次迭代所得最佳迭代方案Aib。

步驟8:當(dāng)|Aib|＞|Abs|時，令A(yù)bs←Aib，其中Abs為準(zhǔn)最佳方案。按照信息素更新規(guī)則更新全局信息素和局部信息素。

步驟9:判斷是否滿足算法終止條件，即準(zhǔn)最佳方案Abs的性能在之后Niter次迭代不再提高。若不滿足，則轉(zhuǎn)至步驟2。

為避免算法陷入局部最優(yōu)而使最終方案質(zhì)量不夠高，重啟算法Nreset次。

2.1 業(yè)務(wù)選擇機(jī)制

業(yè)務(wù)選擇機(jī)制，即如何從需求集合中選取要響應(yīng)的請求。首先，計算每個業(yè)務(wù)在當(dāng)前波長圖上的最短路由長度l，移除不可應(yīng)答請求，為可應(yīng)答請求設(shè)置啟發(fā)式信息ηq，其與l成反比，即

然后，以概率pq從可響應(yīng)請求中隨機(jī)選取一個請求。pq定義為

式中，α、β分別為信息素和啟發(fā)式信息的計算權(quán)重；γ為0～1的實數(shù)；Ni為當(dāng)前的迭代次數(shù)。在算法運(yùn)行初期，pq幾乎與τq和ηq無關(guān)，隨機(jī)選取請求進(jìn)行應(yīng)答，即螞蟻能更自由地探索方案空間，利于獲得更優(yōu)質(zhì)的解決方案。隨著迭代次數(shù)的增加，pq受信息素和啟發(fā)式信息的影響增大，即選擇其他螞蟻選過的或路由較短的請求的可能性更大，利于方案收斂。

2.2 螞蟻尋路規(guī)則

當(dāng)為請求q=（s，d）選定路由時，由源節(jié)點s起，從當(dāng)前節(jié)點的動態(tài)候選點集N′中迭代地選擇下一跳，直到到達(dá)目的節(jié)點d。一般地，對于節(jié)點u，其鄰節(jié)點預(yù)備集是與u相鄰且能到達(dá)d的節(jié)點集合。對于N′中的任一點v，計算其到d的最短路徑長度lr，設(shè)置鏈路（u，v）上的啟發(fā)式信息ηv，u與最短路徑長度lr成反比。此處，當(dāng)候選點就是目的節(jié)點時，lr為0，由于lr作分母，故將lr作加1處理，即該式為

以概率pr來選取候選節(jié)點作為下一跳，直至到達(dá)宿節(jié)點d。pr定義為

式中，τq（u，v）為鏈路（u，v）的信息素濃度。在算法運(yùn)行初期，Ni/Niter較小，螞蟻以近乎等概率選取下一跳節(jié)點，利于螞蟻探索方案空間。隨著算法的運(yùn)行，螞蟻會優(yōu)先選靠近目的節(jié)點的節(jié)點及頻繁訪問的邊緣附近的節(jié)點，利于方案收斂。

2.3 信息素更新

信息素蒸發(fā)是整個啟發(fā)式算法的關(guān)鍵，它保證了隨機(jī)得到的壞方案不會對之后的迭代造成持續(xù)影響。當(dāng)蟻群方案建立完成后，令全局信息素以固定速率ρ蒸發(fā):

在得到迭代準(zhǔn)最佳方案Aib和準(zhǔn)最佳方案Abs后，隨機(jī)選取Aib或Abs為A。選擇Aib的概率越大，越有利于探索方案空間，相反則更利于算法收斂。令:

從而使所得方案更好，該方案中各元素的信息素濃度越高，越有利于方案收斂。最后，按照MAX-MIN（最大-最?。┪浵佅到y(tǒng)的要求將信息素濃度限制在［τmin，τmax］范圍內(nèi)。

3 算法仿真分析

3.1 網(wǎng)格網(wǎng)絡(luò)仿真實現(xiàn)

以4×4的網(wǎng)格網(wǎng)絡(luò)為仿真網(wǎng)絡(luò)，需求空間由計算機(jī)隨機(jī)生成，將本文的SS-ACO與一般ACO（Tra-ACO）和SPMU（最短路徑最多使用）算法方案進(jìn)行比較，如圖2所示。在一般ACO中，螞蟻以相同概率從需求空間隨機(jī)選取請求，螞蟻尋路時的轉(zhuǎn)移概率僅與網(wǎng)絡(luò)信息素分布和啟發(fā)式信息相關(guān)，當(dāng)一只螞蟻建立了螞蟻方案后，便更新局部信息素。

由仿真結(jié)果可知:當(dāng)需求空間大小一定時，隨著網(wǎng)絡(luò)波長數(shù)的增加，解決方案能響應(yīng)更多的連接請求；當(dāng)網(wǎng)絡(luò)波長數(shù)一定時，需求空間越大，解決方案能支持的業(yè)務(wù)需求越多。且當(dāng)波長資源一定，需求空間越大，SS-ACO相對于其他兩種算法的優(yōu)勢越明顯，這是由于SS-ACO引入了業(yè)務(wù)選擇機(jī)制，在算法運(yùn)行后期，會先應(yīng)答路徑較短的業(yè)務(wù)。如果先為路徑較長的請求分配了網(wǎng)絡(luò)資源，可能導(dǎo)致拒絕更多與其包含重復(fù)鏈路的請求。由于信息素更新是在建立蟻群方案之后，各螞蟻探索方案空間不受其他螞蟻信息素的影響，因此蟻群探索方案的過程是并行的，可避免過早進(jìn)入局部最優(yōu)。

圖2 3種算法的性能比較（4×4網(wǎng)格網(wǎng)絡(luò)）

3.2 實際網(wǎng)絡(luò)仿真實現(xiàn)

以某省電力通信網(wǎng)省干OTN（光傳輸網(wǎng)）主平面為例，其拓?fù)淙鐖D3所示。全網(wǎng)采用40× 10 Gbit/s帶寬，網(wǎng)絡(luò)結(jié)構(gòu)分為骨干層和接入層。骨干層節(jié)點為省公司和變電站，接入層節(jié)點為地市公司，共配置節(jié)點設(shè)備30套，光纖鏈路47條。

圖3 某省電力通信網(wǎng)省干OTN主平面拓?fù)鋱D

由于電力通信網(wǎng)是電網(wǎng)生產(chǎn)、管理及營銷的專用通信網(wǎng)，該網(wǎng)絡(luò)主要承載的業(yè)務(wù)包括調(diào)度數(shù)據(jù)網(wǎng)業(yè)務(wù)、數(shù)據(jù)通信網(wǎng)業(yè)務(wù)和省干A網(wǎng)。根據(jù)《電力通信網(wǎng)規(guī)劃設(shè)計技術(shù)導(dǎo)則》、《“十三五”期間各類變電站和辦公場所典型帶寬預(yù)測模型》（信通計劃［2015］82）的方法與要求［3-5］，結(jié)合該省業(yè)務(wù)網(wǎng)絡(luò)特點，預(yù)測該網(wǎng)絡(luò)的主要業(yè)務(wù)帶寬需求如表1所示。

表1 某省骨干網(wǎng)主要業(yè)務(wù)帶寬需求預(yù)測

為評價網(wǎng)絡(luò)的業(yè)務(wù)發(fā)展適應(yīng)性，引入LLR（鏈路負(fù)載率）指標(biāo)，其定義如下:LLR=（Boccupy/B）× 100%，式中，Boccupy為被占用的波長；B為鏈路總帶寬。LLR是評價鏈路負(fù)載是否過重的指標(biāo)，其中，空載鏈路、輕載鏈路、較重載鏈路和重載鏈路分別對應(yīng)LLR=0、0＜LLR≤30%、30＜LLR≤60%和LLR＞60%［6］。重載鏈路數(shù)比重越大，網(wǎng)絡(luò)適應(yīng)性越差。

基于上述網(wǎng)絡(luò)與需求空間，考慮業(yè)務(wù)發(fā)展需求和階段性部署特點，我們將各節(jié)點出口帶寬以逐年遞增的方式進(jìn)行測算，即需求空間大小分別增長為140、280、420、560、840和1 120。下面利用SSACO優(yōu)化算法對某省干OTN主平面的業(yè)務(wù)通道層進(jìn)行模擬仿真，算法結(jié)果對比如圖4所示。

圖4 3種算法性能比較（實際網(wǎng)絡(luò)）

比較算法方案可知，對于特定網(wǎng)絡(luò)和可預(yù)測的需求空間，隨著需求空間的增長，SS-ACO優(yōu)化算法的解決方案一直優(yōu)于其他兩種算法。根據(jù)SS-ACO仿真結(jié)果，目前全網(wǎng)有70條業(yè)務(wù)需求都可應(yīng)答，解決方案僅使用了20個波長。全網(wǎng)共有47×40條鏈路，方案鏈路利用率為12.3%。可見，對于目前的網(wǎng)絡(luò)業(yè)務(wù)需求，該網(wǎng)絡(luò)資源較為充裕。但是由于網(wǎng)絡(luò)資源一定，隨著業(yè)務(wù)需求的逐步增長，必定會有業(yè)務(wù)無法得到響應(yīng)，網(wǎng)絡(luò)阻塞率變高。

另外，考慮網(wǎng)絡(luò)容災(zāi)、可靠性等因素，計算了當(dāng)需求空間分別為140和280時，網(wǎng)絡(luò)中負(fù)載較重的鏈路的分布情況，如圖5所示。

圖5 重載鏈路分布情況

圖中，虛線鏈路表示重載鏈路（LLR＞60%），加粗鏈路為較重載鏈路（30＜LLR≤60%），其他為輕載鏈路（0＜LLR≤30%）?？梢?，重載鏈路多為單根光纜鏈路，而對于鏈路（FX變-ZJ公司），雖然承載的業(yè)務(wù)數(shù)最多，但由于其采用雙光纜配置，降低了負(fù)載壓力。這是由于，在業(yè)務(wù)層各地市公司分別到省公司、備調(diào)公司的業(yè)務(wù)均呈匯聚型，而傳輸層主要呈現(xiàn)環(huán)網(wǎng)結(jié)構(gòu)，因此網(wǎng)絡(luò)負(fù)載不均衡。對于重載鏈路，其波長占用率較高，隨著網(wǎng)絡(luò)需求的增加，這些鏈路將成為“瓶頸”鏈路，因此應(yīng)對該鏈路及時升級，對該鏈路進(jìn)行雙光纜配置，或在相關(guān)站點（如省公司1和SG變）間鋪設(shè)直通光纜，并對中間路由器制定負(fù)載均衡策略，以緩解網(wǎng)絡(luò)流量壓力局部過大，使該網(wǎng)絡(luò)由環(huán)網(wǎng)結(jié)構(gòu)向網(wǎng)狀網(wǎng)結(jié)構(gòu)發(fā)展與演進(jìn)。

4 結(jié)束語

本文基于ACO框架，提出了一種有業(yè)務(wù)選擇機(jī)制的RWA優(yōu)化算法，尤其在需求空間較大的情景中，能夠有效提高網(wǎng)絡(luò)的業(yè)務(wù)承載能力。通過改進(jìn)螞蟻轉(zhuǎn)移概率，使螞蟻在算法初期能自由地探索方案空間，算法后期又利于方案收斂。此外，本文的算法能延伸為解決多并發(fā)業(yè)務(wù)的DRWA（動態(tài)RWA）問題。結(jié)合網(wǎng)格網(wǎng)絡(luò)和某省電力通信省干OTN進(jìn)行了算法的仿真實現(xiàn)，并評價了該省干網(wǎng)絡(luò)對承載業(yè)務(wù)發(fā)展的適應(yīng)性。

［1］劉愛波，陸月明，紀(jì)越峰.智能光網(wǎng)絡(luò)路由及其關(guān)鍵技術(shù)分析［J］.光網(wǎng)絡(luò)，2004，（8）:29-31.

［2］孫海金，朱娜，周乃富.基于蟻群系統(tǒng)的分布式RWA算法研究［J］.光通信研究，2005，（2）:30-34.

［3］周靜，熊素琴，蘇斌，等.一種電力通信網(wǎng)絡(luò)運(yùn)行質(zhì)量量化評估方法及應(yīng)用［J］.電網(wǎng)技術(shù)，2012，36（9）: 168-172.

［4］劉貴榮，周靜，趙子巖，等.電力通信網(wǎng)SDH環(huán)容量均衡優(yōu)化算法研究［J］.電信科學(xué)，2010，（12）:140-144.

［5］周靜，呂天光，陳希，等.省級電力調(diào)度數(shù)據(jù)網(wǎng)帶寬分析與容量規(guī)劃研究［J］.電網(wǎng)技術(shù)，2012，36（5）:173-177.

［6］周靜，陳希.電力通信網(wǎng)規(guī)劃仿真技術(shù)研究及其典型應(yīng)用［J］.電力系統(tǒng)通信，2012，33（242）:25-29.

An Optimization Method of Optical Network RWA Based on ACO and Its Application

SUN Yuan-yuan1，LU Li-feng2，ZHOU Jing2，HU Zi-wei2，ZHAI Ming-yue1，LIU Guo-jun2
（1.School of Electrical&Electronic Engineering，North China Electric Power University，Beijing 102206，China；2.Global Energy Internet Research Institute，Beijing 102211，China）

Focusing on the RWA problem in optical transmission network，we proposed a RWA optimization algorithm based on ant colony algorithm framework.The way of choosing a request from requests zone is introduced，which would improve optimization ability of the algorithm.In addition，the way of updating pheromone and searching routes in ACO algorithm are also improved.This method can effectively reduce the network traffic congestion.Finally，we conduct a simulation to demonstrate the proposed method in a grid network and a province electric power communication network.

ACO；pheromone；congestion rate；RWA；electric power communication network

TN915

A

1005-8788（2016）05-0019-04

10.13756/j.gtxyj.2016.05.006

2016-05-18

國家電網(wǎng)公司2015年科技項目（SGRIXTKJ［2015］241）

孫媛媛（1991-），女，河北邢臺人。碩士研究生，主要從事電力通信網(wǎng)絡(luò)規(guī)劃的研究。