基于自適應蟻群的多約束ＱｏＳ組播路由算法

梁　瀟

摘 要：結合多約束QoS組播路由的特點，應用一種自適應蟻群優化算法解決組播路由問題。考慮到實際通信中鏈路利用率對網絡的影響，將網絡中鏈路的帶寬轉化為鏈路的代價問題，并在蟻群算法中根據螞蟻所選路徑的代價進行信息素更新，增加了信息素調整的自適應性，同時加快了算法的收斂速度,使得組播路由算法在考慮網絡QoS約束的基礎上進一步貼合實際網絡的需求。

關鍵詞：QoS;蟻群算法;自適應;鏈路利用率

中圖分類號：TN919文獻標識碼：B

文章編號：1004-373X(2009)05-017-03

Multi-constrained QoS Multicast Routing Algorithm Based on Adaptive Ant Colony Algorithm

LIANG Xiao

(Computer Science and Technology School,Wuhan University of Technology,Wuhan,430070,China)

Abstract：This paper unifies the characteristics of multi-constrained QoS multicast routing problem,by using an improved adaptive ant colony optimization algorithm to solve multicast routing problem.In real network communications,by considering the link utilization influence transforms bandwidth of link into cost problems.According to the cost of the way which ants choose to updating pheromone,increase the adaptability of pheromone updating,then improve convergence ability of algorithm.Cause the multicast routing algorithm in considering the QoS constraints of network on the basis of further conforms to actual network demands.

Keywords：QoS;ant colony algorithm;adaptive;link utilization

0 引 言

隨著高速網絡技術的發展，與多媒體相關的實時業務應用大量興起［1］，而有效的組播路由［2］是實現多媒體通信的關鍵技術。傳統的組播通信大多采用“盡力而為”，沒有很好地考慮服務質量QoS (Quality of Service)［3］。隨著網絡的發展，多媒體通信對網絡的服務質量QoS提出了越來越高的要求，QoS組播路由問題應運而生。QoS組播路由問題是指在分布的網絡中尋找最優路徑［4］,要求從源節點出發,歷經所有的目的節點,找到一條滿足網絡路由中延時、帶寬、丟包率等約束條件且花費最小的網絡路徑。Wang Z 等學者已經證明了包含兩個及以上約束條件的QoS網絡路由是一個NP完全問題［5］。

蟻群算法(Ant Colony Algorithm,ACA)是上世紀90年代意大利學者 M．Dorigo和V．Maniezzo等人通過模擬自然界螞蟻尋徑的行為提出的一種全新啟發式算法，它被廣泛用于解決各種NP完全問題［6］。現利用一種基于自適應蟻群優化算法，提出考慮網絡鏈路利用率的QoS多約束條件下組播路由解決方法。

1 基本蟻群算法

蟻群算法是一種新近發展起來的、模擬螞蟻群體覓食行為的仿生優化算法。螞蟻在尋找食物的運動過程中，能在其經過的路徑上分泌一定數量具有氣味的稱為信息素的物質進行信息傳遞，并指導自己的運動方向。某一路徑上走過的螞蟻越多，此路徑上螞蟻留下的信息素軌跡也越多，則后來螞蟻選擇該路徑的概率也越大，從而更增加了該路徑被選擇的可能性。同時，路徑上的信息素也會隨著時間的流逝而不斷地揮發，這種機制所得螞蟻不完全受過去經驗的約束，有利于螞蟻向新的路徑搜索。隨著時間的推移，螞蟻就會找到由蟻巢到食物源的最優路徑。該算法采用了正反饋并行自催化機制，具有較強的魯棒性、優良的分布式計算機制、易于與其他方面結合等優點。

