基于無線多跳自組網的混合路由研究

劉穎，唐藝瑋，邵小桃，李旭

(北京交通大學 電子信息工程學院, 北京 100044)

基于無線多跳自組網的混合路由研究

劉穎，唐藝瑋，邵小桃，李旭

(北京交通大學 電子信息工程學院, 北京 100044)

隨著大規模無線多跳自組網在軍隊通信、應急通信等領域的廣泛應用，域路由協議(ZRP)作為一種混合路由協議，其靈活的路由發現和維護策略，使其在大規模網絡中的應用受到了更多的關注。ZRP的域內路由協議以及域間路由協議的選取，對協議整體性能影響巨大。面向具有一定拓撲變化的大規模無線多跳自組網，基于傳統ZRP框架，優化設計得到改進的域路由協議。改進協議中，域內路由協議采用具有更高路由有效性以及較小資源消耗的主動路由策略，域間路由協議則通過增加過期路由緩存機制降低網絡控制開銷。通過建模分析驗證了改進協議的域內路由具有更高的有效性；通過軟件模擬平臺NS2仿真，驗證了改進協議具有更優的性能。

通信技術；無線多跳自組網；混合路由；協議性能

0 引言

無線多跳自組網是一種新型的無線網絡架構，自組織、易架設、可擴展性強等優勢特點使其在軍隊通信、應急通信等領域得到廣泛應用。因無線多跳自組網具有無基礎設施，無中心，網絡中的節點具有移動性，網絡規模可達數百甚至數千個節點的特點，如何保證網絡性能，對路由協議設計來說是較大的挑戰。目前應用于無線多跳自組網的路由協議主要分為3類：主動路由協議、按需路由協議以及混合路由協議。主動路由協議與按需路由協議均采用固定的路由策略，隨著網絡規模的擴大，這兩種協議均暴露出明顯的問題，主動路由協議因其周期性的路由更新產生過大的路由消耗，而按需路由協議則因業務發送前的尋路過程導致全網時延性能較差。域路由協議(ZRP)結合了主動路由策略與按需路由策略，平衡了兩者的優缺點，為大規模無線網絡中的路由尋找和維護提供了一種更為靈活的解決辦法。ZRP草案中給出：域內路由協議(IARP)是一種限制跳數的主動鏈路狀態路由協議,維護到達節點R跳范圍內的所有域內節點的路由信息；域間路由協議(IERP)是一種按需路由協議，用以獲取到達R跳以外節點的路由。

因ZRP在無線多跳自組網中的應用具有較大的潛力，為了能夠使得ZRP具有更優的性能，大量學者對ZRP作出了探索性的優化改進。文獻[1-3]對ZRP的性能針對不同的場景與其他路由協議做出了仿真對比分析，仿真結果表明ZRP性能具有較大提升空間。文獻[4]中將誤比特率作為選路度量值，從而獲得質量更優的路由。文獻[5]中提出了根據移動速度和節點密度來動態調整區域半徑的算法，但運動中的節點移動速度很難估計，導致實際工程中采用該算法動態調整區域半徑很難實現。文獻[6-8]均針對區域重疊問題提出了改進優化方案：文獻[6]提出了動態調整節點發射功率和區域半徑的方案，提高分組投遞率；文獻[7]提出基于位置信息的區域路由協議，但由于需要定位技術支持，使用該方案將提高設備成本和實現復雜度；文獻[8]則提出了一種基于簇域機制的ZRP改進協議(C-ZRP)，在域間利用分層結構進行路由查找，從而降低了路由和網絡開銷，使得協議獲得更高的運行效率，但該改進協議同樣由于需要地理位置信息輔助路由表的建立和更新，且主要針對的網絡規模不是很大的場景，同時需要簇的維護機制，成本高，實現復雜。文獻[9]為了減小路由協議開銷的同時不影響路由精確度，提出了一種基于魚眼狀態路由協議(FSR)的ZRP改進協議(FZRP)，將FSR的思想運用到IARP中，這種改進協議在大規模網絡中，在不明顯增加時延的同時節省了開銷，但該改進協議并未考慮節點的移動性。文獻[10]為降低開銷，提出了區域緩存機制，但該機制很難適用于網絡拓撲變化快、流量較大的網絡中。

