基于监测树的高速铁路光传送网络故障定位研究

周 洋，孙 强

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

近年来高速铁路发展十分迅速，截至2019年，我国高速铁路运营里程已近三万公里，成为世界上高速铁路运营里程最长、在建规模最大的国家。高速铁路光传送网作为高速铁路的神经中枢，承载着包括铁路列车控制、调度指令等重要信息以及大量的视频监控业务数据，其正常运营是保障铁路安全运行、列车安全行车的基础。而由于波分复用技术的发展，光网络中单根光纤可传输超过100个波长，每个波长可工作在40、100 Gbit/s甚至400 Gbit/s[1]。目前铁路光传送网络骨干层主要使用40×100 Gbit/s OTN系统，汇聚层中铁路局多按照40×10 Gbit/s波分系统设计，网络中所承载业务量的不断上升对网络可靠性提出了更高的要求。一旦网络中出现光纤损坏或折断等故障，期间会产生大量的数据丢失，对业务的传输产生极大影响，轻则造成列车控制系统降级运行，重则造成列车中途停车，严重影响高速铁路系统的正常运行。因此当网络中出现故障时，必须在规定的保护切换时间内完成切换动作，减少因故障对列车行车所带来的负面影响。而故障定位是实施保护切换的基础，快速、准确的故障定位是保证高速铁路光传送网络正常运营的前提。

目前对于光传送网络中的故障定位研究主要集中在链路故障方向。据统计，在较大规模的光传送网中，多链路故障的发生概率在0.1%左右[2]，网络中绝大多数链路故障情况为单链路故障，因此本文主要对网络中单链路故障进行讨论。主流的单链路故障定位方案主要可以分为两类：一是通过网络的上层协议等技术实现对网络故障链路的定位[3-4]。文献[3]通过使用开放路径最短优先协议(Open Shortest Path First, OSPF)实现故障链路的定位。文献[4]通过机器学习的方法，结合网络中的业务流，推断故障链路，实现对可疑链路集合的故障定位。但应用此类方案进行故障定位往往需要较高的定位时间，难以满足高速铁路光传送网络的保护恢复时间要求。同时过多的告警信号很容易引发警告风暴，造成网络质量进一步下降，使得故障定位变得更为复杂。二是通过在物理层光域设置专用的监测器实现链路故障定位[5-6]。该方案的基本思想是通过在光域设置多个信号监测器，对指定信号进行监测。当特定监测器无法收到指定监测信号后，表明该监测信号所经过的链路出现故障，监测器立即向网络管理层发送告警信息。多个监测器的告警信息组成告警序列，利用编码的思想，使得网络中的每条链路都拥有互不相同的告警码。当链路出现故障时，网络管理层根据告警码，便可定位故障链路。该方案虽使用了多个监测器，增加了建设成本，但可以迅速、准确地实现网络中链路故障的定位，适用于对可靠性要求较高的网络。基于该基本思想，研究人员提出了监测环(Monitoring Cycle, M-cycle)[7-8]、监测迹(Monitoring Trail, M-trail)[9-13]和监测树(Monitoring Tree, M-tree)[14-15]多种方案，相对于M-cycle和M-trail，M-tree可减少网络故障定位中的监测成本，同时可以完成故障链路的准确定位。如何设计监测方案，以最低的监测成本实现故障链路的监测是本文研究的重点。

本文基于光域设置监测器以实现故障定位的思想，提出基于度与距离的监测器分配算法(Degree and Distance Based Monitor Allocation, DDMA)设计M-tree监测方案。通过多个随机网络拓扑验证DDMA性能，并利用DDMA为高速铁路骨干层光传送网络设计链路故障监测方案。

1 相关工作

