高速铁路光传送网络链路故障定位的研究

刘天阳,王仲凯,孙 强

(北京交通大学 电子信息工程学院，北京 100044)

近年来我国高速铁路取得了快速发展，铁路光传送网络是高速铁路安全运行的基础，光传送网络承载着保证列车安全运行的大量业务，如：同步及时间分配系统业务、应急通信系统业务、列车调度指挥控制、列车运行状态监测、通信网管、电力电牵监控、动力及环境监测、信号业务、GSM-R业务、调度通信等。高速铁路骨干层网络主要采用OTN技术进行环形组网，随着光传送网络技术的发展，单波传输速率可以达到40 Gbit/s，并且逐步向100、400 Gbit/s过渡[1]。一根光纤可以承载数以百计的波长，即使是单根光纤的中断也会带来大量的信息丢失，将会严重影响网络中的业务传输。为了保证光传送网络中的业务安全传输，必须在网络故障发生后能够快速、准确地定位出故障发生的位置，并采取相应的故障恢复措施，以避免网络故障所带来的损失。因此，对于光传送网络链路故障定位的研究具有非常重要的意义。

实现光传送网络的快速故障定位需要一个有效的故障监测机制。其中监测迹m-trail是实现光传送网络故障定位的一种物理层监测结构，其基本思想是把网络中的故障定位问题转化为对网络中的链路进行二进制的编码问题。依据二进制编码机制可知，少量的二进制bits可以产生大量不同的编码，因此少量的m-trail即可实现网络的快速、精确故障定位。

为了实现在大型的网络中快速分配m-trail，相对于ILP(整数线性规划)模型，有学者提出了一种启发式的RCA+RCS算法以及MTA(监测迹分配算法)，启发式算法RCA+RCS可以在较短的时间内找到定位故障的方案，但是RCA+RCS算法具有随机性。更重要的是该算法有可能会出现监测迹不相连的问题，因此在大型的网络中会增加监测迹的数量。由于MTA算法在选择下一条链路时会固定选择最大权重的链路，这样会存在局部最优的问题。本文提出一种基于RWS+MTA的m-trail分配算法，采用一个概率模型在选择下一条链路时可以扩大搜索的空间，经过有限次迭代，可以选出较优的m-trail分配方案。

1 故障定位现状

一根光纤可以承载数以百计的波长，单波承载的带宽可以达到10 GB或者100 GB。因此，一根光纤的中断将会造成大量的数据丢失，为了最大限度减少数据的丢失，能够快速定位并恢复故障链路非常重要。链路故障检测和定位可以在不同的协议层[2-3]。 比如：OSPF(开放路径最短优先协议)，IS-IS(中间系统到中间系统路由协议)。一般来说，通过上层协议需要花费较长的时间，远高于光域要求的50 ms的恢复时间[4]。为实现快速链路故障定位，会优先选择光域[5-7]，光域故障检测与定位原理如图1所示。每一个监测器与控制平面中的管理器直接相连，若网络中出现了故障，相应的监测器会发出告警信息，并把告警信息传递给控制平面中的管理器。管理器收到告警信息后会根据相应的告警信息定位出故障发生的位置，与此同时，管理器会对路径进行重路由，从而绕过发生故障的链路，以保证网络的正常运行[8]。

图1 光域故障检测与定位原理

对于光传送网络的故障检测与定位，文献[9-13]进行了广泛的研究。在光传送网络中故障的检测与定位是根据网络中监测器发出的告警信息来实现的。在大型网络中为了能够实现快速、准确的故障定位，必须把大量冗余告警降低到最低限度，这样才能减少告警的处理时间。因此，合理的分配监测器对于实现快速、准确的故障定位非常重要。

1.1 监测环故障定位

