Ad Hoc網(wǎng)絡(luò)是一種特殊的無線移動網(wǎng)絡(luò)，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)地位平等,，無需設(shè)置任何中心控制節(jié)點(diǎn),，既可以快速、自動地組成一個獨(dú)立的網(wǎng)絡(luò)運(yùn)行,，也可以作為當(dāng)前具有固定設(shè)施網(wǎng)絡(luò)的一種補(bǔ)充形式[1],。在軍事、搶險救災(zāi)等領(lǐng)域應(yīng)用前景廣闊,。

    與現(xiàn)有的有線網(wǎng)絡(luò)和有基站的無線網(wǎng)絡(luò)有很大不同,，Ad Hoc網(wǎng)絡(luò)無中心、自組織,、動態(tài)拓?fù)浜湍芰坑邢薜奶攸c(diǎn),，使得現(xiàn)有的路由協(xié)議(RIP、OSPF)不再適應(yīng)Ad Hoc網(wǎng)絡(luò),因此路由技術(shù)一直是自組網(wǎng)的研究重點(diǎn)之一,。目前主要有按需路由和表驅(qū)動路由兩類[2],，其中按需路由協(xié)議不必維護(hù)到達(dá)所有節(jié)點(diǎn)的路由,有效地節(jié)省了網(wǎng)絡(luò)資源，能夠較好地適應(yīng)節(jié)點(diǎn)移動帶來的動態(tài)拓?fù)鋯栴},，得到了廣泛應(yīng)用,，其典型代表是AODV[3-4]協(xié)議。本文在AODV路由協(xié)議的基礎(chǔ)上,，提出基于鏈路中斷預(yù)測的路由算法(RP-AODV), 能夠降低廣播開銷,提高網(wǎng)絡(luò)性能,。
1 研究現(xiàn)狀
    針對路由可能發(fā)生中斷的問題，路由修復(fù)算法被提出,。最簡單的修復(fù)算法是由源節(jié)點(diǎn)重新發(fā)起新的路由發(fā)現(xiàn)過程,，顯然這會帶來極大的網(wǎng)絡(luò)開銷,。參考文獻(xiàn)[3]認(rèn)為路由斷裂時，斷裂處上游的節(jié)點(diǎn)會率先發(fā)現(xiàn)路徑失效,，此時直接由該節(jié)點(diǎn)發(fā)起到目的節(jié)點(diǎn)的路徑修復(fù)過程,。如果收到目標(biāo)節(jié)點(diǎn)的應(yīng)答，則說明路徑重建成功,；如果路由發(fā)現(xiàn)規(guī)定時間內(nèi)沒有收到目的節(jié)點(diǎn)返回的RREP,，則向其上游節(jié)點(diǎn)發(fā)送該目的節(jié)點(diǎn)的RERR，直到通知到該路由的源節(jié)點(diǎn),，然后再由源節(jié)點(diǎn)進(jìn)行新一輪的路由發(fā)現(xiàn)。
    參考文獻(xiàn)[5]提出一種兩跳范圍局部修復(fù)改進(jìn)算法,，當(dāng)節(jié)點(diǎn)A到節(jié)點(diǎn)B失效時,在斷鏈的附近可能存在A,、B的鄰居節(jié)點(diǎn)，因此由斷鏈的上游節(jié)點(diǎn)發(fā)送兩跳路由請求分組尋找下一跳節(jié)點(diǎn)B,，使得修復(fù)限制在兩跳范圍內(nèi),，路由開銷將會減少，尋路時間減短,。
