基于改進蟻群算法的Ａｄ ｈｏｃ路由算法

摘要：在基于蟻群優(yōu)化算法（ACO）的Ad hoc路由算法的基礎上提出了一種改進的基于螞蟻算法的Ad hoc路由算法。該算法吸收了AODV的優(yōu)點，并且在實現(xiàn)方面得到了改善。分析表明，該算法能大大提高系統(tǒng)的可靠性、魯棒性，增強了通信網(wǎng)絡的自適應能力。

關鍵詞：無線移動自組織網(wǎng)絡；蟻群優(yōu)化；螞蟻代理；按需路由

中圖分類號：TP393； TP301．6文獻標志碼：A

文章編號：1001－3695(2008)01－0059－03

0引言

與傳統(tǒng)有線網(wǎng)絡和蜂窩網(wǎng)絡相比，無線移動自組織網(wǎng)無固定基礎設施；每個節(jié)點都可以隨時進入或離開網(wǎng)絡，并且它們之間的地位是平等的；所有節(jié)點都可作為路由轉發(fā)節(jié)點。因此，開發(fā)一種較好的動態(tài)路由協(xié)議就成為Ad hoc網(wǎng)絡設計的關鍵。一般來說應具備以下功能[1]：

a)能感知網(wǎng)絡拓撲結構的變化。Ad hoc路由協(xié)議要能感知網(wǎng)絡拓撲的動態(tài)變化，因為每個節(jié)點都可以隨時進入或離開網(wǎng)絡，良好的路由協(xié)議要能夠監(jiān)測到網(wǎng)絡拓撲結構的變化。

b)維護網(wǎng)絡拓撲的連接。每個節(jié)點都可以隨時改變位置或離開進入網(wǎng)絡，因此網(wǎng)絡拓撲結構是頻繁變化的。Ad hoc網(wǎng)絡路由協(xié)議為了使節(jié)點之間的鏈路具有較強的連接性，必須動態(tài)更新鏈路狀態(tài)及對自己進行重新配置。

c)高度自適應的路由。這是設計Ad hoc網(wǎng)絡路由的關鍵。鑒于Ad hoc網(wǎng)絡拓撲結構的快速變化，需要設計一種高度自適應路由機制來處理這種變化。據(jù)此，Ad hoc網(wǎng)絡路由協(xié)議大致可以分為先驗式(proactive)路由協(xié)議、反應式(reactive)路由協(xié)議以及兩者相結合的路由協(xié)議。

蟻群優(yōu)化方法是意大利學者M.Dorigo等人[2]最早提出的，又稱螞蟻算法。它是一種性能優(yōu)良的啟發(fā)式隨機優(yōu)化算法，具有自組織及自動學習的能力，在它提出初期主要是為解決旅行商問題(TSP)。后來，G. D. Caro等人[3]將蟻群算法應用到網(wǎng)絡路由中去，并稱這種算法為AntNet。

1AODV路由協(xié)議和ACO路由算法

1．1AODV路由協(xié)議

AODV[4]路由協(xié)議是一種按需路由協(xié)議。它是根據(jù)業(yè)務需求建立起來的。在AODV路由協(xié)議中，當一個節(jié)點（源節(jié)點）需要向目的節(jié)點發(fā)送數(shù)據(jù)時，如果它的路由表項中不存在到達目的節(jié)點的路由時，它將會發(fā)起路由建立過程。源節(jié)點向它所有鄰居節(jié)點廣播路由請求信息RREQs(route requests)；收到RREQs的鄰居節(jié)點建立反向路由，目的節(jié)點為原來的源節(jié)點。如果此相鄰節(jié)點存在通向目的節(jié)點的路由時，則沿反向路由發(fā)送應答信息RREPs（route reply），并據(jù)此建立正向路由；否則，此鄰居節(jié)點將向它所有鄰居節(jié)點廣播RREQs，直到某個中間節(jié)點存在通往目的節(jié)點的路由或直接到達目的節(jié)點為止。在此過程中建立反向路由以備發(fā)送應答信息。最后，此節(jié)點沿反向路由向源節(jié)點發(fā)送應答信息RREPs，收到RREPs的節(jié)點建立到目的節(jié)點的路由——稱為正向路由。在建立路由過程中，利用序列號來避免環(huán)路的產(chǎn)生。