蟻群算法利用隨機策略，使得進化速度較慢，收斂速度不理想；利用正反饋強化性能較好的解，但導致當前不被選用的路徑，往后被選用的概率越來越小，使算法在某些局部最優解附近徘徊，出現停滯現象，而且揮發系數ρ的存在會使那些從未搜索到的路徑上的信息素量逐漸減少到0，從而降低算法的全局搜索能力。若ρ過大，會使以前搜索過的路徑被再次選擇的可能性過大，影響算法的全局搜索能力，易于陷入局部最優解；若ρ過小，雖然可以提高算法的全局搜索能力，但會使算法的收斂速度降低。1996年Gambardella和Dorigo提出了一種修正的蟻群算法(ACS)［7］，該算法對信息素的更新策略作了相應的改進，即使用：

(1) 局部信息更新，螞蟻從城市i轉移到城市j后，路徑上的信息素按式(1)進行更新：

τ璱j(t+1)=(1－ξ)τ璱j(t)+ξτ璷

(1)

式中：ξ∈(0,1)，τ璷為常數。

采用局部信息更新策略減小了已選擇過的路徑再次被選擇的概率，提高了算法的全局搜索能力。

(2) 全局信息更新，針對全局最優解所屬邊按式(2)進行信息素更新：

τ璱j(t+n)=(1－ρ)τ璱j(t)+ρΔτ琯b璱j(t)，ρ∈(0,1)

(2)

式中:Δτ琯b璱j(t)=1/L璯b;L璯b為當前全局最優解的路徑長度。采用全局信息更新策略，增強了全局最優解路徑上的信息素，加強了算法的正反饋作用，從而加快算法的收斂速度。

2 QoS網絡路由模型

2.1 QoS組播路由問題的基本概念和網絡模型定義

就組播路由而言，網絡通常表示成一個帶權圖G=(V，E)，其中V代表節點集合;E代表網絡中雙向鏈路集合,關聯每條鏈路的參數就是該鏈路的QoS度量。在此，E表示網絡中雙向鏈路的集合［8］；S為源節點，S∈V；M∈{V－{S}}為目的節點集，S，M組成組播樹T(s,M)。對于任一鏈路e∈E，可定義某些屬性：延時函數：delay(e):E∈R+；費用函數cost(e):E∈R+；帶寬函數bandwidth(e):E∈R+。對于任一網絡節點n∈V，定義某些屬性：延遲函數delay(n):V∈R+；費用函數cost(n):V∈R+，由此存在如下關系：

delay(p璗(s,t))=∑e∈p璗(s,t)delay(e)+∑n∈p璗(s,t)delay(n)(3)

cost(T(s,M))=∑e∈T(s,M)cost(e)+∑n∈T(s,M)cost(n)

(4)

bandwidth(p璗(s,t))=min{bandwidth(e),e∈p璗(s,t)}

(5)

式中:p璗(s,t)為組播樹T(s,M)上源點s到終點t的路徑。

QoS組播路由問題是要尋找一顆組播樹T(s,M)滿足：

延時約束：

delay(p璗(s,t))

(6)

帶寬約束：

bandwidth(p璗(s,t))>B

(7)

式中：B表示帶寬約束;D璽表示延時約束。

費用函數(目標函數)可描述為在所有滿足條件的組播樹中，cost(T(s,M))最小。

2.2 網絡負載和鏈路利用率

為考慮鏈路利用率的情況,將鏈路代價定義為［9］：

cost(e)=Xbandwidth(e), X=108

(8)

E中的每條邊對應網絡中的一條鏈路e璱,j,其中i表示上游路由器;j表示下游路由器。e璱,j具有三個屬性：Maximum Bandwidth(MB)，Reserved Bandwidth(RB),Unreserved Bandwidth(UB)。因此有對任意e∈E，鯩B(i,j),RB(i,j)和UB(i,j)，并且MB(i,j)=RB(i,j)+UB(i,j)。在式(8)的基礎上,定義式(9),用來計算圖G中每條鏈路的代價。

cost(e)=XMB(i,j),RB(i,j)=0XUB(i,j),RB(i,j)≠0且UB(i,j)≠0∞,RB(i,j)≠0且UB(i,j)=0

