一種基于負載均衡的移動Ad Hoc網絡AODV協議改進

王 鈺，田 杰 ，徐 磊

（武警工程學院 西安 710086）

1 引言

移動無線自組網[1](mobile Ad Hoc network，MANET)是由具有無線通信能力的移動節點組成的，是一種能夠迅速展開使用的網絡體系。它不需要依靠現有固定的通信網絡基礎設施，是沒有任何中心節點的自組織、自愈合網絡。在MANET中，每一個節點既充當了主機的角色，又充當了路由器的角色。由于節點的傳輸距離有限，當通信的源節點和目的節點間的距離超出傳輸范圍時，它們之間的通信就必須通過中間節點轉發。由于移動節點的傳輸能力和能量有限，所以處在網絡拓撲結構中心的若干個節點，將會收到更多的路由請求，成為更多路徑的中間節點。它們在負載壓力和能耗方面都將遠遠大于其他節點，容易超出負載及耗盡能量，進而造成網絡擁塞。如何控制網絡負載和提高網絡生存時間成為了Ad Hoc網絡所面臨的一個重要問題。

2 路由協議描述

Ad Hoc路由協議可分為先驗式(proactive)路由協議和反應式 (reactive)路由協議兩類，也可稱為表驅動(table-driven)路由協議和按需驅動(on-demand)路由協議。表驅動路由協議的主要特點是要求每個節點維護一個或多個路由信息，并在網絡拓撲結構發生改變時及時更新。按需驅動路由協議[2]的主要特點是它只有在源節點需要時才進行路由發現，路由一經建立，就會對其進行維護，直至目的節點無法到達或該路徑不再被需要為止。相關研究[3]表明，與先驗式路由協議相比，反應式路由協議雖然傳送時延較大，但路由開銷小、分組投遞率高，更適合移動自組網絡。本文將要改進的AODV[4]路由協議就是一種按需驅動的路由協議。

AODV路由協議采用逐跳 （hop-by-hop）方式轉發分組，路由表中記錄了到目的節點的下一跳信息。它不需要在報文中攜帶完整的路由信息，當源節點中沒有到達目的節點的路由時，廣播一個RREQ。每個接收到RREQ的中間節點記錄下到源節點的逆向路徑（以便為之后的RREP提供路由），然后查詢路由表中是否有到達目的節點的路由，若有則利用記錄在報文中的逆向路徑回復RREP，否則重新廣播RREQ。當RREQ到達目的節點時，目的節點利用記錄在報文中的逆向路徑發送RREP。每個接收到RREP的節點記錄了本節點到目的節點的路徑，用以傳送后續報文。另外，每個節點都維護有一個目的序列號，當節點需要建立到目的節點的路徑和接收到以自己為目的節點的RREQ時，其值自動加1。該序列號附帶在其發出的RREQ、RREP中，網絡中其他節點在收到包含節點路徑信息的控制報文（RREQ、RREP）時，對比此序列號和本地路由緩存中該節點路由的序列號，來判別路由的新舊程度，避免環路的產生。路由請求信息中包含了TTL（time to live），避免了路由請求帶來的全網廣播。AODV協議通過節點周期廣播hello消息提供與相鄰節點的連接信息，檢測鏈路狀態。

3 改進后的AODV協議

在移動Ad Hoc網絡中，包含擁塞節點的一條路由，即使是通往目的節點的最短路由也未必是最佳路由。因此，在路由選擇的時候應盡力避開擁塞節點。采用負載相對較輕的路由，不但有利于保證傳輸時延，也均衡了全網的負載，有助于提升網絡整體性能。AODV的開銷主要來自于建立路由的泛洪廣播的路由請求報文RREQ。對其進行改進,提出PS-AODV協議。節點收到RREQ分組后先檢查其負載值，若節點負載過大，則拒絕轉發RREQ分組，直到負載降低以后，再重新轉發RREQ分組。在此引入一種MAC層和路由層之間交換信息的跨層機制，網絡中每個節點監視自己的MAC層接口隊列，加入metric值來對網絡中節點的能量和負載進行度量。網絡中從源節點到目的節點的鏈路負載狀況，取決于鏈路中負載大的節點。即該鏈路的metric(m)值為 m=max(m1,m2,m3,…，mn)。設該鏈路中第 i個節點的metric值為mi=li/bi。其中bi為該節點的可用能量百分比，li為該節點MAC層接口隊列的當前占用率li=qi/ci，其中qi為節點i的MAC層接口隊列緩存的分組數量，ci為節點i的MAC層接口隊列能容納的最大長度。假設所有節點的規格都是一樣的，則ci=c。所以到達目的節點的為了簡化計算，可將c去掉，則

