路由算法移動(dòng)多跳的AdHoc網(wǎng)絡(luò)

1、路由算法移動(dòng)多跳的Ad-hoc網(wǎng)絡(luò)Mesut Gunes, Otto Spaniol摘要： 移動(dòng)Ad-hoc網(wǎng)絡(luò)（MANET）是通過廣播形式移動(dòng)節(jié)點(diǎn)集合。這些網(wǎng)絡(luò)有一個(gè)重要的優(yōu)勢，它們不需要任何現(xiàn)有的基礎(chǔ)設(shè)施或中央管理。因此，移動(dòng)Ad-hoc網(wǎng)絡(luò)適合臨時(shí)的通訊聯(lián)系。但是這種靈活性是有代價(jià)的：由于頻繁拓?fù)涞淖兓?，很難組織溝通。 本文提出了一種新的按需路由算法，移動(dòng)多跳Ad-ho網(wǎng)絡(luò)。該算法基于螞蟻算法，是一類群體智能。螞蟻算法嘗試映射蟻群的解決問題的能力，來解決數(shù)學(xué)和工程問題。Ant-Colony-Based路由算法（ARA）具有高度靈活性，高效性，和可擴(kuò)展性。該算法設(shè)計(jì)的主要目標(biāo)是減少路由開銷

2、。此外，我們通過模擬結(jié)果比較ARA與其他路由協(xié)議，包括DSDV，AODV和DSR協(xié)議的性能。 關(guān)鍵詞:Ad-hoc網(wǎng)絡(luò)，移動(dòng)自組網(wǎng)，路由 1.引言 一個(gè)移動(dòng)多跳Ad-hoc網(wǎng)絡(luò)（MANET）是一套移動(dòng)節(jié)點(diǎn)廣播和溝通不需要任何基礎(chǔ)設(shè)施。這種網(wǎng)絡(luò)非常靈活，適合多種應(yīng)用，因?yàn)樗鼈冊(cè)试S沒有任何預(yù)先安裝的基礎(chǔ)設(shè)施（見圖1）。由于無線接口傳輸距離有限，在大多數(shù)情況下的溝通，要通過中間層節(jié)點(diǎn)中繼。因此，移動(dòng)多跳Ad-hoc網(wǎng)絡(luò)的每個(gè)節(jié)點(diǎn)也必須是一個(gè)路由器。除了災(zāi)難和軍事應(yīng)用領(lǐng)域，移動(dòng)廣告的部署，多媒體應(yīng)用也是Ad-hoc網(wǎng)絡(luò)另一個(gè)有趣的用途。然而，由于這種網(wǎng)絡(luò)的性能 ，必須在應(yīng)用之前得到充分完善。隨著新興的

3、無線技術(shù)，如IEEE 802.11a和藍(lán)牙技術(shù)，在移動(dòng)通訊網(wǎng)絡(luò)實(shí)現(xiàn)多媒體應(yīng)用變得更為現(xiàn)實(shí)。找到之間溝通路線的點(diǎn)是移動(dòng)的多跳Ad-hoc網(wǎng)絡(luò)的主要問題。問題是通過節(jié)點(diǎn)進(jìn)一步加劇了流動(dòng)性。近年來提出了許多不同的方法來解決這一問題11，15，但是至今沒有適用于所有情況的路由算法。其他方面的移動(dòng)Ad-hoc網(wǎng)絡(luò)，特別是節(jié)點(diǎn)的動(dòng)態(tài)地址配置4，14，6也有很多人研究。圖1：移動(dòng)多跳Ad-hoc網(wǎng)絡(luò)。節(jié)點(diǎn) F 移動(dòng)到節(jié)點(diǎn) G附近本文提出了一個(gè)需特設(shè)的路由算法，該算法是基于群體智能的。螞蟻算法是一種群體智能的一個(gè)子集，模仿螞蟻通過合作來解決復(fù)雜的問題而不需要直接溝通的能力。這是蟻群算法的一種算法，在最近幾年中

4、解決了例如優(yōu)化問題等問題。為了證明我們的算法是適用于移動(dòng)多跳Ad-hoc網(wǎng)絡(luò)，在ns-25有一些基于模擬結(jié)果的實(shí)施現(xiàn)況。本文的其余部分安排如下：第二節(jié)展望了現(xiàn)有的路由算法的移動(dòng)通訊網(wǎng)絡(luò)。在第三節(jié),我們現(xiàn)在螞蟻算法的基本知識(shí)。第四節(jié)更詳細(xì)的討論ARA路由算法的優(yōu)勢和存在的問題。隨后,在第五部分提出了一些模擬結(jié)果顯示性的方法,并將它與現(xiàn)有的路由算法比較。最后,在第六節(jié)進(jìn)行了總結(jié)。2.相關(guān)工作 2.1目的節(jié)點(diǎn)序列距離矢量（DSDV）在傳統(tǒng)的距離矢量路由，每個(gè)節(jié)點(diǎn)維護(hù)著節(jié)點(diǎn)vD到可能到達(dá)的鄰居節(jié)點(diǎn)vj的距離d(i, j, D)，當(dāng)一個(gè)節(jié)點(diǎn)需要選擇它的一個(gè)直接鄰居vj傳遞數(shù)據(jù)包,它選擇其中最短距離。為了

