ACS算法求解多約束QoS路由問題

譚明佳

(1.武漢大學(xué) 計算機學(xué)院，湖北 武漢 430079;2.湖北民族學(xué)院 信息工程學(xué)院，湖北 恩施 445000)

QoS(Quality of Service)路由已成為解決QoS問題的一項關(guān)鍵技術(shù)，也是當(dāng)今網(wǎng)絡(luò)技術(shù)領(lǐng)域內(nèi)的一個研究熱點[1].在進(jìn)行QoS路由計算時，主要考慮時延、帶寬、費用、數(shù)據(jù)丟失率、時延抖動等特征參數(shù)[2].Wang Z等[3]證明了如果QoS路由計算中包含兩個以上特征參數(shù)時，它就是一個NP-C問題.

ACO(Ant Colony Optimization)元啟發(fā)式算法是多種螞蟻算法的一個共同框架，稱為ACO算法[4]，是由Dorige等于1999年提出的，包括螞蟻系統(tǒng)(Ant System，AS)、蟻群系統(tǒng)(Ant Colony System，ACS)、最大-最小螞蟻系統(tǒng)(MAX-MIN ant system，MMAS)等.ACO算法是一種智能優(yōu)化算法，用于易于表達(dá)但難于求解的離散優(yōu)化問題，使用agent(人工螞蟻)群的協(xié)作來求解最優(yōu)解.

ACO算法中的agent實際上代表的是一個隨機構(gòu)造解的過程，在構(gòu)造解的過程中通過不斷地向部分解中添加符合定義的解，從而構(gòu)造出一個完整的解，因此，ACO算法可以應(yīng)用到任何能夠定義構(gòu)造性啟發(fā)式的組合優(yōu)化問題中，而問題的關(guān)鍵在于如何把某個問題描述成可以被agent用來構(gòu)造解的表達(dá)方式.

相關(guān)的研究表明，如果求解的問題能夠抽象為在一個無向圖中尋找最優(yōu)路徑，ACO算法就能夠求出滿足給定約束條件的最優(yōu)路徑，從而完成對該問題的求解，因此ACO算法非常適合求解多約束條件QoS路由選擇問題.

目前已有的研究成果基本上是先通過修剪不滿足QoS需求的邊、瓶頸約束條件等，對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行預(yù)處理，簡化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)來進(jìn)行求解，而且仿真實驗的網(wǎng)絡(luò)規(guī)模較小，沒有充分考慮算法執(zhí)行的效率和路由器的處理能力.實際上對于多約束QoS路由計算問題，只需要找出滿足約束條件的路徑即可[7]，這樣還可以進(jìn)行負(fù)載均衡，避免所有的數(shù)據(jù)包都走同一條路徑，造成網(wǎng)絡(luò)擁塞.

1 ACS算法

ACO算法的執(zhí)行過程可以被看作是agent在圖G=(V,E,T)上的隨機移動，其中V為圖G頂點的集合，E為圖G邊的集合，T為信息素向量，τ(r,s)表示頂點r到頂點s的邊(r,s)上的信息素.

ACS算法是Gambardella等[4]在1997年提出的，其思想來源于AS算法，但使用了在AS中未出現(xiàn)的新機制，以進(jìn)一步獲得更高的性能.

ACS算法描述如下[4,5]：

輸入：一個組合優(yōu)化問題(S,f,Ω)，S為候選解的集合，f為目標(biāo)函數(shù)，Ω為約束條件的集合.

輸出：至今最優(yōu)解sbest

(1)初始化信息素向量T，即τ(r,s)=τ0>0，?(r,s)∈E；將m只agent隨機地放到n個頂點上.

(2)sbest←null.將至今最優(yōu)解變量sbest置空，用于在構(gòu)造解的過程中保存構(gòu)造的至今最優(yōu)解.

while(算法終止條件未滿足)do

fori=1 tomdo

(3)每只agent構(gòu)造解s.

