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

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

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

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

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

1 基本概念

1.1 問題描述

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

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

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

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

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

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

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

2 探測路徑選擇算法

2.1 貪婪路徑選擇

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

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

算法1 故障檢測的貪婪路徑選擇算法

圖2 顯示了在包含6 個(gè)節(jié)點(diǎn)的簡單網(wǎng)絡(luò)中使用貪婪路徑選擇算法選擇探測路徑進(jìn)行故障檢測，其中節(jié)點(diǎn)1 和4 為探測站節(jié)點(diǎn)。通過Dijkstra 最短路徑算法計(jì)算出了一組候選路徑CP={p12,p13,p14,p15,p16,p42,p43,p45,p46}，其中pij表示探測站節(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)都被選定的探測路徑覆蓋。因此，沿探測路徑p45和p12發(fā)送的兩個(gè)探針可以檢測該網(wǎng)絡(luò)中的任何節(jié)點(diǎn)。

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

2.2 禁忌鏈路搜索

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

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

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

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

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

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

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

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

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

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

圖4 顯示3 種算法在節(jié)點(diǎn)故障率為0.01～0.1下的成功定位率、假陽性率和探測成本比較。生成的網(wǎng)絡(luò)拓?fù)涠及?00 個(gè)節(jié)點(diǎn)，且平均節(jié)點(diǎn)度為3?？梢钥闯觯S著故障節(jié)點(diǎn)數(shù)的增加，探測路徑選擇算法比隨機(jī)游走算法具有更高的成功定位率和更低的假陽性率。除此之外，由于隨機(jī)游走算法是一種非適應(yīng)性故障定位算法，探測成本遠(yuǎn)高于探測路徑選擇算法。與已有的貪婪故障定位算法相比，本文提出的算法在多故障節(jié)點(diǎn)的成功定位率上有了很大的提升，但是探測成本也略微增加。如圖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ò)中探測路徑選擇算法的探測成本隨節(jié)點(diǎn)故障率的變化情況。隨著故障節(jié)點(diǎn)數(shù)目的增加，在故障定位階段選擇的探測路徑也會(huì)增加。為了驗(yàn)證探測路徑選擇算法在不同節(jié)點(diǎn)數(shù)量的網(wǎng)絡(luò)中的性能，接下來在隨機(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í)，探測路徑選擇算法在不同規(guī)模的網(wǎng)絡(luò)中的成功定位率均能保持在90%以上。當(dāng)網(wǎng)絡(luò)平均節(jié)點(diǎn)度較大時(shí)，故障定位的成功率也較高。圖6(b)顯示了探測路徑選擇算法在不同規(guī)模的網(wǎng)絡(luò)中故障定位的探測成本的變化情況?？梢钥闯?，對(duì)于節(jié)點(diǎn)度較大的網(wǎng)絡(luò)，算法的探測成本也較高。

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

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

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

4 結(jié)束語

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