5、保持距離的時(shí)效性，每個(gè)節(jié)點(diǎn)向其路由表中所有的鄰居定期廣播。節(jié)點(diǎn)接收到來自鄰居的廣播消息，更新自己的路由表并應(yīng)用于最短路徑算法的算法中,比如Dijkstra算法。Destination-Sequenced的距離向量路由12，11（DSDV）適用于這個(gè)環(huán)境管理模式的移動(dòng)Ad - hoc網(wǎng)絡(luò)。在DSDV，例如當(dāng)附近的一個(gè)節(jié)點(diǎn)發(fā)生變化，路由信息就會(huì)交換新信息。這個(gè)過程中產(chǎn)生相當(dāng)大的開銷的Ad-hoc網(wǎng)絡(luò)。為了減少開銷，提出了兩種不同的解決方案：完全轉(zhuǎn)儲(chǔ)，和增量轉(zhuǎn)儲(chǔ)。完全轉(zhuǎn)儲(chǔ)包含整個(gè)節(jié)點(diǎn)的路由表。相反，一個(gè)增量轉(zhuǎn)儲(chǔ)包含自完全轉(zhuǎn)儲(chǔ)部分變化。DSDV通過一個(gè)序列號(hào)和每個(gè)路由表的入口避免循環(huán)。這使節(jié)點(diǎn)可以區(qū)分

6、舊和新之間路由信息。一個(gè)節(jié)點(diǎn)以最高的序列號(hào)選擇路由表入口。如果幾個(gè)線路目的地相同，且以相同的順序進(jìn)行編號(hào)，則選定成本較低的路由表。2.2特設(shè)按需距離矢量協(xié)議（AODV協(xié)議）特設(shè)按需距離矢量協(xié)議10，11，13（路由協(xié)議）是移動(dòng)Ad-hoc網(wǎng)絡(luò)的另一種距離矢量路由。AODV是按需路由方法,即進(jìn)行不定期的路由信息交換。這個(gè)協(xié)議包含兩個(gè)階段:1）路由發(fā)現(xiàn)，2）路由維護(hù)。一個(gè)節(jié)點(diǎn)若想與其他節(jié)點(diǎn)進(jìn)行通訊，會(huì)首先從它自己的路由表中選擇一條路徑。如果找到一條路徑則立即開始傳遞，否則該節(jié)點(diǎn)啟動(dòng)一個(gè)路由發(fā)現(xiàn)。該路由發(fā)現(xiàn)過程包括一個(gè)廣播形式的路由請(qǐng)求消息（路由請(qǐng)求）。該路線發(fā)現(xiàn)過程由一個(gè)route-request

7、消息(RREQ)發(fā)出。如果一個(gè)節(jié)點(diǎn)中包含一個(gè)有效的路徑,它向路由請(qǐng)求回復(fù)route-reply(RREP)信息。此外,在其反路線進(jìn)入路由表中建立了一個(gè)回復(fù)節(jié)點(diǎn)所需包含的地址,源節(jié)點(diǎn)，跳數(shù)的來源，以及下一跳的地址，即節(jié)點(diǎn)的地址收到的信息。它們永久相聯(lián)，即反向路線進(jìn)入的路線條目如果在規(guī)定生命周期內(nèi)不使用將被刪除。第二階段的協(xié)議被稱為路由維護(hù)。它是由源節(jié)點(diǎn)組成，其中可分為:（一）源節(jié)點(diǎn)啟動(dòng)一個(gè)新的路線源節(jié)點(diǎn)的探索過程,(二)目的地或中間節(jié)點(diǎn)移動(dòng)路線的錯(cuò)誤信息(如:RERR)被派往源節(jié)點(diǎn)。中間節(jié)點(diǎn)接收RERR更新路由表設(shè)置距離的目標(biāo)。如果源節(jié)點(diǎn)接收到一個(gè)RERR路線將開始一項(xiàng)新的路由發(fā)現(xiàn)。為了防止全局

