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．