相關專題：
（解放軍理工大學通信工程學院，江蘇南京210007）
摘 要：由于Ad hoc網絡自身的特殊性，其路由協(xié)議的設計與傳統(tǒng)固定網絡有很大不同。首先說明了Adhoc網絡中提供高效路由算法的難點，然后討論了Ad hoc網絡中路由協(xié)議設計的幾種策略，接著介紹了幾種典型的Ad hoc路由協(xié)議，最后通過實驗分析比較了4種路由協(xié)議的性能，并給出了結論。
關鍵詞：網絡模擬器；目的序列距離矢量路由；動態(tài)源路由；臨時按序路由；Ad hoc按需距離矢量路由
0 引 言
無線網絡通�？梢苑譃橛兄行木W絡和無中心網絡，前者需要固定基礎設施的支持，移動主機之間的通信通常借助基站來完成，例如蜂窩移動通信系統(tǒng)；后者主要是指移動Ad hoc網絡［1－4］，它不需要固定的基礎設施，能夠快速地自動組網。與有中心網絡相比，Ad hoc網絡靈活、健壯、投資少，特別適合于作戰(zhàn)指揮、搶險救災以及應付突發(fā)事件和執(zhí)行臨時任務的場合。在Ad hoc網絡中，每個移動節(jié)點兼?zhèn)渎酚善骱椭鳈C兩種功能。作為主機，移動節(jié)點需要運行面向用戶的應用程序；作為路由器，它需要運行相應的路由協(xié)議，根據路由策略和路由表參與數(shù)據分組轉發(fā)工作和路由維護工作�？紤]到Ad hoc網絡中節(jié)點是移動的，網絡的拓撲結構不斷變化，傳統(tǒng)的用于因特網的路由協(xié)議（如RIP、OSPF等）無法適應Adhoc網絡的實際需要［2］，同時由于移動節(jié)點的計算能力和存儲容量較低并且能源受限，要求路由協(xié)議盡量簡單，這又增加了Ad hoc網絡中路由協(xié)議設計的難度。
1 Ad hoc中路由協(xié)議的分類
Ad hoc網絡的路由協(xié)議大致可以分為先驗式（Proactive）路由協(xié)議、反應式（Reactive）路由協(xié)議以及混合式路由協(xié)議［2，5］。先驗式路由協(xié)議又稱為表驅動路由協(xié)議，在這種路由協(xié)議中，每個節(jié)點維護一張包含到達其它節(jié)點的路由信息的路由表。當檢測到網絡拓撲結構發(fā)生變化時，節(jié)點在網絡中發(fā)送更新消息，收到更新消息的節(jié)點將更新自己的路由表，以維護一致的、及時的、準確的路由信息，所以路由表可以準確地反映網絡的拓撲結構。源節(jié)點一旦要發(fā)送報文，可以立即獲得到達目的節(jié)點的路由。因此這種路由協(xié)議的時延較小，但是路由協(xié)議的開銷較大；反應式路由協(xié)議，又稱為按需路由協(xié)議，是一種當需要發(fā)送數(shù)據時才查找路由的路由算法。在這種路由協(xié)議中，節(jié)點不需要維護及時準確的路由信息，當向目的節(jié)點發(fā)送報文時，源節(jié)點才在網絡中發(fā)起路由查找過程，找到相應的路由。與先驗式路由協(xié)議相比，反應式路由協(xié)議的開銷較小，但是數(shù)據報傳送的時延較大。在Ad hoc網絡中單純采用先驗式或反應式路由協(xié)議都不能完全解決路由問題。在高速動態(tài)變化的Ad hoc網絡中，使用單純的先驗式路由協(xié)議會產生大量的控制報文，并且很多控制報文經常是無用的；如果單獨采用反應式路由協(xié)議，需要為每個報文查找路由，這也是不合理的（特別是當連續(xù)向某個目的節(jié)點發(fā)送多個報文時）。由此可見，應用結合先驗式和反應式路由協(xié)議優(yōu)點的混合式路由協(xié)議是一種較好的折衷方案。在局部范圍內使用先驗式路由協(xié)議，維護準確的路由信息，并可縮小路由控制消息傳播的范圍，當目標節(jié)點較遠時，通過查找發(fā)現(xiàn)路由，這樣既可以減少路由協(xié)議的開銷，時延特性也得到了改善。
2 4種典型的Ad hoc網絡路由算法
為了比較和驗證Ad hoc網絡中的路由協(xié)議的性能，采用了NS2網絡仿真器［4］進行試驗。NS2是由加利福尼亞大學伯克利分校和VINT項目組聯(lián)合開發(fā)的，是一個包含TCL（Tool Command Lan－guage：工具命令語言）語言的受事件驅動的網絡仿真器。這個仿真器通過NS的解釋程序被調用，解釋程序之間的所有相互作用通過一個專門的TCL程序完成。應用NS命令，可定義一個網絡拓撲，配置流量源和接收器，收集統(tǒng)計的數(shù)據等。NS2最初主要被用來模擬傳統(tǒng)有線網絡上的TCP協(xié)議和其他協(xié)議，它并不支持多跳無線移動網絡環(huán)境，隨著相關領域研究的進展，美國的CMU大學對NS2作了相應的擴展，目前，NS2已經可以支持一定范圍內和一定條件下的無線多跳移動網絡。
2．1 目的序列距離矢量路由協(xié)議（DSDV）
DSDV對Bellman－Ford路由算法進行了改進。
在DSDV中，每個移動節(jié)點都需要維護一個路由表。路由表表項包括目的節(jié)點、跳數(shù)和目的地序號，其中目的地序號由目的節(jié)點分配，主要用于判別路由是否過時，并可防止路由環(huán)路的產生。每個節(jié)點周期性必須與鄰節(jié)點交換路由信息，當然也可以根據路由表的改變來觸發(fā)路由更新。路由表更新有兩種方式：一種是全部更新（Fulldump），即拓撲更新消息中將包括整個路由表，主要應用于網絡變化較快的情況；另一種方式是部分更新（Incrementalupdate），更新消息中僅包含變化的路由部分，通常適用于網絡變化較慢的情況。在DSDV中只使用序列號最高的路由，如果兩個路由具有相同的序列號，那么將選擇最優(yōu)的路由（如跳數(shù)最短）。NS實現(xiàn)DSDV路由協(xié)議的具體策略如下：一個沒有找到路由的分組到達節(jié)點后首先被緩存，同時節(jié)點發(fā)送路由查詢消息，直到接收到來自接收端的路由響應消息。當緩存溢出時，新來的分組將被丟棄。分組到達目的節(jié)點后將直接由地址解復用器送到相應的端口，而后由端口將分組送到目的代理。
2．2 動態(tài)源路由協(xié)議（DSR）
DSR是一種基于源路由的按需路由協(xié)議，它使用源路由算法而不是逐跳路由的方法。DSR主要包括兩個過程：路由發(fā)現(xiàn)和路由維護。當節(jié)點S向節(jié)點D發(fā)送數(shù)據時，它首先檢查緩存是否存在未過期的到目的節(jié)點的路由，如果存在，則直接使用可用的路由，否則啟動路由發(fā)現(xiàn)過程。具體過程如下：源節(jié)點S將使用洪泛法發(fā)送路由請求消息（RREQ），RREQ包含源和目的節(jié)點地址以及唯一的標志號，中間節(jié)點轉發(fā)RREQ，并附上自己的節(jié)點標識。當RREQ消息到達目的節(jié)點D或任何一個到目的節(jié)點路由的中間節(jié)點時（此時，RREQ中已記錄了從S到D或該中間節(jié)點的所經過的節(jié)點標識），D或該中間節(jié)點將向S發(fā)送路由應答消息（RREP），該消息中將包含S到 D的路由信息，并反轉S到D的路由供RREP消息使用。此外，中間節(jié)點也可以使用路由緩存技術（Routing Cache）來對協(xié)議作進一步優(yōu)化。DSR的優(yōu)點：①節(jié)點僅需要維護與之通信的節(jié)點的路由，減少了協(xié)議開銷；②使用路由緩存技術減少了路由發(fā)現(xiàn)的耗費；③一次路由發(fā)現(xiàn)過程可能會產生多條到目的點的路由。DSR的缺點：①每個數(shù)據報文的頭部都需要攜帶路由信息，數(shù)據包的額外開銷較大；②路由請求消息采用洪泛方式，相鄰節(jié)點路由請求消息可能發(fā)生傳播沖突并可能會產生重復廣播；③由于緩存，過期路由會影響路由選擇的準確性。NS實現(xiàn)的DSR協(xié)議中，采用DSR的節(jié)點與其它移動節(jié)點有些不同，在DSR節(jié)點中，所有分組被送到路由代理，路由信息可通過數(shù)據分組進行捎帶確認。
2．3 臨時按序路由算法（TORA）
TORA是一個基于鏈路反轉方法的自適應的分布式路由算法，主要用于高速動態(tài)的多跳無線網絡。作為一個由源端發(fā)起的按需路由協(xié)議，它可以找到從源到一個目的節(jié)點的多條路由。TORA的主要特點是：當拓撲發(fā)生改變時，控制消息只在拓撲發(fā)生改變的局部范圍傳播。因此，節(jié)點只需維護相鄰節(jié)點的路由信息。協(xié)議由3部分構成：路由產生、路由維護和路由刪除。初始化時，目的節(jié)點的高度（即傳播序列號）被置為0。然后由源端廣播一個含有目的節(jié)點ID的QRY分組，一個高度不為0的節(jié)點響應一個UPD分組。收到UPD分組的節(jié)點的高度將比產生該UPD分組的節(jié)點的高度大1，并且具有較大高度值的節(jié)點被規(guī)定為上游節(jié)點。通過這種方式能夠創(chuàng)建一個從源到目的節(jié)點的一個有向無環(huán)路圖（DAG）。當節(jié)點移動時，路由需要重建。在路由刪除階段，TORA通過廣播一個CLR分組來刪除無效的路由。TORA存在的一個問題是當多個節(jié)點同時進行選路和刪除路由時會產生路由振蕩現(xiàn)象。NS中，每個節(jié)點為所有可能的目的節(jié)點運行一個分離的TORA進程。TORA運行在IMEP（IMEP：InternetMANETEncapsulation Protocol）之上，IMEP主要用來提供路由消息的可靠傳送并可以向鄰居節(jié)點通知鏈路的改變。
2．4 Ad hoc按需距離矢量路由協(xié)議（AODV）
AODV［6］是DSDV算法的改進，但它與DSDV的區(qū)別在于它是反應式路由協(xié)議。為了找到通往目的節(jié)點的路由，源端將廣播一個路由請求分組，鄰居節(jié)點依次向周圍節(jié)點廣播此分組直到該分組被送到一個知道目的節(jié)點路由信息中間節(jié)點或目的節(jié)點本身。一個節(jié)點將丟棄重復收到的請求分組，路由請求分組中的序列號用來防止路由環(huán)路，并能判斷中間節(jié)點是否響應了相應的路由請求。當節(jié)點轉發(fā)路由請求分組時，它會將其上游節(jié)點的標志ID錄入路由表，從而能夠構建一條從目的節(jié)點到源節(jié)點的反向路由。當源端移動時，它會重新發(fā)起路由發(fā)現(xiàn)算法；如果中間節(jié)點移動，那么與其相鄰的節(jié)點會發(fā)現(xiàn)鏈路失效并向其上游節(jié)點發(fā)送鏈路失效消息并一直傳到源節(jié)點，而后源節(jié)點根據情況重新發(fā)起路由發(fā)現(xiàn)過程。NS中，AODV的實現(xiàn)組合DSR和DSDV協(xié)議。它既具有DSR協(xié)議的路由發(fā)現(xiàn)和路由維護功能，同時又使用了DSDV采用的逐跳路由、序列號和Beacon消息。
3 模擬試驗和性能比較
模擬工具采用第2節(jié)介紹的NS2網絡仿真器，無線仿真開始時，需要定義每個網絡功能組件的類型，包括天線的類型、電磁波的傳輸模式和移動節(jié)點使用的Ad hoc路由選擇協(xié)議等。試驗中，網絡初始拓撲結構見圖1，該模型由3個移動節(jié)點（節(jié)點0，1和2）構成，并在670 m×670 m的范圍內按以下預定的移動模式移動。3個節(jié)點初始坐標為：節(jié)點0（83，239）、節(jié)點1（257，345）、節(jié)點2（591，199）。模擬開始運行后，在33 s時節(jié)點0以19 m／s速度向目標坐標（89，283）移動，在50 s時節(jié)點2以3．37 m／s的速度向目標坐標（369，173）移動，在51 s時節(jié)點1開始以14．90 m／s速度向目標坐標（221，80）移動。在節(jié)點0和節(jié)點2之間建立固定比特率（CBR）業(yè)務流，CBR的分組大小為512字節(jié)，發(fā)送間隔為4 s。并且在127s時，節(jié)點0開始向節(jié)點2發(fā)送CBR數(shù)據包，模擬的總時間設為400 s。圖2給出了在時間235 s時網絡的拓撲結構，此時3個節(jié)點已到達各自的目標，并且節(jié) 點0正通過節(jié)點1向節(jié)點2發(fā)送CBR數(shù)據包。
在試驗中，分別使用第3節(jié)介紹的4種Ad hoc路由協(xié)議在相同的網絡環(huán)境下進行試驗，而后對模擬產生的數(shù)據進行分析來比較4種路由協(xié)議下CBR應用的性能。試驗的具體分析如下。
�。�1）采用DSDV協(xié)議的情況。模擬開始時節(jié)點0和節(jié)點1由于距離較近可以交換message路由消息，而節(jié)點2和其它2個節(jié)點距離較遠而無法交互路由消息。在時間94 s左右，節(jié)點1和節(jié)點2開始交換路由消息，并且節(jié)點0也可以通過節(jié)點1獲得節(jié)點2的路由信息。在127 s時，節(jié)點0開始向節(jié)點2發(fā)送CBR分組，最初CBR分組由于緩存空間不足或地址解析出錯等原因而被節(jié)點0丟棄，直到188 s時節(jié)點1才收到第一個CBR分組并將其轉發(fā)給節(jié)點2。在此次模擬中，三個節(jié)點總共發(fā)送了71條路由控制消息，節(jié)點0共發(fā)送了71個CBR包，并丟棄了15個CBR包。
�。�2）使用DSR協(xié)議。由于DSR是按需路由協(xié)議，模擬開始時節(jié)點之間不交互路由消息，直到節(jié)點0向節(jié)點2發(fā)送CBR包需要選路時才發(fā)送DSR消息。在整個模擬中，3個節(jié)點共發(fā)送了3條DSR路由控制消息，節(jié)點0共發(fā)送了68個CBR包，并丟棄了0個CBR包。
（3）采用TORA協(xié)議。由于TORA是按需路由協(xié)議，并且TORA運行在IMEP之上，因此，模擬開始時節(jié)點只發(fā)送IMEP消息，直到127 s時節(jié)點0才開始發(fā)送TORA選路消息。在整個模擬中，3個節(jié)點總共發(fā)送了1199條IMEP路由消息和1條TORA消息，節(jié)點0發(fā)送了71個CBR包，其中丟失了0個CBR包。
�。�4）使用AODV協(xié)議。AODV也是按需路由協(xié)議，模擬開始時節(jié)點不發(fā)送路由消息，直到127 s時，節(jié)點0開始發(fā)送CBR數(shù)據包時才發(fā)送AODV選路消息。在整個模擬中，3個節(jié)點總共發(fā)送了4條AODV消息，節(jié)點0發(fā)送了69個CBR包，其中丟失了0個CBR包。
（5）為了比較在不同網絡負載下路由協(xié)議運行的情況，以DSDV路由算法為例，將CBR的分組大小改為1024字節(jié)，并將CBR流的發(fā)送間隔改為0．5s，此時的網絡負載將明顯增加。將這種網絡負載環(huán)境下的DSDV協(xié)議稱為DSDVB，并對其進行相同的試驗。從整個模擬過程中可以發(fā)現(xiàn)：3個節(jié)點總共發(fā)送了97條message路由控制消息，而節(jié)點0總共發(fā)送了426個CBR包，但丟失了97個CBR包。
下面以分組投遞率和路由開銷為性能指標對以上路由協(xié)議進行比較。分組投遞率是指接收端收到的分組總數(shù)和發(fā)送端產生的分組總數(shù)之比，它可以反映網絡所能支持的最大吞吐量，從而在一定程度上刻畫了協(xié)議的完整性和正確性。路由開銷是指模擬期間傳輸?shù)穆酚煽刂品纸M的總數(shù)，并且對一個需要經過多跳路由傳輸?shù)姆纸M而言，每一跳傳輸相當于一次分組傳輸［7］。路由開銷可以用來比較不同路由協(xié)議的可擴展性、適應網絡擁塞的能力和協(xié)議的效率。由測試數(shù)據得到的各協(xié)議的分組投遞率和路由開銷見表1。
分組投遞率：在相同的移動特性下，反應式路由協(xié)議（DSR、TORA以及AODV）的分組投遞率高，趨近100％（因為這里網絡開銷很小，使得分組投遞率達到100％）。而DSDV的分組投遞率最低，大約為79％。這是因為DSDV為目的節(jié)點只維護一個路由，當此路由失效時將沒有可以替換的路由。并且發(fā)現(xiàn)DSDVB協(xié)議的分組投遞率低于DSDV，這是因為分組投遞率將隨網絡負載的增加而減少，實際上網絡負載對其它路由協(xié)議也有類似的影響。
路由協(xié)議開銷：4種路由協(xié)議的開銷差別明顯，DSR開銷最小，TORA開銷最大。由于TORA、DSR和AODV都是按需路由協(xié)議，它們的開銷將隨著節(jié)點移動性的減小而降低，隨著網絡負載的增加而增加。DSDV是一個先驗式的路由協(xié)議，它的開銷基本上與節(jié)點移動性無關。由于DSR和AODV的特性相似，故它們的性能相似。由于DSR使用緩存技術和混雜接收方式偵聽路由請求分組，從而大大降低了路由開銷。TORA的開銷由恒定的與移動無關的路由開銷和可變的與移動相關的路由開銷兩部分構成，前者是由IMEP鄰居發(fā)現(xiàn)機制造成的，該機制要求每個節(jié)點在每個信號周期至少傳送1個HELLO分組，后者是指TORA用來產生和維護路由的路由分組以及IMEP用來確�？煽堪葱騻魉偷闹貍骱痛_認分組。因此TORA的路由開銷較大，并且當網絡負載較大時，路由開銷受節(jié)點移動性的影響減小。
4 結 論
本文介紹和分析了當前Ad hoc網絡采用的幾種路由協(xié)議，并且通過NS網絡仿真器對其中的4種路由算法進行了仿真分析和性能比較。結果表明不同的路由協(xié)議都有各自的應用場合和優(yōu)缺點，設計一種萬能的路由協(xié)議是不現(xiàn)實的。一種較好的解決思路是采用結合先驗式和反應式路由協(xié)議的混合式路由，它能在盡量減少分組時延的前提下降低路由協(xié)議的開銷。例如文獻［10］中提出了一種基于分簇結構的分級路由算法，簇內使用先驗式路由算法，簇間按需尋找路由，并且根據網絡的動態(tài)變化可以自適應地調節(jié)簇的大小。這種路由算法吸取了2種路由算法的優(yōu)點，具有較高的效率和較強的適應性，并且作者在文獻［8］中給出了相應的模擬結果。由于Ad hoc自身復雜多變的動態(tài)特性，路由協(xié)議的設計目前仍是一個人們關注的熱點問題。一種新的設計思路是采用自適應路由協(xié)議，它能夠根據不同的網絡環(huán)境來相應地改變路由算法，但這種方法的計算和維護開銷較大，實現(xiàn)比較復雜，目前正處于研究階段。此外，Ad hoc網絡中的QoS路由也是一個研究方向。總之，Ad hoc網絡的路由協(xié)議是一個比較復雜的問題，真正實現(xiàn)令人滿意的路由算法和機制還需要通過長期的探索和研究。
參考文獻
［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，F(xiàn)ebruary，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－h(huán)op 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．
摘自 重慶郵電學院學報