假设一次最多只有一条链路发生故障，当网络中的某条链路出现故障时，监测环中的监测波长信号就会中断，此时，相应的监测器就会检测到中断的信号从而发出告警信息，进而可以根据监测器产生的告警码进行故障定位。告警码的形式为{am-1,…，aj,…,a1,a0}，其中aj=1表示监测环中的第cj个监测器产生了告警，相应的aj=0表示该监测器没有产生告警。每一条链路的告警码都存入故障告警码表中，在故障发生后可以通过收集监测器发出的故障告警信息，并查找故障告警码表来实现快速、准确的故障定位。图2(a)为m-cycle结构图，图2(b)显示的是由3个监测环{c2,c1,c0}组成的一个链路故障监测方法。表1为该监测环中所有链路对应的告警码，其中Link代表网络中的链路，D代表故障告警码的十进制表示形式。如果链路(0，1)出现了故障，在监测环c1,c0中的监测器就会产生告警，对应的告警码为[0，1，1]。在理想的情况下，每一条链路应该拥有唯一的故障告警码。但是链路(3，4)与链路(2，4)的故障告警码相同，如果链路(3，4)或者链路(2，4)发生故障，由表1可以看出，链路(3，4)与链路(2，4)在发生故障时有相同的告警码，因此，根据监测器产生的告警码不能判定链路(3，4)或者链路(2，4)是否出现故障。

图2 m-cycle结构图及监测环分布

链路c2c1c0D(0,1)0113(0,2)0011(0,3)0102(1,2)1015(1,3)1106(2,4)1004(3,4)1004

1.2 监测迹故障定位

尽管监测环可以很大程度上减少监测器的数量，但是由于监测环有时不能唯一确定链路是否出现故障，并且监测链路固定在一个环中，不具有可扩展性。因此，为了能够在减少监测器数量的同时可以唯一确定链路是否出现故障，文献[14]提出了m-trail(监测迹)的概念。m-trail打破了m-cycle监测通路必须是环的限制，监测路径可以是任意的形状，也可以经过一个节点一次或者多次。

m-trail故障定位方法由一系列监测迹来监测链路是否出现故障，如果网络中某条链路出现了故障，经过该链路的监测迹中的监测器就会产生告警。根据故障告警码表可以看出，通过合理的分配监测迹可以唯一确定故障链路。

图3所示为监测迹的分布，网络m-trail集合为T={t0,t1,t2},共有3条路径，t0的路径为4-2-0-1-2，t1的路径为4-3-1-2-0，t2的路径为0-3-1-0-2。表2为所对应的故障告警码,可以看出能够唯一确定某条链路是否出现故障。

图3 监测迹分布

链路t2t1t0D(0,1)1015(0,2)1117(0,3)1004(1,2)0113(1,3)1106(2,4)0011(3,4)0102

m-trail故障定位实际上是在一定的网络拓扑结构和监测结构的限制条件下，将故障定位的问题转化为对网络中的链路进行二进制编码的问题，可以实现网络监测资源的最优化配置。

2 监测迹研究现状

目前m-trail的设计方法都是为了降低监测代价的同时能够快速、准确地实现故障的定位。在m-trail的设计方法中，采用如下方式估算该方案所消耗的监测代价：监测代价 = 监测器的成本 + 监测带宽的成本=γ×监测器的个数 + 监测波长的总数[14]。

可以通过调整γ的数值来控制监测器的个数与监测波长总数之间的比重，从而实现m-trail分配算法在监测器成本与监测带宽成本之间的折中。如何分配m-trail在保证准确、快速定位出故障的同时需要更少的监测代价是目前研究的方向。

目前对于m-trail的故障定位主要是针对于单链路，其中m-trail的设计方法主要有：整数线性规划方法、RCA+RCS、启发式监测迹分配算法。

2.1 整数线性规划设计方法

文献[14]提出了在光传送网络中基于m-trail的故障定位方法，并设计了分配m-trail的ILP模型以实现对网络中监测资源的优化配置。该设计方法的优势在于能够给出m-trail分配的最优解，但是ILP是以最小化监测代价为目标，通过设置多个约束条件以及参数，然后改变各个参数的值，进而找到最优解。

