范青剛，葉雪梅，蔡艷寧，朱云杰

(第二炮兵工程大學(xué) 理學(xué)院，陜西 西安710025)

當(dāng)前廣泛應(yīng)用的網(wǎng)絡(luò)(如GSM、CDMA等)均需固定的網(wǎng)絡(luò)基礎(chǔ)設(shè)施支持。移動自組網(wǎng)(Mobile Ad Hoc Network，MANET)是一種與上述通信類型不同的無線網(wǎng)絡(luò)。是一個多跳的臨時性無中心網(wǎng)絡(luò)，由一組帶有無線收發(fā)裝置的移動節(jié)點(diǎn)組成，該網(wǎng)絡(luò)能夠隨時隨地快速搭建，且無需網(wǎng)絡(luò)基礎(chǔ)設(shè)施的支持。其具有特點(diǎn)如下［1］:(1)拓?fù)浣Y(jié)構(gòu)動態(tài)變化。由于網(wǎng)絡(luò)節(jié)點(diǎn)的自由移動、隨時開關(guān)機(jī)以及收發(fā)裝置功率的變化等，各節(jié)點(diǎn)間通過無線信道形成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)也可能隨時發(fā)生變化，且不可預(yù)測。(2)自組織性。該網(wǎng)絡(luò)沒有中心，所有節(jié)點(diǎn)可自由移動，地位平等，是一個對等式網(wǎng)絡(luò)。所有節(jié)點(diǎn)都可以隨時加入或離開網(wǎng)絡(luò)，任何節(jié)點(diǎn)的故障均不會影響整個網(wǎng)絡(luò)的運(yùn)行。(3)多跳組網(wǎng)方式。網(wǎng)絡(luò)中的節(jié)點(diǎn)除了具有普通移動終端所需的功能外，還具有報文轉(zhuǎn)發(fā)能力。當(dāng)通信的源節(jié)點(diǎn)和目的節(jié)點(diǎn)相距較遠(yuǎn)，不在直接通信的范圍內(nèi)時，可借助中間節(jié)點(diǎn)通過轉(zhuǎn)發(fā)報文進(jìn)行通信。

1 MANET與傳統(tǒng)無線網(wǎng)絡(luò)在路由上的區(qū)別

目前生活中常見的移動通信網(wǎng)絡(luò)主要有蜂窩數(shù)據(jù)網(wǎng)絡(luò)和無線局域網(wǎng)，在系統(tǒng)的組織、管理和維護(hù)方面都與MANET有較大的區(qū)別［2］。

1.1 MANET與蜂窩數(shù)據(jù)網(wǎng)絡(luò)的區(qū)別

典型的蜂窩數(shù)據(jù)網(wǎng)有全球移動通信(Global System for Mobile communication，GSM)網(wǎng)絡(luò) 和碼分多址(Code Division Multiple Access，CDMA)網(wǎng)絡(luò)，網(wǎng)絡(luò)中的移動節(jié)點(diǎn)主要通過基站進(jìn)行連接，基站之間通過有線網(wǎng)絡(luò)進(jìn)行互聯(lián)，因此移動節(jié)點(diǎn)之間通信路由的建立或選擇主要由基站等固定基礎(chǔ)設(shè)施完成。而在MANET中，不存在固定基礎(chǔ)設(shè)施，節(jié)點(diǎn)通信路由的選擇和建立完全由移動節(jié)點(diǎn)完成。在蜂窩數(shù)據(jù)網(wǎng)中，由于有網(wǎng)絡(luò)固定基礎(chǔ)設(shè)施的存在，網(wǎng)絡(luò)結(jié)構(gòu)相對較為穩(wěn)定。而在MANET中，節(jié)點(diǎn)的隨意移動會使得網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動態(tài)變化，影響通信路由的選擇。

1.2 MANET與無線局域網(wǎng)的區(qū)別

無線局域網(wǎng)中的節(jié)點(diǎn)通過無線接入點(diǎn)連接到網(wǎng)絡(luò)，是單跳的網(wǎng)絡(luò)，路由器和主機(jī)通常是兩個獨(dú)立的設(shè)備。而MANET是多跳的網(wǎng)絡(luò)，每個節(jié)點(diǎn)均同時具備路由和主機(jī)兩種功能。通過比較發(fā)現(xiàn)，MANET與傳統(tǒng)的無線網(wǎng)絡(luò)在路由方面有較大差異，因此路由協(xié)議是MANET研究的重點(diǎn)內(nèi)容。

2 MANET路由協(xié)議分類

