無線Mesh網(wǎng)絡的AODV協(xié)議的研究

康瑋辰

（北京工業(yè)大學 北京 100124）

無線 Mesh 網(wǎng)[1]（Wireless Mesh Network， WMN）是一種多跳、具有自組織和自愈特點的寬帶無線網(wǎng)絡結(jié)構(gòu)，即一種高容量、高速率的分布式網(wǎng)絡。它旨在探索無線移動通信與IP技術(shù)的結(jié)合，研究在小型區(qū)域范圍內(nèi)允許多個網(wǎng)絡同時存在、不同網(wǎng)絡自動區(qū)分、拓撲結(jié)構(gòu)動態(tài)可變、具有多跳和動態(tài)路由能力的自組織網(wǎng)絡結(jié)構(gòu)形式。無線Mesh網(wǎng)絡由Ad Choc網(wǎng)絡發(fā)展而來但靜態(tài)于Ad Hoc[2]，相當于Internet的無線版本。

AODV協(xié)議作為一種按需路由算法，在無線Mesh網(wǎng)絡中有著最為廣泛的應用。 但在無線Mesh網(wǎng)中，AODV協(xié)議路由表中的節(jié)點變?yōu)椴豢蛇_即出現(xiàn)斷路時，會重新發(fā)起整個路由請求過程。本文在借鑒AODV-BR協(xié)議思想的基礎上，提出了改進的AODV-BRS協(xié)議，該協(xié)議維護了除主路由表之外的備用路由表。在發(fā)生路由中斷時，可以使用備用的路由繼續(xù)轉(zhuǎn)發(fā)數(shù)據(jù)包，從而降低了網(wǎng)絡的時延。

1 AODV路由協(xié)議

1.1 路由發(fā)現(xiàn)

AODV[3]路由協(xié)議分為路由發(fā)現(xiàn)和路由維護兩個過程。AODV是一種按需路由協(xié)議，當源節(jié)點需要向目的節(jié)點發(fā)送數(shù)據(jù)時，如果路由表中沒有目的節(jié)點的路由信息，則需要以多播的形式發(fā)出RREQ（路由請求）報文。如圖1所示，節(jié)點S要向節(jié)點D發(fā)送數(shù)據(jù)，由于不知曉到節(jié)點D的路由，以多播的形式向其下游的臨近節(jié)點1，2，3發(fā)出了RREQ報文，節(jié)點1，2，3在收到報文后會建立到S的反向路由，然后將RREQ報文發(fā)送給其下游的節(jié)點4，5，6。同樣的節(jié)點4，5，6在接收到RREQ報文后，會建立到發(fā)給他們報文的節(jié)點1，2，3的反向路由并將RREQ繼續(xù)向下傳遞。此時我們假設節(jié)點5發(fā)送的RREQ最先到達了目的節(jié)點D，那么節(jié)點D就回沿著之前建立的反向路由將RREP報文發(fā)送給節(jié)點S，從而建立起由節(jié)點S到節(jié)點D的路由。節(jié)點D只應答第一個或者之后的目的序列號更新的或者跳數(shù)更少的RREQ請求，依照此原則節(jié)點4，6將不會得到RREP應答。

圖1路由發(fā)現(xiàn)Fig.1 Route discovery

1.2 路由維護

AODV路由維護過程如圖2所示，節(jié)點S向目的節(jié)點D發(fā)送數(shù)據(jù)，數(shù)據(jù)發(fā)送到節(jié)點1后，節(jié)點1向節(jié)點2轉(zhuǎn)發(fā)數(shù)據(jù)時發(fā)現(xiàn)節(jié)點2已經(jīng)不可達。此時如果節(jié)點1離目的節(jié)點較近，則節(jié)點1會發(fā)起本地修復，以多播形式發(fā)送RREQ報文，建立起從節(jié)點1到節(jié)點D的路由。在路由建立過程中，節(jié)點S發(fā)出的數(shù)據(jù)會暫時保存在節(jié)點1中。而如果局部修復失敗，那么節(jié)點1將會向節(jié)點S發(fā)送RRER報文，節(jié)點S收到報文后從重新以路由發(fā)起的方式重新建立到節(jié)點D的路由。

圖2路由維護Fig.2 Route maintenance

2 改進的AODV算法

2.1 現(xiàn)有的AODV-BR算法

