移動Ad Hoc網絡中基于QoS的多路徑路由協議研究

李 健，董亞雷，王 剛

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

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

1 網絡模型及數學描述

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

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

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

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

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

2.1 路徑長度限制的路徑穩定的路由算法

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

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

假設權值w2∈R+表示路徑穩定度。為了定量分析路徑穩定度，設定一個范圍值，1表示穩定度最高，0表示穩定度最低，同時規定路徑中一條邊的存在僅在兩個端節點的通信范圍R之內，這樣路徑中邊的穩定度判定條件為

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

一條路徑由多條邊構成，因而路徑穩定度可表示成

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

假設集合Πs，d表示從源節點s到目的節點d的所有路徑，那么穩定度最高的路徑Popt可以表示為

由于自然對數(ln)嚴格遵循單調遞增，可得

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

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

根據以上的數學推導過程可以得出路徑長度和路徑穩定度的關系，即路徑長度越短，其穩定度越高。

2.2 確定性的最優權值約束算法描述

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

算法具體實現的偽代碼如下所示:

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行是路徑的初始化過程，該過程除了源節點src以外，其他任何節點的PATH集合都設置為空。第5～25行是構建滿足約束條件的路徑集合PATH，該集合中不僅包括從源節點src到目標節點的所有非主導路徑，而且還包括用于計算非主導路徑的其他路徑。由此可知，從源節點src到任意節點n的多數非主導路徑存儲在集合PATH(n)中，而算法的第2個權值限制條件w2，主要為了在集合PATH(n)中尋找最佳路徑(w2權值最小的路徑也就是最短路徑)。當節點n為dest節點時，尋找出來的最佳路徑就是從源節點到目的節點的最佳路徑，第27～37行為在集合PATH(n)中取最佳路徑的過程。

3 基于QoS的多路徑路由協議描述

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

3.1 路徑長度限制的路徑穩定的路由算法

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

同時，RREQ又添加了1 bit的標志位“F”，該標志位主要用來區分路由發現階段主路徑的數據包(RREQ，RREP)和備選路徑的數據包(RREQ_2，RREP_2)，如圖1所示。

3.2 MP-QAODV路由協議描述

3.2.1 路由發現過程

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

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

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

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

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

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

3.2.2 路由維護過程

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

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

圖2 MP-QAODV路由發現流程圖

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

圖3 源節點的本地路由表

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

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

4 仿真評估

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

表1 仿真環境參數設置

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

表2 仿真參數

如圖5所示，隨著節點移動速度的增加，AODV，AOMDV和MP-QAODV三種路由協議的端到端平均時延也相應增加，這是由于節點的移動增大了路徑失效的概率，從而數據分組不能有效傳輸到目的端，導致端到端的時延增加。對于多路徑路由協議AOMDV和MP-QAODV來說，由于采用了備份路由機制，比單路徑路由協議的路由發現次數要少，進而端到端的平均時延也要小于AODV。同時MP-QAODV引入了路徑穩定性的路由算法，增強了網絡路徑的穩定性，路徑的失效概率要小于AOMDV協議，因而其端到端的平均時延最小。

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

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

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

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

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

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

圖8 節點移動速度變化時路由發現頻率比較圖

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

5 結束語

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

［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路由協議的無線Ad hoc網絡實驗［J］.重慶郵電大學學報:自然科學版，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.