基于Ａｄ ｈｏｃ網(wǎng)絡(luò)的一種混合路由算法

摘要：移動Ad hoc網(wǎng)絡(luò)中，混合路由協(xié)議擁有比先發(fā)性（Proactive）和反應(yīng)性（Reactive）路由協(xié)議較好的性能。基于大規(guī)模網(wǎng)絡(luò)中組成員間的連接動態(tài)變化而僅有少數(shù)成員具有穩(wěn)定的位置和連接，提出一種混合路由算法。該算法通過改進(jìn)節(jié)點(diǎn)存儲結(jié)構(gòu)來優(yōu)化路由發(fā)現(xiàn)時(shí)間，理論分析和模擬測試顯示該算法具有一定的優(yōu)勢。

關(guān)鍵詞：Ad hoc網(wǎng)絡(luò)； 混合路由協(xié)議； 存儲結(jié)構(gòu)； 路由發(fā)現(xiàn)

中圖法分類號：TP393．04文獻(xiàn)標(biāo)識碼：A

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

移動自組網(wǎng)沒有固定的路由器，各節(jié)點(diǎn)以任意方式移動并自發(fā)地動態(tài)連接，每個(gè)節(jié)點(diǎn)既作為信息傳遞的終端節(jié)點(diǎn)（Terminode）又作為路由（Router）出現(xiàn)。因此，移動自組網(wǎng)是一個(gè)自組織的多跳無中心接入的系統(tǒng)[1]。其特殊性表現(xiàn)為網(wǎng)絡(luò)自主性、動態(tài)變化的拓?fù)浣Y(jié)構(gòu)、帶寬限制和變化的鏈路容量、節(jié)點(diǎn)受限于設(shè)備條件、多跳通信、分布式控制、有限的物理安全、網(wǎng)絡(luò)的可擴(kuò)展性不強(qiáng)、單向無線信道的存在和生存時(shí)間短等方面[1]。移動Ad hoc網(wǎng)正成為一個(gè)備受關(guān)注的熱點(diǎn)。

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

本文目標(biāo)在于構(gòu)建網(wǎng)絡(luò)環(huán)境，針對移動Ad hoc網(wǎng)的規(guī)模較大，組成員關(guān)系變化大，但組內(nèi)存在少量成員具有比較穩(wěn)定的位置和鏈路連接狀態(tài)的條件下，提出了一種混合路由算法。該算法的主要思想是通過利用節(jié)點(diǎn)之間保存的鄰接關(guān)系矩陣計(jì)算源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間的路由。

1網(wǎng)絡(luò)模型與節(jié)點(diǎn)存儲結(jié)構(gòu)

1．1網(wǎng)絡(luò)模型與定義

2路由算法

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

2．1算法中的路由發(fā)現(xiàn)

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

2．2算法中的路由維護(hù)

Ad hoc網(wǎng)節(jié)點(diǎn)的頻繁移動，將造成組成員的位置改變，包括節(jié)點(diǎn)退出和新節(jié)點(diǎn)加入。路由的維護(hù)，主要是動態(tài)修改BS層中的成員及節(jié)點(diǎn)間的BrotherMetrix表。具體方法如下：

3算法分析

3．1算法的理論分析

3．1．1路由發(fā)現(xiàn)時(shí)間

路由是按需通過先發(fā)性方式產(chǎn)生的鄰接關(guān)系矩陣基礎(chǔ)上用Dijkstra算法計(jì)算生成的，因此路由的發(fā)現(xiàn)時(shí)間就是Dijkstra算法的時(shí)間復(fù)雜度O(n2)，n為節(jié)點(diǎn)的個(gè)數(shù)。源節(jié)點(diǎn)vi指向目的節(jié)點(diǎn)vj的路由發(fā)現(xiàn)時(shí)間如下：

以上討論的是一個(gè)節(jié)點(diǎn)失效情況下的空間代價(jià)，若有n個(gè)節(jié)點(diǎn)，代價(jià)就是上述的n倍。

4算法的模擬測試

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

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

圖1DSR，AODV和MACBLZ的路由發(fā)現(xiàn)初始化時(shí)間

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

5結(jié)論

本文提出的移動Ad hoc網(wǎng)絡(luò)中的混合路由算法減少了節(jié)點(diǎn)的存儲空間代價(jià)，縮短了路由發(fā)現(xiàn)的時(shí)間，路由維護(hù)時(shí)間代價(jià)和空間代價(jià)小。路由的維護(hù)只需修改鄰接關(guān)系表，刪除失效的路由即可。

由于網(wǎng)絡(luò)節(jié)點(diǎn)之間的鄰接關(guān)系維護(hù)，需要定時(shí)發(fā)送Hello消息，在一定程度上仍然會形成控制擁塞，同時(shí)也會造成節(jié)點(diǎn)失效信息獲取的滯后，今后這方面將是改進(jìn)的一個(gè)方向。

參考文獻(xiàn)：

［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］孫荷琨，鄭家玲，張?jiān)品?Ad hoc網(wǎng)絡(luò)路由協(xié)議設(shè)計(jì)及性能評估問題[J]. 中國數(shù)據(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），男，講師，博士，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)通信及安全、電子商務(wù)及物流管理；

霍佳震（1962），男，教授，博導(dǎo)，主要研究方向?yàn)楣芾硇畔⑾到y(tǒng)與企業(yè)物流系統(tǒng)的決策支持；

顧景文（1955），男，教授，博導(dǎo)，主要研究方向?yàn)橛?jì)算機(jī)虛擬現(xiàn)實(shí)及可視化技術(shù)；

曹奇英（1960），男，教授，博導(dǎo)，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)和普適計(jì)算。

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