周德榮， 夏 齡， 田關(guān)偉， 舒 濤

(四川民族學(xué)院 網(wǎng)絡(luò)信息中心，四川 康定 626001)

0 引 言

在網(wǎng)絡(luò)協(xié)議研究和開發(fā)時，驗證網(wǎng)絡(luò)協(xié)議的正確性和測試協(xié)議性能工作通過實際的硬件實驗系統(tǒng)完成非常困難[1]。網(wǎng)絡(luò)仿真器是進行網(wǎng)絡(luò)研究重要的工具,NS2是其中比較常用的軟件之一。面向?qū)ο蟮木W(wǎng)絡(luò)仿真器(Network Simmlator, Version 2, NS2)是由美國加州大學(xué)伯克利分校開發(fā)的開放源代碼網(wǎng)絡(luò)仿真軟件，它是面向?qū)ο蟮木W(wǎng)絡(luò)仿真器,自身有一個虛擬時鐘,所有的仿真都是由離散事件驅(qū)動[2]。NS2常用于協(xié)議和算法的開發(fā)及評估。Ad hoc網(wǎng)絡(luò)是一種特殊的在不借助任何中間網(wǎng)絡(luò)設(shè)備的情況下，可在有限范圍內(nèi)實現(xiàn)多個移動終端臨時互聯(lián)互通的網(wǎng)絡(luò)，它具有無中心、自織組、多跳路由、獨立組網(wǎng)、結(jié)點移動等特點[3-4]。路由協(xié)議是Ad hoc網(wǎng)絡(luò)的重要組成部分，優(yōu)秀的路由協(xié)議是網(wǎng)絡(luò)性能的可靠保證。傳統(tǒng)的路由協(xié)議不能滿足Ad hoc網(wǎng)絡(luò)的要求，根據(jù)其特點設(shè)計出了表驅(qū)動路由協(xié)議DSDV、WRP和按需路由協(xié)議DSR、AODV和TORA等。AODV路由協(xié)議具有一定優(yōu)勢，但也存在一定缺點，本文提出一種改進的AODV路由協(xié)議，分析了改進后的AODV協(xié)議在NS2中的實現(xiàn)和仿真。

1 NS2的基本結(jié)構(gòu)

NS2是一種離散事件驅(qū)動的網(wǎng)絡(luò)模擬器[5]，它包含仿真事件調(diào)度器、網(wǎng)絡(luò)組件對象庫以及網(wǎng)絡(luò)構(gòu)建模型庫等。事件調(diào)度器計算仿真時間，激活事件隊列中的當(dāng)前事件，執(zhí)行一些相關(guān)的事件。網(wǎng)絡(luò)組件通過傳遞分組來相互通信，所有需要花費仿真時間來處理分組的網(wǎng)絡(luò)組件都必須要使用事件調(diào)度器。NS2中的網(wǎng)絡(luò)構(gòu)件一般由相互關(guān)聯(lián)的兩個類來實現(xiàn)，一個是C++類，一個在OTCL類，C++類是算法和協(xié)議的具體實現(xiàn)。OTCL對象是用戶接口對象，主要是建立OTCL對象、設(shè)置屬性、通過事件調(diào)度器調(diào)度網(wǎng)絡(luò)模擬事的發(fā)生。通過編寫Tcl模擬腳本，使用NS2進行仿真產(chǎn)生Trace文件，通過NAM模塊對仿真過程進行動畫演示，通過Xgraph進行仿真結(jié)果圖形繪制,NS2的基本結(jié)構(gòu)如圖1所示。

