周 洋，孫 強(qiáng)

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

近年來(lái)高速鐵路發(fā)展十分迅速，截至2019年，我國(guó)高速鐵路運(yùn)營(yíng)里程已近三萬(wàn)公里，成為世界上高速鐵路運(yùn)營(yíng)里程最長(zhǎng)、在建規(guī)模最大的國(guó)家。高速鐵路光傳送網(wǎng)作為高速鐵路的神經(jīng)中樞，承載著包括鐵路列車控制、調(diào)度指令等重要信息以及大量的視頻監(jiān)控業(yè)務(wù)數(shù)據(jù)，其正常運(yùn)營(yíng)是保障鐵路安全運(yùn)行、列車安全行車的基礎(chǔ)。而由于波分復(fù)用技術(shù)的發(fā)展，光網(wǎng)絡(luò)中單根光纖可傳輸超過(guò)100個(gè)波長(zhǎng)，每個(gè)波長(zhǎng)可工作在40、100 Gbit/s甚至400 Gbit/s[1]。目前鐵路光傳送網(wǎng)絡(luò)骨干層主要使用40×100 Gbit/s OTN系統(tǒng)，匯聚層中鐵路局多按照40×10 Gbit/s波分系統(tǒng)設(shè)計(jì)，網(wǎng)絡(luò)中所承載業(yè)務(wù)量的不斷上升對(duì)網(wǎng)絡(luò)可靠性提出了更高的要求。一旦網(wǎng)絡(luò)中出現(xiàn)光纖損壞或折斷等故障，期間會(huì)產(chǎn)生大量的數(shù)據(jù)丟失，對(duì)業(yè)務(wù)的傳輸產(chǎn)生極大影響，輕則造成列車控制系統(tǒng)降級(jí)運(yùn)行，重則造成列車中途停車，嚴(yán)重影響高速鐵路系統(tǒng)的正常運(yùn)行。因此當(dāng)網(wǎng)絡(luò)中出現(xiàn)故障時(shí)，必須在規(guī)定的保護(hù)切換時(shí)間內(nèi)完成切換動(dòng)作，減少因故障對(duì)列車行車所帶來(lái)的負(fù)面影響。而故障定位是實(shí)施保護(hù)切換的基礎(chǔ)，快速、準(zhǔn)確的故障定位是保證高速鐵路光傳送網(wǎng)絡(luò)正常運(yùn)營(yíng)的前提。

目前對(duì)于光傳送網(wǎng)絡(luò)中的故障定位研究主要集中在鏈路故障方向。據(jù)統(tǒng)計(jì)，在較大規(guī)模的光傳送網(wǎng)中，多鏈路故障的發(fā)生概率在0.1%左右[2]，網(wǎng)絡(luò)中絕大多數(shù)鏈路故障情況為單鏈路故障，因此本文主要對(duì)網(wǎng)絡(luò)中單鏈路故障進(jìn)行討論。主流的單鏈路故障定位方案主要可以分為兩類：一是通過(guò)網(wǎng)絡(luò)的上層協(xié)議等技術(shù)實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)故障鏈路的定位[3-4]。文獻(xiàn)[3]通過(guò)使用開(kāi)放路徑最短優(yōu)先協(xié)議(Open Shortest Path First, OSPF)實(shí)現(xiàn)故障鏈路的定位。文獻(xiàn)[4]通過(guò)機(jī)器學(xué)習(xí)的方法，結(jié)合網(wǎng)絡(luò)中的業(yè)務(wù)流，推斷故障鏈路，實(shí)現(xiàn)對(duì)可疑鏈路集合的故障定位。但應(yīng)用此類方案進(jìn)行故障定位往往需要較高的定位時(shí)間，難以滿足高速鐵路光傳送網(wǎng)絡(luò)的保護(hù)恢復(fù)時(shí)間要求。同時(shí)過(guò)多的告警信號(hào)很容易引發(fā)警告風(fēng)暴，造成網(wǎng)絡(luò)質(zhì)量進(jìn)一步下降，使得故障定位變得更為復(fù)雜。二是通過(guò)在物理層光域設(shè)置專用的監(jiān)測(cè)器實(shí)現(xiàn)鏈路故障定位[5-6]。該方案的基本思想是通過(guò)在光域設(shè)置多個(gè)信號(hào)監(jiān)測(cè)器，對(duì)指定信號(hào)進(jìn)行監(jiān)測(cè)。當(dāng)特定監(jiān)測(cè)器無(wú)法收到指定監(jiān)測(cè)信號(hào)后，表明該監(jiān)測(cè)信號(hào)所經(jīng)過(guò)的鏈路出現(xiàn)故障，監(jiān)測(cè)器立即向網(wǎng)絡(luò)管理層發(fā)送告警信息。多個(gè)監(jiān)測(cè)器的告警信息組成告警序列，利用編碼的思想，使得網(wǎng)絡(luò)中的每條鏈路都擁有互不相同的告警碼。當(dāng)鏈路出現(xiàn)故障時(shí)，網(wǎng)絡(luò)管理層根據(jù)告警碼，便可定位故障鏈路。該方案雖使用了多個(gè)監(jiān)測(cè)器，增加了建設(shè)成本，但可以迅速、準(zhǔn)確地實(shí)現(xiàn)網(wǎng)絡(luò)中鏈路故障的定位，適用于對(duì)可靠性要求較高的網(wǎng)絡(luò)?；谠摶舅枷耄芯咳藛T提出了監(jiān)測(cè)環(huán)(Monitoring Cycle, M-cycle)[7-8]、監(jiān)測(cè)跡(Monitoring Trail, M-trail)[9-13]和監(jiān)測(cè)樹(shù)(Monitoring Tree, M-tree)[14-15]多種方案，相對(duì)于M-cycle和M-trail，M-tree可減少網(wǎng)絡(luò)故障定位中的監(jiān)測(cè)成本，同時(shí)可以完成故障鏈路的準(zhǔn)確定位。如何設(shè)計(jì)監(jiān)測(cè)方案，以最低的監(jiān)測(cè)成本實(shí)現(xiàn)故障鏈路的監(jiān)測(cè)是本文研究的重點(diǎn)。

