全光網(wǎng)中定位故障鏈路的探測(cè)選擇算法

齊小剛， 王曉琳， 劉立芳

(1. 西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，陜西 西安 710071;2. 西安電子科技大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安 710071)

在全光網(wǎng)中，故障管理是至關(guān)重要的功能塊．當(dāng)網(wǎng)絡(luò)中的光纖遭到破壞時(shí)，鏈路上的所有業(yè)務(wù)都會(huì)中斷．因此，一旦網(wǎng)絡(luò)中發(fā)生故障，就需要進(jìn)行故障診斷來(lái)定位故障發(fā)生的確切位置，從而進(jìn)行進(jìn)一步的故障分離和故障修復(fù)以恢復(fù)中斷的業(yè)務(wù)．因?yàn)槿饩W(wǎng)絡(luò)具有全光傳輸?shù)奶匦裕饴飞系闹虚g節(jié)點(diǎn)不進(jìn)行光電轉(zhuǎn)換，所以也就不能對(duì)信號(hào)采用傳統(tǒng)的電子監(jiān)測(cè)手段進(jìn)行監(jiān)測(cè)[1]．作為補(bǔ)救，文獻(xiàn)[2]研究了基于鏈路的監(jiān)測(cè)，這種監(jiān)測(cè)方法對(duì)每條鏈路單獨(dú)進(jìn)行一次測(cè)試，即通過(guò)單跳監(jiān)管光路發(fā)送光信號(hào)監(jiān)測(cè)每條鏈路，這使得發(fā)送的探測(cè)數(shù)等于網(wǎng)絡(luò)中的鏈路數(shù)．

為了減少發(fā)送的探測(cè)數(shù)，基于鏈路監(jiān)測(cè)的進(jìn)一步發(fā)展是使用一組多跳監(jiān)管光路來(lái)發(fā)送光信號(hào)，每發(fā)送1次探測(cè)可以測(cè)試多條鏈路，相關(guān)的研究包括監(jiān)測(cè)環(huán)[3]以及監(jiān)測(cè)跡[4]，一條監(jiān)管光路末端的監(jiān)測(cè)站可以獲得這條監(jiān)管光路上探測(cè)信號(hào)所經(jīng)過(guò)的一組鏈路的狀態(tài)．通過(guò)適當(dāng)?shù)胤峙湟唤M監(jiān)管光路，遠(yuǎn)程網(wǎng)絡(luò)控制中心依據(jù)監(jiān)測(cè)站觸發(fā)的告警就可以定位多條故障鏈路．

非適應(yīng)性鏈路故障定位已經(jīng)被廣泛研究[4-7]，探測(cè)信號(hào)在多條監(jiān)管光路上同時(shí)發(fā)送．文獻(xiàn)[4]給出了關(guān)于定位大型稀疏網(wǎng)絡(luò)中多條故障鏈路的隨機(jī)游走算法．隨機(jī)游走算法的目的是，使用兩個(gè)監(jiān)測(cè)站(發(fā)送方和接收方)通過(guò)多次隨機(jī)游走來(lái)構(gòu)造k分離路由矩陣去定位k條故障鏈路．為了使大型稀疏網(wǎng)絡(luò)中的每條鏈路有惟一的二進(jìn)制編碼，探測(cè)信號(hào)必須從發(fā)送方到接收方隨機(jī)地游走多次．因此，在隨機(jī)游走算法中每條鏈路會(huì)被大量的探測(cè)經(jīng)過(guò)，這將會(huì)增加發(fā)送的探測(cè)數(shù)以及每條鏈路上消耗的平均波長(zhǎng)．

