基于鄰節(jié)點(diǎn)殘存率的AODV路由優(yōu)化算法

摘 要:針對AODV路由發(fā)現(xiàn)缺少路徑穩(wěn)定性考慮以及本地修復(fù)沒有避開不穩(wěn)定區(qū)域的缺陷，提出了基于鄰節(jié)點(diǎn)殘存率的AODV-NSR優(yōu)化算法。借助于鄰節(jié)點(diǎn)殘存率AODV-NSR對路由發(fā)現(xiàn)算法進(jìn)行優(yōu)化，使路徑穩(wěn)定性得以提高;借助于斷鏈責(zé)任檢測和數(shù)據(jù)搶救機(jī)制，AODV-NSR對本地修復(fù)算法進(jìn)行優(yōu)化，使本地修復(fù)盡可能避開不穩(wěn)定區(qū)域，從而降低二次斷鏈的幾率。仿真實(shí)驗(yàn)表明，AODV-NSR對Ad hoc網(wǎng)絡(luò)的性能有較為明顯的提高。

關(guān)鍵詞:Ad hoc網(wǎng)絡(luò);按需距離矢量路由;鄰節(jié)點(diǎn)殘存率;斷鏈責(zé)任檢測;數(shù)據(jù)搶救

中圖分類號:TP393.17 文獻(xiàn)標(biāo)志碼:A

文章編號:1001-3695(2010)03-1102-04

doi:10.3969/j.issn.1001-3695.2010.03.082

Improved AODV routing algorithms based on neighbor survival ratio

LIU Jin-ding1，YAN Han2

(1.College of Information Science Technology， Nanjing Agriculture University， Nanjing 210095 China;2.College of Computer Science Engineering， Nanjing University of Science Technology， Nanjing 210094， China)Abstract:In the traditional AODV routing protocol， the route discovery algorithm does not consider route’s stability， and the local repair algorithm does not avoid the instability regional around broken link.Aiming at the above-mentioned problems， the article proposed an improved AODV algorithm based on neighbor survival ratio (AODV-NSR).With neighbor survival ratio of node， AODV-NSR improved the route discovery algorithm and enhanced route’s stability. With broken link responsibility detecting and data rescue mechanisms， AODV-NSR improved the local repair algorithm and made repaired route avoid the instability regional at full steam， and so diminished the probability of broken link. The result of the simulation indicates that AODV-NSR protocol can reduce the end-to-end delay， routing overhead and enhance packet delivery rate.

Key words:Ad hoc network; AODV; neighbor survival ratio; broken link responsibility detection; data rescue

0 引言

Ad hoc網(wǎng)絡(luò)是無中心、節(jié)點(diǎn)可以自由移動(dòng)、拓?fù)浣Y(jié)構(gòu)不斷變化、多跳的自組網(wǎng)。網(wǎng)絡(luò)中節(jié)點(diǎn)充當(dāng)業(yè)務(wù)主機(jī)和路由器雙重角色，整個(gè)網(wǎng)絡(luò)不需要固定設(shè)施支持。作為移動(dòng)通信技術(shù)的重要分支，Ad hoc網(wǎng)絡(luò)在軍事戰(zhàn)場的快速展開和推進(jìn)、野外科考、抗震救災(zāi)等特殊環(huán)境中發(fā)揮了十分重要的作用。作為Ad hoc網(wǎng)絡(luò)研究的重要組成部分，路由協(xié)議已經(jīng)取得了一定成果，出現(xiàn)了不少典型路由協(xié)議，總體上可分為先驗(yàn)式和反應(yīng)式路由協(xié)議兩大類。先驗(yàn)式路由協(xié)議有DSDV(destination-sequenced distance-vector routing protocol)[1]、OLSR(optimized link state routing protocol)[2]等;反應(yīng)式路由協(xié)議有DSR(dynamic source routing)[3]、AODV(Ad hoc on-demand distance vector routing)[4]以及TORA (temporally-ordered routing algorithms)[5]。AODV作為Ad hoc網(wǎng)絡(luò)的一個(gè)典型反應(yīng)式路由協(xié)議，具有控制開銷低、帶寬開銷小等優(yōu)點(diǎn)。網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化是Ad hoc網(wǎng)絡(luò)的顯著特點(diǎn)，也是影響網(wǎng)絡(luò)路由協(xié)議性能的重要影響因素。AODV路由協(xié)議進(jìn)行路由發(fā)現(xiàn)時(shí)只進(jìn)行路由新鮮度和路由跳數(shù)比較，缺乏結(jié)合網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化對鏈路穩(wěn)定性、可用性不利影響的考慮。此外，AODV在檢測到斷鏈、啟動(dòng)本地修復(fù)時(shí)總是由斷鏈上游節(jié)點(diǎn)發(fā)起修復(fù)，沒有考慮避開不穩(wěn)定區(qū)域，導(dǎo)致修復(fù)后的路徑仍然始終包含斷鏈上游節(jié)點(diǎn)，在斷鏈上游節(jié)點(diǎn)比較活躍的情況下很有可能會很快再次產(chǎn)生斷鏈現(xiàn)象。文獻(xiàn)[6]提出基于信號強(qiáng)度變化來預(yù)測節(jié)點(diǎn)鏈路穩(wěn)定性的方法，這些預(yù)測方法需要底層協(xié)議的支持，實(shí)際設(shè)計(jì)時(shí)實(shí)現(xiàn)從底層獲取信號強(qiáng)度信息的難度較高。文獻(xiàn)[7]利用GPS全球定位系統(tǒng)提供節(jié)點(diǎn)位置和節(jié)點(diǎn)移動(dòng)速度信息以實(shí)現(xiàn)預(yù)測鏈路穩(wěn)定性，這種方法需要GPS硬件功能支持，導(dǎo)致節(jié)點(diǎn)的成本提高，節(jié)點(diǎn)構(gòu)造的復(fù)雜度增加。文獻(xiàn)[8]提出結(jié)合無線電波傳播規(guī)律以及節(jié)點(diǎn)移動(dòng)模型的鏈路預(yù)測方法，這種預(yù)測方法同樣需要硬件支持，而且沒有考慮節(jié)點(diǎn)在將來發(fā)生的變化，導(dǎo)致預(yù)測的準(zhǔn)確性下降。

