10605500376：电力通信传输网络的优化模型探讨_0讲解

1、电力通信传输网络的优化模型探讨衷宇清，张斌，张岚（广州供电局通信公司，广东 广州 510620）摘要 ：本文介绍网络优化的数学模型和几种算法，阐述了图论的基本概念，介绍最小生成树的 Kruskal 算法、最短路径 算法和最大流量算法，根据广州电力通信网的结构，论述了优化的必要性，优化的目标。对于电力通信传输网，提出了受限最短路径优先（CSPF）算法的具体步骤，并详细提出了用于 CSPF计算的约束条件：链路约束和路径约束。采用本算法对广州电力通信网络的骨干网络进行计算机模拟，取得了有实际意义的结果。关键词 ：网络优化，最小生成树，最短路径算法，最大流量算法， CSPF 算法，Discuss of

2、 power supplycommunicationnetwork optimization modelZhongyuqing(Guangzhou Power Supply Bureau Communication Company， guangdong guangzh 510620)Abs tract: This article describes the mathematical model of network optimization algorithm and several described the basic concepts of graph theory on the Kru

3、skal 、 minimum spanning tree algorithm， the shortest path algorithm and the maximum flow algorithm， according to the structure of Guangzhou power supply communication network， discussed the need for optimization ， the goal of optimization. TO power supply communication network ， present constrained

4、Shortest Path First (CSPF) algorithm for the specific steps and details for the calculation of theconstraints CSPF: linkconstraints and path constraints. We carryout computer simulation Using the algorithm for power supply communication network inGuangzhou backbone network， and achieved meaningful r

5、esults.Key wor d: Network optimization， minimum spanning tree ，shortest path algorithm， the maximum flow algorithm， CSPF algorithm0 引言广州电力通信传输网分为 A网和B网，覆盖所有110kV及以上变电站和基层单位大楼， 站点数 量超过238个。A网包括10G核心层、2.5G骨干层，622M汇聚层和155M接入层，B网包括2.5G骨干层， 622M汇聚层和155M接入层。业务包括调度自动化（EMS/SCAD）、安稳信息、继电保护等生产实时信息和生产管理信息。在生产运

6、行中出现以下问题（ 1 ）随着电力专业集约化管理的实施，城区和二区二市（番禺、花都、增城、从化）5 张网融合成一 张网， 业务流向由分布集中到全部集中到地调。 如何对网络保护方式和结构进行优化， 提高网络的安全 可靠性。(2) 在网络结构上，由于各种因数，导致广州供电局传输网网络建设不均衡，网络流量不足。资源利 用率低，网络的分层、分类不清。(3) 在网络业务上，通道使用缺少整体规划，没有详细规划VC4, VC12致使电路调配日益复杂，局端上下电路难度增加，交叉矩阵浪费严重且使用不均衡， 电路运行的清晰度低，查找业务、 调整业务困 难，定位时间长。对此，需要进行传输网络优化，使网络结构更清晰、

7、支持业务更丰富、运营维护更方便、电路生 产更高效、 扩容升级更平滑。由于当前传输网络的优化大多停留在人工预测、简单计算和布点上，造成工作量大，预测不准确、科学。笔者结合“广州供电局网络优化技项目”，根据广州电力通信网络的实际运行情况，在选择数学模型的基础上，提出优化模型和算法。1 数学模型1.1 定义1.1.1网络:用G表示一个网络，则这个网络由一组节点 V=Vi,V2,，Vn和这组节点(两个节点 的联结组)组成的边 E=ej构成，表示为 G=(V,E)。1.1.2 权重：在一个网络图中，边上表示连接强度的权值，称为权重，表示为wij。1.1.3 无向图和有向图：如一图中所有的边没有方向，则该

8、图称为无向图，如一图中所有的边都 有方向，则该图称为有向图。网络中计算拓扑时，使用无向图，计算流量时，使用有向图。1.1.4 容量：在有向图中，边上表示非负的权重，称为容量，表示为cij。1.1.5树：网络图G=(V,E)中，如相邻的两个端点间都有一条路相连，但是又不存在任何回路即 任两点间有且只有一条路径，这样的图称为树 T。1.1.6生成树：对于网络图 G,如树T是G的子图且包含图 G的所有的节点，则称 T是图G的 生成树( Spanning Tree) . 根据 G 的不同，生成树可以有多有少。1.1.7 最小生成树：对于一个给定的网络图 G 中，其生成树中有一个总容量最小的。1.2 算