為了維護路由，在AODV路由協(xié)議中，每個節(jié)點周期性地向鄰居節(jié)點廣播hello信息，表示此節(jié)點存在。如果一個節(jié)點在一定時間內(nèi)沒有接收到hello信息，則說明該鏈路中斷。當鏈路中斷時，每一個經(jīng)該鏈路向目的節(jié)點傳送數(shù)據(jù)的上游節(jié)點將會收到一個自動生成的錯誤信息，停止發(fā)送數(shù)據(jù)，直到一條新的路由建立為止。如果是由于源節(jié)點的移動導致鏈路中斷時，它會重新發(fā)起路由建立過程。 

按需路由協(xié)議AODV存在一些缺點：a）當一個節(jié)點發(fā)送數(shù)據(jù)包而沒有路由存在時，它只能等待，直到建立起一條合適的路由才能發(fā)送。因此AODV存在較長的路由時延。b）在建立路由時，鄰居節(jié)點依次向周圍節(jié)點廣播此分組直到該分組被送到一個知道目的節(jié)點路由信息的中間節(jié)點。但是通過這個中間節(jié)點找到的路由不一定是最好的路由。c）在鏈路失效時，AODV的處理方法可能導致數(shù)據(jù)包的丟失。

1．2ACO路由算法

基于ACO來選擇路由算法的思想[5]是用一種控制報文（又稱螞蟻）來搜集路徑信息進行路由選擇。本文用移動代理來模擬螞蟻，分為兩種，即前向螞蟻(forward ants)和后向螞蟻(backward ants)，并通過移動代理的復雜交互來決定路由。用前向螞蟻搜集從源節(jié)點到目的節(jié)點的路徑信息（包括端到端的延遲、所經(jīng)過的跳數(shù)等）；后向螞蟻據(jù)此來改變所經(jīng)過的各個節(jié)點的路由信息。

1．3基于ACO算法的自組網(wǎng)路由協(xié)議研究現(xiàn)狀

最早在有線網(wǎng)絡如AntNet[3]中引入的基于蟻群優(yōu)化的路由方案是一種主動路由協(xié)議，其通過螞蟻進行路由發(fā)現(xiàn)與維護的基本思想為后續(xù)基于蟻群優(yōu)化的路由協(xié)議所繼承。但由于在網(wǎng)絡中采用周期性發(fā)送螞蟻分組的方法進行路由發(fā)現(xiàn)和維護將引入很大的時延和路由開銷，難以快速適應網(wǎng)絡拓撲的頻繁變化，不能直接應用于動態(tài)拓撲的自組網(wǎng)中[6]。當前所提出的基于蟻群優(yōu)化的自組網(wǎng)路由協(xié)議大多需要通過其他機制來解決上述問題，如GPS/AL[7]、Ant AODV[8]和AntHocNet[9]都采用了類似于螞蟻的移動代理對網(wǎng)絡進行大范圍掃描，將移動代理所經(jīng)過的網(wǎng)絡節(jié)點中對路由有用的信息進行收集和發(fā)布；但AntHocNet是一種混合式算法。其他基于蟻群優(yōu)化方法的自組網(wǎng)優(yōu)化路由算法有 MABR、ANSI、ARAMA等。

單純的基于ACO的路由算法存在一些缺點：a）節(jié)點只是單獨依靠螞蟻代理來尋找最短路由。當網(wǎng)絡動態(tài)變化劇烈和路由生命周期較小時，性能不會很好。b）如果一個節(jié)點在傳輸數(shù)據(jù)時發(fā)現(xiàn)路徑不是最新的路徑，它將把要發(fā)送的數(shù)據(jù)包保存在緩沖區(qū)中，直到有一條新的路由建立起來。其存在較長的時延。c）在ACO路由算法執(zhí)行過程中，不像AODV那樣存在對本地節(jié)點連接的維護，因此當一條路由斷開時，源節(jié)點不知道鏈路已經(jīng)斷開將一直發(fā)送數(shù)據(jù)。這將導致大量數(shù)據(jù)的丟失。

