移動Ad hoc網絡路由協議及性能比較

2019-11-03 09:26:32

字體：大中小

來源：轉載

供稿：網友

王海濤，鄭少仁（解放軍理工大學通信工程學院，江蘇南京210007）

　　摘　要：由于Ad hoc網絡自身的特殊性，其路由協議的設計與傳統固定網絡有很大不同。首先說明了Adhoc網絡中提供高效路由算法的難點，然后討論了Ad hoc網絡中路由協議設計的幾種策略，接著介紹了幾種典型的Ad hoc路由協議，最后通過實驗分析比較了4種路由協議的性能，并給出了結論。

　　關鍵詞：網絡模擬器；目的序列距離矢量路由；動態源路由；臨時按序路由；Ad hoc按需距離矢量路由

0　引　言

　　無線網絡通常可以分為有中心網絡和無中心網絡，前者需要固定基礎設施的支持，移動主機之間的通信通常借助基站來完成，例如蜂窩移動通信系統；后者主要是指移動Ad hoc網絡［1－4］，它不需要固定的基礎設施，能夠快速地自動組網。與有中心網絡相比，Ad hoc網絡靈活、健壯、投資少，特別適合于作戰指揮、搶險救災以及應付突發事件和執行臨時任務的場合。在Ad hoc網絡中，每個移動節點兼備路由器和主機兩種功能。作為主機，移動節點需要運行面向用戶的應用程序；作為路由器，它需要運行相應的路由協議，根據路由策略和路由表參與數據分組轉發工作和路由維護工作。考慮到Ad hoc網絡中節點是移動的，網絡的拓撲結構不斷變化，傳統的用于因特網的路由協議（如Rip、OSPF等）無法適應Adhoc網絡的實際需要［2］，同時由于移動節點的計算能力和存儲容量較低并且能源受限，要求路由協議盡量簡單，這又增加了Ad hoc網絡中路由協議設計的難度。

1　Ad hoc中路由協議的分類

　　Ad hoc網絡的路由協議大致可以分為先驗式（PRoactive）路由協議、反應式（Reactive）路由協議以及混合式路由協議［2，5］。先驗式路由協議又稱為表驅動路由協議，在這種路由協議中，每個節點維護一張包含到達其它節點的路由信息的路由表。當檢測到網絡拓撲結構發生變化時，節點在網絡中發送更新消息，收到更新消息的節點將更新自己的路由表，以維護一致的、及時的、準確的路由信息，所以路由表可以準確地反映網絡的拓撲結構。源節點一旦要發送報文，可以立即獲得到達目的節點的路由。因此這種路由協議的時延較小，但是路由協議的開銷較大；反應式路由協議，又稱為按需路由協議，是一種當需要發送數據時才查找路由的路由算法。在這種路由協議中，節點不需要維護及時準確的路由信息，當向目的節點發送報文時，源節點才在網絡中發起路由查找過程，找到相應的路由。與先驗式路由協議相比，反應式路由協議的開銷較小，但是數據報傳送的時延較大。在Ad hoc網絡中單純采用先驗式或反應式路由協議都不能完全解決路由問題。在高速動態變化的Ad hoc網絡中，使用單純的先驗式路由協議會產生大量的控制報文，并且很多控制報文經常是無用的；如果單獨采用反應式路由協議，需要為每個報文查找路由，這也是不合理的（特別是當連續向某個目的節點發送多個報文時）。由此可見，應用結合先驗式和反應式路由協議優點的混合式路由協議是一種較好的折衷方案。在局部范圍內使用先驗式路由協議，維護準確的路由信息，并可縮小路由控制消息傳播的范圍，當目標節點較遠時，通過查找發現路由，這樣既可以減少路由協議的開銷，時延特性也得到了改善。

2　4種典型的Ad hoc網絡路由算法

　　為了比較和驗證Ad hoc網絡中的路由協議的性能，采用了NS2網絡仿真器［4］進行試驗。NS2是由加利福尼亞大學伯克利分校和VINT項目組聯合開發的，是一個包含TCL（Tool Command Lan－guage：工具命令語言）語言的受事件驅動的網絡仿真器。這個仿真器通過NS的解釋程序被調用，解釋程序之間的所有相互作用通過一個專門的TCL程序完成。應用NS命令，可定義一個網絡拓撲，配置流量源和接收器，收集統計的數據等。NS2最初主要被用來模擬傳統有線網絡上的TCP協議和其他協議，它并不支持多跳無線移動網絡環境，隨著相關領域研究的進展，美國的CMU大學對NS2作了相應的擴展，目前，NS2已經可以支持一定范圍內和一定條件下的無線多跳移動網絡。

2．1　目的序列距離矢量路由協議（DSDV）