盡管上述研究對于ZRP性能均可起到改善作用，但本文認為IARP以及IERP的正確選取是使得ZRP獲得良好性能的根本。因此，本文基于傳統ZRP框架，結合移動Ad-hoc 網絡更優方案(BATMAN)[11]的基本思想以及Ad-hoc 網絡按需距離矢量(AODV)路由協議過期路由緩存機制，優化設計得到一種基于BATMAN的ZRP改進協議(ZRP-B)。ZRP-B首先采用了一種新的基于BATMAN協議的IARP，該協議可及時擴散域內鏈路信息并形成域內路由[12]，相比傳統ZRP協議：域內路由有效保持時間更長，且節省了重新計算路由表的資源消耗；增加了域間過期路由緩存機制，通過對過期路由的充分利用，避免了短時間內反復多次通過洪泛的方式尋路帶來的不必要開銷。通過軟件模擬平臺NS2對協議性能進行仿真驗證，仿真結果表明改進協議可有效地降低時延，對路由開銷稍有改善。

1 改進協議ZRP-B

1.1 ZRP存在問題

ZRP域內主動路由是一種鏈路狀態路由協議，鄰居維護消息與路由更新消息具有相同的周期且分開完成，且每個節點在接收到域內路由更新包后均需要重新計算路由表，資源消耗大，處理時延長，路由收斂性差。某條鏈路狀態經幾跳傳輸以后很可能已經失效，這就導致了路由更新消息中的鏈路信息陳舊，有效性差，影響整體路由質量，進而會增大端到端時延、投遞率等；域內鄰居維護消息與主動路由更新消息均是以相同周期發送，這種方式使得鄰居維護消息與路由更新消息做了重復性的工作，浪費了網絡資源。

為了解決上述域內路由存在的問題，本文提出的改進協議中取消了鄰居維護消息，網絡中的每個節點周期性發送路由包，域內節點接收到路由包以后直接繼續廣播路由包，使得域內節點能夠及時獲取鄰居信息以及到達域內其他節點的路由，提高域內路由有效性。

除上述問題外，在傳統ZRP路由機制中，路由具有一定的生存時間，這意味著路由過期刪除以后節點再次需要到同一目的節點的路由時，需要再次啟動尋路過程。若本次尋路與上一次尋路間隔時間較短，節點運動范圍有限，大規模全網廣播尋路消息是不必要的，會造成網絡資源浪費[13]。

為了減少域間尋路不必要的轉發，改進協議中將過期的域間路由進行緩存，在短時間內再次需要到達該目的節點的路由時，無需全網搜索，只需將搜索方向限定在上一次獲取路由的下一跳節點方向，從而減少無用的轉發。

1.2 ZRP-B具體算法描述

1.2.1 域內路由協議

1)源節點生成并廣播IARP路由包。源節點周期性地廣播IARP路由包來通知域內節點發現它的存在。源節點需將本機地址添加到路由包中的路由區域，將生存時間(TTL)值設為區域半徑值R(單位為跳數)。

2)域內節點接收并轉發IARP路由包。

①更新路由表。接收到IARP路由包的中間節點將本節點地址順序添加至IARP路由包路由區域內，并記錄下路由區域內的路由及鏈路信息，更新本地路由表，繼續步驟②；

②緩存IARP路由包信息。查看IARP路由包信息緩存表，若已接收過同一源節點發來的相同序列號的路由包，則將該路由包丟棄；否則，緩存路由包信息，緩存內容包括：源節點地址和包的序列號，繼續步驟③；

③更新IARP路由包TTL值。更新路由包中TTL值，若TTL值小于等于0，則將該路由包丟棄；否則，向鄰居節點廣播IARP路由包。

圖1為一個區域半徑為2的IARP例圖。節點S到期廣播IARP路由包，在IARP路由包的路由區域中添加本機地址，并將TTL值設為2；A、B、C、D接收到IARP路由包，并分別將本機地址添加至路由區域，分別記錄下鏈路S-A、S-B、S-C、S-D，并更新到節點S的路由，然后查看緩存中是否記錄該包信息，若有，則丟棄；否則，更新TTL值，此時TTL值為1，為大于0的值，因而繼續廣播該路由包；下面以A節點為例，節點A繼續廣播包，節點S、G、C均會收到，節點S、C已收到過該路由包，因此節點S只會記錄下鏈路S-A，節點C會記錄下鏈路S-A和A-C，并分別更新到達節點A的路由，然后節點S和節點C將包丟棄；節點G收到路由包，更新TTL值，發現TTL值為0，記錄下鏈路S-A和A-G并更新到節點A與節點S的路由以后將該路由包丟棄，其他節點接收到域內路由包具有相同處理過程。

圖1 IARP例圖Fig.1 Example of IARP

1.2.2 域間路由協議

