基于改進蟻群算法的QoS路由研究

尹鳳杰，褚群森

(遼寧大學 信息學院，遼寧 沈陽 110036)

0 引言

近年來，網(wǎng)絡(luò)技術(shù)快速發(fā)展，多媒體數(shù)據(jù)的傳輸已經(jīng)占據(jù)更重要的地位，這些業(yè)務(wù)對網(wǎng)絡(luò)的服務(wù)質(zhì)量[1](Quality of Service，QoS)要求不斷增強.多約束QoS問題在文獻[2]中已經(jīng)被證實是一個NP-Complete難題.目前，研究發(fā)現(xiàn)各類智能算法的優(yōu)勢突出，國內(nèi)外學者針對網(wǎng)絡(luò)路由并結(jié)合智能算法的特性進行了深入的研究，提出了多種算法.文獻[3]提出一種基于蛙跳算法的自適應(yīng)多徑路由算法以解決無線傳感器網(wǎng)絡(luò)中的擁堵難題.文獻[4]提出基于遺傳算法(Grenetic Algorithm，GA)的路由算法，該算法針對多約束離散網(wǎng)絡(luò)節(jié)點的路由尋址問題，得到較為實用的解，但是正反饋能力不足是明顯缺點.文獻[5]提出了一種基于分數(shù)布谷鳥搜索的移動自組網(wǎng)QoS感知路由的多路徑選擇方案，通過考慮諸如能量、鏈路壽命、距離和延遲之類的QoS約束，開發(fā)了一種新的適應(yīng)度函數(shù)，但可行性不高.文獻[6-10]基于蟻群算法對多約束QoS路由算法進行不同的優(yōu)化，優(yōu)化后的算法性能從不同角度得到提升，然而，這些算法在一定程度上存在局限性，如搜索前期信息素含量較為匱乏，容易出現(xiàn)盲目搜索、局部最優(yōu)等現(xiàn)象.

針對上述問題，本文設(shè)計一種基于傳統(tǒng)蟻群算法的改進算法，使改進后的算法在保持較強的正反饋性和較高的收斂性的前提下，同時具備隨機搜索的特征，擴大搜索范圍，以保證最終解空間的豐富性.

1 多約束QoS路由數(shù)學模型

多約束QoS路由是指從源節(jié)點開始，建立一條到達目的節(jié)點的路由路徑，與此同時該路徑滿足全部路由約束條件.因此可采用參考文獻[11]中的網(wǎng)絡(luò)模型.

采用與文獻[11]相同的無向圖G=(V，E)表示多約束QoS路由的網(wǎng)絡(luò)模型，其中V表示網(wǎng)絡(luò)中的全部路由節(jié)點，E表示網(wǎng)絡(luò)中全部可通信的鏈路，r為節(jié)點的可交互范圍，d表示節(jié)點間的距離，若d≤r，則兩個節(jié)點之間存在一條可通信的鏈路e，且e∈E.給定的無向圖G=(V，E)，源節(jié)點到目的節(jié)點的路徑集合為P，對于一條路徑p∈P的邊集為E(p)，節(jié)點集為N(p)，則QoS的參數(shù)定義如下：

(1)

2)帶寬：BandWidth(p)=min{BandWidth(e)，e∈E(p)}

(2)

(3)

(4)

式(1)～(4)分別將網(wǎng)絡(luò)中最重要的4個制約因素用數(shù)學公式的形式表達出來，QoS路由算法的目地即為尋找一條滿足如下條件的路由路徑p′.

時延約束：Delay(p′)≤Dmax；

帶寬約束：BandWidth(p′)≥Bmin；

丟包率約束：Lost(p′)≤Lmax；

開銷約束：Cost(p′)最小(式(1)～(3)全滿足).

2 蟻群算法改進策略

蟻群算法運行初期由于路徑上的初始信息素分布較少，不具有明顯的引導作用，此時算法的搜索速度較低；隨著算法搜索的不斷深入，路徑上的信息素濃度不斷加強，此時蟻群算法的正反饋特性突顯作用，則容易導致蟻群算法在后續(xù)的迭代進程中對某一條路徑的搜索持續(xù)進行，從而忽視對周圍路徑的搜索，導致無法輸出最優(yōu)的路徑.

