新的基于MPH的时延约束Steiner树算法

为了在时延约束条件下进一步优化多播树代价并降低算法的复杂度,研究了时延受限的Steiner树问题。在DCMPH算法的基础上,通过改进节点的搜索路径,提出了一种新的基于MPH的时延约束Steiner树算法。该算法中每个目的节点通过最小代价路径加入当前多播树;若时延不满足要求,则通过合并最小时延树进而产生一个满足时延约束的最小代价多播树。仿真实验表明,新算法在性能、空间复杂度方面均优于DCMPH算法。     

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

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

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

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

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

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

时延约束的链路选择平衡优化组播路由算法

针对时延约束的最小代价组播树生成方法,提出一种快速有效的时延约束组播路由算法。该算法改进了KPP算法,设计了代价和时延动态优化的链路选择函数。在选择路径时,该算法综合考虑了时延和代价两个参数,保证了组播树的性能,降低了时间复杂度低。仿真结果表明,该算法能正确地构造出时延约束组播树,同时还具有较低的代价和计算复杂度。     

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

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

时延约束动态不重组组播路由优化

针对时延约束的组播路由问题,提出了一种动态不重组组播路由算法NDMADC。算法将DGA和Floyd最短路径优化算法相结合,确保节点在满足时延约束的前提下动态选择到组播树有最小代价的路径加入组播会话。由于采用贪心算法思想,NDMADC算法保证了节点加入组播树时不需要组播树重组。仿真表明,该算法能正确地构造出满足时延约束的组播树,具有较低的代价和计算复杂度。     

链路共享的时延约束组播路由局部平衡优化算法*

分析了构建时延约束组播树的代价和计算复杂度,从优化最短路径出发,提出了一种基于局部信息的链路共享平衡优化路由算法。算法设计的链路选择函数不仅考虑了目的节点的优先级,同时还考虑了给予低时延路径一定的优先权,在满足时延约束的情况下使组播树的链路数尽可能少,降低了通过最小时延路径建树的概率,提高了链路的共享性。仿真表明,算法的综合性能比较好,在代价、延迟和计算复杂度之间能获得较好的平衡。     

基于骨干结点集的移动IP组播路由算法研究

为了优化移动IP组播生成树代价,减少移动结点切换加入时延和信息传输时延,引入了移动IP"骨干结点集"思想,设计了移动IP组播路由算法BNSBMR(bone node set-based muhicast routing algorithm),"骨干结点集"是移动IP环境下满足一定条件的IP子网接入路由器AR(access router)的集合.该算法通过"骨干结点集"降低移动IP组播生成树的代价;减少移动结点切换的加入时延;并通过路径优化降低信息传输时延.理论上证明了算法的正确性,并分析了其计算复杂度.仿真实验表明:BNSBMR算法从树代价、加入时延、传输时延3个方面提高了移动IP环境下组播业务满足QoS约束的能力.     

基于遗传模拟退火算法的多约束QOS组播路由优化算法

组播路由问题在计算机网络中是著名的Steiner树问题,是NP完全问题.通过考虑组播通信服务质量需求与网络资源约束,研究了基于服务质量的组播路由选择算法问题,首次提出了一个基于遗传算法和模拟退火算法的多约束组播路由优化算法,该算法在满足带宽、延时、延时抖动及包丢失率约束条件下寻找代价最小的组播树.     

Ad hoc网络时延受限的Steiner树启发式算法

针对Ad hoc网络时延受限的Steiner树问题,设计一个分布式的快速启发式算法DCST,该算法通过对网络中节点进行标号,并根据标号修改节点间的关联关系,建立一棵时延受限的Steiner树。在网络节点保持时间同步的前提下,算法的时间复杂度为O(n)。与现有经典的Steiner树算法相比,该算法具有明显优势。     

A hybrid scatter search meta-heuristic for delay-constrained multicast routing problems

This paper investigates the first hybrid scatter search and path relinking meta-heuristic for the Delay-Constrained Least-Cost (DCLC) multicast routing problem. The underpinning mathematic model of the DCLC multicast routing problem is the constrained Steiner tree problem in graphs, a well known NP-complete problem. After combining a path relinking method as the solution combination method in scatter search, we further explore two improvement strategies: tabu search and variable neighborhood search, to intensify the search in the hybrid scatter search algorithm. A large number of simulations on some benchmark instances from the OR-library and a group of random graphs of different characteristics demonstrate that the improvement strategy greatly affects the performance of the proposed scatter search algorithm. The hybrid scatter search algorithm intensified by a variable neighborhood descent search is highly efficient in solving the DCLC multicast routing problem in comparison with other algorithms and heuristics in the literature.     

A scalable method for DCLC problem using hierarchical MDP model

It is well known that the delay-constrained least-cost (DCLC) routing problem is NP-complete, hence various heuristic methods have been proposed for this problem. However, these heuristic methods have poor scalability as the network scale increases. In this paper we propose a new method based on the Markov Decision Process (MDP) theory and the hierarchical routing scheme to address the scalability issue of the DCLC routing problem. We construct a new two-level hierarchy MDP model and apply an infinite-horizon discounted cost model to the upper level for the end-to-end inter-domain link selection. Since the infinite-horizon discounted cost model is independent of network scale, the scalability problem is resolved. With the proposed model, we further give the algorithm of solving the optimal policy to obtain the DCLC routing. Simulation results show that the proposed method improves the scalability significantly.     

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

很多实时多媒体应用要求通信网络提供多播服务支持，而且往往需要传输的信息满足源端到目的端的时延约束。该文对时延约束的多播路由问题进行了研究，基于原有的从源端到目的端的时延受限路径构造算法，提出了一种时延受限多播路由算法。该算法能够快速构建满足时延约束的多播树。理论分析表明，该算法的时间复杂度和CDKS算法相同。仿真实验结果表明，该算法所构建的多播树代价低于CDKS算法。     

VPLS中具有时延约束机制的组播问题研究

VPLS作为一种革新的技术受到了广泛的关注和认可。但是,在用VPLS承载数据业务的时候还面临着一个复杂的难题：组播问题。传统的组播问题是具有NPC复杂度的Steiner问题。本文试图从应用和实现的角度出发,建立具有时延约束机制的组播转发机制。以建立最小时延树和最小开销树作为初始条件,运用循环迭代算法,求解满足时延约束的最小开销树。算法的复杂性为O（n^2）。作为补充,还提出了组播树的剪枝机制。试验结果表明,文中的算法简单可行,易于实现,适合应用于VPLS网络中。     

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

基于ＱｏＳ的多播路由算法需要在满足每个个体ＱｏＳ需求的同时,又能高效管理网络资源,提出了一种满足端端时延限制的低代价多播路由算法。算法使用一个修改的Ｓｔｅｉｎｅｒ树近似算法先构建时延有界的低代价多播树,再通过最小时延路径与其它尚不在多播树的且结点相连。