　　DSDV對Bellman－Ford路由算法進行了改進。

在DSDV中，每個移動節點都需要維護一個路由表。路由表表項包括目的節點、跳數和目的地序號，其中目的地序號由目的節點分配，主要用于判別路由是否過時，并可防止路由環路的產生。每個節點周期性必須與鄰節點交換路由信息，當然也可以根據路由表的改變來觸發路由更新。路由表更新有兩種方式：一種是全部更新（Fulldump），即拓撲更新消息中將包括整個路由表，主要應用于網絡變化較快的情況；另一種方式是部分更新（Incrementalupdate），更新消息中僅包含變化的路由部分，通常適用于網絡變化較慢的情況。在DSDV中只使用序列號最高的路由，如果兩個路由具有相同的序列號，那么將選擇最優的路由（如跳數最短）。NS實現DSDV路由協議的具體策略如下：一個沒有找到路由的分組到達節點后首先被緩存，同時節點發送路由查詢消息，直到接收到來自接收端的路由響應消息。當緩存溢出時，新來的分組將被丟棄。分組到達目的節點后將直接由地址解復用器送到相應的端口，而后由端口將分組送到目的代理。

2．2　動態源路由協議（DSR）

　　DSR是一種基于源路由的按需路由協議，它使用源路由算法而不是逐跳路由的方法。DSR主要包括兩個過程：路由發現和路由維護。當節點S向節點D發送數據時，它首先檢查緩存是否存在未過期的到目的節點的路由，如果存在，則直接使用可用的路由，否則啟動路由發現過程。具體過程如下：源節點S將使用洪泛法發送路由請求消息（RREQ），RREQ包含源和目的節點地址以及唯一的標志號，中間節點轉發RREQ，并附上自己的節點標識。當RREQ消息到達目的節點D或任何一個到目的節點路由的中間節點時（此時，RREQ中已記錄了從S到D或該中間節點的所經過的節點標識），D或該中間節點將向S發送路由應答消息（RREP），該消息中將包含S到　　D的路由信息，并反轉S到D的路由供RREP消息使用。此外，中間節點也可以使用路由緩存技術（Routing Cache）來對協議作進一步優化。DSR的優點：①節點僅需要維護與之通信的節點的路由，減少了協議開銷；②使用路由緩存技術減少了路由發現的耗費；③一次路由發現過程可能會產生多條到目的點的路由。DSR的缺點：①每個數據報文的頭部都需要攜帶路由信息，數據包的額外開銷較大；②路由請求消息采用洪泛方式，相鄰節點路由請求消息可能發生傳播沖突并可能會產生重復廣播；③由于緩存，過期路由會影響路由選擇的準確性。NS實現的DSR協議中，采用DSR的節點與其它移動節點有些不同，在DSR節點中，所有分組被送到路由代理，路由信息可通過數據分組進行捎帶確認。

2．3　臨時按序路由算法（TORA）

　　TORA是一個基于鏈路反轉方法的自適應的分布式路由算法，主要用于高速動態的多跳無線網絡。作為一個由源端發起的按需路由協議，它可以找到從源到一個目的節點的多條路由。TORA的主要特點是：當拓撲發生改變時，控制消息只在拓撲發生改變的局部范圍傳播。因此，節點只需維護相鄰節點的路由信息。協議由3部分構成：路由產生、路由維護和路由刪除。初始化時，目的節點的高度（即傳播序列號）被置為0。然后由源端廣播一個含有目的節點ID的QRY分組，一個高度不為0的節點響應一個UPD分組。收到UPD分組的節點的高度將比產生該UPD分組的節點的高度大1，并且具有較大高度值的節點被規定為上游節點。通過這種方式能夠創建一個從源到目的節點的一個有向無環路圖（DAG）。當節點移動時，路由需要重建。在路由刪除階段，TORA通過廣播一個CLR分組來刪除無效的路由。TORA存在的一個問題是當多個節點同時進行選路和刪除路由時會產生路由振蕩現象。NS中，每個節點為所有可能的目的節點運行一個分離的TORA進程。TORA運行在IMEP（IMEP：InternetMANETEncapsulation Protocol）之上，IMEP主要用來提供路由消息的可靠傳送并可以向鄰居節點通知鏈路的改變。

2．4　Ad hoc按需距離矢量路由協議（AODV）

