首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到19条相似文献,搜索用时 140 毫秒
1.
基于MPH的时延约束Steiner树算法   总被引:2,自引:0,他引:2  
为了在时延约束务件下进一步优化组播树代价,并降低算法计算复杂度,研究了时延受限的Steiner树问题.分析了MPH(minimum path heuristic)算法的计算复杂度;在此基础上设计了一个时延约束Steiner树算法DCMPH(delay-constrained MPH)用于构造时延约束最小代价组播树.该算法中每个目的结点通过与当前组播树有最小代价的路径加入组播树;若时延不满足要求,则通过合并最小时延SPT(shortest path tree)树进而产生一个满足时延约束的最小代价组播树.仿真实验表明,DCMPH算法生成的组播树在保证时延要求的情况下,与同类算法相比取得了很好的代价性能和较低的计算复杂度.  相似文献   

2.
刘维群  李元臣 《计算机应用》2012,32(5):1244-1246
针对时延约束的组播路由问题,提出了一种动态不重组组播路由算法NDMADC。算法将DGA和Floyd最短路径优化算法相结合,确保节点在满足时延约束的前提下动态选择到组播树有最小代价的路径加入组播会话。由于采用贪心算法思想,NDMADC算法保证了节点加入组播树时不需要组播树重组。仿真表明,该算法能正确地构造出满足时延约束的组播树,具有较低的代价和计算复杂度。  相似文献   

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

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

5.
基于遗传算法的受限时延最小代价组播路由问题求解   总被引:3,自引:0,他引:3  
张洁  黄德才 《计算机应用》2003,23(Z2):11-13
在计算机通信中,组播技术越来越重要,它是保证视频会议、多媒体教学系统、视频点播等应用得以实现的基础.文中首先给出基于受限时延的最小代价组播树问题的网络模型及其数学描述.然后提出了一种基于遗传算法来解决该问题,该方法可以在满足时延约束的情况下,寻找费用最小的组播路由树.数值仿真实验结果表明该算法有较好的性能,快速有效.  相似文献   

6.
孙光明  王硕  李伟生 《计算机工程》2010,36(13):117-119
低代价最短路径树是一种广泛使用的组播树,通常不能满足实时多媒体应用中信息从源端到目的端传输的时延限制。针对该问题,提出基于时延约束的快速低代价组播路由算法,利用代价构建满足时延约束的初始树,将不满足时延约束的路径用最小时延路径代替。仿真结果表明,相比时延约束最短路径树算法,该算法的计算时间更少,组播树的总代价更低。  相似文献   

7.
一种基于模拟退火方法的多约束QoS组播路由算法   总被引:3,自引:0,他引:3  
研究了带宽、时延及时延抖动约束最小代价的QoS组播路由问题,提出一种利用模拟退火方法解决该问题的QoS组播路由算法SABDMA。该算法通过选择合适的模拟退火参数迭代求解,以获得满足QoS约束的最小代价组播树。同时,为避免搜索区域的扩大和计算时间的增加,根据时延和时延抖动的关系,提出采用“路径交换”策略在可行解范围内构造邻域集。仿真结果表明该算法具有可行、稳定、收敛快的特点;能根据组播应用对QoS的限制要求,有效地构造代价较低的组播树,具有较强的实时性。  相似文献   

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

9.
一种基于禁忌搜索的时延约束组播路由算法   总被引:4,自引:0,他引:4  
张琨  王珩  刘凤玉  曹宏鑫 《计算机工程》2005,31(11):22-24,64
提出了一种使用禁忌搜索方法构造组播树的时延约束最小代价组播路由算法(TSBDMA)。该算法充分利用禁忌搜索方法中灵活的记忆功能和禁忌规则等特点,以最小时延树为初始解,并使用换边操作构造邻域集,最终求得满足条件的组播树。仿真实验结果表明本算法具有代价性能良好、可靠性高、收敛速度快、时延低的特点。  相似文献   

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

11.
随着网络通信技术的发展和Internet的普及,性能出色的组播路由越来越重要。著名的组播路由Steiner树问题是NP完全问题,应采用启发式方法求解。文中在常规量子遗传算法中引入并行进化模型,提出了一种解决多约束QoS组播路由优化问题的算法。在满足带宽、时延约束条件下寻找代价最小的组播树,并合理安排节点负荷,减少通信开销。仿真实验结果表明本算法搜索速度快、全局寻优能力强,性能和效率优于常规量子遗传算法。  相似文献   