針對上述研究工作的不足，設(shè)計(jì)了評價(jià)節(jié)點(diǎn)活躍程度的鄰節(jié)點(diǎn)殘存率數(shù)學(xué)模型，并借助鄰節(jié)點(diǎn)殘存率模型實(shí)現(xiàn)對AODV路由協(xié)議的優(yōu)化，提出了基于鄰節(jié)點(diǎn)殘存率的AODV路由協(xié)議優(yōu)化算法AODV-NSR(AODV based on neighbor survival ratio)。該優(yōu)化算法包含基于鄰節(jié)點(diǎn)殘存率的穩(wěn)定路徑選擇算法和本地避讓修復(fù)算法兩個(gè)部分。前部分優(yōu)化的目的是使得獲得的路徑穩(wěn)定性提高，后部分優(yōu)化的目的是使得修復(fù)后的路徑發(fā)生二次斷鏈的幾率下降。與文獻(xiàn)[6~8]相比，AODV-NSR優(yōu)化策略是建立在AODV的hello消息機(jī)制基礎(chǔ)上的，實(shí)現(xiàn)比較簡單，不需要硬件支持，節(jié)點(diǎn)構(gòu)成復(fù)雜性不高，成本較低。

1 AODV-NSR穩(wěn)定路徑選擇算法

1.1 鄰節(jié)點(diǎn)殘存率對路徑穩(wěn)定性的影響

依照文獻(xiàn)[9]，動(dòng)態(tài)拓?fù)涫且苿?dòng)自組網(wǎng)的主要特征，拓?fù)浣Y(jié)構(gòu)的動(dòng)態(tài)變化導(dǎo)致鏈路頻繁斷鏈，使得網(wǎng)絡(luò)性能下降、網(wǎng)絡(luò)規(guī)模擴(kuò)展受限，這正是Ad hoc網(wǎng)絡(luò)路由協(xié)議面臨的主要困難。AODV協(xié)議通過hello消息機(jī)制感知、管理與周圍鄰居節(jié)點(diǎn)之間的連接。如果近期某節(jié)點(diǎn)的鄰居節(jié)點(diǎn)丟失嚴(yán)重，那么表示此節(jié)點(diǎn)運(yùn)動(dòng)趨勢和周圍鄰居節(jié)點(diǎn)的運(yùn)動(dòng)趨勢不一致性程度較高。由于節(jié)點(diǎn)移動(dòng)并不是完全隨機(jī)的，往往具有一定目的性，節(jié)點(diǎn)運(yùn)動(dòng)趨勢往往會保持一段時(shí)間，路由發(fā)現(xiàn)時(shí)要盡量避開鄰居節(jié)點(diǎn)丟失嚴(yán)重的那些節(jié)點(diǎn)。因?yàn)閷τ谶@些節(jié)點(diǎn)而言，它們與周圍節(jié)點(diǎn)間不一致的運(yùn)動(dòng)將導(dǎo)致路徑斷鏈幾率大大提高。鄰節(jié)點(diǎn)殘存率是節(jié)點(diǎn)的鄰節(jié)點(diǎn)丟失程度的考查指標(biāo)，它對節(jié)點(diǎn)參與構(gòu)造通信路徑的合適程度具有參考意義。

1.2 鄰節(jié)點(diǎn)殘存率的定義

為了評價(jià)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)丟失程度，提出鄰節(jié)點(diǎn)殘存率的定義:

鄰節(jié)點(diǎn)殘存率(neighbor survival ratio，NSR)是指一段時(shí)間結(jié)束后仍然與當(dāng)前節(jié)點(diǎn)保持連接的鄰居節(jié)點(diǎn)個(gè)數(shù)和這段時(shí)間內(nèi)與當(dāng)前節(jié)點(diǎn)建立過連接的所有鄰居節(jié)點(diǎn)個(gè)數(shù)之比。節(jié)點(diǎn)A在t時(shí)刻的鄰節(jié)點(diǎn)殘存率可以表示為

NSRA_t=|SA_t|/|ALLSA_t|(1)

其中:NSRA_t表示t時(shí)刻節(jié)點(diǎn)A的鄰節(jié)點(diǎn)殘存率;|SA_t|表示在t時(shí)刻節(jié)點(diǎn)A的鄰節(jié)點(diǎn)列表中保持連接的節(jié)點(diǎn)個(gè)數(shù);|ALLSA_t|表示t時(shí)刻前一段時(shí)間周期T內(nèi)與節(jié)點(diǎn)A建立過連接的所有鄰居節(jié)點(diǎn)的個(gè)數(shù)。通過定義可知，SA_t是ALLSA_t的子集，NSRA_t是一個(gè)小于等于1的值。節(jié)點(diǎn)的鄰節(jié)點(diǎn)殘存率越小，則此節(jié)點(diǎn)導(dǎo)致鏈路斷鏈的可能性越高;反之則越低。

