论文部分内容阅读
伴随着互联网的蓬勃发展,IPV6和物联网的实施已经将网络节点扩展到生活的各个角落,而网络的多点通信应用离不开组播技术的支持。在传统的组播中,为每个组播组建立一棵组播树来分发数据包,同时为这棵组播树分配一个组播地址,组播树上的每个路由器需要维护组播的转发状态。当网络中存在大量的并发组播组的时候,相应的组播树也会随之急剧的增加,这些组播树不仅降低了组播地址的查询速度,而且维护着数量庞大的组播状态转发表,需要消耗大量的内存和CPU资源。在网络中,组播组是动态变化的,有组成员加入和离开时,组播树会进行更新,因此对于组播树的控制和管理是一个开销非常大的事情。所有这些后果都来自于组播状态的可扩展问题,它使得网络的性能急剧下降,成为组播应用大规模部署的重要瓶颈。针对组播状态的可扩展性问题,UCLA大学网络实验室提出了聚合组播的解决方案,该方案强迫具有相近形状原始组播树的若干个组播组共享同一棵大型组播树,这样能够有效减少网络中组播树的数目,减少转发的组播状态数量,降低资源的消耗和维护和管理组播树的开销。聚合组播的主要思想是在给定的带宽浪费阈值的约束下建立能够覆盖所有组播组的数目最少的聚合组播树。已有的聚合组播优化算法有Greedy算法和Genetic算法,为聚合组播理论的发展做出了重要的贡献。本文在对已有的聚合组播优化算法的研究基础上,提出了一种基于扰动因子的蚁群算法来减少组播树的数目,而且为了加快蚁群的算法的收敛速度,还提出了一种蚁群算法的并行计算模式。1.基于扰动因子的蚁群算法是对蚁群系统和最大-最小蚁群两种算法的改进。在该算法中,每次循环完成之后,不仅对最优聚合组播树的集合进行信息素的更新,而且也对随机产生的次优的聚合组播树的集合进行更新。通过引入随机的次优解这个干扰因子,可以增加解的多样性,防止过早陷入局部最优的泥淖中。仿真实验表明,蚁群算法的性能超过了贪心算法。贪心算法的启发式信息过于简单,搜索的解的空间范围狭窄,而蚁群算法使用信息素来标记最优解,多付出了时间上的尝试,取得结果自然要好。2.针对串行蚁群算法求解的时候收敛速度慢的缺点,将其改造为并行的蚁群算法,其核心思想是将能够并行处理的计算任务平均分配到多个处理节点上,经过控制节点和从节点的协同计算,最后取得了满意的效果。仿真实验表明,随着组播组数目的增加,计算时间的代价会逐渐的提高,但是并行计算减少了很多串行算法所用的时间,而且并行效率也会提高,这样的并行算法对大规模的聚合组播的优化是显而易见的。