多媒体通信中带度约束的多播路由算法

随着多媒体业务的发展 ,多播技术应用日益广泛 .多播路由是要寻找连接源节点和一组目的节点的一棵多播树 ,这个问题在数学上归结为 Steiner树问题 ,它是一个 NPC问题 .在实际网络中 ,网络节点具备不同的多播能力 ,有些节点不支持多播 ,有些节点支持多播 ,但为了保证网络速度和节点负载平衡 ,支持多播的节点要限制其复制信息的数量 ,即节点的多播能力受限 .在这种情况下 ,寻找多播树变得更加困难 .该文用节点的度约束来表示每个节点具备的多播能力 ,节点多播能力受限情况下的多播路由问题被称为带度约束的多播路由问题 ,其仍是一个 NPC问题 .该文提出了一种求解带度约束多播路由问题的双层遗传算法 .算法的基本思想是最优多播树应是一棵满足度约束的最小生成树 ,因此问题的关键在于如何找到包括在最优生成树中的 Steiner节点 .遗传算法采用二进制编码方式 ,内层算法用于求解满足度约束的最小生成树 ;外层算法进行全局搜索 .该文将算法在稀疏图上进行实验 ,为了更好地模拟真实网络 ,稀疏图中每个节点具有不同的多播能力 ,并且多播目的节点数目相比于网络节点数要小 .实验对算法进行了三方面的比较 :(1)解的质量 ;(2 )计算时间 ;(3)算法的收敛性 .实验结果表明 ,文中提出的遗传算法能够找到费用较小的多播?

基于链路共享度的网络编码多播路由算法

针对网络编码中最小编码子图的构造问题,提出了一种基于链路共享度的网络编码多播路由算法。该算法利用各条链路的共享度不同,依次选择共享度最大的链路加入到多播传输路径中。实验仿真结果表明,该算法与传统的最短路径多播树算法相比,可节省网络资源约6%～15%,能更好地均衡网络负载,结合随机网络编码算法,能够有效提升多播传输的性能。

一个快速的时延有界低代价多播路由算法

基于QoS的多播路由算法需要在满足每个个体QoS需求的同时，又能高效管理网络资源．提出了一种满足端到端时延限制的低代价多播路由算法．算法使用一个修改的Steiner构近似算法先构建时延有界的低代价多播树，再通过最小时延路径与其它尚不在多播树的组结点相连．计算机仿真结果表明，新算法与其它一些时延有界多播路由算法相比有很好的性能，并且避免了许多同类算法常见的高复杂性．

一种时延和时延抖动受约束的启发式多播路由算法

多播路由算法在组播应用中是至关重要的,对视频会议等交互式实时组播业务来说,不仅要考虑时延约束,而且要考虑时延抖动约束。本文提出了一种基于最短时延路径的时延和时延抖动约束的启发式算法,仿真结果表明该算法复杂度较低,而且性能也较好,在算法复杂度和性能之间达到了很好的折中。

多媒体通信的多播路由算法

在多媒体通信网的实际应用中,多播(multicasting)技术日显重要,在实际网络中,网络节点具备不同的多播能力,有些节点不具备多播能力,而具备多播能力的节点要限制其复制信息的数量,即节点多播能力受限,该文用节点的度约束来表示每个节点的多播能力;此外网络中的很多业务要求信息从源节点传送到目的节点的时延受限;因此该文研究带度约束和时延约束的多播路由问题,给出了一种Lagrange松弛法,能够较好地解决这类问题。

一种基于蚁群算法的多媒体网络多播路由算法

为了克服蚁群算法 (Ant Colony Optimization,ACO)收敛速度慢 ,易限于局部最小点等缺陷 ,对 ACO进行了改进 ,在每次循环结束时 ,保留最优解 ,自适应地改变挥发度系数 ,引入遗传算法的交叉算子 ,提出了一种基于 ACO的有时延约束的多播路由算法模型 .仿真结果表明 ,基于改进 ACO的多播路由算法模型可以稳定地获得优于现有启发式算法的解 ,是一种有效的多播路由算法 。

基于混合蚂蚁算法的QoS多播路由算法研究

在研究了QoS多播路由算法的基础上,提出了一种基于混合蚂蚁算法的QoS多播路由算法——QMRA-GAA算法。QMRA-GAA算法利用混合蚂蚁算法构造多播树,真正做到了协议无关,同时QMRA-GAA算法还具有额外负载低、自适应性强、不产生回路等优点。仿真结果表明,和传统的QoS多播路由算法相比,QMRA-GAA算法在加入成功率、自适应性方面都有了很大的提高,建树代价也控制在很好的范围内。

动态启发式最小生成树多播路由算法

会议电视是一种非常受欢迎的多媒体业务，如何选择合适的会议路由、优化会议的配置，以减少开支，成为会议电视业务推广使用的关键．针对会议电视的特点，介绍了基于Ｓｔｅｉｎｅｒ树的动态多播算法以及动态贪婪算法，指出了两种算法的不足，提出了一种动态启发式最小生成树多播路由算法，给出了算法的实现步骤，对该算法的性能、可行性进行了分析，并论证了该算法是合适可行的．实验数据表明，该算法生成的最小生成树的线路开销接近最优．

多播路由算法MPH的时间复杂度研究

多播通信是从一个源点同时向网络中的多个成员发送分组的通信服务 ,一个最小代价的多播路由算法是NP完全的 ,在时间敏感的应用中其运行时间是一个关键问题 .MPH(MinimumPathCostHeuristic)算法是一个著名的启发式最小代价多播路由算法 ,本文对该算法进行了理论分析和证明 ,并做了广泛的仿真实验 ,结果表明其时间复杂度是O(m2 n)而不是过去文献中所给出的O(m2 n +e) .

