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

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

时延受限组播路由的最短路径加速算法求解

分析了时延受限的Steiner树问题,总结了在构建组播树过程中的代价和计算复杂度变化规律,并根据实际网络环境,从优化最短路径出发,提出了一种基于优化最短路径的时延受限组播路由算法AOSPMPH。该算法以MPH算法为基础,利用Floyd最短路径优化算法求出节点对之间的最短路径,选择满足时延要求的最小代价路径加入组播树,进而产生一棵满足时延约束的最小代价组播树。仿真结果表明,AOSPMPH不但能正确地构造时延约束组播树,而且其代价和计算复杂度与其他同类算法相比得到了优化。     

A distributed multicast routing algorithm for real-time applications in wide area networks

The problem of constructing a minimal cost multicast routing tree (MRT) with delay constraints in wide area networks (WAN) is considered. A new distributed token-passing based algorithm that constructs a sub-optimal MRT satisfying given delay constraints for all members in the multicast group is presented. In contrast with the previous works by Jia [A distributed algorithm of delay-bounded multicast routing for multimedia applications in wide area networks, IEEE/ACM Trans. Network. 6 (1998) 828–837] and several others [Y. Im, Y. Lee, S. Wi, Y. Choi, Delay constrained distributed multicast routing algorithm, Comput. Comm. 20 (1997) 60–66; X. Jia, Y. Zhang, N. Pissinou, K. Makki, A distributed multicast routing protocol for real-time multicast applications, Comput. Networks 31 (1999) 101–110; Q. Sun, H. Langendorfer, A distributed delay-constrained dynamic multicast routing algorithm, Telecommun. Systems 11 (1999) 47–58], in which cycles may occur, we show that the multicast routing network produced by our algorithm is indeed a tree, namely, cycle free. Also the success rate of our algorithm to find a feasible solution, if one exists, is guaranteed to be 100%, while Jia's algorithm is not. Furthermore, our algorithm is fault tolerant and can also adapt to cases where the multicast group members are allowed to join or leave the multicast session dynamically. Simulations have been conducted and the results show that the MRT generated by our algorithm has better performance compared to previous methods.     

基于局部信息的时延和时延差约束的组播路由

组播通信是从一个源节点同时向网络中的多个目的节点发送分组的通信服务,它一般提供一个以上的端到端的服务约束,实际的路由算法在应用时可以受到多重约束,解决这类问题的组播路由算法是NP完全的。在研究了构建组播树的相关算法后,提出了一种新的时延和时延差约束的低代价组播路由算法-DDVMC。该算法采用基于贪婪策略的Dijkstra最小生成树算法,利用局部信息来构建低代价组播树,很好地平衡了树的代价、时延和时延差。仿真表明,该算法能正确地构造出满足约束的组播树,同时还具有较低的代价和计算复杂度。     

无线自组网络基于遗传算法的多播路由算法

随着无线自组网络技术的发展,多播应用日益广泛。文章研究无线自组网络多插路由问题,针对已有算法在时延约束多播路由树费用优化方面的不足,提出基于遗传算法的多播路由算法。该算法首先通过Dijkstra算法得到源节点到每个接收节点间的最多K条路径;其次给这些路径编号,进行编码,设计遗传操作;最后,进行遗传迭代运算找到费用全局优...     

基于投影矢量的双组播树高效路由数据收集

现有的节点数据收集算法复杂度高,与路由结合效果不理想,且不能满足无线传感器网络高效能量的节点数据收集,而压缩感知理论具有容错性好、编码简单的优点。基于压缩感知的特性,提出了一种传感器网络中基于投影矢量的双组播树高效路由数据收集,该算法将贝叶斯压缩感知理论与传感器路由相结合,解决现有算法不能满足传感器对能耗敏感的问题。算法的基本思想首先根据初始观测矢量来寻求能量高效并得到合适路由的最优投影。然后利用节点系数能耗最小与广义矢量的主分量作为目标节点,采用微分嫡改变量最大的原则进行求解节点最佳投影系数,最后在sink与目标节点路由问题上采用正逆向组播树进行路由构造。理论和仿真结果表明在保证能耗的条件下取得了较好的重建仿真效果,对无线传感器通信具有一定的实用价值。     

基于免疫遗传算法的多约束QoS组播路由选择方法

