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

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

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

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

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

    本文針對(duì)傳統(tǒng)AODV路由協(xié)議中的路由修復(fù)方法開(kāi)銷(xiāo)大、時(shí)延長(zhǎng)這一問(wèn)題，設(shè)計(jì)了一種基于鏈路中斷預(yù)測(cè)的改進(jìn)算法。通過(guò)監(jiān)測(cè)鏈路質(zhì)量，預(yù)測(cè)鏈路中斷概率，及時(shí)啟用備用節(jié)點(diǎn)，盡量避免路由修復(fù)；而當(dāng)鏈路中斷時(shí)，采用逐層由上游節(jié)點(diǎn)發(fā)起的局部路由搜索，減小控制開(kāi)銷(xiāo)的波及范圍。算法在經(jīng)典的AODV協(xié)議上實(shí)現(xiàn)(稱之為RP-AODV)，并用NS2模擬軟件進(jìn)行了仿真。仿真結(jié)果表明，在多種場(chǎng)景下新算法都降低了路由開(kāi)銷(xiāo)，有效地提高了網(wǎng)絡(luò)性能，與傳統(tǒng)AODV相比控制開(kāi)銷(xiāo)降低了40%，端到端時(shí)延減少了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ù)測(cè)的移動(dòng)自組網(wǎng)路由發(fā)現(xiàn)算法[J].通信學(xué)報(bào)， 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ì)算機(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.