论文部分内容阅读
随着计算机网络技术的发展,新兴的大量多媒体应用如电视会议、多媒体教学、视频点播(VOD)、分布式数据库同步更新等,均涉及到多个用户参与,这不仅需要消耗大量的网络资源,而且视频、音频等多媒体业务对网络服务质量(QoS)也提出了更高要求,组播路由技术正是在此背景下应运而生,它是目前计算机网络传输过程中应用研究较广的一种连接方式。组播涉及到将同一信息从源节点传送到网络中的多个不同的目标节点,组播问题的关键在于确定信息到多个目标节点的传送路径。目前确定这种传送路径通常采用树型结构,即建立组播树(组播树是以源节点为根,且覆盖所有目的节点的一棵生成树)。组播路由算法的作用就是依据多媒体业务的特点,建立一棵满足各种业务服务质量(QoS)需求而且性能良好的组播树。
本文对组播问题的基本知识进行了综述,介绍了当前解决组播路由问题的多种算法。在对现有组播路由算法研究的基础之上,系统总结了两种现代优化算法:遗传算法和神经网络中的BP算法。同时依据组播路由的特点,对这两种算法进行了有针对性地改进后,将其应用于组播路由问题。结果表明,改进后的算法对组播路由问题更加适用。
我们所研究的重点是针对当前各种启发式算法在解决组播路由问题时存在的问题与不足,提出了三种新型的优化算法:梯度改进的遗传算法、改进的B-P算法、这两种算法相融合的新型优化算法。在遗传算法中,我们通过修改梯度向量使函数适应度值的收敛速度与全局收敛性在算法的前后期各有侧重,同时根据深度优先搜索算法思想构造各种各样的既考虑函数值又充分考虑函数值变化率的适应度函数,解决了传统遗传算法中收敛速度与全局收敛相互掣制的缺陷;改进的B-P算法中引入动量因子和可变学习速度来提高收敛速率,通过正态分布克服局部极小的问题;文中我们利用改进的遗传算法求出包括给定节点集的组播树,再根据最小树的特点,通过改进的B-P算法为组播树中不满足条件的节点重新寻路,直到树中所有节点都满足要求。它充分利用了遗传算法的收敛快速性和神经网络的精确性,并采用节点序列编码和浮点数编码两种编码机制,提出了一种新的最小树组播路由算法。实验结果表明,此算法比前两种算法更加有效。