为了实现光域的故障定位，最简单直观的方法便是在每一条链路的两端节点处分别设置激光器与监测器。一旦监测器无法收到激光器所发出的信号，便判定该链路出现故障。然而此方法所需激光器与监测器数量较大，硬件成本过高，难以在实际中应用。为减少激光器与监测器的数量，文献[7-8]研究了监测环M-cycle方案。M-cycle通过在网络中设置多个监测环路，多个激光器发出监测信号，经过不同的环路后回到对应的监测器，方案设计时尽量保证每条链路都被互不相同的一组监测环路经过。当任意一条链路出现故障时，所有经过该链路的监测环都被中断，对应监测环便会在监测器处产生告警信息，网管层收集到告警信息后便可以推断出故障链路。虽然M-cycle可降低网络中的监测器数量，但由于监测信号必须是环路的限制，可能存在无法准确定位故障链路的情况，为克服该缺点，研究人员提出并研究了监测迹M-trail[9-13]概念。相较于M-cycle方案，M-trail中监测信号所经过的链路不必是环路，多个监测信号经过特定路径传送至监测器，方案设计更为灵活。网管层收集所有监测器的告警信息，当某一链路出现故障时，根据告警信息便可定位故障链路。M-trail实现故障链路监测的核心是保证每条链路都被一组互不相同的监测信号经过的前提下，尽量减少监测信号所经过的链路数和监测器的数量，即降低监测代价。文献[9]基于整数线性规划方法设计M-trail，可以得到理论上的最优解，但需要较久的算法运行时间。文献[10]提出RCA+RCS算法设计M-trail，但该算法存在一定随机性，性能表现不稳定。文献[11]提出一种启发式监测器分配算法MTA，可以在较短时间内实现M-trail的设计。文献[12]基于MTA算法，提出轮盘赌选择RWS+MTA算法，进一步降低M-trail方案中所需的监测代价，并通过利用高速铁路光传送网络多个网络拓扑对算法进行仿真验证。文献[13]基于“组”Group的概念设计M-trail，一个组内的链路出现故障时，所需要的保护切换动作相同，因此当链路故障发生时，只需定位故障链路所处的组，保证做出正确的保护切换动作即可。

M-trail方案虽然可以实现链路故障定位，但为了保证每条链路被互不相同的监测信号经过，需要占用多个监测波长以传输监测信号，当网络规模增大时，所占用的监测波长较多，降低了网络容量，方案所需监测代价较高。为减少网络中监测波长的占用，降低监测代价，研究人员提出了监测树M-tree[14-15]概念。M-tree方案利用网络中节点的多播能力，实现只使用一个激光器，同时网络中每条链路只被一个监测信号经过便可完成网络中的链路故障定位。图1(a)所示网络拓扑，在节点4处设置激光器，向节点5处发送监测信号。节点5将监测信号转发至节点1、6，节点1、6收到信号后分别转发至节点2、4和节点2、3，节点3收到由节点6转发的信号后，再次将信号转发至节点1、5，由此实现所有链路的监测信号覆盖。在多个链路的末端设置监测器(图中实心箭头处，即A、B、C、D和E)，便可以实现对整个网络的链路监测。简而言之，M-tree方案等同于将网络的拓扑转换为树形结构，见图1(b)。当监测器无法收到监测信号时，产生告警码‘1’并立即发送至网络管理控制器。例如：当链路(1,2)故障，监测器B会产生告警信息，此时控制器收到告警码为[01000]；当链路(5,6)出现故障，监测器C、D、E会产生告警码[00111]。

图1 M-tree方案示例

链路告警码如表1所示，表中最后一列将一组告警码转换为十进制数字以方便区分。不同链路所对应告警码均不相同，在网络中出现故障时，网络控制器便可根据不同告警码迅速定位故障链路。为实现M-tree的设计，文献[14]基于整数线性规划，利用数学理论对M-tree 进行设计，但由于过多的约束条件导致运算时间长，无法迅速求解。文献[15]提出一种监测器位置搜索(Monitor Location Searching, MLS)启发式算法，在对M-tree进行扩展时，优先选择节点度(即节点所连接的链路数量)大的节点转发监测信号，但部分情况下仍存在监测器浪费的情况。

表1 告警码表格

为方便描述M-tree方案，引入“入链路”和“出链路”概念。当某节点收到监测信号并对其进行转发时，将监测信号传输至该节点的链路定位为入链路，该节点转发监测信号至下一个节点的链路为出链路。例如图1(a)中，当链路(6,3)为入链路时，链路(3,1)和(3,5)便为出链路，但将链路(5,6)看作入链路时，则链路(6,2)和(6,3)便为出链路。“叶子节点”指M-tree中，位于树形结构的末端的节点，例如图1(b)中节点4、2、1、5和2，因M-tree是将原始网络拓扑分解为树形结构，因此某个节点可能多次作为叶子节点。“叶子链路”指M-tree结构中连接叶子节点的链路，叶子链路作为入链路时，不存在任何一条出链路，例如图1(b)中链路(1,4)和(3,1)等。

