組網(wǎng)中基于ＡＯＤＶ協(xié)議的ＱｏＳ延伸及優(yōu)化

(1. 江漢大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院， 武漢 430056； 2.武漢理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 武漢 430063)



摘 要：

為了提高自組網(wǎng)的性能并滿足多媒體數(shù)據(jù)傳輸?shù)葢?yīng)用的需要，提出了一種基于AODV協(xié)議的QoS延伸及優(yōu)化算法。該算法以AODV為基礎(chǔ)，采用限制路由請求分組轉(zhuǎn)發(fā)的機(jī)制并獲取穩(wěn)定的路由，并滿足QoS約束條件。仿真實(shí)驗(yàn)結(jié)果表明，該算法降低了網(wǎng)絡(luò)負(fù)載，減少了開銷和提高了數(shù)據(jù)包傳輸成功率。

關(guān)鍵詞：移動自組網(wǎng); Ad hoc按需距離矢量路由; 服務(wù)質(zhì)量

中圖分類號：TP393 文獻(xiàn)標(biāo)志碼：A

文章編號：10013695(2008)12377302



Quality of service extension and optimization based on AODV in MANET



LIAN Jin1，2， LI Layuan2， ZHU Xiaoyan1

(1.School of Mathematics Computer Science， Jianghan University， Wuhan 430056，China； 2.College of Computer Science Technology， Wuhan University of Technology， Wuhan 430063，China)



Abstract:In order to enhance the performance of mobile Ad hoc network (MANET) and satisfy the demand of many new multimedia applications， the paper presented a QoS routing optimization algorithm based on AODV. It adopted the mechanism of limited route request transmitting and satisfied multiple QoS constraints. The simulation results showed that the approach provides an efficient method of reducing the network overload and enhancing the rate of packet success transmission.

Key words：MANET; AODV; QoS （quality of service）



移動自組網(wǎng)（MANET）是在沒有中心基礎(chǔ)設(shè)施，由一些移動用戶自組織形成的多跳無線移動網(wǎng)絡(luò)，其具有網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動態(tài)變化、有限的傳輸帶寬等特點(diǎn)^[1，2]，因此，有線網(wǎng)絡(luò)中的路由協(xié)議不能滿足其需要。目前MANET中的路由協(xié)議主要可分為表驅(qū)動（table driven）協(xié)議和按需（ondemand）路由協(xié)議。不管哪類協(xié)議，為了建立數(shù)據(jù)傳輸路徑，大多都需要通過廣播機(jī)制來完成路由請求。洪泛式廣播協(xié)議^[1~3]采用一種簡單的策略， 即所有的節(jié)點(diǎn)不論何時收到一個廣播報(bào)文即將其發(fā)送給它相鄰的節(jié)點(diǎn)。由于它不需要任何特殊的設(shè)備或算法， 在Ad hoc 網(wǎng)絡(luò)中大多采用這種方法進(jìn)行廣播。但這種方法造成一系列問題，如信道爭用加劇、大量報(bào)文被重復(fù)發(fā)送等問題。這給MANET的效率和性能帶來了巨大的影響。同時，隨著高性能網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，自組網(wǎng)同樣需要提供QoS控制，以支持多種應(yīng)用，包括實(shí)現(xiàn)多媒體數(shù)據(jù)傳輸，實(shí)時信息獲取等。如何限制廣播路由請求來控制網(wǎng)絡(luò)負(fù)載、滿足QoS要求，是提高M(jìn)ANET網(wǎng)絡(luò)性能的一個非常重要的方面^[1，4]。本文通過對現(xiàn)有自組網(wǎng)路由協(xié)議的研究，以AODV路由協(xié)議為基礎(chǔ)，提出了一種基于AODV優(yōu)化的QoS 路由算法QOAODV (a QoS routing optimization algorithm based on AODV in MANET)。該算法使用時延、帶寬和代價作為QoS 參數(shù)，來滿足業(yè)務(wù)服務(wù)質(zhì)量的需求。

1 QoS約束的網(wǎng)絡(luò)模型

在研究路由問題時，一個網(wǎng)絡(luò)可以表示為一個加權(quán)圖G(N，E)。其中：N表示節(jié)點(diǎn)集合；E表示節(jié)點(diǎn)間的鏈路集合。為不失一般性，只考慮這樣一類圖，即在該類網(wǎng)絡(luò)中任意一對節(jié)點(diǎn)間最多只有一條鏈路。設(shè)R為正實(shí)數(shù)集，R+為非負(fù)實(shí)數(shù)集，對于任意鏈路e∈E，定義某些QoS特征值：延遲函數(shù)delay(e):E→R，帶寬函數(shù)bandwidth(e):E→R，延遲抖動函數(shù)delayjitter(e):E→R+，代價函數(shù)cost(e):E→R。類似地，對于任意節(jié)點(diǎn)n∈N，QoS定義特征值如下：延遲函數(shù)delay(n):E→R，帶寬函數(shù)bandwidth(n):E→R，延遲抖動函數(shù)delayjitter(n):E→R+，代價函數(shù)cost(n):E→R。設(shè)P(s，m)表示從源節(jié)點(diǎn)s至端節(jié)點(diǎn)m的路徑，P(s，m)的QoS特征值與鏈路和節(jié)點(diǎn)的特征值相關(guān)，定義如下：