NS2(NS2的allinone包)由多個開源模塊組成[6]，所有模塊均包含源代碼。NS2網(wǎng)絡(luò)仿真器安裝后的目錄結(jié)構(gòu)如圖2所示，NS2安裝后生成的目錄與模塊是相互對應(yīng)的,即某個模塊包含的內(nèi)容放在同名的目錄下。目錄結(jié)構(gòu)中最重要的是ns2-allinone-2.34/ns-2.34,NS2中對網(wǎng)絡(luò)協(xié)議、算法實現(xiàn)的C++源代碼主要位于ns-2.34目錄,OTCL源碼主要位于ns-2.34/tcl/lib目錄。NS2中實現(xiàn)新協(xié)議、新算法要編寫新的C++和OTCL代碼,同時修改ns-2目錄下的相關(guān)代碼,然后重新編譯連接到NS2核心模塊即可。

2 AODV協(xié)議及其不足

AODV協(xié)議[7]是一種綜合了DSR和DSDV各自優(yōu)點改進而來的按需距離矢量路由協(xié)議。AODV路由協(xié)議包括路由發(fā)現(xiàn)和路由維護兩種機制[8]。當(dāng)源結(jié)點與目的結(jié)點進行通信時，源結(jié)點通過查找路由表是否有到目的結(jié)點的路由，有則直接發(fā)送，若沒有源結(jié)點就通過發(fā)送RREQ路由請求分組發(fā)起路由尋找，中間結(jié)點收到RREQ路由請求分組后對比序列號，如果之前收到過該分組就丟棄。反之，從路由表找到到目的結(jié)點的路由，目的結(jié)點收到RREQ后向源結(jié)點發(fā)送路由應(yīng)答消息RREP，建立一條源結(jié)點到目的結(jié)點的路徑。AODV路由協(xié)議主要通過本地修復(fù)和源結(jié)點重建路由兩種方式實現(xiàn)路由維護。AODV路由協(xié)議通過周期性廣播HELLO報文來檢測鏈路狀態(tài)，如果規(guī)定時間內(nèi)，結(jié)點未收到鄰居結(jié)點的“HELLO”響應(yīng)報文，就判斷該鏈路已經(jīng)斷開，此時啟動本地修復(fù)機制，若本地修復(fù)失敗，刪除緩存中源結(jié)點發(fā)送過來的數(shù)據(jù)包，發(fā)送RRER錯誤分組給源結(jié)點，源結(jié)點重新發(fā)起路由發(fā)現(xiàn)過程。

AODV路由協(xié)議有很多優(yōu)點，同時也存在路由表中僅維護一條到指定的目的結(jié)點的路由、僅適用于雙向傳輸信道的網(wǎng)絡(luò)環(huán)境、采用了超時刪除路由的機制，即使路由未失效，在超過時限后也將被刪除等缺點[9]。在拓撲變化頻繁的網(wǎng)絡(luò)中，AODV協(xié)議中每個源結(jié)點只維護一條到指定目的結(jié)點的路由這個缺點尤為突出。如圖3所示網(wǎng)絡(luò)拓撲,結(jié)點n0要向結(jié)點n4發(fā)送數(shù)據(jù)，結(jié)點n0會創(chuàng)建一個路由請求包RREQ,將其廣播給所有鄰居結(jié)點，如果結(jié)點n1收到來自結(jié)點n0的RREQ,則建立到結(jié)點n0的逆向路由。如果結(jié)點n1沒有到n4的路由，則將該RREQ重新廣播給自身的其他鄰居。所有鄰居結(jié)點均會轉(zhuǎn)發(fā)RREQ，直到有自身到結(jié)點n4的有效路由或直接鄰接結(jié)點n4。當(dāng)RREQ達到結(jié)點n5后，n5發(fā)現(xiàn)有一條到n4的路由，且其序號不小于RREQ中的序號，則會構(gòu)造一個路由響應(yīng)包RREP并沿逆向路由單播給n0，在n0結(jié)點中形成n0-n1-n7-n6-n5-n4路由信息。同理，當(dāng)RREQ達到結(jié)點n3后，還會形成n0-n1-n2-n3-n4路由。結(jié)點n0根據(jù)目的結(jié)點序列號及到目的結(jié)點的跳數(shù)選擇n0-n1-n7-n6-n5-n4作為最佳路由,n0-n1-n2-n3-n4將被丟棄。若結(jié)點n0通過最佳路由與結(jié)點n4通信時,當(dāng)結(jié)點n1得知到結(jié)點n7的路由斷開時,結(jié)點n0將重新廣播到結(jié)點n4的路由請求包RREQ,最終會再次收到包含路由n0-n1-n2-n3-n4的路由響應(yīng)包RREP。