时延和时延抖动约束的低费用多播路由算法

为了有效支持交互式实时组播业务,不仅要考虑时延约束,而且要考虑时延抖动约束,同时还需高效管理网络资源,以降低多播费用。本文提出了一种新的时延和时延抖动约束的低费用多播路由启发式算法,仿真结果表明该算法复杂度较低,时延抖动较小,又降低了网络费用,是一种快速有效的多播路由算法。

在overlay网络上的负载平衡多播路由算法

针对基于代理服务器的overlay网络的负载平衡多播路由算法被提出。它能均衡利用overlay网络的有限资源,并能满足多播应用的延迟限制需求。首先用具有延迟约束的Steiner树问题对路由问题进行建模;然后采用预计算方法将计算复杂度集中在预备的单点路径计算上,使由这些单点路径所构成的网络更易于构建负载平衡路由树;预计算只计算一次,结果使用多次,因此降低了总体的计算复杂度。仿真实验的结果表明,相对于其他的快速启发式算法,该算法能提供更为优越的性能。整体而言,基于预计算的负载平衡多播路由算法在性能和计算复杂度方面取得了很好的平衡。

带约束的多播路由算法

由于网络节点处理信息的能力不同 ,有些节点并不具备多播能力 .为保证网络速度和节点负载平衡 ,应限制有些节点的多播能力 ,为此用节点的度约束来表示节点不同的多播能力 .研究了带度约束且时延受限的多播路由问题 ,提出解决此问题的Lagrange松弛法 .

基于最小生成树的动态多播路由算法

提出了基于最小生成树的动态多播路由算法,称之为DPG(dynamicprim-basedgreedymulticastalgorithm)算法,该算法属于不重组的动态多播路由算法.由于在所有节点都是多播节点时,最小生成树是最佳的,因此期望通过该算法产生的多播树的性能在合理的范围之内.结果表明DPG算法是一种平均无效度和最大无效度都在可接受的范围内的一种动态路由算法,尤其在多播节点密度较高时,它的平均无效度和最大无效度都较低.同时DPG算法的平均无效度对网络大小和网络平均节点度数不敏感.DPG算法的另一优点是时间复杂度低,它比贪婪算法和加权贪婪算法都快速.

基于关键节点和多播节点的多播路由算法

在视频会议等多播应用中,降低多播树网络费用非常重要。本文提出了基于关键节点和目的节点的多播路由KDDMC算法。由于在算法中优先考虑采用关键节点,实现更多链路的共享,从而降低网络费用。在随机网络上的仿真结果表明,KDDMC算法的多播树网络费用优于SPH算法。同时证明了KDDMC算法的复杂度为O(n3),且利用所提出的路由表算法易于分布式实现。

加权的基于多播节点的多播路由算法

在许多多播应用中,降低多播树网络费用非常重要。本文提出了加权的基于多播节点的多播路由算法(WDDMC算法)。由于改变了DDMC(Destination-Drivenrouting for low-cost Multicast)算法中的指示函数,适当降低了多播节点作为中间节点的优先级,提高非多播节点作为中间节点的优先级,从而使得多播树更接近最小Steiner树。在随机网络上的仿真结果表明,WDDMC算法的多播树网络费用优于DDMC算法。该算法的复杂度与DDMC算法完全相同。

基于最小生成树的时延约束多播路由算法

多播路由已有广泛的应用,但满足时延约束而代价最小的多播路由算法复杂性很高.提出一种快速有效的基于最小生成树满足端到端时延限制的多播路由算法STBMR.STBMR试图建立原图的满足时延约束的最小生成树,如果这样的最小生成树不存在,则用已找到的树与时延最小路径一起组成满足时延约束的多播树.此算法简单易实现,时间复杂度为O(n2),与KPP[6]算法的时间复杂度O(Δn3)相比,具有更大的应用价值.当然,这是以多播树的费用增大为代价的.实验模拟表明STBMR算法构造的多播树费用比KPP算法构造的约大4%,但STBMR算法执行所耗CPU时间比KPP算法约少54%.

满足QoS约束可靠的适应性多播路由算法

文章考虑了在通信网络中节点和边都存在生存概率的情况下,权衡可靠性和延迟这两个性能指标而提出的一种接近最小成本的适应性算法。利用该算法,可以避免在有些节点或边失效(或不满足某种可靠性要求)的情况下依旧选择这些节点和边的可能,有效地减少了信息传送和缩短了传输时延。这是以往多播(multicast)算法中很少考虑的情况。数值实验表明,这种算法是快速而有效的。且算法的时间复杂度为O(m｜D｜logn)。

基于遗传操作的带度约束的多播路由算法

利用SPH和GA这两种算法的优点,提出了一种快速的多播路由树的生成算法,算法使用SPH的基本思想,采用遗传操作而不是遗传算法,克服了已有算法的不足。仿真结果显示,算法性能良好。

一种改进的时延受限多播路由算法

针对DCMPH算法不能合理选择连接路径的问题,提出一种改进的满足时延限制的多播路由算法。该算法对不能用最小代价路径连接到多播树上的目的节点,求出其到多播树上所有节点的最小时延路径,再从中选出一条能满足时延限制的费用最小的路径,添加到多播树上。实验结果表明,与DCMPH算法相比,该算法构造多播树的代价更低。

带时延约束的动态多播路由算法

考虑多媒体业务端到端的时延要求 ,需建立有时延约束的 Steiner树 ,提出了一种分布式的带时延约束的动态多播路由算法。通过仿真实验验证了算法具有很好的性能和可扩展性 ,优于已有的几种算法 ,且能适应多播成员的动态变化。