摘 要： 移動Ad hoc是下一代網絡(NGN)的重要組成部分，無需固定基礎設施的臨時網絡。重點研究了目前典型的Ad hoc網絡的路由協議，設計并實現了在NS-2環境下典型協議的仿真場景和性能分析比較。對Ad hoc路由協議的研究和組網具有參考指導意義。
關鍵詞： Ad hoc網絡；仿真；路由協議
移動Ad hoc網絡是一種把移動通信和計算機網絡結合在一起的網絡，它具有分布式、自組織、自配置、自管理等特征，不需要固定基礎設施的支持，能夠在不能或不便利用現有網絡基礎設施的情況下提供一種通信支撐平臺，從而拓寬了移動通信網絡的應用場合，可廣泛應用于國防戰備、搶險救災、應對突發事件等無法得到有線網絡支持或只是臨時需要通信的環境，是下一代網絡的重要組成部分。
路由技術擔負著為數據分組尋找路由和將其傳送到目的地的任務，是移動Ad hoc網絡中的一項關鍵技術，而路由算法和協議則是路由技術的核心內容，直接關系到時延、吞吐率和成功率等網絡性能的優劣。移動Ad hoc網絡所具有的多跳、動態拓撲、時變信道、資源受限等特點，給路由算法和協議的設計帶來很大挑戰，傳統的有線網和有中心無線網絡的路由算法和協議無法在移動Ad hoc網絡中直接應用。為此，需要根據移動Ad hoc網絡的特點設計專門的路由算法和協議，這是移動Ad hoc網絡研究和設計的主要技術難點之一。網絡仿真模擬環境NS-2對Ad hoc網絡路由協議的研究提供了更為便捷的手段，本文對Ad hoc路由協議進行了分類研究，對典型的路由協議在NS-2環境下仿真實現，并對其性能進行跟蹤分析。對Ad hoc路由協議的研究具有參考意義。
1 Ad hoc網絡路由協議
路由是把信息從源經過中間網絡節點(至少有1個)穿過網絡傳遞到目的節點的行為，中間節點兩個基本的動作為確定最佳路徑和通過網絡傳輸信息，即選路和傳輸數據。傳輸數據相對來說比較簡單，而選擇路徑很復雜。
1.1 Ad hoc路由協議的研究分類
近年來，研究人員提出了上百種路由協議的方案。可以根據不同的原則進行分類研究：
(1)根據接收節點的數量[1]，可分為單播(unicast)：單播通信中目的節點只有一個，實現一對一的通信，單播路由協議是研究得最多的路由協議；組播(multicast，也被稱為多播)：一對多的通信，目前有基于樹的多播路由協議和基于網格的多播路由協議；廣播(broadcast)：所有主機都接收數據。
(2)根據路由發現的策略可以分為先應式(Poractvie)路由，也被稱為表驅動(Table-Driven)路由，以及反應式(Reactive)路由，也被稱為按需(On-Demand)路由[2]。表驅動路由協議采用周期性的路由分組廣播，交換路由信息。每個節點維護一張或多張表格，這些表格包含到達網絡中其他所有節點的路由信息。當主機需要和其他主機通信時，可以直接從路由表格中獲得相應的路由。當檢測到網絡拓撲結構發生變化時，節點在網絡中發送更新的消息，收到更新消息的節點更新自己的表格，以維護一致的、及時的、準確的路由信息。源節點一旦要發送報文，可以立即得到到達目的地的路由。但是不管有無通信需求，都要進行路由信息交換，它的優點是:當節點需要發送數據分組時，只要去往目的節點的路由存在，所需延時很小，比較適合有實時和QoS要求的網絡通信。但為了使路由更新能緊隨當前拓撲結構的變化，先應式路由協議需花費較大開銷，而且動態變化的拓撲結構可能使路由信息過時，路由協議不易收斂。表驅動路由協議主要有DSDV[3]、FSR[4]、DBF[5]、DTDV[6]、HSR[7]。按需驅動路由協議，也稱為被動路由協議。與表驅動路由協議相反，按需路由協議根據發送數據分組的需要按需進行路由發現的過程，主機只查找和維護自己需要使用的路由，而不是到所有主機的路由。所以其內容可能僅僅是整個網絡拓撲結構信息的一部分。典型的按需路由協議有DSR、AODV、TORA[8]。
(3)根據網絡邏輯視圖的不同，可分為平面(Flat)路由與分級(cluster-based)路由。平面路由協議的網絡邏輯視圖是平面結構，網絡結構比較簡單，路由協議在平面的邏輯空間里運行，移動節點的地位是平等的，即主機和主機都是平等的。它們所具有的功能完全相同，共同協作完成節點間的通信，每個主機同時還是路由器，負責為其他主機轉發報文。平面結構的網絡管理比較簡單，但路由開銷比較大，擴展性較差，支持的用戶節點較少，限制了網絡的規模；分級路由協議中，網絡由多個簇組成。節點分為兩種類型:普通節點和簇頭節點，處于同一簇的簇頭節點和普通節點共同維護所在簇內部的路由信息，簇頭節點負責所管轄簇的拓撲信息的壓縮和摘要處理，并與其他簇頭節點交換處理過后的拓撲信息。
1.2 三種典型的路由協議
1.2.1 目的節點序列距離矢量協議(DSDV)
DSDV是表驅動的平面路由協議，基于Bellman-Ford算法，通過給每個路由設定序列號避免路由環路的產生。在DSDV路由協議中，每個節點都必須存儲并維護一張路由表，該路由表記錄著目的節點、跳數、下一跳節點和目的節點序列號。其中目的節點序列號由目的節點分配，主要用于判別路由是否過時，并可防止路由環路的產生。每個節點必須周期性地與鄰節點交換路由表信息，以維持所有節點都擁有完整的路徑信息。當然也可以根據路由表的改變來觸發路由更新。DSDV節點維護著整個網絡的路由信息，數據需要發送時可以立即傳送，使用于一些實時性要求較高的網絡環境中。但是在拓撲變化頻繁的網絡中，DSDV存在一些問題：主要是節點維護路由信息的代價很高，因此不適用于規模大的網絡。
1.2.2 動態源路由協議(DSR)[9-10]
DSR是一種按需平面路由協議。每個節點都有路徑緩存器，而路徑信息則保存在每個封包的緩存標題中。當發送者發送報文時，在數據報文頭部攜帶到目的節點的路由信息，該路由信息由網絡中的若干節點地址組成，源節點的數據報文就通過這些節點的中繼轉發到達目的節點。與基于表驅動方式的路由協議不同的是，在DSR協議中，節點不需要實時維護網絡的拓撲信息，因此在節點需要發送數據時，如何能夠知道到達目的節點的路由是DSR路由協議需要解決的核心問題。路由發現過程是：源節點廣播路由請求分組給其鄰居節點，鄰居節點收到路由請求分組后，輪流把自己的地址添加到路由請求分組，并轉發補充了的路由請求分組。這個過程一直持續到有一個路由請求分組到達目的節點。
若發現自己的地址已經在記錄中，就停止廣播。每個請求都有一個由源節點所設置的ID號，每個節點都有一個路由緩存，存儲最近轉發過的路由請求，以便查詢接收的是否為同一個請求，這樣保證每個節點只轉發一次。當路由請求分組到達目的節點時，節點要返回一個路由應答分組，通知節點己收到該路由請求。到達目的節點的路由請求分組包含從源節點到目的節點的路由，目的節點就可以選擇利用反向路由來發送路由應答(這里必須是雙向鏈接的)，或者發起另一個新的路由發現過程返回到源節點。從源節點到目的節點可能有很多條路由，一個源節點可能從目的節點那里收到很多個路由應答。DSR協議把這些路由緩存在路由緩存中以備將來所用。DSR協議主機不需要周期性地發送路由發現報文，支持主機睡眠。但是數據收發的每個報文都需要攜帶完整的路由信息，減低了網絡帶寬的利用率。
1.2.3 AODV
AODV路由協議是一種按需路由協議，允許節點獲得許多路徑到達它所需要到達的目的節點，而且不要求節點維護這些路由信息。當網絡拓撲結構發生變化時，它能快速收斂，具有斷路的自我修復功能，不但計算量小，存儲資源消耗小，而且對網絡帶寬占用也小。通過使用目的節點序列號，協議實現了無環路由，并且避免了無窮計數的問題。為了避免單向鏈路引起的錯誤操作，協議引入了一個黑名單，把和自己是單向鏈路的鄰居節點放入黑名單中。
AODV有四種基本的協議幀:RREQ(Route Request)幀、RREP(Route Reply)幀、RERR(Route Error)幀和RREP-ACK幀格式。
當一個節點要傳送封包給另一個目的節點時，會先去檢查它的路由表。若找不到到達目的節點的路徑信息時，便廣播RREQ尋找路徑，收到RREQ的節點去檢查是否是發給自己的，如不是就查看是否有以自己為中繼的可達目的節點的路由，如沒有，就修改封包內的信息后廣播出去。每個RREQ都有一個ID，當節點收到RREQ后可以確認自己是否收到一個ID，如收到過久則丟棄，以確保循環的產生。
2 路由協議的性能分析
衡量Ad hoc網絡路由協議的性能一般有定性指標和定量指標兩種。
2.1 定性指標
定性指標從整體上描述網絡某個方面的性能，如安全性、分布運行性、提供無環路由、是否按需路由等。
MANET路由協議的定性屬性包括:
(1)適應動態拓撲：移動Ad hoc網絡是一種高度動態的網絡，其拓撲不斷變化，路由協議的設計要滿足拓撲的動態變化。
(2)減少控制開銷：移動節點通?？侩姵毓╇姡Y源有限，協議的設計要節約資源，控制開銷要小。
(3)分布式操作:這是一個基本屬性，但也應該被規定。
(4)無環路:雖然按照某些定量標準(如性能標準)來說不是必須的，但卻可以避免諸如最壞情況現象。
(5)基于需求的操作:在網絡中，讓路由算法適應基于按需流量模式，而不是假設一種不變的流量分布(在任何時刻在所有節點之間維護路由)，是一種更好的方法。如果可以智能地做到這一點，則可以更加有效地利用網絡能源和帶寬資源，其代價是增加了路由發現的延時。
(6)先應操作:基于需求操作比較不重要的方面。在某些情況下，基于需求操作增加的延時是不可接受的。如果帶寬和能源允許，在這種情況下，就需要先應式的操作。
(7)“睡眠”周期操作:基于能量保存，或其他某種非活動的需要，MANET節點在某段時間內可能會停止發送和/或接收。路由協議應該能適應這種睡眠周期，而不產生非常不利的后果。
(8)路由方式和路由更新方式:不同的路由方式和路由更新方式對協議的影響是巨大的，所有路由協議都必須有路由方式的效率和路由更新方式的效率。
典型協議定性分析如表1所示。
2.2 定量指標
定量指標可以更細致地刻畫網絡某方面的性能，本文主要對以下幾個性能指標進行分析:
(1)數據包成功接收率
數據包成功接收率是應用層信宿接收包數目與信源發送的包數目之比[11]。描述是通過應用層觀察到的丟包率，它是路由協議完整性和正確性的指標。
數據包成功接收率=成功接收分組數/發送分組數
(2)端到端平均時延
端到端的平均延遲包含所有可能的延遲時間的總和，如發現路徑的緩沖時間、MAC層的重傳時間、傳送時間等?？梢杂檬?1)計算：
式中，N表示成功傳輸的分組數，rti表示分組到達目的節點的時間，sti表示分組被發送的時間。
(3)路由開銷
路由開銷是計算所有路由控制報文(包括路由尋找報文、路由響應報文和路由錯誤控制報文)的總的字節數與所有報文的字節數之比。對于經過多跳路由傳輸的分組而言，每經過一跳，就增加一次報文傳輸。路由開銷主要是用來衡量路由協議的效率。
路由開銷=路由控制報文字節數/所有報文的字節數
(4)分組數據的丟包率
丟棄的數據包數/發送的數據包數
(5)第一個封包的接收時間參數用來評估路由協議的收斂時間。
3 基于NS-2仿真環境的路由協議性能分析
3.1 NS-2簡介和仿真場景建立
NS(Network Simulator)[12]網絡仿真器，網絡模擬器第二版NS-2(Network Simulator，Version 2)，最初是由美國加州大學伯克利分校(UC Berkeley)開發，目的是為了研究大規模網絡和未來網絡協議的交互行為。它是一款開放源代碼的網絡模擬軟件，一直以來都在吸收全世界各地研究者的成果，包括CMU大學和SUN等公司的無線網絡方面的代碼。
仿真實驗中，仿真時間設為120 s，所有節點一直處于移動狀態，業務代理設置為CBR流，最大的連接數為10條，每秒發出10個封包。在800 m×600 m的范圍內，節點數分別設為100、150、200、250、300、400，分別對三種典型路由協議進行仿真。
3.2 仿真結果及分析
對仿真后的trace文件進行分析，AODV結合了DSR和DSDV兩個協議的優點，因此一直有較高的數據包投遞率，而且較為穩定，但是DSR不適合規模較大的網絡。由圖1可知，當節點數量增多且不停移動時，DSDV封包的送達比例較低，原因是DSDV的路由表更新不夠快，當鏈路發生變化時，節點不能感知，還使用原來的路由發送數據，導致路由包的丟失。而DSR不適合規模大的網絡。
由圖2可知，在節點數量較小時，平均傳輸延遲相當，隨著節點數量的增加，DSDV比DSR和AODV大，說明DSDV路由表建立后，隨著節點移動和節點數的增加，需要更新路由表次數更頻繁，影響包傳送的時間。
以圖3中可以看出，DSR第一個封包的接收的時間比較早，AODV次之，DSDV最慢。說明DSDV雖然是表驅動的先應式路由協議，但是當節點都在移動時，不見得有可使用的路由協議，等到節點更新路由表時，已經花了一段時間。而DSR協議收斂的速度最快，AODV次之。
作為下一代網絡重要的組成部分，Ad hoc網絡成為目前的研究熱點之一，其關鍵技術路由協議的研究由于Ad hoc網絡拓撲動態變化、資源受限等特點成為具有挑戰性的課題。通過上面仿真分析可以看出，按需路由由于是表驅動的路由，也提出了多種按需路由方案。通過分析現有路由綜合其優點加以實現，還需要深入的研究。
參考文獻
[1] 任智.移動Ad Hoc網絡路由算法及協議研究[D].成都：電子科技大學博士學位論文，2005.
[2] ROYER E M， TOH C K. A review of current routing protocols for Ad-hoc mobile wireless networks[J]. IEEE Personal Communications， April， 1999:46-55.
[3] HARLES C， PERKINS E， BHAGWAT Pravin. Highly dynamic destination-sequenced distance-vector routing(DSDV) for mobile computers[A]. ACM SIGCOMM’94[C]， London， Sep， 1994:234-244.
[4] PEI G， GERLA M， CHEN T W. Fisheye state routing: A routing scheme for Ad hoc wireless networks[A]. Proc ICC2000[C]， New Orleans， LA， June， 2000.
[5] AWERBUCH B. Approximate distributed Bellman-Ford algorithms[J]. IEEE Transactions on Communieations， Au， 1994，42:2515-2517.
[6] HAGWAT P B， PERKINS C E. Highly dynamic destination-sequenced distance-vector routing(DTDV) for mobile computers[A]. In Proeeedings of the SIGCOMM’94 Conference on Communieations Architectures[C]， Protocols and Applications， 1994:234-244.
[7] PEI G. A wireless hierarchieal routing Protocol with Group Mobility[A]. IEEE ProeWCNC’99[C]， New Orleans， LA， Sept 1999.
[8] HONG Xiao Yan， XU Kai Xin， GERLA M. Scalable routing protocols for mobile adhoc networks[J]. IEEE Network， July-Aug 2002，16(4):11-21.
[9] JOHNSON D B， MALTZ D A. Dynamic source routing in Ad Hoc wireless networks[J]. Mobile Computing， T Imielinski， H Korth， Eds， Ch 5， Kluwer， 1996:153-81.
[10] JOHNSON D B， MALTZ D A， HU Y C. The dynamic source routing protocol for mobile Ad hoc networks(DSR)[Z]. Draft-ietf-manet-dsr-9.txt， Internet Draft， IETF MANET Working Group， July， 2004.
[11] 歐陽志鵬，沈富可.Ad Hoc網絡基于路由協議的擁塞控制[J].計算機工程與設計，2006(8):3102-310.
[12] The ns Manual.http://www.isi.edu/nsnam/ns/ns-documentation.html，2010.