摘要：本文介绍网络优化的数学模型和几种算法，阐述了图论的基本概念，介绍最小生成树的Kruskal算法、最短路径算法和最大流量算法，根据电力通信网的结构，论述了优化的必要性，优化的目标。对于电力通信传输网，提出了受限最短路径优先（CSPF）算法的具体步骤， 并详细提出了用于CSPF计算的约束条件：链路约束和路径约束。采用本算法对电力通信网络的骨干网络进行计算机模拟，取得了有实际意义的结果。
关键词：网络优化；最小生成树；最短路径算法；最大流量算法；CSPF算法
一、网络优化的目的、原则
网络优化可以提高资源的利用率，提高安全稳定性以及运行维护人员的维护效率。 网络优化原则包括：保证原有网络的投资；掌握并分析现有网络的情况和业务发展趋势；采用可量化的优化方案、采用多种措施保障网络优化工程的实施。
二、网络优化涉及的内容
电力通信传输网优化涉及的主要参数有网络容量、网元配置、网管配置。
三、网络优化的概要过程
网络优化的过程主要包括准备优化、评估网络、分析并提供网络优化方案、实施优化：
1 准备优化需要做如下工作
确认网络优化的需求；初步规划网络优化的范围、对象和日期；确认参与网络优化的人员；收集网络的文档和网络的运行状况；准备网络优化工具。
2 评估网络包括以下内容
确认网络优化的目标、范围、对象、时间；确认网络优化方案的评估方法及细则；进行现场数据采集和测试；进行数据分析、评分和问题分析；发布评估总结和优化建议。
3 分析并提供网络优化方案包括以下内容
确定优化站点、对象等；提供各项目的优化方案，包括：运行环境优化方案；组网优化方案、业务优化方案、网络自愈与保护优化方案、网络时钟优化方案；光网络备件优化方案、网络安全管理优化方案、网络ECC通信优化方案、网络其他优化和建议方案；提供网络优化总体分析与方案；提供方案所需的验证和试验总结、确定网络优化方案；购买设备、材料、相关服务项目；确认到货的设备、材料等。
4实施优化包括以下内容：
确认网络优化的实施方案；确认网络优化的实施人员及工具、车辆、备件、应急方案；实施网络优化；检查、验证优化后的网络；通报网络优化的实施过程和结果；总结与跟踪网络优化项目。
四、网络优化的数学模型和几种算法
电力通信传输网分为A网和B网，覆盖所有110kV及以上变电站和基层单位大楼，业务包括调度自动化（EMS/SCADA）、安稳信息、继电保护等生产实时信息和生产管理信息。在生产运行中出现以下问题：（1）随着电力专业集约化管理的实施，城区和二区二市网融合成一张网，业务流向由分布集中到全部集中到地调。如何对网络保护方式和结构进行优化，提高网络的安全可靠性。（2）在网络结构上，由于各种因数，导致传输网网络建设不均衡，网络流量不足。资源利用率低，网络的分层、分类不清。（3）在网络业务上，通道使用缺少整体规划，没有详细规划，致使电路调配日益复杂，局端上下电路难度增加，交叉矩阵浪费严重且使用不均衡，电路运行的清晰度低，查找业务、调整业务困难，定位时间长。
对此，需要进行传输网络优化，使网络结构更清晰、支持业务更丰富、运营维护更方便、电路生产更高效、扩容升级更平滑。由于当前传输网络的优化大多停留在人工预测、简单计算和布点上，造成工作量大，预测不准确、科学。
1 数学模型
1.1定义
1.1.1网络：用G表示一个网络，则这个网络由一组节点V={v1，v2， … ，Vn}和这组节点（两个节点的联结组）组成的边E={eij}构成，表示为G=（V，E）。
1.1.2权重：在一个网络图中，边上表示连接强度的权值，称为权重，表示为wij。
1.1.3树：网络图G=（V，E）中，如相邻的两个端点间都有一条路相连，但是又不存在任何回路即任两点间有且只有一条路径，这样的图称为树T。
1.1.4生成树：对于网络图G，如树T是G的子图且包含图G的所有的节点，则称T是图G的生成树（Spanning Tree）. 根据G的不同，生成树可以有多有少。
1.1.5最小生成树：对于一个给定的网络图G中，其生成树中有一个总容量最小的。
1.2 算法
求生成树，可以有两种思路：一种是从一个边开始，通过搜索比较，寻找下一个边。称为选边法，一种在全图中，逐渐减去成环的边，称为破圈法。
期刊文章分类查询,尽在期刊图书馆
1.2.1求最小生成树，有Kruskal算法，Prim算法。Kruskal算法如下
给定网络图G=（V，E），每条边e的权w（e）≥0.将G的边按权的大小排序为e1，e2， …em，使W（e1）≤w（e2） ≤ …≤w（em）.
1.2.2 最短路径算法
从起始点到其它各点的最短路径，可以利用最小生成树法求得。具体有以下算法Dijkstras算法。
如果节点vs到vt的最短路径总是沿着某一特定的路径先到达节点 vi，然后再沿边到达节点vj，则这一特定路径肯定也是节点vs到节点vi的最短路径。
1.2.3 最大流量算法
在有向网络图中，每个边上实际通过的信息量或物理量，我们定义为流量，定义为：fij。
以上两条表明：某一边上的实际流量不能超过该边的容量。对于任意中间节点，流入该节点的流量之和等于流出该节点的流量之和。
2 优化模型
实际的通信网络具有相当多的约束条件，除了考虑网络的容量外，如要考虑网络建设费用，节点间光路由的长短，节点的跳数和高低阶业务的不同。
并结合IP路由算法如OSPF算法，考虑SDH环网保护（SNCP和MS-SPRING等）。所有这些都是在多种约束条件下的网络优化。
2.1网络分层
对于实际网络，网络组成包括管道层、物理层（光缆、纤芯）、DWDM、SDH层。通过每层间的对应关系，建立层间映射模型。
2.2 SDH分层
对于SDH层，有核心层、汇聚层和接入层。有2种模型，一种是对每一层作为一个独立网络图进行计算，这种不能对全网起到有效的优化。另一种对不同层的节点赋予不同的权重，并反映到节点和边的计算中。在子网内部采用MS-SPRING，MSP，SNCP等选路。
2.3高低阶属性
对于一条E1电路，在途经每个节点时，是否下低阶关系到网络业务的调配、定位等关系，必须对本节点赋予不同的属性。
2.4受限最短路径优先（CSPF）算法
在通信网络中，使用Dijkstra和Bellman-Ford算法计算最短路径是很有效的，但如果要求将约束条件引入优化问题时，算法会变的十分复杂。约束最短路径优先（Constrained SPF）算法属于启发式算法，它是一种改进的最短路径约束算法，在网络中主要用来完成流量工程和快速的重路由。
2.5 用于CSPF计算的约束条件
通常约束条件分为两类：链路约束和路径约束。
2.5.1 链路约束
链路约束是指一条路径上链路的使用限制，即光链路的属性特征。
2.5.2 路径约束
路径约束是指在选定路径上性能度量标准值的加性或乘性组合的
界限。
五、小结
网络优化设计时遇到的一个难点是大量网络数据的收集、处理。由于数据量大，人工处理比较难，采用软件处理也存在网管数据格式和优化软件格式的转化问题。
通过以上分析，数学模型和优化软件是非常有用的，可以大大提高网络优化的科学性，减轻工作量。但是，实际网络环境是非常复杂的，优化工具不能完全代替人去思考和设计，因此在利用这些工具时，关键要了解原理和设计、优化思想。同时，数据输入时要力求准确，否则，结果不但没有参考价值，反而会误导。本文首次应用约束最短路径优先（Constrained SPF）算法在电力通信网络优化上，并对本功能进行了仿真测试，实际结果表明，优化模型及算法在通信网络规划和建设中起着科学设计、辅助决策的良好作用。
参考文献：
[1]雷功炎. 数学模型讲义[M]. 北京：北京大学出版社，1999.
[2]高随祥. 图论与网络流理论[M]. 北京：高等教育出版社，2009.
[3]刘桂真. 图与网络――优化决策的图论方法. 上海：上海科学技术出版社，2006.
[4]梁雄健，孙青华，张静，杨旭. 通信网规划理论和务实[M]. 北京：通信网规划理论与务实，2006
论文作者:孙冬蕾
论文发表刊物:《电力设备》2018年第25期
论文发表时间:2019/2/13
标签：网络论文; 算法论文; 节点论文; 路径论文; 最短论文; 方案论文; 业务论文; 《电力设备》2018年第25期论文;