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

2.
多媒体通信中带度约束的多播路由算法   总被引:15,自引:1,他引:14  
刘莹  刘三阳 《计算机学报》2001,24(4):367-372
随着多媒体业务的发展,多播技术应用日益广泛,多播路由是要寻找连接源节点和一组目的节点的一棵多播树,这个问题在数学上归结为Steiner树问题,它是一个NPC问题。在实际网络中,网络节点具备不同的多播能力,有些节点不支持多播,有些节点支持多播,但为了保证网络速度和节点负载平衡,支持多播的节点要限制其复制信息的数量,即节点的多播能力受限。在这种情况下,寻找多播树变得更加困难,该文用节点的约束来表示敏个节点具备的多播能力,节点多播能力受限情况下的多播路由问题被称为带度约束的多播路由问题,其仍是一个NPC问题。该文提出了一种求解带度的约束多播路由问题的双层遗传算法。算法的基本思想是最优多播树应是一棵满足度约束的最小生成树,因此问题的关键在于如何找到包括在最优生成树中的Steiner节点。遗传算法 采用二进制编码方式,内层算法用于求解满足度约束的最小生成树;外层算法进行全局搜索。该文将算法在稀疏图上进行实验,为了更好地模拟真实网络,稀疏图中每个节点具有不同的多播能力,并且多播目的节点数目相比于网络节点数要小。实验对算法进行了三方面比较:(1)解的质量;(2)计算时间;(3)算法的收敛性。实验结果表明,文中提出的遗传算法能够找到费用较小的多播树,但是当网络规模增大时,算法的求解时间也较长。  相似文献   

3.
张峰  贾智平  蔡晓军  张兰华 《计算机科学》2014,41(9):132-136,164
在Ad hoc网络中,随着多播应用领域的日益扩大,如何构造最小能耗多播树是一个重要问题。针对选择不同的中继节点对构造最小能耗多播树产生的影响,提出了一种优化最小能耗多播树构造的基于精英学习的量子粒子群算法(QPELSO)。为了避免粒子群算法早熟收敛,采用动态逼近学习策略对精英个体进行局部更新,使其跳出局部极值点,引导种群进行有效搜索;借鉴群体早熟判断机制对停滞状态下的精英个体空间进行变尺度混沌扰动,增大种群全局搜索空间,有效平衡了算法的局部和全局搜索能力。模拟实验结果表明,改进后的粒子群算法具有较强的优化能力,并且有效地优化了最小能耗多播树的构造。  相似文献   

4.
QoS多播路由算法的核心问题就是建立满足QoS约束的多播树,它是计算机网络中著名的受约束最小Steiner树问题,是一个NP完全问题。量子遗传算法是基于量子计算理论的新型遗传算法,基于量子遗传算法的基本原理,提出了QoS约束的多播路由算法(QoSMR-QGA),并详细介绍了QoSMR-QGA算法的实现过程。仿真实验表明,该算法具有较好的算法收敛性和多播路由成功率。  相似文献   

5.
随着当前Intemet的发展和各种多媒体应用的出现,多播技术得到大量应用。多播路由算法主要用来建立一棵性能良好的多播树,并使它能够满足各种业务的服务质量需求。将多种群并行技术和退火技术相结合,克服了基于标准遗传算法的多播路由算法过早收敛和后期搜索速度较慢的缺陷,且使用树状编码方法,提出求解带宽、时延、时延抖动和分组丢失率约束的代价最小多播树的多种群并行退火遗传多播路由算法。对QoS多播路由选择问题进行了描述,给出多种群并行退火多播路由遗传算法和一种有效去除冗余信息的遗传算法编码设计技术,通过仿真实验证明了算法的正确性,分析了算法的时间性能,表明该算法快速有效。  相似文献   

6.
基于遗传算法的带宽-时延约束多播路由优化算法   总被引:7,自引:3,他引:7  
随着许多多媒体在高速网络中的应用,多播路由问题成为越来越重要的课题。多播路由问题在计算机网络中是著名的Steiner树问题,同时也是NP完全问题。该文提出了一种基于遗传算法的多播路由优化算法,采用可变长度染色体(多播树)和基因(路径)应用于编码问题。该算法在满足带宽和时延约束条件下寻找代价最小的多播树。仿真实验证明该算法能快速找到最优解,收敛速度快,可靠性高,能够满足多媒体网络对实时性的要求。  相似文献   

7.
随着多媒体业务的普及,如何为MANET多播路由提供QoS保障成为研究热点。提出了一种带宽和时延受限的QoS多播路由协议,它利用遗传算法搜索满足QoS要求的最优多播树。仿真结果表明该协议收敛速度快,寻径成功率高,它为移动网络中具有QoS保障的多播通信提供了一种有效途径。  相似文献   

8.
基于混合遗传算法的QoS多播路由算法   总被引:5,自引:2,他引:5  
陈年生  李腊元  董武世 《计算机应用》2005,25(7):1485-1487,1497
具有多QoS约束的多播路由问题具有NP完全的复杂度。基于延时、延时抖动、带宽、丢包率等QoS约束,描述了一种适应于研究QoS多播路由的网络模型,提出了基于遗传算法和禁忌搜索混合策略的具有多QoS约束的多播路由算法。该算法充分利用了遗传算法和禁忌搜索的优点。克服了遗传算法在求解多QoS约束多播路由问题中的爬山能力差以及不成熟收敛等问题。仿真实验结果表明,该算法为多QoS约束多播路由问题的求解提供了一种有效的新途径。  相似文献   

