一種改進的AODV路由協議的實現與仿真

周德榮， 夏 齡， 田關偉， 舒 濤

(四川民族學院 網絡信息中心，四川 康定 626001)

0 引 言

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

1 NS2的基本結構

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

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

2 AODV協議及其不足

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

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

3 AODV協議改進及實現

3.1 AODV協議改進思想

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

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

3.2 改進的AODV協議實現

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

3.2.1改進的AODV協議核心代碼實現

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

3.2.2NS2中改進的AODV協議實現

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

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

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

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

(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實現改進協議的編譯、連接到NS2。

4 仿真結果與分析

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

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

表1 主要仿真參數

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

圖5 分組投遞率仿真結果

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

圖6 端到端的平均延時仿真結果

圖7 歸一化的路由開銷仿真結果

圖8 路由發現頻率仿真結果

5 結 語

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

[1] 夏 利，張 鵬，楊 宏，等. NS2中單播動態路由機制的剖析與擴展[J]. 微計算機應用, 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網絡模擬器的原理和應用[M]. 西安: 西北工業大學出版社, 2008.

[3] 陳林星，曾 曦，曹 毅，編著. 移動Ad Hoc網絡自組織分組無線網絡技術[M]. 北京: 電子工業出版社, 2006.

[4] 周杰英，陳子凡，雷 淳，等. 無線網狀網組建及應用[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網絡AODV協議的仿真[J]. 數字通信, 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協議分析及過期路由維護機制改進[J]. 計算機技術與發展, 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路由協議性能比較研究[J]. 計算機技術與發展, 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路由協議的改進[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路由協議的本地修復算法[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網絡路由協議分析與仿真[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網絡路由協議分析實驗[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] 果 然，譚學治，徐貴森. 一種基于NS2的多信道網絡模型的建立和性能檢測[J]. 科學技術與工程, 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網絡協議虛擬仿真實驗平臺研究[J]. 實驗技術與管理, 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.