　　AODV［6］是DSDV算法的改進，但它與DSDV的區別在于它是反應式路由協議。為了找到通往目的節點的路由，源端將廣播一個路由請求分組，鄰居節點依次向周圍節點廣播此分組直到該分組被送到一個知道目的節點路由信息中間節點或目的節點本身。一個節點將丟棄重復收到的請求分組，路由請求分組中的序列號用來防止路由環路，并能判斷中間節點是否響應了相應的路由請求。當節點轉發路由請求分組時，它會將其上游節點的標志ID錄入路由表，從而能夠構建一條從目的節點到源節點的反向路由。當源端移動時，它會重新發起路由發現算法；如果中間節點移動，那么與其相鄰的節點會發現鏈路失效并向其上游節點發送鏈路失效消息并一直傳到源節點，而后源節點根據情況重新發起路由發現過程。NS中，AODV的實現組合DSR和DSDV協議。它既具有DSR協議的路由發現和路由維護功能，同時又使用了DSDV采用的逐跳路由、序列號和Beacon消息。

3　模擬試驗和性能比較

　　模擬工具采用第2節介紹的NS2網絡仿真器，無線仿真開始時，需要定義每個網絡功能組件的類型，包括天線的類型、電磁波的傳輸模式和移動節點使用的Ad hoc路由選擇協議等。試驗中，網絡初始拓撲結構見圖1，該模型由3個移動節點（節點0，1和2）構成，并在670 m×670 m的范圍內按以下預定的移動模式移動。3個節點初始坐標為：節點0（83，239）、節點1（257，345）、節點2（591，199）。模擬開始運行后，在33 s時節點0以19 m／s速度向目標坐標（89，283）移動，在50 s時節點2以3．37 m／s的速度向目標坐標（369，173）移動，在51 s時節點1開始以14．90 m／s速度向目標坐標（221，80）移動。在節點0和節點2之間建立固定比特率（CBR）業務流，CBR的分組大小為512字節，發送間隔為4 s。并且在127s時，節點0開始向節點2發送CBR數據包，模擬的總時間設為400 s。圖2給出了在時間235 s時網絡的拓撲結構，此時3個節點已到達各自的目標，并且節點0正通過節點1向節點2發送CBR數據包。

　　在試驗中，分別使用第3節介紹的4種Ad hoc路由協議在相同的網絡環境下進行試驗，而后對模擬產生的數據進行分析來比較4種路由協議下CBR應用的性能。試驗的具體分析如下。

　　（1）采用DSDV協議的情況。模擬開始時節點0和節點1由于距離較近可以交換message路由消息，而節點2和其它2個節點距離較遠而無法交互路由消息。在時間94 s左右，節點1和節點2開始交換路由消息，并且節點0也可以通過節點1獲得節點2的路由信息。在127 s時，節點0開始向節點2發送CBR分組，最初CBR分組由于緩存空間不足或地址解析出錯等原因而被節點0丟棄，直到188 s時節點1才收到第一個CBR分組并將其轉發給節點2。在此次模擬中，三個節點總共發送了71條路由控制消息，節點0共發送了71個CBR包，并丟棄了15個CBR包。

　　（2）使用DSR協議。由于DSR是按需路由協議，模擬開始時節點之間不交互路由消息，直到節點0向節點2發送CBR包需要選路時才發送DSR消息。在整個模擬中，3個節點共發送了3條DSR路由控制消息，節點0共發送了68個CBR包，并丟棄了0個CBR包。

　　（3）采用TORA協議。由于TORA是按需路由協議，并且TORA運行在IMEP之上，因此，模擬開始時節點只發送IMEP消息，直到127 s時節點0才開始發送TORA選路消息。在整個模擬中，3個節點總共發送了1199條IMEP路由消息和1條TORA消息，節點0發送了71個CBR包，其中丟失了0個CBR包。

　　（4）使用AODV協議。AODV也是按需路由協議，模擬開始時節點不發送路由消息，直到127 s時，節點0開始發送CBR數據包時才發送AODV選路消息。在整個模擬中，3個節點總共發送了4條AODV消息，節點0發送了69個CBR包，其中丟失了0個CBR包。

　　（5）為了比較在不同網絡負載下路由協議運行的情況，以DSDV路由算法為例，將CBR的分組大小改為1024字節，并將CBR流的發送間隔改為0．5s，此時的網絡負載將明顯增加。將這種網絡負載環境下的DSDV協議稱為DSDVB，并對其進行相同的試驗。從整個模擬過程中可以發現：3個節點總共發送了97條message路由控制消息，而節點0總共發送了426個CBR包，但丟失了97個CBR包。

　　下面以分組投遞率和路由開銷為性能指標對以上路由協議進行比較。分組投遞率是指接收端收到的分組總數和發送端產生的分組總數之比，它可以反映網絡所能支持的最大吞吐量，從而在一定程度上刻畫了協議的完整性和正確性。路由開銷是指模擬期間傳輸的路由控制分組的總數，并且對一個需要經過多跳路由傳輸的分組而言，每一跳傳輸相當于一次分組傳輸［7］。路由開銷可以用來比較不同路由協議的可擴展性、適應網絡擁塞的能力和協議的效率。由測試數據得到的各協議的分組投遞率和路由開銷見表1。