筆者提出啟發(fā)式的探測(cè)選擇方法，解決了隨機(jī)游走算法中消耗大量的探測(cè)數(shù)以及波長(zhǎng)問(wèn)題．不同于隨機(jī)游走算法中的非適應(yīng)性方案，文中的思想是采用適應(yīng)性的監(jiān)測(cè)方案[3，8]．首先，需要找到用來(lái)故障檢測(cè)的監(jiān)測(cè)路徑，接著在建立的所有監(jiān)測(cè)路徑上同時(shí)發(fā)送探測(cè)信號(hào)；然后，在有故障的路徑上，按次序發(fā)送探測(cè)信號(hào)定位故障鏈路的確切位置，在定位過(guò)程中根據(jù)每次探測(cè)信號(hào)的返回結(jié)果，適應(yīng)性地調(diào)整下一次的探測(cè)路徑．

1　相關(guān)概念

圖1　在監(jiān)測(cè)路徑上發(fā)送探測(cè)定位故障鏈路

監(jiān)測(cè)路徑是一條監(jiān)管光路．在監(jiān)測(cè)路徑上發(fā)送探測(cè)可以進(jìn)行故障檢測(cè)與定位．如果監(jiān)測(cè)路徑上的一條鏈路出故障，那么在這條監(jiān)測(cè)路徑上的監(jiān)測(cè)站會(huì)由于光信號(hào)的丟失而產(chǎn)生告警[9]．在監(jiān)測(cè)路徑上發(fā)送探測(cè)信號(hào)，如果探測(cè)信號(hào)返回到監(jiān)測(cè)站，則表示在探測(cè)信號(hào)所經(jīng)過(guò)的路徑上沒(méi)有故障鏈路，否則有故障鏈路．如在圖1(a)中建立了一條監(jiān)測(cè)路徑，然后在圖1(b)中給出了在監(jiān)測(cè)路徑上依次發(fā)送兩個(gè)探測(cè)來(lái)定位故障鏈路(3，5)的過(guò)程，其中，節(jié)點(diǎn)1是監(jiān)測(cè)站，探測(cè)p1所走的路徑為1-5-3-5-1，探測(cè)p2所走的路徑為1-5-1．

2　探測(cè)選擇方法

在大型光網(wǎng)絡(luò)中，由于光纖數(shù)據(jù)連接的透明性需求，監(jiān)測(cè)站只能被放置在特殊的位置．因?yàn)槭褂玫谋O(jiān)測(cè)站越少，所需的管理花費(fèi)就越少．和隨機(jī)游走算法一致，在文中使用兩個(gè)監(jiān)測(cè)站進(jìn)行故障檢測(cè)．

2.1　故障檢測(cè)

網(wǎng)絡(luò)中出現(xiàn)故障鏈路時(shí)，首先需要建立監(jiān)測(cè)路徑，然后在建立好的監(jiān)測(cè)路徑上發(fā)送探測(cè)信號(hào)進(jìn)行故障檢測(cè)．一些監(jiān)測(cè)路徑返回故障信息后，網(wǎng)絡(luò)管理中心就可以進(jìn)行故障鏈路的定位．關(guān)于故障鏈路的檢測(cè)，要求每條鏈路至少被1條監(jiān)測(cè)路徑經(jīng)過(guò)，而面臨的問(wèn)題是如何找到可以檢測(cè)到所有鏈路狀態(tài)的最小監(jiān)測(cè)路徑集合，即就是優(yōu)化關(guān)于故障檢測(cè)所需的監(jiān)測(cè)路徑集合．如果存在故障鏈路，那么至少會(huì)有1條監(jiān)測(cè)路徑會(huì)報(bào)告故障．為了尋求能夠覆蓋所有鏈路E的最小監(jiān)測(cè)路徑集合，首先需要證明關(guān)于故障檢測(cè)的最小監(jiān)測(cè)路徑集合問(wèn)題是非確定多項(xiàng)式(Non-deterministic Polynomial，NP)完全問(wèn)題，然后再給出找到最小監(jiān)測(cè)路徑集合的啟發(fā)式算法．

2.1.1最小監(jiān)測(cè)路徑集合問(wèn)題是NP完全問(wèn)題

