Ad Hoc網絡中基于協商機制的QoS多播路由研究

陶 洋，靳黎明

(重慶郵電大學通信軟件技術研究所，重慶400065)

近十多年，Ad Hoc網絡理論獲得長足的進步而愈加完善，Ad Hoc網絡在人們日常生活中的應用也日益廣泛。為了滿足如電話會議、視頻點播等實時多媒體的通信需求，很多學者致力于研究Ad Hoc網絡中的多徑路由、多播路由以及對應的服務質量保障技術，并且提出了大量有建設性的觀點。本文是在研究移動Ad Hoc網絡中的QoS多播路由技術的基礎之上，從實際應用的角度出發，提出一種基于協商機制的QoS多播路由協議，該協議能避免多播引起的網絡擁塞，提高數據傳輸率，實現網絡資源的有效利用。

1 QoS多播路由協議

目前，移動Ad Hoc網絡當中的多播路由協議主要可分為兩類:基于網格結構的多播路由協議，如ODMRP［1］，CAMP［2］，NSMP［3］，DCMP［4］和基于樹結構的多播路由協議，如 MZR［5］，MAODV［6］。

QoS多播路由協議是在多播路由協議的基礎上進行延伸，是QoS保障體系當中最為重要的一部分，它要解決的基本問題就是在源節點和目的節點之間找到一條滿足業務傳輸需求的鏈路，與傳統路由不同，QoS路由選擇的度量不僅僅是路由的跳數，還需要考慮鏈路可用帶寬、時延、時延抖動、節點生存時間等方面的限制。

基于多個不相關QoS約束條件的路由問題已經被證明為NP完全問題。近年來，人們在QoS多播路由領域做了大量的探索和研究，提出很多有價值的思想方法，如利用遺傳算法、蟻群算法、粒子群算法和模擬退火算法等來解決多目標優化問題，期望得到多QoS約束下多播路由的優化解［7－11］。

2 MAODV協議的QoS延伸

對MAODV協議進行QoS延伸時，加入過多的約束條件會導致尋路成功率降低，請求加入多播組的節點在尋路失敗時會設置自身為組長，從而導致網絡中存在多個相同地址的多播組。為了避免這種情況，應該合理選擇QoS參數，并且保證在已經存在多播組的情況下，尋路失敗不會再次創建多播組。考慮到影響業務數據流傳輸最關鍵的因素是鏈路可用帶寬，本文改進MAODV的路由請求過程，在路由發現階段加入帶寬約束，在路由選擇階段根據代價計算公式選擇代價最小的鏈路，目的是在源節點和多播組間尋找一條既滿足業務傳輸帶寬需求又對網絡整體性能影響較小的可用鏈路。

2.1 消息格式延伸

為了實現MAODV協議的QoS延伸，需要在原有的控制消息中新增幾個字段，保證在不改變路由過程的前提下，找到滿足QoS約束的可用鏈路。

RREQ消息和RREP消息需要新增鏈路可用標志位A(1 bit)、最小需求帶寬Bn(32 bit)和鏈路最小可用帶寬Bmin(32 bit)3個字段。新的消息格式如圖1和圖2所示。

MACT消息中增加資源預留標志位S(1 bit)和預留帶寬大小Bres(32 bit)。新的消息格式如圖3所示。

圖3 新的MACT消息格式(截圖)

除了修改消息格式，節點的多播路由表項中也要增加預留帶寬大小字段，為對應多播組預留所需要的網絡資源，從而更好地保障多播業務的QoS。

2.2 路由發現

不論節點是要加入多播組還是僅僅向多播組發送數據，它們首先檢測自身的可用帶寬Bavi是否大于最小需求帶寬Bn，如果大于，則生成RREQ數據包，數據包中的鏈路最小可用帶寬Bmin初始化為源節點的可用帶寬Bavi，鏈路可用標志A初始化為1。如果小于，則放棄請求。

中間節點收到RREQ數據包后，如果該節點不是所請求多播組的成員，且沒有到多播組的已知路由，則按照如下流程進行處理:

1)檢查其中的鏈路可用標志A，如果A為1，轉向步驟2);否則，按照MAODV路由協議中的方法處理。

