AODV帶寬估計和鏈路穩(wěn)定度的QoS擴展研究

孫小強，蔡茂國，陳劍勇，梁榮堅

(深圳大學計算機與軟件學院，廣東深圳518060)

目前對于Ad Hoc網絡可以通過加入帶寬、時延和鏈路穩(wěn)定度等進行QoS保證。AVAODV［1］利用節(jié)點接收到鄰居節(jié)點發(fā)送HELLO分組的機制進行鏈路穩(wěn)定度的計算，但對鏈路穩(wěn)定度并沒有進行考慮。文獻［2］介紹了一種基于令牌傳送機制以及融入CDMA的混合令牌碼分區(qū)多路接入(Token－Code Division Multiple Access)的MAC協(xié)議，模擬實驗結果表明所提出的MAC機制能夠有效地減少分組時延及縮小隊列長度。SQAODV協(xié)議［3］在AODV協(xié)議加入帶寬估計和鏈路穩(wěn)定度選項，利用節(jié)點接收鄰居節(jié)點廣播RREQ分組的功率估計鏈路穩(wěn)定度。CLQ－AODV協(xié)議［4］采用計算MAC層信道空閑時間比率估算節(jié)點剩余帶寬，對AODV協(xié)議進行了帶寬需求和時延要求的擴充。Xiaoxia Huang針對VANETS提出了一種有關節(jié)點不相關的多路徑路由協(xié)議［5］，在文獻［1］中有對節(jié)點不相關性優(yōu)缺點的論述。QAODV_BC［6］路由協(xié)議采用了帶寬估計、業(yè)務流接入控制和鏈路穩(wěn)定度選項改進AODV協(xié)議的QoS性能。

AODV協(xié)議［7］是Ad Hoc網絡一種比較成熟的按需距離向量路由算法，并且是一種支持“盡力而為”的路由協(xié)議，因此存在一些方面的不足［6］。首先，AODV協(xié)議在路由尋找的過程中，僅把跳數作為路徑選擇的依據。只考慮跳數會導致在節(jié)點發(fā)送報文時有可能帶寬不足而使路由不斷重啟、丟包率過大或者時延過大。其次，AODV協(xié)議在進行路由尋找時，源節(jié)點只對首次接收到的RREP(路由回復)分組進行響應，對后到的路由請求分組直接丟棄，并沒有考慮后到的RREP分組可能包含鏈路穩(wěn)定度更好的路徑。AVAODV協(xié)議中采用鏈路穩(wěn)定度方法克服了上述AODV協(xié)議的一些缺點，QVAODV協(xié)議在AVAODV協(xié)議的基礎上增加了帶寬估計選項，采用鏈路穩(wěn)定度與帶寬估計相結合的方法來提高Ad Hoc網絡傳輸多媒體數據的性能，并且還解決了AODV協(xié)議源節(jié)點只對首次到達的RREP分組進行響應的缺點。

1 QoS參數的計算

1.1 帶寬的計算

帶寬估計在研究Ad Hoc網絡QoS性能時是一個很重要的參數。帶寬估計一般指兩個節(jié)點之間可用于數據傳輸的最大吞吐量。帶寬估計會受到節(jié)點碰撞、空閑信道占用比率和回退時間等方面的影響［8－9］。AVAODV協(xié)議只考慮鏈路穩(wěn)定度，而沒有考慮帶寬估計的因素。目前無線帶寬估計有以下兩種檢測機制:一是測量MAC層的信道空閑率［3－4，6］;二是測量網絡層單位時間的吞吐量。

由于QVAODV協(xié)議MAC層采用IEEE802.11協(xié)議，可以采用計算信道忙閑比的方法來計算節(jié)點的可利用帶寬。在QVAODV協(xié)議采用將一段時間劃分成m個相同的時間段，每隔一個時間段觀察MAC層信道是否空閑，空閑信道個數記為n，節(jié)點的剩余帶寬為

