一種基于ACO的光網絡RWA優化方法及應用

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

（1.華北電力大學電氣與電子工程學院，北京 102206； 2.全球能源互聯網研究院，北京 102211）

一種基于ACO的光網絡RWA優化方法及應用

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

（1.華北電力大學電氣與電子工程學院，北京 102206； 2.全球能源互聯網研究院，北京 102211）

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

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

0 引 言

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

本文基于ACO（蟻群算法）的啟發式思想，結合分層圖方法，提出一種優化算法SS-ACO（服務選擇ACO），增加了業務選擇機制，引入業務信息素，改進了螞蟻選路和信息素更新環節，能有效提高算法的尋優能力，降低網絡業務阻塞率。然后，結合網格網絡和某省電力骨干通信網絡進行仿真實現，將算法結果與現有算法進行了比較。

1 SS-ACO數學模型

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

設需求空間Q=｛q1，…，q|Q|｝，其中，qi=（si，di）（si、di∈V，si≠di）表示節點si到di的連接請求。對于同一源-宿節點對，可能有多個連接請求，這種情況對應于實際網絡中帶寬需求較大的業務。對于任一請求q，有相應信息素τq和啟發式信息ηq，其中，τq表示最佳方案能應答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傳遞信息。這是由于在中繼節點變換波長需要實現光/電/光轉換，成本過高。（2）對于經過同一鏈路的不同光通道，必須采用不同波長承載信息。即對于?e∈E，?λ∈Λ，不存在e∈ri，e∈rj，且ai=（ri，λ），aj=（rj，λ）∈A。

本文中RWA的優化目標是使解決方案A能滿足盡量多的業務需求。

2 SS-ACO描述

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

圖1 SS-ACO框架

SS-ACO的主要步驟如下:

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

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

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

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

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

步驟6:判斷網絡波長資源是否用盡:否，則轉至步驟3；是，則得到螞蟻ai的解決方案Ai。

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

步驟8:當|Aib|＞|Abs|時，令Abs←Aib，其中Abs為準最佳方案。按照信息素更新規則更新全局信息素和局部信息素。

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

為避免算法陷入局部最優而使最終方案質量不夠高，重啟算法Nreset次。

2.1 業務選擇機制

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

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

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

2.2 螞蟻尋路規則

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

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

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

2.3 信息素更新

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

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

從而使所得方案更好，該方案中各元素的信息素濃度越高，越有利于方案收斂。最后，按照MAX-MIN（最大-最小）螞蟻系統的要求將信息素濃度限制在［τmin，τmax］范圍內。

3 算法仿真分析

3.1 網格網絡仿真實現

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

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

圖2 3種算法的性能比較（4×4網格網絡）

3.2 實際網絡仿真實現

以某省電力通信網省干OTN（光傳輸網）主平面為例，其拓撲如圖3所示。全網采用40× 10 Gbit/s帶寬，網絡結構分為骨干層和接入層。骨干層節點為省公司和變電站，接入層節點為地市公司，共配置節點設備30套，光纖鏈路47條。

圖3 某省電力通信網省干OTN主平面拓撲圖

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

表1 某省骨干網主要業務帶寬需求預測

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

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

圖4 3種算法性能比較（實際網絡）

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

另外，考慮網絡容災、可靠性等因素，計算了當需求空間分別為140和280時，網絡中負載較重的鏈路的分布情況，如圖5所示。

圖5 重載鏈路分布情況

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

4 結束語

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

［1］劉愛波，陸月明，紀越峰.智能光網絡路由及其關鍵技術分析［J］.光網絡，2004，（8）:29-31.

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

［3］周靜，熊素琴，蘇斌，等.一種電力通信網絡運行質量量化評估方法及應用［J］.電網技術，2012，36（9）: 168-172.

［4］劉貴榮，周靜，趙子巖，等.電力通信網SDH環容量均衡優化算法研究［J］.電信科學，2010，（12）:140-144.

［5］周靜，呂天光，陳希，等.省級電力調度數據網帶寬分析與容量規劃研究［J］.電網技術，2012，36（5）:173-177.

［6］周靜，陳希.電力通信網規劃仿真技術研究及其典型應用［J］.電力系統通信，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

國家電網公司2015年科技項目（SGRIXTKJ［2015］241）

孫媛媛（1991-），女，河北邢臺人。碩士研究生，主要從事電力通信網絡規劃的研究。