连纪文 卓秀者



电力光纤通信网络优化算法及其应用探讨

连纪文1卓秀者2

1.福建电力调度通信中心 2.福建永福通讯技术开发有限公司

依据电力系统通信业务特点，改进了整数线性规划算法，用于SDH组网优化设计，并开发了相应的软件。最后以福州市区东南部的电力光纤网络为例给出了具体的优化设计方案。

电力 SDH 优化 ILP算法 软件

1 引言

近几年来，随着电网快速发展，电力系统光纤通信网络迅速壮大，已经成为电网生产调度重要支撑手段。由于电力通信网一般都随电网分期分批建设，网络路径及结构等均受电网结构的制约，从而影响了电力光纤通信网络结构合理性和可靠性，因此当光纤通信网络达到一定的规模之后，有必要借助先进的网络优化算法，优化原有的通信网络，从而提高通信网络整体性能水平，满足电网规模不断扩大及现代化管理需求。

本文依据福建电力光纤通信网络的实际情况，将对基于1+1保护的SDH/SONET环形网进行组网优化。它在给定业务需求的情况下，优化容纳所有业务所需要的总成本或者说最小化总成本。具体来说，我们将研究SDH环网上的多线速优化问题,即在一个光缆网络中如何组成多个SDH环，以及低速业务流在环上如何路由的问题。

2 SDH组网优化算法

2.1 狭义组网优化

在电力通信网中，存在大型节点（如地调）间对带宽有着很大的需求。例如，可能要求一条甚至多条 STM-16的线路。但是，还有大量节点之间（相邻节点、集控所和下属站点，地调和其余节点）的网络连接请求只需要一个光纤通道提供的STM-16带宽的一小部分，例如STM-1、10Mbps等，因此光传送网必须能够有效地满足这一类节点的业务需求。解决容量巨大的光纤通道和带宽要求不大而数目众多的节点带宽需求之间矛盾的关键，就是有效地安排节点数据流共享高速的光纤通道。

本文将此问题称为组网优化问题，它是从学术界的业务疏导问题引申而来，或者说其学术术语为业务疏导。借鉴业务疏导的定义，可以将我们要研究的组网优化定义为：将节点之间的低速数据流有效地复用到高速的光纤通道，将高速的光纤通道数据流解复用成为低速数据流，并且使得低速数据流在不同高速光纤通道上进行合理的交换。上述组网优化的定义我们称之为狭义意义上的组网优化。

狭义组网优化，它包含两个子问题：一个是确定逻辑拓扑，另一个是在该逻辑拓扑上路由低速业务流。第一个子问题中，要确定组建多少个光纤通道环，每个光纤通道环的线速以及经过哪些节点。如果在一些节点间有足够的业务容量需要传送，那么应该由这些节点组成一个高线速的环，使这些业务在该环上传送，以获得高线速环运送单位业务时的经济性。另一方面，如果一些节点间的业务量较小，那么它们应该在一个线速较低的环上传送，以减少ADM的成本。为给定低速业务流的网络设计一个支持多线速的多环逻辑拓扑是一个困难的工作。一般来说，在整个网络中始终采用单线速的光纤通道环，能大大减少设计的复杂性，但它会带来成本上的不经济性。我们可以不预先确定每一个环的线速，由优化算法来确定。但为了简化计算复杂度和节省优化时间，这里由网络设计或运营者依据业务容量的需求来估计这些环网的线速大致在什么范围，如需要预估这些环的线速在OC-12还是OC-48的量级，然后再由优化设计程序来确定能否找到优化解，即能否在指定的几个环中路由这些业务，并最小化ADM设备的成本。同时确定要组成几个环，每个环的线速，每个环要经过哪些节点，业务在这些环上如何路由，哪些业务需要在环间交换等。

狭义组网优化问题可以形式化为一个整数线性规划问题，并采用商业的整数规划软件来求解。

2.2 优化算法中的输入参数和优化变量

对低速业务流进行组网优化这个问题可以简单归纳如下所述。首先，我们给出组网优化问题的输入条件：

（1） N：有低速业务流要传送的节点数目，我们将在这些节点间组建光纤通道环；

（3）M：一个非常大的整数；

输出结果或者说要得到的目标变量是：

从输出变量可以看出我们的优化要确定组成几个环，各环的线速，以及每个环由哪些节点组成，业务在这些环上如何路由，也可以推导出需要在环间进行交换的业务及其路由等。由于大量的光缆已经铺设，网络的费用主要反映在网络设备上，在SDH环网中采用的设备主要是SDH的分插设备ADM，因此最小化ADM的成本就优化了网络的建设成本。

