齊小剛，汪直平，李家慧，劉立芳

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

有效的故障管理方法是保證網(wǎng)絡(luò)可靠運(yùn)行的基礎(chǔ)。在大規(guī)模網(wǎng)絡(luò)中，由于故障的負(fù)面影響，一個(gè)設(shè)備的故障可能會(huì)導(dǎo)致多個(gè)設(shè)備相繼發(fā)生故障。及時(shí)檢測(cè)并定位出故障是進(jìn)行故障恢復(fù)的前提，能夠減少故障造成的代價(jià)?，F(xiàn)有的故障檢測(cè)技術(shù)主要分為3 類：被動(dòng)監(jiān)測(cè)、主動(dòng)探測(cè)和網(wǎng)絡(luò)層析成像。被動(dòng)監(jiān)測(cè)技術(shù)通過(guò)部署在網(wǎng)絡(luò)設(shè)備上的監(jiān)視代理產(chǎn)生警報(bào)來(lái)為網(wǎng)絡(luò)管理系統(tǒng)提供故障信息。主動(dòng)探測(cè)技術(shù)通過(guò)發(fā)送稱為探針的數(shù)據(jù)包來(lái)執(zhí)行網(wǎng)絡(luò)監(jiān)視，能夠檢測(cè)網(wǎng)絡(luò)的異常并及時(shí)定位異常的根源。主動(dòng)探測(cè)又分為預(yù)計(jì)劃探測(cè)與自適應(yīng)探測(cè)兩種[1-5]。自適應(yīng)探測(cè)將故障診斷過(guò)程劃分為故障檢測(cè)和故障定位。在故障檢測(cè)過(guò)程中，探測(cè)站發(fā)送的探針能夠檢查網(wǎng)絡(luò)中所有組件的健康狀況。確定了可疑的故障區(qū)域，將發(fā)送額外的探針達(dá)到故障定位的目的。與預(yù)計(jì)劃探測(cè)相比，自適應(yīng)探測(cè)更加靈活且開(kāi)銷較小。網(wǎng)絡(luò)層析成像技術(shù)是一種用于監(jiān)測(cè)鏈路性能的方法。該方法通過(guò)端到端測(cè)量來(lái)識(shí)別加性鏈路指標(biāo)，如延遲、損失率等，為網(wǎng)絡(luò)監(jiān)測(cè)、負(fù)載均衡和故障診斷提供了高效的方式。

Natu 等[4]最先提出了基于自適應(yīng)探測(cè)技術(shù)的探針選擇算法。該算法主要包括貪婪故障檢測(cè)算法GFD 和貪婪故障定位算法GFL，能夠很好地用于檢測(cè)和定位網(wǎng)絡(luò)中的少量節(jié)點(diǎn)故障。Lu 等[6]提出了一種新的故障檢測(cè)方法，目的是為了減輕基于主動(dòng)探測(cè)引起的網(wǎng)絡(luò)開(kāi)銷。該方法將整個(gè)網(wǎng)絡(luò)的檢測(cè)過(guò)程分為幾個(gè)階段。在每個(gè)階段，只使用少量探針檢測(cè)網(wǎng)絡(luò)中的部分節(jié)點(diǎn)。Zheng 等[7]提出了一種最小化探測(cè)成本的探測(cè)路徑選擇方法。該方法選擇一組探測(cè)路徑，這些路徑對(duì)于實(shí)現(xiàn)可識(shí)別性和覆蓋無(wú)法識(shí)別的目標(biāo)鏈路最有用。Gyimothi 等[8-9]研究了單節(jié)點(diǎn)故障定位的探測(cè)路徑分配問(wèn)題，提出了遞歸匹配收縮算法 RMCA 來(lái)定位網(wǎng)絡(luò)中的任何單個(gè)節(jié)點(diǎn)故障。Lin 等[10]考慮最小化探針的數(shù)量和鏈路負(fù)載，并提出了一種選擇探測(cè)路徑的新方法。該方法對(duì)貪婪算法進(jìn)行參數(shù)化，用來(lái)在探針數(shù)量和網(wǎng)絡(luò)組件負(fù)載這兩個(gè)目標(biāo)上面達(dá)到平衡。Dusia 等[11]提出了一種探針生成算法來(lái)生成候選探針集，從算法生成的候選探針集里選擇探針能夠降低監(jiān)視網(wǎng)絡(luò)的成本。在最近的研究中，Tayal 等[12]認(rèn)為應(yīng)該將探針的長(zhǎng)度限制在某個(gè)常數(shù)K上以減少探針的往返時(shí)間，并提出了根據(jù)網(wǎng)絡(luò)中的鏈路流量測(cè)量結(jié)果動(dòng)態(tài)地選擇探針進(jìn)行故障檢測(cè)。

