基于改进蚁群算法的PTN网络路径优化

殷 星，魏 明

(1.武汉邮电科学研究院，湖北 武汉 430070；2.武汉烽火技术服务有限公司，湖北 武汉 430070)

0 引 言

最短路径问题的研究在运筹学、图论和计算智能中起着重要的作用。当前，国内外深入研究最短路径问题涵盖通信网络、物联网、机器人和地理信息导航等领域，极其具有研究和应用价值。早期研究最短路径主要有经典的Dijkstra算法、Floyd算法以及带有启发式搜索的A*算法，评价这些算法的优劣主要是从算法占用的时间和空间复杂度两个维度来衡量[1-3]。文献[4]运用改进的Dijkstra算法，在光网络中能够求解指定必经节点的最短路径，但缺点是只适用于网络节点数较少的骨干网中。文献[5]利用网络分割法将复杂网络分解成简单网络，基本思想是减小算法搜索范围达到降低求解网络规模的目的，虽能提高算法的运行效率，但无法快速有效地找出分割点。文献[6]在大规模网络中针对多约束多目标QoS路由问题提出一种遗传算法解决机制，但该算法应用范围有一定的限制。研究最短路径问题，人们试图用传统的经典算法去求解，在时间上并不令人满意。对于优化PTN网络中逻辑同路由问题的方法是要找出符合条件的最优路径，用这些最优路径来替换已经发生逻辑同路由中的路径，从而可以得出优化方案。根据该问题优化的思路，可以将该网络优化问题转换为求解带有多约束条件的最优路径问题。蚁群算法是一种优化路径的算法，具有很强的搜索最优解的能力，但该算法在面对复杂的优化问题时，容易陷入局部最优解，导致优化性能急剧下降[7]。

根据蚁群算法的优缺点，设计一种改进的蚁群算法来求解带有多约束条件的最优路径问题。首先对该问题进行数学建模，然后分析基本蚁群算法的原理，对该算法中的状态转移规则、启发式函数和信息素更新规则进行改进并适当调整其中的参数。实验结果表明，改进后的蚁群算法在求解含多约束条件的最优路径问题时，加快了收敛速度，提高了搜索目标的准确度，并且通过算例验证了改进蚁群算法的有效性。

1 数学模型

在PTN网络优化中，首先是寻找从源网元到宿网元之间的可达路由，在这基础上需要满足QoS约束条件，并且使得优化的路径质量达到最优，最终输出优化方案。QoS约束条件中的变量包括链路时延Delay、链路费用Cost、链路承载业务数量Quantity、链路带宽Band。可以将PTN网络中的路径优化问题转换成图论中带约束的最优路径问题。设无向图G=(V,E,W),其中顶点集V={v1,v2,…,vn}是图中的所有顶点，代表网络拓扑中的所有网元节点，边集E={(eu,v),u∈V,v∈Vandu≠v}是图中顶点u到顶点v的所有边，代表网络拓扑中网元之间的链路，权集W={(wu,v),u∈V,v∈Vandu≠v}表示图中每条边的权值，是一个四元组(Delay，Cost，Quantity，Band)，每条边的初始权值计算公式为：

(1)

根据大量的工程经验，权值影响因子a=0.3,b=0.3,c=0.2,d=0.2；为了方便描述，引入其他数学符号定义：

pod表示源节点到目标节点的路径，其中o,d分别表示图G中的源节点和目标节点；

tuv,Quv,Buv,Luv分别表示节点u到v的时延、业务数量、保证带宽、链路；

|pod|, |Luv|分别表示源节点到目标节点的路径长度、路径节点u到v的链路长度，|pod|=∪|Luv|；

p表示满足多约束条件的路径集合；

δ是每公里传输业务的费用；

Tlimit,Climit,Qlimit,Blimit分别表示设置限制的总时延、路径总费用、链路承载业务数量、链路承载带宽。

给出评价路径质量函数公式：

(2)

构建多约束最短路径目标函数的数学模型为：

(3)

工程上，当链路上的业务数量超过总承载业务数量、链路保证带宽超过承载带宽时，PTN网管将会显示链路的告警信息，因此选取的路径是要在满足QoS约束的条件下，求解目标函数的最优解。

2 算法设计

蚁群算法是一种根据自然界中蚂蚁觅食行为来求解组合优化问题的算法[8]。通过科学观察发现，自然界中的蚂蚁总能发现一条从蚁巢到食物源的最短路径，并且在寻找食物的过程中会释放一种挥发性物质，称为信息素。其他蚂蚁通过感知信息素的浓度来指导自己的运动方向，浓度越高，蚂蚁向该方向移动的概率就越大。因此，更多的蚂蚁在该路径上留下的信息素就越多，最终大部分的蚂蚁都会经过最优的路径。蚁群算法的核心主要是基于蚂蚁状态转移规则和信息素更新规则，但蚁群算法具有收敛速度慢、容易陷入局部最优解的缺陷[9]。为了提高蚁群算法的收敛速度和求解问题的正确率，在基本蚁群算法的基础上，对蚂蚁状态转移规则、启发式函数和信息素更新规则进行改进。

2.1 蚂蚁状态转移规则及启发式函数的改进

基本的蚁群算法状态转移公式[10]为：

(4)

其中，

(5)

基本蚁群算法中的启发式函数，由于使用节点之间距离的倒数作为指导蚂蚁运动的方向，导致蚂蚁在搜索的过程中每一步都趋于单步最优而偏离全局最优方向[11]。针对这一问题，该文采用当前节点走过的距离作为参考值对启发函数进行改进，改进的公式为：

(6)