MANET的路由協(xié)議可基于不同角度進(jìn)行分類［1，3］，如按路徑類型可分為單路徑型路由協(xié)議和多路徑型路由協(xié)議，按廣播方式可分為單播路由協(xié)議和多播路由協(xié)議，按地理定位方式可分為地理定位輔助路由協(xié)議和非地理定位輔助路由協(xié)議，而最常見的分類方式有以下兩種:(1)按網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分類。從這個角度可分為平面結(jié)構(gòu)和分層結(jié)構(gòu)兩種。對于前者，所有移動節(jié)點(diǎn)地位平等，如動態(tài)源路由協(xié)議(Dynamic Source Routing，DSR)。對于后者，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)按簇劃分，每個簇由一個簇頭和若干個簇成員組成，多個簇頭又是更高一級簇的成員。(2)按驅(qū)動方式分類?？煞譃楸眚?qū)動和按需驅(qū)動兩種，例如圖1所示。前者采用周期性的路由分組廣播來交換路由信息，如目的序號距離矢量路由協(xié)議(DSDV);后者則是根據(jù)發(fā)送數(shù)據(jù)分組需要進(jìn)行路由發(fā)現(xiàn)，建立路徑，實(shí)現(xiàn)信息傳送。如需求驅(qū)動距離矢量路由協(xié)議(Ad Hoc Ondemand Distance Vector，AODV)和臨時排序路由選擇算法(Temporary Ordered Routing Algorithm，TORA)協(xié)議。

圖1 MANET路由協(xié)議

3 典型的MANET路由協(xié)議

文中選取DSDV作為表驅(qū)動路由協(xié)議的代表重點(diǎn)介紹;選取AODV、DSR作為按需路由協(xié)議的代表并作重點(diǎn)介紹。

3.1 DSDV協(xié)議

DSDV是一種基于距離矢量算法的路由協(xié)議［4］，通過附加序列號的方法來區(qū)分路由的新舊程度，進(jìn)而防止可能產(chǎn)生的路由環(huán)路。(1)路由表結(jié)構(gòu)。每個節(jié)點(diǎn)包含一個路由表，路由表項包括:目的信宿、下一跳、度量值和序列號。(2)信息通告。各個節(jié)點(diǎn)周期性地向鄰居節(jié)點(diǎn)通告其當(dāng)前的路由表。(3)鏈路斷開。如果在較長一段時間內(nèi)無法收到鄰居節(jié)點(diǎn)的廣播消息，可推斷出鏈路斷開，同時，MAC層實(shí)體也可檢測到。一旦鏈路斷開，則通過以下方法通知網(wǎng)絡(luò)中其余節(jié)點(diǎn):1)斷開的鏈路度量值為∞。2)節(jié)點(diǎn)檢測路由表，下一跳經(jīng)過該鏈路的路由表項的度量值標(biāo)記為∞，并分配一個新的序列號，且為奇數(shù)，以區(qū)別于信宿發(fā)出的更新報文。3)觸發(fā)“遞增更新”報文的立即發(fā)送。經(jīng)過以上過程，在較短時間內(nèi)，該鏈路的變化將通告到網(wǎng)絡(luò)的各個節(jié)點(diǎn)。(4)路由選擇準(zhǔn)則。DSDV中路由選擇的準(zhǔn)則為:序列號新或度量值小。

DSDV協(xié)議操作實(shí)例:在圖2及表1表2中，MHi(i=1，2，…，8)表示節(jié)點(diǎn)標(biāo)識，SXXX_MHi(i=1，2，…，8)發(fā)出更新報文的序列號為XXX。以MH2為例，當(dāng)MH1移動，成為MH7的鄰居時，MH1與MH3的鏈路斷開。表1和表2分別為MH1移動前和移動后MH2的路由。

圖2 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)及變化情況

表1 MH1移動之前MH2節(jié)點(diǎn)的路由表

表2 MH1移動之后MH2節(jié)點(diǎn)的路由表

3.2 AODV協(xié)議

AODV路由協(xié)議［5］是按需驅(qū)動的距離矢量路由協(xié)議，使用目的序列號和經(jīng)典的距離矢量算法，具有對動態(tài)鏈路的快速自適應(yīng)，處理和存儲開銷小，網(wǎng)絡(luò)利用率小等優(yōu)點(diǎn)。AODV路由協(xié)議最明顯的特征是每條路由均使用一個目的節(jié)點(diǎn)序列號，能夠確保路由是開環(huán)的。該序列號由目的節(jié)點(diǎn)產(chǎn)生，與發(fā)送給路由請求節(jié)點(diǎn)的信息相組合。協(xié)議由兩部分組成:路由請求和路由維護(hù)。

AODV的路由請求(RREQ)包含下列項［6］:

＜跳數(shù);路由請求碼;目的地址;目的序列號;源地址;源序列號＞