在多故障定位的研究中，Wu 等[13-17]針對(duì)全光網(wǎng)絡(luò)中的共享風(fēng)險(xiǎn)鏈路組(shared risk link group,SRLG)故障定位問(wèn)題提出了幾種方法。然而，這些方法只適用于小規(guī)模網(wǎng)絡(luò)中的鏈路故障定位。Xuan 等[18]提出了隨機(jī)游走算法RWL 來(lái)解決大規(guī)模網(wǎng)絡(luò)中的多鏈路故障定位問(wèn)題。該算法可擴(kuò)展到多節(jié)點(diǎn)故障定位問(wèn)題中，通過(guò)隨機(jī)游走構(gòu)造一個(gè)探測(cè)路徑與節(jié)點(diǎn)相關(guān)的d-分離矩陣，然后使用探針定位多節(jié)點(diǎn)故障。然而這種非適應(yīng)性方法造成的誤判率和探測(cè)成本較高，無(wú)法滿足多節(jié)點(diǎn)故障定位的要求。Ma 等[19]首先研究了使用網(wǎng)絡(luò)層析成像的方法來(lái)識(shí)別通信網(wǎng)絡(luò)中所有鏈路的問(wèn)題，并提出了最少監(jiān)視器布置算法MMP。在此基礎(chǔ)上，大量研究[20-22]將監(jiān)視器放置問(wèn)題擴(kuò)展到靜態(tài)和動(dòng)態(tài)通信網(wǎng)絡(luò)中的優(yōu)先鏈路層析成像。此外，Ma 等[23]將網(wǎng)絡(luò)層析成像技術(shù)運(yùn)用于多節(jié)點(diǎn)故障定位的監(jiān)視器布置問(wèn)題中。

本文針對(duì)現(xiàn)有故障定位算法在多節(jié)點(diǎn)故障定位中準(zhǔn)確率低、探測(cè)成本高的問(wèn)題，提出了基于主動(dòng)探測(cè)的探測(cè)路徑選擇算法。該算法結(jié)合了貪婪路徑選擇和禁忌鏈路搜索兩種方法，能夠根據(jù)每次的探測(cè)結(jié)果更新候選路徑集以選擇最合適的探測(cè)路徑進(jìn)行故障定位。在故障檢測(cè)過(guò)程中，使用貪婪路徑選擇算法為探針選擇探測(cè)路徑減少故障檢測(cè)的成本。在故障定位過(guò)程中，使用禁忌鏈路搜索算法為每個(gè)可疑節(jié)點(diǎn)選擇最合適的探測(cè)路徑提高成功定位率。

1 基本概念

1.1 問(wèn)題描述

假設(shè)網(wǎng)絡(luò)拓?fù)涫且阎?，并將其建模為無(wú)向連通圖G=(V,E)，其中V，E分別表示節(jié)點(diǎn)集和邊集。網(wǎng)絡(luò)中一些節(jié)點(diǎn)被選擇為探測(cè)站節(jié)點(diǎn)用來(lái)放置探測(cè)站，能夠發(fā)送被稱為探針的探測(cè)數(shù)據(jù)包并收集探測(cè)結(jié)果。探測(cè)站布置的基本要求是能夠發(fā)送探針探測(cè)到所有節(jié)點(diǎn)。用于故障檢測(cè)和定位的探針能夠沿著指定的探測(cè)路徑進(jìn)行傳輸并檢測(cè)路徑上的所有節(jié)點(diǎn)。在主動(dòng)探測(cè)方法中，探針的長(zhǎng)度決定了探針探測(cè)的往返時(shí)間。在實(shí)際網(wǎng)絡(luò)中，探針的長(zhǎng)度應(yīng)該根據(jù)實(shí)際需求進(jìn)行限制以減少探測(cè)時(shí)間。顯然地，探針長(zhǎng)度的閾值K的值越大，探測(cè)成本可能越小，但是探測(cè)時(shí)間會(huì)增加。我們假設(shè)所有的探測(cè)站節(jié)點(diǎn)都為正常節(jié)點(diǎn)，并且探測(cè)數(shù)據(jù)包對(duì)節(jié)點(diǎn)的影響可以忽略不計(jì)。我們定義多節(jié)點(diǎn)故障定位的問(wèn)題如下所示，其中探測(cè)成本定義為用于故障檢測(cè)和定位的探測(cè)路徑的數(shù)量。