2 基于度与距离的监测器分配算法

链路故障的准确定位，本质上是为每一条链路分配一个唯一的告警码，故障定位的监测代价由占用监测波长数量与监测器/激光器的数量决定。在M-tree方案中，每条链路只会被经过一次，所占用监测波长为固定值(等于链路数量)，且只需要一个激光器。因此在M-tree方案中，最重要的问题是如何利用最少数量的监测器实现故障链路的监测，以降低监测代价。

2.1 最少监测器数量

在M-tree设计中，若某条入链路所对应出链路的数量小于2时，则该入链路末端应设置监测器，否则无法实现故障链路的准确定位。例如图2中，入链路e1只有一条出链路e2，若A处不设置监测器时，链路e1与链路e2出现故障时，有且仅有监测器B产生告警信号，此时便无法准确定位故障链路。相反，入链路e3处存在多条出链路，当链路e3出现故障时，只有C、D、E三个监测器产生告警信号，此告警码只对应链路e3，因此链路e3处无需设置监测器。因此，若在M-tree方案设计时，可以保证除叶子链路外其他入链路均有多条出链路，此时可使用最少数量的监测器实现链路故障监测。

图2 监测器位置示例

为使得M-tree中监测器数量最低，每一条入链路对应的出链路的数量仍需要讨论。当每一条入链路选择k(k>1)条出链路时，M-tree包含有1+k+k2+…+kn-1条链路，其中n(n≥1)表示M-tree结构中树的深度(设根节点深度为0，如图2所示)。此时仅需在M-tree所有叶子链路处设置监测器，便可以实现对所有链路的监测。设网络中共有E条链路，为

(1)

(2)

2.2 基于度与距离的监测器分配算法

基于上节分析，为降低监测器的数量，在监测树构造过程中DDMA算法首先在网络中进行满二叉树的M-tree构造。但由于实际网络拓扑结构的限制，不一定满足所有链路均能被二叉树覆盖，此时再将剩余链路依次加入至M-tree中，直至完成所有链路的监测。对于网络中节点度小于3的节点，与其相连的链路数小于3，监测信号到达该节点需要占用一条链路，此时无法为其选择2条或更多的出链路，由上节可知，无论如何都需要在该节点设置监测器以实现故障链路的准确监测。但如果该节点作为根节点，设置激光器发送监测信号，则无需为其设置监测器，可降低监测器数量。因此在满二叉树的构造过程中，DDMA算法首先选择节点度最低的节点设置激光器，发送监测信号至其邻居节点。在为每一条入链路选择出链路时，向相邻节点中节点度数大、节点之间距离远的两个节点转发监测信号，构成2条出链路。对DDMA算法进行详细描述，为方便起见，首先列出算法所需变量符号及其含义。

G=(V,E)：网络G由节点集合V和链路集合E组成，其中V={vi:i=1,2,3,…，n}，E={el:l=1,2,3,…，m}；

Gnew←G(vi,vj)：在网络G中删除链路(vi,vj)，记为网络Gnew；

DG：节点度数组，DG(v1,v2,…)=[2,3,…]表示节点v1,v2节点度为2, 3；

DT：节点间最短路径跳数矩阵；

MF：监测器状态数组，当其元素mfi=1时，表示在节点vi处设置监测器，接收由出链路发送至节点vi的信号，反之为0；

NBNi：节点vi的邻居节点集合；

STN：等待寻找出链路的节点集合，STN(i)表示集合中第i个元素；

EDN：所寻找的出链路的末端节点集合，EDN(i)表示集合中第i个元素；

MTree：最终的M-tree方案，为3列矩阵，每一行的第一列表示监测信号传输链路的源节点，第二列表示宿节点，第三列为依次递增的序号，表示当前宿节点的深度。

DDMA算法详细步骤如下：

Step1输入网络G，确定激光器位置以及监测信号发送的链路。

Step1.1 计算网络中所有节点的度DG，选择节点度数最小的一个节点vi，若多个节点的度相同，则随机选择一个，在该节点设置激光器，STN={vi}，Gnew←G；