綜合考慮上述問題，本文在蟻群算法[12](Ant Colony System，ACS)的基礎(chǔ)上，設(shè)計動態(tài)自適應(yīng)的轉(zhuǎn)移概率因子，同時，對全局信息素更新規(guī)則進行了優(yōu)化，以此來克服ACS算法的一些不足.

2.1 轉(zhuǎn)移概率因子的設(shè)計

在ACS算法中，狀態(tài)轉(zhuǎn)移因子取值不同，螞蟻按照不同的方式篩選下一跳節(jié)點，豐富了下一跳節(jié)點的可選擇性，在一定程度上可以有效地防止算法陷入局部最優(yōu)解.在公式(5)中狀態(tài)轉(zhuǎn)移因子q0是區(qū)間[0，1]內(nèi)的一個常數(shù)，缺乏自適應(yīng)性.

(5)

(6)

根據(jù)分析，當q0的值越大，下一跳節(jié)點越傾向于選擇集合[τij]α[ηij]β中的值最大的節(jié)點，因此算法的收斂速度越高，算法的隨機搜索能力越低；當q0的值越小，下一跳節(jié)點的選擇越傾向于按照概率進行路徑搜索，此時，算法的隨機搜索能力增強，同時算法的整體收斂速度下降[13].

因此，本文設(shè)計轉(zhuǎn)移概率因子函數(shù)q0(t)，在算法執(zhí)行的初始階段，令q0的取值保持在較大的范圍內(nèi)，此時下一跳節(jié)點按照先驗規(guī)律進行選擇，算法具有高收斂性和低隨機性；算法進一步執(zhí)行，若繼續(xù)保持算法初期的高收斂性，則容易導致算法陷入局部最優(yōu)解而無法擺脫，此時需選擇較小q0，算法具有較高的隨機搜索性和較低的收斂性；算法繼續(xù)執(zhí)行，輸出結(jié)果趨于穩(wěn)定，算法的高隨機性已經(jīng)不能繼續(xù)豐富最優(yōu)路徑的集合，重新恢復較大的q0，進一步提高收斂速度并最終找到全局最優(yōu)解.

綜上所述，自適應(yīng)函數(shù)q0(t)滿足在算法執(zhí)行的各個階段對收斂速度和隨機搜索能力的要求.q0按下式進行選擇：

(7)

式中：t為迭代次數(shù)；qmin為q0(t)的最小值；σ為正參數(shù)，控制q0(t)上升和下降的速度.

2.2 全局信息素更新規(guī)則的改進

在ACS算法中，每次迭代完成后只有當前全局最優(yōu)螞蟻經(jīng)過的路徑上的信息素濃度得到加強，全局信息素更新規(guī)則如下：

τij=(1-ρ)τij+ρΔτij

(8)

(9)

式中：Δτij為路徑(i，j)上的信息素的增長強度；ρ為信息素揮發(fā)因子；Q為每代螞蟻攜帶的可釋放信息素總量；PBest為當前全局最優(yōu)路徑的長度.ACS算法信息素更新規(guī)則僅增強了當前全局最優(yōu)路徑上的信息素濃度；同時，由于信息素的揮發(fā)行為，其他的路徑上信息素濃度下降.綜合考慮，這種更新規(guī)則突顯了當前最優(yōu)路徑上的信息素對后續(xù)螞蟻的吸引效果，對進一步迭代的搜索過程具有指導作用.

ACS算法的信息素更新規(guī)則選擇比當代最優(yōu)路徑更好的全局最優(yōu)路徑進行釋放信息素，這一過程完全忽視了當代最優(yōu)路徑對構(gòu)建最終解空間的作用.文獻[14]通過實驗進行驗證，僅更新全局最優(yōu)路徑上的信息素濃度與更新當代最優(yōu)路徑上信息素濃度進行對比，實驗結(jié)果表明前者的引導作用要優(yōu)于后者.無論是對全局最優(yōu)路徑還是對當代最優(yōu)路徑上信息素的增強，對最終解空間的構(gòu)造都具有重要的指導性，使得下一次迭代過程對此次信息素所更新的路徑以及該路徑的鄰近路徑進行進一步搜索.因此，增加了得到最終全局最優(yōu)路徑的概率，與此同時，收斂速度也得到提高.正如文獻[14]所說，此時全局最優(yōu)的性能并沒有比當代最優(yōu)的性能更加優(yōu)越，僅稍強于后者，若將二者同時利用起來有可能使改進后的算法具有更加優(yōu)越的性能.

