Ad Hoc網(wǎng)絡中基于協(xié)商機制的QoS多播路由研究

陶 洋，靳黎明

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

近十多年，Ad Hoc網(wǎng)絡理論獲得長足的進步而愈加完善，Ad Hoc網(wǎng)絡在人們?nèi)粘Ｉ钪械膽靡踩找鎻V泛。為了滿足如電話會議、視頻點播等實時多媒體的通信需求，很多學者致力于研究Ad Hoc網(wǎng)絡中的多徑路由、多播路由以及對應的服務質量保障技術，并且提出了大量有建設性的觀點。本文是在研究移動Ad Hoc網(wǎng)絡中的QoS多播路由技術的基礎之上，從實際應用的角度出發(fā)，提出一種基于協(xié)商機制的QoS多播路由協(xié)議，該協(xié)議能避免多播引起的網(wǎng)絡擁塞，提高數(shù)據(jù)傳輸率，實現(xiàn)網(wǎng)絡資源的有效利用。

1 QoS多播路由協(xié)議

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

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

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

2 MAODV協(xié)議的QoS延伸

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

2.1 消息格式延伸

為了實現(xiàn)MAODV協(xié)議的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消息格式(截圖)

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

2.2 路由發(fā)現(xiàn)

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

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

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

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

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

4)按照MAODV路由協(xié)議中的方法轉發(fā)RREQ數(shù)據(jù)包。

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

2.3 路由選擇

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

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

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

2.4 路由激活

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

3 基于協(xié)商機制的QoS多播路由協(xié)議

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

3.1 協(xié)商控制消息

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

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

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

NRES消息，多播組組長在經(jīng)過資源協(xié)商過程后，用來通知優(yōu)先級低的節(jié)點結束數(shù)據(jù)發(fā)送。主要包含了目的節(jié)點地址、多播組地址、多播組序列號和讓步節(jié)點優(yōu)先等級。

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

3.2 協(xié)商機制

每個多播組成員有數(shù)據(jù)傳輸?shù)男枨髸r，先要向組長發(fā)送NREQ消息來確認當前多播組的使用情況，再決定是否發(fā)送數(shù)據(jù)。組長收到NREQ消息后，首先檢查自身的組內(nèi)可用帶寬，即為該多播組預留的帶寬減去當前多播組占用帶寬后剩余的可用帶寬，然后再進行一系列的資源協(xié)商，具體流程如下:

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

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

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

4)向優(yōu)先級低的節(jié)點發(fā)送NRES消息，并修改多播協(xié)商表，刪除優(yōu)先級低的節(jié)點表項，根據(jù)NREQ數(shù)據(jù)包中的信息增加請求節(jié)點的表項。

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

當多播組組長收到過多的丟包重傳請求時，說明網(wǎng)絡負載過大導致?lián)砣嗖ソM組長負責向多播協(xié)商表中節(jié)點優(yōu)先等級最低的節(jié)點發(fā)送NRES消息，通知其停止數(shù)據(jù)發(fā)送，以減小網(wǎng)絡中的數(shù)據(jù)量來提高分組投遞率，從而提高多播網(wǎng)絡的平均吞吐量。

4 仿真實驗

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

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

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

圖4 網(wǎng)絡規(guī)模變大時控制消息開銷比較圖

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

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

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

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

5 小結

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

:

［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，F(xiàn)AN 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網(wǎng)絡QoS多播路由協(xié)議［J］．計算機學報，2004，27(10):1402－1407．

［8］袁馬軍，陶洋，王堅．Ad Hoc網(wǎng)絡組播路由ODMRP協(xié)議的改進［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．