移動Ad Hoc網(wǎng)絡(luò)中基于QoS的多路徑路由協(xié)議研究

李 健，董亞雷，王 剛

(1.重慶市民防辦公室，重慶400015;2.重慶郵電大學(xué)，重慶400065)

移動自組織網(wǎng)絡(luò)(簡稱移動Ad Hoc網(wǎng)［1］)作為一個臨時性多跳自治系統(tǒng)，是由一組帶有無線收發(fā)裝置的可移動節(jié)點所組成，并且不依賴于預(yù)設(shè)的基礎(chǔ)設(shè)施，具有可臨時組網(wǎng)、快速展開、無控制中心、抗毀性強等特點，在軍事和民用方面都具有廣闊的應(yīng)用前景，是目前網(wǎng)絡(luò)研究中的熱點問題。近年來，隨著無線通信技術(shù)的迅速發(fā)展，語音、視頻等多媒體業(yè)務(wù)也逐漸應(yīng)用于移動Ad Hoc網(wǎng)，因而如何在移動Ad Hoc網(wǎng)中提供高質(zhì)量的QoS保障［2-3］是當(dāng)前亟待解決的問題。同時值得注意的是，在Ad Hoc網(wǎng)中，數(shù)據(jù)的傳輸主要通過單路徑路由的方式進行，對于大流量數(shù)據(jù)業(yè)務(wù)來說，該方式無論在容錯能力上還是在帶寬利用率［4］上都遠遠無法滿足需求。因此本文將針對移動Ad Hoc網(wǎng)中多路徑QoS路由進行研究，通過推導(dǎo)證明提出路徑長度限制的路徑穩(wěn)定的約束關(guān)系，引入QoS的判定因子對該確定性的最優(yōu)權(quán)值約束算法進行實例化，并在該路由算法的基礎(chǔ)上提出基于QoS保障的多路徑［5］路由協(xié)議(MP-QAODV)。

1 網(wǎng)絡(luò)模型及數(shù)學(xué)描述

本文采用通過一個有向圖G(V，E)表示一個網(wǎng)絡(luò)，V為節(jié)點集合，E為邊集合，e=u→v表示節(jié)點v到節(jié)點u的鏈路，其中每條鏈路e都關(guān)聯(lián)k個相互獨立的權(quán)值w1(e)，w2(e)，…，wk(e)，wj(e)∈R+，?1≤j≤k。向量W(e)=［w1(e)，w2(e)，…，wk(e)］表示鏈路e的權(quán)值矩陣。向量W(p)=［w1(p)，w2(p)，…，wk(p)］表示路徑p的權(quán)值矩陣，其中每條路徑p的權(quán)值wj(p)可以通過簡單累加路徑中的每一條邊的權(quán)值來獲得，即

定義1:假設(shè)圖G(V，E)有k個不同的權(quán)值，其中k≥2，src表示源節(jié)點，dest表示目的節(jié)點，多約束條件限制問題(Multi-Constrained Problem，MCP)就是找出一條從src到dest的路徑p，其中w1(p)≤c1，w2(p)≤c2，…，wk(p)≤ck，c1，c2，…，ck表示k個約束條件。當(dāng)k=2時，轉(zhuǎn)換成兩個約束條件問題。

定義2:假設(shè)圖G(V，E)有k個不同的權(quán)值，存在兩條從相同源節(jié)點到相同目的節(jié)點的路徑p和q，如果W(p)＜W(q)，那么有路徑p主導(dǎo)路徑q，也可以說q被p主導(dǎo)。如果路徑p在從相同的源節(jié)點到相同的目的節(jié)點的路徑上不被任何路徑主導(dǎo)，那么就有路徑p為非主導(dǎo)路徑。由此可知，當(dāng)k≥2時，圖中存在不止一條非主導(dǎo)路徑。當(dāng)k=1時，該非主導(dǎo)路徑也就是最優(yōu)路徑。

