智能光网络中选路算法的研究

摘 要：鉴于最大最小蚁群算法有很好的全局搜索能力，被广泛应用于智能光网络的动态选路。但是该算法存在着计算量大，收敛时间慢等缺陷。为了加快蚁群算法的收敛时间，这篇文章通过引进，并且在TSP问题中进行验证，实验结果表明改进型蚁群算法可以有效的提高蚁群算法的收敛时间。

关键字：智能光网络路由；蚁群算法；TSP

智能光网络凭借其可动态分配带宽、高效地支持大容量数据业务等优良性能，成为了重要的通信传输技术。智能光网络除了继承了光传送网的主要特点外，还具备以下优点：可实现流量工程要求，具有灵活多样的恢复能力，能很好地利用资源等。如果把智能光网络中的所有设备都放在一个域中进行管理，域中的每个节点就都需要维护一个非常庞大的数据库信息。为解决此问题，多域智能光网络应运而生，成为了未来传送网规模化分布式管理的必然结果。本文主要针对多域光网络中的关键技术-路由技术进行研究。

1 智能光网络中的路由算法

路由和波长分配指的是在给定一组光路连接请求、拓扑确定的情况下，寻找一条从源节点到目的节点的路由，并为这些路由分配相应的波长。

路由技术分为动态路由技术和静态路由技术。静态路由是指光连接请求在全网的业务矩阵是已知的。静态路由是在路由器中设置固定的路由。动态路由是网络中的路由器之间相互通信，传递路由信息，利用收到的路由信息更新路由表的过程。

几种常见的路由算法定义如下：

固定路由算法：各个节点之间的信息传输路径是提前确定好的，每个节点仅需要将静态路由信息存储到其他节点，请求到达时，節点选择默认的到特定目的节点的路由。

固定备选路由算法：在固定路由算法的基础上，按固定顺序依次考虑一组备用路由的可用性。

自适应路由算法：自适应路由策略路径不是提前固定的，而是根据当前网络链路状态，动态选择一对节点之间的每条路由[2]。

本文对智能光网络路由算法中的蚁群算法进行了研究，针对该算法收敛性慢的问题进行了改进，提出了一种改进型蚁群算法。

2 蚁群算法

20世纪90年代，意大利学者M.Dorigo， V.Maniezzo受到蚂蚁集体寻找最短路径觅食行为的启发，首次提出了基于蚂蚁种群的新型优化算法，即蚁群算法[3]。该算法提出后，以此算法为基础解决了一系列的组合优化问题，如智能光网络中的选路问题。

蚁群算法全局搜索能力非常好。但是，存在计算量大、收敛时间慢等缺陷。本文从蚁群算法的收敛速度出发，采用新的信息素更新策略对最大最小蚁群算法进行了优化。

2.1 基本蚁群算法数学模型

通过研究，蚂蚁在从蚁穴到食物的过程中能够在它经过的路径上释放一种叫信息素的物质。蚂蚁在运动过程中能感知信息素的强度，从而实现信息的交流。算法中蚂蚁工作方式如下：每只蚂蚁根据状态转移规则选路，通过局部和全局信息素更新找到最短路径。

选路过程中，位于节点i的蚂蚁用公式（1）来选择下一节点j。

其中为全局信息素挥发参数，与局部信息素挥发参数值不相同，为一次迭代中找到的全局最优路径，称之为迭代最优路径。

2.2 改进型蚁群算法的基本原理

为了加快蚁群算法的收敛时间本文对基本蚁群算法的信息素更新公式做了改进。基本蚁群算法中，信息素增量与路径长度呈线性关系，且变化较为平缓，不同长度路径的信息素增量差别不大。针对该问题，本文提出了一种新的信息素更新策略见公式（6）。

改进的信息素更新公式斜率大，不同长度路径上的信息素增量的差异拉大，这样不同长度的路径通过信息素的累积就能更快的区分开来，从而更快的找到最优路径，收敛速度加快。

3 仿真与结果分析

本文分别对最大最小蚁群算法和改进型蚁群算法，在TSP问题中进行仿真。仿真拓扑为eil51。参数设置：m =70、=1、=4、Q =100。

图2和图3分别为加入最大最小信息素限制的基本蚁群算法和改进型蚁群算法在eil51中的仿真结果。每幅图中右图L best2表示迭代的最优路径，L ave2表示迭代后各蚂蚁寻路的平均值；对比两图，改进型蚁群算法能够更快地找到最优路径。

4 结语

本文首先对基本蚁群算法的原理进行了介绍。然后，就基本蚁群算法收敛速度慢的问题，提出了一种改进型蚁群算法。通过仿真验证了该改进型算法的可行性。

参考文献

[1].王玉亭. 智能光网络层域路由算法的研究[D]. 北京：北京邮电大学，2012.

[2]. M Dorigo， G Di Caro. Ant algorithms for discrete opetimization[J]. Artificial Life， 1999， 5（3）： 137-172.

[3].M Dorigo， L M Gambardella. Ant colonies for the traveling salesman problem [J]. BioSystems， 1997， 36（43）： 73-81.

[4].陈昊. 蚁群优化算法的原理及其应用[J]. 湖北大学学报，2006，28（4）： 350-352.

[5].段海滨. 蚁群算法原理及其应用[M]. 北京：科学出版社，2005.

作者简介

雷梦瑶（1991-），女，山西，硕士研究生，研究方向：多域智能光网络路由与波长算法研究。