基于ILP的m-trail设计问题在理论上属于NP-hard的问题，所以m-trail的设计过程非常复杂，尤其是在大型网络中，由于使用ILP方法求得最优解所需要的时间较长，往往找不到最优解甚至有可能求不出解。因此，利用ILP方法设计m-trail在实际应用中很难实施。

2.2 RCA+RCS设计方法

为了能够实现快速分配m-trail，文献[15]提出了一种启发式的RCA+RCS算法[15]，相对于ILP(整数线性规划)模型，可以在较短时间内找到m-trail的分配方案。RCA+RCS算法的基本思想是,首先为网络中的每一条链路随机分配一个唯一的二进制识别码，然后在分配识别码的基础上对每一条m-trail进行调整，从而得到正确的m-trail结构。

虽然RCA+RCS算法可以得到有效的监测结构，但是由于其具有随机性，在RCS过程中可能产生多个分离的m-trail，因此在分配m-trail时有可能会使m-trail的数目增多，从而增加m-trail以及监测器的数量。因此，RCA+RCS算法的性能难以得到保证，为了得到一个好的方案，有时需要重复运行该算法以碰巧可以得到一个性能比较好的起点，然后从多个最终得到的运行结果中挑选出最好的。这样不但会使得运行时间变长，而且很难保证会获得好的结果。

2.3 MTA设计方法

MTA算法[16]与RCA+RCS算法的思想相反，RCA+RCS首先为每一条链路分配一个唯一的编码，然后对m-trail的结构进行调整。而MTA算法的基本思想是先将所有链路放入一个集合中，然后添加一条m-trail把集合分为2个集合，再添加一条m-trail把集合分为4个集合，以此类推不断增加m-trail直到集合数等于所有链路数，并且所有链路都被该m-trail经过为止。图4为MTA算法的流程，其中集合AS0为网络中所有的链路的集合。

图4 MTA算法流程

3 RWS+MTA设计方法

虽然MTA算法在设计m-trail时可以有效减少监测器的数量，从而降低监测代价。但是由于MTA算法在选择下一条链路时会固定选择最大权重的链路，这样会存在局部最优的问题。为了避免MTA算法中出现局部最优的状况，引入一种轮盘赌选择RWS(Roulette Wheel Selection)算法。

3.1 RWS+MTA算法流程

由于RWS算法使用一个概率模型在选择下一条链路时扩大了搜索空间，可以避免局部最优情况的出现。因此采用RWS+MTA算法来设计m-trail，通过有限次的迭代可以从中选择出较优的m-trail分配方案，图5为RWS+MTA算法流程。

图5 RWS+MTA算法流程

步骤1初始化m=0，min_cost=+∞，min_ACT=∅。其中，m为迭代次数；min_cost为最小的监测代价；min_ACT为对应的故障告警码表。

步骤2初始化链路集合AS0，AS0为没有被监测迹经过的链路集合；当一次迭代完成后，AS0必须为空集，因为AS0中的每一条链路都唯一确定。

步骤3增加一条m-trail。

步骤3.1寻找监测迹tj的集合pj，tj为添加的第j条监测迹，pj为包含监测迹tj的集合。

步骤3.1.3为节点nk周围的每一个相连的链路赋予权重。在拓扑G(V,E)-pj中以节点的度数与链路成本倒数的乘积作为节点nk的每个邻接链路l的权重，设置为wl，设Q1，Q2为常数，如果l∈AS0，则wl×Q1→wl也就是说该链路没有被m-trail经过;如果有其他链路l在pj中，则wl/Q2→wl，也就是说该链路被另外的m-trail经过了；如果所有链路都可以被唯一确定，则wl→0。

步骤4更新集合，并获取本轮的告警码表。

步骤5是否所有的链路都可以被唯一确定，并且AS0=∅，如果为假转至步骤3，如果为真则转至步骤6。

步骤6计算监测代价。

