無線Ad hoc網絡機會路由的實現與仿真

殷亞敏， 徐春秀， 武穆清， 宿景芳， 張 婷

（北京郵電大學 信息與通信工程學院，北京 100876）

0 引言

無線自組織網絡Ad hoc網絡是由一組帶無線收發裝置的移動設備組成的多跳臨時性自組織網絡，由于無有線基礎設施支持、組網迅速等特點常為需建立臨時通信的特殊場合提供了便利[1]，而Ad hoc網絡中節點的移動性和無線網絡環境的不穩定性，使路由問題成為研究熱點。當前Ad hoc網絡路由協議根據不同的路由策略可以分為表驅動路由協議（如：DSDV[2]、OLSR[3]等）和按需路由協議（如 DSR[4]、AODV[5]等）。傳統的按需路由協議都是利用一定的算法為數據包選擇一條最好的路徑（比如利用Dijskstra算法選擇最短的路徑），然后數據包沿著這條選好的路徑依次傳送。當鏈路狀況好的時候這類協議能表現出很好的性能，但由于實際無線信道的不穩定性經常使所建路徑中的下一跳不可達，導致通信中斷、路由重建，使它們的效率大大降低。

機會路由的概念就是為適應實際無線信道的不穩定性而提出的，當鏈路狀況好的時候，它可以利用距離很遠的傳送，當鏈路狀況不好的時候它又可以利用中間節點的轉發，繼續向前傳。這里實現的應用于無線Ad hoc網絡的機會路由協議（WAOR）引入了“機會轉發”的思想，該協議采用按需路由方式，并通過數據包的廣播和多徑路由來增強鏈路的可靠性，從而提高網絡的整體性能。

1 WAOR的設計思想

機會路由不提前選路，它在源節點和目的節點之間建立一個轉發節點集，源節點以廣播的方式發送數據包，所有轉發節點集中的節點收到數據包后以某種規則將其繼續廣播，直至目的節點。由于數據包的廣播容易造成碰撞和有限帶寬資源的浪費，在機會路由的設計中，應該限制有可能參加轉發的節點數目并盡可能減少重復包的廣播。

WAOR在實現中采用了機會路由的思想，通過傳統路由建立時的路由請求（RREQ）和路由回復（RREP）機制為數據包建立節點轉發列表（FL），這個列表中包含了源節點到目的節點的多條路徑。數據包攜帶FL被廣播，只有FL中的節點才可以轉發數據包，且只能轉發一次。當鏈路狀況好時，WAOR可以利用距離遠的傳送減少分組的端到端時延；當某條鏈路中斷時，由于數據包的廣播和多徑的存在，WAOR可以立即利用其它路徑使數據包繼續傳送，而不會向源節點發送路由錯誤（RRER）消息，也不會重新發起路由查找過程。這樣，比起傳統的Ad hoc路由協議，WAOR不會因為路由中斷丟棄分組，也不會因為路由重建增加端到端時延，同時也不會產生大量路由控制分組增加路由開銷，從而可以在一定程度上提高網絡性能。

2 WAOR的實現

2.1 Forward List的建立

WAOR中FL的建立借鑒DSR中源路由的建立過程。網絡中的每個節點都有一個節點轉發列表緩存（FLC），當源節點有數據包要發送時首先查看 FLC中是否有到目的節點的FL，若有，則將其添加到數據包的頭部，廣播該數據包，若沒有，則啟動RREQ過程。為了使源節點搜集足夠多的有用節點，中間節點對同一RREQ處理多次，目的節點回復多個RREP，源節點按照時間順序處理優先到達的幾個RREP。中間節點記錄處理的RREQ的次數，當超過此次數時將不再處理。當源節點收到多個RREP時，將RREP中的節點無重復地添加到FL中。這樣建立起來的FL中實際上包含了源節點到目的節點的多條路徑，同時由于源節點只處理優先到達的RREP保證了FL中節點的有用性并限制了其數量。

2.2 數據包的處理

由于數據包是以廣播的方式被發送的，為了減少重復包的廣播，每個FL中的節點對同一數據包只轉發一次。實現中，在協議頭部為數據包添加了網絡層的序列號，在網絡中的每個節點添加了記錄本節點所收到的數據包信息的鏈表，節點將記錄所收到數據包的源、目的節點地址和序列號以檢查自己是否重復接收。當節點收到一個數據包時，所做的處理流程如下：

①檢查本節點是否在數據包攜帶的FL中，若在轉向步驟，若不在則轉向步驟⑤；

②檢查本節點的記錄中是否有此數據包的記錄，若有，轉向步驟⑤，否則轉向步驟③；

③將所收到數據包的信息插入到本節點的數據包信息鏈表中，轉向步驟④；

④廣播數據包；

⑤丟棄數據包。

2.3 Forward List的更新

由于 FL中包含了源節點到目的節點的多條路徑，故WAOR沒有傳統路由協議中的路由維護機制。WAOR為FLC中的每個FL都設置了定時器，當定時器超時若節點仍有數據包要發送，將重新發起RREQ過程建立FL。

3 NS2仿真及結果分析