1)啟動IERP. 源節點產生數據包，首先查看本節點路由表中是否含有到目的節點的路由條目，若有，則直接發送；否則，查看過期路由緩存表中是否有到目的節點的路由條目，若有，生成路由請求(RREQ)包，并發送至該緩存條目中的下一跳；否則，生成RREQ包，并邊界廣播。

2)中間節點轉發處理IERP RREQ包。

①緩存IERP RREQ包。中間節點接收到IERP RREQ包后，首先查看本節點的請求緩存中是否存在該RREQ包的相關信息，若存在，則將該RREQ包丟棄；否則建立到達源節點的反向路由，并將該請求包的相關信息添加至緩存中，主要包括請求源節點、目的節點、請求包ID，繼續步驟②；

②轉發RREQ包。中間節點首先查看目的節點是否位于本節點區域內，若在則將RREQ包單播至目的節點；否則，將上一跳節點的區域內節點標記為已覆蓋，并查看RREQ包的多播樹節點地址區域是否有本節點的地址，若有則將原RREQ包中多播樹節點地址區域的所有地址修改為可到達本節點所有邊界節點的鄰居節點地址，并將本節點地址順序添加至源路由列表中，繼續邊界廣播包。

3)目的節點響應RREQ包。目的節點生成路由響應(RREP)包，并沿反向路由將該RREP包單播給源節點。

圖2為一個區域半徑為2的IERP例圖。節點S第1次需要一條到節點J路由(路由緩存中沒有到節點J路由的相關信息)，節點S將進行邊界廣播路由請求包(RREQ報文沿虛線箭頭方向向外廣播)，其中節點S的鄰居節點A、B、C、D位于邊界廣播樹上，它們的地址將被添加至RREQ包的多播樹節點列表中；鄰居節點M不在邊界廣播樹上，于是節點M收到RREQ消息以后，發現自己緩存中沒有該RREQ消息相關信息，于是記錄下該RREQ消息信息，然后查看RREQ消息中的邊界廣播樹節點地址列表發現自己不在其中，于是將包丟棄不再繼續廣播；節點A、B、C、D接收到RREQ包，首先同M記錄下RREQ包信息，然后發現自己在邊界廣播樹節點地址列表中，節點A、B、C查看域內路由，沒有到節點J的路由，于是繼續邊界廣播RREQ包，而節點D發現節點J位于自己的路由區域，于是將 RREQ包單播發送至節點J，同時繼續邊界廣播RREQ包，沿路的進行轉發的節點均會按順序將本節點地址添加至路由請求包的源路由列表中；目的節點J收到路由請求包，將創建路由響應包，將路由請求包中的源路由列表復制到路由響應包中，并按照反向路由方向(J-F-D-S)將包發送至源節點S，源節點S將到達節點J的路由(S-D-F-J)緩存在域間路由表中，設置過期時間，然后可向節點J發送數據。一段時間以后，域間路由表中節點S到節點J的路由過期，于是節點S將到節點J的路由緩存至域間過期路由緩存中，并設置過期移除時間(本次過期將刪除該條路由)。在此期間內節點S再次有到節點J的數據需要發送，本次節點S首先查看路由表中是否有到節點J的路由，沒有查到，于是查看域間過期路由緩存，發現有到節點J的路由，于是節點S直接沿路由S-D-F-J單播路由請求包至節點J，節點J再生成路由響應回復節點S，完成本次路由查找過程。

圖2 IERP例圖Fig.2 Example of IERP

1.2.3 路由維護相關機制

1)斷鏈維護。若節點在發送數據包過程中，若檢測到斷鏈，節點將首先刪除本地鏈路狀態表中存儲的該條鏈路以及路由表中的相關路由表項，通過鏈路狀態表重新計算相關路由。若仍存在可到達該數據包目的節點的路由，則更新數據包路由區域路由，繼續轉發包；若沒有，則將包丟棄，并生成路由錯誤(RERR)包，在包中添加斷鏈信息，然后將RERR包廣播，TTL值設為區域半徑值R，用以通知域內的節點該條斷鏈。

2)域間路由過期處理。當節點路由表中一條到達域外節點的路由過期后，將該條路由信息在過期路由緩存中緩存，并從路由表中刪除該條路由信息。過期路由緩存定時到期，過期路由將從過期路由緩存中被刪除。

2 域內路由有效性分析

本文使用節點存儲的平均鏈路有效保持時間作為路由有效性的衡量標準，定義為鏈路平均保持時間與鏈路信息傳遞平均端到端時延(包括處理時延與傳輸時延)之差。

