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)銷,提高網(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à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)銷將會(huì)減少,，尋路時(shí)間減短,。
2 基于鏈路中斷預(yù)測(cè)的AODV路由算法設(shè)計(jì)
2.1 算法思想
    從降低開(kāi)銷的角度，最理想的是路徑不中斷,，但因?yàn)楣?jié)點(diǎn)的移動(dòng)性,，即使采用穩(wěn)定路由策略獲取的路由也會(huì)發(fā)生路徑中斷。而當(dāng)路徑中斷之后再去修復(fù),，都會(huì)帶來(lái)較大的額外開(kāi)銷,，同時(shí)增大時(shí)延。如果在路徑中斷之前,，能夠預(yù)測(cè)到即將中斷,，提前采取措施尋找備用路由，則可以實(shí)現(xiàn)平滑的路徑切換,，當(dāng)鏈路中斷不可避免時(shí),，不必返回源節(jié)點(diǎn)搜索，而是逐層由上游節(jié)點(diǎn)展開(kāi)局部搜索,，在保證傳輸時(shí)延的同時(shí)使得路由開(kāi)銷最小,。
    節(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)到周圍鏈路的信號(hào)質(zhì)量，能夠知道自己是否可以修補(bǔ)鏈路 (如圖1(c)中的情況),，但是無(wú)法知道自己何時(shí)插入原鏈路,，也無(wú)法知道是否可以縮短原鏈路(如圖1(b)、圖1(e)的情況),。因此需要修改AODV協(xié)議中的路由表,，使之存有下面兩跳路由信息，即存放下游鏈路的兩個(gè)節(jié)點(diǎn),，這樣周圍節(jié)點(diǎn)可以通過(guò)檢測(cè)周邊鏈路信號(hào)情況,，判斷自己是否處在有用鏈路上。
    根據(jù)鏈路斷裂的不同情況,，路由維護(hù)分為以下幾類：
    (1)由周圍節(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)前的狀況，然后向周圍節(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)銷和端到端的平均延遲等3個(gè)性能指標(biāo)。
    數(shù)據(jù)包投遞率：成功到達(dá)的數(shù)據(jù)包和全部發(fā)出數(shù)據(jù)包的比率,。
    歸一化路由開(kāi)銷：每發(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)銷
　由圖2可以看出，在不同的最大移動(dòng)速度下,，RP-AODV的路由開(kāi)銷最小,，總體上比AODV減低了40%。說(shuō)明通過(guò)新算法有效控制了鏈路中斷的次數(shù),，減小了路由發(fā)現(xiàn)的頻次,，從而降低了路由開(kāi)銷。在速度較低時(shí)路徑中斷的概率較小,，隨著速度的增加,，節(jié)點(diǎn)的移動(dòng)性增強(qiáng)，路徑中斷概率增大,，路由修復(fù)過(guò)程出現(xiàn)頻繁,，路由開(kāi)銷都有所增加，但是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)銷?？傮w上來(lái)看,，RP-AODV相比傳統(tǒng)AODV算法歸一化路由開(kāi)銷降低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)銷大,、時(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)銷的波及范圍。算法在經(jīng)典的AODV協(xié)議上實(shí)現(xiàn)(稱之為RP-AODV),，并用NS2模擬軟件進(jìn)行了仿真,。仿真結(jié)果表明,，在多種場(chǎng)景下新算法都降低了路由開(kāi)銷，有效地提高了網(wǎng)絡(luò)性能,，與傳統(tǒng)AODV相比控制開(kāi)銷降低了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.