论文部分内容阅读
随着视频会议、视频点播、远程教育等分布式实时业务的广泛应用,作为其核心技术的QoS组播技术引起了人们的高度重视。组播是一种有效的支持多点通信的机制,它采用树转发结构,每一个数据包只在节点处被复制,在每一条链路上只发送一次。这种方法使IP组播能有效的同时向组内的成员发送数据,并支持大量的组播组。QoS组播是在满足带宽、延迟、丢包率等多个QoS约束条件下进行的组播。QoS组播路由技术是Internet上流媒体、视频会议等高带宽、共享型应用的重要基础。近几年的研究表明,组播路由算法对组播应用的QoS保障起到了非常关键的作用,对QoS组播路由算法的研究已经成为网络研究领域中的一个非常重要研究方向。在以往的研究中,QoS组播路由问题常归结为最小费用的约束斯坦立树(Steiner Tree)问题,该问题已经被证明是一个NP-C问题,不存在多项式时间的解法。随着网络规模的不断扩大和人们对网络服务质量要求的不断提高,研究新的基于多约束的QoS组播路由算法,以获得良好的网络服务质量和高的网络资源利用率,具有十分重要的意义。本文在对蚁群优化算法和组播问题作深入研究的基础上,提出了可以解决Ad Hoc网络上的QoS组播路由问题的带方向因子的蚁群算法、基于树的蚁群算法及其改进算法:(1)目前,Ad Hoc网络因其优异的特性和特殊的应用,受到越来越广泛的重视。本文综合考虑了Ad Hoc网络的特性、已有的GPS定位技术以及蚁群算法本身的特点,在此基础上提出了“方向因子”这个启发式函数,并将方向因子跟蚁群算法相结合,设计了带方向因子的蚁群算法——ACA-O(Ant ColonyAlgorithm considering Orientation),用以解决Ad Hoc网络上的QoS组播问题。该算法使用方向因子来诱导蚂蚁的搜索行为,使蚂蚁能更加迅速地到达目的地,从而保证搜索的快速有效性,避免陷入局部最优解。仿真实验结果表明,该算法提高了执行速度,减少了信息包的发送量,节省了能量开销。(2)本文提出了一种基于树的蚁群算法——ACAT(Ant Colony Algorithmbased on Tree)。与传统蚁群算法的先寻找路再合成树的模式不同,ACAT采用了以树生长的方式直接寻找组播树的模式。基于树的蚁群算法简化了寻树的机制,算法的效率得到了提高。仿真实验结果表明,跟传统蚁群算法相比,ACAT算法能以更快的速度收敛到近似最优解,组成员数目越多,这种优点越明显。(3)专门针对Ad Hoc网络,我们对基于树的蚁群算法作了改进,在原算法基础上添加了重新定义的方向因子。在Ad Hoc网络拓扑,改进后的算法能通过方向因子的诱导作用,使树呈放射状生长,减少树生长过程中的“折回生长”现象,提高了算法的效率。仿真实验结果表明,跟原算法相比,改进后的算法在Ad Hoc网络上收敛速度更快,效率更高。