2基于ACO建立路由算法

在此提出了一種利用ACO建立Ad hoc network路由信息的方法，此算法在路由表更新上對AntHocNet進行了改善。用圖G ={V，E}表示實現(xiàn)中的網(wǎng)絡。其中：V是網(wǎng)絡中所有節(jié)點的集合；E是連接兩節(jié)點的邊集。每個節(jié)點維護一個路由信息表RT。每個螞蟻可根據(jù)路由信息表選擇一條合適的路由發(fā)送數(shù)據(jù)。假設螞蟻在節(jié)點i，信息表RTi如表1所示。其中：D是某個節(jié)點可以選擇的目的節(jié)點數(shù)；N為該節(jié)點相鄰的節(jié)點數(shù)。表1給出了以某個節(jié)點為目的節(jié)點時選擇下一個節(jié)點的概率。因此時延小、跳數(shù)少的鏈路應具有更大的概率值。假設Phin，d是在節(jié)點i通過相鄰節(jié)點n到達目的節(jié)點d的信息素的值（用時延和跳數(shù)來評價），那么螞蟻利用以下規(guī)則選擇下一跳節(jié)點n。其概率為

本文用端到端的時延和所經(jīng)過的跳數(shù)來表示信息素值Phin，d。在此算法中，采用兩類人工螞蟻代理來完成這些工作：a)前向螞蟻代理Fant，表示從源節(jié)點到目的節(jié)點的螞蟻代理，在其向目的節(jié)點前進的過程中收集信息（如時延和跳數(shù)等）；b)后向螞蟻代理Bant，表示從目的節(jié)點返回到源節(jié)點的螞蟻代理，在返回途中根據(jù)Fant搜集的信息進行信息素表的更新。

3基于改進ACO算法的ACO AODV路由算法

為了克服傳統(tǒng)的基于ACO的路由算法以及AODV路由協(xié)議存在的缺點，本文提出了ACO AODV路由算法。該算法融合了ACO和AODV的優(yōu)點，能提高節(jié)點的連接性，降低端到端的時延（end to end delay）和尋找路由的延遲，以及提高數(shù)據(jù)包的傳輸率。

3．1路由的組建

當一個源節(jié)點S需要向目的節(jié)點D傳送數(shù)據(jù)時，首先會在該節(jié)點查詢本地路由，看是否有到達目的節(jié)點D的路由信息。如果有，則會按照信息素概率高的路由進行數(shù)據(jù)分組轉發(fā)；否則，該節(jié)點就會將要發(fā)送的數(shù)據(jù)包保存在緩存中，并按照第2章提到的方法組建一條合適的路由。在建立路由的過程中，當中間節(jié)點接收到一個新的Fant時，該節(jié)點將會檢查本地路由表是否存在到達目的節(jié)點的路由。如果不存在，則該中間節(jié)點將會廣播此Fant直到到達目的節(jié)點為止；否則按以下規(guī)則進行：a)該Fant產(chǎn)生一個Bant，返向源節(jié)點，修改途經(jīng)中間節(jié)點的路由信息，建立一條正向路由分組傳送數(shù)據(jù)；b)由于該路徑可能不是最佳路徑，F(xiàn)ant繼續(xù)向目的節(jié)點移動，其過程同上。直到建立一條最優(yōu)路徑，然后按此路徑傳送數(shù)據(jù)。

3．2路由的維護與探索

經(jīng)過路由初始化后，網(wǎng)絡中存在一系列保存有“有信息素計算的路由信息表”的節(jié)點。這些節(jié)點會按照一定算法對路由表進行維護更新[9]。

3．3鏈路中斷與修復