本文基于光域設(shè)置監(jiān)測(cè)器以實(shí)現(xiàn)故障定位的思想，提出基于度與距離的監(jiān)測(cè)器分配算法(Degree and Distance Based Monitor Allocation, DDMA)設(shè)計(jì)M-tree監(jiān)測(cè)方案。通過(guò)多個(gè)隨機(jī)網(wǎng)絡(luò)拓?fù)潋?yàn)證DDMA性能，并利用DDMA為高速鐵路骨干層光傳送網(wǎng)絡(luò)設(shè)計(jì)鏈路故障監(jiān)測(cè)方案。

1 相關(guān)工作

為了實(shí)現(xiàn)光域的故障定位，最簡(jiǎn)單直觀的方法便是在每一條鏈路的兩端節(jié)點(diǎn)處分別設(shè)置激光器與監(jiān)測(cè)器。一旦監(jiān)測(cè)器無(wú)法收到激光器所發(fā)出的信號(hào)，便判定該鏈路出現(xiàn)故障。然而此方法所需激光器與監(jiān)測(cè)器數(shù)量較大，硬件成本過(guò)高，難以在實(shí)際中應(yīng)用。為減少激光器與監(jiān)測(cè)器的數(shù)量，文獻(xiàn)[7-8]研究了監(jiān)測(cè)環(huán)M-cycle方案。M-cycle通過(guò)在網(wǎng)絡(luò)中設(shè)置多個(gè)監(jiān)測(cè)環(huán)路，多個(gè)激光器發(fā)出監(jiān)測(cè)信號(hào)，經(jīng)過(guò)不同的環(huán)路后回到對(duì)應(yīng)的監(jiān)測(cè)器，方案設(shè)計(jì)時(shí)盡量保證每條鏈路都被互不相同的一組監(jiān)測(cè)環(huán)路經(jīng)過(guò)。當(dāng)任意一條鏈路出現(xiàn)故障時(shí)，所有經(jīng)過(guò)該鏈路的監(jiān)測(cè)環(huán)都被中斷，對(duì)應(yīng)監(jiān)測(cè)環(huán)便會(huì)在監(jiān)測(cè)器處產(chǎn)生告警信息，網(wǎng)管層收集到告警信息后便可以推斷出故障鏈路。雖然M-cycle可降低網(wǎng)絡(luò)中的監(jiān)測(cè)器數(shù)量，但由于監(jiān)測(cè)信號(hào)必須是環(huán)路的限制，可能存在無(wú)法準(zhǔn)確定位故障鏈路的情況，為克服該缺點(diǎn)，研究人員提出并研究了監(jiān)測(cè)跡M-trail[9-13]概念。相較于M-cycle方案，M-trail中監(jiān)測(cè)信號(hào)所經(jīng)過(guò)的鏈路不必是環(huán)路，多個(gè)監(jiān)測(cè)信號(hào)經(jīng)過(guò)特定路徑傳送至監(jiān)測(cè)器，方案設(shè)計(jì)更為靈活。網(wǎng)管層收集所有監(jiān)測(cè)器的告警信息，當(dāng)某一鏈路出現(xiàn)故障時(shí)，根據(jù)告警信息便可定位故障鏈路。M-trail實(shí)現(xiàn)故障鏈路監(jiān)測(cè)的核心是保證每條鏈路都被一組互不相同的監(jiān)測(cè)信號(hào)經(jīng)過(guò)的前提下，盡量減少監(jiān)測(cè)信號(hào)所經(jīng)過(guò)的鏈路數(shù)和監(jiān)測(cè)器的數(shù)量，即降低監(jiān)測(cè)代價(jià)。文獻(xiàn)[9]基于整數(shù)線性規(guī)劃方法設(shè)計(jì)M-trail，可以得到理論上的最優(yōu)解，但需要較久的算法運(yùn)行時(shí)間。文獻(xiàn)[10]提出RCA+RCS算法設(shè)計(jì)M-trail，但該算法存在一定隨機(jī)性，性能表現(xiàn)不穩(wěn)定。文獻(xiàn)[11]提出一種啟發(fā)式監(jiān)測(cè)器分配算法MTA，可以在較短時(shí)間內(nèi)實(shí)現(xiàn)M-trail的設(shè)計(jì)。文獻(xiàn)[12]基于MTA算法，提出輪盤(pán)賭選擇RWS+MTA算法，進(jìn)一步降低M-trail方案中所需的監(jiān)測(cè)代價(jià)，并通過(guò)利用高速鐵路光傳送網(wǎng)絡(luò)多個(gè)網(wǎng)絡(luò)拓?fù)鋵?duì)算法進(jìn)行仿真驗(yàn)證。文獻(xiàn)[13]基于“組”Group的概念設(shè)計(jì)M-trail，一個(gè)組內(nèi)的鏈路出現(xiàn)故障時(shí)，所需要的保護(hù)切換動(dòng)作相同，因此當(dāng)鏈路故障發(fā)生時(shí)，只需定位故障鏈路所處的組，保證做出正確的保護(hù)切換動(dòng)作即可。