9、法求生成树， 可以有两种思路： 一种是从一个边开始， 通过搜索比较， 寻找下一个边。 称为选边法， 一种在全图中，逐渐减去成环的边，称为破圈法。1.2.1 求最小生成树，有 Kruskal 算法， Prim 算法。 Kruskal 算法如下给定网络图G=(V,E),每条边e的权w(e)0将G的边按权的大小排序为 印心，em,使W(e“w w(e2) 三 w(em).第1步：选T第2步：如选好e 则考虑ei+1.如T+ ei+1含圈，则考虑e+2。否则，令边e+1 T。第 3 步：重复第 2 步直到无边可选为止。这时选出的 T 即为图 G 的最小树。1.2.2 最短路径算法从起始点到其它各点的最

10、短路径， 可以利用最小生成树法求得。 具体有以下算法 Dijkstras 算法。如果节点Vs到Vt的最短路径总是沿着某一特定的路径先到达节点Vi，然后再沿边到达节点Vj,则这一特定路径肯定也是节点Vs到节点Vi的最短路径。可用如下迭代公式完成：tt-1d (vs,vj)=mi nd (vs,vj)+w ij若对于所有节点Vj V,均满足dt(vs,vj)= dt-1 (Vs,Vj)则停止迭代，并通过反向追溯寻找Vs到Vj的最短路径。其中Wij表示节点Vi到节点Vj的直接距离，若节点Vi到节点Vj无直接边相连，则Wij = modt-1 (Vs,Vj)表示迭代t步后，节点Vi到节点Vj的最短路径

11、，当 t=0时，d(Vs,Vj)=O1.2.3 最大流量算法在有向网络图中，每个边上实际通过的信息量或物理量，我们定义为流量，定义为：fij o需满足以下条件(1)容量限定条件：ow fij Cj o(2) 平衡条件：若i-s,t，贝y刀fij_刀fki=0以上两条表明：某一边上的实际流量不能超过该边的容量。对于任意中间节点，流入该节点的流 量之和等于流出该节点的流量之和。最大流定理：f是网络G的最大流当且仅 G中不存在关于f的增广路。增广路的概念：从出发节点到汇聚点的路中，有的边的方向是和从发点到收点一致的，这种有向 边称为前向边，有的边的方向与此相反，我们称它为后向变。若一条路每条前向边上

12、的流量fjCij，而每条后向边的流量fij 0,则称它为一条增广路。在增广路的前向边上增加流量，在后向边上减少流量使条件(1)和(2)仍然成立，则得到一个值更大的流，一直重复前面的过程，则可以找到网络的最大流。图1：获得一条增广路由。在图1中，表示一个网络 G=(V,E)，源点为vs,汇聚点为W,边上的两个数字分别表示流量和 容量其中Vs- V1 -V2- V4-Vt是一条增广路。通过标号法进行计算，增加流量后。得到网络最大流图。图2:已得到最大流的图无向边可以分解成两个方向相反的容量相等的有向边。2优化模型实际的通信网络具有相当多的约束条件，除了考虑网络的容量外，如要考虑网络建设费用，节 点

13、间光路由的长短，节点的跳数和高低阶业务的不同。并结合IP路由算法如 OSPF算法，考虑 SDH环网保护（SNCP和MS-SPRING 等）。所有这些都是在 多种约束条件下的网络优化。笔者在具体分析电力通信网络的基础上，提出电力通信网的专有属性，并将约束条件引入最短路径算法。2.1网络分层对于实际网络，网络组成包括管道层、物理层（光缆、纤芯）、DWDM、SDH层。通过每层间的对应关系，建立层间映射模型。2.2 SDH分层对于SDH层，有核心层、汇聚层和接入层。有2种模型，一种是对每一层作为一个独立网络图进行计算，这种不能对全网起到有效的优化。另一种对不同层的节点赋予不同的权重，并反映到节点和边的

14、计算中。在子网内部采用 MS-SPRING ，MSP，SNCP等选路。2.3高低阶属性对于一条E1电路，在途经每个节点时，是否下低阶关系到网络业务的调配、定位等关系，必须对 本节点赋予不同的属性。于一条新开业务，如从番禺的一个110KV站开通到地调，需要经过接入层、汇聚层和核心层，通过以上模型，可以采用最短路径算法，得到一个理论上的优化解。实际中，经常采用CSPF进行选路优化。2.4 受限最短路径优先 (CSPF) 算法在通信网络中， 使用 Dijkstra 和 Bellman-Ford 算法计算最短路径是很有效的， 但如果要求将约束条 件引入优化问题时，算法会变的十分复杂。约束最短路径优先(

15、Co nstrai ned SPF)算法属于启发式算法，它是一种改进的最短路径约束算法，在网络中主要用来完成流量工程和快速的重路由。对于 CSPF 算法有几个输入变量：首先是配置的流量隧道特性(带宽，资源类所属关系，优先级，恢复性等 );其次是与这些特性相关的资源状况;第三是网络的拓扑信息。CSPF 的主要计算步骤如下。(1) CSPF 会排除掉那些链路信息不全的链路，然后进行链路所属的资源类的检查，检查之后，如果 发现有无效的资源所属关系的链路，就把这些链路排除掉 ;(2) 根据删减后的拓扑计算最短距离的路径。2.5 用于CSPF计算的约束条件通常约束条件分为两类：链路约束和路径约束。2.5

16、.1 链路约束链路约束是指一条路径上链路的使用限制，即光链路的属性特征。 单条成员(TE)链路可以包含如下属性 (约束条件 )。(1) 最大带宽：该参数描述了链路的容量;(2) 未预留带宽：该参数描述了链路上还没有被预留的带宽;(3) 最大、最小连接带宽：这两个参数决定了链路中可以分配给某条连接的最大和最小带宽。(4) 链路保护类型：指链路的保护能力;(5) SRLG :共享风险链路组(SRLG)，用于表示和链路相关的管道、光缆、纤芯的关系。；(6) 接口交叉能力：包括交叉能力和交换能力细节信息。2.5.2 路径约束路径约束是指在选定路径上性能度量标准值的加性或乘性组合的界限。(1) 路径跳数

17、限制:到达目的地路径的最大跳数；(2) 松散显示路由:确定给出路径必须经过的一些中间链路或中间节点；(3) 保护恢复机制:当传输链路发生故障时采取哪种备份路径恢复链路。3、应用本项目的开展是结合广州供电局科技项目 传输网络优化及业务流向模型研究 同步进行的。 我们与相关科研单位合作，根据算法思路编写相应的软件，并对我局通信网数据进行模拟。3.1 网络拓扑模拟按照广州供电局10G网络拓扑图作为规划，带宽为10G(64*VC4)，其中承载的业务情况假设如下：1 )北郊到地调和备调开 6VC44VC4;2）罗冲、茶山、增城、赤沙、番禺局到地调和备调分别开3）变电一部、变电二部到地调和备调分别开3VC