8、廣播， AODV協(xié)議介紹了本地連接的管理，通過包含一個(gè)節(jié)點(diǎn)的地址和其他信息的HELLO消息路由應(yīng)答包進(jìn)行定期交流。2.3動(dòng)態(tài)源路由（DSR）源路由的基本思想是源節(jié)點(diǎn)包括將每個(gè)數(shù)據(jù)包的完整路由信息，例如：（vS,V1，V2， VD）發(fā)往到VD的數(shù)據(jù)包，經(jīng)由V1，V2等。動(dòng)態(tài)源路由7，8，11（DSR）為Ad-hoc網(wǎng)絡(luò)提供了源路由選擇的方法，主要問題是如何獲取某一目的地的源路由。DSR使用兩個(gè)階段：1）路由發(fā)現(xiàn)，和2）路由維護(hù)。如果一個(gè)源節(jié)點(diǎn)vS沒有到達(dá)指定目的地VD的路由線路，則向其鄰居節(jié)點(diǎn)廣播請(qǐng)求REEQ。該路由請(qǐng)求是一個(gè)小包,包含vS,vD，唯一的id RREQ_ID，和LSD（這是節(jié)點(diǎn)轉(zhuǎn)

9、交的路由請(qǐng)求清單）。中間節(jié)點(diǎn)接收RREQ之后添加到它的LSD，同時(shí)向其鄰居廣播地址,但不向發(fā)送RREQ的結(jié)點(diǎn)回復(fù)信息。如果目標(biāo)節(jié)點(diǎn)VD接收路由要求獲取其LSD，則創(chuàng)建一個(gè)含有LSD的路由響應(yīng)RREP返回到源節(jié)點(diǎn)。圖2顯示的DSR路由發(fā)現(xiàn)階段。圖2：在DSR路由發(fā)現(xiàn)。目的地Vd通過RREP將最短路徑返回給源節(jié)點(diǎn)。這里使用的度量是躍點(diǎn)的數(shù)量。該方法的第二階段，路由維護(hù)。當(dāng)一個(gè)節(jié)點(diǎn)vi發(fā)送數(shù)據(jù)包轉(zhuǎn)發(fā)到節(jié)點(diǎn) v 它預(yù)計(jì)將從 V 得到確認(rèn)。如果在一個(gè)特定的時(shí)間內(nèi)vi沒有獲得任何確認(rèn),它將會(huì)發(fā)送一個(gè)包含了該路線轉(zhuǎn)發(fā)失敗的路由錯(cuò)誤信息RERR到源節(jié)點(diǎn)。隨后,源節(jié)點(diǎn)在它的路由表尋找另一個(gè)替代路線或啟動(dòng)一個(gè)新的

10、路由發(fā)現(xiàn)過程。 3.螞蟻算法 螞蟻算法是一種群體智能模型中通過合作來解決復(fù)雜任務(wù)的昆蟲群行為。他們是多智能體系統(tǒng)代理表明個(gè)體的行為的螞蟻。參見3，1獲取更多信息。 3.1基本蟻群算法 蟻群算法的基本理念是取自螞蟻的食物搜尋行為。當(dāng)螞蟻尋找食物的時(shí)候,他們就會(huì)從他們的巢走向食物。當(dāng)一只螞蟻到達(dá)十字路口,它必須決定如何采取下一步。螞蟻根據(jù)沉積的信息素來決定選擇那一條路徑。信息素的濃度對(duì)路徑的選擇提供了指示。隨著時(shí)間的推移, 由于信息的擴(kuò)散效應(yīng)濃度降低。 圖3顯示一個(gè)場景和兩條線路。第一個(gè)螞蟻隨機(jī)選擇一個(gè)分支。由于該路線較短，螞蟻?zhàn)咴撀窂綍?huì)第一個(gè)到達(dá)食物。途中回巢，螞蟻又必須選擇一個(gè)路徑。過了一段時(shí)

11、間較短路徑的信息素濃度將高于較長的路徑，因?yàn)槲浵伿褂幂^短的路徑使信息素濃度增加的更快。因此，最終螞蟻將只使用這條線路。 螞蟻的這種行為可以用來在網(wǎng)絡(luò)中尋找最短路徑。特別是在動(dòng)態(tài)的組成部分,該方法提供了高度變化的適應(yīng)性, 盡管移動(dòng)通訊網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中存在的這些網(wǎng)絡(luò)連接是經(jīng)常發(fā)生變化的。 圖3：所有的螞蟻在檢索后都能找到最短路徑 信息素是一種香豆素，螞蟻可以識(shí)別這種味道。 3.2一個(gè)簡單的螞蟻算法 設(shè)G =（V，E）為與n =|V|連通的節(jié)點(diǎn)。簡單的蟻群優(yōu)化方式可以用來在圖G上找到源節(jié)點(diǎn)Vs和目標(biāo)節(jié)點(diǎn)Vd 之間的最短路徑。節(jié)點(diǎn)的編號(hào)給出了路徑的長度。變量i，J類（人工信息素），它在訪問連接頂點(diǎn)vi和