上述的帶寬估計方法存在一個缺點，就是用過去一段時間的帶寬來代替未來時間的帶寬，得到的帶寬可能不準確。為了解決這個問題，平滑處理剩余帶寬，即

式中:B0=0.5b0;Bi表示節(jié)點在i時刻的剩余帶寬;Bi－1表示節(jié)點在i－1時刻的剩余帶寬;bi表示節(jié)點在i時刻由式(1)得到的剩余帶寬;C表示節(jié)點在i時刻的最大帶寬。

1.2 鏈路穩(wěn)定度的計算

QVAODV協(xié)議中計算某條鏈路的鏈路穩(wěn)定度首先需計算相鄰節(jié)點的鏈路穩(wěn)定度，得到該條鏈路所有相鄰節(jié)點的鏈路穩(wěn)定度之后，便可以計算這條鏈路的鏈路穩(wěn)定度，具體計算過程參見文獻［1］。根據上述計算鏈路穩(wěn)定度方法來計算各個備選路徑的鏈路穩(wěn)定度，選擇鏈路穩(wěn)定度好并且滿足帶寬需求的路徑作為最優(yōu)路徑。

2 QVAODV路由協(xié)議的實現

2.1 中間節(jié)點轉發(fā)路由請求分組的優(yōu)化

在AODV協(xié)議中，節(jié)點接收到RREQ分組后，便會建立或更新沒有有效序列號的前一跳的路由。然后節(jié)點判斷最近PATH_DISC_TIME(路由尋找時間)內是否接收到相同源節(jié)點ID(序列號)與相同RREQ_ID(路由請求序列號)的RREQ分組，如果已收到相同源節(jié)點ID與相同RREQ_ID的RREQ分組，節(jié)點會將后到的RREQ分組直接丟掉。AODV采用這種中間節(jié)點轉發(fā)RREQ分組的策略并沒有考慮后到RREQ分組所在路徑的鏈路穩(wěn)定度可能會高于先到路徑的鏈路穩(wěn)定度。由于AODV協(xié)議采取這種直接丟棄后到RREQ分組的方法，直接影響了AODV協(xié)議的性能。

在QVAODV協(xié)議中，根據帶寬估計和鏈路穩(wěn)定度的情況來決定是否對RREQ分組進行轉發(fā)。雖然AVAODV協(xié)議也采用了鏈路穩(wěn)定度選項對RREQ分組轉發(fā)進行了優(yōu)化，便僅僅考慮鏈路穩(wěn)定度并不能適應數據流帶寬需求的動態(tài)性變化。QVAODV路由協(xié)議只有在中間節(jié)點滿足RREQ帶寬要求并且鏈路穩(wěn)定度不小于規(guī)定閾值時，才將中間節(jié)點添加到備選路徑中，RREQ分組才會被該中間節(jié)點轉發(fā)，否則丟棄該RREQ分組。這樣的處理策略保證了所選路徑的穩(wěn)定性及高效性，提高了Ad Hoc網絡傳輸數據分組的性能。

2.2 最優(yōu)路徑的選擇

在AODV協(xié)議中，源節(jié)點只對首次到達的RREP分組進行響應，而對后到RREP分組采取丟棄的策略，有可能忽略后到RREP分組所在路徑的鏈路穩(wěn)定度可能會更好。QVAODV路由協(xié)議對于后到RREP分組采取不直接丟棄的方法，并且判斷它的鏈路穩(wěn)定度是否比路由表中相同目的節(jié)點的鏈路穩(wěn)定度大且更新次數不超過設定好的閾值。當Ad Hoc網絡傳輸數據分組時，可能會由于后到RREP分組所在路徑鏈路穩(wěn)定度更好而發(fā)生改變，但對于正在傳送數據分組的業(yè)務流需求來說并沒有什么影響，相反會由于鏈路穩(wěn)定度的提高而使網絡性能更好。

2.3 QVAODV 具體路由實現過程［1］