位于頂點r的agentk根據(jù)偽隨機比例規(guī)則選擇頂點s作為下一個訪問的頂點，直到構(gòu)造完成一個可行解為止.其狀態(tài)概率轉(zhuǎn)移公式為：

(1)

(2)

(4)if (f(s)≤f(sbest)) or (sbest==null)thensbest←s.

end for

(5)根據(jù)sbest更新信息素向量T.

對信息素向量進(jìn)行局部更新：在構(gòu)造解的過程中，agent每經(jīng)過一條邊(r,s)，都將立即按式(3)更新該邊上的信息素：

τ(r,s)←(1-ξ)×τ(r,s)+ξ×τ0

(3)

對信息素向量進(jìn)行全局更新：只有一只agent(至今最優(yōu)agent)被允許在每一次迭代之后釋放信息素.信息素向量的全局更新規(guī)則為：

τ(r,s)←(1-ρ)×τ(r,s)+ρ×Δτbest(r,s)，?(r,s)∈sbest

(4)

在ACS算法中，無論是信息素?fù)]發(fā)還是信息素釋放，都只在構(gòu)成至今最優(yōu)解sbest的邊上執(zhí)行.

end while

2 多約束QoS路由計算

設(shè)無向賦權(quán)圖G=(V,E)表示一個計算機網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，其中V是圖G的頂點(如路由器，交換機等交換設(shè)備)組成的非空集合，E是圖G的邊組成的非空集合，每一條邊表示相鄰兩頂點間的通信鏈路.根據(jù)實際應(yīng)用，頂點和邊上都會有一個或多個特征值.

定義1 稱頂點序列P(V1,V2,…,Vm)為頂點V1到Vm的一條長度為m的路徑[6]，其中?Vi∈V,1≤i≤m，且?(Vi-1,Vi)∈E,2≤i≤m.

多約束QoS路由計算即是求出一條從信源s∈V到信宿d∈V的路徑P(s,…,d)，使得該路徑滿足具體業(yè)務(wù)的服務(wù)質(zhì)量要求.

2.1 多約束QoS路由的數(shù)學(xué)模型

不失一般性，假定相鄰兩頂點間最多僅有一條邊.對于從信源S∈V到信宿D(zhuǎn)∈V的路徑P(s,…,d)，路徑P的特征值可表示為：

路徑帶寬B(P)=min(BL(l),l∈E1)，其中BL∶E→R+∪{0}為邊的可用帶寬；

設(shè)Bω,Dω,Cω,Lω,Jω分別表示一個路由請求ω的QoS要求的帶寬、時延、費用、丟包率和時延抖動約束，則具體約束條件為：

B(P)≥Bω，D(P)≤Dω，C(P)≤Cω，L(P)≤Lω，J(p)≤Jω.

由于不同路由請求對網(wǎng)絡(luò)服務(wù)質(zhì)量的要求不同，因此各特征值的重要程度也不一樣[6]，針對具體路由請求給各特征值賦予不同的權(quán)值，設(shè)權(quán)重向量為：

W=(wb,wd,wc,wl,wj)，且wb+wd+wc+wl+wj=1

對于多約束QoS路由問題，由于各特征值的量化標(biāo)準(zhǔn)不一致，在數(shù)值上會出現(xiàn)較大的差異，為此建立式(5)所示的函數(shù)，對各特征值進(jìn)行歸一化處理.

(5)

其中：A為常數(shù)，對不同特征參數(shù)分別取(B(P),Dω,Cω,Lω,Jω).

令F(P)=(F1,F2,F3,F4,F5)T

其中：F1=f(B(P)-Bω)，F(xiàn)2=f(Dω-D(P))，F(xiàn)3=f(Cω-C(P))，F(xiàn)4=f(Lω-L(P))，F(xiàn)5=f(Jω-J(P))

則：多約束QoS路由的數(shù)學(xué)模型為：maxF=W?F(P)

說明，如果F1、F2、F3、F4、F5中有一個為負(fù)數(shù)，此時F為負(fù)，則這條路徑是不能接受的.