9.
胡光岷  CHANG Rocky 《软件学报》2008,19(6):1546-1554
提出了一种提高多播可扩展性的新思路——将多播可扩展性作为一个最优化目标引入到多播路由算法的设计中,采用多目标最优化路由算法,提高现有多播可扩展性方法的效率.采用多目标最优化路由设计方法对AM(aggregated multicasc)和DTM(dynamic tunnel multicast)两种方法进行改进,给出了相应的最优化目标、启发式多目标最优化多播路由算法和多目标最优化多播路由遗传算法.对于AM方法,使用该算法可以有效地减少汇聚多播树的数量;对于DTM方法,使用该算法可以有效地增加非分枝节点的数量,减少多播状态.  相似文献   

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

11.
基于GA的多约束条件QoS组播路由算法   总被引:2,自引:1,他引:1       下载免费PDF全文
李飞  侯惠芳 《计算机工程》2009,35(16):198-200
通过研究带QoS约束的组播路由问题,提出一种由改进的遗传算法实现的组播路由算法。利用树型结构编码,设计独特的杂交算子和变异算子。仿真实验验证该算法能节省大量解码操作,缩短求解时间,并且其收敛速度不会随着网络规模的增大而变慢,具有快速收敛寻优的特点。  相似文献   

12.
遗传算法、蚁群优化算法已在多播路由优化问题中得到了广泛应用,但由于算法本身的缺陷,二者在具体应用时都存在着时间性能与优化性能之间的矛盾。论文将遗传算法与蚁群优化算法二者合成,优势互补。仿真实验表明,应用这种算法于多播路由问题,可以得到比现有启发式算法更好的结果。  相似文献   

13.
求解动态组播路由问题的混合优化遗传算法   总被引:4,自引:0,他引:4  
陈云亮  杨捷  康立山 《计算机应用》2006,26(8):1947-1949
分析了具有网络时延和时延抖动限制的动态组播路由问题的数学模型。在此模型的基础上提出了一种基因库(GP)与传统遗传算法(GA)混合的优化算法GP-GA。该算法利用基因库保存进化过程中得到的解路径以指导后继进化过程,同时改进了交叉和变异算子来加快算法的收敛速度。考虑到问题可能陷入的局部最优情况,又构造了基于“保留和不保留”的进化控制策略来增强寻优能力,很大程度上避免了算法“早熟”现象的发生。大量的仿真实验表明:GP GA算法相对现有的遗传算法求得最优解的概率更高,相对于动态的组播环境也有很好的代价性能。  相似文献   

14.
Many new multimedia applications involve dynamic multiple participants, have stringent end-to-end delay requirement and consume large amount of network resources. In this paper, we propose a new dynamic delay-constrained least-cost multicast routing algorithm (DDCLCMR) to support these applications. When group membership changes, the existing multicast tree is perturbed as little as possible. Simulation results show that DDCLCMR performs very well in terms of cost for both, static and dynamic multicast groups, when compared to the best multicast algorithms known. Our evaluation of the cost performance of the algorithms showed that DDCLCMR is always within 10% from BSMA which has the best cost performance among all the proposed delay-constrained static multicast heuristics, while NAIVE, the well-known dynamic multicast routing algorithm, is up to 70% worse than BSMA in some cases.  相似文献   

15.
基于遗传算法的多约束QoS多播路由优化算法   总被引:3,自引:0,他引:3  
随着大量新型的多媒体在高性能网络、移动网络及Internet中的应用,满足QoS约束的多播路由问题成为越来越重要,它吸引了许多爱好者.本文讨论了多约束QoS多播路由问题,主要包含延迟、延迟抖动、带宽和分组丢失率等QoS约束,文中描述了一种在动态网络环境及不确定参数下适应于研究QoS多播路由的网络模型.提出了一种在网络规模、可行性方面为Imernet、移动网络和高性能网络下基于遗传算法的多约束QoS多播路由优化算法(MQMRGA).仿真结果表明该算法收敛速度快、可靠性高.MQMRGA为QoS多播路由提供了一种新的有效途径.  相似文献   

16.
基于蚁群遗传混合算法的QoS组播路由   总被引:3,自引:0,他引:3       下载免费PDF全文
具有延迟、延迟抖动、带宽、丢包率等服务质量约束的组播路由问题具有NP完全的复杂度。基于蚁群优化算法和遗传算法,提出解决QoS约束组播路由问题的混合算法。利用遗传算法和蚁群优化算法各自的优点,使用蚁群优化算法选择种群,遗传算法优化蚂蚁遍历所得到的解。仿真实验结果表明,该算法可满足各个约束条件,且全局寻优性能好,能够满足网络服务质量要求。  相似文献   

17.
基于信息熵多种群遗传算法的组播路由   总被引:1,自引:1,他引:0  
针对网络信息不确定性和链路负载不均匀所造成的网络拥塞,提出基于信息熵的组播路由算法。该遗传算法从最小代价树开始,在多种群中不断选择信息熵较大的种群,以求得满足延时要求且路径负载较小的组播树。结果表明,该算法性能快速、有效地构造最小时延组播树,且保证网络负载均衡分布。  相似文献   

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

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