3 AODV協(xié)議改進及實現(xiàn)

3.1 AODV協(xié)議改進思想

針對上述AODV協(xié)議的缺點，提出AODV協(xié)議的改進方法是每個源結(jié)點增加一條到指定目的結(jié)點的備份路由，形成源結(jié)點到目的結(jié)點主備兩條路由。當(dāng)主路由失效時,使用備份路由發(fā)送數(shù)據(jù), 只有當(dāng)備用路由也失效時才重新發(fā)起路由發(fā)現(xiàn)過程。協(xié)議改進后路由表中主備路由的建立流程圖4所示，選擇最優(yōu)路由原則是路由序列號較大或跳數(shù)較小。

協(xié)議改進后,采用圖3所示網(wǎng)絡(luò)拓撲，如果結(jié)點n0與結(jié)點n4需要通信，但結(jié)點n0的路由表中沒有到結(jié)點n4的有效路由,結(jié)點n0則廣播一個RREQ分組。路由建立完后，結(jié)點n0將先后收到包含n0-n1-n2-n3-n4和n0-n1-n7-n6-n5的路由RREP分組，結(jié)點n0收到的兩條路由以主備方式保存于自身的路由表，若結(jié)點n0與結(jié)點n4通信時,結(jié)點n1發(fā)現(xiàn)與結(jié)點n7路由斷開,路由斷裂處理的同時,會立即查找是否有本結(jié)點至目的結(jié)點的備份路由,若有,則將收到的數(shù)據(jù)包通過備份路由發(fā)送至目的結(jié)點。只有當(dāng)主路由與備份路由都失效時,n0再次重新發(fā)起路由發(fā)現(xiàn)過程。

3.2 改進的AODV協(xié)議實現(xiàn)

NS2 2.34中,AODV路由協(xié)議主要由協(xié)議實體、路由表、定時器、日志記錄器、路由緩存隊列等組件構(gòu)成。AODV路由協(xié)議源代碼位于安裝目錄下的ns-2.34/aodv目錄，協(xié)議由aodv_packet.h,aodv.h,aodv.cc,aodv_rqueue.h,aodv_rqueue.cc,aodv_rtable.h,aodv_rtable.cc及aodv_logs.cc文件構(gòu)成，協(xié)議改進以AODV為基礎(chǔ)實現(xiàn)。

3.2.1改進的AODV協(xié)議核心代碼實現(xiàn)

對原有的路由表進行擴充實現(xiàn)主路由與備份路由,做法是通過修改aodv_rtable.h文件中的aodv_rt_entry類聲明部分，在其中添加變量rt_priority作為標(biāo)志位，aodv_rt_entry類構(gòu)造函數(shù)將rt_priority初始化為0，0表示主路由,1表示備份路由。aodv_rtable類中添加rt_addbak(nsaddr_t id)和rt_lookupbak(nsaddr_t id) 兩個函數(shù)，用于實現(xiàn)備份路由添加及查找功能。修改aodv.cc中的recvReply(Packet*P)函數(shù)，實現(xiàn)源結(jié)點可根據(jù)選擇序列號最大以及跳數(shù)最小的兩條路由作為主路由與備份路由的功能。同時，對aodv.cc中rt_ll_failed(Packet*P)函數(shù)中的本地修復(fù)機制進行修改[10-11],完成當(dāng)鏈路層發(fā)現(xiàn)主路由失效時能夠使用備份路由來傳輸數(shù)據(jù)。部分關(guān)鍵代碼實現(xiàn)如下：