收到請求報文的節(jié)點(diǎn)，查看路由表中是否有到目的節(jié)點(diǎn)更新的路由，即目的序列號大于等于請求報文中的序列號。若沒有，該節(jié)點(diǎn)將記錄請求報文的信息并廣播;若有或節(jié)點(diǎn)是目的節(jié)點(diǎn)，則將發(fā)送路由應(yīng)答報文(RREP)給源節(jié)點(diǎn)。RREP包含如下項:

＜跳數(shù);目的地址;目的序列號;源地址;壽命＞

轉(zhuǎn)發(fā)RREP的節(jié)點(diǎn)根據(jù)RREP更新路由表，并將RREP轉(zhuǎn)發(fā)給先前記錄的上游節(jié)點(diǎn)，直至源節(jié)點(diǎn)S，此時由源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路由已建立。

AODV通過周期性的廣播Hello報文來監(jiān)視鏈路狀態(tài)［7］，若節(jié)點(diǎn)在使用過程中發(fā)現(xiàn)某條鏈路斷開，則將從自身的路由表中刪除包含該鏈路的路由，并發(fā)送“路由出錯”報文(RERR)給因鏈路斷開而不可達(dá)的節(jié)點(diǎn)，沿途轉(zhuǎn)發(fā)RERR的節(jié)點(diǎn)并同時刪除自身路由表中的對應(yīng)路由。如圖3所示，節(jié)點(diǎn)6為目的節(jié)點(diǎn)，由于節(jié)點(diǎn)4從4處移動到4'處，導(dǎo)致節(jié)點(diǎn)3到目標(biāo)節(jié)點(diǎn)的鏈路中斷。圖3(a)所示為RERR通知過程，圖3(b)所示為重新建立的路由。

圖3 AODV協(xié)議路由維護(hù)過程

3.3 DSR協(xié)議

DSR是動態(tài)源路由協(xié)議［7－8］，其最重要的特點(diǎn)是利用了源路由，即發(fā)送方知道到達(dá)目的地的完整路徑，可實(shí)現(xiàn)節(jié)點(diǎn)間跨越多跳傳輸空間進(jìn)行通信。DSR路由協(xié)議包括路由尋找和路由維護(hù)兩個主要機(jī)制，共同作用于移動Ad Hoc網(wǎng)絡(luò)，完成源路由的尋找和維護(hù)。

(1)路由尋找。當(dāng)節(jié)點(diǎn)S有分組要發(fā)送至節(jié)點(diǎn)D，而S并未找到任何可用的路由，那么節(jié)點(diǎn)S就通過路由尋找協(xié)議來動態(tài)的尋找一條可達(dá)節(jié)點(diǎn)D的新路由。如圖4所示，源節(jié)點(diǎn)S試圖尋找一條路由到達(dá)目的節(jié)點(diǎn)D。

圖4 路由尋找

節(jié)點(diǎn)S的路由尋找進(jìn)程執(zhí)行如下:1)節(jié)點(diǎn)S按照本地廣播分組方式發(fā)送路由請求(RREQ)，被當(dāng)前正處在節(jié)點(diǎn)S的無線電波覆蓋范圍的所有節(jié)點(diǎn)所接受，如節(jié)點(diǎn)A。RREQ識別路由尋找的源節(jié)點(diǎn)和目的節(jié)點(diǎn)，也包含了由源節(jié)點(diǎn)確定的唯一請求識別碼(Request ID)。RREQ還包含一個記錄列表，用于記錄該RREQ被成功轉(zhuǎn)發(fā)的中間節(jié)點(diǎn)。2)當(dāng)另一個節(jié)點(diǎn)接收到該RREQ時，若該節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)，則給源節(jié)點(diǎn)回送一個路由應(yīng)答(RREP)，同時回送在路由尋找過程中的路由記錄，源節(jié)點(diǎn)接受到該RREP后，存儲該路信息。否則，若接受到該RREQ的節(jié)點(diǎn)已經(jīng)收到另一個來自相同源節(jié)點(diǎn)、具有相同請求識別碼和目標(biāo)節(jié)點(diǎn)的RREQ，或該節(jié)點(diǎn)已經(jīng)發(fā)現(xiàn)自己的地址已在該RREQ的路由記錄中，那么該節(jié)點(diǎn)認(rèn)為該路由請求已被接受，即丟掉該路由請求;否則該節(jié)點(diǎn)將自己的地址添加到該RREQ的記錄中，然后按照本地廣播分組方式將該路由請求發(fā)送出去。3)目的節(jié)點(diǎn)D收到RREQ后，要給源節(jié)點(diǎn)S回送路由應(yīng)答(RREP)，先檢查自己是否有到達(dá)源節(jié)點(diǎn)S的路由，如果有，則目的節(jié)點(diǎn)D通過這條路由將RREP交付給源節(jié)點(diǎn)S;否則，目的節(jié)點(diǎn)D執(zhí)行自己的路由尋找，找出到達(dá)源節(jié)點(diǎn)S的路由。