AODV-BR[4]算法在發(fā)起路由請求過程中，當源節(jié)點需要向目的節(jié)點建立路由時，同樣的會使用洪范法發(fā)送RREQ報文。每個RREQ請求都有一個為一個ID標識，因此節(jié)點可以檢測并拋棄重復的RREQ請求。一個中間的節(jié)點，在接收了一個非重復的RREQ請求后，會記錄下之前一跳節(jié)點和源節(jié)點的信息保存在自己的路由表中。而如果該節(jié)點路由表中擁有到目的節(jié)點的路由，則會向源節(jié)點發(fā)送RREP報文，否則將RREQ繼續(xù)向下游傳遞，直至到達目的節(jié)點后，由目的節(jié)點依靠反向路由將RREP報文發(fā)送至源節(jié)點。在以上過程中，AODV-BR算法與AODV協(xié)議保持一致。AODV-BR協(xié)議對AODV的改進之處，在于在RREP報文返回至源節(jié)點過程中，增加了對非直接相關(guān)節(jié)點的“意外”收獲的RREP報文的處理。

如圖3所示，節(jié)點S到節(jié)點D的路由請求過程中會生成與AODV一致的S→2→5→D的主路由。備用路由的建立是在D回傳RREP報文的過程中，由于無線網(wǎng)絡環(huán)境，節(jié)點4，6會“偷聽”到這個RREP報文。在原始的AODV協(xié)議中，節(jié)點4，6是不會對這條報文進行處理的，但在AODV-BR協(xié)議中，節(jié)點4，6會記錄下這條由本身到節(jié)點D的路由，放在自己的備用路由表中。以此類推，節(jié)點1，3也會在RREP報文回傳至節(jié)點S過程中，由于收到了來自節(jié)點5的RREP報文，在各自的備用路由表中分別添加了下一跳為節(jié)點5，目的節(jié)點為節(jié)點D的備用路由。備用路由的更新原則與主路由的更新原則一致，都是在接收到更新的或者跳數(shù)更少的路由信息后，進行更新。

圖3 AODV-BR協(xié)議Fig.3 AODV-BR protocol

2.2 借鑒AODV-BR改進的AODV-BRS

當AODV-BR在用現(xiàn)有的路由轉(zhuǎn)發(fā)數(shù)據(jù)時，在未到達目的節(jié)點前，有中間節(jié)點發(fā)現(xiàn)了鏈路中斷時，該中間節(jié)點會發(fā)出一個一跳的廣播給該節(jié)點所有的鄰居節(jié)點。在該廣播中，除了包含需要轉(zhuǎn)發(fā)的數(shù)據(jù)外，還在廣播頭中加入了標識信息用以告知鄰居節(jié)點鏈路的中斷。鄰居節(jié)點在收到該廣播后，會查找自己的備用路由表中是否存在目的節(jié)點的路由信息，若存在，則利用備用路由繼續(xù)完成數(shù)據(jù)的轉(zhuǎn)發(fā)[5]。但在該過程中，存在一個弊端：備用路徑并不是在被發(fā)現(xiàn)鏈路中斷的節(jié)點直接使用，而是這個節(jié)點告知后續(xù)的節(jié)點，由后續(xù)一跳范圍內(nèi)的節(jié)點啟用自己的備用路徑。這樣做會導致這些鄰居如果使用了節(jié)點不相交的路徑進行數(shù)據(jù)傳輸時，會導致導致多個重復數(shù)據(jù)被傳送至目的節(jié)點，造成資源的浪費[6]。

改進后的協(xié)議AODV-BRS，在某種程度上可以減輕原有協(xié)議機制對鏈路資源浪費造成的影響。在改進后的協(xié)議中，在主路由建立過程中，除了為非主路徑上的節(jié)點建立備用路由，同時也會為主路徑上的節(jié)點建立備用路由。在發(fā)生鏈路中斷時，節(jié)點會首先檢查備用路由是否存在路徑：若存在則直接利用備用路由發(fā)送，否則再利用AODV-BR原協(xié)議機制發(fā)送頭部攜帶有鏈路中斷信息的給周圍鄰居節(jié)點。

在AODV-BRS協(xié)議中，需要加入新的RREPS報文，報文格式如圖4。

圖4 RREPS報文Fig.4 RREPSmessage

報文中，除Backup Route Flag外，其余字段都與原有RREP字段相同。新加入的字段Backup Route Flag，是為了使節(jié)點在收到該報文后，將路由信息保存在自己的備用路由中。

非主路徑上節(jié)點收到RREP判定是否發(fā)送RREPS的偽代碼：

