1、收稿日期:2009-04-18;修回日期:2009-07-09基金項目:國家自然科學基金(96012003作者簡介:金 偉(1985-,男,碩士研究生,研究方向為網絡模擬;劉方愛,教授,博士生導師,研究方向為網格計算、分布式計算。基于NS 的Ad hoc 網絡路由協議仿真研究金 偉1,劉方愛1,王曉潔2(11山東師范大學信息科學與工程學院,山東濟南250014;21山東大學數學科學學院,山東濟南250014摘 要:運用NS2網絡仿真模擬軟件對Ad hoc 移動自組網絡三種典型路由協議D SD V 、DSR 、AOD V 在不同網絡拓撲復雜度環境下進行仿真模擬,提取部分仿真數據進行分析,從數據包

2、發送率、端到端延時、路由開銷三個方面綜合比較Ad hoc 網絡三種典型路由協議的優缺點;引入NS2節點能量模型,分析仿真過程中節點能量變化。仿真結果表明,隨著網絡拓撲復雜性的增加,AOD V 路由協議較其它兩種路由協議更具可行性與有效性。關鍵詞:Ad hoc 網絡;NS 仿真;能量模型中圖分類號:TP393 文獻標識碼:A 文章編號:1673-629X (201001-0063-04Simulation Research of Ad hoc Routing Protocols Based on NSJIN Wei 1,LIU Fang 2ai 1,WANG Xiao 2jie 2(1.Scho

3、ol of Information Science and Engineering,Shandong Normal University,Jinan 250014,China;2.School of Mathematics,Shandong University,Jinan 250014,ChinaAbstr act:Analyzes and compares three tipical routing protocols:DSDV,DSR and AODV for Ad hoc network,and then simulates the re 2sults with NS2in diffe

4、rent net topology com plexity,and shows the performances of them in recv/send rate of node,end-to-end delay and routing overhead by analyzing part of simulation data.Finally,analyzes th e change about energy of nodes in simulation by energy model in NS2.The simulation results that the on-demand prot

5、ocol AODV provides better feasibili ty an d effectivity when the net topol o 2gy becomes complex.Key wor ds:Ad hoc network;NS si mulation;energy model0 引 言移動通信網絡是有中心的、基于預設網絡設施運行的網絡。例如手機等移動通訊工具需要基站的支持;無線局域網也需要有接入點和有線骨干網模式才能工作。但某些特殊場合,有中心的移動網絡并不能勝任。比如戰場上部隊快速展開和推進,地震或水災營救等。這些場合的通信不依賴任何預設的網絡設施,而需要一種能夠臨時

6、快速自動組網的移動網絡。因此,一種新的網絡技術同時作為移動通信的一種特殊形式移動自組網1(Mobil Ad hoc Network,MANET,也稱移動Ad hoc 網絡應運而生。移動Ad hoc 網絡2是一種特殊的無控制中心的無線網絡。網絡中的節點兼有主機和路由器功能,二者作為同等實體連接在一起。不相鄰的節點之間的通信依靠網絡中其它節點作為中繼節點實現。Ad hoc 網絡的特點使其相應的路由協議面臨挑戰。根據對網線拓撲結構的不同反應(即路由發現策略,Ad hoc 網絡路由協議2可以分為表驅動(Table Driven路由協議,或者稱為先驗式路由協議、主動(proac t ive路由協議和按需

7、(on-demand驅動路由協議,也稱為被動(react ive路由協議。Ad hoc 網絡路由協議種類繁多,典型Ad hoc 網絡路由協議有DSDV 、DSR 、AODV 。文中運用NS 網絡模擬軟件,從數據包發送成功率、端到端延時、路由開銷三方面綜合比較三種路由協議優缺點,在此基礎上引入NS 能量模型,分析復雜網絡拓撲環境中節點能量變化。仿真結果表明,按需驅動路由協議AODV 較其他兩種協議更具可行性與有效性。1 Ad-hoc 路由協議1.1 DSDV(Destination S equence Distance Vect orDSDV 協議基于有線路由協議中的距離矢量協第20卷 第1期2

8、010年1月 計算機技術與發展COM PUT ER TECHNOLOGY AND DEVELOPMENTVol.20 No.1Jan. 2010議3。該路由算法中,Ad-hoc 網絡中的每一個節點都保持一張完整路由表,路由表中記錄從該節點到網絡中其他節點的路由信息,包括跳數以及下一跳地址等。DSDV 協議通過目的序號來消除環路問題,每一條路由項都和一個目的序列號相關,該目的序列號表示了對應路由的新舊程度,由目的節點產生,當某一節點檢測到相鄰節點的鏈路中斷時可以產生新的路由更新消息,當節點發現自己移動時,就會產生具有新的序號的路由。1.2 DSR(Dynamic Source RoutingDS

9、R 是一種基于源路由方式的按需路由協議4,是按需路由協議的一個典型代表。在DSR 協議中,發送者發送報文,在數據報文頭部攜帶到目的節點的路由信息,該路由信息由網絡中的若干節點地址組成,源節點的數據報文就通過這些節點的中繼轉發到達目的節點。與基于表驅動方式的路由協議不同的是,在DSR 協議中,節點不需要實時維護網絡拓撲信息,因此在節點需要發送數據時,如何能夠知道到達目的節點的路由是DSR 路由協議需要解決的核心問題。1.3 AODV(Ad hoc On De mand Distance VectorAODV 也是一種按需路由協議5,它綜合了DS 2DV 和DSR 兩個協議的特點。AODV 吸取了

10、DSDV 中逐跳、序列號和周期性廣播機制,但是它又是按需路由,所以網絡中節點不需要實時維護整個網絡的拓撲信息,只是在發送報文而又沒有到達目的節點的路由時才發起路由請求過程。AODV 吸取了DSR 中路由發現和路由維護的思想,但是AODV 的數據報文頭部不再需要攜帶完整路徑,減少了數據報文頭部路由信息對信道的占用,提高了系統效率。AODV 同時也支持多播機制。表1是以上三種典型Ad hoc 網絡路由協議的比較。表1 三種典型Ad hoc 網絡路由協議的比較路由協議類型優點缺點DS DV 發送分組時延時很小存在儲存和計算負擔,浪費帶寬D SR 節省能源和帶寬,快速獲得路由網絡帶寬利用率低,存在過時

11、路由AODV降低信道占用率,提高系統效率需要對稱鏈路,路由存在刪除可能2 NS2仿真Ad hoc 路由協議NS26全稱是Net work Simulat or Version2。它是面向對象的,離散事件驅動的網絡環境模擬器,主要用于解決網絡研究方面的問題。NS2是一種針對網絡技術的源代碼公開的、免費的軟件模擬平臺,研究人員使用它可以方便地進行網絡技術的開發。NS2包含豐富的網絡模塊,涉及網絡技術的各個方面,是學術界廣泛使用的一種網絡模擬軟件。NS2中含有多個模塊,如Tc l 、Tk 、Otel 、TclCL 、Nam 和xgraph 等7。圖1為NS2功能示意圖,粗框里為NS 的模塊,方框外的

12、script 是腳本語言。NS 解釋腳本,將輸出寫到輸出文件中,然后調用Nam 或xgraph 顯示輸出文件。NS2仿真的步驟為:(1編寫OTCL 腳本,配置網絡拓撲結構,建立協議代理,配置業務量模型參數,設置trace 對象。(2NS2解釋執行OTCL 腳本。(3對仿真結果的trace 文件進行分析,得出有用數據。采用NS2對Ad hoc 網絡三種典型的路由協議進行仿真模擬。首先使用NS2中自帶的運動場景生成器setdest 和流量場景生成器cbrgen 產生模擬需要的運動場景和流量場景。場景規模1000m 1000m,場景包括30個節點,信源為CBR 方式,隨機選擇15個節點,啟動15個c

13、br 數據流,每秒產生1個512k 的數據包。節點移動速度5m/s,仿真時間200s 。圖1 NS 功能示意圖運動場景代碼:setdest -n 30-p 0-s 5-t 200-x 1000-y 1000scen-30n-5m流量場景代碼:ns cbrgen.tcl -t ype cbr -nn 30-seed 1-mc 15-rat e 1.0cbr-30n-mc15通過編寫Tcl 腳本語言,調用相應的場景文件模擬三種路由協議,在NS 目錄下生成各自的仿真跟蹤文件*.t r 。相關參數如下(以AODV 為例:路由協議類型(val:AODV通信信道類型(chan:Channel/Wirele

14、ssChannel 無線信號傳輸模式(prop:Propagat ion/TwoRay 2Ground網絡接口類型(net if:Phy/WirelessPhy Mac 層協議類型(mac :Mac/802-11接口隊列類型(ifq:Queue/DropTail/PriQueue 鏈路層類型(ll:LL天線模式(ant :Antenna/OmniAntenna 調用場景文件運行模擬并記錄實驗數據:puts /Lo ading connection pattern 0#64# 計算機技術與發展 第20卷so ur ce $v al(cpputs /Lo ading scenar i o file

15、.0so ur ce $v al(scfor set i 0$i $val(nnincr i $ns -at $val(stop.0/$node -($ireset 0;$ns -at $val(sto p.0002/puts 0NS EXITING.0;$ns -halt 0puts $tracefd /M 0.0nn $val(nnx $val(xy $val(yrp $val(adhocRouting0puts $tracefd /M 0.0sc $v al(sccp $val(cp0puts $tracefd /M 0.0prop $val(propant $v al(ant0puts

16、 /Starting Si mulation.0$ns -run運用gawk 工具對仿真跟蹤文件執行awk 程序收集到相應的數據,然后通過NS 的gnuplot 繪圖工具得到需要的數據圖像8。通過比較數據包接收率、端到端時延和路由開銷三個方面可以清晰看到三種Ad hoc 網絡路由協議各自的優缺點。數據包成功接收率(Recv/Send Rat e即成功接收到的數據包與所有發送的數據包的比率,這個比率反應了路由的可靠性。圖2是各路由協議數據包接受率的比較。此圖表明,此實驗按需驅動的路由協議DSR 和AODV 的數據包成功接收率優于表驅動路由協議DSDV 。圖2 數據包成功接收率端到端延時(End-

17、t o-End Delay即從源節點發送數據包到目的節點接收到數據包之間的所用的時間,圖3所反應的是在整個仿真過程中所有數據包的端到端延時。隨著節點移動性的增大,三種路由協議的平均端到端延時呈現不斷提高的趨勢。這是由于網絡拓撲變化頻繁,路由更新次數增多,從而分組轉發時間變長。DSDV 端到端延時最小,其次是AODV,最大的是DSR 。路由開銷(rout ecosts:rout ecosts=pkt -rout e -sum/pkt -cbr -sum pkt -rout e -sum 指仿真期間傳輸的路由控制分組總數。使用的分組數少,開銷則低,協議的運行效率提高,帶寬和能源消耗相應降低。該指標

18、路由開銷可以用來比較不同路由協議的可擴展性、適應網絡擁塞的能力和協議的效率。圖4表明,DSR 開銷最小,DSDV 開銷最大。隨著節點移動性降低,按需驅動路由協議AODV 和DSR 的開銷隨之減小。表驅動路由協議DSDV 由于需要連續監測鏈路狀態,維護網絡拓撲和路由信息,周期性地發送控制報文, 開銷很大。3 Ad hoc 路由協議中節點能量分析Ad hoc 網絡中的移動節點是便攜式設備,使用電池工作,能量有限,學術界在對Ad hoc 網絡路由協議的研究過程中,往往關注數據傳送率、端到端時延、平均跳數等方面,而忽略節點本身能量問題9。文中對Ad hoc 網絡三種典型路由協議引入NS 能量模型,分析

19、數據傳輸過程中節點能量變化。3.1 NS 能量模型NS 實現的能量模型10是一個節點屬性。能量模型表示了一個移動主機的能量水平。模擬實驗開始時,每個節點的能量模型都有一個能量初始值ini 2t ialEnergy -。同時,還包括每個包的發射和接收的能耗,分別為txPower -和rxPower -。init ialEnergy -的值在每一次的數據包發射和接收都會減少。當節點的能量水平降低到0時,節點就不能發射或接收數據包。能量模型定義文件在ns/energymodel 中。基本的能量模型比較簡單,在NS2中,類EnergyModel 定義如下:class EnergyModel :publ

20、ic TclObject#65#第1期 金 偉等:基于NS 的Ad hoc 網絡路由協議仿真研究public:EnergyModel(double energyenergy -=energy; inline double energy(return energy -; inline vo id setenergy(do uble eenergy -=e;virtual void D ecrTxEnergy(double txtime,double P -tx energy -=(P -tx *txtime;virtual void D ecrRcvEnergy(double rcvtime,d

21、ouble P -rcv energy -=(P -rcv *rcvtime; protected: double energy -;3.2 節點能量分析為了更直觀地觀察三種路由協議節點能量的變換情況,增大移動網絡拓撲復雜性:在1500m 1500m 區域進行測試,節點數目設置為50,節點連接度20,移動速度8m/s,其余參數不變。同時,在模擬腳本語言中增加移動節點能量參數初始化以及獲取移動節點能量的代碼:set val(energymo delEnergyModel set val(initialenergy1000set val(logenergy/on 0set val(stop300-

22、energyModel $val(energymodel-idlePower 0.035-rxPower 0.395-txPower 0.660-sleepPower 0.001-transitionPower 0.2-transitionTime 0.005-initialEnergy $val(initialenergy模擬實驗結束后,各節點能量數值保存在Trac e 文件中,使用NS 自帶數據處理工具gawk 對Trace 文件進行處理,提取其中關于節點能量的數據:gawk .$3=/t ime 0sum+=$7END print sum/50trace.tr然后運用NS 繪圖工具Gnu

23、plot 繪圖。圖5是模擬實驗中50個節點的平均能量變化曲線圖。三種路由協議中,先驗式路由協議DSDV 由于網絡中的每一個節點都保持了一張完整的路由表,不需要頻繁地進行路由發現過程,節點能耗較小;按需驅動路由協議DSR 和AODV 存在選路過程,節點能耗相對較大。4 結束語雖然先驗式路由協議DSDV 的平均端到端延時短、移動節點能耗較低,但是數據包發送成功率明顯低于按需驅動路由協議DSR 和AODV,同時存在較大的路由開銷。而在按需驅動路由協議中,DSR 的端到端延時存在較大的波動性,反觀AODV 協議,綜合DSR 和DSDV 兩種路由協議優點,數據包發送成功率高于80%,路由開銷比率又控制在20%以下。隨著網絡拓撲復雜性的增加,AODV 的這種優勢體現更加明顯。通過引入NS 能量模型分析移動節點能量的變化,在按需驅動路由協議中,尋找一種有效地降低選路過程節點能量消耗的路由算法,仍需進一步 研究。圖5 節點能量變化圖參考文獻:1 Royer E M.