為了使QVAODV協(xié)議能夠正常運行，需要對AODV協(xié)議的RREQ分組、RREP分組、BROADCAST_ID(RREQ廣播分組緩存)、AODV_RT_ENTRY(AODV路由表項)及AODV_NEIGHBOR(AODV鄰接表項)進行擴充，需要擴充的分組選項如表1和表2所示。

表1 AODV RREQ與RREP需要擴充的選項

表2 AODV廣播分組緩存、路由表項與鄰接表項需要擴充的選項

在QVAODV協(xié)議中，QVAODV RREQ分組比AODV RREQ分組增加了3個選項，分別是AHV選項、BREQ選項和備選路徑節(jié)點ID序列，其中AHV表示鏈路穩(wěn)定度，BREQ表示帶寬需求。相應地，QVAODV RREP也增加了相同的3個選項。QVAODV RT_ENTRY比原先的AODV RT_ENTRY增加了AHV選項、BREQ選項和COUNT選項，COUNT選項表示目的節(jié)點收到RREP的個數。QVAODV BROADCAST_ID比原來的AODV BROADCAST_ID增加了COUNT_FORWARD選項，用來保存中間節(jié)點接收到RREQ分組的次數，如果超過了一定次數，則丟棄該RREQ分組。QVAODV_NEIGHBOR比 AODV_NEIGHBOR增加了COUNT_HELLO字段，用來保存鄰居節(jié)點成功接收到HELLO分組的個數。相比較AVAODV協(xié)議而言，QVAODV協(xié)議的RREQ分組和RREP分組分別增加了BREQ帶寬需求選項，以適應中間節(jié)點動態(tài)變化的可用帶寬，并且QVAODV協(xié)議的 RT_ENTRY選項也比AVAODV協(xié)議增加了BREQ選項和COUNT選項。

在QVAODV路由協(xié)議中，若源節(jié)點需要向目的節(jié)點發(fā)送數據而源節(jié)點路由表中并不存在有效路由時，則啟動路由尋找過程。從源節(jié)點發(fā)出RREQ分組，若遇到滿足中間節(jié)點轉發(fā)規(guī)則的節(jié)點則會被轉發(fā)，如果RREQ分組被轉發(fā)，中間節(jié)點ID會被記錄到RREQ分組選項中，AHV值也會被更新。中間節(jié)點轉發(fā)RREQ分組的規(guī)則:如果中間節(jié)點通過MAC層估計的帶寬值大于等于RREQ分組所要求的帶寬值并且滿足原先AVAODV協(xié)議中間節(jié)點轉發(fā)RREQ分組的判定條件，則中間節(jié)點轉發(fā)RREQ分組，同時更新RREQ的AHV值，將轉發(fā)節(jié)點的ID加入到RREQ分組中間節(jié)點序列中，并且將中間節(jié)點轉發(fā)該RREQ分組的次數加1;否則，丟棄該 RREQ分組。QVAODV協(xié)議轉發(fā)RREQ分組的規(guī)則比AVAODV協(xié)議增加了中間節(jié)點的剩余帶寬是否大于等于RREQ的需求帶寬判定選項。

源節(jié)點在第一次收到RREP分組時，建立相應的路由表項，將RREP分組的AHV值與BREQ值記錄到路由表中，并且將路由表中的更新次數初始化為0。對于后到的RREP分組，則可以當作更新路由表項而不直接丟棄，是否丟棄還得看是否滿足路由更新條件，并且采用更新次數來限制接收到的RREP分組個數。如果后到RREP分組的AHV值大于路由表中相同目的節(jié)點路由表項的AHV值且該路由表項的更新次數不大于15時，則更新該路由表項，同時將該路由表項的更新次數增加1;否則，將忽略后到RREP分組。

3 仿真實驗結果與性能分析

利用 NS－2.35對 AODV協(xié)議、AVAODV協(xié)議和QVAODV協(xié)議的性能進行對比分析。

3.1 仿真實驗場景