性質(zhì)1:如果從源節(jié)點到目的節(jié)點存在一條滿足所有QoS約束的路徑，那么必然至少存在一條從源節(jié)點到目的節(jié)點并且滿足這些約束的非主導(dǎo)路徑。一個性能較佳的QoS路由算法僅僅只需要考慮從源節(jié)點到目的節(jié)點的非主導(dǎo)路徑。

2 基于QoS約束的路由算法描述

2.1 路徑長度限制的路徑穩(wěn)定的路由算法

通常來講，路徑的穩(wěn)定度直接影響網(wǎng)絡(luò)性能，尤其在無線網(wǎng)絡(luò)環(huán)境下，對路徑的穩(wěn)定度要求更高。但是路徑的穩(wěn)定度和對應(yīng)節(jié)點跳數(shù)要有一個權(quán)衡，往往由大量節(jié)點跳數(shù)組成的穩(wěn)定路徑的網(wǎng)絡(luò)性能都不盡如人意。本算法意在對路徑長度和路徑穩(wěn)定度進行權(quán)衡，從而尋找出一條滿足兩個限制條件的最佳路徑。下面定義兩個權(quán)值:

假設(shè)權(quán)值w1∈N*表示路徑中的節(jié)點跳數(shù)，對于任意e∈E，存在w1(e)=1;對于任意路徑p=(scr=u0)→u1→…→(un=dest)，存在權(quán)值ui+1)=n。

假設(shè)權(quán)值w2∈R+表示路徑穩(wěn)定度。為了定量分析路徑穩(wěn)定度，設(shè)定一個范圍值，1表示穩(wěn)定度最高，0表示穩(wěn)定度最低，同時規(guī)定路徑中一條邊的存在僅在兩個端節(jié)點的通信范圍R之內(nèi)，這樣路徑中邊的穩(wěn)定度判定條件為

式中:dx，y表示端節(jié)點x，y之間的距離值。通過數(shù)學(xué)變換，式(1)可以轉(zhuǎn)化成

一條路徑由多條邊構(gòu)成，因而路徑穩(wěn)定度可表示成

式中:路徑P=(s，d)，而s，d分別表示源節(jié)點和目的節(jié)點;集合Ss，d表示構(gòu)成路徑的邊的集合。

假設(shè)集合Πs，d表示從源節(jié)點s到目的節(jié)點d的所有路徑，那么穩(wěn)定度最高的路徑Popt可以表示為

由于自然對數(shù)(ln)嚴(yán)格遵循單調(diào)遞增，可得

由式(3)和(5)進一步轉(zhuǎn)化可得

將式(6)化簡，每條邊穩(wěn)定度的權(quán)值可以表示為

根據(jù)以上的數(shù)學(xué)推導(dǎo)過程可以得出路徑長度和路徑穩(wěn)定度的關(guān)系，即路徑長度越短，其穩(wěn)定度越高。

2.2 確定性的最優(yōu)權(quán)值約束算法描述

通過上述算法，可以獲取路徑長度因子和路徑穩(wěn)定因子兩個限制權(quán)值w1，w2。下面將通過本算法解決在兩個權(quán)值限定的基礎(chǔ)上獲取最佳路徑的問題，即為具有相同源節(jié)點和目的節(jié)點的路徑尋找一條最優(yōu)權(quán)值約束的路徑。集合PATH(u)用來存儲任意節(jié)點與節(jié)點u相關(guān)聯(lián)并且滿足權(quán)值w1的限制條件的非主導(dǎo)路徑，而尋找一條最優(yōu)權(quán)值約束的路徑就是在集合PATH(dest)中挑選滿足另一權(quán)值w2限制條件的非主導(dǎo)路徑。

算法具體實現(xiàn)的偽代碼如下所示:

1:for i=1 to|V(G)|do

2:PATH(i)←Φ

3:end for

4:PATH(src)←{src}

5:for i=1 to|V(G)|do//Note:W=(w1，w2)

6:for all(u，v)∈E(G)do//u and v are neighbors

7: for all p∈PATH(u)do

8: if(w1((u，v))+w1(p))≤C then

9: for all q∈PATH(v)do

10: if(W((u，v))+W(p)≤W(q))then