　　分組投遞率：在相同的移動特性下，反應式路由協議（DSR、TORA以及AODV）的分組投遞率高，趨近100％（因為這里網絡開銷很小，使得分組投遞率達到100％）。而DSDV的分組投遞率最低，大約為79％。這是因為DSDV為目的節點只維護一個路由，當此路由失效時將沒有可以替換的路由。并且發現DSDVB協議的分組投遞率低于DSDV，這是因為分組投遞率將隨網絡負載的增加而減少，實際上網絡負載對其它路由協議也有類似的影響。

　　路由協議開銷：4種路由協議的開銷差別明顯，DSR開銷最小，TORA開銷最大。由于TORA、DSR和AODV都是按需路由協議，它們的開銷將隨著節點移動性的減小而降低，隨著網絡負載的增加而增加。DSDV是一個先驗式的路由協議，它的開銷基本上與節點移動性無關。由于DSR和AODV的特性相似，故它們的性能相似。由于DSR使用緩存技術和混雜接收方式偵聽路由請求分組，從而大大降低了路由開銷。TORA的開銷由恒定的與移動無關的路由開銷和可變的與移動相關的路由開銷兩部分構成，前者是由IMEP鄰居發現機制造成的，該機制要求每個節點在每個信號周期至少傳送1個HELLO分組，后者是指TORA用來產生和維護路由的路由分組以及IMEP用來確保可靠按序傳送的重傳和確認分組。因此TORA的路由開銷較大，并且當網絡負載較大時，路由開銷受節點移動性的影響減小。

4　結　論

　　本文介紹和分析了當前Ad hoc網絡采用的幾種路由協議，并且通過NS網絡仿真器對其中的4種路由算法進行了仿真分析和性能比較。結果表明不同的路由協議都有各自的應用場合和優缺點，設計一種萬能的路由協議是不現實的。一種較好的解決思路是采用結合先驗式和反應式路由協議的混合式路由，它能在盡量減少分組時延的前提下降低路由協議的開銷。例如文獻［10］中提出了一種基于分簇結構的分級路由算法，簇內使用先驗式路由算法，簇間按需尋找路由，并且根據網絡的動態變化可以自適應地調節簇的大小。這種路由算法吸取了2種路由算法的優點，具有較高的效率和較強的適應性，并且作者在文獻［8］中給出了相應的模擬結果。由于Ad hoc自身復雜多變的動態特性，路由協議的設計目前仍是一個人們關注的熱點問題。一種新的設計思路是采用自適應路由協議，它能夠根據不同的網絡環境來相應地改變路由算法，但這種方法的計算和維護開銷較大，實現比較復雜，目前正處于研究階段。此外，Ad hoc網絡中的QoS路由也是一個研究方向。總之，Ad hoc網絡的路由協議是一個比較復雜的問題，真正實現令人滿意的路由算法和機制還需要通過長期的探索和研究。　

參考文獻

［1］　MAGNUSFrodigh，PERJohansson．Wire－less Ad hoc networking－the art of network－ing without a network［J］．EriCSSon Review，2000（4）：248－262．

［2］　PADMINIMisra．Routing protocol for Adhoc mobile wireless network［EB／OL］．http：／／www．cis．ohio－state．edu／～jain／cis788－99／adhoc＿routing／index．html．

［3］　KEVIN Fall，KANNANVaradhan．The nsmanual．The VINT Project［EB／OL］．

http：／／www－mash．cs．berkeley．edu／ns，February，2001．

［4］　Mobile Ad hoc Networks（MANET）［EB／OL］．http：／／www．ietf．org／html．charters／manet－charter．html．2000（5）．

［5］　JOSHB，DAVIDA M，DAVIDBJ．A per－formance comparison of multi－hop wirelessAd hoc network routing protocols［C］．Mo－biCom98，Dallas，USA，October 1998．

［6］　CHARLESEPerkins，ELIZABETHM Roy－er，SAMIR RDas．Ad hoc on－demand dis－tance vector routing［EB／OL］．http：／／www．ietf．org／internet－drafts／draft－ietf－manet－aodv－04．txt，October 1999．

［7］　英春，史美林．自組網如何路由［J］．計算機世　　界，2000，（44期C版）：5－7．

［8］　BRUCEMcDonald，TAIEBFZnati．Scal－able routing strategies for Ad hoc wirelessnetworks［J］．IEEEJournalon Selected Ar－eas in Communications，1999，17（8）：1466－1487．

摘自　重慶郵電學院學報

上一篇：3G移動通信中的安全改進

下一篇：UMTS與WCDMA的關聯分析