1.3 鄰節(jié)點(diǎn)殘存率獲取

AODV協(xié)議中，節(jié)點(diǎn)通過HelloTimer、NeighborTimer兩個(gè)定時(shí)器實(shí)現(xiàn)鄰節(jié)點(diǎn)的感知和管理。HelloTimer用于周期廣播hello消息，NeighborTimer用于周期管理鄰節(jié)點(diǎn)列表。要及時(shí)準(zhǔn)確獲得節(jié)點(diǎn)的鄰節(jié)點(diǎn)殘存率，同樣也需要設(shè)計(jì)一個(gè)鄰節(jié)點(diǎn)殘存率計(jì)算的定時(shí)器(NeighborSRTimer)，用這個(gè)定時(shí)器周期計(jì)算、更新節(jié)點(diǎn)的鄰節(jié)點(diǎn)殘存率。

根據(jù)鄰節(jié)點(diǎn)殘存率計(jì)算公式可知，NSR的分母部分為統(tǒng)計(jì)時(shí)間段內(nèi)出現(xiàn)的所有鄰節(jié)點(diǎn)個(gè)數(shù)。這些鄰節(jié)點(diǎn)是由統(tǒng)計(jì)時(shí)間段開始時(shí)鄰節(jié)點(diǎn)列表中的節(jié)點(diǎn)與統(tǒng)計(jì)時(shí)間段內(nèi)所有建立過連接的鄰節(jié)點(diǎn)兩部分構(gòu)成的，即使在統(tǒng)計(jì)時(shí)間段內(nèi)出現(xiàn)又消失的鄰居節(jié)點(diǎn)也應(yīng)該在統(tǒng)計(jì)范圍內(nèi)。為了統(tǒng)計(jì)所有出現(xiàn)的鄰節(jié)點(diǎn)，AODV-NSR需另外增加一個(gè)節(jié)點(diǎn)列表(allnb)用于收集出現(xiàn)過的鄰節(jié)點(diǎn)。統(tǒng)計(jì)時(shí)間段開始時(shí)從節(jié)點(diǎn)的鄰節(jié)點(diǎn)列表中復(fù)制節(jié)點(diǎn)到allnb中，然后在統(tǒng)計(jì)時(shí)間段內(nèi)，節(jié)點(diǎn)每次接收到hello消息時(shí)，除了正常更新鄰節(jié)點(diǎn)列表外，還要更新allnb列表用于登記鄰節(jié)點(diǎn)出現(xiàn)情況。NeighborSRTimer計(jì)時(shí)器計(jì)算NSR值時(shí)，可借助節(jié)點(diǎn)鄰節(jié)點(diǎn)列表和allnb列表來實(shí)現(xiàn)。在計(jì)算完NSR值之后，清空allnb，復(fù)制鄰節(jié)點(diǎn)列表中的節(jié)點(diǎn)到allnb列表中，進(jìn)入下一個(gè)統(tǒng)計(jì)周期。關(guān)于NeighborSRTimer計(jì)時(shí)周期設(shè)定，通過仿真比較的方式確定NeighborSRTimer計(jì)時(shí)周期為三個(gè)Hello_Interval時(shí)最優(yōu)。

1.4 穩(wěn)定路徑衡量標(biāo)準(zhǔn)

路徑穩(wěn)定性除了與節(jié)點(diǎn)自身運(yùn)動(dòng)趨勢相關(guān)，還與路徑的長度相關(guān)。通過以下的推理可以證明:

設(shè)路徑L由n個(gè)節(jié)點(diǎn)(node1，…，noden)構(gòu)成，其中包含有n-1個(gè)鏈路{(node1， node2)，(node2， node3)，…，(noden-1， noden)}，各個(gè)鏈路斷鏈概率分別為p1，p2，…，pn-1。只要路徑上任何一個(gè)鏈路斷鏈都會導(dǎo)致整個(gè)路徑斷裂，因此整個(gè)路徑斷裂的概率為

P(L)=1-n-1i=1(1-pi)(2)

路由發(fā)現(xiàn)時(shí)無法預(yù)知各個(gè)鏈路具體斷鏈幾率，但可以確定pi和1-pi肯定是小于1的，很容易得出P(L)是隨著節(jié)點(diǎn)的數(shù)量增加而增加的，也就是構(gòu)成路徑的跳數(shù)越多，整個(gè)路徑斷鏈幾率越大，整個(gè)路徑穩(wěn)定性越低。為了兼顧?quán)徆?jié)點(diǎn)殘存率和路徑長度對路徑穩(wěn)定性的影響，AODV-NSR采用路徑上的所有節(jié)點(diǎn)的鄰節(jié)點(diǎn)殘存率累乘積來評價(jià)通信路徑整體穩(wěn)定性，具體可以用式(3)表示為

NSRL=ni=1NSRi(3)

1.5 AODV-NSR穩(wěn)定路徑選擇算法

AODV-NSR路由發(fā)現(xiàn)過程與原始AODV路由發(fā)現(xiàn)過程追求的目標(biāo)不統(tǒng)一，它的路由發(fā)現(xiàn)要求獲得路徑NSR累乘積盡可能大的路徑，因此需要作如下的改動(dòng):