定義1(多節(jié)點(diǎn)故障定位) 給定無(wú)向連通圖G=(V,E)和一組探測(cè)站節(jié)點(diǎn)PS，其中V表示節(jié)點(diǎn)集，E表示邊集。假設(shè)V中的k(k>1)個(gè)節(jié)點(diǎn)發(fā)生故障，選擇一組最少數(shù)量的探測(cè)路徑并發(fā)送探針來(lái)識(shí)別出所有故障節(jié)點(diǎn)。

圖1 顯示了在不同網(wǎng)絡(luò)中使用現(xiàn)有探測(cè)路徑選擇算法選擇探測(cè)路徑識(shí)別目標(biāo)節(jié)點(diǎn)。在圖1(a)中，當(dāng)節(jié)點(diǎn)4、5 和8 發(fā)生故障時(shí)，探測(cè)站節(jié)點(diǎn)1和2 沿著探測(cè)路徑p18(1-5-8)和p28(2-4-6-8)發(fā)送探針無(wú)法定位出節(jié)點(diǎn)8 的故障。然而，探測(cè)站節(jié)點(diǎn)3 沿著探測(cè)路徑p37(3-7-8)可以明確定位出節(jié)點(diǎn)8 的故障。在圖1(b)中，選擇不合適的探測(cè)路徑p25(2-3-4-5)和p65(6-4-5)進(jìn)行故障定位會(huì)導(dǎo)致節(jié)點(diǎn)5 的狀態(tài)無(wú)法被識(shí)別出，因?yàn)樵谶x擇的探測(cè)路徑上存在故障節(jié)點(diǎn)4。

圖1 選擇探測(cè)路徑識(shí)別目標(biāo)節(jié)點(diǎn)Fig.1 Selecting probing paths to identify the target node

1.2 候選路徑權(quán)重

在選擇探測(cè)站節(jié)點(diǎn)后，可以通過(guò)計(jì)算探測(cè)站節(jié)點(diǎn)到其余節(jié)點(diǎn)的最短路徑生成候選路徑集CP。在以往的方法中，使用了最大搜索、最小搜索和二進(jìn)制搜索從候選路徑中選擇探測(cè)路徑，忽略了探測(cè)數(shù)據(jù)包對(duì)鏈路負(fù)載的影響。因此，從候選路徑集中選擇探測(cè)路徑之前，我們首先定義探測(cè)路徑p的權(quán)重：

式中：n(l)代表當(dāng)前已選擇探測(cè)路徑經(jīng)過(guò)邊l的次數(shù)；L(p)代表路徑p上的所有鏈路集合。在故障檢測(cè)過(guò)程中，|M(p)|代表候選探測(cè)路徑p上所有未被覆蓋節(jié)點(diǎn)的數(shù)量。在故障定位過(guò)程中，|M(p)|代表候選探測(cè)路徑p上所有可疑節(jié)點(diǎn)的數(shù)量。

2 探測(cè)路徑選擇算法

2.1 貪婪路徑選擇

故障檢測(cè)是網(wǎng)絡(luò)中故障診斷的第一步。為了保證網(wǎng)絡(luò)的正常運(yùn)行，需要快速、準(zhǔn)確的故障檢測(cè)方法。在自適應(yīng)探測(cè)方法中，故障檢測(cè)的目地是找到網(wǎng)絡(luò)中可能出現(xiàn)故障的區(qū)域，從而減少用于準(zhǔn)確定位故障節(jié)點(diǎn)的探針數(shù)量。應(yīng)該選擇適當(dāng)?shù)奶綔y(cè)路徑，以便在網(wǎng)絡(luò)中存在故障時(shí)，發(fā)送的探針可以檢測(cè)到故障。探測(cè)路徑選擇問(wèn)題是NP難的，常用貪婪算法來(lái)近似求解。