M-trail方案雖然可以實(shí)現(xiàn)鏈路故障定位，但為了保證每條鏈路被互不相同的監(jiān)測(cè)信號(hào)經(jīng)過(guò)，需要占用多個(gè)監(jiān)測(cè)波長(zhǎng)以傳輸監(jiān)測(cè)信號(hào)，當(dāng)網(wǎng)絡(luò)規(guī)模增大時(shí)，所占用的監(jiān)測(cè)波長(zhǎng)較多，降低了網(wǎng)絡(luò)容量，方案所需監(jiān)測(cè)代價(jià)較高。為減少網(wǎng)絡(luò)中監(jiān)測(cè)波長(zhǎng)的占用，降低監(jiān)測(cè)代價(jià)，研究人員提出了監(jiān)測(cè)樹(shù)M-tree[14-15]概念。M-tree方案利用網(wǎng)絡(luò)中節(jié)點(diǎn)的多播能力，實(shí)現(xiàn)只使用一個(gè)激光器，同時(shí)網(wǎng)絡(luò)中每條鏈路只被一個(gè)監(jiān)測(cè)信號(hào)經(jīng)過(guò)便可完成網(wǎng)絡(luò)中的鏈路故障定位。圖1(a)所示網(wǎng)絡(luò)拓?fù)?，在?jié)點(diǎn)4處設(shè)置激光器，向節(jié)點(diǎn)5處發(fā)送監(jiān)測(cè)信號(hào)。節(jié)點(diǎn)5將監(jiān)測(cè)信號(hào)轉(zhuǎn)發(fā)至節(jié)點(diǎn)1、6，節(jié)點(diǎn)1、6收到信號(hào)后分別轉(zhuǎn)發(fā)至節(jié)點(diǎn)2、4和節(jié)點(diǎn)2、3，節(jié)點(diǎn)3收到由節(jié)點(diǎn)6轉(zhuǎn)發(fā)的信號(hào)后，再次將信號(hào)轉(zhuǎn)發(fā)至節(jié)點(diǎn)1、5，由此實(shí)現(xiàn)所有鏈路的監(jiān)測(cè)信號(hào)覆蓋。在多個(gè)鏈路的末端設(shè)置監(jiān)測(cè)器(圖中實(shí)心箭頭處，即A、B、C、D和E)，便可以實(shí)現(xiàn)對(duì)整個(gè)網(wǎng)絡(luò)的鏈路監(jiān)測(cè)。簡(jiǎn)而言之，M-tree方案等同于將網(wǎng)絡(luò)的拓?fù)滢D(zhuǎn)換為樹(shù)形結(jié)構(gòu)，見(jiàn)圖1(b)。當(dāng)監(jiān)測(cè)器無(wú)法收到監(jiān)測(cè)信號(hào)時(shí)，產(chǎn)生告警碼‘1’并立即發(fā)送至網(wǎng)絡(luò)管理控制器。例如：當(dāng)鏈路(1,2)故障，監(jiān)測(cè)器B會(huì)產(chǎn)生告警信息，此時(shí)控制器收到告警碼為[01000]；當(dāng)鏈路(5,6)出現(xiàn)故障，監(jiān)測(cè)器C、D、E會(huì)產(chǎn)生告警碼[00111]。

圖1 M-tree方案示例

鏈路告警碼如表1所示，表中最后一列將一組告警碼轉(zhuǎn)換為十進(jìn)制數(shù)字以方便區(qū)分。不同鏈路所對(duì)應(yīng)告警碼均不相同，在網(wǎng)絡(luò)中出現(xiàn)故障時(shí)，網(wǎng)絡(luò)控制器便可根據(jù)不同告警碼迅速定位故障鏈路。為實(shí)現(xiàn)M-tree的設(shè)計(jì)，文獻(xiàn)[14]基于整數(shù)線性規(guī)劃，利用數(shù)學(xué)理論對(duì)M-tree 進(jìn)行設(shè)計(jì)，但由于過(guò)多的約束條件導(dǎo)致運(yùn)算時(shí)間長(zhǎng)，無(wú)法迅速求解。文獻(xiàn)[15]提出一種監(jiān)測(cè)器位置搜索(Monitor Location Searching, MLS)啟發(fā)式算法，在對(duì)M-tree進(jìn)行擴(kuò)展時(shí)，優(yōu)先選擇節(jié)點(diǎn)度(即節(jié)點(diǎn)所連接的鏈路數(shù)量)大的節(jié)點(diǎn)轉(zhuǎn)發(fā)監(jiān)測(cè)信號(hào)，但部分情況下仍存在監(jiān)測(cè)器浪費(fèi)的情況。

