孙媛媛，卢利锋，周 静，胡紫巍，翟明岳，刘国军

（1.华北电力大学电气与电子工程学院，北京 102206； 2.全球能源互联网研究院，北京 102211）

一种基于ACO的光网络RWA优化方法及应用

孙媛媛1，卢利锋2，周 静2，胡紫巍2，翟明岳1，刘国军2

（1.华北电力大学电气与电子工程学院，北京 102206； 2.全球能源互联网研究院，北京 102211）

针对光传输网络中由于光纤和波长资源有限而导致的RWA（路由波长分配）问题，基于ACO（蚁群算法）框架提出了一种优化算法SS-ACO（服务选择ACO），在蚁群探索方案空间过程中增加了业务选择机制，改进了蚂蚁转移概率和信息素更新方法，有利于提高算法的寻优能力，能有效降低网络业务阻塞率。结合网格网络和实际网络进行了仿真实现。

蚁群算法；信息素；阻塞率；路由波长分配；电力通信网

0 引 言

WDM（波分复用）技术以不同的波长作为传输信道来传递信息，因此波长资源是WDM光网络中最重要的资源［1-2］。由于RWA（路由波长分配）问题本身是NP-C问题，网络规模越大，算法的复杂度越高。在工程上，一般将RWA问题分为路由子问题和波长子问题串行解决，由于这类方法一般采用最短路径寻路，采用首次命中方式分配波长，可能出现多条光通道占用同一链路，导致网络需要的波长数较多，在网络波长资源有限的情况下阻塞率较高。因此，有必要研究新的启发式算法以期得到更优化的规划方案。

本文基于ACO（蚁群算法）的启发式思想，结合分层图方法，提出一种优化算法SS-ACO（服务选择ACO），增加了业务选择机制，引入业务信息素，改进了蚂蚁选路和信息素更新环节，能有效提高算法的寻优能力，降低网络业务阻塞率。然后，结合网格网络和某省电力骨干通信网络进行仿真实现，将算法结果与现有算法进行了比较。

1 SS-ACO数学模型

给定网络G=（V，E），其中，V=｛v1，…，v|V|｝为网络节点集合，E=｛e1，…，e|E|｝为节点间的光纤链路集合。每条光纤能够使用|Λ|个不同波长进行并行无干扰传输，Λ=｛λ1，…，λ|Λ|｝。对于任一节点v，有邻节点预备集N｛n1，…｝，其每一个元素与v直接相邻。网络链路e上分布的信息素τqe表示q的路由包含链路e的可能性。

设需求空间Q=｛q1，…，q|Q|｝，其中，qi=（si，di）（si、di∈V，si≠di）表示节点si到di的连接请求。对于同一源-宿节点对，可能有多个连接请求，这种情况对应于实际网络中带宽需求较大的业务。对于任一请求q，有相应信息素τq和启发式信息ηq，其中，τq表示最佳方案能应答q的可能性，ηq与q的最短路径长度成反比。

A=｛a1，…，a|A|｝为解决方案，其中ai=（rj，λk），包括为请求q=（s，d）∈Q分配的波长λk（λk∈Λ）和路由其中，vj1，…，vjn∈V，ej0，…，ejn∈E。

此外，本文遵循以下原则:（1）对于光通路（sn→dn），在所分配路由包含的每条链路上都使用相同波长λk传递信息。这是由于在中继节点变换波长需要实现光/电/光转换，成本过高。（2）对于经过同一链路的不同光通道，必须采用不同波长承载信息。即对于∀e∈E，∀λ∈Λ，不存在e∈ri，e∈rj，且ai=（ri，λ），aj=（rj，λ）∈A。

本文中RWA的优化目标是使解决方案A能满足尽量多的业务需求。

2 SS-ACO描述

基于ACO框架，利用蚂蚁群体觅食过程中的正反馈机制，派出多只蚂蚁独立探索方案空间，经过多次迭代得到最佳方案。本文所提SS-ACO的框架如图1所示。

图1 SS-ACO框架

SS-ACO的主要步骤如下:

步骤1:初始化。初始化是设置ACO计算参数、方案空间中初始信息素和启发式信息的重要过程，关系到算法最终解决方案性能的优劣。ACO计算参数包括阻塞迭代次数Niter、蚂蚁数Nants、信息素蒸发速率ρ和信息素边界比γ等。

步骤2:派出新蚂蚁ai搜索方案空间。

步骤3:选择可用波长，其原则是使用一个波长响应尽可能多的请求。即将波长资源进行编号后，按一定顺序依次选择，判断当前波长不能再满足任一业务时，再启用新波长。

步骤4:基于选定的波长图，蚂蚁ai按照业务选择机制从需求空间选取请求q。

步骤5:为连接请求q寻路，按照蚁群寻路规则在步骤3选定的波长图上寻找最优路径。

步骤6:判断网络波长资源是否用尽:否，则转至步骤3；是，则得到蚂蚁ai的解决方案Ai。