2 基于鏈路中斷預(yù)測的AODV路由算法設(shè)計
2.1 算法思想
    從降低開銷的角度,，最理想的是路徑不中斷，但因?yàn)楣?jié)點(diǎn)的移動性,，即使采用穩(wěn)定路由策略獲取的路由也會發(fā)生路徑中斷,。而當(dāng)路徑中斷之后再去修復(fù)，都會帶來較大的額外開銷,，同時增大時延,。如果在路徑中斷之前，能夠預(yù)測到即將中斷,，提前采取措施尋找備用路由,，則可以實(shí)現(xiàn)平滑的路徑切換，當(dāng)鏈路中斷不可避免時,，不必返回源節(jié)點(diǎn)搜索,，而是逐層由上游節(jié)點(diǎn)展開局部搜索，在保證傳輸時延的同時使得路由開銷最小,。
    節(jié)點(diǎn)的移動導(dǎo)致節(jié)點(diǎn)間鏈路中斷,，但在較短時間內(nèi)，節(jié)點(diǎn)并不會走遠(yuǎn),，仍在原位置附近,，在較短時間內(nèi)節(jié)點(diǎn)的活動范圍也往往是以短途和小范圍為主[6-7]。同時鏈路中斷處也存在其他的鄰居節(jié)點(diǎn),。因此當(dāng)鏈路中斷時可以在斷點(diǎn)附近展開鏈路修復(fù),，沒必要全網(wǎng)重新開始新的路由,。如圖1所示，鏈路中斷一般有多種情況,，圖1(a)中源節(jié)點(diǎn)S和目的節(jié)點(diǎn)D,，經(jīng)由A、B,、C三個中間節(jié)點(diǎn)組成一條鏈路,。隨著節(jié)點(diǎn)的移動，鏈路出現(xiàn)斷裂,，如圖1(b)所示,，B節(jié)點(diǎn)移動出了A的覆蓋范圍，A與C之間失去了聯(lián)系,，但是存在E節(jié)點(diǎn)可以同時連接A和C,，則可以選擇E取代B。如果E節(jié)點(diǎn)不能同時覆蓋到A和C,，但可以覆蓋到A和B,，如圖1(c)所示，則可以在原鏈路中增加一個E節(jié)點(diǎn),，鏈路變?yōu)镾-A-E-B-C-D,。如果B和E都移動出了A的覆蓋區(qū)域，如圖1(d)所示,，則A到下游節(jié)點(diǎn)的鏈路完全中斷了,，必須由它的上游節(jié)點(diǎn)開始新的鏈路搜索。

    基于這樣一種思想,，將路由維護(hù)的過程分解為兩個步驟：(1)監(jiān)聽路由中各個鏈路的聯(lián)通情況,，判斷鏈路是否會中斷或者是否有更短鏈路的出現(xiàn)。(2)尋找保持鏈路聯(lián)通的備用節(jié)點(diǎn),，當(dāng)鏈路出現(xiàn)中斷時,，備用節(jié)點(diǎn)迅速啟動。如果找不到可用路由,，則逐層由更上游節(jié)點(diǎn)發(fā)起路由發(fā)現(xiàn)過程,，而并不是返回源節(jié)點(diǎn)。
2.2 算法設(shè)計
    鏈路的中斷是由節(jié)點(diǎn)的移動導(dǎo)致的,，但鏈路的中斷最終是由信號質(zhì)量下降引起,。因此判斷鏈路中斷最有效的方法是監(jiān)測鏈路信號質(zhì)量。無線信號在傳輸過程中存在著慢衰落和快衰落,，多種因素會引起信號質(zhì)量的起伏,，為了避免頻繁的鏈路切換，可以取一個時間窗口,，在這個窗口中取均值,，作為判斷依據(jù),。
    AODV的路由機(jī)制中上游節(jié)點(diǎn)路由表中存有下一跳節(jié)點(diǎn)的信息，而下游節(jié)點(diǎn)不知道上游節(jié)點(diǎn),，這就決定了當(dāng)鏈路中斷時,，只能由上游節(jié)點(diǎn)決定去尋找哪個節(jié)點(diǎn)。而不在原鏈路上的節(jié)點(diǎn)可以監(jiān)聽到周圍鏈路的信號質(zhì)量,，能夠知道自己是否可以修補(bǔ)鏈路 (如圖1(c)中的情況),，但是無法知道自己何時插入原鏈路，也無法知道是否可以縮短原鏈路(如圖1(b),、圖1(e)的情況),。因此需要修改AODV協(xié)議中的路由表，使之存有下面兩跳路由信息,，即存放下游鏈路的兩個節(jié)點(diǎn),，這樣周圍節(jié)點(diǎn)可以通過檢測周邊鏈路信號情況，判斷自己是否處在有用鏈路上,。
    根據(jù)鏈路斷裂的不同情況，路由維護(hù)分為以下幾類：
    (1)由周圍節(jié)點(diǎn)自己判斷是否能夠縮短原鏈路長度,，如果能則由該節(jié)點(diǎn)主動聯(lián)系上游和下游節(jié)點(diǎn),，確認(rèn)后啟動新鏈路。
    (2)鏈路可能斷裂處的上游節(jié)點(diǎn)通過監(jiān)聽反向路徑的信號質(zhì)量,，判斷鏈路當(dāng)前的狀況,，然后向周圍節(jié)點(diǎn)發(fā)起備用節(jié)點(diǎn)查詢，找到后確認(rèn)新鏈路,。