算法1 給出了用于故障檢測(cè)的貪婪路徑選擇算法。該算法使用Dijkstra 最短路徑算法計(jì)算所有可能的候選探測(cè)路徑。對(duì)于每條候選探測(cè)路徑，使用式(1)為其計(jì)算一個(gè)權(quán)重。在每次選擇探測(cè)路徑過(guò)程中，選擇的探測(cè)路徑具有最小的權(quán)重。探針的傳輸會(huì)對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)和鏈路造成額外的開(kāi)銷。權(quán)重較小的探測(cè)路徑意味著發(fā)送的探針對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)和鏈路產(chǎn)生較小的干擾，且能夠盡可能多地覆蓋未覆蓋的節(jié)點(diǎn)。算法迭代地選擇探測(cè)路徑直到網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都至少被一條路徑所覆蓋。沿著探測(cè)路徑發(fā)送的探針能夠檢測(cè)出故障可能發(fā)生的區(qū)域。如果一個(gè)節(jié)點(diǎn)故障，則通過(guò)該節(jié)點(diǎn)的所有探針將失效。

算法1 故障檢測(cè)的貪婪路徑選擇算法

圖2 顯示了在包含6 個(gè)節(jié)點(diǎn)的簡(jiǎn)單網(wǎng)絡(luò)中使用貪婪路徑選擇算法選擇探測(cè)路徑進(jìn)行故障檢測(cè)，其中節(jié)點(diǎn)1 和4 為探測(cè)站節(jié)點(diǎn)。通過(guò)Dijkstra 最短路徑算法計(jì)算出了一組候選路徑CP={p12,p13,p14,p15,p16,p42,p43,p45,p46}，其中pij表示探測(cè)站節(jié)點(diǎn)vi到節(jié)點(diǎn)vj的最短路徑。算法首先選擇具有最小權(quán)重的候選路徑p45(4-3-6-5)。為了覆蓋剩余未覆蓋的節(jié)點(diǎn)1 和2，從剩余候選路徑集中選擇權(quán)重最小的路徑p12(1-2)。此時(shí)，所有節(jié)點(diǎn)都被選定的探測(cè)路徑覆蓋。因此，沿探測(cè)路徑p45和p12發(fā)送的兩個(gè)探針可以檢測(cè)該網(wǎng)絡(luò)中的任何節(jié)點(diǎn)。

圖2 選擇探測(cè)路徑進(jìn)行故障檢測(cè)Fig.2 Selecting probing paths for fault detection

2.2 禁忌鏈路搜索

在以前的方法中，使用最大搜索或最小搜索選擇的探測(cè)路徑僅適用于定位單節(jié)點(diǎn)故障。當(dāng)故障節(jié)點(diǎn)較多時(shí)，所選探測(cè)路徑可能會(huì)遍歷多個(gè)故障節(jié)點(diǎn)，導(dǎo)致發(fā)送的探針無(wú)法準(zhǔn)確定位多個(gè)節(jié)點(diǎn)故障。

考慮到一些難以被識(shí)別的節(jié)點(diǎn)，以前的探測(cè)路徑選擇方法不能滿足多節(jié)點(diǎn)故障定位的要求。一種可能的解決方案是根據(jù)探測(cè)結(jié)果不斷更新候選探測(cè)路徑集并選擇更合適的探測(cè)路徑。如果沿著選定的探測(cè)路徑發(fā)送的探針能夠識(shí)別出所有故障節(jié)點(diǎn)，那么算法將停止并返回故障節(jié)點(diǎn)。否則，為剩余可疑節(jié)點(diǎn)生成新的候選路徑集并選擇探測(cè)路徑，直到識(shí)別出所有故障節(jié)點(diǎn)或新的候選路徑集為空。