步骤7:判断是否所有蚂蚁都找到解决方案:否，则转至步骤2；是，则从蚁群方案中选出本次迭代所得最佳迭代方案Aib。

步骤8:当|Aib|＞|Abs|时，令Abs←Aib，其中Abs为准最佳方案。按照信息素更新规则更新全局信息素和局部信息素。

步骤9:判断是否满足算法终止条件，即准最佳方案Abs的性能在之后Niter次迭代不再提高。若不满足，则转至步骤2。

为避免算法陷入局部最优而使最终方案质量不够高，重启算法Nreset次。

2.1 业务选择机制

业务选择机制，即如何从需求集合中选取要响应的请求。首先，计算每个业务在当前波长图上的最短路由长度l，移除不可应答请求，为可应答请求设置启发式信息ηq，其与l成反比，即

然后，以概率pq从可响应请求中随机选取一个请求。pq定义为

式中，α、β分别为信息素和启发式信息的计算权重；γ为0～1的实数；Ni为当前的迭代次数。在算法运行初期，pq几乎与τq和ηq无关，随机选取请求进行应答，即蚂蚁能更自由地探索方案空间，利于获得更优质的解决方案。随着迭代次数的增加，pq受信息素和启发式信息的影响增大，即选择其他蚂蚁选过的或路由较短的请求的可能性更大，利于方案收敛。

2.2 蚂蚁寻路规则

当为请求q=（s，d）选定路由时，由源节点s起，从当前节点的动态候选点集N′中迭代地选择下一跳，直到到达目的节点d。一般地，对于节点u，其邻节点预备集是与u相邻且能到达d的节点集合。对于N′中的任一点v，计算其到d的最短路径长度lr，设置链路（u，v）上的启发式信息ηv，u与最短路径长度lr成反比。此处，当候选点就是目的节点时，lr为0，由于lr作分母，故将lr作加1处理，即该式为

以概率pr来选取候选节点作为下一跳，直至到达宿节点d。pr定义为

式中，τq（u，v）为链路（u，v）的信息素浓度。在算法运行初期，Ni/Niter较小，蚂蚁以近乎等概率选取下一跳节点，利于蚂蚁探索方案空间。随着算法的运行，蚂蚁会优先选靠近目的节点的节点及频繁访问的边缘附近的节点，利于方案收敛。

2.3 信息素更新

信息素蒸发是整个启发式算法的关键，它保证了随机得到的坏方案不会对之后的迭代造成持续影响。当蚁群方案建立完成后，令全局信息素以固定速率ρ蒸发:

在得到迭代准最佳方案Aib和准最佳方案Abs后，随机选取Aib或Abs为A。选择Aib的概率越大，越有利于探索方案空间，相反则更利于算法收敛。令:

从而使所得方案更好，该方案中各元素的信息素浓度越高，越有利于方案收敛。最后，按照MAX-MIN（最大-最小）蚂蚁系统的要求将信息素浓度限制在［τmin，τmax］范围内。

3 算法仿真分析

3.1 网格网络仿真实现

以4×4的网格网络为仿真网络，需求空间由计算机随机生成，将本文的SS-ACO与一般ACO（Tra-ACO）和SPMU（最短路径最多使用）算法方案进行比较，如图2所示。在一般ACO中，蚂蚁以相同概率从需求空间随机选取请求，蚂蚁寻路时的转移概率仅与网络信息素分布和启发式信息相关，当一只蚂蚁建立了蚂蚁方案后，便更新局部信息素。

由仿真结果可知:当需求空间大小一定时，随着网络波长数的增加，解决方案能响应更多的连接请求；当网络波长数一定时，需求空间越大，解决方案能支持的业务需求越多。且当波长资源一定，需求空间越大，SS-ACO相对于其他两种算法的优势越明显，这是由于SS-ACO引入了业务选择机制，在算法运行后期，会先应答路径较短的业务。如果先为路径较长的请求分配了网络资源，可能导致拒绝更多与其包含重复链路的请求。由于信息素更新是在建立蚁群方案之后，各蚂蚁探索方案空间不受其他蚂蚁信息素的影响，因此蚁群探索方案的过程是并行的，可避免过早进入局部最优。

图2 3种算法的性能比较（4×4网格网络）

3.2 实际网络仿真实现

以某省电力通信网省干OTN（光传输网）主平面为例，其拓扑如图3所示。全网采用40× 10 Gbit/s带宽，网络结构分为骨干层和接入层。骨干层节点为省公司和变电站，接入层节点为地市公司，共配置节点设备30套，光纤链路47条。

图3 某省电力通信网省干OTN主平面拓扑图

由于电力通信网是电网生产、管理及营销的专用通信网，该网络主要承载的业务包括调度数据网业务、数据通信网业务和省干A网。根据《电力通信网规划设计技术导则》、《“十三五”期间各类变电站和办公场所典型带宽预测模型》（信通计划［2015］82）的方法与要求［3-5］，结合该省业务网络特点，预测该网络的主要业务带宽需求如表1所示。

表1 某省骨干网主要业务带宽需求预测