定理1最小監(jiān)測(cè)路徑集合等價(jià)于最小集合覆蓋問(wèn)題．

證明(最小集合覆蓋問(wèn)題?最小監(jiān)測(cè)路徑集合): 這部分要證的是最小集合覆蓋問(wèn)題的解是最小監(jiān)測(cè)路徑集合的解．最小集合覆蓋問(wèn)題的解是大小為k的集合C′，即C′覆蓋N中的每個(gè)元素．如上述構(gòu)造中提到的，如果集合Cj覆蓋元素n，相當(dāng)于與Cj對(duì)應(yīng)的監(jiān)測(cè)路徑經(jīng)過(guò)元素n對(duì)應(yīng)的鏈路e．因此，大小為k的集合C′覆蓋N中的每個(gè)元素，C′中表示的這k條監(jiān)測(cè)路徑將會(huì)經(jīng)過(guò)E中的每條鏈路．因此，表示C′中的這些監(jiān)測(cè)路徑為大小是k的監(jiān)測(cè)路徑集合．

(最小監(jiān)測(cè)路徑集合?最小集合覆蓋問(wèn)題): 這部分要證的是最小監(jiān)測(cè)路徑集合的解是最小集合覆蓋問(wèn)題的解．最小監(jiān)測(cè)路徑集合的解是大小為k的一組監(jiān)測(cè)路徑，可以經(jīng)過(guò)E中的每條鏈路．如上述構(gòu)造中提到的，如果與監(jiān)測(cè)路徑m對(duì)應(yīng)的集合Cj覆蓋與鏈路e對(duì)應(yīng)的元素n，則監(jiān)測(cè)路徑m經(jīng)過(guò)鏈路e．因此，如果監(jiān)測(cè)路徑集合中的k條監(jiān)測(cè)路徑經(jīng)過(guò)所有節(jié)點(diǎn)，則與k條監(jiān)測(cè)路徑對(duì)應(yīng)的k個(gè)集合將覆蓋鏈路所表示的所有元素．

2.1.2監(jiān)測(cè)路徑集合選擇的啟發(fā)式算法

關(guān)于故障檢測(cè)的監(jiān)測(cè)路徑選擇算法是基于啟發(fā)式的算法來(lái)選擇監(jiān)測(cè)路徑進(jìn)行故障檢測(cè)的．通過(guò)構(gòu)造監(jiān)測(cè)路徑使得每條鏈路至少被1條監(jiān)測(cè)路徑經(jīng)過(guò)．

算法1故障檢測(cè)的監(jiān)測(cè)路徑選擇．

輸入: 網(wǎng)絡(luò)拓?fù)銰(V，E)，兩個(gè)監(jiān)測(cè)站(一個(gè)發(fā)送方s，一個(gè)接收方t)．

輸出: 監(jiān)測(cè)路徑集合M．

初始化每條鏈路上的計(jì)數(shù)器ρ(ei)=0(i=1，2，…，|E|);

獨(dú)立地構(gòu)造M的每一行的過(guò)程如下:

while(?ρ(ei)=0)

在G中找一條從s到t的隨機(jī)游走mj(mj?M);

把mj放入M中;

對(duì)mj經(jīng)過(guò)的每條鏈路ei執(zhí)行ρ(ei)++;

end while.

在算法1中使用了局部稀缺最優(yōu)策略，其思想是在每條鏈路ei上安裝一個(gè)計(jì)數(shù)器ρ(ei) (i=1，2，…，|E|)，ρ(ei)表示每條鏈路上經(jīng)過(guò)的監(jiān)測(cè)路徑的數(shù)目．這樣就可以控制從發(fā)送方s到接收方t的隨機(jī)游走，即不是隨機(jī)選擇一個(gè)鄰居節(jié)點(diǎn)進(jìn)行隨機(jī)游走，而是選擇計(jì)數(shù)器上數(shù)值最小的鏈路進(jìn)行游走．當(dāng)在G上找到一條從s到t的隨機(jī)游走mj，則在由mj經(jīng)過(guò)的所有鏈路上的計(jì)數(shù)器加1．算法終止的條件是每條鏈路上的計(jì)數(shù)器ρ(ei)≠ 0，即就是每條鏈路至少被1條監(jiān)測(cè)路徑經(jīng)過(guò)．因此，最小監(jiān)測(cè)路徑集合問(wèn)題就被解決了．最后可以得到一組監(jiān)測(cè)路徑M，即就是最小監(jiān)測(cè)路徑集合．在M中的所有監(jiān)測(cè)路徑上同時(shí)發(fā)送探測(cè)來(lái)進(jìn)行故障檢測(cè)．

