基于遗传算法的可扩展应用层组播树构建

摘要：

在应用层组播中,为降低节点的路径延时,通常采用遗传算法和启发式算法来减小组播树直径的方法,但在组播树具有大规模节点数时,遗传算法收敛时间长,而采用启发式算法难以在有约束条件下达到全局最优.本文在具有超节点的双层应用层组播模型基础上,提出了利用遗传算法构建出度受限最小带权路径延时生成树(MWPL -DC-ST)的生成算法GA-MWPL-DC-ST,利用该算法可在超节点上对双层组播树进行分布式构建,从而将求最优解问题的巨大计算量分担到多个超节点上.算法中的初始化、杂交和变异阶段采用启发式算法,对变异参数进行适应性调整,加快了算法的收敛速度.仿真试验表明,本文提出的双层应用层组播模型和GA-MWPL-DC-ST算法能得到比启发式算法更优的解,与采用单层模型的遗传算法相比较,显著降低了算法收敛时间,解决了遗传算法构建有大规模节点数的应用层组播树的可扩展性问题.

关键词：遗传算法、应用层组播、平均路径延时

所属期刊栏目：28

分类号：TP301(计算技术、计算机技术)

资助基金：中国下一代互联网示范工程CNGI资助项目CNGI-04-12-1D;北京市科技计划D0105006040331

在线出版日期：2007-10-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：1591-1595