Step1.2 计算NBNi和DG(NBNi)，并对DG(NBNi)进行排序，选择度最大的节点vj，EDN={vj}；

Step1.3 选择链路el=(vi,vj)做为激光器发送监测信号的链路，i=1，将el加入监测树中，MTree←[MTree;vi,vj,i]，Gnew←Gel。

Step2判断Gnew中是否存在链路，存在则跳转至Step3，否则跳转至Step6。

Step3扩展监测树结构，增加监测树所覆盖的链路。

Step3.1i←i+1，计算DG(EDN)，并对其进行排序，如果DG(EDN)中的最大值小于2，跳转至Step4，否则继续；

Step3.2 对于EDN中节点度小于2的节点vk，在该节点设置监测器mfk=1，并将该节点从EDN中删除，将EDN集合赋给STN，STN←EDN，清空EDN，EDN=∅；

Step3.3 对于STN中每一个节点STN(i)，计算NBNSTN(i)和DG(NBNSTN(i))，对DG(NBNSTN(i))进行排序，选择节点度最大的两个节点，如果仅有一种选择，将两个节点vm,vn加入至EDN，如果存在多种选择组合，计算DT(NBNSTN(i))，选择邻居节点中节点度最大，且距离最远(使用最短路径计算距离，且不经过节点STN(i))的两个节点vm,vn加入至EDN，MTree←[MTree;STN(i),vm,i;STN(i),vn,i],Gnew←Gem,en，其中em=(STN(i),vm)，en=(STN(i),vn)；

Step3.4 跳转至Step2。

Step4在EDN中每个节点处均设置监测器，mfi=1，其中vi∈EDN。

Step5随机选择网络Gnew中一条链路el，将el加入监测树中，并将el末端节点添加至EDN中，Gnew←Gnewel，跳转至Step2。

Step6输出监测树方案MTree以及监测器的位置信息。

DDMA算法流程见图3。

图3 DDMA算法流程

2.3 DDMA算法示例

图4给出高速铁路骨干层光传送网络二号环的简化网络拓扑，其中含有节点18个(以数字表示)，链路共27条。利用DDMA算法为二号环设计M-tree方案如图4中虚线所示，实心箭头表示监测器设置位置。激光器设置于节点1处，其邻居节点中，节点3度最大，因此首先将监测信号转发至节点3。节点3在其邻居节点中寻找两个度最大且相互距离最远的节点，即节点4和8，向其转发监测信号。节点4将监测信号转发至节点1和6；节点8邻居节点中，节点9、14度较大，因此将监测信号转发至节点9和14，如图4中橙色虚线所示。此时节点9邻居节点中，节点11、14和15度均为3(计算节点度时删掉已经被监测信号经过的链路)，但节点11与节点14之间距离较远，因此节点9选择将监测信号发送至节点11和14，如图4中红色点划线所示。如此反复直至所有链路均被监测信号经过，如图4中蓝色点线所示，完成M-tree的设计。

图4 骨干层二号环M-tree方案设计

3 算法仿真与结果

为验证DDMA算法性能，利用该算法在不同网络拓扑下设计M-tree方案，计算所需要的监测器数量，统计不同链路下DDMA算法设计M-tree方案所需要的运行时间。

图5 不同算法所需监测器数量对比

由图5可看出，在不同网络拓扑下DDMA算法所设计的M-tree方案所需的监测器数量与理论最低数量接近。当网络中链路数为55时，DDMA所需监测器数量超过理论最低值7%，其他情况下均低于7%。较MLS算法，DDMA最大可以节省约11%的监测器数量(对应链路数量95处)。

由2.1节可知，当入链路可以找到两条出链路时，M-tree设计可以最大限度降低监测器数量，因此当网络中平均节点度较大时，M-tree所需监测器数量应更接近于理论最小值。为进一步验证DDMA在不同节点度网络中的表现，在平均节点度为2.5、3和3.5的网络中，利用DDMA与MLS算法设计M-tree方案，所需要监测器数量见图6。

图6 不同节点度所需监测器数量