2.2　故障定位

當(dāng)算法1生成監(jiān)測(cè)路徑集合后，如果存在故障鏈路，則開(kāi)始進(jìn)行故障鏈路定位．當(dāng)網(wǎng)絡(luò)中的故障鏈路被一條監(jiān)測(cè)路徑上的探測(cè)信號(hào)探測(cè)到時(shí)，將會(huì)在這條監(jiān)測(cè)路徑上發(fā)送更多的探測(cè)．這個(gè)故障表示在這條故障的監(jiān)測(cè)路徑上存在1個(gè)或多個(gè)故障鏈路．但是，這些探測(cè)可能不會(huì)精確地定位故障鏈路的具體位置．因此，在這些有故障的監(jiān)測(cè)路徑上將會(huì)發(fā)送更多的探測(cè)來(lái)定位故障鏈路．故障定位需要發(fā)送的探測(cè)數(shù)要使得有故障的監(jiān)測(cè)路徑上的所有鏈路的狀態(tài)可以被判斷出來(lái)．

在故障定位過(guò)程中使用一個(gè)監(jiān)測(cè)站，從監(jiān)測(cè)站發(fā)出的探測(cè)信號(hào)最終會(huì)返回到這個(gè)監(jiān)測(cè)站．因此探測(cè)所走的路徑相當(dāng)于是一條環(huán)路，即每條鏈路上有互反方向的兩個(gè)波長(zhǎng)．如圖1(b)探測(cè)p1所走的路徑是1-5-3-5-1，實(shí)際探測(cè)所監(jiān)測(cè)的范圍是1-5-3，這樣可以引入折半查找的思想來(lái)進(jìn)行快速的故障定位．算法2是基于折半查找方法[3]來(lái)明確地定位所有故障鏈路．在折半查找的方法中，對(duì)每條有故障的監(jiān)測(cè)路徑進(jìn)行獨(dú)立的查找．在每條故障的監(jiān)測(cè)路徑上，第1次探測(cè)是從監(jiān)測(cè)站發(fā)送到監(jiān)測(cè)路徑的中間點(diǎn)．如果探測(cè)失敗，則接著對(duì)第1次探測(cè)所經(jīng)過(guò)的路徑的前半部分發(fā)送探測(cè)；否則，以相同的方式對(duì)監(jiān)測(cè)路徑的后半部分進(jìn)行探測(cè)．

算法2故障定位的探測(cè)選擇．

輸入: 監(jiān)測(cè)路徑集合M，1個(gè)監(jiān)測(cè)站．

輸出: 故障鏈路集合F．

由算法1得到監(jiān)測(cè)路徑集合M;

for(M中的每條監(jiān)測(cè)路徑)

在所有的監(jiān)測(cè)路徑上同時(shí)發(fā)送探測(cè)信號(hào);

//faultylink(a，b)表示節(jié)點(diǎn)a和節(jié)點(diǎn)b之間的鏈路是故障的

flag←Binarysearch(p，low，high，faultylink(a，b))

while(flag為false)//如果鏈路是故障的，則找到替換路徑

把faultylink(a，b)放入F中;

在節(jié)點(diǎn)a和節(jié)點(diǎn)b之間找到的最短路徑替換faultylink(a，b);