表1 告警碼表格

為方便描述M-tree方案，引入“入鏈路”和“出鏈路”概念。當(dāng)某節(jié)點(diǎn)收到監(jiān)測(cè)信號(hào)并對(duì)其進(jìn)行轉(zhuǎn)發(fā)時(shí)，將監(jiān)測(cè)信號(hào)傳輸至該節(jié)點(diǎn)的鏈路定位為入鏈路，該節(jié)點(diǎn)轉(zhuǎn)發(fā)監(jiān)測(cè)信號(hào)至下一個(gè)節(jié)點(diǎn)的鏈路為出鏈路。例如圖1(a)中，當(dāng)鏈路(6,3)為入鏈路時(shí)，鏈路(3,1)和(3,5)便為出鏈路，但將鏈路(5,6)看作入鏈路時(shí)，則鏈路(6,2)和(6,3)便為出鏈路?！叭~子節(jié)點(diǎn)”指M-tree中，位于樹(shù)形結(jié)構(gòu)的末端的節(jié)點(diǎn)，例如圖1(b)中節(jié)點(diǎn)4、2、1、5和2，因M-tree是將原始網(wǎng)絡(luò)拓?fù)浞纸鉃闃?shù)形結(jié)構(gòu)，因此某個(gè)節(jié)點(diǎn)可能多次作為葉子節(jié)點(diǎn)。“葉子鏈路”指M-tree結(jié)構(gòu)中連接葉子節(jié)點(diǎn)的鏈路，葉子鏈路作為入鏈路時(shí)，不存在任何一條出鏈路，例如圖1(b)中鏈路(1,4)和(3,1)等。

2 基于度與距離的監(jiān)測(cè)器分配算法

鏈路故障的準(zhǔn)確定位，本質(zhì)上是為每一條鏈路分配一個(gè)唯一的告警碼，故障定位的監(jiān)測(cè)代價(jià)由占用監(jiān)測(cè)波長(zhǎng)數(shù)量與監(jiān)測(cè)器/激光器的數(shù)量決定。在M-tree方案中，每條鏈路只會(huì)被經(jīng)過(guò)一次，所占用監(jiān)測(cè)波長(zhǎng)為固定值(等于鏈路數(shù)量)，且只需要一個(gè)激光器。因此在M-tree方案中，最重要的問(wèn)題是如何利用最少數(shù)量的監(jiān)測(cè)器實(shí)現(xiàn)故障鏈路的監(jiān)測(cè)，以降低監(jiān)測(cè)代價(jià)。

2.1 最少監(jiān)測(cè)器數(shù)量

在M-tree設(shè)計(jì)中，若某條入鏈路所對(duì)應(yīng)出鏈路的數(shù)量小于2時(shí)，則該入鏈路末端應(yīng)設(shè)置監(jiān)測(cè)器，否則無(wú)法實(shí)現(xiàn)故障鏈路的準(zhǔn)確定位。例如圖2中，入鏈路e1只有一條出鏈路e2，若A處不設(shè)置監(jiān)測(cè)器時(shí)，鏈路e1與鏈路e2出現(xiàn)故障時(shí)，有且僅有監(jiān)測(cè)器B產(chǎn)生告警信號(hào)，此時(shí)便無(wú)法準(zhǔn)確定位故障鏈路。相反，入鏈路e3處存在多條出鏈路，當(dāng)鏈路e3出現(xiàn)故障時(shí)，只有C、D、E三個(gè)監(jiān)測(cè)器產(chǎn)生告警信號(hào)，此告警碼只對(duì)應(yīng)鏈路e3，因此鏈路e3處無(wú)需設(shè)置監(jiān)測(cè)器。因此，若在M-tree方案設(shè)計(jì)時(shí)，可以保證除葉子鏈路外其他入鏈路均有多條出鏈路，此時(shí)可使用最少數(shù)量的監(jiān)測(cè)器實(shí)現(xiàn)鏈路故障監(jiān)測(cè)。

圖2 監(jiān)測(cè)器位置示例

為使得M-tree中監(jiān)測(cè)器數(shù)量最低，每一條入鏈路對(duì)應(yīng)的出鏈路的數(shù)量仍需要討論。當(dāng)每一條入鏈路選擇k(k>1)條出鏈路時(shí)，M-tree包含有1+k+k2+…+kn-1條鏈路，其中n(n≥1)表示M-tree結(jié)構(gòu)中樹(shù)的深度(設(shè)根節(jié)點(diǎn)深度為0，如圖2所示)。此時(shí)僅需在M-tree所有葉子鏈路處設(shè)置監(jiān)測(cè)器，便可以實(shí)現(xiàn)對(duì)所有鏈路的監(jiān)測(cè)。設(shè)網(wǎng)絡(luò)中共有E條鏈路，為

(1)

(2)

2.2 基于度與距離的監(jiān)測(cè)器分配算法

