劉天陽,王仲凱,孫 強(qiáng)

(北京交通大學(xué) 電子信息工程學(xué)院，北京 100044)

近年來我國高速鐵路取得了快速發(fā)展，鐵路光傳送網(wǎng)絡(luò)是高速鐵路安全運(yùn)行的基礎(chǔ)，光傳送網(wǎng)絡(luò)承載著保證列車安全運(yùn)行的大量業(yè)務(wù)，如：同步及時(shí)間分配系統(tǒng)業(yè)務(wù)、應(yīng)急通信系統(tǒng)業(yè)務(wù)、列車調(diào)度指揮控制、列車運(yùn)行狀態(tài)監(jiān)測、通信網(wǎng)管、電力電牽監(jiān)控、動力及環(huán)境監(jiān)測、信號業(yè)務(wù)、GSM-R業(yè)務(wù)、調(diào)度通信等。高速鐵路骨干層網(wǎng)絡(luò)主要采用OTN技術(shù)進(jìn)行環(huán)形組網(wǎng)，隨著光傳送網(wǎng)絡(luò)技術(shù)的發(fā)展，單波傳輸速率可以達(dá)到40 Gbit/s，并且逐步向100、400 Gbit/s過渡[1]。一根光纖可以承載數(shù)以百計(jì)的波長，即使是單根光纖的中斷也會帶來大量的信息丟失，將會嚴(yán)重影響網(wǎng)絡(luò)中的業(yè)務(wù)傳輸。為了保證光傳送網(wǎng)絡(luò)中的業(yè)務(wù)安全傳輸，必須在網(wǎng)絡(luò)故障發(fā)生后能夠快速、準(zhǔn)確地定位出故障發(fā)生的位置，并采取相應(yīng)的故障恢復(fù)措施，以避免網(wǎng)絡(luò)故障所帶來的損失。因此，對于光傳送網(wǎng)絡(luò)鏈路故障定位的研究具有非常重要的意義。

實(shí)現(xiàn)光傳送網(wǎng)絡(luò)的快速故障定位需要一個(gè)有效的故障監(jiān)測機(jī)制。其中監(jiān)測跡m-trail是實(shí)現(xiàn)光傳送網(wǎng)絡(luò)故障定位的一種物理層監(jiān)測結(jié)構(gòu)，其基本思想是把網(wǎng)絡(luò)中的故障定位問題轉(zhuǎn)化為對網(wǎng)絡(luò)中的鏈路進(jìn)行二進(jìn)制的編碼問題。依據(jù)二進(jìn)制編碼機(jī)制可知，少量的二進(jìn)制bits可以產(chǎn)生大量不同的編碼，因此少量的m-trail即可實(shí)現(xiàn)網(wǎng)絡(luò)的快速、精確故障定位。

為了實(shí)現(xiàn)在大型的網(wǎng)絡(luò)中快速分配m-trail，相對于ILP(整數(shù)線性規(guī)劃)模型，有學(xué)者提出了一種啟發(fā)式的RCA+RCS算法以及MTA(監(jiān)測跡分配算法)，啟發(fā)式算法RCA+RCS可以在較短的時(shí)間內(nèi)找到定位故障的方案，但是RCA+RCS算法具有隨機(jī)性。更重要的是該算法有可能會出現(xiàn)監(jiān)測跡不相連的問題，因此在大型的網(wǎng)絡(luò)中會增加監(jiān)測跡的數(shù)量。由于MTA算法在選擇下一條鏈路時(shí)會固定選擇最大權(quán)重的鏈路，這樣會存在局部最優(yōu)的問題。本文提出一種基于RWS+MTA的m-trail分配算法，采用一個(gè)概率模型在選擇下一條鏈路時(shí)可以擴(kuò)大搜索的空間，經(jīng)過有限次迭代，可以選出較優(yōu)的m-trail分配方案。

1 故障定位現(xiàn)狀