2.2 仿真實驗

利用上述分析結(jié)果，采用ACS算法，用C語言編寫程序進(jìn)行仿真實驗.實驗用的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖1所示[8]，有20個頂點，37條邊，網(wǎng)絡(luò)結(jié)構(gòu)模型中各邊的屬性參數(shù)用三元組(時延，帶寬，費用)來描述.為了簡化編寫程序和實驗初值的設(shè)置，本文沒有考慮網(wǎng)絡(luò)頂點的特征參數(shù)約束.

Agent的數(shù)據(jù)結(jié)構(gòu)定義為：

structure single_ant

begin

integer tour_F //保存agent路徑的F值

integer tour[n] //保存agent(部分)路徑

integer visited[n] //標(biāo)識agent已經(jīng)訪問過的頂點

end

single_ant ant[m] //定義m只agent

integer best //至今最優(yōu)路徑的agent標(biāo)識符

使用所求的F值對信息素向量的全局更新，只有至今最優(yōu)agent被更新：

inputbest //讀入最優(yōu)agent的標(biāo)識符

F←0.1/ant[best].tour_F //讀取最優(yōu)agent的F值

for i=1 to n do

j←ant[best].tour[i]

h←ant[best].tour[i+1]

τ[j][h]←(1-ρ)×τ[j][h]+ρ×F

τ[h][j]←τ[j][h] //信息素矩陣是對稱的

end-for

假設(shè)對于QoS路由請求(1，20)、(1，18)、(1，19)、(4，15)、(5，15)、(5，16)、(9，10)，其約束條件設(shè)置為Bω=60，Dω=100，Cω=100.ACS算法中參數(shù)設(shè)置為：m=10，ξ=0.1，ρ=0.1，τ0=0.32，q0=0.9，最大迭代次數(shù)NcMax=20，帶寬權(quán)重w1=0.2，時延權(quán)重w2=0.65，費用權(quán)重w3=0.15.對于QoS路由請求(1，20)，求解過程的進(jìn)化曲線如圖2所示.

圖1 網(wǎng)絡(luò)拓?fù)浼捌鋮?shù)

圖2 求解過程的進(jìn)化曲線

仿真計算的結(jié)果如表1所示.

表1 多約束QoS路由優(yōu)化仿真計算的結(jié)果

3 結(jié)語

ACS算法求解多約束QoS路由選擇的問題，目的是在最短的時間找到滿足特征約束條件的可行解，同時減少路由器的計算量，實驗證明這種思想是可行的和有效的.利用ACO算法求解實際問題的關(guān)鍵在于ACO算法與實際問題的切入點以及算法的改進(jìn)策略方面.

[1]段海濱.蟻群算法原理及其應(yīng)用[M].北京:科學(xué)出版社，2005：1-447.

[2]楊華江,陳巖,沈林成.基于改進(jìn)蟻群算法的多約束QoS路由方法[J].計算機應(yīng)用與軟件,2008,25(5):15-17.

[3]Wang Z,Crowcroft J.Quality of service routing for supporting multimedia applications[J].IEEE Journal on Selected Areas in Communications,1996,14(7):1 228-1 234.

[4]Macro Dorigo,Thomas Stützle.蟻群優(yōu)化[M].張軍,譯.北京:清華大學(xué)出版社,2007：1-298.

[5]黃翰,郝志峰,吳春國,等.蟻群算法的收斂速度分析[J].計算機學(xué)報,2007,30(8):1 344-1 353.

[6]陳巖,楊華江,沈林成.基于再勵學(xué)習(xí)蟻群算法的多約束QoS路由方法[J].計算機科學(xué),2007,34(5):25-27.

[7]王宇,許都,王宏,等.一個效率可觀的啟發(fā)式多約束QoS路由算法[J].計算機應(yīng)用研究,2008,25(2):345-347.

[8]劉萍,高飛,楊云.基于遺傳算法和蟻群算法融合的QoS路由算法[J].計算機應(yīng)用研究,2007,25(9):224-226.