基于上節(jié)分析，為降低監(jiān)測(cè)器的數(shù)量，在監(jiān)測(cè)樹(shù)構(gòu)造過(guò)程中DDMA算法首先在網(wǎng)絡(luò)中進(jìn)行滿二叉樹(shù)的M-tree構(gòu)造。但由于實(shí)際網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的限制，不一定滿足所有鏈路均能被二叉樹(shù)覆蓋，此時(shí)再將剩余鏈路依次加入至M-tree中，直至完成所有鏈路的監(jiān)測(cè)。對(duì)于網(wǎng)絡(luò)中節(jié)點(diǎn)度小于3的節(jié)點(diǎn)，與其相連的鏈路數(shù)小于3，監(jiān)測(cè)信號(hào)到達(dá)該節(jié)點(diǎn)需要占用一條鏈路，此時(shí)無(wú)法為其選擇2條或更多的出鏈路，由上節(jié)可知，無(wú)論如何都需要在該節(jié)點(diǎn)設(shè)置監(jiān)測(cè)器以實(shí)現(xiàn)故障鏈路的準(zhǔn)確監(jiān)測(cè)。但如果該節(jié)點(diǎn)作為根節(jié)點(diǎn)，設(shè)置激光器發(fā)送監(jiān)測(cè)信號(hào)，則無(wú)需為其設(shè)置監(jiān)測(cè)器，可降低監(jiān)測(cè)器數(shù)量。因此在滿二叉樹(shù)的構(gòu)造過(guò)程中，DDMA算法首先選擇節(jié)點(diǎn)度最低的節(jié)點(diǎn)設(shè)置激光器，發(fā)送監(jiān)測(cè)信號(hào)至其鄰居節(jié)點(diǎn)。在為每一條入鏈路選擇出鏈路時(shí)，向相鄰節(jié)點(diǎn)中節(jié)點(diǎn)度數(shù)大、節(jié)點(diǎn)之間距離遠(yuǎn)的兩個(gè)節(jié)點(diǎn)轉(zhuǎn)發(fā)監(jiān)測(cè)信號(hào)，構(gòu)成2條出鏈路。對(duì)DDMA算法進(jìn)行詳細(xì)描述，為方便起見(jiàn)，首先列出算法所需變量符號(hào)及其含義。

G=(V,E)：網(wǎng)絡(luò)G由節(jié)點(diǎn)集合V和鏈路集合E組成，其中V={vi:i=1,2,3,…，n}，E={el:l=1,2,3,…，m}；

Gnew←G(vi,vj)：在網(wǎng)絡(luò)G中刪除鏈路(vi,vj)，記為網(wǎng)絡(luò)Gnew；

DG：節(jié)點(diǎn)度數(shù)組，DG(v1,v2,…)=[2,3,…]表示節(jié)點(diǎn)v1,v2節(jié)點(diǎn)度為2, 3；

DT：節(jié)點(diǎn)間最短路徑跳數(shù)矩陣；

MF：監(jiān)測(cè)器狀態(tài)數(shù)組，當(dāng)其元素mfi=1時(shí)，表示在節(jié)點(diǎn)vi處設(shè)置監(jiān)測(cè)器，接收由出鏈路發(fā)送至節(jié)點(diǎn)vi的信號(hào)，反之為0；

NBNi：節(jié)點(diǎn)vi的鄰居節(jié)點(diǎn)集合；

STN：等待尋找出鏈路的節(jié)點(diǎn)集合，STN(i)表示集合中第i個(gè)元素；

EDN：所尋找的出鏈路的末端節(jié)點(diǎn)集合，EDN(i)表示集合中第i個(gè)元素；

MTree：最終的M-tree方案，為3列矩陣，每一行的第一列表示監(jiān)測(cè)信號(hào)傳輸鏈路的源節(jié)點(diǎn)，第二列表示宿節(jié)點(diǎn)，第三列為依次遞增的序號(hào)，表示當(dāng)前宿節(jié)點(diǎn)的深度。

DDMA算法詳細(xì)步驟如下：

Step1輸入網(wǎng)絡(luò)G，確定激光器位置以及監(jiān)測(cè)信號(hào)發(fā)送的鏈路。

Step1.1 計(jì)算網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度DG，選擇節(jié)點(diǎn)度數(shù)最小的一個(gè)節(jié)點(diǎn)vi，若多個(gè)節(jié)點(diǎn)的度相同，則隨機(jī)選擇一個(gè)，在該節(jié)點(diǎn)設(shè)置激光器，STN={vi}，Gnew←G；

Step1.2 計(jì)算NBNi和DG(NBNi)，并對(duì)DG(NBNi)進(jìn)行排序，選擇度最大的節(jié)點(diǎn)vj，EDN={vj}；

Step1.3 選擇鏈路el=(vi,vj)做為激光器發(fā)送監(jiān)測(cè)信號(hào)的鏈路，i=1，將el加入監(jiān)測(cè)樹(shù)中，MTree←[MTree;vi,vj,i]，Gnew←Gel。

Step2判斷Gnew中是否存在鏈路，存在則跳轉(zhuǎn)至Step3，否則跳轉(zhuǎn)至Step6。

Step3擴(kuò)展監(jiān)測(cè)樹(shù)結(jié)構(gòu)，增加監(jiān)測(cè)樹(shù)所覆蓋的鏈路。