为评价网络的业务发展适应性，引入LLR（链路负载率）指标，其定义如下:LLR=（Boccupy/B）× 100%，式中，Boccupy为被占用的波长；B为链路总带宽。LLR是评价链路负载是否过重的指标，其中，空载链路、轻载链路、较重载链路和重载链路分别对应LLR=0、0＜LLR≤30%、30＜LLR≤60%和LLR＞60%［6］。重载链路数比重越大，网络适应性越差。

基于上述网络与需求空间，考虑业务发展需求和阶段性部署特点，我们将各节点出口带宽以逐年递增的方式进行测算，即需求空间大小分别增长为140、280、420、560、840和1 120。下面利用SSACO优化算法对某省干OTN主平面的业务通道层进行模拟仿真，算法结果对比如图4所示。

图4 3种算法性能比较（实际网络）

比较算法方案可知，对于特定网络和可预测的需求空间，随着需求空间的增长，SS-ACO优化算法的解决方案一直优于其他两种算法。根据SS-ACO仿真结果，目前全网有70条业务需求都可应答，解决方案仅使用了20个波长。全网共有47×40条链路，方案链路利用率为12.3%。可见，对于目前的网络业务需求，该网络资源较为充裕。但是由于网络资源一定，随着业务需求的逐步增长，必定会有业务无法得到响应，网络阻塞率变高。

另外，考虑网络容灾、可靠性等因素，计算了当需求空间分别为140和280时，网络中负载较重的链路的分布情况，如图5所示。

图5 重载链路分布情况

图中，虚线链路表示重载链路（LLR＞60%），加粗链路为较重载链路（30＜LLR≤60%），其他为轻载链路（0＜LLR≤30%）。可见，重载链路多为单根光缆链路，而对于链路（FX变-ZJ公司），虽然承载的业务数最多，但由于其采用双光缆配置，降低了负载压力。这是由于，在业务层各地市公司分别到省公司、备调公司的业务均呈汇聚型，而传输层主要呈现环网结构，因此网络负载不均衡。对于重载链路，其波长占用率较高，随着网络需求的增加，这些链路将成为“瓶颈”链路，因此应对该链路及时升级，对该链路进行双光缆配置，或在相关站点（如省公司1和SG变）间铺设直通光缆，并对中间路由器制定负载均衡策略，以缓解网络流量压力局部过大，使该网络由环网结构向网状网结构发展与演进。

4 结束语

本文基于ACO框架，提出了一种有业务选择机制的RWA优化算法，尤其在需求空间较大的情景中，能够有效提高网络的业务承载能力。通过改进蚂蚁转移概率，使蚂蚁在算法初期能自由地探索方案空间，算法后期又利于方案收敛。此外，本文的算法能延伸为解决多并发业务的DRWA（动态RWA）问题。结合网格网络和某省电力通信省干OTN进行了算法的仿真实现，并评价了该省干网络对承载业务发展的适应性。

［1］刘爱波，陆月明，纪越峰.智能光网络路由及其关键技术分析［J］.光网络，2004，（8）:29-31.

［2］孙海金，朱娜，周乃富.基于蚁群系统的分布式RWA算法研究［J］.光通信研究，2005，（2）:30-34.

［3］周静，熊素琴，苏斌，等.一种电力通信网络运行质量量化评估方法及应用［J］.电网技术，2012，36（9）: 168-172.

［4］刘贵荣，周静，赵子岩，等.电力通信网SDH环容量均衡优化算法研究［J］.电信科学，2010，（12）:140-144.

［5］周静，吕天光，陈希，等.省级电力调度数据网带宽分析与容量规划研究［J］.电网技术，2012，36（5）:173-177.

［6］周静，陈希.电力通信网规划仿真技术研究及其典型应用［J］.电力系统通信，2012，33（242）:25-29.

An Optimization Method of Optical Network RWA Based on ACO and Its Application

SUN Yuan-yuan1，LU Li-feng2，ZHOU Jing2，HU Zi-wei2，ZHAI Ming-yue1，LIU Guo-jun2
（1.School of Electrical&Electronic Engineering，North China Electric Power University，Beijing 102206，China；2.Global Energy Internet Research Institute，Beijing 102211，China）

Focusing on the RWA problem in optical transmission network，we proposed a RWA optimization algorithm based on ant colony algorithm framework.The way of choosing a request from requests zone is introduced，which would improve optimization ability of the algorithm.In addition，the way of updating pheromone and searching routes in ACO algorithm are also improved.This method can effectively reduce the network traffic congestion.Finally，we conduct a simulation to demonstrate the proposed method in a grid network and a province electric power communication network.

ACO；pheromone；congestion rate；RWA；electric power communication network

TN915

A

1005-8788（2016）05-0019-04

10.13756/j.gtxyj.2016.05.006

2016-05-18

国家电网公司2015年科技项目（SGRIXTKJ［2015］241）

孙媛媛（1991-），女，河北邢台人。硕士研究生，主要从事电力通信网络规划的研究。