随着不断增长的分布式多媒体应用的需求,以及Internet上商业化应用的飞速发展,对网络的服务质量(QoS:Quality of Service)提出了更高的要求,高效的QoS支持变得越来越重要。IETF已经提出了许多服务模型和机制来满足对QoS的需求,QoS路由(QoS-based routing)就是其中的关键技术之一。 组描是指将同一信息从源结点传送到网络中多个结点(不一定是网络中所有结点)。实现组播的一般方式是建立组播树,组播树的优点在于:首先,信息以并行方式沿着树枝发送到不同的组播终点,从而降低了信息传递的时延;其次,信息的复制只在树的分支处进行,因此网络中需要传送的复制信息量最少,能够节约网络带宽资源,降低网络负载,减少拥塞,所以组播成为目前研究最多、应用最广的网络信息传输方式。组播路由算法主要用来建立一棵性能良好的组播树,并使它能够满足各种业务的服务质量需求。本文主要研究就是QoS组播路由算法,即建立满足媒体传输服务质量需求的组播树。 本文首先分析了组播和组播路由选择技术的原理,随后介绍了遗传算法的基本思想和运行过程。组播路由算法通常采用启发式技术,但仿真结果表明,这些启发式算法要么太复杂而难以求解,要么太费时而不能实际应用。 遗传算法则是近几年提出的一种模拟生物界自然选择和遗传机制,只有简单高效、高度并行、随机和自适应的新型最优化搜索算法,非常适用了织播路由。本文在总结了别人的工作的前提下,对带宽、延时、延时抖动和包丢失率约束以及费用最小的QoS组播路由问题进行分析,抽象出OoS组播路由模型的基础上,提出了一种新的基于遗传算法的QoS组播路由算法。该算法具有以下特点: 预处理机制,这样简化了算法设计的难度,同时也优化了算法的性能,减少了算法搜索的空间; 树型结构编码,这样就可以用树的任何一种数据结构来描述算法中染色体的结构,既减少了编码空间,也省略了解码操作; 启发式初始种群生成和交叉策略,该交叉策率采用了启发式方法,兼顾了各种QoS度量,使后代能尽量继承好的性能(满足QoS约束且费用较小),加快了算法收敛的速度; 指导性变异过程,有效的改善了算法的性能,既有利于算法跳出局部最优解,也有利于算法向性能奸的方向转化(满足QoS约束且费用较小)。 而且仿真结果也表明该算法快速有效,并且在性能和效率方面都要优于文中提到的其它现存的算法。