以具有精英保留的免疫遗传算法（IGAE）为基础,提出了一种新的用来求解带宽、时延、时延抖动受限,费用最小的QoS组播路由选择问题的方法。首先采用预处理机制,将网络结构中不满足带宽约束的链路去掉,利用Dijkstra第k最短路径算法建立编码空间的备选路径集;然后采用基于路径的树结构编码来随机产生初始群体,使种群中的每个个体都代表组播路由问题的一个候选解;最后利用IGAE算法对种群进行优化,最终求得满足QoS要求的组播路由。仿真实验结果表明,该算法具有较好的性能,能以较快的速度搜索到满足QoS要求的费用最小的组播树。     

受时延约束的组播路由算法

提出了一种新的受时延约束的组播路由算法。算法借鉴了MPH算法的思想,最初的组播树只包含源结点,然后每次将到达组播树的代价最小且满足时延约束的结点及其相应的路径加入到组播树,直到所有的成员加入为止。谊算法能够快速地得到一棵满足时延约束的组播树,并且组播树的代价也很小。实验表明：该算法简单,复杂度低,性能良好,易于在分布式环境中实现,可应用于实际的应用系统中。     

AODV路由算法的多播通信

ah—hoc网络具有网络拓扑结构易变的特性，苒加上移动网络本身具有的通信带宽有限，电池能源有限等特性。使得设计适合ad-hoc的路由协议具有一定的难度。AODV（Ad Hoc On—demand Distance Vector）是现在被广泛应用于adhoc网络中的一种按需路由算法，并且还设计了多播功能。多播是指一次给一个有明确定义的组发送消息。AODV的多播功能是路由器通过建立多播书树的方法实现的。本文主要介绍AODV路由协议算法的多播通信，其中详细介绍了多播树的建立过程和维护过程。并且选取传输半径和发包率为参     

基于时延约束的快速低代价组播路由算法

低代价最短路径树是一种广泛使用的组播树,通常不能满足实时多媒体应用中信息从源端到目的端传输的时延限制。针对该问题,提出基于时延约束的快速低代价组播路由算法,利用代价构建满足时延约束的初始树,将不满足时延约束的路径用最小时延路径代替。仿真结果表明,相比时延约束最短路径树算法,该算法的计算时间更少,组播树的总代价更低。     

A novel optimization-based bandwidth-aware minimum power multicast routing algorithm in green wireless networks

Multicast routing in wireless networks that possess the wireless multicast advantage could significantly reduce the power and energy consumption. However, this kind of multicast routing that only addresses the transmission radius coverage might not be able to meet the bandwidth requirement of the users. As a result, additional transmissions are required to incur more energy consumption and carbon dioxide emissions that make existing algorithms not applicable to bandwidth constrained applications. In this paper, for the first time, we address the bandwidth aware minimum power multicast routing problem in wireless networks where the objective function is to minimize the total power consumption subject to the users?? bandwidth requirements. This problem is a challenging cross-layer design problem that requires seamless and sophisticated integrated design in the network layer (multicast routing) and physical layer (bandwidth-aware wireless transmission and power control). We first formulate this problem as a mixed integer linear programming problem and then propose a Lagrangian relaxation based algorithm to solve this problem. Numerical results demonstrate that the proposed approach is a sound green networking algorithm that outperforms the existing power efficient multicast routing approaches under all tested cases, especially in large bandwidth request, fine radius granularity, large group size and sparse network.     

Multicast communication in wormhole-routed 2D torus networks with hamiltonian cycle model

In this paper, we propose an efficient multipath multicast routing algorithm in wormhole-routed 2D torus networks. We first introduce a hamiltonian cycle model for exploiting the feature of torus networks. Based on this model, we find a hamiltonian cycle in torus networks. Then, an efficient multipath multicast routing algorithm with hamiltonian cycle model (mulitpath-HCM) is presented. The proposed multipath multicast routing algorithm utilizes communication channels more uniformly in order to reduce the path length of the routing messages, making the multicasting more efficient. Simulation results show that the multicast latency of the proposed multipath-HCM routing algorithm is superior to that of fixed and dual-path routing algorithms.     

基于共享边的时延约束组播路由算法