步骤7判断监测代价是否小于min_cost，如果为真转至步骤8，如果为假转至步骤9。

步骤8令min_cost等于步骤7得出的最小监测代价。

步骤9m=m+1。

步骤10如果m

3.2 m-trail 设计

表3为铁路骨干层二号环故障告警码表，若要对网络中的每一条链路都能唯一确定其是否出现了故障，需要{t7,t6,t5,t4,t3,t2,t1,t0}8条监测迹,如图6所示。由表3可以看出每一条链路都对应唯一的故障告警码。

表3 骨干层二号环故障告警码

图6 骨干层二号环监测迹分布

通过运行RWS+MTA算法得到了以上8条监测迹，监测迹的分配如图6所示。

3.3 算法仿真与结果分析

为了验证该算法，对随机生成的100个网络拓扑进行仿真。由于RCA+RCS算法具有随机性，因此，选取随机生成的100个网络拓扑中的每一个拓扑运行RCA+RCS算法100次，然后分别选择这100次中效果最好的，同时运用RWS+MTA算法进行10次迭代。因为MTA算法每一次选择下一条链路时都是固定的，因此MTA算法只需要运行一次。

图7为不同链路数所对应的监测代价。采用RWS+MTA算法设计m-trail所需要的监测代价最小。随着链路数的增多，RCA+RCS算法对应的监测代价明显增加，这是由于RCA+RWS算法的随机性引起的。由于RWS+MTA算法可以进行一定次数的迭代，从而在生成m-trail选择下一条链路时扩大了搜索空间，进而得到较优的m-trail分配方式。

图7 不同链路数对应的监测代价

图8 不同链路数所需监测器的数目

图9为不同节点数所需要的监测器数量。随着节点数的增加，在节点数大于40后，RCA+RCS算法所需要的监测器数量明显增多，这是由RCA+RCS算法的随机性引起的。MTA与RWS+MTA算法随着节点数目的增加变化不大，但是RWS+MTA可以通过不断迭代进而找到较优的m-trail分配方法，因此需要的监测器数目较MTA少。

图9 不同节点数需要的监测器的数目

由于网络拓扑的随机性，选取平均节点度数为2与4的网络进行仿真。由图10可以看出,随着节点数的增多，RWS+MTA算法相对于其他两种算法所需要的监测代价最低，并且随着节点度数的减少，监测代价也随之降低。这是因为随着网络连通性降低，需要监测的链路数变少，因此监测代价也随之减少。

图10 不同度数的节点对应的监测代价

图11为不同节点数所需要的监测器数量。可以看出随着节点数的增多，RWS+MTA算法所需要的监测器的数目最少，另外随着节点度数的降低，所需要的监测器数目反而增多，这是因为随着网络连通度的降低，会对m-trail设置的灵活性有一定限制，这样就会增加m-trail数量，进而需要更多的监测器。

图11 不同度数节点数目对应的监测器数目

图12为运用RWS+MTA算法对铁路骨干层五大环设计m-trail时不同迭代次数所对应的监测代价，可以看出在经过一定次数的迭代后，监测代价趋于平稳。因此，采用RWS+MTA算法可以利用较少的迭代次数以获得比较优的m-trail分配。

图12 迭代次数对应的监测代价

4 结束语

本文研究光传送网中的链路故障定位方法，由于m-trail可以在光域实现快速、准确的链路故障定位，满足光传送网络50 ms的保护恢复时间，在故障发生时可以快速倒换至备用链路，以避免链路故障带来的损失。本文提出一种基于RWS+MTA的m-trail分配算法，不仅可以避免RCA+RCS算法出现不相连的监测迹使监测迹数目增多的问题，并且可以避免MTA算法在设计m-trail时由于固定选择权重最大的链路而带来局部最优问题。运用该算法设计了骨干层二号环的m-trail分配方案，并通过仿真验证，结果表明该算法不仅可以获得较优的监测迹分配，而且可以减少所需的监测代价。