蟻群算法在網(wǎng)絡(luò)路由中的應(yīng)用

彭歆筠

（長(zhǎng)江大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院,湖北 荊州 434023）

1 現(xiàn)狀

動(dòng)物界的智能行為一直都是科學(xué)家靈感的源泉，近年來，群居的昆蟲表現(xiàn)出來的集體智能吸引了研究者的注意?？茖W(xué)家發(fā)現(xiàn)，昆蟲在群落一級(jí)上的合作基本上是自組織的，在許多場(chǎng)合中盡管這些合作可能很簡(jiǎn)單，但是它們卻可以解決許多復(fù)雜的問題。蟻群算法就是利用群集智能解決組合優(yōu)化問題的典型例子。蟻群算法是由意大利學(xué)著Dorigo等人于20世紀(jì)90年代初期通過模擬自然界中螞蟻集體尋徑的行為而提出的一種基于種群的啟發(fā)式隨機(jī)搜索算法，蟻群算法具有并行性，魯棒性，正反饋性等特點(diǎn)，蟻群算法最早成功應(yīng)用于解決著名的旅行商問題（TSP）、車間任務(wù)調(diào)度問題（JSP）、網(wǎng)絡(luò)路由等許多復(fù)雜的組合優(yōu)化問題。

生態(tài)學(xué)家發(fā)現(xiàn)螞蟻在尋找食物時(shí)總是可以找到食物源到巢穴之間的最短路徑，這是因?yàn)槲浵佋谒褜な澄镌吹臅r(shí)候，能在其走過的路徑上釋放一種螞蟻特有的信息素，可以將信息傳遞給其它螞蟻并影響其對(duì)路徑的選擇。當(dāng)螞蟻碰到一個(gè)還沒有走過的路口時(shí)就隨機(jī)地挑選一條路徑前行，并釋放與路徑有關(guān)的信息素，通常螞蟻會(huì)以較大概率選擇信息素濃度高的路徑，并加強(qiáng)該路徑的信息素濃度，而其它路徑張的信息素濃度就會(huì)隨時(shí)間衰減，最終螞蟻能找到一條從食物源到巢穴的最短路徑。

2 蟻群算法與QoS路由

網(wǎng)絡(luò)路由方面的研究主要通過兩個(gè)途徑來提高服務(wù)質(zhì)量（quality of service,QoS）:一條途徑是節(jié)點(diǎn)控制；另一條途徑是整個(gè)網(wǎng)絡(luò)或局部網(wǎng)絡(luò)控制。節(jié)點(diǎn)控制在單節(jié)點(diǎn)或單鏈路完成，主要控制業(yè)務(wù)對(duì)單節(jié)點(diǎn)共享資源的占用；整個(gè)網(wǎng)絡(luò)或局部網(wǎng)絡(luò)控制通常通過對(duì)路由與信令的控制達(dá)到對(duì)業(yè)務(wù)流和業(yè)務(wù)連接在網(wǎng)絡(luò)中傳輸?shù)闹苯涌刂?。因?yàn)槁酚芍苯雨P(guān)系到網(wǎng)絡(luò)性能，所以QoS路由成為解決QoS問題的核心技術(shù)之一，也是當(dāng)今網(wǎng)絡(luò)技術(shù)領(lǐng)域內(nèi)的一個(gè)研究熱點(diǎn)。

QoS路由的任務(wù)就是在網(wǎng)絡(luò)中尋找一條路徑，使其能滿足帶寬、時(shí)延、時(shí)延抖動(dòng)和費(fèi)用的限制。上述問題可以利用蟻群算法來解決。

（1）問題描述，可將網(wǎng)絡(luò)模型表示為一個(gè)有向圖G=（V,E）,其中V是圖中所有交換節(jié)點(diǎn)組成的集合，E是圖中所有邊的集合，每一條邊表示相鄰兩節(jié)點(diǎn)間的直達(dá)通信路徑。一般的，假定相鄰兩節(jié)點(diǎn)間最多僅有一條邊。同時(shí)，假定B(l)表示鏈路l的可用帶寬，對(duì)于一個(gè)路由請(qǐng)求,路由算法如果能夠找到一條具有小費(fèi)用的路徑，同時(shí)滿足如下4個(gè)條件，則此路由請(qǐng)求W就可接受。