3.2.2NS2中改進的AODV協(xié)議實現(xiàn)

NS2使用分裂對象模型，協(xié)議開發(fā)從C++和Tcl兩個類入手。以AODV協(xié)議源代碼為基礎(chǔ)將改進后的協(xié)議取名AODVN,將協(xié)議源代碼存于ns-2.34/aodvn目錄中，主要由定義計時器和路由代理的aodvn.h文件，實現(xiàn)所有定時器、路由代理和Tcl鏈接的文件的aodvn.cc文件，聲明aodvn路由協(xié)議需要在無線自組網(wǎng)結(jié)點交換數(shù)據(jù)包的aodvn_packet.h文件，聲明路由表的aodvn_rtable.h文件，路由表實現(xiàn)的aodvn_rtable.cc文件，隊列聲明及實現(xiàn)的aodvn＿queue.h和aodvn＿queue.cc等文件組成。

(1) 聲明分組類型。在common/packet.h把PT＿AODVN添加到枚舉類型值列表中，為新的分組類型在p＿info類中定義名稱name＿[PT＿AODVN]= "aodvn"。

(2) 實現(xiàn)跟蹤支持。要記錄分組信息，在Trace/cmu-trace.h、Trace/cmu-trace.cc文件中的CMUTrace類添加并實現(xiàn)void format_aodvn()函數(shù)，修改trace/cmu-trace.cc文件中的format()函數(shù)添加case PT＿AODVN實現(xiàn)能夠調(diào)用void format_aodvn()函數(shù)。

(3) 修改OTCL庫文件。tcl/lib/ns-packet.tcl文件中添加協(xié)議名AODVN實現(xiàn)協(xié)議分組類型； Tcl/lib/ns-default.tcl文件中添加Agent/AODVN set accessible＿var＿ true綁定屬性的默認值；Queue/priqueue.cc文件中添加case PT_AODVN實現(xiàn)隊列對協(xié)議的支持；tcl/lib/ns-lib.tcl文件中新建一個使用AODVN路由協(xié)議的無線結(jié)點過程。

(4) 修改ns-2.34/Makefile文件增加對新類的編譯。文件放在ns-2.34/aodvn目錄下，修改Makefile文件里OBJ_CC變量，增加aodvn/aodvn_logs.o aodvn/aodvn.o aodvn/aodvn_rtable.o aodvn/aodvn_rqueue.o實現(xiàn)改進協(xié)議的編譯、連接到NS2。

4 仿真結(jié)果與分析

仿真網(wǎng)絡(luò)由50個移動結(jié)點構(gòu)成,各結(jié)點隨機分布在1 200～400 m的平面矩形區(qū)域內(nèi), 結(jié)點的無線傳輸范圍為300 m,隨機以均勻分布最大20 m/s的速度向任意方向移動，結(jié)點間的最大連接數(shù)為30，20個源結(jié)點，每秒發(fā)送4個CBR包,每個CBR包的大小為512B,Mac層協(xié)議采用IEEE802.11，模擬時間為900 s,不同運動場景中,結(jié)點到達目的地后的停留時間分別為0，30，60，120，300，600，900 s，結(jié)點停留時間越短,網(wǎng)絡(luò)拓撲變化越頻繁。具體仿真參數(shù)如表1所示。

根據(jù)仿真參數(shù)使用NS2中的傳輸產(chǎn)生器(cbrgen)生成傳輸模型文件，用結(jié)點移動產(chǎn)生器(setdest)生成結(jié)點暫停時間不同，結(jié)點個數(shù)、結(jié)點運動的最大速度、結(jié)點運動區(qū)域大小、場景持續(xù)時間等參數(shù)完全相同的運動場景文件[12, 13]。編寫TCL腳本,使用AODV協(xié)議、AODVN協(xié)議分別載入規(guī)定的場景文件進行仿真,通過awk腳本對仿真產(chǎn)生Trace文件進行處理，分別提取兩種協(xié)議的分組投遞率、端到端平均時延、歸一化路由開銷以及路由發(fā)現(xiàn)頻率等網(wǎng)絡(luò)性能數(shù)據(jù)[14]，最后繪制協(xié)議仿真圖。