12、vj的邊e(i,j) E時(shí)由螞蟻分類。信息素濃度i,j 是使用這條邊的表示（象征）。最初i，J對(duì)任意邊e（1，j）是個(gè)常量。 一個(gè)螞蟻位于結(jié)點(diǎn)i用結(jié)點(diǎn)vj的信息素濃度i,jNi去計(jì)算節(jié)點(diǎn)vj是下一個(gè)跳躍的機(jī)率。其中Ni是鄰接于結(jié)點(diǎn)vi的所有結(jié)點(diǎn)的集合。一個(gè)結(jié)點(diǎn)vi等的過渡機(jī)率pi,j等一個(gè)螞蟻訪問過結(jié)點(diǎn)vi后選擇訪問結(jié)點(diǎn)vj的機(jī)率如下定義：在路線尋找的過程中，螞蟻存放信息素。在算法的簡單版本，螞蟻存放不變的數(shù)量信息，對(duì)于邊 e(vi, vj )當(dāng)螞蟻從節(jié)點(diǎn)vi移動(dòng)到vj時(shí)，信息數(shù)量改變?nèi)缦拢?i,j= i,j+ 就像真實(shí)的信息素濃度隨時(shí)間下降，在這個(gè)簡單的蟻群算法中描述為：i,j (t+):=

13、 (1 q)·i,j (t), q (0, 1 （1）3.3為什么蟻群算法適用于Ad-hoc網(wǎng)絡(luò) 簡單的蟻群算法在上一節(jié)列舉了很多原因說明為什么這種算法可以在移動(dòng)多跳Ad - hoc網(wǎng)絡(luò)中使用。下面我們討論與Ad - hoc網(wǎng)絡(luò)有關(guān)的一些重要性質(zhì)。動(dòng)態(tài)拓?fù)洌涸诮?jīng)典的路由算法多跳Ad - hoc網(wǎng)絡(luò)中此項(xiàng)表現(xiàn)較差。螞蟻算法基于自主代理模仿螞蟻系統(tǒng)。這使得高適應(yīng)當(dāng)前的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。 基本工作：與其他的路由方法相比，蟻群算法僅僅基于本地信息,即沒有路由表或其他信息塊已經(jīng)被傳送到其它節(jié)點(diǎn)的網(wǎng)絡(luò)。鏈路質(zhì)量：它將信息素濃度的概念整合到鏈路中,特別是引入了蒸發(fā)過程。這將有助于加強(qiáng)對(duì)鏈路質(zhì)量的決策過

14、程。重要的是該方法可以修改，以便節(jié)點(diǎn)也可以獨(dú)立的操縱信息素濃度，例如如果一個(gè)節(jié)點(diǎn)檢測到鏈路的性能變化。支持多路徑：每個(gè)節(jié)點(diǎn)都有一個(gè)與所有鄰居節(jié)點(diǎn)關(guān)聯(lián)的路由表項(xiàng)，其中也包含信息素濃度。對(duì)于下一個(gè)節(jié)點(diǎn)選擇決策規(guī)則是基于當(dāng)前節(jié)點(diǎn)的信息素濃度。因此，這種方法支持多路徑路由。4.螞蟻路由算法的移動(dòng)自組網(wǎng) 在這一節(jié)中，我們討論適應(yīng)于多跳Ad - hoc網(wǎng)絡(luò)的簡單螞蟻算法，并描述蟻群路由算法（ARA）。路由算法類似于許多其他路由方法由三個(gè)階段組成。4.1路由發(fā)現(xiàn)階段 在路由發(fā)現(xiàn)階段創(chuàng)建新路線。新路線的創(chuàng)建需要使用一個(gè)前驅(qū)螞蟻（FANT）和一個(gè)螞蟻（BANT）。AFANT是一個(gè)代理，建立了可以回到源節(jié)點(diǎn)的信息