if（exist route to Destination IPaddress in backup table）{

if（Hop==Hop0&&AddressTo!=Originator IP address）Ignore；

else if（Hop-Hop0==1&&AddressTo!=Originator IP address）

Send RREPS to AddressFrom；

Else if（Hop==Hop0&&AddressTo==Originator IPaddress）

Send RREPS to Originator IP address；

}

Destination IP address和Originator IP address分別代表RREP報文中的對應字段。

Hop0代表備用路由表中到達目的節(jié)點的跳數(shù)，Hop代表發(fā)送RREP給自己的節(jié)點到目的節(jié)點的跳數(shù)。

AddressTo代表RREP所指向的節(jié)點地址，AddressFrom代表發(fā)送RREP的節(jié)點地址。

具體工作過程如圖5所示，a在節(jié)點D收到來 5的RREQ請求之后，會發(fā)送RREP報文，節(jié)點4，6在無線傳輸?shù)挠行Х秶鷥?nèi)接收到了這條報文，會建立到節(jié)點D的備用路由，這里和原始AODV-BR協(xié)議保持一致。節(jié)點5在收到這條來自節(jié)點D的RREP報文后，會繼續(xù)將報文傳遞，這時節(jié)點4，6會再次收到來自節(jié)點 5的RREP報文，節(jié)點4，6根據(jù)偽代碼中原則不予處理。b接下來節(jié)點2接收到了來自節(jié)點5的RREP報文，這次在傳輸范圍內(nèi)的節(jié)點4，6又會收到來自節(jié)點2發(fā)送RREP報文，節(jié)點4，6再次根據(jù)偽代碼原則進行判斷，需要向節(jié)點2發(fā)送RREPS報文，假設節(jié)點2先收到來自節(jié)點4的RREPS報文，則建立以節(jié)點4為下一跳目的節(jié)點為節(jié)點D的路由放入備用路由表中。c節(jié)點1，3同樣會收到來自節(jié)點2的RREP報文，根據(jù)偽代碼中原則，節(jié)點1，3會向節(jié)點S發(fā)送RREPS報文，假設節(jié)點S先收到了來自節(jié)點3的RREPS報文，則將以節(jié)點3為下一跳目的節(jié)點為節(jié)點D的路由存入自己的備用路由表中。

圖5 AODV-BRS協(xié)議Fig.5 AODV-BRSprotocol

3 結(jié) 論

相較原始的AODV-BR協(xié)議，在改進后的AODV-BRS協(xié)議中，備用路由不僅只在非主路徑上建立，主路徑上節(jié)點的備用路由也會隨之建立。改進后的協(xié)議可以在鏈路出現(xiàn)中斷時，直接在發(fā)現(xiàn)鏈路中斷的節(jié)點處利用備用路徑將數(shù)據(jù)轉(zhuǎn)發(fā)，取代了之前協(xié)議中發(fā)現(xiàn)斷路節(jié)點將數(shù)據(jù)包轉(zhuǎn)發(fā)給全部鄰居節(jié)點，由鄰居使用自己的備用路徑將數(shù)據(jù)轉(zhuǎn)發(fā)的機制。這樣有效避免了之前協(xié)議中，多個重復數(shù)據(jù)造成的傳輸路徑資源的浪費，進一步降低了無線Mesh網(wǎng)絡時延。

[1]王萍，李穎哲．無線Mesh網(wǎng)絡基礎[M].西安：西安交通大學出版社，2012:1-25．

[2]方旭明．移動AdHoc網(wǎng)絡研究與發(fā)展現(xiàn)狀[J].數(shù)據(jù)通信，2003（4）:30-33．FANG Xu-ming．Research and development status of mobile Adhoc[J].Data Communication，2003（4）:30-33．

[3]Perkins C，Bekling-Royer E，Das S．Ad Hoc On-demand Distance Vector （AODV） routing protocol[J]．Internet Engineering Task Force（IETF），2003（7）:134-146．

[4]Sung JL，Mario Gerla．AODV-BR:Backup Routing in Ad hoc Networks [C]//Wireless Communications and Networking Confernce，WCNC.IEEE.2000，3:1311-1216．

[5]Hsing Lung Chen，Chein Hsin Lee．Two hops backup routing protocol in mobile ad hoc networks [C]//Parallel and Distributed Systems，2005:600-604．

[6]Junghui Jeon．Fast route recovery scheme for Mobile Ad Hoc Networks [C]//International Conference on Information Networking （ICOIN），2011:419-423．