彭歆筠

（長江大學 計算機科學學院,湖北 荊州 434023）

1 現(xiàn)狀

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

生態(tài)學家發(fā)現(xiàn)螞蟻在尋找食物時總是可以找到食物源到巢穴之間的最短路徑，這是因為螞蟻在搜尋食物源的時候，能在其走過的路徑上釋放一種螞蟻特有的信息素，可以將信息傳遞給其它螞蟻并影響其對路徑的選擇。當螞蟻碰到一個還沒有走過的路口時就隨機地挑選一條路徑前行，并釋放與路徑有關(guān)的信息素，通常螞蟻會以較大概率選擇信息素濃度高的路徑，并加強該路徑的信息素濃度，而其它路徑張的信息素濃度就會隨時間衰減，最終螞蟻能找到一條從食物源到巢穴的最短路徑。

2 蟻群算法與QoS路由

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

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

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

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

②在w的路由上，端到端時延限制為

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

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

④在目的節(jié)點，端到端時延抖動限制為

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

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

否則，有

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

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

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

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

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

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

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

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

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

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

3 結(jié)語

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

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

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

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

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

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

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

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