(1)

(2)

ZRP-B IARP中，域內路由包發送周期與傳統ZRP IARP中路由更新消息周期相同，為T. 由于源節點不攜帶與鄰居節點間的鏈路信息，因此可直接生成路由更新包，并發送，節點在接收到來自其他節點的域內路由包以后，無需重新計算路由，可直接記錄下路由更新包中的路由信息，并直接轉發。因此域內鏈路信息在中間節點平均駐留時間近似為0，因此網絡中的節點與鄰居節點之間的鏈路信息到達域內k跳的節點所需平均端到端時延為

(3)

則ZRP-B IARP中節點存儲的平均鏈路有效保持時間為

(4)

經上述分析可知ZRP-B域內路由有效性高于傳統ZRP.

3 ZRP-B仿真與分析

3.1 仿真環境

本文基于軟件模擬NS2平臺對ZRP-B進行仿真。由于混合路由協議的產生主要是為了適應大規模且網絡拓撲變化較快的場景下，因此，本文仿真中設置具體仿真場景參數如表1所示。

表1 仿真場景參數Tab.1 Parameters of simulation scene

根據上述表格設置的場景參數，使用NS2下的移動場景生成工具，選用隨機路點模型生成移動場景，并使用流量生成器采用等概率隨機產生每對連接的收發節點的方式生成流量場景。

為提高仿真數據可靠性，針對表1場景參數設置生成多組移動場景文件與流量場景文件進行多次試驗，最終通過平均仿真結果來估計路由協議性能。

3.2 仿真結果及分析

通過仿真結果，本文主要從平均端到端時延τ、包投遞率ρ以及控制開銷占比η3個方面對ZRP-B與傳統ZRP進行對比分析。

如圖3所示，ZRP-B的端到端時延明顯優于傳統ZRP. 由第2部分路由有效性分析知，當ZRP-B與ZRP具有相同更新周期的情況下，ZRP-B所獲得的域內路由有效性更高，因而可有效降低發包過程中因路由質量導致的重傳概率，進而降低了整體的端到端時延。

圖3 ZRP與ZRP-B平均端到端時延對比圖Fig.3 Average end-to-end delay comparison of ZRP and ZRP-B

圖4 ZRP與ZRP-B投遞率對比圖Fig.4 Delivery ratios of ZRP and ZRP-B

圖5 ZRP與ZRP-B路由開銷對比圖Fig.5 Routing overheads of ZRP and ZRP-B

圖4為兩個路由協議投遞率的對比關系，從圖4中可以看出，ZRP-B投遞率相對傳統ZRP稍有提高，這是因為ZRP-B獲得的路由具有更好的有效性，降低了數據包發送途中因路由失效或中斷導致丟失的概率。

圖5為仿真得到的ZRP與ZRP-B路由控制開銷占比對比圖。兩種協議在3.1仿真場景設置之下，IARP開銷基本相當，而ZRP-B的IERP增加了過期路由緩存機制，有效減少了域間路由尋路過程洪泛導致的開銷，因此ZRP-B相比傳統ZRP協議路由開銷稍有減少。

4 結論

本文針對傳統的ZRP協議在域內路由有效性、資源消耗以及域間尋路開銷方面的不足之處，提出了一種改進的混合路由協議ZRP-B，通過采用類似BATMAN的主動路由策略以及域內斷鏈維護提高了路由有效性，減小了資源消耗，降低了端到端時延，同時通過增加域間過期路由緩存機制降低了路由控制開銷。通過仿真結果和對比分析，改進協議ZRP-B在整體性能上優于傳統ZRP，尤其在時延方面改善顯著。

References)

[1] Loutfi A, Elkoutbi M. Evaluation and enhancement of ZRP performances[C]∥International Conference on Multimedia Computing and Systems. Ouarzazate, Morocco: IEEE, 2011.

[2] Gandhi S, Chaubey N, Shah P, et al. Performance evaluation of DSR, OLSR and ZRP protocols in MANETs[C]∥International Conference on Computer Communication and Informatics. Coimbatore, India: IEEE, 2012.

[3] Khatkar A, Singh Y. Performance evaluation of hybrid routing protocols in mobile ad hoc networks[C]∥International Conference on Advanced Computing and Communication Technologies. Rohtak, India: IEEE, 2012:542-545.

[4] Yelemou T, Meseure P, Poussard A M. Improving ZRP performance by taking into account quality of links[C]∥IEEE Wireless Communications and Networking Conference. Bratislava, Czechoslovakia: IEEE, 2012:2956-2960.

