论文部分内容阅读
近些年来,由于互联网技术的迅猛发展以及通信网络带宽和处理能力的大幅提高,使得网络能够提供形式多样的多媒体业务,同时也使得支持“点对多点”或“多点对多点”的组播通信方式成为网络支持多媒体业务的必要形式。组播路由作为多媒体网络的核心技术,其研究范围包括路由协议、路由策略、路由算法等多个方面,而组播问题的关键在于组播路由的确定,所以寻找简单、高效、健壮的组播路由算法一直是网络界致力研究但未完全解决的问题。许多分布式的多媒体应用对延时、延时抖动、带宽以及包丢失率有不同的要求,而带有多个QoS约束参数的QoS组播路由问题属于NP完全问题。对于QoS组播路由问题的研究大都集中在采用启发式算法进行求解,然而由于这些算法要么具有较高的时间复杂度而不能满足实际应用的需求,要么算法早熟收敛,陷入局部,不能求出全局最优解。因此,基于多约束QoS的组播路由算法的研究成为网络研究领域的重要内容和热点问题。遗传算法是一种全局优化搜索算法,具有简单通用,鲁棒性强和并行处理以及应用范围广等显著特点,其缺点是容易早熟,陷入局部最优解,后期爬山能力弱。模拟退火算法是一种局部搜索能力极强的全局搜索算法,它采用Metropolis准则从而能够跳出局部达到全局最优解,其主要缺点是解的质量与求解时间长短之间的矛盾。本文正是在总结了这两种算法的优缺点的基础上提出了一种新型的混合遗传算法。首先,采用基于备选路径集的整数队列编码机制有效减少了编解码的工作量,并针对遗传算法的局限性,对适应度函数进行了调整,实施最优保留策略,应用启发式交叉和变异策略。其次,用模拟退火算法对遗传操作的子代个体进行优化,采用“路径交换”策略在可行解范围内构造邻域解集,避免了搜索区域的扩大和计算时间的增加,加快了算法的收敛速度。最后,利用海明算子提高算法对解空间的覆盖度,利用入侵算子保证种群的健壮性,利用重升温算子强化算法的局部搜索能力。本文中,在参考Salama模型基础上利用K均值聚类算法保证节点分布接近真实情况,设计了一种简单有效的网络仿真环境,对提出的算法进行仿真,并与其它算法进行比较,仿真结果表明算法具有可行性、有效性和稳定性,以及代价低、收敛快的特点。