算法2 給出了用于故障定位的禁忌鏈路搜索算法。網(wǎng)絡(luò)中的所有節(jié)點(diǎn)可以被分為3 類：正常節(jié)點(diǎn)、故障節(jié)點(diǎn)和未知節(jié)點(diǎn)。在故障檢測(cè)中，使用算法1 選擇一組探測(cè)路徑并發(fā)送探針來(lái)檢測(cè)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)。故障檢測(cè)的探針結(jié)果將作為故障定位算法的輸入。首先將正常探針和故障探針經(jīng)過(guò)的節(jié)點(diǎn)分別加入到正常節(jié)點(diǎn)集No和可疑節(jié)點(diǎn)集Ns中。故障定位的任務(wù)就是從可疑節(jié)點(diǎn)集中識(shí)別故障的節(jié)點(diǎn)。算法通過(guò)計(jì)算每個(gè)探測(cè)站節(jié)點(diǎn)到每個(gè)可疑節(jié)點(diǎn)的最短路徑來(lái)生成候選路徑集CP 并使用式(1) 計(jì)算每條候選路徑的權(quán)重。如果某些可疑節(jié)點(diǎn)不能被任何候選路徑經(jīng)過(guò)，則這些可疑節(jié)點(diǎn)是未知節(jié)點(diǎn)，例如孤立節(jié)點(diǎn)。為了盡可能多地識(shí)別出故障節(jié)點(diǎn)，算法依次選擇具有最小權(quán)重的候選路徑來(lái)發(fā)送探針。根據(jù)故障節(jié)點(diǎn)的判定條件，如果故障探針經(jīng)過(guò)的節(jié)點(diǎn)中只有一個(gè)可疑節(jié)點(diǎn)，則該可疑節(jié)點(diǎn)必為故障節(jié)點(diǎn)。確定一部分故障節(jié)點(diǎn)后，將網(wǎng)絡(luò)中所有與故障節(jié)點(diǎn)關(guān)聯(lián)的邊加入到禁忌表T中。在下一次的候選路徑生成中，算法為剩余的可疑節(jié)點(diǎn)生成更合適的候選路徑?？傊涉溌匪阉魉惴ㄍㄟ^(guò)禁止搜索與故障節(jié)點(diǎn)相連的鏈路來(lái)多次生成候選路徑集并選擇探測(cè)路徑，以實(shí)現(xiàn)多節(jié)點(diǎn)故障定位的目的。

算法2 故障定位的禁忌鏈路搜索算法

圖3 顯示了在包含8 個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中使用禁忌鏈路搜索算法選擇探測(cè)路徑進(jìn)行故障定位的過(guò)程，其中節(jié)點(diǎn)2 是探測(cè)站。假設(shè)網(wǎng)絡(luò)中的節(jié)點(diǎn)4、5 和7 發(fā)生故障。最初，故障節(jié)點(diǎn)的位置和數(shù)目是未知的。故障檢測(cè)階段的探測(cè)結(jié)果顯示了節(jié)點(diǎn)4、5 和7 為可疑節(jié)點(diǎn)。如圖3(a)所示，通過(guò)計(jì)算探測(cè)站節(jié)點(diǎn)到可疑節(jié)點(diǎn)的最短路徑生成候選路徑集CP={p24,p25,p27}。算法首先選擇權(quán)值最小的候選路徑p27(2-4-7)。沿該路徑發(fā)送的探針無(wú)法識(shí)別節(jié)點(diǎn)4 和節(jié)點(diǎn)7。然后，算法依次選擇路徑p24(2-4)和p25(2-5)分別將節(jié)點(diǎn)4 和節(jié)點(diǎn)5 識(shí)別為故障節(jié)點(diǎn)。此時(shí)，候選路徑集CP=?，可疑節(jié)點(diǎn)集Ns={7}。為了識(shí)別可疑節(jié)點(diǎn)7，算法生成一個(gè)新的候選路徑集。如圖3(b) 所示，算法將鏈路l1、l2、l3和l4加入到禁忌表T中，并生成一個(gè)新的候選路徑集CP={p27}。通過(guò)選擇探測(cè)路徑p27(2-3-6-8-7)來(lái)達(dá)到識(shí)別故障節(jié)點(diǎn)7 的目的。因此，故障節(jié)點(diǎn)集Nf={4,5,7}。對(duì)于復(fù)雜的大規(guī)模網(wǎng)絡(luò)，探測(cè)路徑選擇算法為識(shí)別大量故障節(jié)點(diǎn)提供了可能。

圖3 選擇探測(cè)路徑進(jìn)行故障定位Fig.3 Selecting probing paths for fault localization

3 實(shí)驗(yàn)與分析

