通过蚁群算法解决QoS组播路由问题

随着网络应用越来越广泛，在传统的HTTP、FTP、E-mail等数据业务的基础上增加了各种实时和多媒体业务。要满足这些业务的需求，特别是要保证一些实时业务的带宽、时延等特殊需求，仅以目前Internet中"尽最大努力交付"的服务是难以完成的。因此，组播技术的研究成为这个领域的热点，同时也对于组播的服务质量提出了更高的要求，QoS组播的需求已成为Internet相关技术的研究热点。Qos组播路由技术是网络支持QoS保证的关键技术之一，因此，高效的QoS组播路由算法就显得至关重要。QoS（Quality of Service）服务质量，是网络的一种安全机制， 是用来解决网络延迟和阻塞等问题的一种技术。 在正常情况下，如果网络只用于特定的无时间限制的应用系统，并不需要QoS,比如Web应用，或E-mail设置等。但是对关键应用和多媒体应用就十分必要。当网络过载或拥塞时，QoS 能确保重要业务量不受延迟或丢弃，同时保证网络的高效运行。网络资源总是有限的，只要存在抢夺网络资源的情况，就会出现服务质量的要求。服务质量是相对网络业务而言的，在保证某类业务的服务质量的同时，可能就是在损害其它业务的服务质量。例如，在网络总带宽固定的情况下，如果某类业务占用的带宽越多，那么其他业务能使用的带宽就越少，可能会影响其他业务的使用。因此，网络管理者需要根据各种业务的特点来对网络资源进行合理的规划和分配，从而使网络资源得到高效利用。

遗传算法GA（Genetic Algorithm）的特点在于具有搜索能力、潜在的并行性及较强的鲁棒性，计算过程简单，能很好地解决开发最优解和探寻搜索空间的矛盾；蚁群算法（ant colony optimization, ACO），又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种信息素，吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物！有些蚂蚁并没有象其它蚂蚁一样总重复同样的路，他们会另辟蹊径，如果令开辟的道路比原来的其他道路更短，那么，渐渐，更多的蚂蚁被吸引到这条较短的路上来。最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复着。

将遗传算法和蚁群算法用于QoS组播路由已经取得较好的效果，但是缺点也很明显。遗传算法对于系统中的反馈信息利用不够，在中后期往往做大量无谓的迭代，求最优解的效率降低；蚁群算法则由于初期蚂蚁的随机活动使得前期信息素的更新较慢、求解速度慢，由于在后期容易早熟，而陷入局部最优。

本文针对目前应用蚁群算法解决NP完全问题的研究现状，以基本蚁群算法为基础，提出一种遗传多蚁群融合算法（GAMAC_QoS）来解决QoS多约束组播路由问题，对多个约束QoS组播路由问题进行了研究。利用基本蚁群算法的分布式和全局搜索能力，使信息素积累和更新收敛于最优路径上。

（3）初始种群生成

采用随机方法从中选择若干个个体组成初始种群，首先删除不满足QoS约束条件的节点以及与之相连的链路，再删除不满足带宽要求的链路，得到一个新的精简后的网络拓扑。

（4）选择算子

采用个体最佳保留策略（最佳个体保留个数设置为2）与采用遗传算法中运用最广的轮盘赌选择机制执行选择功能。

（5）交叉算子

采用Davis顺序交叉方法，先进行常规的双点交叉，再进行维持原有相对访问顺序的巡回线路修改[5].具体交叉如下：

①随机在父串上选择一个交配区域，如两父串选定为：

old1=12|3456|789

old2=98|7654|321

②将old2的交配区域加到old1的前面，将old1的交配区域加到old2的前面：

old1'=7654|123456789

old2'=3456|987654321

③依次删除old1',old2'中与交配区相同的数码，得到最终的两子串：

new1=765412389

new2=345698721

（6）变异算子

采用逆转变异法逆转。如染色体（1-2-3-4-5-6）在区间2-3和区间5-6处发生断裂，断裂片段又以反向顺序插入，于是逆转之后的染色体变为（1-2-5-4-3-6）。这里的进化，是指逆转算子的单方向性，只有经逆转后，适应值有提高的才接受下来，否则逆转无效。

2.2 GAMAC_QoS中的多蚁群算法规则

GAMAC_QoS算法定义了三种类型的蚂蚁：

（1）全智能蚂蚁。蚂蚁按照传统蚁群算法选择规则选择下一节点，此蚂蚁称为全智能蚂蚁，简称为M1.

（2）非智能蚂蚁。蚂蚁不按照选择规则来选择路径，而是随机地选择下一节点，此蚂蚁称为非智能蚂蚁，简称为M2.引入非智能蚂蚁是为了在算法陷入停滞时扩大搜索空间。

（3）半智能蚂蚁。在选择下一节点时以δ概率按照全智能蚂蚁的选择策略选择下一节点，以1-δ概率按照非智能蚂蚁的选择策略选择下一节点，此蚂蚁称为半智能蚂蚁，简称为M3.考虑到算法在陷入停滞的时候，前期的部分次优解还是有价值的，因此引入半智能蚂蚁是最大程度地利用之前的次优解，增加搜索最优解的成功率。

算法开始之时，蚂蚁的初值全为智能蚂蚁，数目为M,执行蚁群算法。当算法进行到停滞状态且比当前的参考值差的时刻，全智能蚂蚁发生变化，一部分转变成非智能蚂蚁，一部分转变成半智能蚂蚁，余下部分保持全智能蚂蚁的性质不变，其中半智能蚂蚁由智能蚂蚁和非智能蚂蚁组成，引入参数δ（0<δ<1）来决定其组成比例。

（1）适应值函数与遗传算法的适应值函数相同。

（2）路径选择策略[6].全智能蚂蚁M1,其选择策略为：

对于非智能蚁群M2,选择前进策略是不考虑任何信息素的反馈信息，随机选择下一节点，其前进策略如下：

图2表示网络费用与迭代次数的关系，目的节点为20个，从图中可以看出，随着迭代次数的增加，该算法比基本蚁群算法具有更快的收敛性，最终组播树的费用也更低，与参考文献[7]算法相比收敛速度上相差无几，但是最终最优组播树的费用更低。

针对蚁群算法的特点进行了改进，将遗传算法和蚁群算法相融合，并结合多蚁群的行为，提出了GAMAC_QoS组播路由算法。通过仿真实验证明，该算法相比于基本蚁群算法和参考文献[7]算法，在多节点中寻找组播树，具有更好的寻优能力、可靠性更高，是一种解决QoS组播路由的有效算法。