一根光纖可以承載數(shù)以百計(jì)的波長，單波承載的帶寬可以達(dá)到10 GB或者100 GB。因此，一根光纖的中斷將會造成大量的數(shù)據(jù)丟失，為了最大限度減少數(shù)據(jù)的丟失，能夠快速定位并恢復(fù)故障鏈路非常重要。鏈路故障檢測和定位可以在不同的協(xié)議層[2-3]。 比如：OSPF(開放路徑最短優(yōu)先協(xié)議)，IS-IS(中間系統(tǒng)到中間系統(tǒng)路由協(xié)議)。一般來說，通過上層協(xié)議需要花費(fèi)較長的時(shí)間，遠(yuǎn)高于光域要求的50 ms的恢復(fù)時(shí)間[4]。為實(shí)現(xiàn)快速鏈路故障定位，會優(yōu)先選擇光域[5-7]，光域故障檢測與定位原理如圖1所示。每一個(gè)監(jiān)測器與控制平面中的管理器直接相連，若網(wǎng)絡(luò)中出現(xiàn)了故障，相應(yīng)的監(jiān)測器會發(fā)出告警信息，并把告警信息傳遞給控制平面中的管理器。管理器收到告警信息后會根據(jù)相應(yīng)的告警信息定位出故障發(fā)生的位置，與此同時(shí)，管理器會對路徑進(jìn)行重路由，從而繞過發(fā)生故障的鏈路，以保證網(wǎng)絡(luò)的正常運(yùn)行[8]。

圖1 光域故障檢測與定位原理

對于光傳送網(wǎng)絡(luò)的故障檢測與定位，文獻(xiàn)[9-13]進(jìn)行了廣泛的研究。在光傳送網(wǎng)絡(luò)中故障的檢測與定位是根據(jù)網(wǎng)絡(luò)中監(jiān)測器發(fā)出的告警信息來實(shí)現(xiàn)的。在大型網(wǎng)絡(luò)中為了能夠?qū)崿F(xiàn)快速、準(zhǔn)確的故障定位，必須把大量冗余告警降低到最低限度，這樣才能減少告警的處理時(shí)間。因此，合理的分配監(jiān)測器對于實(shí)現(xiàn)快速、準(zhǔn)確的故障定位非常重要。

1.1 監(jiān)測環(huán)故障定位

假設(shè)一次最多只有一條鏈路發(fā)生故障，當(dāng)網(wǎng)絡(luò)中的某條鏈路出現(xiàn)故障時(shí)，監(jiān)測環(huán)中的監(jiān)測波長信號就會中斷，此時(shí)，相應(yīng)的監(jiān)測器就會檢測到中斷的信號從而發(fā)出告警信息，進(jìn)而可以根據(jù)監(jiān)測器產(chǎn)生的告警碼進(jìn)行故障定位。告警碼的形式為{am-1,…，aj,…,a1,a0}，其中aj=1表示監(jiān)測環(huán)中的第cj個(gè)監(jiān)測器產(chǎn)生了告警，相應(yīng)的aj=0表示該監(jiān)測器沒有產(chǎn)生告警。每一條鏈路的告警碼都存入故障告警碼表中，在故障發(fā)生后可以通過收集監(jiān)測器發(fā)出的故障告警信息，并查找故障告警碼表來實(shí)現(xiàn)快速、準(zhǔn)確的故障定位。圖2(a)為m-cycle結(jié)構(gòu)圖，圖2(b)顯示的是由3個(gè)監(jiān)測環(huán){c2,c1,c0}組成的一個(gè)鏈路故障監(jiān)測方法。表1為該監(jiān)測環(huán)中所有鏈路對應(yīng)的告警碼，其中Link代表網(wǎng)絡(luò)中的鏈路，D代表故障告警碼的十進(jìn)制表示形式。如果鏈路(0，1)出現(xiàn)了故障，在監(jiān)測環(huán)c1,c0中的監(jiān)測器就會產(chǎn)生告警，對應(yīng)的告警碼為[0，1，1]。在理想的情況下，每一條鏈路應(yīng)該擁有唯一的故障告警碼。但是鏈路(3，4)與鏈路(2，4)的故障告警碼相同，如果鏈路(3，4)或者鏈路(2，4)發(fā)生故障，由表1可以看出，鏈路(3，4)與鏈路(2，4)在發(fā)生故障時(shí)有相同的告警碼，因此，根據(jù)監(jiān)測器產(chǎn)生的告警碼不能判定鏈路(3，4)或者鏈路(2，4)是否出現(xiàn)故障。

