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

为了在时延约束务件下进一步优化组播树代价,并降低算法计算复杂度,研究了时延受限的Steiner树问题.分析了MPH(minimum path heuristic)算法的计算复杂度;在此基础上设计了一个时延约束Steiner树算法DCMPH(delay-constrained MPH)用于构造时延约束最小代价组播树.该算法中每个目的结点通过与当前组播树有最小代价的路径加入组播树;若时延不满足要求,则通过合并最小时延SPT(shortest path tree)树进而产生一个满足时延约束的最小代价组播树.仿真实验表明,DCMPH算法生成的组播树在保证时延要求的情况下,与同类算法相比取得了很好的代价性能和较低的计算复杂度.     

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

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

一种满足时延和时延差约束的组播路由算法

针对时延和时延差约束的组播路由优化问题,提出一种最优代价组播路由算法。基于Dijkstra最短路径树算法,通过指示函数调整新加入节点的优先级,利用局部信息构建低代价组播树,使其能较好地平衡组播树代价、时延和时延差之间的关系。仿真实验结果表明,该算法能正确构造出满足时延和时延差约束的组播树,同时具有时间复杂度低、求解成功率高等综合性能。     

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

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

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

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

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

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

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

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

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

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

一种具有时延约束的组播路由算法研究*

对于多媒体应用等实时组播业务而言,组播路由算法不仅要考虑优化代价,还要考虑时延约束。针对这一问题,提出一种支持动态组播的时延受限低代价组播路由启发式算法(delay-constrained multicast algorithm,DCMA)。该算法基于DDMC算法进行扩展,采用新的指示函数和链路选择函数,综合考虑了时延和代价,有效保证了组播树的性能,而且时间复杂度低,可用于实际的应用系统中。     

基于关键节点时延约束低代价组播路由算法

针对时延约束下低代价组播树的构建方法,提出了一种基于关键节点的时延约束低代价组播路由算法.该算法对已有的动态时延优化的链路选择函数进行改进,并加入关键节点和关键次数的概念.在首次选择目的节点时,重点考虑关键节点和关键次数因素,降低了选择低代价链路的时间复杂性,再利用改进后的链路选择函数依次选择节点加入树中,进而产生满足要求的组播树.实验仿真结果表明,该算法不仅能正确构建出时延约束低代价组播树,且与其他算法相比,构成组播树所需平均时间更少.     

时延受限费用最小多播树算法

在一种构造费用最小多播树算法（RSTF）的基础上,考虑了网络的时延,提出一种新的时延受限费用最小多播树算法。通过随机网络的仿真结果表明,新算法与KPP算法相比在费用、时延方面有很好的性能。     

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

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

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

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

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

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

多播路由KPP算法的改进

论文提出一种满足端到端时延限制的多播路由算法。该算法参考KPP[7]算法,在构造多播路由树的过程中动态调整路径的选取,使尽可能地共享网络中的链路,并对所构造的多播树进行进一步的调整优化,最后得到一棵低代价的满足端到端时延限制的多播路由树。论文通过对KPP算法进行分析发现KPP算法思想忽略了对转发节点的处理,而且在两节点间路径的选取过程中仅仅选取最佳路径,这就导致了对边稠密的图,KPP算法存在缺陷。算法基于上述缺陷完善了KPP算法,在复杂的网络图中应用该算法比KPP算法更加有效,实验模拟表明该算法构造的多播树与KPP算法构造的多播树相比能优化9%到10%。     

基于拉格朗日松弛法的时延约束组播路由算法

通过对时延约束组播路由网络模型的分析,提出了一种基于拉格朗日松弛法的时延约束的低代价组播路由算法(LR-DLMR)。由于封闭图对原网络的多播不可达问题,该算法并没有构建原网络的封闭图,从而有效利用了链路中间节点信息。仿真实验结果表明本算法具有良好的稳定性,有较低的代价和时延。