Step3.1i←i+1，計(jì)算DG(EDN)，并對(duì)其進(jìn)行排序，如果DG(EDN)中的最大值小于2，跳轉(zhuǎn)至Step4，否則繼續(xù)；

Step3.2 對(duì)于EDN中節(jié)點(diǎn)度小于2的節(jié)點(diǎn)vk，在該節(jié)點(diǎn)設(shè)置監(jiān)測(cè)器mfk=1，并將該節(jié)點(diǎn)從EDN中刪除，將EDN集合賦給STN，STN←EDN，清空EDN，EDN=?；

Step3.3 對(duì)于STN中每一個(gè)節(jié)點(diǎn)STN(i)，計(jì)算NBNSTN(i)和DG(NBNSTN(i))，對(duì)DG(NBNSTN(i))進(jìn)行排序，選擇節(jié)點(diǎn)度最大的兩個(gè)節(jié)點(diǎn)，如果僅有一種選擇，將兩個(gè)節(jié)點(diǎn)vm,vn加入至EDN，如果存在多種選擇組合，計(jì)算DT(NBNSTN(i))，選擇鄰居節(jié)點(diǎn)中節(jié)點(diǎn)度最大，且距離最遠(yuǎn)(使用最短路徑計(jì)算距離，且不經(jīng)過(guò)節(jié)點(diǎn)STN(i))的兩個(gè)節(jié)點(diǎn)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 跳轉(zhuǎn)至Step2。

Step4在EDN中每個(gè)節(jié)點(diǎn)處均設(shè)置監(jiān)測(cè)器，mfi=1，其中vi∈EDN。

Step5隨機(jī)選擇網(wǎng)絡(luò)Gnew中一條鏈路el，將el加入監(jiān)測(cè)樹(shù)中，并將el末端節(jié)點(diǎn)添加至EDN中，Gnew←Gnewel，跳轉(zhuǎn)至Step2。

Step6輸出監(jiān)測(cè)樹(shù)方案MTree以及監(jiān)測(cè)器的位置信息。

DDMA算法流程見(jiàn)圖3。

圖3 DDMA算法流程

2.3 DDMA算法示例

圖4給出高速鐵路骨干層光傳送網(wǎng)絡(luò)二號(hào)環(huán)的簡(jiǎn)化網(wǎng)絡(luò)拓?fù)?，其中含有?jié)點(diǎn)18個(gè)(以數(shù)字表示)，鏈路共27條。利用DDMA算法為二號(hào)環(huán)設(shè)計(jì)M-tree方案如圖4中虛線所示，實(shí)心箭頭表示監(jiān)測(cè)器設(shè)置位置。激光器設(shè)置于節(jié)點(diǎn)1處，其鄰居節(jié)點(diǎn)中，節(jié)點(diǎn)3度最大，因此首先將監(jiān)測(cè)信號(hào)轉(zhuǎn)發(fā)至節(jié)點(diǎn)3。節(jié)點(diǎn)3在其鄰居節(jié)點(diǎn)中尋找兩個(gè)度最大且相互距離最遠(yuǎn)的節(jié)點(diǎn)，即節(jié)點(diǎn)4和8，向其轉(zhuǎn)發(fā)監(jiān)測(cè)信號(hào)。節(jié)點(diǎn)4將監(jiān)測(cè)信號(hào)轉(zhuǎn)發(fā)至節(jié)點(diǎn)1和6；節(jié)點(diǎn)8鄰居節(jié)點(diǎn)中，節(jié)點(diǎn)9、14度較大，因此將監(jiān)測(cè)信號(hào)轉(zhuǎn)發(fā)至節(jié)點(diǎn)9和14，如圖4中橙色虛線所示。此時(shí)節(jié)點(diǎn)9鄰居節(jié)點(diǎn)中，節(jié)點(diǎn)11、14和15度均為3(計(jì)算節(jié)點(diǎn)度時(shí)刪掉已經(jīng)被監(jiān)測(cè)信號(hào)經(jīng)過(guò)的鏈路)，但節(jié)點(diǎn)11與節(jié)點(diǎn)14之間距離較遠(yuǎn)，因此節(jié)點(diǎn)9選擇將監(jiān)測(cè)信號(hào)發(fā)送至節(jié)點(diǎn)11和14，如圖4中紅色點(diǎn)劃線所示。如此反復(fù)直至所有鏈路均被監(jiān)測(cè)信號(hào)經(jīng)過(guò)，如圖4中藍(lán)色點(diǎn)線所示，完成M-tree的設(shè)計(jì)。

圖4 骨干層二號(hào)環(huán)M-tree方案設(shè)計(jì)

3 算法仿真與結(jié)果

為驗(yàn)證DDMA算法性能，利用該算法在不同網(wǎng)絡(luò)拓?fù)湎略O(shè)計(jì)M-tree方案，計(jì)算所需要的監(jiān)測(cè)器數(shù)量，統(tǒng)計(jì)不同鏈路下DDMA算法設(shè)計(jì)M-tree方案所需要的運(yùn)行時(shí)間。

圖5 不同算法所需監(jiān)測(cè)器數(shù)量對(duì)比

