王锐

（中国移动通信集团广东有限公司，广东 广州 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]。……