11: delete q from path(v)

12: end if

13: r←p+(u，v)

14: if w1(r)≥w1(q)and w2(r)＞w2(q)then

15: delete r

16: Ignore p

17: break

18: else

19: add r to PATH(V)

20: end if

21: end for

22: end if

23:end for

24:end for

25:end for

26:

27:if PATH(dest)is empty then

28:return NUL

29:end if

30:

31:Shortest_Path←First element of PATH(dest)

32:for all p∈PATH(dest)do

33:if W(p)≤W(Shortest_Path)then

34:Shortest_Path←p

35:end if

36:end for

37:return Shortest_Path

上述代碼中:第1～4行是路徑的初始化過程，該過程除了源節(jié)點src以外，其他任何節(jié)點的PATH集合都設(shè)置為空。第5～25行是構(gòu)建滿足約束條件的路徑集合PATH，該集合中不僅包括從源節(jié)點src到目標(biāo)節(jié)點的所有非主導(dǎo)路徑，而且還包括用于計算非主導(dǎo)路徑的其他路徑。由此可知，從源節(jié)點src到任意節(jié)點n的多數(shù)非主導(dǎo)路徑存儲在集合PATH(n)中，而算法的第2個權(quán)值限制條件w2，主要為了在集合PATH(n)中尋找最佳路徑(w2權(quán)值最小的路徑也就是最短路徑)。當(dāng)節(jié)點n為dest節(jié)點時，尋找出來的最佳路徑就是從源節(jié)點到目的節(jié)點的最佳路徑，第27～37行為在集合PATH(n)中取最佳路徑的過程。

3 基于QoS的多路徑路由協(xié)議描述

前面提出了一種路徑長度和路徑穩(wěn)定度限制的路由算法，通過數(shù)學(xué)推導(dǎo)得出路徑長度和路徑穩(wěn)定度的關(guān)系，并將QoS判定因子實例化到算法中。將算法應(yīng)用于AODV［6］協(xié)議后，僅加入一個路徑長度衡量標(biāo)志就可確保從源節(jié)點到目的節(jié)點滿足QoS要求的路徑。但是單路徑的路由協(xié)議在網(wǎng)絡(luò)利用率和容錯性上仍不能滿足現(xiàn)有大流量數(shù)據(jù)傳輸業(yè)務(wù)的QoS需求，因此采用多路徑的方式來克服單路徑路由存在的缺陷。本節(jié)將對現(xiàn)有的AODV協(xié)議進行修改，從而提出一種基于QoS的節(jié)點不相交備份多路徑路由協(xié)議MP-QAODV。

3.1 路徑長度限制的路徑穩(wěn)定的路由算法

MP-QAODV協(xié)議對路由請求包RREQ和路由應(yīng)答包都作了修改。RREQ包中添加了Distance Sign字段，該字段存儲了節(jié)點通過配備GPS設(shè)備獲取所處位置的坐標(biāo)信息。源節(jié)點s到目的節(jié)點d的距離可以根據(jù)公式dis=得到，根據(jù)前面算法中路徑長度和路徑穩(wěn)定度的關(guān)系，直接通過路徑長度判斷路徑穩(wěn)定度。

同時，RREQ又添加了1 bit的標(biāo)志位“F”，該標(biāo)志位主要用來區(qū)分路由發(fā)現(xiàn)階段主路徑的數(shù)據(jù)包(RREQ，RREP)和備選路徑的數(shù)據(jù)包(RREQ_2，RREP_2)，如圖1所示。

3.2 MP-QAODV路由協(xié)議描述

3.2.1 路由發(fā)現(xiàn)過程

MP-QAODV源節(jié)點開始廣播ID值為1的路由請求包RREQ到目的節(jié)點。當(dāng)中間節(jié)點接收到RREQ包后，將把ID值以及有關(guān)源節(jié)點的路由信息保存在本地路由表中。目的節(jié)點將沿著反向路由將RREP包發(fā)送給源節(jié)點。

圖1 MP-QAODV RREQ包格式和RREP包格式