為了驗(yàn)證探測(cè)路徑選擇算法的有效性，本文在隨機(jī)生成的網(wǎng)絡(luò)拓?fù)浜驼鎸?shí)網(wǎng)絡(luò)拓?fù)渖戏抡娌⒈容^了以下3 種算法。1) 探測(cè)路徑選擇算法(PPSA)：本文提出的一種結(jié)合貪婪路徑選擇和禁忌鏈路搜索的自適應(yīng)故障定位算法。2) 隨機(jī)游走算法(RWL)：Xuan 等[18]提出的一種通過(guò)隨機(jī)游走生成探測(cè)路徑的非適應(yīng)性故障定位算法。3)貪婪故障定位算法(GFL)：Natu 等[4]提出的一種用于定位少量節(jié)點(diǎn)故障的自適應(yīng)故障定位算法。本文設(shè)置探針長(zhǎng)度的閾值為K=8 并選擇兩個(gè)節(jié)點(diǎn)作為探測(cè)站節(jié)點(diǎn)，使得探測(cè)站節(jié)點(diǎn)能夠在8 跳以內(nèi)到達(dá)最多數(shù)量的其余節(jié)點(diǎn)且探測(cè)站節(jié)點(diǎn)的度最大。

3.1 BA 無(wú)標(biāo)度網(wǎng)絡(luò)上的實(shí)驗(yàn)

我們比較了3 種算法在隨機(jī)生成的BA 無(wú)標(biāo)度網(wǎng)絡(luò)中的性能。BA 無(wú)標(biāo)度網(wǎng)絡(luò)具有現(xiàn)實(shí)世界中的大多數(shù)網(wǎng)絡(luò)的增長(zhǎng)方式，能夠反映真實(shí)網(wǎng)絡(luò)的特性。性能比較使用的指標(biāo)有：成功定位率，假陽(yáng)性率和探測(cè)成本。仿真結(jié)果圖中的每個(gè)點(diǎn)都是在不同網(wǎng)絡(luò)拓?fù)渖线M(jìn)行共20 次實(shí)驗(yàn)之后取平均值繪制而成的。

圖4 顯示3 種算法在節(jié)點(diǎn)故障率為0.01～0.1下的成功定位率、假陽(yáng)性率和探測(cè)成本比較。生成的網(wǎng)絡(luò)拓?fù)涠及?00 個(gè)節(jié)點(diǎn)，且平均節(jié)點(diǎn)度為3?？梢钥闯?，隨著故障節(jié)點(diǎn)數(shù)的增加，探測(cè)路徑選擇算法比隨機(jī)游走算法具有更高的成功定位率和更低的假陽(yáng)性率。除此之外，由于隨機(jī)游走算法是一種非適應(yīng)性故障定位算法，探測(cè)成本遠(yuǎn)高于探測(cè)路徑選擇算法。與已有的貪婪故障定位算法相比，本文提出的算法在多故障節(jié)點(diǎn)的成功定位率上有了很大的提升，但是探測(cè)成本也略微增加。如圖4(a)所示，當(dāng)節(jié)點(diǎn)故障率增加時(shí)，本文提出的算法與貪婪故障定位算法相比能夠?qū)⒐?jié)點(diǎn)故障的成功定位率提升10%以上。

圖4 3 種算法的比較結(jié)果Fig.4 Comparison results of the three algorithms

圖5 顯示了在不同規(guī)模的網(wǎng)絡(luò)中探測(cè)路徑選擇算法的探測(cè)成本隨節(jié)點(diǎn)故障率的變化情況。隨著故障節(jié)點(diǎn)數(shù)目的增加，在故障定位階段選擇的探測(cè)路徑也會(huì)增加。為了驗(yàn)證探測(cè)路徑選擇算法在不同節(jié)點(diǎn)數(shù)量的網(wǎng)絡(luò)中的性能，接下來(lái)在隨機(jī)生成的節(jié)點(diǎn)數(shù)為100～1 000，平均節(jié)點(diǎn)度分別為3、4 和5 的網(wǎng)絡(luò)中進(jìn)行實(shí)驗(yàn)，其中節(jié)點(diǎn)故障率被設(shè)置為0.1。圖6(a)中的結(jié)果顯示，當(dāng)節(jié)點(diǎn)故障率為0.1 時(shí)，探測(cè)路徑選擇算法在不同規(guī)模的網(wǎng)絡(luò)中的成功定位率均能保持在90%以上。當(dāng)網(wǎng)絡(luò)平均節(jié)點(diǎn)度較大時(shí)，故障定位的成功率也較高。圖6(b)顯示了探測(cè)路徑選擇算法在不同規(guī)模的網(wǎng)絡(luò)中故障定位的探測(cè)成本的變化情況?？梢钥闯?，對(duì)于節(jié)點(diǎn)度較大的網(wǎng)絡(luò)，算法的探測(cè)成本也較高。