表1 主要仿真參數(shù)

仿真中分別使用了0、30、60、120、300、600和900 s的暫停時間，暫停時間越小，結(jié)點的移動性越強，網(wǎng)絡(luò)拓撲變化越頻繁。每個暫停時間數(shù)據(jù)點仿真時采用相同的業(yè)務(wù)流模型和不同移動模型。AODV和AODVN兩種協(xié)議的分組投遞率、端到端的平均時延、歸一化的路由開銷和路由發(fā)現(xiàn)頻率的仿真結(jié)果如圖5～圖8所示。

圖5 分組投遞率仿真結(jié)果

從圖5看出，當(dāng)暫停時間較小時,由于結(jié)點移動頻繁使得路由失效頻發(fā)，AODV和AODVN的分組投遞率較低，由于暫停時間的增加，AODV和AODVN的分組投遞率逐漸提高，AODVN比AODV有一定提高。從圖6看出,隨著結(jié)點暫停時間的增加,AODV和AODVN的端到端平均時延均呈現(xiàn)下降趨勢，與AODV比較,AODVN大幅降低了端到端的平均時延,特別是網(wǎng)絡(luò)拓撲變化較慢時,降低的幅度尤為明顯。由圖7和圖8看出,AODVN與AODV相比較,歸一化的路由開銷以及路由發(fā)現(xiàn)頻率均有大大降低，這也表明AODVN協(xié)議當(dāng)主路由失效時,備份路由能及時起到原來主路由的作用,減少了路由發(fā)現(xiàn)過程的次數(shù),降低路由發(fā)現(xiàn)頻率，網(wǎng)絡(luò)性能得到一定提高。

圖6 端到端的平均延時仿真結(jié)果

圖7 歸一化的路由開銷仿真結(jié)果

圖8 路由發(fā)現(xiàn)頻率仿真結(jié)果

5 結(jié) 語

網(wǎng)絡(luò)仿真是檢驗網(wǎng)絡(luò)協(xié)議和算法的正確性和有效性,以及測試網(wǎng)絡(luò)性能必不可少的有效方法[15]。本文通過提出一種改進的AODV協(xié)議,詳述改進的AODV協(xié)議在NS2中的實現(xiàn)過程,對新協(xié)議進行測試和驗證，仿真結(jié)果驗證了新協(xié)議的有效性。采用NS2實現(xiàn)一些新協(xié)議和算法進行網(wǎng)絡(luò)仿真研究大大提高了效率、降低了成本, 具有很好的靈活性。

[1] 夏 利，張 鵬，楊 宏，等. NS2中單播動態(tài)路由機制的剖析與擴展[J]. 微計算機應(yīng)用, 2006, 27(3): 275-277.

XIA Li, ZHANG Peng, YANG Hong,etal. The Analyses and Extending of Unicast Dynamic Routhing in NS2[J]. Microcomputer Applications, 2006, 27(3): 275-277.

[2] 王 輝. NS2網(wǎng)絡(luò)模擬器的原理和應(yīng)用[M]. 西安: 西北工業(yè)大學(xué)出版社, 2008.

[3] 陳林星，曾 曦，曹 毅，編著. 移動Ad Hoc網(wǎng)絡(luò)自組織分組無線網(wǎng)絡(luò)技術(shù)[M]. 北京: 電子工業(yè)出版社, 2006.

[4] 周杰英，陳子凡，雷 淳，等. 無線網(wǎng)狀網(wǎng)組建及應(yīng)用[J]. 實驗室研究與探索, 2011(12): 56-59.