為了檢測鏈路中斷情況，采用了AODV協(xié)議的管理機制。正在通信的節(jié)點在一段時間內(nèi)如果沒有成功發(fā)送任何數(shù)據(jù)，就主動向自己的鄰居節(jié)點廣播路由檢測信息的螞蟻代理Cant，此代理只有一個hello信息通知鄰居節(jié)點自己的存在；收到Cant的鄰居節(jié)點返回一個應答信息Rant到該節(jié)點。如果該節(jié)點長時間沒有收到鄰居節(jié)點的應答信息，從而認為鄰居節(jié)點已經(jīng)離開，導致本鏈路的中斷。

發(fā)生鏈路中斷時，此節(jié)點將向所有使用該鏈路的上游節(jié)點發(fā)送中斷信息并進行處理。對鏈路中斷處理有以下三種方式：a）將從鏈路中斷的路由切換到備用路由中發(fā)送數(shù)據(jù)。b）先將要發(fā)送的數(shù)據(jù)包保存在本節(jié)點的緩沖區(qū)中；然后對鏈路進行本地修復。如果成功則將保存的數(shù)據(jù)包發(fā)送出去；否則該節(jié)點可以發(fā)起一次路由建立過程，方法同路由組建。建立起合適的路由后，再把保存的數(shù)據(jù)包發(fā)送出去。這樣做的目的是避免了大量的數(shù)據(jù)包丟失，從而提高數(shù)據(jù)包的傳輸率。c）將錯誤信息發(fā)送到源節(jié)點，讓源節(jié)點重建路由。

4結束語

由于本文算法是在ACO路由算法與AODV路由協(xié)議的基礎上設計而成的，本文僅僅討論此算法與ACO路由算法和AODV路由協(xié)議之間的性能。從上面的介紹可知，此算法融入了兩種算法的優(yōu)點，不管在路由的組建、維護與探索方面都得到提高，而且大大避免了數(shù)據(jù)包的丟失，提高了數(shù)據(jù)的傳輸率。由于信息素增量的計算以及信息素表的更新是建立最優(yōu)路由以及維護路由的重要方面，怎樣采用較好的控制參數(shù)來進行信息素表的更新將是進一步研究的方向。

參考文獻：

［1］鄭相全.無線自組網(wǎng)技術實用教程[M].北京：清華大學出版社，2004:19－20.

[2]DORIGO M，MARIA G L.Ant colony system:a cooperative learning approach to the traveling salesman problem [J].IEEE Trans on Evolutionary，1997，1(1):53－66.

[3]CARO G D，DORIGO M.AntNet:a mobile agents approach to adaptive routing，IRIDIA/97 12[R]. Brussels:Universite Libre de Bruxel les，1997.

[4]PERKINS C E，ROYER E M，DAS S R.Ad hoc on demand distance vector(AODV) routing[C]//Proc of IEEE Workshop on Mobile Computing Systems and Applications.1999:90 100.

[5]CARO GD.Ant colony optimization and its application to adaptive routing in telecommunication networks[D]. Brussels:Universite Libre de Bruxelles，2004.

[6]鄭相全.基于負載均衡的無線自組網(wǎng)關鍵技術與算法研究[D].成都：電子科技大學通信與信息工程學院，2004.[7]CAMARA D，ALFREDO A，LOUREIRO F.A GPS/ant like routing algorithm for Adhoc networks[C]//Proc of IEEEWirelessCommunicationsandNetworking Conference (WCNC’00).Chicago:[s.n.]，2000:1232 1236.

[8]MARWAHA S，THAM C K，SRINIVASAN D.A novel routing protocol using mobile agents and reactive route discovery for Ad hoc wireless networks[C]//Proc of IEEE International Conference on Networks.2002:311－316.

[9]CARO G D，DUCATELLE F，GAMBARDELLA L M.AntHocNet: an ant based hybrid routing algorithm for mobile Ad hoc networks[C]//Proc of Parallel Problem Solving from Nature (PPSN VIII).[S.l.]:Springer Verlag， 2004:461－470.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”