2.3 优化算法的ILP公式

在组网优化设计方案中，我们以最小化容纳所有低速业务流所需要的ADM设备成本为目标，利用ILP公式对组网优化问题进行求解。它可以表示为：

所需满足的约束条件为：

2.3.1业务需求约束

2.3.2业务的环约束

业务在一环离开（或者说发出），一定要在该环上到达（或者说终止），离开和到达的节点在同一环上可以不是同一节点。即使业务为环间业务，它也要先从一环到达双环共有的节点，到达（终止）于此环的该节点，再在该节点从另一环离开（重新发出），故有此约束。

2.3.3环容量约束

它表示任意节点发出的，经过任意节点离开的业务量之和要小于该环的业务容量。它约束了一个环上路由的业务总量不超过该环的业务容量，一个环的业务容量用该环所用ADM设备的线速来表示。

2.3.4节点约束

2.3.5环上最大节点约束

2.3.6环上已知节点约束

2.3.7ADM成本约束

组网优化结果中ADM成本的总和，它等于形成的多环网中所有ADM成本的总和。

2.3.8整数约束

通过业务疏导，能依据给定的业务矩阵，获得最小的ADM成本，疏导的结果同时给出对应的逻辑拓扑和业务在逻辑拓扑上的路由结果。获得的最优化性能值是性能的上限（对ADM成本而言该值为下界），它可以用于衡量现有网络性能与最优网络性能之间的差异。依据最优逻辑拓扑，可以调整以获得想要的逻辑拓扑。

3 组网优化软件实现及数值结果

3.1 组网优化的软件实现

3.1.1参数录入

(1)录入需要组网的节点

录入的16个节点如表1所示。

表1 组网节点表

(2)录入需要路由的业务

录入需要进行组网优化的低速业务矩阵，组网优化根据各节点间业务量的多少来进行组网设计。

(3)线速及成本设置

图1 环线速、成本及最大节点数录入

根据电力系统业务特点，环1~5的线速分别设为622Mbps、622Mbps、2500Mbps、0Mbps、0 Mbps，即后两个环用户可以指定不用，前三个环分别为OC-12环、OC-12环和OC-48环。假定OC-12环所用ADM的成本为3，OC-48的成本为9，这是基于高线速环所用ADM的成本高于低线速环，但其传送单位业务的成本应低于低线速环。同时指定了同一环上允许的最大节点个数为8，以满足福建电力系统继电保护通道转接次数要求。

(4)环上节点指定

指定某个环一定要经过某个节点，以适应实际情况的需要。如指定了环1要包含节点“东台”和“江田”，环2也要包含节点“东台”和“江田”，而环3一定要包含节点“地调”。

3.1.2组网优化求解

优化软件将对整数线性规划算法进行求解，并把最近的求解结果显示在状态窗口中，包括到目前为止的迭代次数，找到的解值（ADM的最小成本），和边界值（下边界，解值不可能小于这个值）。一旦求解结束或者用户中断求解过程，优化状态将被显示在状态窗口中。它反映了到目前为止求解的状态，如找到了“全局最优解”，“可行解”，“局部最优解”，还是“无可行解”，“求解过程失败”等，见图2。

图2 组网优化求解

图2中显示找到了“全局最优解”，总共迭代了572258次，解值为105（即组建这些SDH环网的总成本），边界值也为105。解值等于边界值，也反映了最优解的获得。

3.2 组网优化的数值结果

把输入参数录入后，通过对ILP算法的求解，可以获得相应的数值结果。

3.2.1组建的环数

表2 值

3.2.2环包含节点

表3 环包含节点

图3 优化后SDH网络拓扑图

4 结论

本文依据福建电力光纤通信网络的实际情况，针对基于1+1保护的SDH/SONET环形网进行了组网优化设计。其内容为在给定节点对间要传输的低速业务流的情况下，设计一个多环SDH网络来传输这些业务流，使得所花费的ADM设备成本最小。为此建立了组网优化模型，提出了组网优化设计算法，并针对福州市区东南部的电力光纤网络给出了组网优化设计的数值结果，为其提出了优化方案，为组网设计提供了很好的参考。

[1] 王毅,赵彦灵,向军.SDH环状传输网络中的业务疏导策略研究[J].通信与信息技术,2005,(8):36-42.

[2] 张程,鲍振武,曹俊忠.WDM网络光层保护整数线性规划算法的探讨[J].光纤与电缆及其应用技术,2003,(6):17-20.

[3] 业务疏导在传输网络评估中的应用研究.通信世界网,2007.

[4] 王庆铸,连纪文等.电力系统光纤通信网络优化模型建立与应用,2008.