聚合组播算法研究

论文摘要

近年来,随着在Internet上流媒体、视频点播等业务的相继开展,IP组播技术得到了快速的发展。组播是一种有效的支持多点通信的机制,它采用树转发结构,每一个数据包只在节点处被复制,在每一条链路上只发送一次。这种方法使IP组播能有效的同时向组成员发送数据,并支持大量的组播组。IP组播是Internet上流媒体、视频会议等高带宽、共享型应用的重要基础。然而,一棵组播分布树要求所有树节点保持每一个组的转发状态,因此,当多个组播组并存于网络当中的时候,IP组播遇到一系列问题:随着组播组个数的增加,组播转发状态增多,组播树上路由器的内存需求随之增大:同时,由于每个数据包的转发需要进行地址查找,进行组播转发查询的CPU开销也随之增大,转发过程也会变慢。当网络中的组播会话数很大时,需要大量的资源和控制开销来管理组播组。组播转发状态数是制约网络中大规模组播应用可扩展性的瓶颈。聚合组播技术就是针对大规模组播可扩展性问题、结合真实网络拓扑结构特点提出来的。其主要思想是适当放宽对节约带宽的要求,使能够复合的组播组共享一棵组播分发树。树节点上保持的是这棵树的状态,而不是每一个组播组的状态,这样大大减少了组播转发的状态数,提高了网络性能。聚合组播问题的关键在于如何找到数目最小的组播树,使之覆盖所有的组播组。它的数学本质是最小集合覆盖问题,是一个NP-C问题。传统的解决聚合组播的方法是贪婪算法。贪婪算法有一定的局限性,它每一次都选择当前情况下的最优解,很容易陷入局部最优解,所以得到全局最优解的可能性很小,最终的聚合效果并不理想。针对于这个问题,本文提出了拉格朗日松弛算法、遗传算法和免疫算法来选择聚合组播树。拉格朗日松弛的基本思想是,把造成问题难的约束条件吸收到目标函数中,并使得目标函数仍保持线性,使得问题容易求解。在传统的拉格朗日松弛算法的基础上,算法能够动态调整拉格朗日乘子,使找到的解尽量接近于全局最优解。遗传算法是一类借鉴生物界“自然选择、适者生存”机制的智能搜索算法。在生物进化过程中,适应性好的个体生存和繁衍的可能性大,适应性差的个体被淘汰,最终生成最优个体。遗传算法是一种有效的全局优化搜索算法。免疫算法是一类借鉴生物免疫系统提出的智能搜索算法,它利用先验知识来引导种群的进化,通过生成不同抗原的抗体来达到全局优化的目的,可以在庞大的搜索空间中寻找接近最优解的准全局最优解。相同网络拓扑和相同数目组播组条件下的仿真结果表明,这三种算法在提高聚合度、降低转发状态方面都优于传统的贪婪算法。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 组播转发状态数问题
• 1.2 聚合组播的提出
• 1.3 聚合组播的研究现状
• 1.4 论文的主要工作概述
• 1.5 论文的整体结构和章节安排
• 第二章 聚合组播介绍
• 2.1 聚合组播的相关概念
• 2.2 带宽浪费分析
• 2.3 聚合组播的数学模型
• 2.4 国际上求解聚合组播的方法
• 2.4.1 选树算法
• 2.4.2 仿真环境
• 2.5 本章小结
• 第三章 解决聚合组播的拉格朗日松弛算法
• 3.1 传统的拉格朗日松弛算法
• 3.2 拉格朗日松弛算法求解聚合组播问题
• 3.3 仿真实验结果
• 3.4 本章小结
• 第四章 解决聚合组播的遗传算法
• 4.1 传统的遗传算法
• 4.1.1 编码
• 4.1.2 适应性评估
• 4.1.3 选择种群
• 4.1.4 选择双亲
• 4.1.5 交配
• 4.1.6 变异
• 4.1.7 自适应
• 4.1.8 替换
• 4.2 遗传算法求解聚合组播问题
• 4.2.1 编码
• 4.2.2 适应性评估
• 4.2.3 选择种群
• 4.2.4 选择双亲
• 4.2.5 交配
• 4.2.6 变异
• 4.2.7 自适应
• 4.2.8 替换
• 4.3 仿真实验结果
• 4.4 本章小结
• 第五章 解决聚合组播的免疫算法
• 5.1 免疫算法
• 5.2 免疫算法求解聚合组播问题
• 5.2.1 接种疫苗
• 5.2.2 疫苗检测
• 5.3 仿真实验结果
• 5.4 本章小节
• 第六章 总结和展望
• 6.1 总结
• 6.2 展望
• 参考文献
• 致谢
• 攻读学位期间发表的主要学术论文目录
• 攻读学位期间参与的科研项目目录
• 学位论文评阅及答辩情况表