18、44）其他站点到地调和备调分别开2VC45）每个站之间预留1个VC4罗冲MAINSTM-1636.25北郊MAINSTM-16 |20.1MAINSTM-16茶山北片10G50km环网变电二部6.33MA梅花路MAIN4.3广州地调MAINSTM-16天河maSTM棠下40km五仙门南片10G环网訂备调EXT6428km28.1611.3km15.5kmN百召开元东南片10G环网I StMi6 I变电一部3.513STM-16EXT6427.54芳村 番禺局19km36+10广南赤沙1Q0km注：虚线表示可以建设的路由，实现为当前已运行的路由。图1 传输网络拓扑仿真示意图3.2网络优化仿真条件

19、给定以下约束条件1）给定限制直接到地调和备调的链路使用带宽不超过50%（32 VC4）2）其他链路不超过75% （48 VC4）的情况下进行计算的，由软件自动进行计算，保证每条链路不超过阈值。3）设置链路使用带宽的阈值以及节点容量使用带宽的阈值，对现网，如果超过阈值，会以红色进行警示。4）查看究竟是哪些业务经过超过阈值的链路，可以选择对部分的业务进行重路由优化，在优化时选 择链路阈值，保证优化后的结果不超过阈值。3.3网络优化仿真结果通过网络优化仿真结果，共增加 5条链路，其中1）原有链路上新增链路：地调-棠下，备调到地调，变电二部到梅花路。2）在新的光缆路由上新增：增城-北郊，备调到广南，而

20、罗涌-变电一部、 开元-黄埔局-广州地调、芳村-赤沙、瑞宝-梅花路则没有新增链路， 详见图所示。辽注：0：已有光缆，但本期不用增加电路1：表示有一条路由，若原始为0,则为新增电路；若原始为1,则表示不增加2:表示有两条路由，在原有一条上新增一条路由。图2传输网络拓扑仿真结果4、小结通过计算机模拟，并结合现状及业务分析，初步已达到以下目标。1|、对网络拓扑提出优化建议。共增加5 条链路。2、保护与恢复策略优化，提高安全可靠性。3、对网络扩容提出优化建议。4、对业务的分层、分类，碎片整理、时隙连续化、小业务归并提出优化建议。5、网络资源利用率最优化，负载均衡最优化，业务的路由优化。6、两区两市集约化后，两区两市传输A、B网与城区传输 A、B网进行融合调整，提出网络调整方案。网络优化设计时遇到的一个难点是大量网络数据的收集、处理。由于数据量大，人工处理比较难，