其中，L(u)表示蚂蚁在节点u所走过的距离，即使单步距离Luv很小，当节点u走过的总路径L(u)较大时，节点u到v的期望程度也不会很大，避免了蚂蚁因贪图一小步而偏离全局最优解，使得蚂蚁算法在搜索的过程中有了方向性指导，提升算法搜索最优路径的精确度。

为了进一步提高蚂蚁在搜索下一个节点时的效率，将图G中初始权重wuv引入到状态转移规则中，使得在蚂蚁搜索下一个节点的过程中不会盲目随机地寻找路径，缩短算法寻优的收敛时间。改进后的状态转移公式为：

(7)

其中，

(8)

其中，ε是初始权重的重视程度因子。根据蚂蚁寻路的特性可知，蚂蚁在前期几轮迭代中随机寻路的收敛时间较长，这与q0是固定的阈值有关，因此对q0采用一种动态的调整策略，调整公式为：

(9)

其中，Nmax为最大迭代次数，Nc为当前迭代次数。

2.2 信息素更新规则的改进

基本蚁群算法信息素更新公式[12]为：

(10)

(11)

其中，H为信息素强度，是一个正的常数值。由于挥发系数ρ设置成一个固定的常数，对于蚂蚁经过的路径挥发速度都相同，这不利于提升蚂蚁搜索的效率，挥发系数设置不同，又会造成蚂蚁对某些路径有所偏好，也会影响蚂蚁搜索最优解的正确率[14]。因此，在设置不同的挥发系数时，需要弱化蚂蚁对单步路径的偏好，提高搜索效率。改进的挥发系数公式为：

ρ(t+1)=

(12)

2.3 算法寻优的步骤

改进后求解多约束最优路径的蚁群算法步骤如下：

①设置蚁群算法中的基本参数和约束参数；

②根据网络拓扑图中各边的权重初始化信息素；

③放置K个蚂蚁在源节点，蚂蚁通过状态转移规则和约束条件进行选路，路径信息素更新规则的选择采用局部和全局更新相结合的方式，即偏向最大信息素一侧采用全局更新，偏向最小信息素一侧采用局部更新；

④当蚂蚁都到达目标节点后，计算蚂蚁经过的路径质量；

⑤重复步骤④，直到K个蚂蚁都完成寻路为止；

⑥判断当前迭代次数是否达到最大迭代次数，是则将满足条件下的路径质量进行排序，输出路径质量最高的那条路径作为求解PTN网络中的最优路径；否则重复步骤③～⑤。

3 实验仿真及结果分析

3.1 仿真实验

该文利用可视化的网络拓扑生成软件Gephi，首先获取网管中的各网元坐标、网元名称、光纤连接信息和链路的权重值，其次将获得的数据转成CSV文件，将CSV文件导入到Gephi的数据资料中，用网络布局FR算法(Fruchterman-Reingold)生成300个节点的网络拓扑，如图1所示。

图1 网络拓扑无向图

在运行算法之前，需要对算法中的各个参数进行设置，详细参数如表1所示。

表1 参数设置

实验1：在网络节点数n=300和最大迭代次数Nmax=100的情况下，基于生成的网络拓扑图，将图中的所有节点依次按1～300进行编号，选定不同的三组源节点和目标节点，第一组源节点1和目标节点50，第二组源节点66和目标节点120，第三组源节点185和目标节点268，三组分别运行基本蚁群算法和改进后的蚁群算法，比较两者寻找到最优解时的收敛时间(单位：秒)、迭代次数和满足条件的路径个数。实验得到的数据如表2所示。

表2 改进前和改进后的蚁群算法比较

改进前和改进后的蚁群算法寻优迭代曲线如图2所示，平均收敛时间曲线如图3所示。

图2 寻优迭代曲线

图3 平均收敛时间曲线

实验2：选定固定的源节点和目标节点，逐渐增大网络节点n的个数，比较蚁群算法、遗传算法[15]和A*算法[16]达到最优解时的运行时间，实验数据如表3所示，实验结果如图4所示。

表3 算法最优解耗时比较

图4 寻优耗时曲线

3.2 结果分析

从实验1可以看出，相比较改进前，改进后的蚁群算法搜索效率有明显的提升，平均收敛时间缩短了68.95%。从得到最优解时的迭代次数上看，平均迭代次数减少了77.21%。从寻优的准确度上看，改进前的蚁群算法搜索满足约束条件的路径个数不全，这说明基本蚁群算法在寻优过程中很容易陷入局部最优解；改进后的蚁群算法提高了搜索的准确度。

从实验2可以看出，随着网络节点数的增加，基本蚁群算法的收敛时间急速增长，遗传算法和A*算法次之，改进后的蚁群算法收敛时间增长较缓，这是因为改进后的蚁群算法中的基本参数提升了算法的寻优速度，很好地克服了该算法的缺点。

4 结束语

关于优化PTN网络中存在的逻辑同路由问题，构建出了含多约束条件的最优路径模型，并采用改进的蚁群算法搜索出满足QoS约束的最优路径，将最优路径作为解决逻辑同路由问题的优化方案。通过改进基本蚁群算法中的状态转移规则、启发式函数和信息素更新规则，充分发挥出了算法较强的寻优能力，同时又避免了该算法“早熟停滞”现象的发生，加快了算法的收敛速度。实验结果表明，改进后的算法在运行效率和寻优效果上都有明显提升。今后，随着网络规模数量的增加，运行的时间复杂度也随之增高，研究将大型PTN网络进行分区和并行化思路是一种有效的解决方法。简单、易用的蚁群算法将在PTN网络规划和优化中发挥重要的作用，同时，该算法为研究网络最优路径问题提供一定的实用价值。