圖2 m-cycle結(jié)構(gòu)圖及監(jiān)測環(huán)分布

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

1.2 監(jiān)測跡故障定位

盡管監(jiān)測環(huán)可以很大程度上減少監(jiān)測器的數(shù)量，但是由于監(jiān)測環(huán)有時(shí)不能唯一確定鏈路是否出現(xiàn)故障，并且監(jiān)測鏈路固定在一個(gè)環(huán)中，不具有可擴(kuò)展性。因此，為了能夠在減少監(jiān)測器數(shù)量的同時(shí)可以唯一確定鏈路是否出現(xiàn)故障，文獻(xiàn)[14]提出了m-trail(監(jiān)測跡)的概念。m-trail打破了m-cycle監(jiān)測通路必須是環(huán)的限制，監(jiān)測路徑可以是任意的形狀，也可以經(jīng)過一個(gè)節(jié)點(diǎn)一次或者多次。

m-trail故障定位方法由一系列監(jiān)測跡來監(jiān)測鏈路是否出現(xiàn)故障，如果網(wǎng)絡(luò)中某條鏈路出現(xiàn)了故障，經(jīng)過該鏈路的監(jiān)測跡中的監(jiān)測器就會產(chǎn)生告警。根據(jù)故障告警碼表可以看出，通過合理的分配監(jiān)測跡可以唯一確定故障鏈路。

圖3所示為監(jiān)測跡的分布，網(wǎng)絡(luò)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為所對應(yīng)的故障告警碼,可以看出能夠唯一確定某條鏈路是否出現(xiàn)故障。

圖3 監(jiān)測跡分布

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

m-trail故障定位實(shí)際上是在一定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和監(jiān)測結(jié)構(gòu)的限制條件下，將故障定位的問題轉(zhuǎn)化為對網(wǎng)絡(luò)中的鏈路進(jìn)行二進(jìn)制編碼的問題，可以實(shí)現(xiàn)網(wǎng)絡(luò)監(jiān)測資源的最優(yōu)化配置。

2 監(jiān)測跡研究現(xiàn)狀

目前m-trail的設(shè)計(jì)方法都是為了降低監(jiān)測代價(jià)的同時(shí)能夠快速、準(zhǔn)確地實(shí)現(xiàn)故障的定位。在m-trail的設(shè)計(jì)方法中，采用如下方式估算該方案所消耗的監(jiān)測代價(jià)：監(jiān)測代價(jià) = 監(jiān)測器的成本 + 監(jiān)測帶寬的成本=γ×監(jiān)測器的個(gè)數(shù) + 監(jiān)測波長的總數(shù)[14]。

可以通過調(diào)整γ的數(shù)值來控制監(jiān)測器的個(gè)數(shù)與監(jiān)測波長總數(shù)之間的比重，從而實(shí)現(xiàn)m-trail分配算法在監(jiān)測器成本與監(jiān)測帶寬成本之間的折中。如何分配m-trail在保證準(zhǔn)確、快速定位出故障的同時(shí)需要更少的監(jiān)測代價(jià)是目前研究的方向。

目前對于m-trail的故障定位主要是針對于單鏈路，其中m-trail的設(shè)計(jì)方法主要有：整數(shù)線性規(guī)劃方法、RCA+RCS、啟發(fā)式監(jiān)測跡分配算法。

2.1 整數(shù)線性規(guī)劃設(shè)計(jì)方法

文獻(xiàn)[14]提出了在光傳送網(wǎng)絡(luò)中基于m-trail的故障定位方法，并設(shè)計(jì)了分配m-trail的ILP模型以實(shí)現(xiàn)對網(wǎng)絡(luò)中監(jiān)測資源的優(yōu)化配置。該設(shè)計(jì)方法的優(yōu)勢在于能夠給出m-trail分配的最優(yōu)解，但是ILP是以最小化監(jiān)測代價(jià)為目標(biāo)，通過設(shè)置多個(gè)約束條件以及參數(shù)，然后改變各個(gè)參數(shù)的值，進(jìn)而找到最優(yōu)解。