在Ubuntu 12.04操作系統(tǒng)下，采用NS－2.35仿真平臺對QVAODV路由協(xié)議進行仿真模擬。仿真場景設置為1 000 m×1 000 m的大小，節(jié)點個數為25，隨機布置在網絡中，并且設置部分節(jié)點動態(tài)地移動，以模擬Ad Hoc動態(tài)環(huán)境。MAC層采用IEEE802.11協(xié)議，無線信道帶寬為2 Mbit/s。節(jié)點的最大通信范圍為250 m，數據分組大小為512 byte。仿真時間設置為800 s，業(yè)務流設置為CBR流，在本實驗中有兩條CBR流。為了驗證QVAODV協(xié)議的性能，仿真了相同條件下的AODV協(xié)議和AVAODV協(xié)議進行參照對比。

3.2 性能評價

1)數據丟包率:(源節(jié)點發(fā)送數據分組的個數－目的節(jié)點正確接收到的分組個數)/源節(jié)點發(fā)送數據分組的個數。分組丟包率越低，數據分組成功傳送到目的節(jié)點的比例越大。

2)平均路由開銷:發(fā)送和轉發(fā)的路由控制分組個數/目的節(jié)點接收到的數據分組。平均路由開銷越小，路由協(xié)議效率越高。

3)平均端到端分組時延:所有數據分組從源節(jié)點到目的節(jié)點所花時間總和/目的節(jié)點成功接收到數據分組個數。端到端平均時延越小，數據傳送所花費的時間越少。

3.3 實驗結果分析

1)圖1是AODV協(xié)議、AVAODV協(xié)議和QVAODV協(xié)議數據丟包率的比較，很明顯可以看出，QVAODV協(xié)議比AODV協(xié)議數據丟包率要低很多，AVAODV協(xié)議和QVAODV協(xié)議的數據丟包率曲線幾乎重疊在一起。實際上AVAODV協(xié)議與QVAODV協(xié)議的丟包率還是有差別的，由于圖1的坐標軸刻度過大看不出兩者的差異。為了更好地比較QVAODV協(xié)議與AVAODV協(xié)議的數據丟包率大小，特意將相同數據轉發(fā)率下的AVAODV協(xié)議丟包率與QVAODV協(xié)議數據丟包率進行相減，得到的差值如果為正，則說明相同數據轉發(fā)率下QVAODV協(xié)議數據丟包率要小于AVAODV協(xié)議數據丟包率。圖2表示相減后得到的差值，由于QVAODV協(xié)議加入了帶寬估計選項，相同數據發(fā)送速率下的QVAODV協(xié)議數據丟包率要比AVAODV協(xié)議要低些。

2)圖3是AODV協(xié)議、AVAODV協(xié)議和QVAODV協(xié)議平均端到端分組時延的比較，可以看出，相同數據轉發(fā)率下QVAODV協(xié)議的平均端到端分組時延要比AVAODV協(xié)議的平均端到端分組時延小。將AODV協(xié)議與QVAODV協(xié)議的平均端到端分組時延進行比較可以看出，數據轉發(fā)率從360 kbit/s開始，QVAODV協(xié)議要明顯比AODV協(xié)議的平均端到端分組時延小。

3)圖4是AODV協(xié)議和QVAODV協(xié)議的平均路由開銷比較，很明顯可以看出，AODV協(xié)議的平均路由開銷明顯小于QVAODV協(xié)議的平均路由開銷。從圖5可以看出，QVAODV協(xié)議的平均路由開銷要小于AVAODV協(xié)議的平均路由開銷。

圖1 數據丟包率的比較

圖2 AVAODV與QVAODV數據丟包率差值

圖3 平均端到端分組時延比較

圖4 AODV與QVAODV平均路由開銷比較

4 結語

