基于Ａｄ ｈｏｃ網絡的一種混合路由算法

摘要：移動Ad hoc網絡中，混合路由協議擁有比先發性（Proactive）和反應性（Reactive）路由協議較好的性能。基于大規模網絡中組成員間的連接動態變化而僅有少數成員具有穩定的位置和連接，提出一種混合路由算法。該算法通過改進節點存儲結構來優化路由發現時間，理論分析和模擬測試顯示該算法具有一定的優勢。

關鍵詞：Ad hoc網絡； 混合路由協議； 存儲結構； 路由發現

中圖法分類號：TP393．04文獻標識碼：A

文章編號：1001－3695(2007)01－0313－03

移動自組網沒有固定的路由器，各節點以任意方式移動并自發地動態連接，每個節點既作為信息傳遞的終端節點（Terminode）又作為路由（Router）出現。因此，移動自組網是一個自組織的多跳無中心接入的系統[1]。其特殊性表現為網絡自主性、動態變化的拓撲結構、帶寬限制和變化的鏈路容量、節點受限于設備條件、多跳通信、分布式控制、有限的物理安全、網絡的可擴展性不強、單向無線信道的存在和生存時間短等方面[1]。移動Ad hoc網正成為一個備受關注的熱點。

目前Ad hoc網中有三種類型的路由建立方法，即先發性（Proactive）路由協議、反應性（Reactive）路由協議和混合性（Hybrid）路由協議。其中先發性路由協議因要為每個節點維護到整個網絡中所有節點的實時路由信息，會產生大量的控制擁塞；反應性路由協議因路由只是在通信終端間交換數據之前才完成路由發現，導致第一個包發送之前出現延遲；混合路由協議的基本思想為協議組合了限制范圍的本地先發性路由協議和全局的反應性路由協議，本地目標的路由可以立即獲得，以避免路由查找[2]。

本文目標在于構建網絡環境，針對移動Ad hoc網的規模較大，組成員關系變化大，但組內存在少量成員具有比較穩定的位置和鏈路連接狀態的條件下，提出了一種混合路由算法。該算法的主要思想是通過利用節點之間保存的鄰接關系矩陣計算源節點與目的節點之間的路由。

1網絡模型與節點存儲結構

1．1網絡模型與定義

2路由算法

主機采用先發性方式以一跳為距離向量構成BL層，層內按照主機的性能(內存容量、電能大小、CPU運算能力)和基于QoS的鏈路狀態穩定性（傳輸帶寬、信號傳輸質量、生存時間），與類似LANMAR協議[3]一樣選出一個成員作為MN，然后BL層中的MN組成PL層，形成全局網絡拓撲結構。其中BL層內節點以反應性方式維護頻繁變化的組內鄰接關系，而PL層內的節點以先發性方式獲得全局網的鄰接關系。在進行數據轉發時，源節點首先利用BrotherMetrix表判斷目的節點是否與自己同屬一BL層，若是，則直接建立路由；否則，向所處的BL層中的MN發送路由請求，然后MN接管路由請求，利用ParentsMetrix表計算類似協議無關稀疏模式（PIMSM）共享樹的路由，此時的數據發送由源節點到BL層內的MN，再由MN根據計算的路由轉發到目的節點。

2．1算法中的路由發現

BL層的形成，將通過主機間互相發送Hello報文確定以一跳為距離向量的范圍，其組成員的規模通常定為六個主機[4]。路由發現的算法將以按需建立斯坦利（Steiner）路由樹的方式，根據源和目的節點的位置按以下三種情況建立：

2．2算法中的路由維護

Ad hoc網節點的頻繁移動，將造成組成員的位置改變，包括節點退出和新節點加入。路由的維護，主要是動態修改BS層中的成員及節點間的BrotherMetrix表。具體方法如下：

3算法分析

3．1算法的理論分析

3．1．1路由發現時間

路由是按需通過先發性方式產生的鄰接關系矩陣基礎上用Dijkstra算法計算生成的，因此路由的發現時間就是Dijkstra算法的時間復雜度O(n2)，n為節點的個數。源節點vi指向目的節點vj的路由發現時間如下：