delay(P(s，m))=∑e∈P(s，m)delay(e)+∑n∈P(s，m)delay(n)

cost(P(s，m))=∑e∈P(s，m)cost(e)+∑n∈P(s，m)cost(n)

bandwidth(P(s，m))=min{bandwidth(e)，e∈P(s，m)}

delayjitter(P(s，m))=∑e∈P(s，m)delayjitter(e)+

∑n∈P(s，m)delayjitter(n)（1）



多QoS約束問題是發(fā)現(xiàn)一條路徑P從源節(jié)點(diǎn)s到目的節(jié)點(diǎn)d滿足：

delay(P(s，m))≤Dc，min(cost(P(s，m)))

bandwidth(P(s，m))≥Bc，delayjitter(P(s，m))≤DJc

（2）



其中:Dc表示延遲約束;Bc表示帶寬約束;DJc表示延遲抖動約束。由于節(jié)點(diǎn)和鏈路具有等價性，在本文討論中只考慮鏈路或邊的帶寬約束、延遲約束以及最小代價，假設(shè)所有的節(jié)點(diǎn)均有足夠的資源。

2 優(yōu)化的機(jī)制

AODV協(xié)議是一種按需路由協(xié)議，源節(jié)點(diǎn)通過廣播路由請求分組（RREQ），中間節(jié)點(diǎn)收到路由分組后向它的周圍節(jié)點(diǎn)廣播分組，直到找到目的節(jié)點(diǎn)，其采用洪泛的路由發(fā)現(xiàn)機(jī)制。這種機(jī)制加大了網(wǎng)絡(luò)負(fù)載和控制開銷。為了解決這個問題，本文提出了一種穩(wěn)定的、限制路由請求分組轉(zhuǎn)發(fā)的機(jī)制。當(dāng)某節(jié)點(diǎn)收到RREQ包時，該節(jié)點(diǎn)要進(jìn)行有選擇的廣播或丟棄該包。因此，本優(yōu)化機(jī)制主要解決兩個問題：a）節(jié)點(diǎn)如何有選擇地轉(zhuǎn)發(fā)分組；b）如何判斷鏈路的穩(wěn)定性。

本文中將自組網(wǎng)中的節(jié)點(diǎn)相對分成兩類(見定義1)^[5]，即上游節(jié)點(diǎn)（upnode）和下游節(jié)點(diǎn)（downnode）。只有上游節(jié)點(diǎn)能夠轉(zhuǎn)發(fā)RREQ包，而下游節(jié)點(diǎn)不能發(fā)送RREQ包給其上游節(jié)點(diǎn)。由于AODV協(xié)議自身特點(diǎn)不能滿足要求，為了能夠判斷上游節(jié)點(diǎn)還是下游節(jié)點(diǎn)，在RREQ包中添加了一個輔助域，即采用標(biāo)記的方法^[3，5]。上游節(jié)點(diǎn)在RREQ包中進(jìn)行標(biāo)記，然后轉(zhuǎn)發(fā)。圖1中，在節(jié)點(diǎn)N的傳輸范圍之內(nèi)，節(jié)點(diǎn)N為上游節(jié)點(diǎn)，節(jié)點(diǎn)N的下游節(jié)點(diǎn)為節(jié)點(diǎn)1~4。

定義1 當(dāng)節(jié)點(diǎn)i轉(zhuǎn)發(fā)RREQ包給節(jié)點(diǎn)j時，稱節(jié)點(diǎn)i為上游節(jié)點(diǎn)，節(jié)點(diǎn)j為下游節(jié)點(diǎn)。