QVAODV協(xié)議通過對AVAODV協(xié)議添加帶寬估計選項以適應數據流帶寬需求的動態(tài)性變化，并且針對AODV協(xié)議源節(jié)點只對首次到達的RREP分組進行響應的缺點進行了改進，源節(jié)點在一定的次數限制下選擇鏈路穩(wěn)定度最好與滿足帶寬需求的一條路徑來進行數據分組的傳輸。仿真實驗結果表明，QVAODV協(xié)議相比較AVAODV協(xié)議在數據丟包率、平均端到端分組時延和平均路由開銷均有改進，尤其在平均端到端時延和平均路由開銷方面效果顯著。AODV協(xié)議與QVAODV協(xié)議在數據丟包率和平均端到端分組時延方面，QVAODV協(xié)議要明顯好于AODV協(xié)議，盡管QVAODV協(xié)議的平均路由開銷還遠遠大于AODV協(xié)議的平均路由開銷。綜上所述，所提出的QVAODV協(xié)議在Ad Hoc網絡中性能表現優(yōu)異，對于提高Ad Hoc網絡數據傳送性能有著重要的現實意義。

在實際Ad Hoc網絡應用中由于節(jié)點是動態(tài)移動的，并且還要承擔數據轉發(fā)任務，如何降低節(jié)點的能量消耗［10］尤其重要，而且 Ad Hoc 網絡還存在安全接入［11－12］的問題，非法節(jié)點的接入嚴重影響了Ad Hoc網絡的QoS性能。因此，不僅需要考慮帶寬估計和鏈路穩(wěn)定度，而且還要考慮節(jié)點的能量限制、節(jié)點的安全接入等方面的因素。接下來準備結合節(jié)點的能量限制與節(jié)點的安全接入提出更好的帶寬估計和鏈路穩(wěn)定度算法。

圖5 AVAODV與QVAODV平均路由開銷比較

［1］ HOSSEN M，XIN Z，ZHENHUA L，et al.Jamming－resilient multipath routing［J］.IEEE Trans.Dependable And Secure Computing，2012，6(9):852－864.

［2］ LIU IS，FAMBIRAIT，XU H J.A hybrid token－CDMA MAC protocol forwireless Ad Hoc networks［J］.IEEE Trans.Mobile Computing，2008(5):557－560.

［3］梁榮堅，蔡茂國，張立海.Ad Hoc網絡中基于鏈路穩(wěn)定度的QoS路由協(xié)議［J］.計算機工程與應用，2010，46(32):105－107.

［4］陳麗芳，陳燕，徐白.基于跨層設計AODV的QoS擴展和仿真實現［J］.廣西科學院學報，2011，27(3):221－227.

［5］ HUANG Xiaoxia，FANG Yuguang.Performance study of node－disjoint multipath routing in vehicular Ad Hoc networks［J］.IEEE Trans.Vehicular Technology，2009，58(4):1942－1950.

［6］梁榮堅.移動Ad Hoc網絡QoS路由算法的研究［D］.深圳:深圳大學，2010.

［7］陳林星，曾曦，曹毅.移動Ad Hoc網絡——自組織分組無線網絡技術［M］.北京:電子工業(yè)出版社，2012.

［8］吳大鵬，武穆清，甄巖.移動自組織網絡可用帶寬估計方法研究進展［J］.通信學報，2010(4):103－115.

［9］ CHEIKH S，CLAUDE C，GUILLAUME C，et al.Bandwidth estimation for IEEE 802.11－based Ad Hoc networks［J］.IEEE Trans.Mobile Computing，2008(10):1228－1241.

［10］廖勇超.Ad Hoc網絡節(jié)能問題研究［D］.長沙:中南大學，2009.

［11］ GANG X，CRISTIAN B，LIVIU I.A policy enforcingmechanism for trusted Ad Hoc networks［J］.IEEE Trans.Dependable and Secure Computing，2011(3):321－325.

［12］ YUDHVIR S，YOGESH C.Security and network performance evaluation of KK＇cryptographic technique inmobile Ad Hoc networks［C］//Proc.IEEE International Advance Computing Conference.［S.l.］:IEEE Press，2009:1152－1154.