2)比較節點的當前可用帶寬Bavi和RREQ數據包中的最小需求帶寬Bn，如果Bavi＞Bn，轉向步驟3);否則，設置鏈路可用標志位A為0，轉向步驟4)。

3)比較節點的當前可用帶寬Bavi和RREQ數據包中的鏈路最小可用帶寬Bmin，如果Bavi＜Bmin，則更新Bmin為Bavi。

4)按照MAODV路由協議中的方法轉發RREQ數據包。

多播組的成員節點收到請求加入該多播組的RREQ數據包后，只有當RREQ中的J標志和A標志都被置位時，才更新多播路由表，然后從RREQ中的相應字段取出最小需求帶寬、鏈路最小可用帶寬和鏈路可用標志位填充生成RREP數據包，并發送給源節點。

2.3 路由選擇

源節點發出RREQ消息后，在設定的等待時間內，可能會收到多條RREP消息。源節點首先檢查RREP數據包中的鏈路可用標志位，如果A為0，則說明源節點和多播組間存在一條通路但不滿足帶寬需求，同時說明網絡中存在多播組的成員，可以避免因尋路不成功而收不到RREP消息時再創建一顆多播樹。

先從中選出鏈路可用標志A為1，且具有最大多播組序列號的RREP消息，然后根據如下的代價計算公式選擇代價最小的鏈路

式中:H為RREP中的跳數;Bn為最小需求帶寬;Bmin為鏈路最小可用帶寬;M為節點轉發數據的平均代價。ε1和ε2是影響因子，滿足ε1+ε2=1。用于多播數據傳輸所需要的帶寬占用鏈路最小可用帶寬的比例越小，對其他數據傳輸的影響越小，網絡的吞吐量越好。源節點到多播組的跳數越小，數據傳輸需要的轉發次數越少，端到端時延越小，轉發節點的減少還延長了網絡的壽命。

2.4 路由激活

選出代價最小的鏈路后，源節點向收到RREP數據包的下一跳發送MACT消息，完成鏈路上的資源預留和多播路由的激活。MACT消息中包含了最小需求帶寬，當節點收到MACT消息后，設置多播路由表項中下一跳的激活標志，并且把最小需求帶寬存入到多播路由表當中，然后生成新的MACT消息沿著選定鏈路繼續發送。其他沒有收到MACT消息的節點在等待時間結束后把臨時路由信息從路由表中刪除。

3 基于協商機制的QoS多播路由協議

在多播路由協議當中引入QoS保障的最終目的是為了應對人們對多媒體信息日益增長的需求，資源預留能夠更好地保證服務所需的QoS，但網絡中隨時可能有新的服務請求到達，不同的服務請求可能對QoS的要求不同，這使得在服務請求少時網絡資源得不到有效利用，服務請求多時預留的網絡資源被迅速耗盡。針對這種情況，在MAODV協議上進行QoS延伸的基礎上，提出一種基于協商機制的QoS多播路由協議 CBQ_MAODV。CBQ_MAODV中節點在發送數據前首先與多播組組長進行協商，根據一定的規則協商使用多播組的預留資源，達到充分而又不過度地使用網絡資源，提高數據傳輸率。

3.1 協商控制消息

CBQ_MAODV中新增了4種控制消息，來完成協商過程，并且加入了節點優先級策略，在網絡負載達到一定值后，通過釋放低優先級節點所占用的資源來保證高優先級節點業務的QoS需求。控制消息的格式如下:

NREQ消息，多播組成員用來向組長查詢多播組使用情況，主要包含了源節點地址、多播組地址、組長節點地址、多播組序列號、請求帶寬、請求節點優先等級。其中請求帶寬是要發送的業務所需求的帶寬，根據業務的類型來確定。

NREP消息，多播組組長在收到NREQ后進行資源協商，發送NREP消息告知源節點協商結果。主要包含了目的節點地址、多播組地址、多播組序列號、可用標志位A。

NRES消息，多播組組長在經過資源協商過程后，用來通知優先級低的節點結束數據發送。主要包含了目的節點地址、多播組地址、多播組序列號和讓步節點優先等級。

每個多播組的組長節點除了維護必要的多播路由表外，還需要額外維護一張多播協商表，表項包含了節點地址、占用帶寬、節點優先等級和可用狀態。

3.2 協商機制

