摘 要： 移動Ad hoc是下一代網(wǎng)絡(NGN)的重要組成部分，無需固定基礎設施的臨時網(wǎng)絡。重點研究了目前典型的Ad hoc網(wǎng)絡的路由協(xié)議，設計并實現(xiàn)了在NS-2環(huán)境下典型協(xié)議的仿真場景和性能分析比較。對Ad hoc路由協(xié)議的研究和組網(wǎng)具有參考指導意義。
關鍵詞： Ad hoc網(wǎng)絡；仿真；路由協(xié)議
移動Ad hoc網(wǎng)絡是一種把移動通信和計算機網(wǎng)絡結(jié)合在一起的網(wǎng)絡，它具有分布式、自組織、自配置、自管理等特征，不需要固定基礎設施的支持，能夠在不能或不便利用現(xiàn)有網(wǎng)絡基礎設施的情況下提供一種通信支撐平臺，從而拓寬了移動通信網(wǎng)絡的應用場合，可廣泛應用于國防戰(zhàn)備、搶險救災、應對突發(fā)事件等無法得到有線網(wǎng)絡支持或只是臨時需要通信的環(huán)境，是下一代網(wǎng)絡的重要組成部分。
路由技術(shù)擔負著為數(shù)據(jù)分組尋找路由和將其傳送到目的地的任務，是移動Ad hoc網(wǎng)絡中的一項關鍵技術(shù)，而路由算法和協(xié)議則是路由技術(shù)的核心內(nèi)容，直接關系到時延、吞吐率和成功率等網(wǎng)絡性能的優(yōu)劣。移動Ad hoc網(wǎng)絡所具有的多跳、動態(tài)拓撲、時變信道、資源受限等特點，給路由算法和協(xié)議的設計帶來很大挑戰(zhàn)，傳統(tǒng)的有線網(wǎng)和有中心無線網(wǎng)絡的路由算法和協(xié)議無法在移動Ad hoc網(wǎng)絡中直接應用。為此，需要根據(jù)移動Ad hoc網(wǎng)絡的特點設計專門的路由算法和協(xié)議，這是移動Ad hoc網(wǎng)絡研究和設計的主要技術(shù)難點之一。網(wǎng)絡仿真模擬環(huán)境NS-2對Ad hoc網(wǎng)絡路由協(xié)議的研究提供了更為便捷的手段，本文對Ad hoc路由協(xié)議進行了分類研究，對典型的路由協(xié)議在NS-2環(huán)境下仿真實現(xiàn)，并對其性能進行跟蹤分析。對Ad hoc路由協(xié)議的研究具有參考意義。
1 Ad hoc網(wǎng)絡路由協(xié)議
路由是把信息從源經(jīng)過中間網(wǎng)絡節(jié)點(至少有1個)穿過網(wǎng)絡傳遞到目的節(jié)點的行為，中間節(jié)點兩個基本的動作為確定最佳路徑和通過網(wǎng)絡傳輸信息，即選路和傳輸數(shù)據(jù)。傳輸數(shù)據(jù)相對來說比較簡單，而選擇路徑很復雜。
1.1 Ad hoc路由協(xié)議的研究分類
近年來，研究人員提出了上百種路由協(xié)議的方案?？梢愿鶕?jù)不同的原則進行分類研究：
(1)根據(jù)接收節(jié)點的數(shù)量[1]，可分為單播(unicast)：單播通信中目的節(jié)點只有一個，實現(xiàn)一對一的通信，單播路由協(xié)議是研究得最多的路由協(xié)議；組播(multicast，也被稱為多播)：一對多的通信，目前有基于樹的多播路由協(xié)議和基于網(wǎng)格的多播路由協(xié)議；廣播(broadcast)：所有主機都接收數(shù)據(jù)。
(2)根據(jù)路由發(fā)現(xiàn)的策略可以分為先應式(Poractvie)路由，也被稱為表驅(qū)動(Table-Driven)路由，以及反應式(Reactive)路由，也被稱為按需(On-Demand)路由[2]。表驅(qū)動路由協(xié)議采用周期性的路由分組廣播，交換路由信息。每個節(jié)點維護一張或多張表格，這些表格包含到達網(wǎng)絡中其他所有節(jié)點的路由信息。當主機需要和其他主機通信時，可以直接從路由表格中獲得相應的路由。當檢測到網(wǎng)絡拓撲結(jié)構(gòu)發(fā)生變化時，節(jié)點在網(wǎng)絡中發(fā)送更新的消息，收到更新消息的節(jié)點更新自己的表格，以維護一致的、及時的、準確的路由信息。源節(jié)點一旦要發(fā)送報文，可以立即得到到達目的地的路由。但是不管有無通信需求，都要進行路由信息交換，它的優(yōu)點是:當節(jié)點需要發(fā)送數(shù)據(jù)分組時，只要去往目的節(jié)點的路由存在，所需延時很小，比較適合有實時和QoS要求的網(wǎng)絡通信。但為了使路由更新能緊隨當前拓撲結(jié)構(gòu)的變化，先應式路由協(xié)議需花費較大開銷，而且動態(tài)變化的拓撲結(jié)構(gòu)可能使路由信息過時，路由協(xié)議不易收斂。表驅(qū)動路由協(xié)議主要有DSDV[3]、FSR[4]、DBF[5]、DTDV[6]、HSR[7]。按需驅(qū)動路由協(xié)議，也稱為被動路由協(xié)議。與表驅(qū)動路由協(xié)議相反，按需路由協(xié)議根據(jù)發(fā)送數(shù)據(jù)分組的需要按需進行路由發(fā)現(xiàn)的過程，主機只查找和維護自己需要使用的路由，而不是到所有主機的路由。所以其內(nèi)容可能僅僅是整個網(wǎng)絡拓撲結(jié)構(gòu)信息的一部分。典型的按需路由協(xié)議有DSR、AODV、TORA[8]。
(3)根據(jù)網(wǎng)絡邏輯視圖的不同，可分為平面(Flat)路由與分級(cluster-based)路由。平面路由協(xié)議的網(wǎng)絡邏輯視圖是平面結(jié)構(gòu)，網(wǎng)絡結(jié)構(gòu)比較簡單，路由協(xié)議在平面的邏輯空間里運行，移動節(jié)點的地位是平等的，即主機和主機都是平等的。它們所具有的功能完全相同，共同協(xié)作完成節(jié)點間的通信，每個主機同時還是路由器，負責為其他主機轉(zhuǎn)發(fā)報文。平面結(jié)構(gòu)的網(wǎng)絡管理比較簡單，但路由開銷比較大，擴展性較差，支持的用戶節(jié)點較少，限制了網(wǎng)絡的規(guī)模；分級路由協(xié)議中，網(wǎng)絡由多個簇組成。節(jié)點分為兩種類型:普通節(jié)點和簇頭節(jié)點，處于同一簇的簇頭節(jié)點和普通節(jié)點共同維護所在簇內(nèi)部的路由信息，簇頭節(jié)點負責所管轄簇的拓撲信息的壓縮和摘要處理，并與其他簇頭節(jié)點交換處理過后的拓撲信息。
1.2 三種典型的路由協(xié)議
1.2.1 目的節(jié)點序列距離矢量協(xié)議(DSDV)
DSDV是表驅(qū)動的平面路由協(xié)議，基于Bellman-Ford算法，通過給每個路由設定序列號避免路由環(huán)路的產(chǎn)生。在DSDV路由協(xié)議中，每個節(jié)點都必須存儲并維護一張路由表，該路由表記錄著目的節(jié)點、跳數(shù)、下一跳節(jié)點和目的節(jié)點序列號。其中目的節(jié)點序列號由目的節(jié)點分配，主要用于判別路由是否過時，并可防止路由環(huán)路的產(chǎn)生。每個節(jié)點必須周期性地與鄰節(jié)點交換路由表信息，以維持所有節(jié)點都擁有完整的路徑信息。當然也可以根據(jù)路由表的改變來觸發(fā)路由更新。DSDV節(jié)點維護著整個網(wǎng)絡的路由信息，數(shù)據(jù)需要發(fā)送時可以立即傳送，使用于一些實時性要求較高的網(wǎng)絡環(huán)境中。但是在拓撲變化頻繁的網(wǎng)絡中，DSDV存在一些問題：主要是節(jié)點維護路由信息的代價很高，因此不適用于規(guī)模大的網(wǎng)絡。
1.2.2 動態(tài)源路由協(xié)議(DSR)[9-10]
DSR是一種按需平面路由協(xié)議。每個節(jié)點都有路徑緩存器，而路徑信息則保存在每個封包的緩存標題中。當發(fā)送者發(fā)送報文時，在數(shù)據(jù)報文頭部攜帶到目的節(jié)點的路由信息，該路由信息由網(wǎng)絡中的若干節(jié)點地址組成，源節(jié)點的數(shù)據(jù)報文就通過這些節(jié)點的中繼轉(zhuǎn)發(fā)到達目的節(jié)點。與基于表驅(qū)動方式的路由協(xié)議不同的是，在DSR協(xié)議中，節(jié)點不需要實時維護網(wǎng)絡的拓撲信息，因此在節(jié)點需要發(fā)送數(shù)據(jù)時，如何能夠知道到達目的節(jié)點的路由是DSR路由協(xié)議需要解決的核心問題。路由發(fā)現(xiàn)過程是：源節(jié)點廣播路由請求分組給其鄰居節(jié)點，鄰居節(jié)點收到路由請求分組后，輪流把自己的地址添加到路由請求分組，并轉(zhuǎn)發(fā)補充了的路由請求分組。這個過程一直持續(xù)到有一個路由請求分組到達目的節(jié)點。
若發(fā)現(xiàn)自己的地址已經(jīng)在記錄中，就停止廣播。每個請求都有一個由源節(jié)點所設置的ID號，每個節(jié)點都有一個路由緩存，存儲最近轉(zhuǎn)發(fā)過的路由請求，以便查詢接收的是否為同一個請求，這樣保證每個節(jié)點只轉(zhuǎn)發(fā)一次。當路由請求分組到達目的節(jié)點時，節(jié)點要返回一個路由應答分組，通知節(jié)點己收到該路由請求。到達目的節(jié)點的路由請求分組包含從源節(jié)點到目的節(jié)點的路由，目的節(jié)點就可以選擇利用反向路由來發(fā)送路由應答(這里必須是雙向鏈接的)，或者發(fā)起另一個新的路由發(fā)現(xiàn)過程返回到源節(jié)點。從源節(jié)點到目的節(jié)點可能有很多條路由，一個源節(jié)點可能從目的節(jié)點那里收到很多個路由應答。DSR協(xié)議把這些路由緩存在路由緩存中以備將來所用。DSR協(xié)議主機不需要周期性地發(fā)送路由發(fā)現(xiàn)報文，支持主機睡眠。但是數(shù)據(jù)收發(fā)的每個報文都需要攜帶完整的路由信息，減低了網(wǎng)絡帶寬的利用率。
1.2.3 AODV
AODV路由協(xié)議是一種按需路由協(xié)議，允許節(jié)點獲得許多路徑到達它所需要到達的目的節(jié)點，而且不要求節(jié)點維護這些路由信息。當網(wǎng)絡拓撲結(jié)構(gòu)發(fā)生變化時，它能快速收斂，具有斷路的自我修復功能，不但計算量小，存儲資源消耗小，而且對網(wǎng)絡帶寬占用也小。通過使用目的節(jié)點序列號，協(xié)議實現(xiàn)了無環(huán)路由，并且避免了無窮計數(shù)的問題。為了避免單向鏈路引起的錯誤操作，協(xié)議引入了一個黑名單，把和自己是單向鏈路的鄰居節(jié)點放入黑名單中。
AODV有四種基本的協(xié)議幀:RREQ(Route Request)幀、RREP(Route Reply)幀、RERR(Route Error)幀和RREP-ACK幀格式。
當一個節(jié)點要傳送封包給另一個目的節(jié)點時，會先去檢查它的路由表。若找不到到達目的節(jié)點的路徑信息時，便廣播RREQ尋找路徑，收到RREQ的節(jié)點去檢查是否是發(fā)給自己的，如不是就查看是否有以自己為中繼的可達目的節(jié)點的路由，如沒有，就修改封包內(nèi)的信息后廣播出去。每個RREQ都有一個ID，當節(jié)點收到RREQ后可以確認自己是否收到一個ID，如收到過久則丟棄，以確保循環(huán)的產(chǎn)生。
2 路由協(xié)議的性能分析
衡量Ad hoc網(wǎng)絡路由協(xié)議的性能一般有定性指標和定量指標兩種。
2.1 定性指標
定性指標從整體上描述網(wǎng)絡某個方面的性能，如安全性、分布運行性、提供無環(huán)路由、是否按需路由等。
MANET路由協(xié)議的定性屬性包括:
(1)適應動態(tài)拓撲：移動Ad hoc網(wǎng)絡是一種高度動態(tài)的網(wǎng)絡，其拓撲不斷變化，路由協(xié)議的設計要滿足拓撲的動態(tài)變化。
(2)減少控制開銷：移動節(jié)點通?？侩姵毓╇?，資源有限，協(xié)議的設計要節(jié)約資源，控制開銷要小。
(3)分布式操作:這是一個基本屬性，但也應該被規(guī)定。
(4)無環(huán)路:雖然按照某些定量標準(如性能標準)來說不是必須的，但卻可以避免諸如最壞情況現(xiàn)象。
(5)基于需求的操作:在網(wǎng)絡中，讓路由算法適應基于按需流量模式，而不是假設一種不變的流量分布(在任何時刻在所有節(jié)點之間維護路由)，是一種更好的方法。如果可以智能地做到這一點，則可以更加有效地利用網(wǎng)絡能源和帶寬資源，其代價是增加了路由發(fā)現(xiàn)的延時。
(6)先應操作:基于需求操作比較不重要的方面。在某些情況下，基于需求操作增加的延時是不可接受的。如果帶寬和能源允許，在這種情況下，就需要先應式的操作。
(7)“睡眠”周期操作:基于能量保存，或其他某種非活動的需要，MANET節(jié)點在某段時間內(nèi)可能會停止發(fā)送和/或接收。路由協(xié)議應該能適應這種睡眠周期，而不產(chǎn)生非常不利的后果。
(8)路由方式和路由更新方式:不同的路由方式和路由更新方式對協(xié)議的影響是巨大的，所有路由協(xié)議都必須有路由方式的效率和路由更新方式的效率。
典型協(xié)議定性分析如表1所示。
2.2 定量指標
定量指標可以更細致地刻畫網(wǎng)絡某方面的性能，本文主要對以下幾個性能指標進行分析:
(1)數(shù)據(jù)包成功接收率
數(shù)據(jù)包成功接收率是應用層信宿接收包數(shù)目與信源發(fā)送的包數(shù)目之比[11]。描述是通過應用層觀察到的丟包率，它是路由協(xié)議完整性和正確性的指標。
數(shù)據(jù)包成功接收率=成功接收分組數(shù)/發(fā)送分組數(shù)
(2)端到端平均時延
端到端的平均延遲包含所有可能的延遲時間的總和，如發(fā)現(xiàn)路徑的緩沖時間、MAC層的重傳時間、傳送時間等。可以用式(1)計算：
式中，N表示成功傳輸?shù)姆纸M數(shù)，rti表示分組到達目的節(jié)點的時間，sti表示分組被發(fā)送的時間。
(3)路由開銷
路由開銷是計算所有路由控制報文(包括路由尋找報文、路由響應報文和路由錯誤控制報文)的總的字節(jié)數(shù)與所有報文的字節(jié)數(shù)之比。對于經(jīng)過多跳路由傳輸?shù)姆纸M而言，每經(jīng)過一跳，就增加一次報文傳輸。路由開銷主要是用來衡量路由協(xié)議的效率。
路由開銷=路由控制報文字節(jié)數(shù)/所有報文的字節(jié)數(shù)
(4)分組數(shù)據(jù)的丟包率
丟棄的數(shù)據(jù)包數(shù)/發(fā)送的數(shù)據(jù)包數(shù)
(5)第一個封包的接收時間參數(shù)用來評估路由協(xié)議的收斂時間。
3 基于NS-2仿真環(huán)境的路由協(xié)議性能分析
3.1 NS-2簡介和仿真場景建立
NS(Network Simulator)[12]網(wǎng)絡仿真器，網(wǎng)絡模擬器第二版NS-2(Network Simulator，Version 2)，最初是由美國加州大學伯克利分校(UC Berkeley)開發(fā)，目的是為了研究大規(guī)模網(wǎng)絡和未來網(wǎng)絡協(xié)議的交互行為。它是一款開放源代碼的網(wǎng)絡模擬軟件，一直以來都在吸收全世界各地研究者的成果，包括CMU大學和SUN等公司的無線網(wǎng)絡方面的代碼。
仿真實驗中，仿真時間設為120 s，所有節(jié)點一直處于移動狀態(tài)，業(yè)務代理設置為CBR流，最大的連接數(shù)為10條，每秒發(fā)出10個封包。在800 m×600 m的范圍內(nèi)，節(jié)點數(shù)分別設為100、150、200、250、300、400，分別對三種典型路由協(xié)議進行仿真。
3.2 仿真結(jié)果及分析
對仿真后的trace文件進行分析，AODV結(jié)合了DSR和DSDV兩個協(xié)議的優(yōu)點，因此一直有較高的數(shù)據(jù)包投遞率，而且較為穩(wěn)定，但是DSR不適合規(guī)模較大的網(wǎng)絡。由圖1可知，當節(jié)點數(shù)量增多且不停移動時，DSDV封包的送達比例較低，原因是DSDV的路由表更新不夠快，當鏈路發(fā)生變化時，節(jié)點不能感知，還使用原來的路由發(fā)送數(shù)據(jù)，導致路由包的丟失。而DSR不適合規(guī)模大的網(wǎng)絡。
由圖2可知，在節(jié)點數(shù)量較小時，平均傳輸延遲相當，隨著節(jié)點數(shù)量的增加，DSDV比DSR和AODV大，說明DSDV路由表建立后，隨著節(jié)點移動和節(jié)點數(shù)的增加，需要更新路由表次數(shù)更頻繁，影響包傳送的時間。
以圖3中可以看出，DSR第一個封包的接收的時間比較早，AODV次之，DSDV最慢。說明DSDV雖然是表驅(qū)動的先應式路由協(xié)議，但是當節(jié)點都在移動時，不見得有可使用的路由協(xié)議，等到節(jié)點更新路由表時，已經(jīng)花了一段時間。而DSR協(xié)議收斂的速度最快，AODV次之。
作為下一代網(wǎng)絡重要的組成部分，Ad hoc網(wǎng)絡成為目前的研究熱點之一，其關鍵技術(shù)路由協(xié)議的研究由于Ad hoc網(wǎng)絡拓撲動態(tài)變化、資源受限等特點成為具有挑戰(zhàn)性的課題。通過上面仿真分析可以看出，按需路由由于是表驅(qū)動的路由，也提出了多種按需路由方案。通過分析現(xiàn)有路由綜合其優(yōu)點加以實現(xiàn)，還需要深入的研究。
參考文獻
[1] 任智.移動Ad Hoc網(wǎng)絡路由算法及協(xié)議研究[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網(wǎng)絡基于路由協(xié)議的擁塞控制[J].計算機工程與設計，2006(8):3102-310.
[12] The ns Manual.http://www.isi.edu/nsnam/ns/ns-documentation.html，2010.