中間節(jié)點收到RREP包后將對保存在路由表中的RREQ ID進行遞增。協(xié)議通過遞增RREQ ID值的過程確保備份路徑不占用主路徑中的任意一個節(jié)點。

當(dāng)源節(jié)點接收到RREP包后，就完成了主路徑建立的過程，這時源節(jié)點開始一邊發(fā)送數(shù)據(jù)包一邊廣播RREQ_2包(RREQ ID值遞增后為2)來尋找備用路徑。其中RREQ_2是備份路徑的路由請求包，它的標(biāo)志位F設(shè)置為1。

當(dāng)RREQ_2包傳遞到中間節(jié)點時，中間節(jié)點就在本地路由表中查詢RREQ包的ID值與RREQ_2包進行比較。若相同，則丟棄該數(shù)據(jù)包;否則將轉(zhuǎn)發(fā)該數(shù)據(jù)包。由于主路徑在建立過程中都對各個節(jié)點路由表中的RREQ ID值進行了遞增，所以如果RREQ_2 ID值與中間節(jié)點路由表中RREQ ID值相同，說明中間節(jié)點是主路徑中的一個節(jié)點，這樣協(xié)議在選擇備用路徑時將放棄該節(jié)點(MPQAODV屬于節(jié)點不相交的備用多路徑路由協(xié)議)。

當(dāng)RREQ_2包到達目的節(jié)點后，目的節(jié)點將沿著反向路由方向發(fā)送RREP_2(標(biāo)志位F設(shè)置為1)包到源節(jié)點。源節(jié)點收到RREP_2包后，備份路徑的建立過程完成。在整個備份路由發(fā)現(xiàn)過程中，路徑中的節(jié)點將不會遞增路由表中的RREQ ID值，但主路徑節(jié)點路由表中的RREQ ID值必須遞增。即在協(xié)議完成路由發(fā)現(xiàn)過程之后，主路徑節(jié)點路由表中的RREQ ID值為3，而備份路徑中的為2，總是要比備份路徑的值大1。圖2所示為MPQAODV協(xié)議的流程圖。

3.2.2 路由維護過程

MP-QAODV協(xié)議的路由維護過程存在兩種情況:

1)當(dāng)主路徑發(fā)生斷裂［7］時，源節(jié)點會收到返回錯誤信息包RERR。同時備份路徑將取代主路徑來進行數(shù)據(jù)包的傳輸，而主路徑將初始化并重新建立路由。主路徑重新發(fā)起路由發(fā)現(xiàn)之前，需要將RREQ ID值在備份路徑的基礎(chǔ)上遞增1個單位，由此來區(qū)分重新建立主路徑和備份路徑。

圖2 MP-QAODV路由發(fā)現(xiàn)流程圖

2)當(dāng)備份路徑發(fā)生斷裂時，源節(jié)點仍然需要接收返回錯誤信息包RERR，為了判斷該錯誤信息包是來自主路徑還是備份路徑問題，協(xié)議在源節(jié)點的本地路由表中增添了一個表項Route_flag。如圖3所示，Route_flag值為0和1，分別代表主路徑和備份路徑。所以源節(jié)點收到RERR包后，通過核對路由表中的“Route_flag”表項來判斷是主路徑還是備份路徑。

圖3 源節(jié)點的本地路由表

備份路徑重新建立過程只需要初始化源節(jié)點，同開始建立備份路由過程一樣重新進行路由發(fā)現(xiàn)，這樣備份路由中的RREQ ID值相比主路徑的值仍然小于1，從而與主路徑相區(qū)別。如圖4所示，MP-QAODV協(xié)議路由維護過程流程圖。

圖4 MP-QAODV路由維護流程圖

4 仿真評估