NS2是非常適合報文交換網絡和無線網絡仿真[6]，支持眾多協議，在Ad hoc網絡仿真方面，它所提供的Nakagami-m信道模型更接近于實際的無線信道，為研究路由協議在實際信道中的性能提供了很大的便利?，F采用NS2網絡仿真器，將WAOR在Nakagami-m信道模型的不同參數下進行仿真并與DSR和AODV的性能進行了對比。

3.1 仿真場景的建立

信道模型的設置：Nakagami-m模型是NS2新添加的一種無線信道模型，它可以模擬信道的時變特性、設定信道對不同距離有不同程度的衰減。在提出的仿真中信道參數設置如下表所示，其中信道衰落情況根據設置從0到5逐漸變壞。

表1 Nakagami-m模型信道參數設置

仿真環境設置：9個節點分布在1000×1000的正方形區域，位置關系如圖1所示。每個節點使用IEEE802.11的MAC層協議。仿真中節點0到8產生一條CBR數據流，包大小為512 Bytes，發包間隔為0.02 s，持續時間為50 s。

圖1 節點分布

3.2 仿真結果分析

這里評價路由協議的性能指標主要采用了體現網絡可靠性的分組投遞率、平均端到端時延以及影響無線網絡帶寬利用率的路由開銷，結果如圖2、圖3和圖4所示。

圖2 投遞率隨信道參數的變化

圖3 平均端到端時延隨信道參數的變化

圖4 路由開銷隨信道參數的變化

圖2給出了無線信道參數變化對分組投遞率的影響。從圖2中可以看出，隨無線信道參數變化，AODV和DSR的分組投遞率變化較大，而 WAOR基本不變，且始終接近于100%。這是因為，無線信道參數變差，使節點間鏈路的不可靠性增強，可能導致AODV和DSR剛建立起來的路由不可用，導致通信中斷、分組被丟棄。而 WAOR中數據包是通過多徑傳輸的，當其中某條鏈路失效，數據包仍可通過其它鏈路傳輸而不被丟棄。所以，WAOR在信道參數較差時更能體現其優勢。

圖3給出了無線信道參數變化對分組平均端到端時延的影響。圖3中顯示，隨無線信道參數變差，AODV和DSR的分組平均端到端時延變化較大，且明顯高于WAOR，在某些信道參數下，它們的平均端到端時延已超出上層應用所能容忍的100 ms（圖3中只畫到了100 ms）；而WAOR的分組平均端到端時延始終低于30 ms，可以滿足上層應用的需要。這是因為，無線信道參數變差使得節點間鏈路失效的概率增加，使AODV和DSR重建路由的概率增加，由重建路由所帶來的時延使得二者的平均端到端時延升高。而由于WAOR中包含了源到目的的多條路徑，沒有路由重建所增加的時延。

圖4給出了無線信道參數變化對路由開銷的影響。可以看出，當無線信道參數變差時，AODV和DSR的路由開銷明顯增加，而 WAOR的此項性能基本沒有變化。無線信道參數的變差導致節點間鏈路失效的概率增大，此時，AODV和DSR會向源節點發送RERR消息，源節點會重新建路而洪泛 RREQ消息，從而使路由控制分組大量增加。由于WAOR沒有路由維護，只有FL過期時才會重新發起RREQ過程，所以路由控制開銷不會因為某條鏈路的失效而增大。

4 結語

針對無線信道參數變化對Ad hoc網絡主要性能的影響，采用機會路由的設計思想，在NS2平臺實現了無線Ad hoc網絡中的機會路由WAOR。該協議在FL的建立過程中包含了多條路徑的轉發節點，數據包采用廣播的方式被發送，從而增強了鏈路的可靠性，減小了無線信道參數變差對網絡性能的影響。仿真結果表明，此協議能有效地減小由于信道參數變差而導致的鏈路失效的概率，從而提升了分組投遞率，降低了端到端時延，減小了路由控制開銷。這對于提高實際應用中無線Ad hoc網絡的性能來說是十分有益的。

[1] 侯祥博,王一強,楊金政. 移動Ad Hoc網絡技術研究及應用[J].通信技術,2008,42(08)：15-17,20.

[2] CLAUSEN T,JACQUET P. Optimized Link State Routing Protocol(OLSR) [EB/OL].[2003-10-12] (2009-12-12) http：//tools.ietf.org/rfc/rfc3626.txt,2003.10.

[3] 鄭創明. Ad hoc網絡多目標發送的 DSDV路由協議[J].通信技術,2005,28(04)：6-10.

[4] JOHNSON D,HU Y, MALTZ D. The Dynamic Source Routing Protocol(DSR) for Mobile Ad Hoc Networks for IPv4 [EB/OL].(2007-02-12)[2009-12-15].http：//tools.ietf.org/rfc/rfc4728.txt.

[5] PERKINS C,BELDING-ROYER E, DAS S. Ad hoc On-Demand Distance Vector (AODV) Routing [EB/OL].(2003-01-01)[2009-12-15].http：//tools.ietf.org/rfc/rfc3561.txt.

[6] 韓勇,陳強,王建新. 移動 Ad Hoc網絡仿真工具比較[J].通信技術,2008,41(12)：305-307.