12.
基于启发式遗传算法的QoS组播路由问题求解   总被引:63,自引:0,他引:63  
研究了带宽、延时抖动和包丢失率约束以及费用最小的QoS组播路由问题,并提出一种启发式遗传算法。该算法有以下特点:(1)预处理机制;(2)树结构编码;(3)启发式交叉策略;(4)指导性变异过程,最后通过仿真实验证明该算法快速有效。  相似文献   

13.
量子克隆多播路由算法   总被引:5,自引:0,他引:5  
李阳阳  焦李成 《软件学报》2007,18(9):2063-2069
BSMA(bounded shortest multicast algorithm)被认为是最好的受限多播路由算法;然而,过长的计算时间限制了其应用.作为一种全局优化算法,遗传算法(GA)被越来越多地应用于解决多播路由问题.与传统的算法相比,遗传算法的全局搜索能力更强,但其易"早熟"的特点使它并不总是能够得到最优多播树.提出量子克隆多播路由算法,有效地解决了"遗传"多播路由算法中的"早熟"问题,量子交叉的引入,加快了算法的收敛速度.算法实现简单、控制灵活.仿真结果表明,该算法的性能优于BSMA算法和传统的遗传算法.  相似文献   

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

15.
王旅  胡劲松  彭宏  李君 《计算机工程与应用》2006,42(19):123-125,188
多路广播技术可以使多种网络资源得到接近最佳的使用率,提供满足QoS需求的多播服务的关键是如何建立满足多个QoS约束的最小代价树,多约束QoS多播路由选择问题是NP完全问题。论文提出的极值元素算法(EEA)能够快速解决全局优化问题,极值元素算法选择亲本的原则是:该亲本为极值点,与极值点的适应度无关。描述了多约束QoS多播路由问题的网络模型,给出了极值元素算法的原理,并将该算法应用于求解多约束QoS的多播路由选择问题。  相似文献   

16.
免疫组播路由选择算法   总被引:15,自引:0,他引:15  
刘芳  冯小军 《计算机学报》2003,26(6):676-681
研究了带宽延时受限、费用最小的QoS组播路由问题,并提出了一种解决该问题的免疫算法.免疫算法的核心在于免疫算子的构造,而它又是通过接种疫苗和免疫选择两个步骤来完成的.根据QoS组播路由问题,给出了免疫疫苗选取与免疫算子构造的具体方法.将免疫算法应用于组播路由选择,是通过在基于遗传算法的组播路由选择的基础上引入免疫算子来实现的.该算法采用的进化算子简便、高效.仿真实验表明,该算法不仅有效可行,而且较好地解决了标准遗传算法中出现的退化现象,提高了收效速度和搜索能力.  相似文献   

17.
基于遗传算法的时延受限多播路由研究   总被引:1,自引:0,他引:1  
陈曦  柳林 《计算机工程与应用》2002,38(17):170-171,183
该文探讨了包交换计算机网络中,具有端到端时延限制的多播路由问题。提出了一种基于遗传算法的多播路由优化算法,利用该算法可以实现在给定网络和多播需求的情况下,寻找费用最小的多播路由树,使该树覆盖所有的多播目的节点,并使网络费用达到最小。  相似文献   

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

19.
李渊  杨立波 《计算机科学》2013,40(4):115-118
针对Ad hoc网络中最小能耗多播树的生成和优化问题,提出了基于最优能耗多播树构造的Ad hoc网络节点路由算法。在该算法中,首先将最小能耗多播树生成问题转化为不同中继节点集合幂空间中的动态寻优问题,构建基于最优能耗多播树求解模型;然后利用改进的粒子群算法对不同维度空间上代表中继节点链路的粒子的权值进行映射和修正计算,再依据粒子适应度值对粒子的局部极值和全局极值进行更新;最后根据粒子位置和速度更新机制进行迭代计算,将最终的全局极值点和极值作为最优多播树的节点位置和能耗值。实验仿真证明,该算法具有较好的粒子多样性,全局搜索和局部搜索能力较好,并且优化能力较强。  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号