圖5 本文算法在不同規(guī)模網(wǎng)絡(luò)中的探測(cè)成本Fig.5 Probing cost of the algorithm in this paper in different scale networks

圖6 本文算法在不同規(guī)模網(wǎng)絡(luò)中的性能Fig.6 Performance of the algorithm in this paper in different scale networks

3.2 真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)

為了展示本文算法可以很好地?cái)U(kuò)展到真實(shí)網(wǎng)絡(luò)上，本文使用了阿德萊德大學(xué)開(kāi)發(fā)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)數(shù)據(jù)集[24]中的2 個(gè)網(wǎng)絡(luò)拓?fù)?GEANT、GTS CE) 和華盛頓大學(xué)的火箭燃料項(xiàng)目[25-26]導(dǎo)出的6 個(gè)網(wǎng)絡(luò)拓?fù)?AS3967、AS1755、AS1221、AS6461、AS3257、AS1239)進(jìn)行實(shí)驗(yàn)。這些拓?fù)浞从沉嘶ヂ?lián)網(wǎng)的真實(shí)連通性，被廣泛應(yīng)用于相關(guān)研究中。表1 顯示了每個(gè)拓?fù)涞墓?jié)點(diǎn)數(shù)、鏈路數(shù)和平均度。

表1 真實(shí)網(wǎng)絡(luò)拓?fù)銽able 1 Real network topologies

在這8 個(gè)真實(shí)網(wǎng)絡(luò)拓?fù)渲?，仿真?yàn)證了3 種算法的成功定位率和探測(cè)成本。對(duì)于每一個(gè)拓?fù)?，將?jié)點(diǎn)故障率設(shè)置為0.1。表2 和表3 分別給出了3 種算法在8 個(gè)真實(shí)網(wǎng)絡(luò)拓?fù)渖系某晒Χㄎ宦屎吞綔y(cè)成本?？梢钥闯?，本文提出的探測(cè)路徑選擇算法與其他算法相比具有較高的成功定位率和較低的探測(cè)成本。雖然探測(cè)成本稍微高于貪婪故障定位算法，但是成功定位率卻大大提升。

表2 算法的成功定位率比較Table 2 Comparison of successful localization ratios of algorithms

表3 算法的探測(cè)成本比較Table 3 Comparison of probing costs of algorithms

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

本文提出了一種有效的探測(cè)路徑選擇算法來(lái)解決網(wǎng)絡(luò)中的多節(jié)點(diǎn)故障定位問(wèn)題。該算法實(shí)現(xiàn)的原理是基于主動(dòng)探測(cè)技術(shù)為故障檢測(cè)和故障定位選擇最合適的探測(cè)路徑。用于故障檢測(cè)的貪婪路徑選擇算法在選擇最少數(shù)量探測(cè)路徑進(jìn)行故障檢測(cè)的同時(shí)減少探測(cè)數(shù)據(jù)包對(duì)鏈路負(fù)載的影響。用于故障定位的禁忌鏈路搜索算法通過(guò)構(gòu)造禁忌表多次生成候選路徑集，能夠顯著提高故障節(jié)點(diǎn)的成功定位率。在BA 無(wú)標(biāo)度網(wǎng)絡(luò)上的仿真結(jié)果表明，與現(xiàn)有故障定位算法相比，本文算法能夠顯著提高多節(jié)點(diǎn)故障的成功定位率并降低探測(cè)成本。在真實(shí)網(wǎng)絡(luò)拓?fù)渖系姆抡骝?yàn)證了探測(cè)路徑選擇算法能夠很好地?cái)U(kuò)展到實(shí)際網(wǎng)絡(luò)中。在之后的研究中，將在故障檢測(cè)和定位中引入探針長(zhǎng)度和節(jié)點(diǎn)負(fù)載等參數(shù)以滿足實(shí)際故障診斷需求。