無線Mesh網絡的AODV協議的研究

康瑋辰

（北京工業大學 北京 100124）

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

AODV協議作為一種按需路由算法，在無線Mesh網絡中有著最為廣泛的應用。 但在無線Mesh網中，AODV協議路由表中的節點變為不可達即出現斷路時，會重新發起整個路由請求過程。本文在借鑒AODV-BR協議思想的基礎上，提出了改進的AODV-BRS協議，該協議維護了除主路由表之外的備用路由表。在發生路由中斷時，可以使用備用的路由繼續轉發數據包，從而降低了網絡的時延。

1 AODV路由協議

1.1 路由發現

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

圖1路由發現Fig.1 Route discovery

1.2 路由維護

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

圖2路由維護Fig.2 Route maintenance

2 改進的AODV算法

2.1 現有的AODV-BR算法

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

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

圖3 AODV-BR協議Fig.3 AODV-BR protocol

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

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

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

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

圖4 RREPS報文Fig.4 RREPSmessage

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

非主路徑上節點收到RREP判定是否發送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代表備用路由表中到達目的節點的跳數，Hop代表發送RREP給自己的節點到目的節點的跳數。

AddressTo代表RREP所指向的節點地址，AddressFrom代表發送RREP的節點地址。

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

圖5 AODV-BRS協議Fig.5 AODV-BRSprotocol

3 結 論

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

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

[2]方旭明．移動AdHoc網絡研究與發展現狀[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．