由圖5可看出，在不同網(wǎng)絡(luò)拓?fù)湎翫DMA算法所設(shè)計(jì)的M-tree方案所需的監(jiān)測(cè)器數(shù)量與理論最低數(shù)量接近。當(dāng)網(wǎng)絡(luò)中鏈路數(shù)為55時(shí)，DDMA所需監(jiān)測(cè)器數(shù)量超過(guò)理論最低值7%，其他情況下均低于7%。較MLS算法，DDMA最大可以節(jié)省約11%的監(jiān)測(cè)器數(shù)量(對(duì)應(yīng)鏈路數(shù)量95處)。

由2.1節(jié)可知，當(dāng)入鏈路可以找到兩條出鏈路時(shí)，M-tree設(shè)計(jì)可以最大限度降低監(jiān)測(cè)器數(shù)量，因此當(dāng)網(wǎng)絡(luò)中平均節(jié)點(diǎn)度較大時(shí)，M-tree所需監(jiān)測(cè)器數(shù)量應(yīng)更接近于理論最小值。為進(jìn)一步驗(yàn)證DDMA在不同節(jié)點(diǎn)度網(wǎng)絡(luò)中的表現(xiàn)，在平均節(jié)點(diǎn)度為2.5、3和3.5的網(wǎng)絡(luò)中，利用DDMA與MLS算法設(shè)計(jì)M-tree方案，所需要監(jiān)測(cè)器數(shù)量見(jiàn)圖6。

圖6 不同節(jié)點(diǎn)度所需監(jiān)測(cè)器數(shù)量

在鏈路數(shù)大于50的網(wǎng)絡(luò)中，平均節(jié)點(diǎn)度為2.5時(shí)，DDMA所設(shè)計(jì)M-tree方案所需監(jiān)測(cè)器數(shù)量超過(guò)理論最低值20%～25%，低于MLS算法5%～9%；平均節(jié)點(diǎn)度為3時(shí)，DDMA所需監(jiān)測(cè)器超過(guò)理論值5%～10%，低于MLS算法5%～8%；當(dāng)平均節(jié)點(diǎn)度為3.5時(shí)，DDMA所需監(jiān)測(cè)器數(shù)量不超過(guò)理論值5%，低于MLS算法5%～8%。DDMA算法在節(jié)點(diǎn)度較低的網(wǎng)絡(luò)中表現(xiàn)較差，其原因是節(jié)點(diǎn)度較低的網(wǎng)絡(luò)拓?fù)湫螤钇蛴诃h(huán)形網(wǎng)，而環(huán)形網(wǎng)絡(luò)難以分解為樹(shù)形結(jié)構(gòu)，不適合使用M-tree方案實(shí)現(xiàn)鏈路故障的監(jiān)測(cè)。當(dāng)網(wǎng)絡(luò)中平均節(jié)點(diǎn)度大于3.5時(shí)，DDMA算法所需監(jiān)測(cè)器數(shù)量十分接近理論最低值。而目前鐵路光傳送網(wǎng)絡(luò)中骨干層網(wǎng)絡(luò)也逐漸向網(wǎng)狀網(wǎng)演進(jìn)，鏈路數(shù)不斷增加，網(wǎng)絡(luò)平均節(jié)點(diǎn)度隨之上升，未來(lái)也更加適合使用M-tree實(shí)現(xiàn)故障監(jiān)測(cè)。同時(shí)匯聚層與接入層網(wǎng)絡(luò)拓?fù)涓訌?fù)雜，使用M-tree方案也可以降低其故障監(jiān)測(cè)成本。

為了進(jìn)一步驗(yàn)證M-tree方案在鐵路光傳送網(wǎng)絡(luò)中的表現(xiàn)，針對(duì)當(dāng)前高速鐵路骨干層中一號(hào)環(huán)、二號(hào)環(huán)、三號(hào)環(huán)和四號(hào)環(huán)的網(wǎng)絡(luò)簡(jiǎn)化拓?fù)?，使用DDMA算法為其設(shè)計(jì)M-tree監(jiān)測(cè)方案，所需監(jiān)測(cè)器數(shù)量見(jiàn)圖7。在四大環(huán)中，DDMA算法所設(shè)計(jì)M-tree方案均可以用接近理論最低的監(jiān)測(cè)器數(shù)量實(shí)現(xiàn)鏈路的故障監(jiān)測(cè)，其中一號(hào)環(huán)、三號(hào)環(huán)和四號(hào)環(huán)所需監(jiān)測(cè)器數(shù)量超過(guò)理論最低值1個(gè)，二號(hào)環(huán)中超過(guò)理論最低值2個(gè)。DDMA算法與MLS表現(xiàn)基本相同，但參考圖 5、圖6仿真結(jié)果，隨著未來(lái)高速鐵路骨干層網(wǎng)絡(luò)復(fù)雜化，其鏈路數(shù)量增加后，DDMA可獲得更優(yōu)的監(jiān)測(cè)方案。

圖7 骨干層網(wǎng)絡(luò)拓?fù)渌璞O(jiān)測(cè)器