基于ILP的m-trail設(shè)計(jì)問題在理論上屬于NP-hard的問題，所以m-trail的設(shè)計(jì)過程非常復(fù)雜，尤其是在大型網(wǎng)絡(luò)中，由于使用ILP方法求得最優(yōu)解所需要的時(shí)間較長，往往找不到最優(yōu)解甚至有可能求不出解。因此，利用ILP方法設(shè)計(jì)m-trail在實(shí)際應(yīng)用中很難實(shí)施。

2.2 RCA+RCS設(shè)計(jì)方法

為了能夠?qū)崿F(xiàn)快速分配m-trail，文獻(xiàn)[15]提出了一種啟發(fā)式的RCA+RCS算法[15]，相對于ILP(整數(shù)線性規(guī)劃)模型，可以在較短時(shí)間內(nèi)找到m-trail的分配方案。RCA+RCS算法的基本思想是,首先為網(wǎng)絡(luò)中的每一條鏈路隨機(jī)分配一個(gè)唯一的二進(jìn)制識別碼，然后在分配識別碼的基礎(chǔ)上對每一條m-trail進(jìn)行調(diào)整，從而得到正確的m-trail結(jié)構(gòu)。

雖然RCA+RCS算法可以得到有效的監(jiān)測結(jié)構(gòu)，但是由于其具有隨機(jī)性，在RCS過程中可能產(chǎn)生多個(gè)分離的m-trail，因此在分配m-trail時(shí)有可能會使m-trail的數(shù)目增多，從而增加m-trail以及監(jiān)測器的數(shù)量。因此，RCA+RCS算法的性能難以得到保證，為了得到一個(gè)好的方案，有時(shí)需要重復(fù)運(yùn)行該算法以碰巧可以得到一個(gè)性能比較好的起點(diǎn)，然后從多個(gè)最終得到的運(yùn)行結(jié)果中挑選出最好的。這樣不但會使得運(yùn)行時(shí)間變長，而且很難保證會獲得好的結(jié)果。

2.3 MTA設(shè)計(jì)方法

MTA算法[16]與RCA+RCS算法的思想相反，RCA+RCS首先為每一條鏈路分配一個(gè)唯一的編碼，然后對m-trail的結(jié)構(gòu)進(jìn)行調(diào)整。而MTA算法的基本思想是先將所有鏈路放入一個(gè)集合中，然后添加一條m-trail把集合分為2個(gè)集合，再添加一條m-trail把集合分為4個(gè)集合，以此類推不斷增加m-trail直到集合數(shù)等于所有鏈路數(shù)，并且所有鏈路都被該m-trail經(jīng)過為止。圖4為MTA算法的流程，其中集合AS0為網(wǎng)絡(luò)中所有的鏈路的集合。

圖4 MTA算法流程

3 RWS+MTA設(shè)計(jì)方法

雖然MTA算法在設(shè)計(jì)m-trail時(shí)可以有效減少監(jiān)測器的數(shù)量，從而降低監(jiān)測代價(jià)。但是由于MTA算法在選擇下一條鏈路時(shí)會固定選擇最大權(quán)重的鏈路，這樣會存在局部最優(yōu)的問題。為了避免MTA算法中出現(xiàn)局部最優(yōu)的狀況，引入一種輪盤賭選擇RWS(Roulette Wheel Selection)算法。

3.1 RWS+MTA算法流程

由于RWS算法使用一個(gè)概率模型在選擇下一條鏈路時(shí)擴(kuò)大了搜索空間，可以避免局部最優(yōu)情況的出現(xiàn)。因此采用RWS+MTA算法來設(shè)計(jì)m-trail，通過有限次的迭代可以從中選擇出較優(yōu)的m-trail分配方案，圖5為RWS+MTA算法流程。

圖5 RWS+MTA算法流程

步驟1初始化m=0，min_cost=+∞，min_ACT=?。其中，m為迭代次數(shù)；min_cost為最小的監(jiān)測代價(jià)；min_ACT為對應(yīng)的故障告警碼表。