由于自組網(wǎng)中節(jié)點(diǎn)移動性的特點(diǎn)，節(jié)點(diǎn)間的通信鏈路隨時可能斷開，總希望找到一條較穩(wěn)定的通信鏈路，從而減少路由重構(gòu)、降低網(wǎng)絡(luò)控制開銷。本文中節(jié)點(diǎn)采用hello消息機(jī)制^[5]來標(biāo)志其自身的存在，每個節(jié)點(diǎn)建立一個鄰接表，該表記錄此節(jié)點(diǎn)收到的鄰節(jié)點(diǎn)的hello消息數(shù)，通過該表中的hello消息數(shù)判斷鏈路聯(lián)通性和穩(wěn)定性。鄰接表的組成主要包括兩部分，即節(jié)點(diǎn)標(biāo)志號（node identification）和穩(wěn)定度（connectivity）。分別表示鏈路連通性和穩(wěn)定性。如果某節(jié)點(diǎn)的鄰接表中的穩(wěn)定度域的值大于穩(wěn)定度的門限值（connectivity threshold）時，則表明該節(jié)點(diǎn)與其鄰節(jié)點(diǎn)的通信鏈路是穩(wěn)定的。穩(wěn)定度的門限取值與傳輸范圍、移動節(jié)點(diǎn)的最大速度，發(fā)送hello消息的時間間隔等因素有關(guān)。表1顯示了圖1中節(jié)點(diǎn)N的每個鄰節(jié)點(diǎn)的穩(wěn)定度。當(dāng)穩(wěn)定度的門限值取200時，則從表1中可知鏈路（N，2）和（N，4）是穩(wěn)定的。

表1 節(jié)點(diǎn)N的鄰接表

鄰節(jié)點(diǎn)標(biāo)志號穩(wěn)定度鄰節(jié)點(diǎn)標(biāo)志號穩(wěn)定度

1153123

23004260

3 QOAODV路由算法描述

在QOAODV路由算法中，除了AODV協(xié)議中所具有的相關(guān)信息外，還應(yīng)該具有延遲約束、帶寬約束、代價參數(shù)以及上游節(jié)點(diǎn)的標(biāo)志。其一般過程包括路由發(fā)現(xiàn)和路由維護(hù)階段。路由發(fā)現(xiàn)的一般過程如下：

a)如果本地存在到目的節(jié)點(diǎn)D的路由，根據(jù)式（2）判斷從源節(jié)點(diǎn)S到目的節(jié)點(diǎn)D的路由是否滿足帶寬和延遲約束，若滿足，直接傳送數(shù)據(jù)包；否則轉(zhuǎn)b)。

b)本地節(jié)點(diǎn)在RREQ包中添加自身標(biāo)記（即標(biāo)記上游節(jié)點(diǎn)），廣播對D的RREQ包。

c)若中間節(jié)點(diǎn)不是一個下游節(jié)點(diǎn)或收到一個重復(fù)的RREQ請求包或中間節(jié)點(diǎn)與其上游節(jié)點(diǎn)的帶寬不滿足帶寬約束Bc，則丟棄請求包；否則轉(zhuǎn)步驟d)。

d)中間節(jié)點(diǎn)檢查鄰接表，判斷其與上游節(jié)點(diǎn)的穩(wěn)定度是否大于給定的穩(wěn)定度的門限值，若大于門限值，則轉(zhuǎn)發(fā)RREQ包，并標(biāo)記自身；否則丟棄該RREQ請求包。

e)目的節(jié)點(diǎn)收到路由請求包后并不立即回復(fù)，等待一段時間，緩存來自同一個源節(jié)點(diǎn)的所有路由請求，然后計(jì)算整個路由的延遲和代價是否滿足延遲Dc約束和最小代價，選擇一條最優(yōu)路徑，發(fā)送RREP應(yīng)答包，源節(jié)點(diǎn)S可以進(jìn)行數(shù)據(jù)傳輸。

f)每個源節(jié)點(diǎn)在發(fā)起路由請求時，設(shè)置一個定時器，若在規(guī)定的時間沒有收到任何RREP，則重新發(fā)起路由請求（算法的其他細(xì)節(jié)與AODV協(xié)議相同）。

在路由發(fā)現(xiàn)階段通過周期性地發(fā)送hello分組來判斷鏈路的穩(wěn)定性，當(dāng)不考慮QoS約束時，尋找從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路由應(yīng)該是最穩(wěn)定的，但是當(dāng)有QoS約束或網(wǎng)絡(luò)中節(jié)點(diǎn)移動速度較大時，路由會失效。因此，QOAODV算法需要進(jìn)行路由維護(hù)。其一般過程是若中間節(jié)點(diǎn)發(fā)現(xiàn)鏈路斷開，則向其上游節(jié)點(diǎn)鏈路失效的信息，然后由該節(jié)點(diǎn)將鏈路失效信息轉(zhuǎn)發(fā)給活躍鄰節(jié)點(diǎn)，直至源節(jié)點(diǎn)收到鏈路失效信息。當(dāng)源節(jié)點(diǎn)同時收到RREP分組和鏈路失效信息時，丟棄RREP分組，重新發(fā)起路由重構(gòu)。

4 仿真

