一种PTN网络路由调度方法

王锐

（中国移动通信集团广东有限公司，广东 广州 510623）

0 引言

分组传送网（PTN,Packet Transport Network）是一种光传送网络架构和技术，在IP业务和底层光传输媒质之间设置了一个层面，它针对分组业务流量的突发性和统计复用传送的要求而设计，以分组业务为核心并支持多业务提供[1]。PTN结构复杂，需要合理地调度网络资源，以保证较好的网络服务水平和用户体验。PTN路由调度的目标是寻找一条从起始网元（简称A端）到目标网元（简称Z端）之间的最佳路由[2]。该路由除了要求权值和最小外，还需要满足多种业务约束（如必经节点、禁止节点）[3]。PTN路由调度属于典型的带约束最短路径优化（CSP,Constrained Shortest Path），无法使用传统的最短路径算法精确求解[4-5]。

现有的技术方案一般把路由调度当成无约束最短路径问题（SP,Shortest Path）来求解[6]，经常使用的有Dijkstra算法[7-8]、A*算法[9]等，并对基本算法进行定制修改以实现对特定业务约束的要求。比如，业务要求A、Z端的路由必经网元C，则分别计算最短路径A-C、C-Z，再将这两个结果拼接组成最终结果（A-C-Z）。这种方法需要穷举所有必经点的排列，计算复杂度等于必经点数量的阶乘。随着约束数量的增加，需要计算的组合数呈爆炸式增长，无法在有效时间内求解。

现有技术方案存在计算复杂度高、支持业务约束规模受限以及算法与业务强耦合的问题，而且在计算路由时未考虑复用已有A、Z端路由方案，若路由与用户经验不符，则需要花费额外的精力进行调整及优化。

蚁群算法是一种仿生学算法，它是意大利学者M.Dorigo在1991年提出的[10]。在其提出后的十多年里，蚁群算法在理论研究和实际应用上均取得较大发展。到目前为止，蚁群算法已在优化领域取得众多应用，其中在组合优化领域的应用最为广泛，包括旅行商问题（TSP,Traveling Salesman Problem）、二次指派问题（QAP,Quadratic Assignment Problem）、车间作业调度问题（JSP,Job Scheduling Problem）、车辆调度问题（VRP,Vehicle Routing Problem）等。

蚁群算法具有的优点包括：正反馈、较强的鲁棒性、分布式计算、易于与其他方法结合等。同时，蚁群算法也有自身的不足之处，包括：需要较长的计算时间、容易出现停滞现象。围绕着改进蚁群算法的性能，从最初的蚂蚁系统开始，学者们进行了大量的改进研究。蚁群算法主要包括5个基本系统：蚂蚁系统（AS,Ant System）、精英系统（ASelite,Ant System with Elitist Strategy）、排序系统（ASrank,Rank-Based Version of Ant System）、蚁群系统（ACS,Ant Colony System）和最大最小蚂蚁系统（MMAS,Max-Min Ant System）[10-13]。这些系统是蚁群算法不断完善的产物，其中MMAS在大量的应用中体现出较好的品质。

本文提出了一种PTN网络路由调度方法，该方法将路由调度的约束转换成统一的必经节点约束，结合改进后的Dijkstra算法和带变异策略的最大最小蚂蚁算法（VMMAS,Variation Max-Min Ant System）来计算PTN最佳路由。其中，改进后的Dijkstra算法在时间复杂度和空间复杂度都有了一定的提升；VMMAS算法是基于信息素混合更新和变异更新策略对最大最小蚂蚁算法进行优化得到，通过自适应调整参数和变异策略实现收敛速度与计算精确度的平衡。

1 路由调度约束转换

PTN路由调度属于典型的带约束最短路径优化，随着约束数量的增加，计算复杂度和计算时长将会呈现指数级增长。本文将路由调度中的4类主要业务约束统一转换为必经点约束，从而将带约束路由调度问题转换成节点遍历问题求解。

1.1 业务约束转换

目前PTN路由调度业务约束主要有4类：必须经过某些节点、必须经过某些路由、禁止通过某些节点以及禁止通过某些路由，约束由操作员在计算路由前根据规划要求输入。通过调整网络参数，可以将这4类业务约束统一转换为必经点约束。

具体约束转换方法为：将业务约束中必须经过路由的两端节点设置为必经点，且必须经过的路由设置为两端节点的最短路由；将业务约束中禁止通过节点和禁止通过路由设置为节点不可达，如图1所示。通过这种方法，4类主要业务约束都可以统一转换成必经点约束。

图1 通过设置节点不可达实现禁止类型约束

1.2 获取网络中所有必经点

必经点的获取方法为：网络图经过约束转换后，把禁止节点和禁止链路进行剔除，结合必经节点和必经链路的起、止节点，即可得出PTN网络中的所有必经点。

如图2所示，节点A、Z分别是所求路由的起始网元和目标网元，对于禁止通过的节点X，删除网络中所有目标节点为X的链路；对于禁止通过的链路L，删除网络中的链路L；对于必须经过的链路L，令L的起点M1和终点M2为必经节点，同时设置必经点M1和M2的最短路由为L，并且不计算M1到其他节点的最短路由，即L为必经点M1到M2的最短且唯一路由。

图2 提取网络中的必经点

2 最短路径算法改进

最优路由依赖于必经点间的路径权重之和，经转换后的目标网络图能得到路由中所有的必经点。通过最短路径算法，计算目标网络中的路由起止点和各必经点任意两点之间的最短路径。

2.1 Dijkstra算法优化

传统单源最短路径的Dijkstra算法可以找到从起始点到其他点的最短路径信息，在地图障碍物较多的情况下，其搜索时间较长[14]。因此，本文提出从时间复杂度和空间复杂度这两方面对Dijkstra算法进行优化改进，以降低计算时间和空间资源。

（1）时间复杂度优化

原生Dijkstra算法采用线性搜索，其时间复杂度为O(N2)，其中N为网络节点数量。通过使用二分法搜索代替线性搜索，将时间复杂度由O(N2)下降到O(N*log(N))，如4万个节点的搜索平均比较次数由2万次下降到15次，可有效地降低搜索时间。除此以外，实际网络中存在多条相同长度的路由，在选择下一步要处理的节点时，相同长度的路由可以并行处理，使用并行计算代替串行计算，从而提高计算效率。

（2）空间复杂度优化

原生Dijkstra算法使用邻接矩阵存储路径权值，邻接矩阵较为简便，也容易理解。但是，它的空间复杂度始终为O(N2)，所以在稀疏图的情况下会导致空间的大量浪费[15]。可通过使用HashMap+List代替邻接矩阵存储路由关系，以减少存储空间。比如，某生产网络中有4万个节点、7万条链路，若使用邻接矩阵，需要16亿个存储单元，而使用HashMap+Li

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

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