(9)

由式(9)可知,剩余帶寬越大,鏈路代價越小;反之,鏈路代價越大。

3 自適應蟻群算法的QoS組播問題實現

3.1 適應度函數

適應度函數是蟻群進行路徑選擇的依據，也就是螞蟻從初始路徑集Ω璱中選擇第j條路徑的概率：

f(p璲)=phe璸璲(s,D璱)∑p璱∈Ω璱phe璸璱(s,D璱)

(10)

式中: phe璸璲(s,D璱)是路徑p璲(s,D璱)上的分泌物強度，它表明某條路徑上的分泌物強度越大，該路徑被選中的概率也就越大。初始狀態時各條路徑上的分泌物強度相同。

3.2 螞蟻的信息素調整

螞蟻尋找路徑時，按以下規則進行信息素調整：

(1) 對螞蟻所經過的路徑進行分泌物強度調整。其中a是常量參數;cost(e)為該路徑的代價;phe璸璱(s,D璱)為源節點S到目的節點D璱的路徑上的分泌物強度。調整后,有:

phe璸璱(s,D璱)=phe璸璱(s,D璱)+acost(e)

(11)

上述公式與文獻［10］不同，信息素的調整不是固定值，而是根據所選擇路徑的代價來調整的，并且路徑代價受帶寬影響，是根據鏈路利用率來確定的。增加信息調整的自適應性，同時也加快了收斂速度。

(2) 當螞蟻都走完一條路徑時，對所有路徑進行分泌物揮發調整。其中ρ是揮發度;Δ為各條路徑上的初始信息強度。

phe璸璱(s,D璱)=(1－ρ)*phe璸璱(s,D璱),phe璸璱(s,D璱)>0.05Δ

D璱∈D

0,其他

(12)

(3) 當螞蟻都找到所有目的節點，組成一顆組播樹時，再按式(13)進行信息素調整，即:

phe璸璱(s,D璱)=phe璸璱(s,D璱)+Bcost(T)

(13)

式中:B為常量參數;cost(T)為該組播樹的代價;p璱(s,D璱)是被選路徑。

3.3 算法步驟

Step 1：生成初始路徑集。找出從源節點S到每個目的節點D璱∈D (i=1,2,…,m)滿足延時約束的有效路徑，并組成初始路徑集Ω璱。

Step 2：初始化α,β,B,ANTn和初始集中各條路徑上的信息強度Δ。

Step 3：從源節點發出ANTn只螞蟻，按式(10)計算路徑集Ω璱中每條路徑的適應度，每只螞蟻再按賭輪旋轉規則從中選擇一條路徑，再按式(11)進行分泌物強度調整。

Step 4：當每只螞蟻都完成一條路徑選擇后，按式(12)進行分泌物揮發性調整。

Step 5：重復執行Step 3和Step 4，直到螞蟻找到所有目的節點的路徑，每只螞蟻尋找到的路徑各組成一顆組播樹。計算各組播樹的代價(相同鏈路的代價只計算一次)，判斷是否大多數螞蟻收斂于同一組播樹，如果是，則該組播樹為最優路徑，退出程序；否則，用代價最小的組播樹替代代價最大的組播樹，轉執行Step 6。

Step 6：螞蟻按原路返回，并按式(13)調整返回路徑上的分泌物強度，再轉Step 3執行。

4 實驗仿真和算法分析