為了對QOAODV路由算法的性能進(jìn)行分析，采用NS的網(wǎng)絡(luò)仿真工具。仿真環(huán)境和主要參數(shù)如下：網(wǎng)絡(luò)中有40個節(jié)點(diǎn)，地理范圍1 000 m×1 000 m，節(jié)點(diǎn)的最大移動速度為20 m/s，節(jié)點(diǎn)的傳輸范圍是250 m，仿真時間是300 s，MAC協(xié)議為IEEE 802.11，節(jié)點(diǎn)按Waypoint模型隨機(jī)移動，信號衰減服從自由空間模型，業(yè)務(wù)為CBR，每包512 Byte。算法性能主要從數(shù)據(jù)包傳輸成功率和平均控制開銷兩個方面來分析，同時將QOAODV與QAODV^[3，6，7]進(jìn)行性能比較（分別選擇10和30個源節(jié)點(diǎn)同時發(fā)起路由請求，以及當(dāng)穩(wěn)定度門限值選擇200和500時算法性能情況）。

圖2顯示了在網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為40、源節(jié)點(diǎn)數(shù)為10時，數(shù)據(jù)包傳輸成功率與節(jié)點(diǎn)移動速度的關(guān)系。從圖2中可知，隨著節(jié)點(diǎn)移動速度的增大，三種算法的數(shù)據(jù)包傳輸成功率有所下降，但它們之間差別不是很明顯。但是在圖3中，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為40、源節(jié)點(diǎn)數(shù)為30時，三種算法的數(shù)據(jù)包傳輸成功率差別比較明顯。其原因在于當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)移動速度不斷增大且發(fā)起路由請求的源節(jié)點(diǎn)數(shù)目增加時，不可避免地會出現(xiàn)鏈路失效的情況，此時需要進(jìn)行路由維護(hù)。QOAODV算法尋找的是一條穩(wěn)定的QoS路由；而QAODV選擇的卻只是滿足QoS的路由。因此，QAODV進(jìn)行路由重構(gòu)的概率要比QOAODV大得多，從而會降低數(shù)據(jù)包的傳輸成功率。

圖4中顯示了當(dāng)節(jié)點(diǎn)平均移動速度為10 m/s時，網(wǎng)絡(luò)的平均控制開銷與網(wǎng)絡(luò)中節(jié)點(diǎn)個數(shù)之間的關(guān)系。從圖4中可知，三種算法的平均控制開銷QAODV最大、QOAODV_500最小。QOAODV中采用了限制路由請求的策略；而QAODV中采用的是洪泛式的廣播策略，同時QOAODV中還采用了選擇穩(wěn)定路由的策略，減少了路由重構(gòu)的開銷。

5 結(jié)束語

本文討論了QoS約束的路由問題，描述了基于QoS約束的網(wǎng)絡(luò)模型，提出了一種優(yōu)化的基于AODV的QoS路由算法。該算法采用限制路由請求轉(zhuǎn)發(fā)的機(jī)制降低網(wǎng)絡(luò)的負(fù)載和控制開銷，利用hello消息機(jī)制判斷節(jié)點(diǎn)間的穩(wěn)定度，從而選擇一條滿足帶寬、延遲以及代價約束的穩(wěn)定路由。仿真實(shí)驗(yàn)結(jié)果表明優(yōu)化的AODV算法的有效性，提高了數(shù)據(jù)包的傳輸成功率、降低了控制包的開銷。

參考文獻(xiàn)：

［1］李臘元，李春林.多QoS約束的多播路由協(xié)議[J].軟件學(xué)報(bào)，2004，15(2):286291.

［2］孫寶林，李臘元.Ad hoc網(wǎng)絡(luò)QoS多播路由協(xié)議[J]. 計(jì)算機(jī)學(xué)報(bào)，2004，27(10):14021407.

［3］PERKINS C， ROYER E B. Quality of service for Ad hoc ondemand distance vector routing [EB/OL]. (200306).http://draftperkinsmanetaodvqos02.txt.

［4］LIAN Jin， LI Layuan， ZHU Xiaoyan. A multiple QoS constraints routing protocol based on mobile predicting in ad hoc network[C]//Proc of the 3rd IEEE International Conference on Wireless Communications， Networking and Mobile Computing.[S.l.]:IEEE Press， 2007:16081611.

［5］LEE S J， YOUN J S， JUNG S H， et al. Selective routerequest scheme for ondemand routing protocols in Ad hoc networks[C]//Proc of the 4th International Conference on Ad hoc， Mobile， and Wireless Networks.[S.l.]:SpringerVerlag， 2005:153163.

［6］PERKINS C， ROYER E B， DAS S. RFC 3561， Ad hoc ondemand distance vector (AODV) routing[S]. 2003.

［7］QI Xue， GANZ A. Ad hoc QoS ondemand routing (AQOR) in mobile Ad hoc networks[J]. Journal of Parallel and Distributed Computing， 2003，6(3): 154165.