基于最短路径敏感度的光网络关键链路识别

田云飞，彭玲艳，程紫运，韩东升，靳攀润

(1.国网甘肃省电力公司 经济技术研究院，兰州 730050； 2.华北电力大学 电气与电子工程学院，河北 保定 071003)

0 引 言

在电力光网络中，对业务产生较大影响的链路称为关键链路。关键链路的工作状态对通信业务具有重要影响。为了客观准确地识别电力光网络的关键链路，有必要对链路关键性的量化模型及其识别算法开展深入研究。关键链路识别方法的研究成果主要包括：基于复杂网络理论的全局和局部效能测度[1]；考虑业务需求和链路流量的测度[2]；基于节点对连通性的测度[3]；基于介中心度的测度[4]；基于加权自然连通度的测度[5]；文献[6]给出了4种提高算法效率的加速技术；文献[7-9]采用多种测度综合的方法，保证识别结果更符合实际；文献[10]给出了光缆长度服从一般极值分布的结论，并用来估计光缆和光放大器数量，甚至用来选择光调制方式[11]；文献[12]和[13]分别提出了两种最短路径长度的概率分布函数，用来间接得到网络规划与设计所需要的基础数据。

在实际工程中，关键链路识别结果用于光网络容量设计[7]和网络运行质量评估[14]。同时，关键链路识别对网络规划设计和运行管理具有辅助决策作用。然而，现有研究成果存在效率低和针对性不强的问题，很少考虑“最小路径时延”和“最高路径可靠性”这两种电力光网络重点关注的测度。鉴于此，本文将以最短路径敏感度为基础，综合考虑路径跳数、时延和可靠性因素，来实现高效、灵活的电力光网络关键链路识别。

1 最短路径敏感度

电力光网络可用无向、无环、有权图表示，即G=(V,E,W)，式中：V为节点集，|V|=m；E为链路集，|E|=n；W为链路权重集，|W|=n。现实网络中的光传输设备等价为节点，光缆等价为链路。链路权重可以有多种不同的物理含义。若链路权重设为1，则表示信息传输跳数为1；若链路权重为光缆长度，则表示实际的物理距离。同理，链路权重可以灵活地表示传输时延、不可靠性和传输容量等网络性能参数。由于电力通信网更加关注实时性和可靠性，所以电力光网络采用时延和可靠性作为链路权重更符合实际。

设图G中的节点s和t之间存在多条路径，并构成路径集合，记为P(s,t)，s,t∈V，其中|P|=m(m-1)/2。任意一条路径都是链路的集合，其长度等于路径所包含链路的权重之和。第k条路径的长度为

式中：wr(Pk(s,t))为路径Pk(s,t)所包含第r条链路的权重；LPk(s,t)为路径Pk(s,t)的长度。

如若任何两节点间仅选择一条最短路径，那么，可以用全部最短路径长度的平均值表示网络效能，即

根据这一定义，Q值越大，网络效能越差。若网络节点均为理想的，那么，Q值受网络结构和链路权重影响。在网络结构保持不变的情况下，链路权重增加，会导致Q值增大。这意味着，链路状态的恶化，会使网络效能变差。把Q值随链路权重的变化率定义为最短路径敏感度。第d条链路的最短路径敏感度表达式为

式中：wd为第d条链路的权重；W0为初始链路权向量。将式(2)带入式(3)，并化简，得到

对式(4)规范化后可得：

2 关键链路识别方法

2.1 确定链路权重

由前述内容可知，链路权重决定了最短路径的选择结果，决定关键链路的排序。根据电力光网络的需求，本文考虑3种链路权重场景，分别是：路径跳数最少、路径时延最小和路径可靠性最高。

(1) 路径跳数最少

设路径权重wr=1，利用最短路径法得到基于跳数的最短路径，路径长度可实现跳数最少的目标。最短路径敏感度可根据式(5)计算得到。

(2) 路径时延最小

设光缆信号的传输时延为5 μs/km，光网络设备的信号处理时延为50 μs。在不考虑数据分组传输时延的条件下，链路权重可表示为

式中：Lr为链路长度，单位为km；wr为第r条链路时延与端节点时延之和，单位为μs。

(3) 路径可靠性最高

设光缆每千米的不可靠性为5×10-7，光网络设备的不可靠性为5×10-5，链路权重可表示为

因为电力光网络的可靠性非常高，所以链路和节点的串联不可靠性近似等于二者之和，路径的整体不可靠性等于各环节不可靠性之和。这种运算规律与最短路径算法相一致，由此得到的最短路径就是最可靠路径。

2.2 计算最短路径敏感度

最短路径敏感度的计算过程分两步实现。首先，在网络拓扑结构和链路权重已知的条件下，利用最短路径法计算所有节点对之间的最短路径长度；然后，选择链路d，并将其权重赋值为恶化阈值，重新计算最短路径长度。两次计算得到两组长度为Np的数据；最后，根据两组数据的差判断得到链路d的长度Nd，再根据式(5)计算最短路径敏感度。

2.3 链路关键性指标排序

算法按照路径跳数最少、时延最小和可靠性最高等3种最短路径目标，分别得到链路关键性指标，采用升序排序可得到关键链路的顺序。为便于描述，用HOP表示最少跳数，DEL表示最短时延，REL表示最可靠。

2.4 算法描述

链路识别方法流程如图1所示。算法首先输入网络拓扑结构、链路长度、时延参数和可靠性参数；然后，生成关联矩阵和3种不同的链路权值，两次重复计算最短路径长度得到最短路径敏感度；最后，将敏感度指标按升序排列得到链路排序，从而达到关键链路识别的目的。

图1 链路识别方法流程图

