Internet网络传输和处理能力的大幅提高使得基于网络的应用越来越多,如远程教学、视频会议、数据分发和网络游戏等网络多媒体应用。这些多媒体应用有着数据量大、时延要求高、持续时间长等特点,需要采用不同于传统单播和广播机制的转发技术及服务质量(Quality of Service,简称QoS)保证机制来实现,组播技术正是解决这个问题的理想方案。组播(Multicast)是一种有效的支持多点通信的机制,一般指的是一个或多个源节点向多个目的节点发送信息的通信方式。它是指在IP网络中将数据包以尽力传送(best-effort)的形式发送到网络中的某个确定节点子集,这个子集称为组播组(Multicast Group) o QoS是网络在传输业务流时,业务流对网络服务的需求的集合,其中业务流是指与特定QoS相关的从源到目的地的分组流。IETF已经提出了多种服务模型和机制来满足各种QoS组播的需求。实时应用往往会对延时,延时抖动,带宽,丢失率,业务代价等多个参数同时提出性能要求。这些参数相互独立时,选择满足多个参数限制的最优组播路由就成为NP完全问题。
本文在对组播问题和蚁群优化算法作深入研究的基础上,提出了可以解决组播路由问题的生长森林的蚁群优化算法和可以分布式实现的蚁群优化算法:
(1)针对多播树费用最小化问题,即Steiner树问题,它是指使用树最优化函数构建最优的多播树,本文提出一种可以解决Steiner树问题的新的蚁群算法,生长森林的蚁群优化算法。蚂蚁行动过程中形成的是森林,每只蚂蚁走出的每一步都只是使当前的森林进一步生长,蚂蚁行动的目标就是森林中所有的树连接成一棵树且这棵树包含了所有的目标节点。本文分别使用SteinLab Repository中B类拓扑图和MRSIM中的拓扑生成器生成的Waxman模型作为测试的拓扑,仿真试验结果表明,算法的性能明显优于KMB、SPH、CDKS和传统蚁群算法等生物启发式算法。本算法在速度上与传统蚁群算法、遗传算法相比要快得多,并且在拓扑规模增大时,有更好的表现。此算法有效地解决了无约束多播树费用最小化问题。
(2)对于多QoS约束的组播路由问题,本文提出了一种可以分布式实现的蚁群优化算法,算法考虑了多种QOS约束条件,包括带宽、延迟、延迟抖动和丢包率。在此算法中蚂蚁行动过程中形成的是组播树的森林。在开始时森林中只有源节点和目的节点。蚂蚁走出一步是使森林中的每棵树都选择一条边加入。若某一步结束时森林中仅剩下一棵树,则蚂蚁达到目标,停止行动。算法最为重要的一个优点是可以分布式实现。仿真结果表明算法在寻优能力和收敛速度方面都优于ANTNET、传统蚁群和遗传等算法,而且拓扑规模越大,优秀性越明显。可以分布式实现的蚁群优化算法既能并行性和分布式实现,又能以较快的速度收敛到一个理想的结果。
暂无评论