每個多播組成員有數據傳輸的需求時，先要向組長發送NREQ消息來確認當前多播組的使用情況，再決定是否發送數據。組長收到NREQ消息后，首先檢查自身的組內可用帶寬，即為該多播組預留的帶寬減去當前多播組占用帶寬后剩余的可用帶寬，然后再進行一系列的資源協商，具體流程如下:

1)比較組內可用帶寬Bg和NREQ數據包中的請求帶寬Br，如果Bg＞Br，直接回復源節點NREP消息，其中可用標志位A置為1;否則，轉向步驟2)。

2)檢查多播協商表中是否有節點優先等級低于請求節點優先等級的表項，如果沒有，回復源節點NREP消息，其中可用標志位A置為0;否則，轉向步驟3)。

3)比較低優先級節點占用的帶寬和Bt與(Br－Bg)，如果Bt＜(Br－Bg)，回復源節點NREP消息，其中可用標志位A置為0;否則，回復源節點NREP消息，其中可用標志位A置為1，轉向步驟4)。

4)向優先級低的節點發送NRES消息，并修改多播協商表，刪除優先級低的節點表項，根據NREQ數據包中的信息增加請求節點的表項。

多播組成員收到NREP數據包后，檢查其中的可用標志位A，若A為1，則可以開始發送多播數據;若A為0，則取消發送，在等待一段時間后，再次發送NREQ消息請求多播。

當多播組組長收到過多的丟包重傳請求時，說明網絡負載過大導致擁塞，多播組組長負責向多播協商表中節點優先等級最低的節點發送NRES消息，通知其停止數據發送，以減小網絡中的數據量來提高分組投遞率，從而提高多播網絡的平均吞吐量。

4 仿真實驗

為了有效地評價CBQ_MAODV協議的性能，使用NS2對該QoS多播路由協議進行仿真實驗，并與原始多播路由協議MAODV進行比較，比較協議在控制消息的開銷、端到端時延、吞吐量和分組投遞率方面的性能。在計算機上模擬100個節點，隨機分布在一個1 km×1 km的區域，為每個節點隨機分配一個［0，4］之間的優先等級，每個節點的無線信號傳輸范圍為以250 m為半徑的圓，若兩個節點在彼此的傳輸范圍內就用一條鏈路連接它們，數據傳輸速率最大為2 Mbit/s，設定節點以1 m/s的速度移動或靜止，每次仿真時間是600 s。實驗中，隨機選擇節點加入多播組，并且多播組的成員數不多于節點總數的20%，多播組成員隨機選擇發送盡力而為的數據業務或實時多媒體數據業務，它們所需的帶寬分別為［0．1，0．5］Mbit/s 和［0．5，1．0］Mbit/s之間的隨機數。

圖4為控制消息開銷隨網絡規模變化的比較情況，從圖中可以看出，隨著網絡規模的增大，MAODV和CBQ_MAODV兩種協議的控制開銷都在增大，且后者比前者略大，這是因為在CBQ_MAODV路由協議中引入了QoS約束和協商機制，但控制消息的開銷增長緩慢，顯然不會產生消息風暴。

圖5給出了兩種協議在多播組成員個數增加時平均端到端時延的變化情況。從圖中可以看出，隨著多播組成員個數的增加，CBQ_MAODV協議的平均端到端時延穩定在一條直線附近;MAODV協議的平均端到端時延在多播組成員個數小于6時緩慢增長，但是在多播組成員個數大于6時平均端到端時延快速增長。這是因為CBQ_MAODV協議增加了協商過程，多播組成員協商使用網絡中各節點為多播組預留的網絡資源，所以端到端時延比較穩定。然而，MAODV協議隨著多播組成員個數的增加，網絡中傳輸的數據達到網絡最大流上限時，在網絡中會出現數據包的擁塞，并導致丟包，所以會出現平均端到端時延增大的情況。

圖4 網絡規模變大時控制消息開銷比較圖

圖5 多播節點增加時平均端到端時延比較圖

