一种PTN网络路由调度方法

一种PTN网络路由调度方法一文创作于：2023-04-12 11:34:53，全文字数：15522。

一种PTN网络路由调度方法

t只需11万个，空间复杂度由O(N2)下降到O(N+R)，其中N为网络节点数量，R为链路数量。

2.2 算法对比及结果分析

原生Dijkstra算法的时间复杂度是O(N2)，并且空间复杂程度也是O(N2)[16]。而改进后的Dijkstra算法使用HashMap+List存储路径权值，并使用二分法搜索和并行方式进行计算，时间复杂度是O(N*log(N))，空间复杂度是O(N+R)，空间和时间复杂度都有了较大的提升。将算法改进前后的时间复杂度和空间复杂度进行对比，具体如图3和图4所示：

图3 算法改进前后的时间复杂度对比

图4 算法改进前后的空间复杂度对比

3 最优路由求解过程

最优路由调度方法：基于目标网络必经点间最短路径，通过使用VMMAS计算出满足约束条件的最优路由。其中，VMMAS是基于信息素混合更新和变异更新策略对最大最小蚂蚁算法进行优化得到。

3.1 个性化信息素设计

蚁群算法具有并行性、鲁棒性、正反馈性等特点，最早成功应用于解决著名的旅行商问题[17]。作为一类新型的机器学习技术，已经广泛用于组合优化问题的求解[18]。蚂蚁个体之间通过一种称为信息素的物质来进行信息传递，个体可以根据信息素的强度来指导自己的前进方向；而信息素会随着时间推移逐渐挥发，于是路径上通过蚂蚁的多少就会影响该路径残余信息素的强度[19-21]。现有技术方案的算法与约束强耦合，在算法实现中揉进业务约束的内容。这种方式具有明显的缺陷：不同业务约束之间可能存在互相制约，影响稳定性及正确性；业务约束实现需考虑算法本身的特点，效率低且不具有通用性。针对上述缺陷，引入自适应调整参数以制定不同环境的蚁群信息素，可使不同区域根据自身网络特点、各自的业务习惯和要求，获取最适配的路由调度结果。

3.2 VMMAS设计

最大最小蚂蚁算法（MMAS）是比利时学者Tomas Stutzle提出的[12]，具有收敛速度快的优点，也容易陷入局部最优。Weixin Ling等学者提出了自适应参数设置策略、分段求解等方式，对蚁群算法作进一步的优化改进[22-25]。参考Dorigo[26]对蚁群算法的全局收敛性进行的初步讨论，针对上述问题，对MMAS算法做了以下改进来增强算法的全局搜索能力：

（1）MMAS在开始阶段只使用迭代最优蚂蚁对信息素更新，以扩大算法的搜索范围。而随着算法的运行，MMAS逐渐增加使用至今最优蚂蚁的频率以保证算法的收敛。如果几次更新都使用迭代最优蚂蚁，至今最优解可能会因为信息素挥发而被蚂蚁遗忘。因此，提出信息素混合更新策略，每次迭代同时增加迭代最优解和至今最优解的信息素以扩大最优解搜索方向。更新权重考虑迭代最优解和至今最优解的路由长度，更新规则为：

其中，τij为路由(i,j)的信息素浓度；ρ为信息素蒸发的速率；x=Cp/Cl-1，Cp为当前迭代最优解长度，Cl为当前迭代之前所找到的最优解长度；f(x)代表信息素全局更新时Δ所占的比重。

当Cp≤Cl时，本次迭代没发现更优解，应增加Δ所占比重；反之，则应减少Δ所占比重。当Cp=Cl时，Δ和Δ比重各占1/2。

（2）MMAS存在容易陷入局部最优的不足。参考遗传算法思路，每一轮迭代选择部分解实施变异操作以增强全局搜索能力[27]。一般的变异算子随机选择某些变异位，这种操作可能会破坏优秀基因结构。参考2-opt算法思路，对变异的个体任意两点之间的基因片段进行倒置，变异后的个体若路径长度优于变异前，则保留变异结果，否则保留变异前个体。如变异前路径为(1,2,3,6,5,4,7,8)，变异片段为(3,6,5)，则变异后个体为(1,2,5,6,3,4,7,8)。然后比较变异前后两个路径长度，若变异后路径长度更小，则保留变异后路径，否则保留变异前路径。

改进后的VMMAS算法通过自适应调整参数和变异策略让MMAS在迭代早期可以快速收敛，在迭代后期跳出局部最优，实现收敛速度与计算精确度平衡。

3.3 最优路由计算过程

计算路由分为两部分：存量路由搜索和使用VMMAS计算。首先在存量路由中查找相同起点、终点和必经点的路由。如果存在这样一条路由，则直接返回路由，否则继续下一步计算。

使用VMMAS计算路由过程如下：

（1）初始化种群，将所有蚂蚁置于起始网元A上；

（2）对每次迭代的每只蚂蚁k：

从起始网元A出发，搜索一条遍历A和必经点Mi(i=1,2,…,m)的路由。由节点i转移到节点j的转移概率为：

其中，τij为路由(i,j)的信息素浓度；nij=1/dij为启发式因子；α、β分别代表信息素和启发因子的影响程度；dij为节点i到节点j的最短路由长度。

每只蚂蚁k都找到一条(A,…,Mki,Z)的路由后，随机选择部分路由实施变异算子操作。如果变异后路径长度更小，则保留变异后路径，否则保留变异前路径。

对于至今最优解和迭代最优解所经过的路由，按照公式(1)更新信息素浓度，其他路由则按照以下公式更新信息素：

VMMAS计算流程图如图5所示：

图5 VMMAS计算流程图

3.4 实验分析

实验分析主要针对MMAS和VMMAS算法进行比较，其中VMMAS各参数取固定值，实验只改变必经节点数量，两种算法分别测试10次求最优解平均值并记录算法找到最优解的次数。在Intel I5 2.6 GHz/4 GB机器运行程序，测试结果如表1所示，其中方括号中的数字表示测试过程中找到最优解的次数。链路权重由时延、抖动、带宽利用率、优先级等QoS相关参数计算获得，权重越小则链路质量越高。

表1 MMAS和VMMAS算法求解情况对比

通过分析表1 中两种算法的求解结果，可以看出VMMAS所求得的结果平均值更小、找到最优解次数更多，而且随着节点规模变大，VMMAS更能求出最优解，说明改进后的VMMAS算法具有更全面的搜索能力。

同时，通过分析MMAS 和VMMAS 算法分别求解节点数为76 的最优解演进过程，对算法的收敛情况进行对比，具体如图6 所示：

图6 MMAS和VMMAS算法求解节点数为76的演进情况对比

从图6可以看出，虽然MMAS能很快找到次优解，但之后需要经过480次迭代后才能找到下一个更优解；而VMMAS能够一直保持较稳定的全局搜索能力，收敛速度越来越快于MMAS，最终比MMAS更快找到最优解。

综上所述，VMMAS在全局搜索能力和收敛速度方面均胜于MMAS算法，其不仅能扩大蚂蚁的搜索范围、加快算法收敛速度，还能减少算路陷入局部最优的情况，使得路由调度更加精确、快速。

4 结束语

本文将路由调度问题转换成节点遍历问题，并综合使用改进后的Dijkst

提醒您：因为《一种PTN网络路由调度方法》一文较长还有下一页，点击下面数字可以进行阅读！

《一种PTN网络路由调度方法》在线阅读地址：一种PTN网络路由调度方法