①在W的路由的每條路徑l上，帶寬可用限制為

②在w的路由上，端到端時(shí)延限制為

③在w的路由上，端到端丟失率限制為

這里只考慮由于節(jié)點(diǎn)緩存器溢出引起的丟失。

④在目的節(jié)點(diǎn)，端到端時(shí)延抖動(dòng)限制為

式中，Bw、Dw、Lw、Jw分別表示 QoS 要求的帶寬，時(shí)延、丟失率和時(shí)延抖動(dòng)限制；DN表示節(jié)點(diǎn)處理時(shí)延，DN:V→R+；DL表示鏈路時(shí)延，且DL:E→R+；V1表示ω路由的節(jié)點(diǎn)集合；E1表示ω的路由鏈路LR是節(jié)點(diǎn)丟失率，且DV表示在目的節(jié)點(diǎn)d的節(jié)點(diǎn)時(shí)延變化其中R+是正實(shí)數(shù)集合。

（2）算法設(shè)計(jì)。假設(shè)平面QoS蟻群路由算法中有m只螞蟻，并且采用了全局和局部信息素更新規(guī)則。①狀態(tài)轉(zhuǎn)移規(guī)則。位于節(jié)點(diǎn)r的第i只螞蟻依據(jù)下述規(guī)則來選擇節(jié)點(diǎn)s;如果有，q≤q0，有

否則，有

采用此定義來實(shí)現(xiàn)螞蟻狀態(tài)的轉(zhuǎn)移可保證尋找優(yōu)化路徑時(shí)避免陷入局部最優(yōu)解。

② 信息素的局部更新規(guī)則，對(duì)于第i只螞蟻，如果節(jié)點(diǎn)r,s是該螞蟻所選路徑上的兩個(gè)相鄰節(jié)點(diǎn)，則信息素pheromone（i，r，s）用公式（7）來調(diào)節(jié)；否則，不調(diào)節(jié)。

若沒有局部更新，所有螞蟻將在前一次的最好路徑的有限相鄰區(qū)域內(nèi)搜尋。

③信息素的全局更新規(guī)則，對(duì)于第i只螞蟻，如果節(jié)點(diǎn)r,s是該螞蟻所選路徑上的兩個(gè)相鄰節(jié)點(diǎn)，則信息素pheromone（i，r，s）按公式（8）

否則，按公式（9）調(diào)節(jié)

為了定義公式（8）中的限制函數(shù)F,首先引入幾個(gè)符號(hào)定義：如果節(jié)點(diǎn)r是第i只螞蟻所選路由的節(jié)點(diǎn)，則Nri=1，否則Nri=0；如果從節(jié)點(diǎn)r到節(jié)點(diǎn)s的邊是第i只螞蟻所選路由的邊，則 Prsi=1 否則 Prsi=0；LBrs、LCrs、和 LDrs分別表示從節(jié)點(diǎn) r到節(jié)點(diǎn)s的邊的帶寬、費(fèi)用和時(shí)延；NDr和NLr分別表示節(jié)點(diǎn)r的處理時(shí)延和丟失率。由此，可將限制函數(shù)F定義為

如果 Z<0,H(Z)=0；否則，H(Z)=Z0

式中，V表示網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)目；A、B、C分別表示帶寬可用限制、端到端時(shí)延限制和端到端丟失率限制，且為正實(shí)數(shù)；F1表示費(fèi)用限制；F2表示QoS限制。

根據(jù)上述的定義，如果所選路由的總費(fèi)用小，同時(shí)QoS限制也滿足要求，那么最優(yōu)螞蟻所選路由的各鏈路上的信息素應(yīng)該增加更多。為了進(jìn)一步提高算法的收斂性能，這里做了以下兩點(diǎn)改進(jìn)：①在蟻群算法迭代中不考慮時(shí)延抖動(dòng)，而是在算法執(zhí)行前進(jìn)行處理；②通過刪除帶寬小于需求帶寬的鏈路，把網(wǎng)絡(luò)過濾成一個(gè)新的簡(jiǎn)單網(wǎng)絡(luò)，因此在F函數(shù)中設(shè)A=0。