(2)路由維護(hù)。當(dāng)使用某條源路由發(fā)送分組時，該路由中的節(jié)點(diǎn)均要通過應(yīng)答(Acknowledgement)機(jī)制來保證該分組能夠順利到達(dá)下一跳節(jié)點(diǎn)。若一個應(yīng)答請求發(fā)送后仍未得到回應(yīng)，則需要重發(fā)，當(dāng)重發(fā)次數(shù)達(dá)到最大值時，發(fā)送節(jié)點(diǎn)則認(rèn)為到下一節(jié)點(diǎn)的鏈路已經(jīng)斷開，同時從路由表中刪除該斷開鏈路，并給該源路由上的節(jié)點(diǎn)回傳一個路由錯誤(Router Error)。

如圖5所示，若節(jié)點(diǎn)B經(jīng)過若干次應(yīng)答請求后，仍未接收到節(jié)點(diǎn)C的回應(yīng)，則B認(rèn)為到C的鏈已斷開，同時從路由表中刪除該斷開鏈路，并給S及所有同樣的節(jié)點(diǎn)回傳一個路由錯誤。若S的路由表中存在另一條到達(dá)D的路由，則S使用該條路由，否則S應(yīng)執(zhí)行一個新的路由尋找來獲取一條可到達(dá)D的新路由。

圖5 路由維護(hù)

4 MANET路由協(xié)議發(fā)展方向

目前，MANET路由協(xié)議的研究多集中在設(shè)計路由協(xié)議，用來支持網(wǎng)絡(luò)節(jié)點(diǎn)之間的高效通信。MANET路由協(xié)議的性能和多樣性仍有較大的提高空間，其中包括以下幾個方面:(1)路由安全性。MANET與傳統(tǒng)網(wǎng)絡(luò)結(jié)構(gòu)上的差異導(dǎo)致傳統(tǒng)網(wǎng)絡(luò)中的安全機(jī)制不再適用于MANET。對于MANET來說，路由安全具有重要的地位，也是較難解決的問題。路由協(xié)議是網(wǎng)絡(luò)攻擊的主要目標(biāo)，然而目前已經(jīng)提出的路由協(xié)議在安全方面鮮有涉及，因此提高路由協(xié)議的安全是今后的研究方向。(2)路由協(xié)議的節(jié)能問題［9］。由于MANET沒有固定基礎(chǔ)設(shè)施的支持，單個節(jié)點(diǎn)必須依靠可攜帶的電源提供能量。網(wǎng)絡(luò)的發(fā)展導(dǎo)致單個節(jié)點(diǎn)的能量消耗越來越大，這就使得減少節(jié)點(diǎn)的耗能顯得尤為重要。目前的許多協(xié)議都沒有節(jié)能策略，因此這方面的問題仍有待進(jìn)一步的研究。

［1］ 張程.移動自組網(wǎng)的關(guān)鍵技術(shù)研究［D］.重慶:重慶大學(xué)，2010.

［2］ 陳林星.移動Ad Hoc網(wǎng)絡(luò)－自組織分組無線網(wǎng)絡(luò)技術(shù)［M］.北京:電子工業(yè)出版社，2006.

［3］ 李振宇.移動自組網(wǎng)中路由協(xié)議的分析與研究［D］.北京:北京郵電大學(xué)，2006.

［4］AMITH K.Step by step procedural comparison of DSR，AODV and DSDV Routing protocol［C］.Torolento:ICCET，2012.

［5］ 吳翠萍，蔡明.AODV路由協(xié)議的改進(jìn)［J］.計算機(jī)工程與應(yīng)用，2012，48(24):91－94.

［6］SARITA R，SINGH B，BHADAURIA W，et al.Bandwidth reservation routing technique based on agent in mobile ad hoc networks using rate control with AODV［C］.Amsterdam:ICNCS，2012.

［7］KHATAWKAR S D，PANDYAJI K K.Performance comparison of DSDV，AODV，DSR routing protocols for MANETs［C］.Paris:ICCNC，2012.

［8］SANGEETA B，SUNEETA M.Study of DSR routing protocol in mobile adhoc network［C］.Nanjing:ICINT，2011.

［9］ 李鵬.基于能量的移動自組網(wǎng)路由協(xié)議研究［D］.武漢:華中科技大學(xué)，2006.