a)RREQ消息中攜帶它所經(jīng)過節(jié)點(diǎn)的NSR累乘積，這個(gè)累乘積反映了它所經(jīng)過路徑的穩(wěn)定程度。

b)中間節(jié)點(diǎn)不僅保存RREQ消息的廣播號，而且還應(yīng)該保存相同廣播號的RREQ消息帶來的最大NSR累乘積。

c)允許中間節(jié)點(diǎn)和目的節(jié)點(diǎn)多次接收相同RREQ請求，但是要求后轉(zhuǎn)發(fā)RREQ消息帶來的NSR累乘積比之前的大，這樣可以篩選出更為穩(wěn)定的路徑。

d)限制中間節(jié)點(diǎn)進(jìn)行路由應(yīng)答，保證每次RREQ請求都能夠獲得最穩(wěn)定的路徑。

AODV-NSR路由發(fā)現(xiàn)算法通過RREQ、RREP消息的產(chǎn)生、接收處理這幾個(gè)方面描述如下:

a)源節(jié)點(diǎn)在沒有到達(dá)目的節(jié)點(diǎn)路由時(shí)發(fā)起路由請求，源節(jié)點(diǎn)生成RREQ消息，并把自身NSR值添加到RREQ消息中，設(shè)置RREQ的其他相關(guān)參數(shù)(如跳數(shù)等)，然后廣播出去。

b)節(jié)點(diǎn)接收到RREQ消息后的處理如下:

(a)如果首次接收此RREQ消息，那么轉(zhuǎn)(b)，否則轉(zhuǎn)(c);

(b)提取RREQ消息中的廣播序列號和NSR值，保存到節(jié)點(diǎn)的廣播緩存區(qū)中，轉(zhuǎn)(e);

(c)如果當(dāng)前接收的RREQ消息攜帶NSR值比廣播緩存區(qū)中存儲的對應(yīng)相同廣播序列號的NSR值大，那么轉(zhuǎn)(d)，否則轉(zhuǎn)(i);

(d)用當(dāng)前接收的RREQ消息攜帶的NSR值修改廣播緩存區(qū)中存儲的對應(yīng)相同廣播序列號的NSR值，轉(zhuǎn)(e);

(e)把當(dāng)前節(jié)點(diǎn)自身的NSR值累乘到RREQ消息的NSR域中，設(shè)置RREQ消息的其他參數(shù)，轉(zhuǎn)(f);

(f)建立反向路由，轉(zhuǎn)(g);

(g)如果當(dāng)前節(jié)點(diǎn)為目的節(jié)點(diǎn)，生成并沿著反向路由廣播RREP消息，轉(zhuǎn)(i);否則轉(zhuǎn)(h);

(h)廣播RREQ消息，轉(zhuǎn)(i);

(i)結(jié)束。

c)目的節(jié)點(diǎn)收到RREQ消息且確定要進(jìn)行應(yīng)答時(shí)產(chǎn)生RREP消息(RREP消息結(jié)構(gòu)與原始AODV協(xié)議的RREP消息一致)，并把RREP消息沿著反向路由轉(zhuǎn)發(fā)到源節(jié)點(diǎn)，在轉(zhuǎn)發(fā)過程中建立正向路由。

d)節(jié)點(diǎn)接收到RREP消息后，如果不存在到達(dá)目的節(jié)點(diǎn)的正向路由，那么直接建立正向路由;如果存在到達(dá)目的節(jié)點(diǎn)的正向路由，那么在RREP消息的目的節(jié)點(diǎn)序列號大于等于路由中的目的節(jié)點(diǎn)序列號的情況下，不需要進(jìn)行跳數(shù)比較，直接進(jìn)行路由更新。

2 AODV-NSR本地避讓修復(fù)算法

2.1 本地避讓修復(fù)算法的提出

優(yōu)化的AODV本地修復(fù)算法以及文獻(xiàn)[10]提出的局部修復(fù)算法有著共同特性——縮小修復(fù)范圍。通過縮小修復(fù)范圍來減少因泛洪引起的網(wǎng)絡(luò)開銷增大;通過縮小修復(fù)范圍來縮短修復(fù)時(shí)間，減小端到端平均延時(shí)和數(shù)據(jù)分組丟失量。這些本地修復(fù)優(yōu)化策略仍存在一個(gè)缺陷:在本地修復(fù)時(shí)總是由斷鏈上游節(jié)點(diǎn)發(fā)起(即始終在斷鏈不穩(wěn)定區(qū)域內(nèi)發(fā)起)，這很有可能會因斷鏈上游節(jié)點(diǎn)過分活躍導(dǎo)致修復(fù)后的路徑很快再次斷鏈。如圖1所示，由于節(jié)點(diǎn)B的移動(dòng)導(dǎo)致BC鏈路斷鏈，經(jīng)過本地修復(fù)后，建立了替換路徑BMC。由于節(jié)點(diǎn)B比較活躍，其運(yùn)動(dòng)趨勢很有可能還會保持一段時(shí)間，這樣修復(fù)后的路徑可能會因?yàn)楣?jié)點(diǎn)B繼續(xù)移動(dòng)而導(dǎo)致AB間或者BM間的鏈路再次發(fā)生斷鏈。可見，發(fā)起本地修復(fù)時(shí)有必要評價(jià)斷鏈上游節(jié)點(diǎn)的活躍程度，在斷鏈上游節(jié)點(diǎn)活躍程度較高的情況下，有必要避開斷鏈上游節(jié)點(diǎn)由其前驅(qū)節(jié)點(diǎn)發(fā)起本地修復(fù)，這樣就可以減小二次斷鏈的幾率。