flag←Binarysearch(p，low，high，faultylink(a，b));

end while.

end for.

折半查找在每條監(jiān)測(cè)路徑上只能識(shí)別出1條故障鏈路．在每條監(jiān)測(cè)路徑上，由于探測(cè)信號(hào)不能在故障鏈路上進(jìn)行傳送，所以故障鏈路后面的鏈路狀態(tài)無(wú)法判斷出來(lái)．因此，當(dāng)在1條監(jiān)測(cè)路徑上定位出1條故障鏈路后，找一條最短路徑替換這條故障鏈路，也就是在與故障鏈路相鄰的兩個(gè)節(jié)點(diǎn)間找到這條最短路徑．這個(gè)過(guò)程一直持續(xù)到這條監(jiān)測(cè)路徑上的所有故障鏈路都被識(shí)別出來(lái)．圖2給出示例，節(jié)點(diǎn)4的度為3，網(wǎng)絡(luò)中有3條故障鏈路，一條探測(cè)所走的路徑是1-4-3-4-1，實(shí)際的探測(cè)信號(hào)監(jiān)測(cè)范圍是1-4-3．圖2在路徑1-4-3-4-1上使用折半查找方法可以定位出故障鏈路(1，4)，但是不能定位出故障鏈路(3，4)．由于在節(jié)點(diǎn)1和節(jié)點(diǎn)4之間不能找到無(wú)故障的替換路徑，所以在監(jiān)測(cè)路徑1-4-3上故障鏈路(1，4)后面的故障鏈路(3，4)不能被定位到．

圖2 在3邊連通的網(wǎng)絡(luò)中的3條故障鏈路圖3 k條鏈路組成圖中的割

定理2用1個(gè)監(jiān)測(cè)站來(lái)定位所有可能的k條故障鏈路的充分必要條件是網(wǎng)絡(luò)為k+1 邊連通的．

證明通過(guò)反證法來(lái)證明充分性．假設(shè)網(wǎng)絡(luò)是k邊連通的而不是k+1邊連通的．因?yàn)榫W(wǎng)絡(luò)不是k+1 邊連通的，所以如圖3存在一組k條鏈路，刪掉它們后網(wǎng)絡(luò)變得不連通，標(biāo)記這些鏈路為l1，l2，…，lk．現(xiàn)在假設(shè)這k條鏈路都是故障的，當(dāng)通過(guò)折半查找方法定位到故障鏈路l1后，不能找到健康的替換路徑來(lái)替換掉l1，因?yàn)榫W(wǎng)絡(luò)是k邊連通的，而且這k條鏈路都是故障的．因此，當(dāng)l1和li(li∈ (l2，…，lk))在同一監(jiān)測(cè)路徑上時(shí)，l1后面的故障(li)不能被監(jiān)測(cè)站定位到，引出矛盾．因此，在k邊連通的網(wǎng)絡(luò)中不能定位出k條故障鏈路，即就是k+1 邊連通是構(gòu)造探測(cè)集合的充分條件．

通過(guò)構(gòu)造法來(lái)證明必要性．因?yàn)榫W(wǎng)絡(luò)是k+1邊連通的，網(wǎng)絡(luò)中的任意k條故障鏈路故障使得網(wǎng)絡(luò)至少是1邊連通的．對(duì)于任意一個(gè)故障鏈路，總能找到健康的替換路徑并使用折半查找方法來(lái)定位同一監(jiān)測(cè)路徑上的其他故障鏈路．因此，總能找到這樣的探測(cè)來(lái)定位k條故障鏈路．