以上討論的是一個節點失效情況下的空間代價，若有n個節點，代價就是上述的n倍。

4算法的模擬測試

選取NS2作為仿真平臺，仿真中選取Random Waypoint Model作為仿真模型，其中每個節點靜止特定的一段時間，然后在仿真空間隨機選取一個目的點，以一個符合均勻分布的速度向目的點移動，在此目的點靜止后重復上述過程。環境參數參考C. Alaettinoglu等人[6]指出的移動性、網絡負荷和網絡大小等方面的因素，設置為：網絡由50個移動主機構成，主機分布在670m×670m的區域里，最大移動速度是20m/s，每個節點的停頓時間為600s。MAC層采用IEEE 802.11標準，通信方式為全雙工，隊列采用DropTail方式。其中傳輸業務流選取CBR（Constant Bit Rate，恒定比特率）和FTP，其中CBR使用UDP作為傳輸協議，FTP使用TCP作為傳輸協議。

參考S. Corson等人[7]對路由協議的性能評估的指標，重點考察初始路由獲取時間和傳輸延遲兩方面的性能指標。在數據包發送的源和目的主機間的距離為四跳內的條件下，記錄數據包發送時間和位置，得出首次路由的查找時間，如圖1所示。

圖1DSR，AODV和MACBLZ的路由發現初始化時間

從圖1中不難看出，MACBLZ相對于DSR和AODV縮短了初始路由獲取時間，并且隨著數據發送源和目的主機間的跳數增加，初始路由獲取時間有加速減少的趨勢，這與前面分析的MACBLZ的時間代價主要決定于Dijkstra算法的時間復雜度O(n2)，而DSR和AODV的時間代價主要決定于節點間的跳數相吻合。

5結論

本文提出的移動Ad hoc網絡中的混合路由算法減少了節點的存儲空間代價，縮短了路由發現的時間，路由維護時間代價和空間代價小。路由的維護只需修改鄰接關系表，刪除失效的路由即可。

由于網絡節點之間的鄰接關系維護，需要定時發送Hello消息，在一定程度上仍然會形成控制擁塞，同時也會造成節點失效信息獲取的滯后，今后這方面將是改進的一個方向。

參考文獻：

［1］Martin Mauve， Jorg Widmer，Hannes Hartenstein. A Survey on Positionbased Routing in Mobile Ad hoc Networks[J]. IEEE Network， 2001，15（6）：3039.

［2］Zygmunt J Haas， Marc R Pearlman， Prince Samar. The Bordercast Resolution Protocol (BRP) for Ad hoc Networks[R]. Internet Draft. draftietfmanetzonebrp01.txt. work in progress， 2001.

［3］ Mario Gerla， Xiaoyan Hong， Li Ma， et al. Landmark Routing Protocol (LANMAR) for Large Scale Ad hoc Networks[R]. draftietfmanetlanmar03.txt， 2001.

［4］ Singh S，Woo M，Raghavendra C S.Poweraware Routing in Mobile Ad hoc Networks[C]. Dallas，TX:Proc.of the 4th Annuai ACM/IEEE International Conference on Mobile Compouting and Networking，1998.181190.

［5］孫荷琨，鄭家玲，張云峰.Ad hoc網絡路由協議設計及性能評估問題[J]. 中國數據通信，2002，(7):7174.

［6］C Alaettinoglu， A U Shankar， et al. Design and Implementation of MaRS: A Routing Testbed. Technical Report， CSTR2964， Department of Computer Science， University of Maryland[EB/OL].http://citeseer.nj.nec.com/article/alaettinoglu92design.html.

［7］RFC 25011999，Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations[S].

作者簡介:

徐光偉（1969），男，講師，博士，主要研究方向為計算機網絡通信及安全、電子商務及物流管理；

霍佳震（1962），男，教授，博導，主要研究方向為管理信息系統與企業物流系統的決策支持；

顧景文（1955），男，教授，博導，主要研究方向為計算機虛擬現實及可視化技術；

曹奇英（1960），男，教授，博導，主要研究方向為計算機網絡和普適計算。

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文