2.2 斷鏈責(zé)任檢測機(jī)制

在斷鏈上游節(jié)點(diǎn)檢測到斷鏈時(shí)，如果自身NSR值比選定的閾值大，則由斷鏈上游節(jié)點(diǎn)直接發(fā)起本地修復(fù);如果自身NSR值比選定的閾值小，那么斷鏈上游節(jié)點(diǎn)認(rèn)定斷鏈的責(zé)任者很有可能是自己，因此需采取本地避讓修復(fù)算法，即通知其前驅(qū)節(jié)點(diǎn)發(fā)起本地修復(fù)，同時(shí)對自己緩存的數(shù)據(jù)分組進(jìn)行搶救。

節(jié)點(diǎn)的NSR值會隨著不同特性的網(wǎng)絡(luò)環(huán)境而改變，如果網(wǎng)絡(luò)整體的活躍程度比較高，那么每個(gè)節(jié)點(diǎn)的NSR值就比較小;如果網(wǎng)絡(luò)整體的活躍程度比較低，那么每個(gè)節(jié)點(diǎn)的NSR值就比較大，因此難以選定一個(gè)確定的NSR閾值。AODV-NSR選擇了相對比較方法，即斷鏈上游節(jié)點(diǎn)用自己的NSR值與它所有鄰居節(jié)點(diǎn)NSR的平均值進(jìn)行比較。這樣做的原因在于斷鏈上游節(jié)點(diǎn)與鄰節(jié)點(diǎn)靠得比較近，它們之間有許多共同覆蓋區(qū)域，具有一定的可比性。

獲得鄰節(jié)點(diǎn)的NSR值實(shí)現(xiàn)起來還是比較簡單的，節(jié)點(diǎn)可以在廣播hello消息時(shí)攜帶自己的NSR值，從而可以使鄰居節(jié)點(diǎn)能夠及時(shí)獲得自己的NSR值。

2.3 數(shù)據(jù)搶救機(jī)制

2.3.1 AODV本地修復(fù)的數(shù)據(jù)搶救處理

斷鏈上游節(jié)點(diǎn)檢測出斷鏈且確定發(fā)起本地修復(fù)時(shí)，斷鏈上游節(jié)點(diǎn)會把發(fā)送隊(duì)列中相關(guān)數(shù)據(jù)分組轉(zhuǎn)移到等待路由隊(duì)列中。在本地修復(fù)過程中斷鏈上游節(jié)點(diǎn)會繼續(xù)接收前驅(qū)節(jié)點(diǎn)發(fā)來的數(shù)據(jù)分組并緩存到等待路由隊(duì)列中，本地修復(fù)成功后，斷鏈上游節(jié)點(diǎn)將獲得到達(dá)目的節(jié)點(diǎn)的路由。在路由管理機(jī)制的支持下，斷鏈上游節(jié)點(diǎn)將自動(dòng)用新獲得的路由發(fā)送等待路由隊(duì)列中的相關(guān)數(shù)據(jù)分組，這樣，斷鏈上游節(jié)點(diǎn)中緩存的數(shù)據(jù)分組就得以搶救。如果本地修復(fù)不成功，斷鏈上游節(jié)點(diǎn)將丟棄緩存的數(shù)據(jù)分組，通知源節(jié)點(diǎn)發(fā)起修復(fù)(即重新路由發(fā)現(xiàn))。

2.3.2 本地避讓修復(fù)的數(shù)據(jù)搶救處理

如果斷鏈上游節(jié)點(diǎn)檢測出自身活躍度較高(NSR值低于其鄰居節(jié)點(diǎn)NSR平均值)，那么斷鏈上游節(jié)點(diǎn)將采用避讓策略通知其前驅(qū)節(jié)點(diǎn)發(fā)起本地修復(fù)，目的是使得修復(fù)后的路徑盡可能避開斷鏈上游節(jié)點(diǎn)。修復(fù)有三種不同結(jié)果，具體處理如下:

a)路徑修復(fù)不成功。路徑修復(fù)不成功，丟棄緩存的數(shù)據(jù)分組，緩存的數(shù)據(jù)分組不予搶救，通知源節(jié)點(diǎn)發(fā)起修復(fù)。這種處理與原始本地修復(fù)一致，不需要另外處理。

b)修復(fù)后的路徑仍然經(jīng)過斷鏈上游節(jié)點(diǎn)。斷鏈上游節(jié)點(diǎn)仍在修復(fù)后的路徑上，所以它必定有到達(dá)目的節(jié)點(diǎn)的有效路由，緩存的數(shù)據(jù)分組會自動(dòng)得到搶救。這種情況也不需要另外處理。

