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

梁　瀟

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

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

中圖分類號(hào)：TN919文獻(xiàn)標(biāo)識(shí)碼：B

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

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

1 基本蟻群算法

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

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

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

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

(1)

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

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

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

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

(2)

式中:Δτ琯b璱j(t)=1/L璯b;L璯b為當(dāng)前全局最優(yōu)解的路徑長(zhǎng)度。采用全局信息更新策略，增強(qiáng)了全局最優(yōu)解路徑上的信息素，加強(qiáng)了算法的正反饋?zhàn)饔茫瑥亩涌焖惴ǖ氖諗克俣取?/p>

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

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

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

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

延時(shí)約束：

delay(p璗(s,t))

(6)

帶寬約束：

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

(7)

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

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

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

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

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

(8)

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

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)可知,剩余帶寬越大,鏈路代價(jià)越小;反之,鏈路代價(jià)越大。

3 自適應(yīng)蟻群算法的QoS組播問題實(shí)現(xiàn)

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

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

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

(10)

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

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

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

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

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

(11)

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

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

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

D璱∈D

0,其他

(12)

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

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

(13)

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

3.3 算法步驟

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

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

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

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

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

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

4 實(shí)驗(yàn)仿真和算法分析

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

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

αβQρn

0.20.31000.530

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

202428333640

AAC365359358355350346

IAAC355348347345342330

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

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

5 結(jié) 語

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

參考文獻(xiàn)

［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é)與計(jì)算機(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］李昌兵.基于計(jì)算智能的多播QoS路由技術(shù)研究.重慶:重慶大學(xué),2007.

［8］王應(yīng)征，石冰心.基于遺傳算法的時(shí)延受限代價(jià)最小組播路由選擇方法.通信學(xué)報(bào)，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)度方法.計(jì)算機(jī)工程，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.

作者簡(jiǎn)介

梁 瀟 女，1983年出生，湖北監(jiān)利人，碩士研究生。主要研究方向?yàn)橹悄苡?jì)算。

軍 事 通 信

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