算法的关键环节是求解网络的最短路径。本文直接调用Matlab R2014a软件的graphallshortestpaths(G)函数，实现对中规模电力光网络的最短路径计算。

3 算 例

3.1 算例说明

为了验证所提方法的可行性和正确性，本文选择一个省级电力主干光网络作为实例，对其进行关键链路识别，并对结果进行分析。实例网络的相关参数如表1所示。

表1 实例网络的相关参数

表1中的m、n和L等参数通过对实例网络的统计得到，Do和De由参考文献[15]整理得到，Fo和Fe来源于实例网络年度运行分析报告的统计数据；HT和T是根据实例网络规模和链路长度分布情况，假设得到的。

实例网络拓扑如图2所示。图中粗线部分表示识别出的关键链路示例。

图2 实例网络拓扑

3.2 结果分析

(1) 最关键链路识别

在已知网络拓扑结构和光链路物理长度的条件下，本文基于HOP、DEL和REL 3类路径目标，分别进行关键链路识别。算法调用函数graphallshortestpaths(b,'Directed',false)，计算得到163组最短路径敏感度。前10个最关键链路的排序情况如表2所示。

表2 前10最关键链路排序

由表2可知，实例网络的最关键链路是编号为66的链路，其次是编号为53、77、163、21和75的链路。链路权重采用的测度不同，关键链路识别结果略有差别。HOP、DEL和REL 3种识别结果中排序前10的链路，绝大多数相同，如表2中加粗字体所示。但有些链路的排序发生了变化，如编号为18、40、41、48和49等的链路。这说明利用不同测度会得到不同识别结果。

(2) 最不关键链路识别

同理，根据163组最短路径敏感度，可得到10个最不关键链路的排序情况，如表3所示。

表3 10个最不关键链路排序

由表3可知，实例网络的最不关键链路是编号为68、56、147、142和29的链路。HOP、DEL和REL 3种不同的识别方法所得结果绝大多数相同，如表3中加粗字体所示。但部分链路的排序结果不尽相同，如编号为134、90、155、126和140的链路。

图2标出了相应链路的关键性信息。红色和粉色粗线最为关键链路，绿色粗线为最不关键的链路。另外，从网络的物理结构上看，识别出的关键链路属于网络骨干链路。

(3) 均值与方差

为了直观表示各条链路的关键性，可视化3种关键链路识别方法得到的结果，如图3所示。

图3 3种关键链路识别结果

由图可知，本文采用的3种识别方法所得结果绝大多数一致，个别链路存在差异。例如，链路40在HOP和REL方法中关键性排序在前10，而在DEL方法中排序为最不关键。链路41、48和49在HOP和REL方法中关键性排序落后，但在DEL方法中关键性排序超前。对这一现象的放大图如图4所示。

图4 特殊链路关键性排序不一致情况

根据最短路径敏感度分析结果，实例网络全局的关键链路识别结果如表4所示。

表4 敏感度指标的分布参数

由表可知，最大值约为0.5，最小值为0，平均值约为0.05。这意味着，当一条最关键链路出现失效时，将有近50%的最短路径受到影响，而不关键链路失效对最短路径几乎没有影响。各类链路失效对网络路径的平均影响程度约为5%。标准差表征链路关键性差异化程度，其值越小，关键性越均衡，网络效能越好。

3.3 讨论

(1) 不同识别方法的必要性

本文以最短路径敏感度为基本网络效能测度对关键链路进行了识别。同时，本文又扩展到了基于HOP、DEL和REL等3种识别方法。实例验证表明，这3种方法都能有效识别关键链路，且链路排序整体一致。利用Spearman相关系数检验，HOP_DEL为0.655，HOP_REL为0.986，DEL_REL为0.693。可见，HOP和REL两种方法几乎作用相同。

在特殊情况下，3种识别方法会得到不同结果。例如，链路40在HOP和REL方法中关键性非常高，但在DEL方法中却最低。这种高步不一致的原因可以参考图5加以分析。节点30和43之间存在两条路径，一条是链路40直接连接，另一条是41、48和49号3条链路串联，其总长度低于链路40。这导致了识别结果不一致。

图5 部分实际网络

总体看来，综合采用3种不同的识别方法是必要的，可发现更多的网络特征，提供更加丰富的参考信息。

(2) 综合考虑多种链路信息

链路的关键性不仅取决于网络拓扑结构和链路长度，还与其他多种因素有关。以电力光网络为例，光缆的类型主要有光纤复合架空地线(Optical Power Ground Wire, OPGW)、全介质自承式(All Dielectric Self Supporting, ADSS)光缆和普通光缆3种，其中OPGW可靠性和安全性最高。如果识别出的关键光缆是电压等级较高的OPGW，那么电力通信网络就能为业务质量提供保障。本文识别出的绝大多数最关键链路都是750 kV OPGW，这符合工程实际要求。另外，连接高电压等级变电站和省市调度中心的链路应该具有较高的关键性，因为这些站点通常需要较大的传输容量，而且承载较重要的业务，所以节点信息需要融合到关键链路识别算法中去。为了保证高可靠性，电力光网络对于没有实现环形组网的链路通常采用双光缆冗余配置，光缆冗余的相关信息也应该融合到关键链路识别中去。

4 结束语

本文针对电力光网络关键链路识别问题，给出了基于最短路径敏感度的3种有效识别关键链路的方法。研究结果表明，本文所提方法可以从跳数最少、时延最短和可靠性最高等3个方面对电力光网络的关键链路进行有效识别，并具有实现简单和一致性好等特点。研究结果能够为电力通信网的规划设计和运行维护提供参考。下一步的研究工作重点将放在融合电力通信网多源异构信息，综合实现关键链路识别。