圖6給出了兩種協議在平均吞吐量方面的比較。開始時隨著多播組成員個數的增加，MAODV和CBQ_MAODV兩種協議的網絡平均吞吐量都呈現上升趨勢，這是因為更多節點發送數據，增加了網絡中實際傳輸的數據量，從而提高多播網絡的平均吞吐量。但在多播組成員個數大于6時，MAODV協議的平均吞吐量呈下降趨勢，這是因為發送的數據量超過了網絡負載，會造成數據包丟失，導致平均吞吐量下降，然而由于CBQ_MAODV中加入了協商機制，在網絡負載達到一定值后，停止低優先等級節點的數據傳輸，從而保證多播網絡的平均吞吐量，因此CBQ_MAODV協議的平均吞吐量在一條直線附近波動。

圖7給出了兩種協議在分組投遞率方面的比較，隨著多播組成員個數的增加，MAODV和CBQ_MAODV兩種協議的分組投遞率都逐漸下降，但后者下降緩慢且一直高于前者。這是因為CBQ_MAODV協議在選擇路由時加入了帶寬約束，并且使用協商機制避免擁塞，使得丟包概率更小，分組投遞率能夠保持較高的水平。

圖6 多播節點增加時平均吞吐量比較圖

5 小結

本文研究了Ad Hoc網絡中幾種經典的多播路由協議，分析了多位學者關于多播路由中保證業務服務質量的解決思路，從實際應用的角度出發，對MAODV協議進行了QoS延伸，并提出一種基于協商機制的QoS多播路由協議CBQ_MAODV。該協議考慮了對多媒體業務傳輸最為重要的帶寬約束，建立起滿足QoS需求的多播鏈路并為之預留網絡資源，節點協商使用預留的多播資源，避免了多個節點同時發送多播數據引起的網絡擁塞。仿真證明，該協議改善了平均端到端時延，增加了網絡平均吞吐量，提高了分組投遞率，能夠有效地保障Ad Hoc網絡中多媒體業務的服務質量。

:

［1］ LEE S，SU W，GERLA M．On－demand multicast routing protocol in multihop wireless mobile networks［J］．Mobile Networks and Applications，2002，7(6):441－453．

［2］ MADRUGA E L，ACEVES G L．Scalable multicasting:the core－assisted mesh protocol［J］．Mobile Networks and Applications，2001，6(2):151－165．

［3］ LEE S，KIM C．Neighbor supporting ad hoc multicast routing protocol［C］//Proc．ACM/IEEE Workshop on Mobile Ad Hoc Networking and Computing(MOBIHOC)．Boston:IEEE Press，2000:37－44．

［4］ DAS S K，MANOJ B S，MURTHY C S R．A dynamic core based multicast routing protocol for ad hoc wireless networks［C］//Proc．3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing(MOBIHOC)．Switzerland:IEEE Press，2002:24－35．

［5］ CHENG H，CAO J，FAN X．GMZRP:geography－aided multicast zone routing protocol in mobile Ad Hoc networks［J］．Mobile Networks and Applications，2009，14(2):165－177．

［6］ ROYER E M，PERKINS C E．Multicast Ad hoc on－demand distance vector(MAODV)routing［EB/OL］．［2013－07－15］．http://tools．ietf．org/id/draft－ietf－manet－maodv－00．txt．

［7］孫寶林，李臘元．Ad Hoc網絡QoS多播路由協議［J］．計算機學報，2004，27(10):1402－1407．

［8］袁馬軍，陶洋，王堅．Ad Hoc網絡組播路由ODMRP協議的改進［J］．通信技術，2008，41(1):63－65．

［9］ SABARI A，DURAISWAMY K．Ant based multicast routing algorithm with multiple constraints for mobile Adhoc networks［C］//Proc．2008 International Conference on Security Technology．Hainan:IEEE Press，2008:35－40．

［10］ DEEPALAKSHMI P，RADHAKRISHNAN S．Source－initiated QoS multicasting scheme for MANETs using ACO［C］//Proc．2011 International Conference on Process Automation，Control and Computing．Coimbatore:IEEE Press，2011:1－4．

［11］ LU Jin，ZHAO Dongfeng，AN Zhenzhou，et al．Family particle swarm optimization for QoS multicast routing in Ad hoc［C］//Proc．2011 International Conference on Computer Science and Network Technology．Harbin:IEEE Press，2011:1699－1702．

［12］ BITAM S，MELLOUK A．MQBM:an autonomic QoS multicast routing protocol for mobile ad hoc networks［C］//Proc．2012 IEEE International Conference on Communications．Ottawa:IEEE Press，2012:5488－5492．