在链路数大于50的网络中，平均节点度为2.5时，DDMA所设计M-tree方案所需监测器数量超过理论最低值20%～25%，低于MLS算法5%～9%；平均节点度为3时，DDMA所需监测器超过理论值5%～10%，低于MLS算法5%～8%；当平均节点度为3.5时，DDMA所需监测器数量不超过理论值5%，低于MLS算法5%～8%。DDMA算法在节点度较低的网络中表现较差，其原因是节点度较低的网络拓扑形状偏向于环形网，而环形网络难以分解为树形结构，不适合使用M-tree方案实现链路故障的监测。当网络中平均节点度大于3.5时，DDMA算法所需监测器数量十分接近理论最低值。而目前铁路光传送网络中骨干层网络也逐渐向网状网演进，链路数不断增加，网络平均节点度随之上升，未来也更加适合使用M-tree实现故障监测。同时汇聚层与接入层网络拓扑更加复杂，使用M-tree方案也可以降低其故障监测成本。

为了进一步验证M-tree方案在铁路光传送网络中的表现，针对当前高速铁路骨干层中一号环、二号环、三号环和四号环的网络简化拓扑，使用DDMA算法为其设计M-tree监测方案，所需监测器数量见图7。在四大环中，DDMA算法所设计M-tree方案均可以用接近理论最低的监测器数量实现链路的故障监测，其中一号环、三号环和四号环所需监测器数量超过理论最低值1个，二号环中超过理论最低值2个。DDMA算法与MLS表现基本相同，但参考图 5、图6仿真结果，随着未来高速铁路骨干层网络复杂化，其链路数量增加后，DDMA可获得更优的监测方案。

图7 骨干层网络拓扑所需监测器

文献[12]中提出使用M-trail监测方案实现高速铁路光传送网络的链路故障监测，其理论所需监测器与激光器数量为2×log2「E+1⎤，但其所需的监测波长较多，影响网络中业务的传输。M-tree监测方案虽使用了更多的监测器，但降低了所占用监测波长的数量。本文利用监测代价[9]对比M-trail和M-tree两种监测方案，监测代价表示为：λ·(NMN+NLD)+WLS，其中NMN、NLD分别代表监测器和激光器的数量，WLS代表占用波长数，λ为可调节系数，调节监测器和激光器代价与波长资源代价的比值。监测代价综合考虑监测方案中所使用的监测器、激光器和占用监测波长的数量，以评估当前监测方案的性能，结果见图8。M-trail监测方案理论所占用波长资源[10]可表示为

(3)

其中

(4)

由图8可看出，当λ=2时，M-tree方案相比M-trail方案可节省约30%监测代价，当λ=3时，M-tree可降低20%左右监测代价，而当λ=4时，M-tree可降低10%左右监测代价。高速铁路光传送网络骨干层四大环中，M-trail与M-tree实现链路故障监测所需监测代价如表2所示，其中M-trail监测代价为理论最低值，M-tree监测代价为DDMA算法所得结果。综上所述，相对于M-trail方案，DDMA算法所设计M-tree监测方案可有效降低网络中的监测成本。

图8 M-tree(DDMA)与M-trail所需监测代价对比

表2 骨干层四大环所需监测代价

图9给出不同网络拓扑下DDMA算法的运行时间，本次仿真基于MATLAB，使用Intel®CoreTMi5-4590处理器，4 GB内存。图中可见随着网络链路数增加，DDMA算法运行时间近似线性增加，在100条链路的网络中，DDMA耗时0.169 s可得到M-tree监测方案，此时MLS耗时0.153 s。

图9 DDMA算法运行时间

4 结束语

本文研究了M-tree监测方案在高速铁路光传送网路中的链路故障定位方法，提出了DDMA算法设计M-tree监测方案。在对M-tree进行扩展时，向节点度最大且相互之间距离最远的两个节点转发监测信号，以降低M-tree所需的监测器数量，进而降低监测代价。将DDMA算法应用于高速铁路光传送网络骨干层网络，为其设计链路监测方案，所需监测器数量均接近理论最小值。通过利用大量随机网络拓扑进行仿真验证，结果表明，本文所提出DDMA算法在设计M-tree时，所使用监测器数量不超过理论最低值7%，相对于现有M-trail监测方法，可以节省20%～30%的监测代价。同时随着网络链路数量增加，DDMA算法所需时间近似线性增长，运行所需时间较短，对高速铁路光传送网络的故障监测具有一定参考意义。