本文在ACS算法全局信息素更新規(guī)則的基礎(chǔ)上，設(shè)計一種新的更新規(guī)則.結(jié)合最大最小蟻群算法[15]對各路徑上的信息素含量進行限制，即網(wǎng)絡(luò)中任意一條的路徑的信息素含量限制在[τmin，τmax]范圍內(nèi)，當超出這個范圍時，信息素含量強制限定為τmin或τmax，下確界可以防止某條路徑信息素含量過低進入停滯搜索狀態(tài)，而上確界可以避免某條路徑信息素含量過高，算法陷入局部最優(yōu)解.

為了加快算法的收斂效率，綜合考量全局最優(yōu)路徑和當代最優(yōu)路徑的影響，本文采用對全局最優(yōu)路徑以及當代最優(yōu)路徑同時進行信息素的更新.當代最優(yōu)路徑(k，l)與全局最優(yōu)路徑(i，j)為同一路徑時，此時該路徑上的信息素增量大于僅對全局最優(yōu)路徑進行更新的信息素增量，提高了算法的收斂速度.當代最優(yōu)路徑(k，l)與全局最優(yōu)路徑(i，j)為兩條路徑時，同時對兩條路徑上的信息素進行增強，擴大了最優(yōu)解的搜索范圍，增加了對次最優(yōu)解的搜索深度，降低算法陷入局部最優(yōu)解的概率.

此時信息素增量Δτij(t)的計算公式如下：

(10)

式中：PBest′表示此次迭代過程產(chǎn)生的最優(yōu)路徑；PBest表示迭代至今產(chǎn)生的整體最優(yōu)路徑.

3 改進蟻群算法在多約束QoS路由中的應(yīng)用

(11)

(12)

(13)

此時，開銷函數(shù)Cost(p)可以用公式(14)來表示：

(14)

式中：ω1、ω2、ω3分別為時延、帶寬和丟包率所占權(quán)重，同時，ω1+ω2+ω3=1且ω1、ω2、ω3≥0.在基于蟻群算法的QoS路由算法中，路徑啟發(fā)式信息ηij相應(yīng)的表達式如下：

(15)

基于改進蟻群算法QoS路由路徑搜索步驟：

1)初始化網(wǎng)絡(luò)參數(shù).

2)源節(jié)點s收到發(fā)送數(shù)據(jù)請求，按照改進后的蟻群算法發(fā)出M個“螞蟻幀”，每個“螞蟻幀”生成各自的路由表，將源節(jié)點s和目的節(jié)點d加入到路由表，并隨機生成一個q.

3)“螞蟻幀”根據(jù)概率轉(zhuǎn)移因子q0與q的關(guān)系，來選擇下一跳節(jié)點的尋找方式，當“螞蟻幀”到達下一跳節(jié)點時，則將當前節(jié)點記錄到“螞蟻幀”中.

4)對當前螞蟻幀所處節(jié)點進行判斷，若此時螞蟻幀位于目標節(jié)點d，則更新路由表中的相關(guān)記錄，并計算相應(yīng)開銷函數(shù)；否則按照步驟3)繼續(xù)進行路徑搜索，直到找到目標節(jié)點或者完成TTL時間，此時當代螞蟻幀完成搜索.

5)比較M個螞蟻幀所記錄的開銷函數(shù)的大小，找到當代最優(yōu)路徑；比較當代最優(yōu)路徑的開銷函數(shù)與上一次迭代后的全局最優(yōu)路徑的開銷函數(shù)，找到本次迭代完成后的兩類最優(yōu)路徑，按照改進后的信息素更新規(guī)則，對這兩條路徑上的信息素濃度進行加強，并更新路由表中相應(yīng)的數(shù)據(jù).

