共查询到17条相似文献,搜索用时 140 毫秒
1.
基于MPH的时延约束Steiner树算法 总被引:2,自引:0,他引:2
为了在时延约束务件下进一步优化组播树代价,并降低算法计算复杂度,研究了时延受限的Steiner树问题.分析了MPH(minimum path heuristic)算法的计算复杂度;在此基础上设计了一个时延约束Steiner树算法DCMPH(delay-constrained MPH)用于构造时延约束最小代价组播树.该算法中每个目的结点通过与当前组播树有最小代价的路径加入组播树;若时延不满足要求,则通过合并最小时延SPT(shortest path tree)树进而产生一个满足时延约束的最小代价组播树.仿真实验表明,DCMPH算法生成的组播树在保证时延要求的情况下,与同类算法相比取得了很好的代价性能和较低的计算复杂度. 相似文献
2.
分析了时延受限的Steiner树问题,总结了在构建组播树过程中的代价和计算复杂度变化规律,并根据实际网络环境,从优化最短路径出发,提出了一种基于优化最短路径的时延受限组播路由算法AOSPMPH。该算法以MPH算法为基础,利用Floyd最短路径优化算法求出节点对之间的最短路径,选择满足时延要求的最小代价路径加入组播树,进而产生一棵满足时延约束的最小代价组播树。仿真结果表明,AOSPMPH不但能正确地构造时延约束组播树,而且其代价和计算复杂度与其他同类算法相比得到了优化。 相似文献
3.
4.
组播通信是从一个源节点同时向网络中的多个目的节点发送分组的通信服务,它一般提供一个以上的端到端的服务约束,实际的路由算法在应用时可以受到多重约束,解决这类问题的组播路由算法是NP完全的。在研究了构建组播树的相关算法后,提出了一种新的时延和时延差约束的低代价组播路由算法-DDVMC。该算法采用基于贪婪策略的Dijkstra最小生成树算法,利用局部信息来构建低代价组播树,很好地平衡了树的代价、时延和时延差。仿真表明,该算法能正确地构造出满足约束的组播树,同时还具有较低的代价和计算复杂度。 相似文献
5.
针对时延约束的组播路由问题,提出了一种动态不重组组播路由算法NDMADC。算法将DGA和Floyd最短路径优化算法相结合,确保节点在满足时延约束的前提下动态选择到组播树有最小代价的路径加入组播会话。由于采用贪心算法思想,NDMADC算法保证了节点加入组播树时不需要组播树重组。仿真表明,该算法能正确地构造出满足时延约束的组播树,具有较低的代价和计算复杂度。 相似文献
6.
提出了一种新的受时延约束的组播路由算法。算法借鉴了MPH算法的思想,最初的组播树只包含源结点,然后每次将到达组播树的代价最小且满足时延约束的结点及其相应的路径加入到组播树,直到所有的成员加入为止。谊算法能够快速地得到一棵满足时延约束的组播树,并且组播树的代价也很小。实验表明:该算法简单,复杂度低,性能良好,易于在分布式环境中实现,可应用于实际的应用系统中。 相似文献
7.
8.
基于共享边的时延约束组播路由算法 总被引:1,自引:2,他引:1
为了优化在时延约束下的组播树代价,降低算法计算复杂度,研究了时延受限的Steiner树问题.分析了最短路径启发式(MPH)算法的执行过程,以此为基础提出一个基于共享边的时延约束组播路由算法ESAMPH.该算法在构建组播路由树时能够优先采用包含有较多的最短路径经过的节点,这样后面的组播成员节点到树上的最短路径也有可能经过这些节点,由此实现边的共享,降低了组播树的代价.仿真结果表明,ESAMPH算法在代价、延迟和计算时间之间能获得较好的平衡,综合性能较好. 相似文献
9.
10.
针对时延约束下低代价组播树的构建方法,提出了一种基于关键节点的时延约束低代价组播路由算法.该算法对已有的动态时延优化的链路选择函数进行改进,并加入关键节点和关键次数的概念.在首次选择目的节点时,重点考虑关键节点和关键次数因素,降低了选择低代价链路的时间复杂性,再利用改进后的链路选择函数依次选择节点加入树中,进而产生满足要求的组播树.实验仿真结果表明,该算法不仅能正确构建出时延约束低代价组播树,且与其他算法相比,构成组播树所需平均时间更少. 相似文献
11.
时延受限费用最小多播树算法 总被引:1,自引:0,他引:1
在一种构造费用最小多播树算法(RSTF)的基础上,考虑了网络的时延,提出一种新的时延受限费用最小多播树算法。通过随机网络的仿真结果表明,新算法与KPP算法相比在费用、时延方面有很好的性能。 相似文献
12.
13.
14.
15.
通过对时延约束组播路由网络模型的分析,提出了一种基于拉格朗日松弛法的时延约束的低代价组播路由算法(LR-DLMR)。由于封闭图对原网络的多播不可达问题,该算法并没有构建原网络的封闭图,从而有效利用了链路中间节点信息。仿真实验结果表明本算法具有良好的稳定性,有较低的代价和时延。 相似文献
16.
多播路由KPP算法的改进 总被引:1,自引:1,他引:0
论文提出一种满足端到端时延限制的多播路由算法。该算法参考KPP[7]算法,在构造多播路由树的过程中动态调整路径的选取,使尽可能地共享网络中的链路,并对所构造的多播树进行进一步的调整优化,最后得到一棵低代价的满足端到端时延限制的多播路由树。论文通过对KPP算法进行分析发现KPP算法思想忽略了对转发节点的处理,而且在两节点间路径的选取过程中仅仅选取最佳路径,这就导致了对边稠密的图,KPP算法存在缺陷。算法基于上述缺陷完善了KPP算法,在复杂的网络图中应用该算法比KPP算法更加有效,实验模拟表明该算法构造的多播树与KPP算法构造的多播树相比能优化9%到10%。 相似文献
17.
This paper is concerned with a restricted version of minimum cost
delay-constrained multicast in a network where each link has a delay and a
cost.
Given a source vertex $s$ and $p$ destination vertices
$t_1, t_2, \ldots, t_p$ together with $p$ corresponding nonnegative delay
constraints $d_1, d_2, \ldots, d_p$,
many QoS multicast problems seek a minimum cost multicast tree in which
the delay along the unique $s$--$t_i$ path is no more than $d_i$ for
$1 \le i \le p$.
This problem is NP-hard even when the topology of the multicast tree is fixed.
In this paper we show that every multicast tree has an underlying Steiner topology and that
every minimum cost delay-constrained multicast tree corresponds to a minimum
cost delay-constrained realization of a corresponding Steiner topology.
We present a fully polynomial time approximation scheme for computing a
minimum cost delay-constrained multicast tree under a Steiner topology.
We also present computational results of a preliminary implementation to
illustrate the effectiveness of our algorithm and discuss its applications. 相似文献