步驟2初始化鏈路集合AS0，AS0為沒有被監(jiān)測跡經(jīng)過的鏈路集合；當(dāng)一次迭代完成后，AS0必須為空集，因?yàn)锳S0中的每一條鏈路都唯一確定。

步驟3增加一條m-trail。

步驟3.1尋找監(jiān)測跡tj的集合pj，tj為添加的第j條監(jiān)測跡，pj為包含監(jiān)測跡tj的集合。

步驟3.1.3為節(jié)點(diǎn)nk周圍的每一個(gè)相連的鏈路賦予權(quán)重。在拓?fù)銰(V,E)-pj中以節(jié)點(diǎn)的度數(shù)與鏈路成本倒數(shù)的乘積作為節(jié)點(diǎn)nk的每個(gè)鄰接鏈路l的權(quán)重，設(shè)置為wl，設(shè)Q1，Q2為常數(shù)，如果l∈AS0，則wl×Q1→wl也就是說該鏈路沒有被m-trail經(jīng)過;如果有其他鏈路l在pj中，則wl/Q2→wl，也就是說該鏈路被另外的m-trail經(jīng)過了；如果所有鏈路都可以被唯一確定，則wl→0。

步驟4更新集合，并獲取本輪的告警碼表。

步驟5是否所有的鏈路都可以被唯一確定，并且AS0=?，如果為假轉(zhuǎn)至步驟3，如果為真則轉(zhuǎn)至步驟6。

步驟6計(jì)算監(jiān)測代價(jià)。

步驟7判斷監(jiān)測代價(jià)是否小于min_cost，如果為真轉(zhuǎn)至步驟8，如果為假轉(zhuǎn)至步驟9。

步驟8令min_cost等于步驟7得出的最小監(jiān)測代價(jià)。

步驟9m=m+1。

步驟10如果m

3.2 m-trail 設(shè)計(jì)

表3為鐵路骨干層二號環(huán)故障告警碼表，若要對網(wǎng)絡(luò)中的每一條鏈路都能唯一確定其是否出現(xiàn)了故障，需要{t7,t6,t5,t4,t3,t2,t1,t0}8條監(jiān)測跡,如圖6所示。由表3可以看出每一條鏈路都對應(yīng)唯一的故障告警碼。

表3 骨干層二號環(huán)故障告警碼

圖6 骨干層二號環(huán)監(jiān)測跡分布

通過運(yùn)行RWS+MTA算法得到了以上8條監(jiān)測跡，監(jiān)測跡的分配如圖6所示。

3.3 算法仿真與結(jié)果分析

為了驗(yàn)證該算法，對隨機(jī)生成的100個(gè)網(wǎng)絡(luò)拓?fù)溥M(jìn)行仿真。由于RCA+RCS算法具有隨機(jī)性，因此，選取隨機(jī)生成的100個(gè)網(wǎng)絡(luò)拓?fù)渲械拿恳粋€(gè)拓?fù)溥\(yùn)行RCA+RCS算法100次，然后分別選擇這100次中效果最好的，同時(shí)運(yùn)用RWS+MTA算法進(jìn)行10次迭代。因?yàn)镸TA算法每一次選擇下一條鏈路時(shí)都是固定的，因此MTA算法只需要運(yùn)行一次。

圖7為不同鏈路數(shù)所對應(yīng)的監(jiān)測代價(jià)。采用RWS+MTA算法設(shè)計(jì)m-trail所需要的監(jiān)測代價(jià)最小。隨著鏈路數(shù)的增多，RCA+RCS算法對應(yīng)的監(jiān)測代價(jià)明顯增加，這是由于RCA+RWS算法的隨機(jī)性引起的。由于RWS+MTA算法可以進(jìn)行一定次數(shù)的迭代，從而在生成m-trail選擇下一條鏈路時(shí)擴(kuò)大了搜索空間，進(jìn)而得到較優(yōu)的m-trail分配方式。

圖7 不同鏈路數(shù)對應(yīng)的監(jiān)測代價(jià)

