1、一种 MANET 网络带宽时延约束的多播路由算法研究摘要：本文提出一种启发式的按需多播路由算法。在认真研究MANET网络的带宽估计算法基础上，有效限制了洪泛加入请求分组的数量，并基于 MANET网络特点提出了新的选择函数，保证了公平地对待时延和带宽性能。算法具有路由开销较少，成功率高的优点。 关键词： MANET；多播；NS2 中图分类号：TN711 文献标识码：A 文章编号： 1 引言 MANET 网络又称为移动多跳无线网络。因为具有无中心、自组织、多跳路由、动态拓扑等区别于普通网络的特性，所以被重点研究和广泛应用。多播路由协议作为 MANET网络的重要组成部分，为支持多媒体应用提供技术保障
2、。文中针对 MANET网络经典树型多播路由协议的 QoS问题，提出一种优化算法，在动态环境中增加时延和带宽约束，并有效控制了路由开销，经仿真分析，改善了路由性能。 2 问题分析 2.1 MANET 网络中的带宽估计 对于网络中节点和链路的带宽估计，依网络的 MAC协议不同而将有所不同。IEEE 802.11DCF 是标准委员会提出的针 MANET的一种 MAC协议，其采用的是 CSMA/CA机制，文献1在全面考虑了网络中节点和链路的流内干扰、流间干扰、带宽的不对称性和隐藏节点等因素后提出： （2-1） 设代表一条路径，为路径上的节点，为第个节点的可用带宽。在充分考虑流内干扰的情况下，路径可用带
3、宽定义为： （2-2） 2.2 减少控制开销的方法 构建 QoS多播树的分布式算法，是一个受约束 Steiner树的不断生长的过程。发现最优路径最为有效的方法就是洪泛加入请求，但全网广播会引入过多的控制消息，降低网络性能。本文提出一种限制洪泛的算法，即节点在洪泛加入请求时，按式（2-1）计算自己的节点可用带宽并累计跳数，一并加入控制分组中发送出去，转发节点依据式（2-2）对链路带宽值和约束条件做出比较，如果不能满足约束条件就停止转发，否则继续广播，这样，只有满足约束条件的链路可以将加入请求传递到树上，而不满足约束条件的链路在中途即停止了加入请求的转发，从而有效限制了洪泛控制消息的数量。 3BD
4、CMR 算法 基于前面的分析，本文提出一种 MANET带宽时延约束的多播路由算法 BDCMR（MANET Bandwidth and Delay Constrained Multicast Routing） 。算法结合链路可用带宽的计算，使用自定义的路径选择函数，有效限制洪泛开销，提升了路由性能。描述如下： 给定移动 Ad hoc网络，源节点，多播组集合，求得的多播树为。 对于，则节点 a和节点 b之间的路径用表示；表示节点 a的度；表按式（2-1）计算得到的节点 a的可用带宽；，为源节点沿多播树到达目的节点的路径。对于，有三个正实数， ， ，分别表示的可用带宽、时延和代价。设路径的带宽为，的
5、时延为，的代价为。网络中带宽和时延约束为： ； ；。公式（3-1）为选择函数，其中（3-2）式和（3-3）式为指示函数，其目的在于，当存在多条可行链路时，通过它找出最优路径，从而构建最优多播树。式（3-1）中表示从源节点 S到节点的代价，表示任意链路的代价，通过节点连接到多播树上。选择函数以得值小者为佳。（3-1） 其中： （3-2） （3-3） 则带宽时延约束的多播路由问题可以表述为：寻找从源节点 S到所有目的节点的多播树，并且满足、和条件。 4BDCMR 算法的仿真分析 为验证 BDCMR算法的性能，在 NS2环境下，对比 MAODV-QoS协议做出了仿真分析。以下的仿真数据来自多次试验的
6、平均值。 从图 4-1可以看出在 BDCMR中由于选路时依据选择函数做出判断，所以树的整体成功率高于 MAODV-QoS，尤其在多播节点较多时优势更为明显。在图 4-2中，随网络节点数目的增加网络中更多的组播组成员要加入多播树，开销变大，MAODV-QoS 的请求分组是洪泛方式广播的，而在BDCMR中节点转发路由请求分组依据对当前链路是否可行（即满足约束条件）做出判断，所以控制开销小于前者。图 4-3和图 4-4表现的是，带宽约束为 1.5Mbps时延约束为 100ms时，多播树的平均路径带宽和平均路径时延随网络节点数目的变化情况。可以看出 BDCMR的路径平均带宽指标总体上好于 MAODV-
7、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.通信学报
