高速鐵路光傳送網絡鏈路故障定位的研究

劉天陽,王仲凱,孫 強

(北京交通大學 電子信息工程學院，北京 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分配方案，并通過仿真驗證，結果表明該算法不僅可以獲得較優的監測跡分配，而且可以減少所需的監測代價。