光网络抗自然灾害能力评估范文

1WCGM算法

WCGM算法表明，满足以下4个约束条件的环形切割中一定有网络图的最差环形切割：①与边的交点为顶点且圆心在边所在的直线上；②分别与两条边相切，两切点为不同点，且其中一点为顶点；③分别与两条边相切，两切点都为顶点；④分别与两条边相切，两切点为不同点。WCGM算法步骤如下：步骤1：输入网络信息及环形切割范围r。步骤2：对网络中所有边进行不重复的两两组合，计算每一个组合，找出满足约束条件的环形切割。步骤3：计算每个环形切割对网络的影响测度值。步骤4：找出使测度值最大的环形切割，得到最差环形切割集。根据算法约束条件，在给定环形切割半径r的情况下，如果两条边上任意两点的距离均大于2r，那么这两条边所组成的组合不能计算出有效的环形切割圆心，这种组合为无效组合。WCGM算法并没有对这一情况加以筛选，影响了执行效率。

2改进的WCGM算法

2.1网络图的预处理根据算法特性，引入了对网络图分区域的预处理方法。在进行约束条件计算前，把网络图分为4个小区域，并分配边的所属区域，只对区域内的边进行组合，减小组合对数的同时保证所有可能的有效组合都被包括在内。以网络图中顶点的横纵坐标极值作为区域的外边界，形成区域A，并把区域A划分成相同大小的4个小区域a1、a2、a3和a4，划分后的区域如图1(a)所示在确定环形切割半径为r的情况下，这种分区域方法不会漏掉图中有效组合。由图1（a）可以看出，四个区域在中间横竖两个宽为2r的长方形部分中互相重叠，保证网络图中任何距离小于2r的两点都属于同一区域。这样，两边属于同一区域成为两边组成有效组合的必要条件，即这种分区方法不会漏掉任何一种有效组合。

2.2约束条件计算的优化算法中4条约束条件在程序中分别用以下的方式进行计算。方式1：以某条边上的顶点为圆心，r为半径，得到圆方程。与边所在的直线方程组成方程组，求解方程组得交点坐标。取不在边上的点为所求的圆心。方式2：以某条边上的顶点为圆心，r为半径，得到圆方程。求与另一条边所在直线距离为r的两个直线方程。圆方程分别与两个直线方程联立求解，最后取实数坐标点为所求的圆心。方式3：以某条边上的顶点为圆心，r为半径；以另一条边上的顶点为圆心，r为半径。两个圆方程组成方程组，联立求交点。取其中实数坐标点为所求圆心。方式4：求分别与两条边所在直线距离为r的直线方程。对求得的4个方程两两联立得出直线交点。方式1和方式4的计算不受无效组合的影响。对于方式2，由几何原理可知，给定一点a和直线l，a不在l上，存在半径为r的圆，此圆与直线l相切且a在圆上的充要条件是a到直线l的距离小于等于2r。同样，对于方式3，给定两点，存在半径为r的圆，使得两点都在圆上的充要条件为两点距离小于等于2r。在用方式2和方式3计算之前，用两点和点与直线间的距离公式判定参数是否满足条件，若满足则计算，不满足则跳过计算。边组合是否有效的判定是基于距离公式的简单计算，用距离公式计算代替部分组合中方式2和方式3的多元方程组计算可以减少程序运行时的计算量。

2.3算法优化效果用MATLAB7.1编写仿真程序，程序1基于2.2节所述的WCGM算法步骤进行编写；程序2基于改进的WCGM算法编写，即将算法步骤2改为分别计算四个小区域内的边组合，并在方式2和方式3的计算中加入距离判定机制。分别用程序1和程序2对不同规模的网络进行计算，计算时间如图2所示。从图2可以看出，程序2在计算时间上有较大的优势，且在网络规模变大的过程中程序2时间的增幅要小于程序1，证明优化后的算法计算效率更高，对大规模网络计算的适应性更好。

3计算结果

用改进的WCGM算法对某省的实际电力通信光纤网进行计算分析，网络如图3所示。其中节点数为183个，连接数为221条，距离单位均为像素距离。使用网络损失连接数为测度，图3（a）为r=100时的最差环形切割，连接损失数为16。图3（b）中的大环为r=200时的最差环形切割，连接损失数为31。使用网络连通性为测度，最差环形切割出现在灰色圆环位置。仿真结果表明，光网络的脆弱位置与网络的连接状态、光纤连接的地理分布、灾害影响范围和所选取的测度有关。

4结束语

本文对WCGM算法进行了改进，通过对实际网络进行计算，证明优化后的算法执行效率明显提高。通过此方法对实际网络进行评估，找出网络最脆弱的部分并有针对性地对网络连接分布结构进行优化和保护，对提高通信网络的抗灾能力有一定的参考价值。不同类型的光纤连接对不同灾害的承受能力和光纤中承载的不同业务都会影响单个光纤连接在网络中的权重，建议对网络测度进行深入研究，使计算结果更具客观性和工程适用性。

作者：高会生王龙单位：华北电力大学电子与通信工程系