c)修復(fù)后的路徑不經(jīng)過斷鏈上游節(jié)點(diǎn)。斷鏈上游節(jié)點(diǎn)不在修復(fù)后的路徑上，它沒有到達(dá)目的節(jié)點(diǎn)的有效路由，緩存的數(shù)據(jù)分組需要搶救。要對斷鏈上游節(jié)點(diǎn)中數(shù)據(jù)分組搶救，只要在斷鏈上游節(jié)點(diǎn)中建立到達(dá)目的節(jié)點(diǎn)的路由即可，利用路由管理機(jī)制可以實(shí)現(xiàn)。要想讓斷鏈上游節(jié)點(diǎn)建立到達(dá)目的節(jié)點(diǎn)的路由，只需斷鏈上游節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)把RREP消息轉(zhuǎn)發(fā)一份給斷鏈上游節(jié)點(diǎn)即可。斷鏈上游節(jié)點(diǎn)處理RREP消息時(shí)，將建立到達(dá)目的節(jié)點(diǎn)的路由，這樣緩存的數(shù)據(jù)分組就可以重新回到通信路徑上了。

通過分析可知，要搶救斷鏈上游節(jié)點(diǎn)中數(shù)據(jù)分組必須要實(shí)現(xiàn)以下幾個(gè)功能:a)斷鏈上游節(jié)點(diǎn)能夠通知其前驅(qū)節(jié)點(diǎn)發(fā)起本地修復(fù);b)斷鏈上游節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)能夠區(qū)別是由自己主動(dòng)發(fā)起修復(fù)還是由斷鏈上游節(jié)點(diǎn)要求發(fā)起修復(fù);c)斷鏈上游節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)在修復(fù)路徑完成時(shí)能夠辨別是否要搶救斷鏈上游節(jié)點(diǎn)中的數(shù)據(jù)分組，即是否需要轉(zhuǎn)發(fā)RREP消息給斷鏈上游節(jié)點(diǎn)。

2.3.3 本地避讓修復(fù)中的數(shù)據(jù)搶救機(jī)制實(shí)現(xiàn)

本地避讓修復(fù)算法的數(shù)據(jù)搶救機(jī)制主要涉及三個(gè)方面，即斷鏈上游節(jié)點(diǎn)通知前驅(qū)節(jié)點(diǎn)發(fā)起修復(fù)(發(fā)送notice消息)的處理、節(jié)點(diǎn)收到notice通知后的處理、節(jié)點(diǎn)接收到RREP消息的處理。下面對這三個(gè)部分進(jìn)行詳細(xì)闡述。

1)斷鏈上游節(jié)點(diǎn)確定通知前驅(qū)節(jié)點(diǎn)發(fā)起修復(fù)處理過程

a)設(shè)置到達(dá)目的節(jié)點(diǎn)路由狀態(tài)為修復(fù)狀態(tài)，但不需要發(fā)送RREQ請求。

b)生成notice消息，其中登記斷鏈路由的目的節(jié)點(diǎn)地址以及此路由的前驅(qū)節(jié)點(diǎn)矩陣，一跳范圍內(nèi)廣播notice消息。

c)清空斷鏈路由的前驅(qū)節(jié)點(diǎn)列表，目的是修復(fù)不成功時(shí)不再生成RERR消息通知源節(jié)點(diǎn)，而是由其前驅(qū)節(jié)點(diǎn)通知源節(jié)點(diǎn)。

d)設(shè)定定時(shí)器，用于處理修復(fù)不成功時(shí)數(shù)據(jù)分組釋放。

e)結(jié)束。

2)節(jié)點(diǎn)收到notice消息時(shí)的處理過程

a)根據(jù)notice消息，判斷當(dāng)前節(jié)點(diǎn)是否為斷鏈上游節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，如果不是，則轉(zhuǎn)g)。

b)設(shè)置到達(dá)目的節(jié)點(diǎn)的路由狀態(tài)為修復(fù)狀態(tài)。

c)提取發(fā)送隊(duì)列中相關(guān)數(shù)據(jù)分組到等待路由隊(duì)列中。

d)給到達(dá)目的節(jié)點(diǎn)的路由前驅(qū)節(jié)點(diǎn)列表增加一個(gè)前驅(qū)節(jié)點(diǎn)，此前驅(qū)節(jié)點(diǎn)就是notice消息發(fā)送者，即斷鏈上游節(jié)點(diǎn)，此節(jié)點(diǎn)同時(shí)也應(yīng)該是到達(dá)目的節(jié)點(diǎn)路由的下一跳節(jié)點(diǎn)(目的是標(biāo)志要求發(fā)起本地修復(fù)不是自己)。

e)生成并廣播RREQ消息，發(fā)起本地修復(fù)。

f)設(shè)定定時(shí)器，用于處理修復(fù)不成功時(shí)數(shù)據(jù)釋放和通知源節(jié)點(diǎn)。

g)結(jié)束。

3)節(jié)點(diǎn)接收到RREP消息后的處理過程

a)如果到達(dá)目的節(jié)點(diǎn)的路由的下一跳沒有出現(xiàn)在路由的前驅(qū)節(jié)點(diǎn)列表中，那么說明RREP消息還沒有到達(dá)斷鏈上游節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，此時(shí)直接按照正常接收RREP消息處理方式處理，轉(zhuǎn)d)。