在折半查找過(guò)程中，low表示探測(cè)的起始點(diǎn)，high表示探測(cè)的終止點(diǎn)．探測(cè)所走的路徑是low-high-low，實(shí)際探測(cè)所監(jiān)測(cè)的范圍R是low-high．在監(jiān)測(cè)站發(fā)送每次探測(cè)的開(kāi)始，low是0，high是 |m|-1，|m|表示監(jiān)測(cè)路徑的長(zhǎng)度．因此，初始的mid是 (|m|- 1)/2>．監(jiān)測(cè)站將在監(jiān)測(cè)路徑上發(fā)送初始的探測(cè)，其探測(cè)的終點(diǎn)為high節(jié)點(diǎn)．p表示發(fā)送的探測(cè)，flag為折半查找的返回值．當(dāng)flag為真時(shí)，探測(cè)路徑上不存在故障鏈路；否則，返回一條故障鏈路．

為了減少計(jì)算時(shí)間，一條從發(fā)送方s開(kāi)始到接收方t的隨機(jī)游走所經(jīng)過(guò)的節(jié)點(diǎn)被存放在vector容器中．由算法2得到的故障鏈路集合F被存放在內(nèi)部數(shù)據(jù)結(jié)構(gòu)中(C++中的std::set)，使得找到的F中不存在重復(fù)的故障鏈路．每條鏈路上的計(jì)數(shù)器ρ(ei)存放在平衡二叉查找樹(shù)上(C++中的std::map)，這提供了快速查找和修改功能．當(dāng)執(zhí)行一條隨機(jī)游走mj時(shí)，則需要更新被這條隨機(jī)游走經(jīng)過(guò)的所有鏈路上的計(jì)數(shù)器．

3　仿真結(jié)果

在Visual studio 2010上模擬全光網(wǎng)故障定位仿真系統(tǒng)，依據(jù)BA模型[10]生成平均節(jié)點(diǎn)度為2和3，節(jié)點(diǎn)范圍為50～500，鏈路數(shù)從100到500的大型無(wú)標(biāo)度網(wǎng)絡(luò)，在生成的大型無(wú)標(biāo)度網(wǎng)絡(luò)上測(cè)試隨機(jī)游走[4]算法和探測(cè)選擇算法的性能．對(duì)于生成的每一個(gè)無(wú)標(biāo)度網(wǎng)絡(luò)，在故障檢測(cè)過(guò)程中，固定兩個(gè)最大度節(jié)點(diǎn)，分別為發(fā)送方和接收方(兩個(gè)監(jiān)測(cè)站)，以及任意選擇一個(gè)最大度節(jié)點(diǎn)作為故障定位過(guò)程中的監(jiān)測(cè)站．文中給出發(fā)送的探測(cè)數(shù)和每條鏈路上探測(cè)相關(guān)的平均波長(zhǎng)數(shù)的仿真結(jié)果．由于在故障檢測(cè)過(guò)程中所有的探測(cè)信號(hào)在監(jiān)測(cè)路徑上同時(shí)發(fā)送，則會(huì)造成每條鏈路上消耗過(guò)多的監(jiān)測(cè)資源[11-12]．而在故障定位過(guò)程中每條探測(cè)在監(jiān)測(cè)路徑上按次序發(fā)送，探測(cè)經(jīng)過(guò)的每條鏈路上消耗單個(gè)波長(zhǎng)[13]，因此，文中只考慮故障檢測(cè)過(guò)程中平均每條鏈路上消耗的監(jiān)測(cè)波長(zhǎng)．通過(guò)統(tǒng)計(jì)定位故障所發(fā)送的探測(cè)和每個(gè)探測(cè)的路徑長(zhǎng)度，來(lái)得出仿真結(jié)果要呈現(xiàn)的探測(cè)數(shù)和平均每條鏈路上消耗的監(jiān)測(cè)波長(zhǎng)．探測(cè)選擇算法運(yùn)行結(jié)果的仿真圖描繪的每一點(diǎn)為在不同網(wǎng)絡(luò)拓?fù)渖?00次實(shí)驗(yàn)的平均值，而隨機(jī)游走算法的結(jié)果是通過(guò)不斷地增加監(jiān)測(cè)跡的數(shù)量來(lái)找到能夠惟一定位故障鏈路所需的監(jiān)測(cè)跡的數(shù)量，即就是發(fā)送的探測(cè)的數(shù)量．