6)下次迭代開始前自適應(yīng)改變算法中相關(guān)參數(shù)的值，接著將迭代次數(shù)增加1.

7)重復執(zhí)行算法的第3)～6)步直至“螞蟻幀”生命周期結(jié)束或算法運行周期結(jié)束，并向源節(jié)點返回路由路徑信息.

4 仿真實驗及分析

本文利用Matlab進行仿真實驗，模擬在1 000 km×1 000 km范圍內(nèi)隨機生成35個網(wǎng)絡(luò)節(jié)點，節(jié)點之間隨機連通，構(gòu)建可通信的鏈路，同時生成相應(yīng)的網(wǎng)絡(luò)參數(shù)，如鏈路時延、節(jié)點時延、帶寬、丟包率、開銷等.網(wǎng)絡(luò)拓撲圖如圖 1 所示.

仿真實驗網(wǎng)絡(luò)相關(guān)的參數(shù)選擇如表 1 所示.

表1 網(wǎng)絡(luò)相關(guān)參數(shù)

在仿真實驗中，有關(guān)參數(shù)的設(shè)置如下：

QoS約束條件參數(shù)：Bmin=60，Dmax=100 ms，Lmax=1e-2.

算法中各參數(shù)的設(shè)置：α=2，β=2，Q=10，M=20，k=10，ρ=0.1，源節(jié)點s=1，目的節(jié)點d=35，最大迭代次數(shù)N=100.

仿真實驗表明最優(yōu)路徑為(1，3，9，17，23，28，35)，實驗歸一化開銷為3.21.

仿真圖像2表明，在初期搜索階段，兩種算法均未找到較好的路徑，此時延遲比較大，根據(jù)歸一化延遲計算公式，此時歸一化延遲趨于0；當路徑搜索平穩(wěn)時，改進蟻群算法的歸一化延遲高于基本蟻群算法，說明改進蟻群算法得到的路徑延遲優(yōu)于基本蟻群算法路徑的延遲.圖像3表明隨著迭代進程的不斷進行，改進蟻群算法費用曲線的下降速度明顯高于基本蟻群算法，改進蟻群算法最終搜索到的路徑的費用明顯低于基本蟻群算法，表明基本蟻群算法在搜索過程中搜索深度不足，陷入局部最優(yōu)解，而改進后的算法通過限制信息素的持續(xù)增長，避免了這種情況，得到更加優(yōu)秀的路徑.改進蟻群算法在迭代次數(shù)22左右趨于穩(wěn)定，而基本蟻群算法則在迭代次數(shù)39左右趨于穩(wěn)定，實驗結(jié)果表明在收斂特性上，改進蟻群算法比基本蟻群算法更優(yōu)秀.

這是由于改進蟻群算法在迭代搜索初期階段通過設(shè)置了較大的概率轉(zhuǎn)移因子q0，降低算法的隨機性，有利于初期路徑上信息素的積累；在算法中期，選擇較小的q0，此時改進算法與基本蟻群算法保持一致的全局搜索性，同時通過最大最小蟻群策略限制了信息素在某一路徑的大量積累；同時依照優(yōu)化后的信息素更新規(guī)則對信息素進行更新，對當代最優(yōu)路徑和全局最優(yōu)路徑進行信息素更新，進一步強化算法的收斂性，使算法不斷朝著全局最優(yōu)目標進一步尋找.

5 結(jié)束語

蟻群算法由于算法自身具有較強的正反饋作用，針對多約束條件下的網(wǎng)絡(luò)路由路徑尋優(yōu)問題經(jīng)實驗驗證有較好的效果.本文設(shè)計了隨時間變化的轉(zhuǎn)移概率因子函數(shù)q0(t)，較好地控制了下一跳節(jié)點在不同時期的搜索范圍；同時，設(shè)計了一種新的信息素更新的規(guī)則，在一定程度上加強了算法的整體收斂速度.這種改進算法與多約束QoS路由模型結(jié)合起來，構(gòu)造了基于改進蟻群算法的路由算法.實驗仿真結(jié)果表明，改進的路由算法的路徑搜索速度得到提高，路由路徑傳輸數(shù)據(jù)的開銷較低，得到了比較理想的實驗結(jié)果.