b)如果RREP消息已經(jīng)到達(dá)了原路徑斷鏈上游節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，那么判斷RREP消息的轉(zhuǎn)發(fā)節(jié)點(diǎn)是否與到達(dá)目的節(jié)點(diǎn)路由的下一跳相同，即判斷修復(fù)后路徑是否經(jīng)過斷鏈上游節(jié)點(diǎn):(a)如果經(jīng)過斷鏈上游節(jié)點(diǎn)，則不用考慮數(shù)據(jù)搶救的問題，直接轉(zhuǎn)c);(b)如果不經(jīng)過斷鏈上游節(jié)點(diǎn)， 則需要通知斷鏈上游節(jié)點(diǎn)建立到達(dá)其前驅(qū)節(jié)點(diǎn)路由，以實(shí)現(xiàn)數(shù)據(jù)分組的搶救。具體操作步驟為:復(fù)制一個(gè)RREP消息，修改復(fù)制來的RREP消息的ih→daddr()為路由的下一跳節(jié)點(diǎn)，即原路徑的斷鏈上游節(jié)點(diǎn)。修改的目的是使得斷鏈上游節(jié)點(diǎn)接收RREP后不再轉(zhuǎn)發(fā)RREP;把修改后的RREP消息發(fā)送給斷鏈上游節(jié)點(diǎn)。

c)消除要求搶救數(shù)據(jù)分組的標(biāo)志，即在路由的前驅(qū)節(jié)點(diǎn)列表中刪除路由下一跳節(jié)點(diǎn)地址。

d)根據(jù)RREP消息更新到達(dá)目的節(jié)點(diǎn)的正向路由。

e)如果RREP消息的目的地址(即IP頭的ih→daddr())與當(dāng)前節(jié)點(diǎn)相等，那么釋放RREP消息，轉(zhuǎn)g)。

f)尋找到達(dá)RREP消息的目的地址的反向路由，按照此反向路由轉(zhuǎn)發(fā)RREP消息。

g)結(jié)束。

2.4 AODV-NSR本地避讓修復(fù)算法

本地避讓修復(fù)算法核心思想是本地修復(fù)盡可能避開斷鏈所處的不穩(wěn)定區(qū)域，使得修復(fù)后路徑二次斷鏈的幾率降低。為了減少避讓的盲目性，在AODV-NSR本地避讓修復(fù)算法中引入了斷鏈責(zé)任檢測機(jī)制。修復(fù)后的路徑有可能不再經(jīng)過斷鏈上游節(jié)點(diǎn)，需對斷鏈上游節(jié)點(diǎn)中緩存的相關(guān)數(shù)據(jù)分組進(jìn)行搶救，因此引入了數(shù)據(jù)搶救機(jī)制。AODV-NSR本地避讓修復(fù)算法完整描述如下:斷鏈出現(xiàn)時(shí)，斷鏈上游節(jié)點(diǎn)首先判斷斷鏈位置是否離目的節(jié)點(diǎn)比較近(斷鏈位置到目的節(jié)點(diǎn)的跳數(shù)小于到源節(jié)點(diǎn)的跳數(shù))，如果離目的節(jié)點(diǎn)比較遠(yuǎn)，那么丟棄緩存的數(shù)據(jù)分組，立即廣播RERR消息，通知源節(jié)點(diǎn)重新發(fā)起路由請求;否則進(jìn)入本地避讓修復(fù)。在本地避讓修復(fù)過程中，斷鏈上游節(jié)點(diǎn)首先設(shè)置當(dāng)前到達(dá)目的節(jié)點(diǎn)的路由為修復(fù)狀態(tài)，然后借助斷鏈責(zé)任檢測機(jī)制判斷斷鏈上游節(jié)點(diǎn)是否為斷鏈責(zé)任者。如果不是斷鏈責(zé)任者，它將立即發(fā)起本地修復(fù)，本地修復(fù)尋找路由仍然采用基于鄰節(jié)點(diǎn)殘存率的穩(wěn)定路徑選擇算法;如果斷鏈上游節(jié)點(diǎn)是斷鏈責(zé)任者，那么通知其前驅(qū)節(jié)點(diǎn)發(fā)起本地修復(fù)(生成并廣播notice消息)并設(shè)置修復(fù)計(jì)時(shí)器，用于處理修復(fù)不成功時(shí)緩存數(shù)據(jù)分組的釋放以及通知源節(jié)點(diǎn)修復(fù)等相關(guān)問題處理。在數(shù)據(jù)搶救機(jī)制的支持下，如果路徑修復(fù)成功，那么斷鏈上游節(jié)點(diǎn)中緩存的數(shù)據(jù)分組將得以搶救。

3 仿真實(shí)驗(yàn)

3.1 仿真環(huán)境及評價(jià)指標(biāo)說明

本仿真實(shí)驗(yàn)的目的是為了比較AODV-NSR和原始AODV路由協(xié)議的性能，仿真采用NS 2.30。50個(gè)節(jié)點(diǎn)在1 000 m×1 000 m的區(qū)域內(nèi)隨機(jī)移動(dòng)，采用的是way-point移動(dòng)模型。AODV和AODV-NSR的等待路由緩沖隊(duì)列大小為64個(gè)分組，發(fā)送等待隊(duì)列為50個(gè)分組。MAC層采用IEEE 802.11 DCF，傳輸速率為2 Mbps，節(jié)點(diǎn)發(fā)送范圍為250 m。節(jié)點(diǎn)移動(dòng)模型采用隨機(jī)移動(dòng)模型:每個(gè)節(jié)點(diǎn)停留預(yù)設(shè)停滯時(shí)間后，在規(guī)定的移動(dòng)區(qū)域內(nèi)隨機(jī)選擇一個(gè)目的位置，然后在[0，maxspeed]速度區(qū)間內(nèi)隨機(jī)選擇一個(gè)速度，按該速度恒定移向目的位置，節(jié)點(diǎn)到達(dá)目的位置后停留預(yù)設(shè)停滯時(shí)間，然后重新選擇新的目的位置和移動(dòng)速度，如此反復(fù)。實(shí)驗(yàn)按照不同的停滯時(shí)間共設(shè)計(jì)了六種移動(dòng)場景進(jìn)行模擬。為了防止實(shí)驗(yàn)中的偶然性，對每種移動(dòng)場景實(shí)驗(yàn)五次，然后取平均值進(jìn)行分析比較。