QoS螞蟻路由算法的具體步驟如下：①如果NDV(d)>Jw，那么退出；否則，跳轉(zhuǎn)到第（2）步。②通過刪除帶寬小于需求帶寬的鏈路，把網(wǎng)絡(luò)濾成一個(gè)新的簡(jiǎn)單網(wǎng)絡(luò)。③初始化網(wǎng)絡(luò)拓?fù)渲懈鬟叺南鄳?yīng)信息素。④從蟻巢開始放出m只螞蟻去尋找食物源，在第一個(gè)時(shí)間單位，每只螞蟻從節(jié)點(diǎn)集合中隨機(jī)地選擇一個(gè)節(jié)點(diǎn)，然后各螞蟻通過重復(fù)應(yīng)用狀態(tài)轉(zhuǎn)移規(guī)則來選擇各自的路徑。在選路徑的過程中，如果螞蟻在到達(dá)目的節(jié)點(diǎn)前就死亡，另外一只和死亡的螞蟻的同類的螞蟻重新放出來代替死亡的螞蟻，重新開始選擇從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑。當(dāng)某只螞蟻成功地完成路由選擇后，該螞蟻所選路由各路徑上的信息素根據(jù)局部更新規(guī)則進(jìn)行更新。⑤對(duì)所有的螞蟻重復(fù)第（4）步，直到m只螞蟻都完成了第（4）步。⑥選擇建立了最小費(fèi)用并滿足QoS限制的路由的螞蟻，然后使用全局更新規(guī)則對(duì)該螞蟻所選的路由的各路徑上的信息素進(jìn)行更新。⑦重復(fù)第（4）（6）步，直到獲得滿意的結(jié)果。

3 結(jié)語

蟻群算法問世至今已有近二十年的時(shí)間，從最初的最短路徑問題，逐步發(fā)展為一個(gè)優(yōu)化工具。蟻群算法具有很強(qiáng)的發(fā)現(xiàn)最優(yōu)解的能力，該算法不僅利用了正反饋原理，而且是一種本質(zhì)并行的算法，不同個(gè)體之間不斷進(jìn)行信息交流和傳遞實(shí)現(xiàn)協(xié)作。

蟻群算法在網(wǎng)絡(luò)方面的應(yīng)用尤為重要，本文介紹了蟻群算法在平面網(wǎng)絡(luò)QoS路由中的應(yīng)用，分析了算法設(shè)計(jì)和執(zhí)行的過程。從帶寬、時(shí)延、時(shí)延抖動(dòng)和費(fèi)用等關(guān)鍵因素出發(fā)，結(jié)合蟻群算法的狀態(tài)轉(zhuǎn)移規(guī)則、信息素局部更新規(guī)則、信息素全局更新規(guī)則來分析QoS路由問題。根據(jù)蟻群算法的思想在網(wǎng)絡(luò)中尋找一條最優(yōu)路徑，實(shí)現(xiàn)網(wǎng)絡(luò)傳輸?shù)目焖?、?zhǔn)確，直接提高網(wǎng)絡(luò)性能。在進(jìn)行路由運(yùn)算時(shí)，就可以減少大量的運(yùn)算和運(yùn)算時(shí)間。同時(shí)，蟻群在工業(yè)控制和生命科學(xué)等若干領(lǐng)域也有典型應(yīng)用，從目前的應(yīng)用情況來看，蟻群算法在智能優(yōu)化應(yīng)用領(lǐng)域具有極強(qiáng)的適應(yīng)性和生命力。

[1]李世勇.蟻群優(yōu)化算法及其應(yīng)用研究進(jìn)展[J].計(jì)算機(jī)測(cè)量與控制，2003，(12).

[2]姜長(zhǎng)園.蟻群算法的理論及應(yīng)用[J].計(jì)算機(jī)時(shí)代，2004，(6).

[3]趙天男,王曉紅.蟻群算法及其應(yīng)用研究[J].軟件導(dǎo)刊，2010，(6).

[4]張學(xué)敏,張航.基于改進(jìn)蟻群算法的最短路徑問題研究[J].自動(dòng)化技術(shù)與應(yīng)用，2009，(6).

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

[6]李世勇.蟻群算法及其應(yīng)用[M].哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2004.