ZHOU Jie-ying, CHEN Zi-fan, LEI Chun,etal. Wireless Mesh Network Construction and Application[J]. Research and Exploration in Laboratory, 2011(12): 56-59.

[5] Ekram H., Issariyakul T. Introduction to Network Simulator NS2[M]. Springer, 2009.

[6] Fall Kevin, Varadhan Kannan. The ns Manual (formerly ns Notes and Documentation)[Z]. The VINT Project, 2008.

[7] 童 燕，李儉兵. NS2的Ad hoc網(wǎng)絡(luò)AODV協(xié)議的仿真[J]. 數(shù)字通信, 2009(3): 50-53.

TONG Yan, LI Jian-bing. Simulation of AODV routing protocol in Ad hoc networks based on NS2[J]. Digital Communication, 2009(3): 50-53.

[8] 莊春梅，陸建德. AODV協(xié)議分析及過期路由維護機制改進[J]. 計算機技術(shù)與發(fā)展, 2009(7): 44-47.

ZHUANG Chun-mei, LU Jian-de. Analysis and Improvement of Expired Routing Management Mechanism of AODV Routing Protocol[J]. Computer Technology and Development, 2009(7): 44-47.

[9] 張登銀，王軍玲. 改進的AODV路由協(xié)議性能比較研究[J]. 計算機技術(shù)與發(fā)展, 2010(1): 67-70.

ZHANG Deng-yin, WANG Jun-ling. Research on Performance Comparison among Improved AODV Routing Protocols[J]. Computer Technology and Development, 2010(1): 67-70.

[10] 陳?？疲?勤，張 旻. 基于hello消息的AODV路由協(xié)議的改進[J]. 計算機仿真, 2009(8): 143-146.

CHEN Mo-ke, CHEN Qin, ZHANG Min. The Improve of AODV Based on HelloMessage[J]. Computer Simulation, 2009(08): 143-146.

[11] 丁緒星，吳 青，謝方方. AODV路由協(xié)議的本地修復(fù)算法[J]. 計算機工程, 2010(6): 126-127.

DING Xu-xing, Qing Wu, Fang-Fang Xie. Local Repair Algorithm for AODV Routing Protocol[J]. Computer Engineering. 2010(06): 126-127.

[12] 趙新偉，鄭洪飛. Ad Hoc網(wǎng)絡(luò)路由協(xié)議分析與仿真[J]. 計算機安全, 2011(7): 40-43.

ZHAO Xin-wei, ZHENG Hong-fei. Analysis and Simulation on Routing Protocols of Ad Hoc Networks[J]. Computer Security, 2011(7): 40-43.

[13] 何增穎. 基于NS2的Ad Hoc網(wǎng)絡(luò)路由協(xié)議分析實驗[J]. 實驗室研究與探索, 2010(5): 71-74.

ZHAO Xin-wei, ZHENG Hong-fei. Analysis Experiment of Ad Hoc Network Routing Protocol Based on NS2[J]. Research and Exploration in Laboratory, 2010(05): 71-74.

[14] 果 然，譚學(xué)治，徐貴森. 一種基于NS2的多信道網(wǎng)絡(luò)模型的建立和性能檢測[J]. 科學(xué)技術(shù)與工程, 2009(17): 4950-4954.

GUO Ran, TAN Xue-zhi, XU Gui-sen. Construction and Performance Test of a Multi-channel Network Model Based on NS2[J]. Science Technology and Engineering, 2009(17): 4950-4954.

[15] 周德榮，齡 夏，舒 濤，等. NS2網(wǎng)絡(luò)協(xié)議虛擬仿真實驗平臺研究[J]. 實驗技術(shù)與管理, 2014, 31(3): 87-90.

ZHOU De-rong, XIA Ling, SHU Tao,etal. Protocol, Research of Virtual Simulation[J]. Experimental Technology and Management. 2014, 31(3): 87-90.