仿真結(jié)果選擇端到端平均延遲、數(shù)據(jù)分組投遞率、標(biāo)準(zhǔn)路由負(fù)載三個(gè)方面指標(biāo)進(jìn)行比較分析。端到端平均延遲是指所有目的節(jié)點(diǎn)接收到分組時(shí)間與該分組發(fā)送時(shí)間差的平均值;數(shù)據(jù)分組投遞率是指目的節(jié)點(diǎn)接收分組的個(gè)數(shù)與源節(jié)點(diǎn)發(fā)送分組的個(gè)數(shù)的比值;標(biāo)準(zhǔn)路由負(fù)載是指每交付一個(gè)數(shù)據(jù)分組所需要發(fā)送的路由控制分組的數(shù)量，控制分組包括RREQ消息、RREP消息、hello消息以及notice消息。

3.2 仿真結(jié)果及性能分析

實(shí)驗(yàn)結(jié)果如圖2～4所示。從圖2、3中可以看出，AODV-NSR協(xié)議的數(shù)據(jù)分組投遞率、端到端平均延遲有明顯改善，尤其在停滯時(shí)間較短的情況下改善的效果更為明顯。這是因?yàn)锳ODV-NSR采用了穩(wěn)定路徑選擇算法以及本地避讓修復(fù)算法，有效地減少斷鏈次數(shù)實(shí)現(xiàn)了網(wǎng)絡(luò)性能的改善。由于不允許中間節(jié)點(diǎn)對路由請求進(jìn)行應(yīng)答以及允許中間節(jié)點(diǎn)、目的節(jié)點(diǎn)有條件地對RREQ消息進(jìn)行重復(fù)處理，導(dǎo)致路由請求階段控制消息數(shù)量有所增加。因此AODV-NSR標(biāo)準(zhǔn)路由負(fù)載改善的效果不是很明顯。但從整體而言，AODV-NSR的網(wǎng)絡(luò)性能還是優(yōu)于傳統(tǒng)AODV協(xié)議的。

4 結(jié)束語

AODV-NSR是建立在鄰節(jié)點(diǎn)殘存率基礎(chǔ)上的AODV優(yōu)化算法，不需要額外硬件支持，對AODV協(xié)議整體改動(dòng)不大，只增加了一個(gè)notice控制消息，基本保持了AODV對各種控制消息整體處理規(guī)則。AODV-NSR的本地避讓修復(fù)算法沒有另起爐灶，而是建立在穩(wěn)定路徑選擇算法基礎(chǔ)上的(否則也不能實(shí)現(xiàn)避讓的效果)，路由發(fā)現(xiàn)和本地修復(fù)保持了兼容性和延續(xù)性。仿真表明，AODV-NSR與AODV相比，在標(biāo)準(zhǔn)路由負(fù)載、端到端平均延遲以及數(shù)據(jù)分組投遞率等幾個(gè)方面性能上都有所改善。下一步研究工作主要是在負(fù)載均衡、安全方面的考慮，以期形成更為穩(wěn)定、安全的路由協(xié)議。

參考文獻(xiàn):

[1]

PERKINS C E，BHAGWAT P. Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers[J].Computer Communication Review，1994，24(4):234-244.

[2]CLAUSEN T，JACQUET P. RFC 3626，optimized link state routing protocol (OLSR)[S].2003.

[3]PERKINS C E， ROYER E M. Ad hoc on-demand distance vectorrouting[C]//Proc of the 2nd IEEE Workshop on Mobile Computing Systems and Applications.1999:90-100.

[4]JOHNSON D B，MALTZ D A.Dynamic source routing in Ad hoc wireless networks[M].New York:Kluwer Academic Publishers，1996.

[5]PARK V D，CORSON S M.A highly adaptive distributed routing algorithm for mobile wireless networks[C]//Proc of the 16th Conference on Computer and Communications Societies.1997:1405-1413.

[6]PAUL K，BANDYOPADHYAY S， MUKHERJEE A，et al. Communication aware mobile hosts in Ad hoc wireless networks[C]//Proc of Conference on Personal Wireless Communication.1999:83-87.

[7]SU W，GERLA M.IPv6 flow handoff in Ad hoc wireless networks using mobility prediction[C]//Proc of Global Telecommunications Conference.1999:271-275.

[8]年梅，王能.通過鏈路實(shí)效預(yù)測機(jī)制提高AODV協(xié)議的性能[J].計(jì)算機(jī)應(yīng)用，2005，25(6):1251-1256.

[9]PERKINS C E，ROYER E M，DAS S R，et al.Performance comparison of two on-demand routing protocols for Ad hoc networks[J].Personal Communications，2001，8(1):16-28.

[10]肖百龍，郭偉，劉軍，等.移動(dòng)自組網(wǎng)路由局部修復(fù)算法研究[J].計(jì)算機(jī)研究與發(fā)展，2007，44(8):1383-1389.