摘 要： 為解決Ad Hoc網絡的AODV路由協議在通信過程中存在的擁塞問題，提出了改進AODV路由協議的思想。根據網絡鏈路擁塞度的大小采取不同措施和節點路由，建立不相關多徑路由分流以避免擁塞。仿真結果表明，改進后的路由協議有效地減少了發生擁塞的幾率，從而提高了移動Ad Hoc網絡的性能。
關鍵詞： Ad Hoc網絡；路由協議；鏈路擁塞
移動自組網MANET(Mobile Ad Hoc Network)[1]是由一組帶有無線通信收發裝置的移動終端節點組成的一個多跳、臨時性無中心的網絡，整個網絡沒有固定的基礎設施,網中的每個終端都可以自由移動、自由加入和退出網絡，各網絡節點地位相等。Ad Hoc網絡具有很高的靈活性，可以廣泛應用于不易建立基礎設施的環境，如地震后的緊急搜救、軍用戰術環境和民用應急通信。與單跳的無線網路不同，移動自組網的節點之間通過多跳數據轉發機制進行數據通信，需要中間節點進行分組轉發決策。
移動自組網路由協議的多數路由協議以單徑路由算法為基礎，而且在路由選擇時以跳數最少(或稱為路徑最短)作為選擇標準，沒有考慮網絡擁塞問題。由于一條路徑的帶寬有限，當很多節點都選擇跳數最少路徑作為路由路徑時，骨干節點連接繁忙，從而造成端到端時延和丟包率增大，網絡擁塞，影響網絡整體性能[2]，而且擁塞引起的路由控制消息丟失會觸發更多的路由請求和路由回復，從而加劇網絡擁塞。
1 AODV路由協議
網絡路由協議是實現網絡通信最關鍵和最核心的問題。目前比較成熟透明的按需距離矢量路由AODV(Ad Hoc on-Demand Distance Vector Routing)[3]基于傳統的距離向量路由機制，具有簡單易實現、防止循環發生、支持中間節點應答等優點，但也存在一定不足：每次由源節點發起路由請求均只得到一條路由、中間節點的應答路由可能過時等。在AODV協議的仿真實驗中發現，隨著網絡負荷的增加，網絡經常出現局部擁塞，吞吐率下降很快。網絡中某些節點負荷很大，而節點的鏈路帶寬和處理能力有限，當數據到達速率超過節點處理能力時，數據將阻塞在這些節點中等待傳輸。一旦這種狀況持續一段時間，節點緩沖區會很快溢出，從而造成數據分組丟失。而源節點因在規定時間內沒有收到確認而選擇重傳，這又將進一步加劇該路徑節點的擁塞，導致這些節點成為影響網絡效率的瓶頸[4]。
為了緩解擁塞對網絡性能的影響，提出一種基于AODV路由協議，能夠緩解鏈路擁塞的路由算法LC-AODV。在擁塞節點的上游節點處建立能繞過擁塞節點的旁路，在網絡工作路由處于堵塞情況時啟動備份路由分流，從而避免擁塞的發生。
2 LC-AODV路由協議
2.1 AODV路由協議的修改
在AODV路由協議中，路由查找過程只建立一條從源節點到目的節點的跳數最少、距離最短的路由。為了緩解擁塞，在一次尋找路由過程中建立多條節點不相關路由，并在路由尋找過程中加入鏈路擁塞度。
定義1：節點不相關路由，指所建多條路由中，任何兩條路徑除了源節點和目的節點外，其他節點都不共用。
定義2：鏈路擁塞度，描述本節點與下一跳鄰居節點的擁塞狀態，取值為下一跳節點的MAC層接口緩存隊列中剩余空間占總隊列的比率。
具體修改操作如下：
(1)在AODV路由協議的基礎上，針對路由請求RREQ和路由應答RREP控制包分別增加一個條目——鏈路擁塞度。在源節點需要傳輸數據時，發送路由請求RREQ消息，當RREQ報文按照不同的路徑到達目的節點時，目的節點不是簡單地只處理第一個到達的RREQ，對此后到達的RREQ回復相同的RREP，并建立源節點到目的節點的備份路由。
(2)在路由維護階段，周期性地傳輸Hello報文以確保鏈路的連接。但是在LC-AODV路由協議中，同樣在Hello消息中增加鏈路擁塞度這一條目，檢測該節點與鄰居節點之間鏈路的擁塞度，并加以動態調整。
2.2 擁塞狀態檢測
在進行數據傳輸過程中，當傳到一個節點的包個數超過它的處理能力時，節點就會變得擁塞，由于節點隊列長度有限，故包會根據隊列類型的方式開始丟棄，用R來表示定義2描述的鏈路擁塞程度[5]。根據R值的不同，設定三種擁塞狀態。根據式(1)的劃分，LCD為0時表示鏈路不擁塞，顯示為綠色狀態；LCD為1時表示鏈路出現擁塞，但是不是很嚴重，顯示為黃色狀態；LCD為2時，鏈路出現嚴重擁塞，顯示為紅色狀態。
2.3 LC-AODV工作原理
搭建一個移動Ad Hoc網絡，如圖1所示，S為源節點，D為目的節點，其他為中間轉發節點。當源節點有數據要向目的節點傳輸，而且S節點中沒有到目的節點的路由時，需要建立路由。源節點廣播路由請求RREQ，假設在路由建立過程中，找到了兩條路由分別為路由1：S-3-4-5-D和路由2：S-1-2-D。路由1先返回路由應答，則路由2作為備份路由存在于網絡中。當數據開始傳輸一段時間后，節點3到節點4之間發生路由擁塞，則節點3啟動局部修復，發現可通過節點6到達目的節點，則產生路由S-3-6-5-D，因為通過節點6進行傳輸時，鏈路有輕微擁塞，則向上游節點通知備份路由，隨時準備發送數據。如果修復不成功，則直接啟動備份路由2進行數據傳輸。當所有路由都失效的情況下，源節點重新啟動路由請求過程。
2.4 鄰居擁塞表
每個節點維護一個鄰居擁塞表，記錄本節點所有鄰居節點(除去上一跳節點)的擁塞狀態。例如在表1中，對于節點S而言，LCDs1的值為0。
3 實驗仿真及結果分析
實驗采用NS2[6]模擬平臺進行模擬，將LC-AODV算法與AODV在相同網絡環境和高負載特性下進行仿真和性能對比分析，以便有效評價本算法的性能。網絡拓撲結構設計為50個移動節點的網絡模型，各節點隨機分布在1 200 m×1 000 m的平面矩形區域，每一個節點的最大傳輸范圍為250 m，隨機任意方向運動(Random Way Point) ，節點停留時間為0 s，實驗模擬時間500 s，運動最大速率為40 m/s，連接為20個CBR，大小為512 B數據流，數據流為3 packets/s，最大連接數為20。物理層選用TwoRayGround無線傳播模型，MAC層采用802.11b DCF協議。仿真過程如圖2所示。通過數據包的成功傳輸率和平均端到端傳輸延遲2個指標來比較。
3.1 數據包的成功傳遞率
數據包遞交率：目的節點收到的數據包數與源節點發送的總數據包數的比率。仿真結果如圖3所示。LC-AODV的正確傳輸率比AODV更高，因為采取抗擁塞措施，節點丟失包的幾率就會降低，導致到達目的節點的數據包增加。當節點移動速度不快時，網絡的節點位置變化不大，即拓撲結構較為穩定，網絡數據包的正確傳遞率都處于高水平，但是隨著節點移動速度增大，數據包丟失增多，網絡整體性能下降。而且隨著網絡拓撲結構變化的加快，兩種路由協議之間的差距在慢慢變小，這是因為改進后的路由協議在拓撲結構變化比較快時，路由經常失效，抗擁塞措施作用有所下降。
3.2 平均端到端延遲
傳輸數據包所需的總延遲包括緩存數據包、新路由發現、在隊列中排隊、MAC層重傳、發送和傳播所用的時延總和。仿真結果如圖4所示。整體而言，LC-AODV的性能優于AODV路由協議，這是因為采取了抗擁塞措施，在數據傳輸的時候選擇擁塞度低的鏈路，而且在傳輸過程中若遇到擁塞會及時地進行鏈路轉移，使得傳輸更為順暢。而且在節點移動速度較小時，拓撲變化較小，備份路由存在時間長，導致備份路由在節點移動速度低時較節點移動速度快時的利用率更高，從而速度低時兩路由協議的延遲差距更小。
本文針對移動Ad Hoc網絡高負載情況下網絡路由不能很好適應網絡環境的問題，提出了一種抗擁塞的改進AODV路由協議。改進的LC-AODV協議是一個適用于動態Ad Hoc網絡的擁塞適應路由協議。利用鄰居擁塞表，節點能即時感知與鄰居之間的網絡擁塞度，并根據擁塞等級采取不同的策略，通過備份路由來快速重新傳輸數據。結果證明改進后的路由協議可以緩解網絡的負載，提高了數據包正確傳輸率并降低端到端平均延遲。
參考文獻
[1] RAMANATHAN R，REDI J.A brief overview of mobile Ad Hoc networks: Challenges and direction[J].IEEE Communications Magazine, 2002, 40(5): 20-23.
[2] KLIAZOVICH D，GRANELLI F. Cross-layer congestion control in Ad Hoc wireless networks[J]. Ad Hoc Networks, 2006(4): 687-708.
[3] PERKINS C E, ROYER E M.Ad Hoc on demand and distance vector(AODV) routing[C]. The second IEEE workshop on mobile computing systems and applications. New Orleans. 1999:90-100.
[4] RAGHAVENDRA H.Congestion adaptive routing in mobile Ad Hoc networks[A]. IEEE Transactions on Parallel Distributed Systems[C].NJ, USA: IEEE Press,2006:1294-1305.
[5] 蔣道霞,劉鳳玉.Ad Hoc網絡中基于AODV的擁塞適應路由協議[J]. 南京理工大學學報(自然科學版),2009, 33(4):411-416.
[6] 方路平，劉世華，陳盼，等. NS-2網絡模擬基礎與應用
[M]. 北京：國防工業出版社，2008.