圖8 不同鏈路數(shù)所需監(jiān)測器的數(shù)目

圖9為不同節(jié)點(diǎn)數(shù)所需要的監(jiān)測器數(shù)量。隨著節(jié)點(diǎn)數(shù)的增加，在節(jié)點(diǎn)數(shù)大于40后，RCA+RCS算法所需要的監(jiān)測器數(shù)量明顯增多，這是由RCA+RCS算法的隨機(jī)性引起的。MTA與RWS+MTA算法隨著節(jié)點(diǎn)數(shù)目的增加變化不大，但是RWS+MTA可以通過不斷迭代進(jìn)而找到較優(yōu)的m-trail分配方法，因此需要的監(jiān)測器數(shù)目較MTA少。

圖9 不同節(jié)點(diǎn)數(shù)需要的監(jiān)測器的數(shù)目

由于網(wǎng)絡(luò)拓?fù)涞碾S機(jī)性，選取平均節(jié)點(diǎn)度數(shù)為2與4的網(wǎng)絡(luò)進(jìn)行仿真。由圖10可以看出,隨著節(jié)點(diǎn)數(shù)的增多，RWS+MTA算法相對于其他兩種算法所需要的監(jiān)測代價(jià)最低，并且隨著節(jié)點(diǎn)度數(shù)的減少，監(jiān)測代價(jià)也隨之降低。這是因?yàn)殡S著網(wǎng)絡(luò)連通性降低，需要監(jiān)測的鏈路數(shù)變少，因此監(jiān)測代價(jià)也隨之減少。

圖10 不同度數(shù)的節(jié)點(diǎn)對應(yīng)的監(jiān)測代價(jià)

圖11為不同節(jié)點(diǎn)數(shù)所需要的監(jiān)測器數(shù)量。可以看出隨著節(jié)點(diǎn)數(shù)的增多，RWS+MTA算法所需要的監(jiān)測器的數(shù)目最少，另外隨著節(jié)點(diǎn)度數(shù)的降低，所需要的監(jiān)測器數(shù)目反而增多，這是因?yàn)殡S著網(wǎng)絡(luò)連通度的降低，會對m-trail設(shè)置的靈活性有一定限制，這樣就會增加m-trail數(shù)量，進(jìn)而需要更多的監(jiān)測器。

圖11 不同度數(shù)節(jié)點(diǎn)數(shù)目對應(yīng)的監(jiān)測器數(shù)目

圖12為運(yùn)用RWS+MTA算法對鐵路骨干層五大環(huán)設(shè)計(jì)m-trail時(shí)不同迭代次數(shù)所對應(yīng)的監(jiān)測代價(jià)，可以看出在經(jīng)過一定次數(shù)的迭代后，監(jiān)測代價(jià)趨于平穩(wěn)。因此，采用RWS+MTA算法可以利用較少的迭代次數(shù)以獲得比較優(yōu)的m-trail分配。

圖12 迭代次數(shù)對應(yīng)的監(jiān)測代價(jià)

4 結(jié)束語

本文研究光傳送網(wǎng)中的鏈路故障定位方法，由于m-trail可以在光域?qū)崿F(xiàn)快速、準(zhǔn)確的鏈路故障定位，滿足光傳送網(wǎng)絡(luò)50 ms的保護(hù)恢復(fù)時(shí)間，在故障發(fā)生時(shí)可以快速倒換至備用鏈路，以避免鏈路故障帶來的損失。本文提出一種基于RWS+MTA的m-trail分配算法，不僅可以避免RCA+RCS算法出現(xiàn)不相連的監(jiān)測跡使監(jiān)測跡數(shù)目增多的問題，并且可以避免MTA算法在設(shè)計(jì)m-trail時(shí)由于固定選擇權(quán)重最大的鏈路而帶來局部最優(yōu)問題。運(yùn)用該算法設(shè)計(jì)了骨干層二號環(huán)的m-trail分配方案，并通過仿真驗(yàn)證，結(jié)果表明該算法不僅可以獲得較優(yōu)的監(jiān)測跡分配，而且可以減少所需的監(jiān)測代價(jià)。