15、素軌道。類似的，BANT建立了信息素來源的軌道，即目標(biāo)節(jié)點(diǎn)。FANT是一個(gè)有單獨(dú)序列號(hào)的小包。節(jié)點(diǎn)能夠區(qū)分基礎(chǔ)序列號(hào)和重復(fù)的數(shù)據(jù)包源地址。 節(jié)點(diǎn)首次接到FANT時(shí)在其路由表創(chuàng)建一個(gè)記錄。一個(gè)路由表項(xiàng)由三部分組成（目的地址，下一跳，信息素的值）。該節(jié)點(diǎn)FANT的源地址的作為目的地址,前一節(jié)點(diǎn)的地址作為下一跳,并利用FANT經(jīng)過的跳數(shù)計(jì)算出信息值。然后節(jié)點(diǎn)將其FANT發(fā)送給鄰居節(jié)點(diǎn)。利用唯一的序列號(hào),復(fù)制并移動(dòng)FANT。提取目的節(jié)點(diǎn)的FANT信息，創(chuàng)建一個(gè)BANT，并返回到源節(jié)點(diǎn)。該BANT的任務(wù)類似于FANT，即跟蹤一個(gè)節(jié)點(diǎn)。當(dāng)發(fā)送者接收到來目標(biāo)節(jié)點(diǎn)的BANT，則該路徑建立和數(shù)據(jù)包可以被發(fā)送。

16、圖4：ARA中路徑探索過程a)前驅(qū)螞蟻F從Vs發(fā)送到目的節(jié)點(diǎn)Vd。前驅(qū)螞蟻穿過其中節(jié)點(diǎn)，并初始化它們的路由表和其他節(jié)點(diǎn)信息素值。b)后繼螞蟻B與前驅(qū)螞蟻執(zhí)行相同任務(wù)。它從目標(biāo)節(jié)點(diǎn)Vd發(fā)送到源節(jié)點(diǎn)Vs。圖4顯示了ARA路由發(fā)現(xiàn)階段。圖4 a）顯示了信息素是如何返回到源節(jié)點(diǎn)Vs的過程。遠(yuǎn)期螞蟻只創(chuàng)建一個(gè)信息素有望在節(jié)點(diǎn)6源節(jié)點(diǎn)，但有兩個(gè)節(jié)點(diǎn)5追蹤，通過節(jié)點(diǎn)3 a和節(jié)點(diǎn)4。圖4 b）以螞蟻為落后類似的情況。只創(chuàng)建一個(gè)信息素追蹤到目標(biāo)節(jié)點(diǎn) v D在節(jié)點(diǎn)5和6兩個(gè)節(jié)點(diǎn)的軌道。因此，多路徑路由也支持ARA。 4.2路由維護(hù) 該路由算法的第二階段稱為路由維護(hù)。這一階段在通信過程中負(fù)責(zé)維修線路。不需要為此創(chuàng)建

17、任何特殊的數(shù)據(jù)包。一旦FANT和BANT為源和目的節(jié)點(diǎn)創(chuàng)建了信息素跟蹤路徑，則數(shù)據(jù)包可以用來維護(hù)道路。如生物系統(tǒng)，建立路徑時(shí)信息素的初始值不是永遠(yuǎn)不變的。當(dāng)一個(gè)節(jié)點(diǎn)Vi發(fā)送數(shù)據(jù)包到目的地Vd的鄰居節(jié)點(diǎn)Vj，它增加了條目的信息素值 （Vd，Vj，），即這條道路到目的地是加強(qiáng)了的數(shù)據(jù)包。同樣，下一跳Vj增加了條目信息素值 （vS , vi, ），即后繼的路徑源節(jié)點(diǎn)也得到加強(qiáng)。在真正的信息素蒸發(fā)過程以公式1為參考過程。4. 以下是基于圖4的例子。下面你會(huì)看到節(jié)點(diǎn)5和6的路由表。 Dest. NodeNext HopPheromonevSvD.46.12.節(jié)點(diǎn)5的路由表 節(jié)點(diǎn)6的路由表Dest. No

18、deNext HopPheromonevSvD.57.34. 、現(xiàn)在，我們考慮兩個(gè)節(jié)點(diǎn)的路由表后，節(jié)點(diǎn)5轉(zhuǎn)發(fā)數(shù)據(jù)包到節(jié)點(diǎn)6。只有對(duì)目標(biāo)節(jié)點(diǎn)Vd的進(jìn)入改變了節(jié)點(diǎn)5的路由表。與節(jié)點(diǎn)6的路由表的變化類似，只有源節(jié)點(diǎn)Vs發(fā)生了改變。節(jié)點(diǎn)5與節(jié)點(diǎn)6的改變相同。我們進(jìn)行模擬，其賦值為0.1。 節(jié)點(diǎn)5的路由表 節(jié)點(diǎn)6的路由表節(jié)點(diǎn)5的路由表Dest. NodeNext HopPheromonevSvD.46.12 + .Dest. NodeNext HopPheromonevSvD.57.3 + 4.、信息素值下降的時(shí)間間隔為=1秒。以（1-q）=0.1的速度成倍遞減（見公式1）。兩個(gè)節(jié)點(diǎn)路由表的增加過程如下

