一种MANET网络带宽时延约束的多播路由算法研究

李悦 刘强 刘银辉 赵航

摘要：本文提出一种启发式的按需多播路由算法。在认真研究MANET网络的带宽估计算法基础上，有效限制了洪泛加入请求分组的数量，并基于MANET网络特点提出了新的选择函数，保证了公平地对待时延和带宽性能。算法具有路由开销较少，成功率高的优点。

关键词： MANET；多播；NS2

中图分类号：TN711 文献标识码：A 文章编号：

1引言

MANET网络又称为移动多跳无线网络。因为具有无中心、自组织、多跳路由、动态拓扑等区别于普通网络的特性，所以被重点研究和广泛应用。多播路由协议作为MANET网络的重要组成部分，为支持多媒体应用提供技术保障。文中针对MANET网络经典树型多播路由协议的QoS问题，提出一种优化算法，在动态环境中增加时延和带宽约束，并有效控制了路由开销，经仿真分析，改善了路由性能。

2问题分析

2.1 MANET网络中的带宽估计

对于网络中节点和链路的带宽估计，依网络的MAC协议不同而将有所不同。IEEE 802.11DCF是标准委员会提出的针MANET的一种MAC协议，其采用的是CSMA/CA机制，文献[1]在全面考虑了网络中节点和链路的流内干扰、流间干扰、带宽的不对称性和隐藏节点等因素后提出：

（2-1）

设代表一条路径，为路径上的节点，为第个节点的可用带宽。在充分考虑流内干扰的情况下，路径可用带宽定义为：

（2-2）

2.2减少控制开销的方法

构建QoS多播树的分布式算法，是一个受约束Steiner树的不断生长的过程。发现最优路径最为有效的方法就是洪泛加入请求，但全网广播会引入过多的控制消息，降低网络性能。本文提出一种限制洪泛的算法，即节点在洪泛加入请求时，按式（2-1）计算自己的节点可用带宽并累计跳数，一并加入控制分组中发送出去，转发节点依据式（2-2）对链路带宽值和约束条件做出比较，如果不能满足约束条件就停止转发，否则继续广播，这样，只有满足约束条件的链路可以将加入请求传递到树上，而不满足约束条件的链路在中途即停止了加入请求的转发，从而有效限制了洪泛控制消息的数量。

3BDCMR算法

基于前面的分析，本文提出一种MANET带宽时延约束的多播路由算法BDCMR（MANET Bandwidth and Delay Constrained Multicast Routing）。算法结合链路可用带宽的计算，使用自定义的路径选择函数，有效限制洪泛开销，提升了路由性能。描述如下：

给定移动Ad hoc网络，源节点，多播组集合，求得的多播树为。

对于，则节点a和节点b之间的路径用表示；表示节点a的度；表按式（2-1）计算得到的节点a的可用带宽；，为源节点沿多播树到达目的节点的路径。对于，有三个正实数，，，分别表示的可用带宽、时延和代价。设路径的带宽为，的时延为，的代价为。网络中带宽和时延约束为： ； ；。公式（3-1）为选择函数，其中（3-2）式和（3-3）式为指示函数，其目的在于，当存在多条可行链路时，通过它找出最优路径，从而构建最优多播树。式（3-1）中表示从源节点S到节点的代价，表示任意链路的代价，通过节点连接到多播树上。选择函数以得值小者为佳。

（3-1）

其中：

（3-2）

（3-3）

则带宽时延约束的多播路由问题可以表述为：寻找从源节点S到所有目的节点的多播树，并且满足、和条件。

4BDCMR算法的仿真分析

为验证BDCMR算法的性能，在NS2环境下，对比MAODV-QoS协议做出了仿真分析。以下的仿真数据来自多次试验的平均值。

从图4-1可以看出在BDCMR中由于选路时依据选择函数做出判断，所以树的整体成功率高于MAODV-QoS，尤其在多播节点较多时优势更为明显。在图4-2中，随网络节点数目的增加网络中更多的组播组成员要加入多播树，开销变大，MAODV-QoS的请求分组是洪泛方式广播的，而在BDCMR中节点转发路由请求分组依据对当前链路是否可行（即满足约束条件）做出判断，所以控制开销小于前者。图4-3和图4-4表现的是，带宽约束为1.5Mbps时延约束为100ms时，多播树的平均路径带宽和平均路径时延随网络节点数目的变化情况。可以看出BDCMR的路径平均带宽指标总体上好于MAODV-QoS，同时平均路径时延总体上也要小于后者，而且BDCMR的两项指标更加平滑。

图4-1 成功率随网络节点数的变化 图4-2路由开销随网络节点数的变化

图4-3平均路径带宽随网络节点数的变化图4-4平均路径时延随网络节点数的变化

5 结束语

在MANET网络中，带有QoS约束的多播路由协议是保证多媒体应用的重要基础。本文基于对MANET网络带宽估计的研究，有效控制了洪泛广播开销，使用自定义的路径选择函数，提出了一种带有时延和带宽约束的多播路由算法。在NS2下，对BDCMR算法进行了仿真，结果显示，在成功率、路由开销和时延方面协议性能得到改善。

参考文献

[1] 周贤伟,刘臻臻，林琳.一种具有时延约束的组播路由算法研究[J].计算机应用研究,2009，26（9）：3259-3262.

[2] 孙宝林,李腊元. QoS动态多播路由协议[J].小型微型计算机系统,2005,26(11):1877-1880

[3] 王岩,张连芳,窦志斌.无线Ad hoc多媒体网络中的可用带宽估计[J].计算机工程与应用,2006,42(33):107-110.

[4] 石坚,邹玲.Ad Hoc网络中一种基于QoS的分布式多播路由算法[J].通信学报