3.1　在平均節(jié)點(diǎn)度為2的網(wǎng)絡(luò)中定位所有的單鏈路故障

由BA模型生成無(wú)標(biāo)度網(wǎng)絡(luò)的過(guò)程可以知道平均節(jié)點(diǎn)度為2的網(wǎng)絡(luò)的邊連通度為2．依據(jù)定理2，在邊連通度為2的網(wǎng)絡(luò)中所有的單鏈路故障可以被定位出來(lái)．圖4(a)給出了在平均節(jié)點(diǎn)度為2的網(wǎng)絡(luò)中定位所有單鏈路故障時(shí)，隨機(jī)游走算法和探測(cè)選擇算法需要發(fā)送的探測(cè)數(shù)．從圖4(a)可以看出，隨機(jī)游走算法比探測(cè)選擇算法需要發(fā)送更多的探測(cè)．圖4(b)給出了在定位所有單鏈路故障時(shí)兩種算法消耗的平均波長(zhǎng)數(shù)的對(duì)比．為了在平均節(jié)點(diǎn)度為2的網(wǎng)絡(luò)中定位所有的單鏈路故障，探測(cè)選擇算法在每條鏈路上大約需要的平均波長(zhǎng)數(shù)為6，而隨機(jī)游走算法在每條鏈路上大約消耗的波長(zhǎng)是22．

圖4　平均節(jié)點(diǎn)度為2的網(wǎng)絡(luò)中隨機(jī)游走算法和探測(cè)選擇算法的性能

3.2　在平均節(jié)點(diǎn)度為3的網(wǎng)絡(luò)中定位任意兩條鏈路故障

基于BA模型，平均節(jié)點(diǎn)度為3的網(wǎng)絡(luò)的邊連通度為3．圖5(a)給出了定位平均節(jié)點(diǎn)度為3的網(wǎng)絡(luò)中的任意兩條故障鏈路時(shí)，隨機(jī)游走算法和探測(cè)選擇算法所需發(fā)送的探測(cè)數(shù)．對(duì)比探測(cè)選擇算法，圖5(a)表明隨機(jī)游走算法需要更多的探測(cè)，圖5(b)比較了定位任意兩條鏈路故障時(shí)，兩種算法在每條鏈路上需要的平均波長(zhǎng)數(shù)．在每條鏈路上，探測(cè)選擇算法大約需要的波長(zhǎng)數(shù)為5，而隨機(jī)游走算法需要的波長(zhǎng)數(shù)大約為20．

圖5　平均節(jié)點(diǎn)度為3的網(wǎng)絡(luò)中隨機(jī)游走算法和探測(cè)選擇算法的性能

文中也研究了算法的穩(wěn)健性，可通過(guò)增加鏈路數(shù)來(lái)增加網(wǎng)絡(luò)規(guī)模．如圖4(a)和5(a)所示，隨著網(wǎng)絡(luò)規(guī)模的增加，定位鏈路故障所需的探測(cè)數(shù)也在增加．因?yàn)殒溌窋?shù)越多，定位越困難．

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

文中研究了全光網(wǎng)中使用適應(yīng)性探測(cè)方案定位故障鏈路的探測(cè)選擇算法，證明了最小監(jiān)測(cè)路徑集合問(wèn)題是NP完全問(wèn)題，接著通過(guò)啟發(fā)式的監(jiān)測(cè)路徑選擇算法來(lái)找到最小監(jiān)測(cè)路徑集合．進(jìn)一步提出了在網(wǎng)絡(luò)連通度方面用一個(gè)監(jiān)測(cè)站來(lái)定位故障鏈路的充分必要條件．探測(cè)選擇算法首先獲得關(guān)于故障檢測(cè)的一組監(jiān)測(cè)路徑，接著在有故障的監(jiān)測(cè)路徑上按次序發(fā)送探測(cè)信號(hào)來(lái)進(jìn)行故障定位，避免了隨機(jī)游走算法中消耗的大量探測(cè)和波長(zhǎng)問(wèn)題．仿真結(jié)果表明，探測(cè)選擇算法有更優(yōu)越的性能，具有很強(qiáng)的實(shí)際意義．