目的節點或者擁有到達目的節點路由信息的中間節點，在回復RREP分組的時候，若存在多條路徑，可憑借metric值進行最優選擇。PS-AODV在路由請求RREQ中添加一個字段metric(m)，來記錄所經過節點的最大負載，當源節點發起路由請求時，它計算m值，并把m值寫入RREQ分組中，然后進行廣播。同時在節點路由表中添加一個字段mt，記錄從源節點到該節點的m值。中間節點收到RREQ后，計算m值來確定當前節點的負載狀況和可用能量。根據節點的m值以及是否有目的節點的路由信息，決定該節點是否可以作為中間節點。節點有3種狀態。癱瘓:m≥a；擁塞:b≤m≤a；正常:m

網絡中每個節點可根據其負載狀況和可用能量決定轉發或丟棄收到的RREQ分組。當一個中間節點處于“癱瘓”狀態時，除非它是該鏈路的目的節點，否則將不處理任何路由請求，丟棄所有收到的RREQ，使其不能再成為中間節點。當節點處于“擁塞”狀態時，只有其路由表中已經存在了此路由請求目的節點的路由信息或它是該鏈路的目的節點，它才會回復其路由請求，否則將丟棄該路由請求，以此來減少由于RREQ廣播造成的網絡負載和降低路由發現的端到端時延。當節點處于“正常”狀態時，如果首次收到新的RREQ，則把路由表中的相應路由值設為該RREQ中的m值。然后比較m和該節點的metric值，將大的m值記錄在RREQ的mt中，最后轉發RREQ。如果節點已經收到過來自同一源節點的相同廣播ID的RREQ，則比較m和mt。如果m值較小，則丟棄RREQ。否則，更新路由表的mt值，并將指向前一跳節點的指針指向發送該RREQ的節點，并且不再轉發該RREQ。收到第一個RREQ后，目的節點等待一段時間來獲得可能的更多路由，然后從中選擇擁有最小m值的路由回復RREP。

4 仿真和分析

下面在NS2[5]上進行仿真。以下描述仿真環境、性能參數和試驗結果。物理信道的帶寬為2 Mbit/s。鏈路層采用IEEE 802.11MAC層協議的分布式協調功能(distributed coordination function，DCF)。PS-AODV 的 b 值取 0.5，a值取0.7。將50個節點隨機地分布在1 200 m×800 m的范圍內，節點的通信范圍是250 m，最大移動速度為 5 m/s，節點初始能量為200 J，暫停時間為50 s，仿真運行500 s。信源采用固定比特率(constant bit rate，CBR)，每個分組長度為512 byte，一共啟動40個CBR流。仿真通過改變信源發送分組的頻率來改變網絡負荷。

4.1 仿真參數

以下是本文選取的協議性能比較參數：

平均端到端時延=路由發現過程所需時間+分組在緩存中的排隊時間+鏈路層重傳時間+傳播時間；

4.2 仿真結果

圖1反映了隨著網絡負載增加，AODV和PS-AODV分組傳送率的變化曲線。結果顯示隨著網絡負載的增加，兩者的分組傳送率都在下降，當負載為0～480 kbit/s時，AODV和PS-AODV的分組傳送率下降不明顯，差距不大，但隨著負載增加，兩者的分組傳送率都急劇下降，但PS-AODV的下降幅度比AODV小，當負載達到1 440 kbit/s時，PS-AODV的分組傳送率比AODV高7%。由此可見，PS-AODV在分組傳送率上比AODV擁有更大的優勢，尤其是在高負載情況下優勢更加明顯。這是因為AODV沒有考慮負載均衡問題，在高負載環境下，處于網絡中心的若干節點負荷急劇增加，當流量超出節點傳輸極限時，其分組丟失率迅速提高，導致分組傳送率急劇下降。而PS-AODV根據metric值選擇傳輸路徑，并且高負載的節點能有選擇地回復RREQ分組，有效地對數據流量進行了分流，均衡了負載，間接提高了分組傳送率。