19、： Dest. NodeNext HopPheromonevSvD.46.1 · (1 q)(2 + ) · (1 q).Dest. NodeNext HopPheromonevSvD.57.(3 + ) · (1 q)4 · (1 q).Dest. NodeNext HopPheromonevSvD.46.1 · (1 q)(2 + ) · (1 q).節(jié)點(diǎn)5的路由表（秒后） 節(jié)點(diǎn)6的路由表（秒后） 上述方法可能會(huì)導(dǎo)致不希望出現(xiàn)的循環(huán)。ARA通過在路由發(fā)現(xiàn)階段使用循環(huán)這種非常簡單的方法來防止死循環(huán)的出現(xiàn)。節(jié)點(diǎn)可以根據(jù)源地址和序列號(hào)識(shí)

20、別數(shù)據(jù)包的重復(fù)收據(jù)。如果節(jié)點(diǎn)收到一個(gè)重復(fù)的數(shù)據(jù)包，它將設(shè)置 DUPLICATE_ERROR 標(biāo)志，同時(shí)發(fā)送數(shù)據(jù)包返回到前驅(qū)的節(jié)點(diǎn)。前驅(qū)節(jié)點(diǎn)停用這個(gè)節(jié)點(diǎn)的鏈接，因此 ，這種數(shù)據(jù)包不能被發(fā)送到這個(gè)方向了。 4.3路由故障處理 ARA的第三和最后階段處理特別節(jié)點(diǎn)移動(dòng)造成的路由，這是移動(dòng)Ad-hoc網(wǎng)絡(luò)中常見的故障。正確的設(shè)置是在MAC層網(wǎng)絡(luò)設(shè)置ARA的IE802.11。通過對(duì)MAC層失蹤確認(rèn)使得ARA不能接收到路線失敗信息。如果一個(gè)節(jié)點(diǎn)接收到ROUTE_ERROR消息時(shí)，它首先通過設(shè)置信息素值為0來停用此鏈接。隨后，在其路由表另一條節(jié)點(diǎn)搜索。如果有另一個(gè)目標(biāo)，則通過該路徑發(fā)送數(shù)據(jù)包路由。否則，該節(jié)點(diǎn)

21、通知它的鄰居，希望他們可以把數(shù)據(jù)包轉(zhuǎn)發(fā)到目的地。無論是數(shù)據(jù)包可以運(yùn)到目的地節(jié)點(diǎn)或回溯到源節(jié)點(diǎn)，如果數(shù)據(jù)包沒有到達(dá)目的地，源節(jié)點(diǎn)發(fā)起一個(gè)新的路由發(fā)現(xiàn)過程。 4.4 ARA的性能 通過對(duì)9的分析，移動(dòng)Ad-hoc網(wǎng)絡(luò)應(yīng)符合下列要求，ARA需要做到： 分布式操作：在ARA中，每個(gè)節(jié)點(diǎn)在其路由表中擁有一個(gè)信息素計(jì)數(shù)器i,j 用來連接節(jié)點(diǎn)Vi和Vj。當(dāng)螞蟻路線搜尋，檢測鏈路故障時(shí)每個(gè)節(jié)點(diǎn)獨(dú)立的控制信息素。 避免循環(huán)：路線唯一的序列號(hào)使得數(shù)據(jù)包傳輸過程避免了循環(huán)。 基礎(chǔ)需求的操作：信息素計(jì)數(shù)器i,j使路線有操縱性。隨著時(shí)間的推移，當(dāng)螞蟻不訪問節(jié)點(diǎn)使對(duì)信息素減少量降到最低值。只能由發(fā)送者啟動(dòng)路由發(fā)現(xiàn)過程。睡

22、眠周期運(yùn)行：當(dāng)節(jié)點(diǎn)的路由信息素值已經(jīng)降到較低時(shí)，節(jié)點(diǎn)可以進(jìn)入睡眠。除非數(shù)據(jù)包必須，其他的節(jié)點(diǎn)不會(huì)考慮這個(gè)節(jié)點(diǎn)。此外，ARA具有以下屬性： 位置：路由表和節(jié)點(diǎn)的統(tǒng)計(jì)信息，不會(huì)傳送到其他節(jié)點(diǎn)。 多路徑：每個(gè)節(jié)點(diǎn)到達(dá)目的地可以有多條路徑。例如，路線的選擇取決于鏈接的環(huán)境質(zhì)量。休眠模式：處于休眠模式的節(jié)點(diǎn)只處理傳送給它的數(shù)據(jù)包，這樣可以節(jié)省資源和電量。4.5 ARA的開銷預(yù)期ARA的開銷非常小，因?yàn)楣?jié)點(diǎn)之間沒有路由表的改變。不像其他的路由算法，F(xiàn)ANT和BANT數(shù)據(jù)包不會(huì)傳送多路由信息，只有一個(gè)唯一的序列號(hào)傳輸?shù)穆酚蓴?shù)據(jù)包。大部分路線通過數(shù)據(jù)包進(jìn)行維護(hù)。ARA只需要數(shù)據(jù)包中的IP頭信息。 5仿真結(jié)果