　(3)周邊沒有備用節(jié)點(diǎn)的情況,，由上游節(jié)點(diǎn)向更上游節(jié)點(diǎn)發(fā)送斷鏈請求，從而啟動新的路由搜索過程,。在搜索備用節(jié)點(diǎn)的過程中,，采用擴(kuò)展環(huán)的方法，在網(wǎng)絡(luò)層分組的報頭部分設(shè)計一個字段TTL,，限定為3,，表示分組可以被轉(zhuǎn)發(fā)的次數(shù)，收到該分組的節(jié)點(diǎn)每次將TTL值減1,，減至0則停止轉(zhuǎn)發(fā),。
2.3 算法流程
　路由維護(hù)的過程主要由鏈路上游節(jié)點(diǎn)和周邊節(jié)點(diǎn)完成，通過監(jiān)聽各個鏈路質(zhì)量,，判斷鏈路是否會中斷或者是否有更短鏈路的出現(xiàn),，然后尋找保持鏈路聯(lián)通的備用節(jié)點(diǎn)，并迅速啟動,。找不到備用節(jié)點(diǎn)時,，鏈路會斷裂,，此時啟動ERS算法在3跳之內(nèi)進(jìn)行局部路由修復(fù)。如果仍然不成功,，則由更上游的節(jié)點(diǎn)啟動路由發(fā)現(xiàn),。算法流程描述如下：
    (1)節(jié)點(diǎn)從收到數(shù)據(jù)包中獲取下游兩跳節(jié)點(diǎn)路由信息;
    (2)監(jiān)聽信號質(zhì)量，更新時間窗口信息,，計算均值,，并與設(shè)定的閾值比較，判斷鏈路中斷概率;
    (3)上游節(jié)點(diǎn)判斷鏈路可能中斷則會啟動ERS搜索,， 發(fā)起路由修復(fù)過程;
    (4)周邊節(jié)點(diǎn)判斷可以接續(xù)原鏈路或者縮短路由長度,，
則會向上下游節(jié)點(diǎn)發(fā)送應(yīng)答;
    (5)上游節(jié)點(diǎn)收到應(yīng)答信息，則更新路由表,；在規(guī)定時間內(nèi)沒有收到應(yīng)答,，則會向更上游中間節(jié)點(diǎn)發(fā)送重新路由請求，啟動新的路由發(fā)現(xiàn)過程,。
3 仿真分析
3.1 仿真模型
    用NS2作為仿真軟件進(jìn)行了模擬實(shí)驗(yàn),，將本文提出的基于鏈路中斷預(yù)測的AODV算法(RP-AODV)與標(biāo)準(zhǔn)AODV協(xié)議進(jìn)行比較，重點(diǎn)關(guān)注數(shù)據(jù)包投遞率,、歸一化路由開銷和端到端的平均延遲等3個性能指標(biāo),。
    數(shù)據(jù)包投遞率：成功到達(dá)的數(shù)據(jù)包和全部發(fā)出數(shù)據(jù)包的比率。
    歸一化路由開銷：每發(fā)送一個DATA數(shù)據(jù)分組需要的控制消息分組數(shù),，其中路由分組每一跳的傳輸均認(rèn)為是一個新的控制消息分組,，反映了網(wǎng)絡(luò)的擁塞程度和路由效率。
    端到端的平均延遲：每個數(shù)據(jù)包從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)間的傳送時延,。
    在仿真場景中,，100個節(jié)點(diǎn)隨機(jī)分布在1 500 m×1 000 m 的矩形區(qū)域內(nèi)，每個節(jié)點(diǎn)采用IEEE 802.11無線網(wǎng)絡(luò)接口,，無線傳輸半徑為250 m,，單一增益的全向天線，信道容量為2 Mb/s,。每次仿真隨機(jī)選擇10對源-目的節(jié)點(diǎn)傳輸數(shù)據(jù),，通信源是CBR流，數(shù)據(jù)包大小為512 B,，每秒發(fā)送2個包,，隊(duì)列長度為50。采用Random Way Point 運(yùn)動模型,， 節(jié)點(diǎn)最大移動速度Vmax分別為5 m/s,、10 m/s、15 m/s,、20 m/s,、25 m/s,，暫停時間為30 s，實(shí)驗(yàn)反復(fù)運(yùn)行50次,，每次仿真1 000 s,，實(shí)驗(yàn)結(jié)果取平均值。
3.2 仿真結(jié)果分析
3.2.1歸一化路由開銷
　由圖2可以看出,，在不同的最大移動速度下,，RP-AODV的路由開銷最小，總體上比AODV減低了40%,。說明通過新算法有效控制了鏈路中斷的次數(shù),，減小了路由發(fā)現(xiàn)的頻次，從而降低了路由開銷,。在速度較低時路徑中斷的概率較小,，隨著速度的增加，節(jié)點(diǎn)的移動性增強(qiáng),，路徑中斷概率增大,，路由修復(fù)過程出現(xiàn)頻繁，路由開銷都有所增加,，但是RP-AODV優(yōu)勢顯現(xiàn),。當(dāng)節(jié)點(diǎn)移動速度超過20 m/s以后，優(yōu)勢縮小,，主要是因?yàn)楣?jié)點(diǎn)的移定性增強(qiáng)之后，鏈路預(yù)測和備份鏈路的選擇的準(zhǔn)確性也會隨之下降,，增加了路由開銷,。總體上來看,，RP-AODV相比傳統(tǒng)AODV算法歸一化路由開銷降低40%左右,。