圖2顯示了隨著網絡負載的增加，AODV和PS-AODV的平均端到端時延變化情況。隨著網絡負載增加，兩者的平均端到端時延開始上升，PS-AODV的平均端到端時延總體低于AODV,當負載達到1 440 kbit/s時，PS-AODV比AODV的平均端到端時延低240 ms，該圖反映出PS-AODV比AODV擁有更低的平均端到端時延。這是因為PS-AODV根據metric值選擇路徑，而metric值的決定性因子是MAC層接口隊列緩存的分組數量，而端到端時延主要由排隊時間產生，所以PS-AODV會選擇排隊時間較小的路由，從而減小了網絡時延。

圖3顯示了PS-AODV和AODV的路由開銷隨網絡負載變化時的變化情況。隨著網絡負載增加，數據分組所占比例不斷提高，兩者的路由開銷降低。PS-AODV的路由開銷總體低于AODV，當負載為1 120 kbit/s時兩者差距達到最高的0.9。由于AODV的路由開銷主要來自于建立路由時泛洪廣播的路由請求報文RREQ。在PS-AODV中，處于“癱瘓”和“擁塞”狀態中的節點會有選擇性地丟棄RREQ分組。且PS-AODV提高了分組傳送率，減少了路由重傳的次數，從而減少了初始化路由發現的次數，有效地降低了RREQ分組的產生。在路由發現過程中，收到同一源節點相同廣播ID的中間節點，會通過比較metric值后刪除m值大的路徑，減少了RREQ的轉發，從而減少了網絡路由開銷，所以PS-AODV的路由開銷要低于AODV。

圖4顯示了網絡生存時間隨網絡負載變化情況，在此項分析中，選用了第一個節點與第n/2個節點死亡時間的中值作為網絡生存時間，這是因為當網絡中第n/2個節點死亡以后，整個網絡將會急劇惡化，失去其使用價值。當網絡負載增加時，PS-AODV和AODV的網絡生存時間都降低，PS-AODV的網絡生存時間要長于AODV,這主要由于PS-AODV會根據節點負載情況選擇負載更小的節點，使整個網絡的能量消耗更加均衡，避免了網絡中心的節點過早耗盡的能量，從而延長了網絡的生存時間。

5 結束語

本文在AODV基礎上提出了一個基于路徑選擇和應答拒絕算法的改進MANET路由協議PS-AODV。它根據本地節點的負載情況和可用能量來決定是否應答，并根據RREQ分組和節點中的metric值進行路徑選擇，從而實現負載均衡的目的。PS-AODV降低了因為網絡中心的節點能耗過快、負載過重而造成的網絡擁塞概率。仿真顯示PS-AODV在分組傳送率、平均端到端時延、路由開銷和網絡生存時間等性能指標上較AODV有一定提高。今后的工作主要是將PS-AODV協議與其他負載平衡協議[6]對比，并對協議進行進一步改進，提高其性能。

1 陳林星,曾曦,曹毅.移動Ad Hoc網絡.北京:電子工業出版社,2006

2 Best P,Gundeti S,Pendse R.Self-learning Ad Hoc routing protocol.In:Proc of the 58th Vehicular Technology Conference,Orlando,Florida,USA,2003

3 Eshghi F,Elhakeem A K.Performance analysis of Ad Hoc wireless LANs for real-time traffic.IEEE Journal on Selected Areas in Communications,2003,21(2):204～215

4 IETF RFC 3561.Ad Hoc on-demand distance vector(AODV)routing,2003

5 于斌，孫斌，溫暖等，NS-2與網絡模擬.北京：人民郵電出版社，2007

6 Lee S J,Gerla M.Dynamic load-aware routing in Ad Hoc networks.In:IEEE International Conference on Communications(ICC),Helsinki,Finland,2001