本文采用NS2仿真場景來衡量MP-QAODV，AOMDV和AODV協(xié)議的性能［8］。同時本文采用IEEE802.11 DCF(Distrbuted Coordination Function)MAC協(xié)議的CSMA/CA技術(shù)來傳輸分組數(shù)據(jù);傳輸信道帶寬設(shè)置為2 Mbit/s;無線信道范圍為R=250 m。節(jié)點的移動模型采用雙徑地面反射模型(Two-ray Ground Reflection，TGR)，在R=250 m的網(wǎng)絡(luò)覆蓋范圍內(nèi)，發(fā)送天線和接收天線的高度為1.5 m，收發(fā)天線的增益為1，最低接收功率3.65×10-10W;節(jié)點的移動速度為［0 m/s，30 m/s］，仿真時間為900 s。具體參數(shù)如表1所示。

表1 仿真環(huán)境參數(shù)設(shè)置

本仿真場景主要對比節(jié)點移動狀態(tài)下3種路由協(xié)議的性能，分別對比端到端時延、分組投遞率、歸一化路由開銷和路由發(fā)現(xiàn)頻率4個參數(shù)，測試場景具體參數(shù)如表2所示。

表2 仿真參數(shù)

如圖5所示，隨著節(jié)點移動速度的增加，AODV，AOMDV和MP-QAODV三種路由協(xié)議的端到端平均時延也相應(yīng)增加，這是由于節(jié)點的移動增大了路徑失效的概率，從而數(shù)據(jù)分組不能有效傳輸?shù)侥康亩?，?dǎo)致端到端的時延增加。對于多路徑路由協(xié)議AOMDV和MP-QAODV來說，由于采用了備份路由機制，比單路徑路由協(xié)議的路由發(fā)現(xiàn)次數(shù)要少，進而端到端的平均時延也要小于AODV。同時MP-QAODV引入了路徑穩(wěn)定性的路由算法，增強了網(wǎng)絡(luò)路徑的穩(wěn)定性，路徑的失效概率要小于AOMDV協(xié)議，因而其端到端的平均時延最小。

圖5 節(jié)點移動速度變化時端到端平均時延比較圖

由圖6可知，當(dāng)節(jié)點接近靜止時，3種協(xié)議的分組投遞率非常相近，但隨著移動速度的增加，它們的分組投遞率都有所下降，其中AOMDV下降程度明顯高于其他兩種協(xié)議。這是因為AOMDV協(xié)議采用備份路由方式，即在所有路徑都失效后才發(fā)起新的路由請求，并且分組數(shù)據(jù)在主路徑傳輸時沒有對備份路徑進行有效的維護，從而很容易造成備份路徑在啟動前失效后主路徑在路徑間來回切換，最后導(dǎo)致丟失更多的數(shù)據(jù)分組。對于同樣是多路徑的MPQAODV協(xié)議來說，因為它是基于AODV協(xié)議改進的，其備份路徑的建立與主路徑發(fā)送數(shù)據(jù)分組在同一過程并且該協(xié)議僅維護一條備份路徑，不存在主路徑和失效路徑的頻繁切換，因而分組投遞率要高于AOMDV和AODV協(xié)議。

圖6 節(jié)點移動速度變化時分組投遞率比較圖

如圖7所示，隨著節(jié)點移動速度的增加，AODV，AOMDV和MP-QAODV三種路由協(xié)議的歸一化路由開銷也相應(yīng)增加。AOMDV協(xié)議相對于其他兩種協(xié)議的路由開銷要大些，這是因為AOMDV在路由發(fā)現(xiàn)過程中建立了多條備份路徑，在節(jié)點移動速度增加的時候，其備份路徑失效的可能性增加，從而維護路由分組消息將大大增加，同時根據(jù)圖6可知，AOMDV在較快的節(jié)點移動速度時分組投遞率相對較低，從而導(dǎo)致AOMDV的歸一化路由開銷明顯高于其他兩種協(xié)議。對于多路徑路由協(xié)議MPQAODV，它僅僅維護一條備份路由協(xié)議，并且在AODV的基礎(chǔ)上加入了路徑穩(wěn)定性算法，在移動速度增加情況下路徑失效的可能性大大減少，同時相對于AODV協(xié)議，它的控制分組數(shù)明顯要小一些，再加上相對較高的分組投遞率，因而MP-QAODV的歸一化路由開銷要小一些。

圖7 節(jié)點移動速度變化時歸一化路由開銷比較圖