3.2.2 端到端平均時延
    圖3給出了平均端到端時延隨節(jié)點(diǎn)不同移動速度的變化情況。隨著節(jié)點(diǎn)移動速度的增加,，RP-AODV和傳統(tǒng)AODV協(xié)議的端到端時延都在增加,，其中AODV增加的幅度更為明顯。這是因?yàn)楣?jié)點(diǎn)移動速度增加以后,，鏈路斷開的幾率增大,，路由修復(fù)頻次增多，而路由修復(fù)過程中數(shù)據(jù)傳輸中斷,，數(shù)據(jù)包端到端時延增加,，RP-AODV算法通過鏈路預(yù)測，啟用備用節(jié)點(diǎn),，盡量減少路徑斷開的幾率,，即使鏈路斷開,，也會采用局部修復(fù)的方法，降低了路由修復(fù)時間,，從而減小了端到端時延,。總體上來看,，RP-AODV相比傳統(tǒng)AODV算法端到端時延降低25%左右,。

3.2.3 數(shù)據(jù)包投遞率
    從圖4中可看出，與傳統(tǒng)AODV算法相比,，改進(jìn)的RP-AODV算法數(shù)據(jù)包投遞率有所提高,，在節(jié)點(diǎn)最大移動速度不大時，兩者相差不大,，這是因?yàn)楣?jié)點(diǎn)移動較弱時,，鏈路斷開的幾率較小，發(fā)起路由修復(fù)次數(shù)較少,，數(shù)據(jù)包投遞率差別不大,。當(dāng)最大移動速度較大時，傳統(tǒng)AODV算法和算法投遞率都有所下降,，但RP-AODV仍然優(yōu)于傳統(tǒng)AODV,。這主要是因?yàn)楣?jié)點(diǎn)移動性提高之后，鏈路斷開的幾率增大,，路由修復(fù)頻次增多,，修復(fù)不成功的幾率也隨之增加，從而導(dǎo)致數(shù)據(jù)包投遞率有所下降,。在路由修復(fù)過程中,，RP-AODV能夠快速地找到備用節(jié)點(diǎn)，盡最大可能地保持原路由有效,，減少了路徑中斷次數(shù),，從而提高了數(shù)據(jù)包投遞率。

    本文針對傳統(tǒng)AODV路由協(xié)議中的路由修復(fù)方法開銷大,、時延長這一問題,，設(shè)計了一種基于鏈路中斷預(yù)測的改進(jìn)算法。通過監(jiān)測鏈路質(zhì)量,，預(yù)測鏈路中斷概率,，及時啟用備用節(jié)點(diǎn)，盡量避免路由修復(fù),；而當(dāng)鏈路中斷時,，采用逐層由上游節(jié)點(diǎn)發(fā)起的局部路由搜索，減小控制開銷的波及范圍。算法在經(jīng)典的AODV協(xié)議上實(shí)現(xiàn)(稱之為RP-AODV),，并用NS2模擬軟件進(jìn)行了仿真,。仿真結(jié)果表明，在多種場景下新算法都降低了路由開銷,，有效地提高了網(wǎng)絡(luò)性能,，與傳統(tǒng)AODV相比控制開銷降低了40%，端到端時延減少了25%,。
參考文獻(xiàn)
[1] CHLAMTAC I,CONTI M,LIU JN. Mobile Ad Hoc networking: imperatives and challenges[J]. Ad Hoc Networks,2003,1(1):13-64.
[2] 李世寶, 洪利. 基于距離預(yù)測的移動自組網(wǎng)路由發(fā)現(xiàn)算法[J].通信學(xué)報,， 2010,31(11):180-187.
[3] PERKINS C, BELDING-ROYER E. AODV Ad Hoc Ondemand distance vector Routing[S]. The Internet Engineering Task Force, IETF, RFC 3561, 2003.
[4] NI S Y, TSENG Y C, CHEN Y S. The broadcast storm  problem in a mobile ad hoc network[A]. the Fifth Annual  ACM/IEEE International Conference on Mobile Computing  and Networking (MOBICOM 99)[C]. Seattle, Washington, 1999:151-162.
[5] 丁緒星,吳青,謝方方.AODV 路由協(xié)議的本地修復(fù)算法[J]. 計算機(jī)工程, 2010,36(6):126-127.
[6] GONZALEZ M C, HIDALGO CA, BARABASI A L. Understanding individual human mobility patterns[J]. Nature, 2008,453:779-782.
[7] RHEE I, SHIN M, HONG S, et al. On the levy walk nature of human mobility[A]. INFOCOM 2008:the 27th Conference on Computer Communications[C]. Phoenix, AZ, 2008:924-932.