为了优化在时延约束下的组播树代价,降低算法计算复杂度,研究了时延受限的Steiner树问题.分析了最短路径启发式(MPH)算法的执行过程,以此为基础提出一个基于共享边的时延约束组播路由算法ESAMPH.该算法在构建组播路由树时能够优先采用包含有较多的最短路径经过的节点,这样后面的组播成员节点到树上的最短路径也有可能经过这些节点,由此实现边的共享,降低了组播树的代价.仿真结果表明,ESAMPH算法在代价、延迟和计算时间之间能获得较好的平衡,综合性能较好.     

按需分枝组播

在分析总结目前IP组播路由研究的主要成果基础上,提出了一个新的组播路由方案,按需分枝组播.它采用了一种全新的组播树维护方式,即组播树由树上的部分节点(关键节点)维护,不同于现有的组播树由所有树上节点维护的方式,从而节省了网络资源.     

基于蚁群遗传算法的QoS多播路由研究*

为解决多播路由中的QoS约束问题,不仅研究了QoS多播路由中的带宽、时延﹑时延抖动和包丢失率等约束问题,还重点分析了路径开销问题,从而提出一种基于蚁群遗传算法的多播路由算法。该算法将遗传算法与蚁群算法结合起来,对多播树群体进行编码、选择、杂交和变异等遗传操作,同时利用蚁群算法的信息素正反馈求解,充分发挥两者的优势,从而更快更好地产生出既满足服务质量保障（QoS）又具有最小路径开销的多播树。仿真实验证明了该算法具有更高的运行效率和更好的收敛性。     

A Heuristic Algorithm for Core Selection in Multicast Routing

With the development of network multimedia technology, more and more real-time multimedia applications need to transmit information using multicast. The basis of multicast data transmission is to construct a multicast tree. The main problem concerning the construction of a shared multicast tree is selection of a root of the shared tree or the core point. In this paper, we propose a heuristic algorithm for core selection in multicast routing. The proposed algorithm selects core point by considering both delay and inter-destination delay variation. The simulation results show that the proposed algorithm performs better than the existing algorithms in terms of delay variation subject to the end-to-end delay bound. The mathematical time complexity and the execution time of the proposed algorithm are comparable to those of the existing algorithms.     

基于遗传算法的多约束QoS组播路由优化算法

在计算机网络中,随着大量新兴多媒体实时业务的应用,组播路由问题成为越来越重要的课题。组播路由问题在计算机网络中是著名的Steiner树问题,同时也是NP完全问题。目前许多研究者在单约束(特别是延时约束)组播路由中取得了较好的成果,但对于多约束Qos组播路由方面的研究相对比较少。论文提出了一种基于遗传算法的多约束组播路由优化算法,该算法在满足带宽、延时、延时抖动和包丢失率约束条件下寻找代价最小的组播树,文中描述了一种适应于研究Qos组播路由的网络模型。最后通过仿真实验证明该算法操作简单、搜索速度快、效率高且具有较强的实用性和鲁棒性。     

Bandwidth-delay-constrained least-cost multicast routing based on heuristic genetic algorithm

We present an heuristic genetic algorithm for the quality of service (QoS) multicast routing that depends on: (1) bounded end-to-end delay and link bandwidth along the paths from the source to each destination, and (2) minimum cost of the multicast tree, where the link delay and the link cost are independent metrics. The problem of computing such a constrained multicast tree is NP-complete. We show by experiments that our proposed genetic algorithm is efficient and effective.     

一种基于混合混沌遗传算法的QoS组播路由算法

IP/DWDM光Internet是下一代互联网NGI(NextGenerationInternet)主干网的主要组网技术之一,服务质量QoS(QualityofService)组播路由算法是其一个研究热点,已经证明它是NP难的。为此,文章设计了一种非NP类QoS组播路由算法。在给定用户请求的情况下,基于混合混沌遗传算法来构造带宽、延迟、延迟抖动与出错率受限且费用优化的QoS组播路由树,兼顾网络负载均衡。仿真结果表明,该算法是可行和有效的,明显优于基于传统遗传算法的QoS组播路由算法。     

基于遗传算法的无线网状网QoS多播路由算法

探讨了基于遗传算法的无线网状网QoS多播路由算法,选用边集表示方式对多播树进行编码,其空间复杂度为O(N),给出了该编码方式下的初始种群生成算法RandWalkMT,同时对传统的遗传操作进行改进使子代个体中不会产生非法多播树,从而避免了复杂的惩罚机制或多播树修复算法。实验表明该算法收敛快且性能较好。