23、5.1仿真環(huán)境 我們已經(jīng)在2-5中應(yīng)用了ARA。對(duì)于我們的結(jié)果， 我們假設(shè)50個(gè)移動(dòng)節(jié)點(diǎn)通過IEEE 802.11溝通。節(jié)點(diǎn)在一個(gè)1500m×300m的模擬仿真區(qū)域移動(dòng)。模擬的時(shí)間是900秒。 節(jié)點(diǎn)的最大速度均為10m/s，并根據(jù)模型2隨機(jī)流動(dòng)。在這個(gè)模型中，節(jié)點(diǎn)在模擬領(lǐng)域隨機(jī)選擇一個(gè)點(diǎn)，并為下一步的行動(dòng)分配一個(gè)介于0和最大速度之間的速度值。隨后，節(jié)點(diǎn)以恒定的速度到達(dá)隨機(jī)選擇的點(diǎn)。在抵達(dá)終點(diǎn)節(jié)點(diǎn)后仍然有一段時(shí)間。隨后，該節(jié)點(diǎn)重復(fù)選擇一個(gè)新的終結(jié)點(diǎn)和新的速度操作。我們進(jìn)行了7次暫停時(shí)間的不同的測試，分別為0，30，60，120，300，600和900秒。當(dāng)暫停時(shí)間為0秒時(shí)，節(jié)點(diǎn)不斷移動(dòng)

24、。相反，當(dāng)暫停時(shí)間為900秒時(shí)節(jié)點(diǎn)不動(dòng)。正如我們?cè)谝摬糠痔岬?，與其他類似的算法性能比較，下面我們主要在這些方面討論ARA。 5.2比較與現(xiàn)有路由算法 為了得到一個(gè)更好的性能，我們將ARA與DSDV，AODV協(xié)議和DSR進(jìn)行比較，在第二部分詳細(xì)介紹了該部分內(nèi)容。我們以恒定10比特速率（CBR）在UDP流量并行連接模擬得到以下數(shù)據(jù)。參數(shù)與2相同。 圖5：作為暫停時(shí)間的函數(shù)的一小部分，比較了4個(gè)協(xié)議成功傳遞的數(shù)據(jù)包數(shù)量。模擬10 CBR的連接。 我們將首先討論路由協(xié)議的強(qiáng)度。圖5顯示了傳遞率，即路由協(xié)議是否能夠提供一定數(shù)量的正確數(shù)據(jù)包。 在暫停時(shí)間低的情況下，即頻繁的移動(dòng)和頻繁的拓?fù)渥兓闆r下，只

25、有DSR和ARA能夠提供超過95的數(shù)據(jù)包。DSR在非常高的動(dòng)態(tài)顯示出的最佳性能的情況活動(dòng)性較差（最多300秒暫停時(shí)間）。ARA非常接近DSR。AODV路由協(xié)議和DSDV高流動(dòng)性情況下表現(xiàn)不佳。他們只能提供600或更多秒的暫停時(shí)間。 圖6 ARA的傳遞率，置信度為=0.05圖7描述了圖5中所提到的路由算法的開銷。圖表顯示了路由提供一個(gè)數(shù)據(jù)比特位的一小部分。我們計(jì)算路由使用的位數(shù)，因?yàn)椴煌膮f(xié)議產(chǎn)生了截然不同的開銷。這里ARA顯示出其優(yōu)勢。在非常高動(dòng)態(tài)（0 - 100秒暫停時(shí)間的情況下），它產(chǎn)生最少的開銷。按照暫停時(shí)間300 - 600秒，AODV協(xié)議與ARA非常相似， ARA和AODV協(xié)議是對(duì)D

26、SR的模擬仿真。只有DSDV與其它三種情況有明顯的差異。 圖8顯示的是置信區(qū)間為95%的ARA開銷。所有情況的模擬的結(jié)果非常相近。這表明，ARA考慮了流動(dòng)情景的路由開銷。 我們現(xiàn)在比較以包的數(shù)量為基礎(chǔ)的路由協(xié)議的開銷。圖9描述了必要的路由下數(shù)據(jù)包的數(shù)量。在高流動(dòng)性的情況DSR和ARA產(chǎn)生最小的開銷。DSR比ARA有更好的性能。這是由于在路由發(fā)現(xiàn)階段，具有高流動(dòng)性的路線故障節(jié)點(diǎn)頻繁發(fā)生。因此，路線失敗處理算法，要經(jīng)常進(jìn)行，在最壞情況下的路徑回溯到sender是必要的。流動(dòng)性較低（高達(dá)300秒的暫停時(shí)間），ARA和DSR產(chǎn)生相似數(shù)額的開銷。在這里，AODV協(xié)議和DSDV產(chǎn)生大量的數(shù)據(jù)包，路由性能不