[5] 黃小嶺.基于節點密度和速度的新型路由協議ZRP-DV研究與仿真[J].電腦知識與技術,2010,6(9):2115-2118. HUANG Xiao-ling. Ad Hoc network routing protocol ZRP research and simulation[J]. Computer Knowledge and Technology,2010, 6(9):2115-2118.(in Chinese)

[6] 楊羽.基于ZRP的Ad Hoc網絡路由協議的優化研究[J].遼東學院學報:自然科學版,2009,16(3):227-231. YANG Yu. ZRP-based optimization for Ad Hoc routing protocol[J]. Journal of Eastern Liaoning University:Natural Science, 2009,16(3):227-231. (in Chinese)

[7] 施榮華,羅棋峰.一種MANET中基于位置信息的ZRP路由協議[J].湖南大學學報:自然科學版,2009,36(8):38-42. SHI Rong-hua,LUO Qi-feng. Location-aided ZRP in MANET[J]. Journal of Hunan University:Natural Science, 2009, 36(8):38-42. (in Chinese)

[8] 付光輝.基于簇域機制的ZRP改進研究[D].重慶：西南大學,2011. FU Guang-hui. The research of the zone routing protocol based on cluster[D]. Chongqing: Southwest University, 2011. (in Chinese)

[9] 樊琛潔.Ad Hoc網絡路由協議FZRP協議研究[D].西安：西安電子科技大學,2009. FAN Chen-jie. The research of Ad Hoc network routing protocol FZRP[D]. Xi’an:Xidian University,2009. (in Chinese)

[10] 朱麗亞,馮軍,陳彥輝，等.區域緩存機制在ZRP協議中的應用[C]∥2005年中國西部青年通信學術會議.成都：中國通信學會，2005:388-391. ZHU Li-ya,FENG Jun,CHEN Yan-hui, et al. Application of zone caching scheme in ZRP[C]∥2005 Western China Young People Conference on Communication Technology. Chengdu: China Institute of Communications, 2005: 388-391. (in Chinese)

[11] Sanchez-Iborra R, Cano M D, Garcia-Haro J. Performance evaluation of BATMAN routing protocol for VoIP services: a QoE perspective[J]. IEEE Transactions on Wireless Communications, 2014, 13(9):4947-4958.

[12] 申爽,李紹文,羅軍. 無線mesh網絡B.A.T.M.A.N.adv路由協議的分析與優化[J]. 微計算機信息,2012(10):327-329. SHEN Shuang,LI Shao-wen,LUO Jun. Analysis and optimization of wireless mesh network B.A.T.M.A.N. Adv routing protocol[J]. Microcomputer Information, 2012(10):327-329. (in Chinese)

[13] Koyama A, Honma Y, Arai J, et al. An enhanced zone-based routing protocol for mobile ad-hoc networks based on route reliability[C]∥International Conference on Advanced Information Networking and Applications. Vienna, Austria: IEEE Computer Society, 2006:61-68.

Hybrid Routing Protocol for Wireless Multi-hop Ad Hoc Networks

LIU Ying，TANG Yi-wei，SHAO Xiao-tao，LI Xu

(School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing 100044，China)

Since the large-scale wireless multi-hop ad hoc networks have been widely used in military communications, emergency communications and other fields, the zone routing protocol (ZRP), as a hybrid routing protocol, has been paid more attention in the large scale network application because of its more flexible routing discovery and maintenance strategy. The selection of intrazone routing protocol and interzone routing protocol of ZRP has great impact on the overall protocol performance. An improved zone routing protocol based on the traditional ZRP framework is proposed for large-scale wireless multi-hop ad hoc network that has certain topological changes. In the improved protocol, the intrazone routing protocol uses a more effective and less resource consumption routing strategy, and the interzone routing protocol uses an expired routing cache mechanism to reduce network overhead. The modeling and analysis results show that the improved routing protocol has higher validity. It is verified through NS2 simulation that the improved protocol has better performance.

communication technology; wireless multi-hop ad hoc network; hybrid routing protocol; protocol performance

2016-04-05

國家自然科學基金項目(61371068)；國家“863”計劃項目(2015AA01A705)；國家科技支撐項目(2014BAK02B04)；中央高校基本科研業務費專項資金項目(2014JBZ002)

劉穎(1964—)，女，教授，博士生導師。E-mail: liuying@bjtu.edu.cn

TN915.04

A

1000-1093(2017)01-0184-06

10.3969/j.issn.1000-1093.2017.01.024