文獻(xiàn)[12]中提出使用M-trail監(jiān)測(cè)方案實(shí)現(xiàn)高速鐵路光傳送網(wǎng)絡(luò)的鏈路故障監(jiān)測(cè)，其理論所需監(jiān)測(cè)器與激光器數(shù)量為2×log2「E+1?，但其所需的監(jiān)測(cè)波長(zhǎng)較多，影響網(wǎng)絡(luò)中業(yè)務(wù)的傳輸。M-tree監(jiān)測(cè)方案雖使用了更多的監(jiān)測(cè)器，但降低了所占用監(jiān)測(cè)波長(zhǎng)的數(shù)量。本文利用監(jiān)測(cè)代價(jià)[9]對(duì)比M-trail和M-tree兩種監(jiān)測(cè)方案，監(jiān)測(cè)代價(jià)表示為：λ·(NMN+NLD)+WLS，其中NMN、NLD分別代表監(jiān)測(cè)器和激光器的數(shù)量，WLS代表占用波長(zhǎng)數(shù)，λ為可調(diào)節(jié)系數(shù)，調(diào)節(jié)監(jiān)測(cè)器和激光器代價(jià)與波長(zhǎng)資源代價(jià)的比值。監(jiān)測(cè)代價(jià)綜合考慮監(jiān)測(cè)方案中所使用的監(jiān)測(cè)器、激光器和占用監(jiān)測(cè)波長(zhǎng)的數(shù)量，以評(píng)估當(dāng)前監(jiān)測(cè)方案的性能，結(jié)果見(jiàn)圖8。M-trail監(jiān)測(cè)方案理論所占用波長(zhǎng)資源[10]可表示為

(3)

其中

(4)

由圖8可看出，當(dāng)λ=2時(shí)，M-tree方案相比M-trail方案可節(jié)省約30%監(jiān)測(cè)代價(jià)，當(dāng)λ=3時(shí)，M-tree可降低20%左右監(jiān)測(cè)代價(jià)，而當(dāng)λ=4時(shí)，M-tree可降低10%左右監(jiān)測(cè)代價(jià)。高速鐵路光傳送網(wǎng)絡(luò)骨干層四大環(huán)中，M-trail與M-tree實(shí)現(xiàn)鏈路故障監(jiān)測(cè)所需監(jiān)測(cè)代價(jià)如表2所示，其中M-trail監(jiān)測(cè)代價(jià)為理論最低值，M-tree監(jiān)測(cè)代價(jià)為DDMA算法所得結(jié)果。綜上所述，相對(duì)于M-trail方案，DDMA算法所設(shè)計(jì)M-tree監(jiān)測(cè)方案可有效降低網(wǎng)絡(luò)中的監(jiān)測(cè)成本。

圖8 M-tree(DDMA)與M-trail所需監(jiān)測(cè)代價(jià)對(duì)比

表2 骨干層四大環(huán)所需監(jiān)測(cè)代價(jià)

圖9給出不同網(wǎng)絡(luò)拓?fù)湎翫DMA算法的運(yùn)行時(shí)間，本次仿真基于MATLAB，使用Intel?CoreTMi5-4590處理器，4 GB內(nèi)存。圖中可見(jiàn)隨著網(wǎng)絡(luò)鏈路數(shù)增加，DDMA算法運(yùn)行時(shí)間近似線性增加，在100條鏈路的網(wǎng)絡(luò)中，DDMA耗時(shí)0.169 s可得到M-tree監(jiān)測(cè)方案，此時(shí)MLS耗時(shí)0.153 s。

圖9 DDMA算法運(yùn)行時(shí)間

4 結(jié)束語(yǔ)

本文研究了M-tree監(jiān)測(cè)方案在高速鐵路光傳送網(wǎng)路中的鏈路故障定位方法，提出了DDMA算法設(shè)計(jì)M-tree監(jiān)測(cè)方案。在對(duì)M-tree進(jìn)行擴(kuò)展時(shí)，向節(jié)點(diǎn)度最大且相互之間距離最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)轉(zhuǎn)發(fā)監(jiān)測(cè)信號(hào)，以降低M-tree所需的監(jiān)測(cè)器數(shù)量，進(jìn)而降低監(jiān)測(cè)代價(jià)。將DDMA算法應(yīng)用于高速鐵路光傳送網(wǎng)絡(luò)骨干層網(wǎng)絡(luò)，為其設(shè)計(jì)鏈路監(jiān)測(cè)方案，所需監(jiān)測(cè)器數(shù)量均接近理論最小值。通過(guò)利用大量隨機(jī)網(wǎng)絡(luò)拓?fù)溥M(jìn)行仿真驗(yàn)證，結(jié)果表明，本文所提出DDMA算法在設(shè)計(jì)M-tree時(shí)，所使用監(jiān)測(cè)器數(shù)量不超過(guò)理論最低值7%，相對(duì)于現(xiàn)有M-trail監(jiān)測(cè)方法，可以節(jié)省20%～30%的監(jiān)測(cè)代價(jià)。同時(shí)隨著網(wǎng)絡(luò)鏈路數(shù)量增加，DDMA算法所需時(shí)間近似線性增長(zhǎng)，運(yùn)行所需時(shí)間較短，對(duì)高速鐵路光傳送網(wǎng)絡(luò)的故障監(jiān)測(cè)具有一定參考意義。