27、佳。 圖10顯示在圖9考慮的情境下，置信區(qū)間為95的ARA產(chǎn)生開銷。 圖7：4個(gè)協(xié)議成功發(fā)送位和所需要的比特的一部分的比較。 圖8：ARA的總開銷。置信度為 = 0.056結(jié)論和未來工作 移動(dòng)多跳Ad-hoc網(wǎng)絡(luò)是靈活的網(wǎng)絡(luò)，并不需要預(yù)先安裝的基礎(chǔ)設(shè)施。隨著即將到來的無線傳輸技術(shù)和應(yīng)用的增加，路由給移動(dòng)多跳Ad-hoc網(wǎng)絡(luò)的節(jié)點(diǎn)增加帶來重大挑戰(zhàn)。圖9：4個(gè)協(xié)議所需路由數(shù)據(jù)包數(shù)的比較，模擬10 CBR的連接。 圖10：ARA的包的開銷。置信度為 = 0.05， CBR的連接和仿真運(yùn)行間隔10s。 本文提出了一種新的按需路由的方法移動(dòng)多跳（ARA）基于螞蟻算法的網(wǎng)絡(luò)。此外，與現(xiàn)有的三個(gè)路由算法在工

28、作表現(xiàn)方面進(jìn)行了比較。 由于我們的主要目標(biāo)之一是減少必要的路由開銷，因此主要從這個(gè)角度來討論該算法的性能。為了對(duì)所花費(fèi)的開銷進(jìn)行比較，我們考慮了路由位以及其中的數(shù)據(jù)包開銷的其他算法。經(jīng)進(jìn)一步調(diào)查，包括高網(wǎng)絡(luò)負(fù)載和多媒體數(shù)據(jù)的實(shí)驗(yàn)，我們的分析表明，ARA的表現(xiàn)是非常接近的DSR所考慮的模擬場景，并且開銷更低。 此外，我們將對(duì)信息素濃度的影響做更為詳細(xì)的研究。由于ARA是一個(gè)啟發(fā)式的路由算法，采用ARA實(shí)現(xiàn)新的路徑動(dòng)態(tài)發(fā)現(xiàn)，所產(chǎn)生的路徑有時(shí)并不是最優(yōu)路徑，我們也正在努力改善這方面情況。 參考文獻(xiàn) 1 Eric Bonabeau , Marco Dorigo , and Guy Theraulaz.

29、 Swarm intelligence: from natural to artificial intelligence. Oxford University Press, 1999.ISBN 0-19-513158-4.2Josh Broch , David A. Maltz, David B. Johnson, Yih-Chun Hu, and Jorjeta Jetcheva. A performance comparison of multihop wireless ad hoc network routing protocols. Pro- ceedings of the Fourt

30、h Annual ACM/IEEE International Conference on Mobile Comput- ing and Networking (MobiCom98), pages 8597, 1998.3Marco Dorigo and Gianni Di Caro. The ant colony optimization meta-heuristic. In David Corne, Marco Dorigo, and Fred Glover, editors, New Ideas in Optimization, pages 1132. McGraw-Hill, Lond

31、on, 1999.4R.Droms.Dynamic host configuration protocol, /rfc/rfc2131.txt,Mar 1997.5Kevin Fall and Kannan Varadhan. The ns Manual, Nov 2000.6Mesut Günes¸ and Jörg Reibel. An ip address configuration algorithm for zeroconf. mo- bile multi-hop ad-hoc networks. In Proceedings of

32、the International Workshop on Broad- band Wireless Ad-Hoc Networks and Services, Sophia Antipolis, France, September 2002. ETSI.7David B Johnson and David A Maltz. Dynamic source routing in ad hoc wireless net- works. In T. Imielinski and H. Korth, editors, Mobile Computing, volume 353. Kluwer Acade

33、mic Publishers, 1996.8D.B.Johnson,D.A.Maltz,Y.-C. Hu, and J. G. Jetcheva. The dynamic source routing protocol for mobile ad hoc networks. IETF Internet draft, draft-ietf-manet-dsr-04.txt, November 2000.9Joseph P. Macker and M.Scott Corson. Mobile adhoc networking and the IETF. Mobile Computing and Communications Review, 2(1):914, 1998.10Charle