梁　瀟

摘 要：結(jié)合多約束QoS組播路由的特點，應(yīng)用一種自適應(yīng)蟻群優(yōu)化算法解決組播路由問題?？紤]到實際通信中鏈路利用率對網(wǎng)絡(luò)的影響，將網(wǎng)絡(luò)中鏈路的帶寬轉(zhuǎn)化為鏈路的代價問題，并在蟻群算法中根據(jù)螞蟻所選路徑的代價進行信息素更新，增加了信息素調(diào)整的自適應(yīng)性，同時加快了算法的收斂速度,使得組播路由算法在考慮網(wǎng)絡(luò)QoS約束的基礎(chǔ)上進一步貼合實際網(wǎng)絡(luò)的需求。

關(guān)鍵詞：QoS;蟻群算法;自適應(yīng);鏈路利用率

中圖分類號：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 引 言

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

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

1 基本蟻群算法

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

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

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

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

(1)

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

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

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

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

(2)

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

2 QoS網(wǎng)絡(luò)路由模型

2.1 QoS組播路由問題的基本概念和網(wǎng)絡(luò)模型定義

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

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璽表示延時約束。

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

2.2 網(wǎng)絡(luò)負載和鏈路利用率

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

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

(8)

E中的每條邊對應(yīng)網(wǎng)絡(luò)中的一條鏈路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)的基礎(chǔ)上,定義式(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 自適應(yīng)蟻群算法的QoS組播問題實現(xiàn)

3.1 適應(yīng)度函數(shù)

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

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

(10)

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

3.2 螞蟻的信息素調(diào)整

螞蟻尋找路徑時，按以下規(guī)則進行信息素調(diào)整：

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

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

(11)

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

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

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

D璱∈D

0,其他

(12)

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

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

(13)

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

3.3 算法步驟

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

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

Step 3：從源節(jié)點發(fā)出ANTn只螞蟻，按式(10)計算路徑集Ω璱中每條路徑的適應(yīng)度，每只螞蟻再按賭輪旋轉(zhuǎn)規(guī)則從中選擇一條路徑，再按式(11)進行分泌物強度調(diào)整。

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

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

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

4 實驗仿真和算法分析

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

表1 蟻群算法參數(shù)選取

αβQρn

0.20.31000.530

表2 30個網(wǎng)絡(luò)節(jié)點運行20次的延時與代價的關(guān)系

202428333640

AAC365359358355350346

IAAC355348347345342330

圖1 組播樹代價與迭代次數(shù)

圖2 組播樹代價與網(wǎng)絡(luò)節(jié)點數(shù)

5 結(jié) 語

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

參考文獻

［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］鄒德莉,郝應(yīng)光.基于非精確狀態(tài)信息的QoS組播路由算法［J］.微電子學(xué)與計算機,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路由技術(shù)研究.重慶:重慶大學(xué),2007.

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

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

［10］李生紅，劉澤民.基于蟻群算法的組播路由調(diào)度方法.計算機工程，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］田炳麗，劉常波，解貴新.旋轉(zhuǎn)貨架揀選作業(yè)優(yōu)化的交叉蟻群算法求解.現(xiàn)代電子技術(shù),2008,31(12):59-61.

作者簡介

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

軍 事 通 信

馮 正等：多線程串口通信技術(shù)在GPS導(dǎo)航中的應(yīng)用