參考文獻(xiàn)：

[1] 熊余, 董先存, 李圓圓, 等. 軟件定義光網(wǎng)絡(luò)中基于最小點(diǎn)覆蓋的控制平面跨層生存性設(shè)計(jì)[J]. 電子與信息學(xué)報(bào), 2016, 38(5): 1211-1218.

XIONG Yu, DONG Xiancun, LI Yuanyuan, et al. The Cross-layer Survivable Design of Control Plane Based on Minimum Point Covering in Software Defined Optical Network[J]. Journal of Electronics & Information Technology, 2016, 38(5): 1211-1218.

[2]HARVEY N J A, PATRASCU M, WEN Y G, et al. Non-adaptive Fault Diagnosis for All-optical Networks via Combinatorial Group Testing on Graphs[C]//Proceedings of the 2007 26th IEEE International Conference on Computer Communications. Piscataway: IEEE, 2007: 697-705.

[3]ALI M L, HO P H, TAPOLCAI J. SRLG Failure Localization Using Nested M-trails and Their Application to Adaptive Probing[J]. Networks, 2015, 66(4): 347-363.

[4]XUAN Y, SHEN Y, NGUYEN N P, et al. Efficient Multi-link Failure Localization Schemes in All-optical Networks[J]. IEEE Transactions on Communications, 2013, 61(3): 1144-1151.

[5]ALI M L, HO P H, TAPOLCAI J. A Novel M-trail Allocation Method for SRLG Fault Localization in All-optical Networks[J]. Optical Switching and Networking, 2017, 23(2): 179-188.

[6]TAPOLCAI J, RONYAI L, HOSSZU E, et al. Signaling Free Localization of Node Failures in All-optical Networks[C]//Proceedings of the 2014 IEEE Conference on Computer Communications. Piscataway: IEEE, 2014: 1860-1868.

[7] 劉英挺, 朱睿杰, 杜曉明, 等. 全光網(wǎng)中采用可信度模型的故障定位技術(shù)[J]. 西安電子科技大學(xué)學(xué)報(bào), 2016, 43(6): 152-157.

LIU Yingting, ZHU Ruijie, DU Xiaoming, et al. Mechanism for Fault Location Based on the Credibility Model of All Optical Networks[J]. Journal of Xidian University, 2016, 43(6): 152-157.

[8]NATU M, SETHI A S, LLOYD E L. Efficient Probe Selection Algorithms for Fault Diagnosis[J]. Telecommunication Systems, 2008, 37(1/3): 109-125.

[9]張新, 常義林, 孫方濤, 等. 一種改進(jìn)的網(wǎng)絡(luò)故障監(jiān)測(cè)算法[J]. 西安電子科技大學(xué)學(xué)報(bào), 2006, 33(3): 416-421.

ZHANG Xin, CHANG Yilin, SUN Fangtao, et al. An Improved Algorithm for Monitoring the Network Fault[J]. Journal of Xidian University, 2006, 33(3): 416-421.

[10]ALBERT R, BARABASI A L. Statistical Mechanics of Complex Networks[J]. Quantitative Biology, 2001, 74(1): 47-97.

[11]THAI M T. Group Testing Theory in Network Security: Advanced Solution[M]. New York: Springer, 2012: 3-4.

[12]ALI M L, HO P H, TAPOLCAI J. SRLG Fault Localization Using Nested M-trails[J]. Computer Networks, 2015, 85: 63-79.

[13]WANG B, HO P H. Energy-efficient Routing and Bandwidth Allocation in OFDM-based Optical Networks[J]. Journal of Optical Communications and Networking, 2016, 8(2): 71-84.