基于蚁群优化算法的QoS路由算法的设计与仿真

摘 要 传统蚁群算法在解决QoS路由问题时往往会在非线性整数规划模型的基础上盲目地搜索，其仿生智能没有与问题特征很好的结合，所得到的组播树有可能包含冗余的环路。为了研制性能更高的QoS组播路由方法，本文提出了一种新的基于蚁群优化算法的QoS组播路由新算法。新算法根据最大最小蚂蚁思想，结合蚂蚁-Q算法对原算法进行了改进，使得在实际应用中，算法选路更合理有效。

关键字 蚁群优化算法 QoS路由

中图分类号：TP311.52 文献标识码：A

0引言

纵观目前学术界已经提出的QoS组播路由算法，有相当一部分是基于备选路径集的方法，即首先使用蚁群算法创建源节点到各个目的节点的备选路径集，把组播路由的数学模型转化为一个非线性整数规划模型，再使用神经网络等算法求解这个模型。虽然这些算法利用了生物进化、群智能等仿生智能，但它们都是在非线性整数规划模型的基础上盲目地搜索，其仿生智能没有与问题特征很好的结合，这限制了其优化性能的充分发挥，而且所得到的组播树有可能包含冗余的环路。为了研制性能更高的QoS组播路由方法，本文提出了一种新的基于蚁群优化算法的QoS组播路由新算法。

1算法设计

传统蚁群系统在解决复杂问题时会早熟停滞。当蚂蚁搜索太少并且迅速开发到信息素浓度较高的路径时，就有可能发生停滞。Stutzle和Hoos研究出最大最小蚂蚁系统用于避免早熟停滞的发生。最大最小蚁群系统与蚁群系统最大的不同在于其信息素浓度被限定在一个给定的区间内。新算法根据最大最小蚂蚁思想，结合蚂蚁-Q算法对原算法进行了改进。

3 算法仿真

为了尽可能体现真实的网络环境，验证算法的可行性，在模拟仿真实验中采用基于C-均值聚类的随机网络拓扑生成器。仿真过程中，网络拓扑模型是建立在1000km€？000km的正方形区域内，由新算法随机在该区域内随机生成25个节点，并建立连接。不断调整组播树，直到寻找到的包含所有目的节点的组播树势能不再减小，组播树更新结束。

在100个不同的网络拓扑模型上运行新算法，验证结果成功率为99%。

4 算法评价

针对传统蚁群系统在解决复杂问题时存在的缺陷，本文提出了改进的蚁群算法。原有蚁群系统算法中采用参数控制路径上的信息素浓度挥发，在蚂蚁寻路过程中，如果某一步选择概率较大，会造成后续蚂蚁在此路径上堆积过多信息素，最终会引起早熟停滞的现象发生。在新算法中，本文加入了参数，用于控制新加入的边（）的信息素浓度在规定范围内，这样就可以避免单条路径上信息素猛增的现象发生。同时，在信息素更新规则中，将原有信息素变量（）更改为价值变量（），这样更有利于在实际问题中的应用。在QoS路径求解中，价值变量（）体现为路径代价。

新算法在设计中保留了原有蚁群算法中随机数调整转移规则的技术，加入了边界制约参数防止路径中信息素浓度的过度增长，有效避免了早熟停滞的发生。引入了价值变量，使得在实际应用中，选路更合理有效。

参考文献

[1] 段海滨.蚁群算法原理及其应用.科学出版社，2006（07）.

[2] 蔡慧，刘洪波，等.基于K均值聚类的随机网络拓扑模型[J].计算机工程与设计，2009，30（5）：1089-1901.

推荐访问:算法 路由 仿真 优化 设计