本文采用改進的Waxman網絡拓撲仿真模型［11］,利用Matlab 7.0進行仿真，其特點是每對節點之間按概率p(u,v)=βexp(－d(u,v)/2an)相連，其中d(u,v)為u,v兩節點之間的距離，并且按照Salama和Reeves在Waxman基礎上的網絡生成算法使平均節點度達到指定值。參數α,β分別控制網絡中長邊和短邊的比例以及邊的密度，n為網絡節點個數。參數的選取如表1所示。表2列出了30個節點的網絡仿真試驗中，兩種不同算法在不同延時約束條件下的組播樹代價。每次試驗分別進行20次，其中代價值分別是20次試驗得到的平均值。從表2容易看出，算法IAAC比算法AAC在相同延時條件下生成組播樹的代價要小。圖1描述了兩種算法在30個網絡節點的網絡仿真中，組播樹的代價隨迭代次數的變化情況。從圖中可以看出，IAAC算法在收斂速度上要優于AAC算法，并且在最優組播樹的代價上也要優于AAC算法。圖2顯示了兩種算法在隨著網絡節點數變化時，組播樹代價的變化情況。隨著網絡節點數的增加，IAAC算法所得最優組播樹的代價低于AAC算法所得最優組播樹的代價，并且最優組播樹的代價增加比AAC算法得到最優組播樹代價的增加速度要慢。通過仿真試驗，本文改進的自適應蟻群算法能以更快的收斂速度得到最優組播樹，并且最優組播樹的代價相對原有自適應蟻群算法要更優。

表1 蟻群算法參數選取

αβQρn

0.20.31000.530

表2 30個網絡節點運行20次的延時與代價的關系

202428333640

AAC365359358355350346

IAAC355348347345342330

圖1 組播樹代價與迭代次數

圖2 組播樹代價與網絡節點數

5 結 語

本文提出了一種應用自適應蟻群算法并結合實際網絡的鏈路利用率的多約束QoS組播路由算法。將鏈路利用和網絡負載考慮到組播路由中，使得網絡路由問題的研究更符合實際網絡的需求。在運用自適應蟻群時，結合信息素更新的特點，將鏈路代價考慮到其中，使得信息調整的自適應性加強，同時收斂速度得到改善。

參考文獻

［1］Chockler G V,et al.Group Communication Specifications:A Comprehensive Study［J］.ACM Computing Surveys,2001,33(4):1-43.

［2］Wang B,Hou C J.A Survey on Multicast Routing and Its QoS Extensions:Problems,Algorithms and Protocols［J］.IEEE Network Magazine,2000,14(1):22-36.

［3］Xiao X P,Ni L M.Internet QoS:the Big Picture［J］.IEEE Network Magazine,1999,13(2):1-13.

［4］鄒德莉,郝應光.基于非精確狀態信息的QoS組播路由算法［J］.微電子學與計算機,2006,23(9):66-72.

［5］Wang Zheng,Crowcroft J.Quality of Service Routing forSupporting Multimedia Applications［J］.IEEE Journal on Selected Areas in Communications,1996,14(7):1 228-1 234.

［6］Dorigo M,Maniezzo V,Colorni A.Ant System:Optimization by a Colony Cooperating Agents［J］.IEEE Trans.on Systems,Man,and Cybernetics-bart B:Cybernetics,1996,26(1):29-41.

［7］李昌兵.基于計算智能的多播QoS路由技術研究.重慶:重慶大學,2007.

［8］王應征，石冰心.基于遺傳算法的時延受限代價最小組播路由選擇方法.通信學報，2002，23(3)：112-117.

［9］Cisco.OSPF Design Guide［EB/OL］.http://www.cisco.com/warp/public/104/1.html,2004-02.

［10］李生紅，劉澤民.基于蟻群算法的組播路由調度方法.計算機工程，2001,27(4):63-65.

［11］Waxman B M.Routing of Multiple Connections.IEEE Journal on Selected Area in Communications,1986，6(9)：1 622-1 671.

［12］田炳麗，劉常波，解貴新.旋轉貨架揀選作業優化的交叉蟻群算法求解.現代電子技術,2008,31(12):59-61.

作者簡介

梁 瀟 女，1983年出生，湖北監利人，碩士研究生。主要研究方向為智能計算。

軍 事 通 信

馮 正等：多線程串口通信技術在GPS導航中的應用