由圖8可知，AODV，AOMDV和MP-QAODV三種協(xié)議的路由發(fā)現(xiàn)頻率隨著節(jié)點移動速度的增加而增加。對于多路徑路由協(xié)議AOMDV和MP-QAODV，一次路由發(fā)現(xiàn)會找到多條路徑，所以路由發(fā)現(xiàn)頻率相對于單路徑路由協(xié)議AODV要明顯低很多。同時，與AOMDV在路由發(fā)現(xiàn)階段選擇多條備份路徑相比，MP-QAODV僅選擇一條備份路徑，因而MP-QAODV的路由發(fā)現(xiàn)頻率略高于AOMDV。

圖8 節(jié)點移動速度變化時路由發(fā)現(xiàn)頻率比較圖

仿真結(jié)果表明，隨著節(jié)點移動速度的變化，AODV，AOMDV和MP-QAODV三種路由協(xié)議端到端的平均時延、分組投遞率、歸一化路由開銷以及路由發(fā)現(xiàn)頻率都有相應(yīng)的變化。同時由以上分析可知，MP-QAODV協(xié)議在端到端的平均時延、分組投遞率以及歸一化路由開銷所表現(xiàn)出來的網(wǎng)絡(luò)性能要優(yōu)于其他兩種協(xié)議。盡管在路由發(fā)現(xiàn)頻率上略高于AOMDV協(xié)議，但是并不影響其整體的網(wǎng)絡(luò)性能。

5 結(jié)束語

本文針對當(dāng)前移動Ad Hoc網(wǎng)絡(luò)不能有效滿足大流量業(yè)務(wù)情況，提出了一種基于QoS保障的多路徑路由協(xié)議(MP-QAODV)，該協(xié)議采用路徑長度限制的路徑穩(wěn)定的路由算法，其平均端到端時延、分組投遞率以及歸一化路由開銷3項性能指標(biāo)都優(yōu)于AODV和AOMDV協(xié)議，僅在路由發(fā)現(xiàn)頻率上略高于AOMDV協(xié)議。因此，下一步的主要工作是研究如何降低該協(xié)議的路由發(fā)現(xiàn)頻率，從而達到更好的網(wǎng)絡(luò)性能。

［1］JOHNSON D B，MALTZ D A.Dynamic source routing in Ad Hoc wireless networks［M］//IMIELINSKI T，KORTH H F.Mobile Computing:The Kluwer International Series in Engineering and Computer Science.［S.l.］:Springer US，1996:153-181.

［2］MUELLER S，TSANG R P，OHOSAL D.Multipath muting in mobile Ad Hoc networks:issues and challenges［EB/OL］.［2012-05-05］.http://alumni.cs.ucr.edu/～ibasaran/research/Multipath% 20Routing%20in% 20Mobile% 20Ad% 20Hoc% 20Networks% 20Issues% 20and%20Challenges.pdf.

［3］SHENG M，LI J D，SHI Y.Routing protocol with QoS guarantees for adhoc network［J］.Electronics Letters，2003，9(1):143-145.

［4］JULIAN D，CHIANG M.QoS and fairness constrained convex optimization of resource allocation for wireless cellular and Ad Hoc networks［C］//Proc.21st Almual Joint Conf.IEEE Computer and Communications Societies.［S.l.］:IEEE Press，2002:477-486.

［5］WU K，HARMS J.Multipath routing for mobile ad hoc networks［J］.Journal Of Communications And Networks，2002，4(1):48-58.

［6］RFC3561，Ad Hoc on-demand distance vector(AODV)routing［S］.2003.

［7］魏明磊，王浩，李云，等.基于DSR路由協(xié)議的無線Ad hoc網(wǎng)絡(luò)實驗［J］.重慶郵電大學(xué)學(xué)報:自然科學(xué)版，2005，17(6):714-717.

［8］MARINA M K，DAS S R.Ad Hoc on-demand multipath distance vector routing［J］.ACM SIGMOBILE Mobile Computing and Communications Review，2002，6(3):92-93.