梁若舟，趙曦濱，萬(wàn)海

（清華大學(xué)軟件學(xué)院，北京 100084）

1 引言

時(shí)間敏感網(wǎng)絡(luò)（TSN，time-sensitive networking）是一種確定性傳輸網(wǎng)絡(luò)。它確保了可靠、確定和實(shí)時(shí)的網(wǎng)絡(luò)數(shù)據(jù)傳輸，滿足了工業(yè)控制應(yīng)用對(duì)實(shí)時(shí)性、確定性的需求。TSN 根據(jù)預(yù)先計(jì)算的調(diào)度表傳輸實(shí)時(shí)數(shù)據(jù)。調(diào)度表是根據(jù)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和應(yīng)用數(shù)據(jù)傳輸要求獲得的。當(dāng)網(wǎng)絡(luò)發(fā)生故障（如鏈路故障）時(shí)，網(wǎng)絡(luò)拓?fù)鋾?huì)發(fā)生改變，從而導(dǎo)致調(diào)度表失效，引起實(shí)時(shí)數(shù)據(jù)傳輸服務(wù)的降級(jí)。當(dāng)網(wǎng)絡(luò)發(fā)生故障時(shí)，為了重新計(jì)算調(diào)度表，TSN 需要對(duì)發(fā)生故障的鏈路或節(jié)點(diǎn)進(jìn)行定位，以獲得最新的網(wǎng)絡(luò)拓?fù)?。調(diào)度表的重新配置將中斷實(shí)時(shí)數(shù)據(jù)傳輸。因此，需要在確定的時(shí)間內(nèi)盡快獲得最新的網(wǎng)絡(luò)拓?fù)洹?/p>

工業(yè)場(chǎng)景下的故障檢測(cè)是一類非常重要的問(wèn)題，其中包括過(guò)程層的異常檢測(cè)[1]和網(wǎng)絡(luò)層的故障檢測(cè)。過(guò)程層的異常檢測(cè)主要關(guān)注工業(yè)生產(chǎn)過(guò)程中的數(shù)據(jù)是否正常。Wuest 等[2]使用有監(jiān)督機(jī)器學(xué)習(xí)的方法檢測(cè)異常。由于工業(yè)過(guò)程數(shù)據(jù)具有高維、復(fù)雜和非線性等性質(zhì)，Huang 等[3]提出使用核字典學(xué)習(xí)的方法解決這一問(wèn)題。針對(duì)真實(shí)工業(yè)場(chǎng)景中標(biāo)簽較少的問(wèn)題，Huang 等[4]使用半監(jiān)督字典學(xué)習(xí)方法為過(guò)程監(jiān)控提供有效模型。網(wǎng)絡(luò)層的故障檢測(cè)主要關(guān)注網(wǎng)絡(luò)中的鏈路故障的發(fā)現(xiàn)和定位。對(duì)于網(wǎng)絡(luò)故障檢測(cè)目前已有很多研究。主流的方法可分為兩類。第一類采用局部狀態(tài)感知技術(shù)。網(wǎng)絡(luò)設(shè)備向其鄰居發(fā)送鏈路層發(fā)現(xiàn)協(xié)議數(shù)據(jù)（LLDPDU,link layer discovery protocol data unit）以獲取其他設(shè)備的狀態(tài)，然后將收集到的狀態(tài)信息發(fā)送到網(wǎng)絡(luò)的控制器節(jié)點(diǎn)。第二類采用檢測(cè)流進(jìn)行故障檢測(cè)。一組檢測(cè)包從端節(jié)點(diǎn)發(fā)送，通過(guò)預(yù)定義的路徑覆蓋網(wǎng)絡(luò)中的每個(gè)鏈路，最后到達(dá)控制器節(jié)點(diǎn)?？刂破鞴?jié)點(diǎn)再根據(jù)每個(gè)檢測(cè)包的到達(dá)狀態(tài)（到達(dá)或丟失）來(lái)推斷每個(gè)鏈路的狀態(tài)。第二類方法又可以細(xì)分為以下3 種。1) 基于概率的檢測(cè)方法。通過(guò)發(fā)送多輪檢測(cè)包來(lái)計(jì)算每條檢測(cè)路徑的丟包率，進(jìn)而推斷每條鏈路的擁塞概率[5-7]，文獻(xiàn)[8]采用基于概率的貝葉斯網(wǎng)絡(luò)檢測(cè)方法來(lái)定位故障鏈路。2) 基于布爾觀測(cè)模型的方法[9-13]，稱為布爾網(wǎng)絡(luò)測(cè)繪。布爾網(wǎng)絡(luò)測(cè)繪模型如圖1 所示，針對(duì)圖1(a)的網(wǎng)絡(luò)拓?fù)?，生成? 條檢測(cè)流p1～p4。檢測(cè)流對(duì)應(yīng)的檢測(cè)矩陣如圖1(b)所示。矩陣的每一行代表一條檢測(cè)流，行中元素為1 代表該條流覆蓋對(duì)應(yīng)邊，為0 則代表該條流未覆蓋對(duì)應(yīng)邊。例如，p1覆蓋邊A 和B，未覆蓋C、D 和E。對(duì)應(yīng)行則為(1,1,0,0,0)。檢測(cè)矩陣的列代表對(duì)應(yīng)邊的故障編碼。例如，邊B 的故障編碼為(1,1,0,0)，表示若邊B 發(fā)生故障，則通過(guò)路徑p1和p2的包會(huì)丟失（列元素為1 表示包丟失），通過(guò)路徑p3和p4的包會(huì)順利到達(dá)（列元素為0 表示包未丟失）。3) 針對(duì)特定拓?fù)浣Y(jié)構(gòu)的方法。例如，針對(duì)環(huán)形拓?fù)涞亩帱c(diǎn)故障檢測(cè)方法[14]。

圖1 布爾網(wǎng)絡(luò)測(cè)繪模型

Duffield[15]提出的方法是檢測(cè)網(wǎng)絡(luò)故障的經(jīng)典方法。它通過(guò)檢測(cè)不同端到端路徑的狀態(tài)來(lái)推斷單個(gè)鏈路是擁塞還是失敗。文獻(xiàn)[16]提出了一種應(yīng)用于一般網(wǎng)絡(luò)拓?fù)渲胁紶柧W(wǎng)絡(luò)測(cè)繪問(wèn)題的經(jīng)典方法，主要分為兩類：非自適應(yīng)檢測(cè)和自適應(yīng)檢測(cè)。非自適應(yīng)檢測(cè)[17-19]在鏈路故障檢測(cè)過(guò)程中并行地發(fā)送所有數(shù)據(jù)包。自適應(yīng)檢測(cè)[10,20-22]根據(jù)已經(jīng)獲得的檢測(cè)數(shù)據(jù)包的結(jié)果依次建立檢測(cè)路徑。

如何優(yōu)化檢測(cè)路徑集也是研究熱點(diǎn)。一些研究的目的是尋找最小檢測(cè)路徑集。這是一個(gè)NP-hard問(wèn)題。Zeng 等[23]提出了一種網(wǎng)絡(luò)故障自動(dòng)檢測(cè)系統(tǒng)ATPG（automatic test packet generation），通過(guò)讀取路由配置和拓?fù)浣Y(jié)構(gòu)來(lái)生成一組最小的數(shù)據(jù)包。但由于其迭代檢測(cè)策略，無(wú)法實(shí)現(xiàn)時(shí)間確定性檢測(cè)。Bai 等[10]提出了一種利用二元觀測(cè)模型進(jìn)行網(wǎng)絡(luò)監(jiān)測(cè)的兩階段方法，但它只適用于單點(diǎn)檢測(cè)。Chan等[19]提出了一種針對(duì)不同拓?fù)浣Y(jié)構(gòu)的非自適應(yīng)組測(cè)試，并行發(fā)送最小數(shù)量的預(yù)先確定的數(shù)據(jù)包。但是該方案對(duì)拓?fù)涞倪B通性有嚴(yán)格要求，例如，為了識(shí)別s個(gè)故障，網(wǎng)絡(luò)拓?fù)涞倪呥B通度需大于或等于2(s+1)。

此外，K點(diǎn)可檢測(cè)（K-identifiable）性質(zhì)也是一個(gè)研究熱點(diǎn)。文獻(xiàn)[17]討論了識(shí)別最多d個(gè)缺陷項(xiàng)所需的最少m條路徑數(shù)的基本界問(wèn)題，介紹了4 種不同場(chǎng)景的隨機(jī)路徑構(gòu)造。文獻(xiàn)[13]考慮給定m條檢測(cè)路徑、網(wǎng)絡(luò)拓?fù)?、路由方案和路徑長(zhǎng)度約束的最大可識(shí)別項(xiàng)目數(shù)的上界。這些文獻(xiàn)旨在證明K-identifiable 性質(zhì)，但并沒(méi)有給出一種實(shí)用、有效的檢測(cè)路徑集的構(gòu)造方法。

布爾網(wǎng)絡(luò)測(cè)繪通過(guò)求解布爾代數(shù)中的一組線性方程組，通過(guò)端到端測(cè)量推斷鏈路擁塞狀態(tài)。一些研究集中在如何高效、準(zhǔn)確地求解布爾代數(shù)中的模型。Chen 等[5]開(kāi)發(fā)了一個(gè)學(xué)習(xí)估計(jì)方案來(lái)推斷網(wǎng)絡(luò)中的擁塞鏈路。文獻(xiàn)[6]考慮了利用鏈路時(shí)延變化的多路徑路由方案，提出了一種貪婪算法求解擁塞路徑，同時(shí)兼容時(shí)延方差。類似地，文獻(xiàn)[7]提出了一個(gè)擴(kuò)展的狀態(tài)空間模型，通過(guò)自上而下的貪婪算法來(lái)識(shí)別擁塞鏈路。然而，上述算法是對(duì)擁塞鏈路的概率估計(jì)，并不能確定性地識(shí)別鏈路故障。

在工業(yè)控制拓?fù)涞膽?yīng)用場(chǎng)景中，一種理想的鏈路故障檢測(cè)方法應(yīng)具有以下性質(zhì)。

1) 確定性檢測(cè)。此處的確定性有兩層含義：①拓?fù)浒l(fā)現(xiàn)所用的時(shí)間是有界的；②方法檢測(cè)到的鏈路狀態(tài)是確定性的，而不是概率性的。

2) 網(wǎng)絡(luò)負(fù)載優(yōu)化。檢測(cè)方法應(yīng)使用盡可能少的檢測(cè)包，以減少帶寬消耗。

3) 多點(diǎn)故障檢測(cè)。檢測(cè)方法應(yīng)盡可能多地發(fā)現(xiàn)故障。

4) 適用于工業(yè)控制拓?fù)?。工業(yè)控制拓?fù)渚哂芯植窟B通度高、整體連通度低的特點(diǎn)。例如，在圖2所示的工業(yè)控制拓?fù)渲?，在路徑S0—S1—S8—S12—S16—S20—S24中只能實(shí)現(xiàn)單點(diǎn)故障檢測(cè)，但在局部如Car1中可以實(shí)現(xiàn)多點(diǎn)故障檢測(cè)。

圖2 一種工業(yè)控制拓?fù)?/p>

目前的方法并不能完全滿足工業(yè)控制拓?fù)滏溌饭收蠙z測(cè)的上述4 個(gè)性質(zhì)。具體而言，它們具有以下不足之處。

1) 檢測(cè)時(shí)間不確定。基于概率的檢測(cè)方法[5-7]預(yù)測(cè)鏈路失效或擁塞的概率，不能滿足確定性檢測(cè)的要求。基于布爾網(wǎng)絡(luò)測(cè)繪的方法[9-13]需要多輪迭代檢測(cè)，存在檢測(cè)時(shí)間不確定的問(wèn)題。

2) 未對(duì)網(wǎng)絡(luò)負(fù)載優(yōu)化。當(dāng)前方法未對(duì)生成的檢測(cè)包數(shù)量進(jìn)行優(yōu)化，影響性能。

3) 無(wú)法應(yīng)對(duì)多點(diǎn)故障檢測(cè)場(chǎng)景。Bai 等[10]提出的基于二元觀測(cè)模型進(jìn)行網(wǎng)絡(luò)監(jiān)測(cè)的兩階段方法只能應(yīng)用于單點(diǎn)故障檢測(cè)。

4) 無(wú)法適應(yīng)工業(yè)控制拓?fù)涮攸c(diǎn)。當(dāng)前方法未針對(duì)工業(yè)控制拓?fù)湔w連通度低、局部連通度高的特點(diǎn)進(jìn)行優(yōu)化，降低了對(duì)于局部高連通度部分的檢測(cè)能力。

針對(duì)以上不足之處，本文提出了一種針對(duì)工業(yè)控制拓?fù)涞拇_定性局部多點(diǎn)故障檢測(cè)方法。該方法的基本思路如下。

首先，根據(jù)當(dāng)前網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，識(shí)別網(wǎng)絡(luò)中連通度較低的主干部分和連通度較高的簇，對(duì)主干部分使用單點(diǎn)故障檢測(cè)方法生成檢測(cè)流，對(duì)簇使用多點(diǎn)故障檢測(cè)方法生成檢測(cè)流。然后利用檢測(cè)流優(yōu)化算法減少檢測(cè)流的數(shù)量。每個(gè)檢測(cè)流從某個(gè)節(jié)點(diǎn)開(kāi)始，經(jīng)過(guò)指定的路由，最后到達(dá)TSN 控制器。

其次，為每個(gè)檢測(cè)流分配一個(gè)傳輸周期和最壞時(shí)延，并在此基礎(chǔ)上生成檢測(cè)流的TSN 調(diào)度表。當(dāng)網(wǎng)絡(luò)運(yùn)行時(shí)，每個(gè)檢測(cè)包從起始節(jié)點(diǎn)按照預(yù)定的時(shí)間周期與檢測(cè)流一起周期性地發(fā)送，并到達(dá)TSN 控制器。當(dāng)故障發(fā)生時(shí)，一些檢測(cè)包將無(wú)法到達(dá)TSN控制器。TSN 控制器定期收集每個(gè)檢測(cè)包的到達(dá)或故障狀態(tài)信息，并使用拓?fù)浒l(fā)現(xiàn)算法獲得鏈路狀態(tài)和網(wǎng)絡(luò)拓?fù)洹?/p>

此外，為了保證整個(gè)故障檢測(cè)過(guò)程的時(shí)間確定性，檢測(cè)流需要在確定的時(shí)間范圍內(nèi)到達(dá)控制器。本文將檢測(cè)流實(shí)現(xiàn)為T(mén)SN 數(shù)據(jù)流，從而實(shí)現(xiàn)了檢測(cè)流傳輸?shù)臅r(shí)間確定性。IEEE 802.1Qav 標(biāo)準(zhǔn)中闡述了隊(duì)列及轉(zhuǎn)發(fā)協(xié)議能夠確保傳輸時(shí)延控制在一定的范圍內(nèi)；IEEE 802.1Qbv 標(biāo)準(zhǔn)中使用了時(shí)間感知整形器，保障業(yè)務(wù)流消息的傳輸時(shí)延是確定的；IEEE 802.1Qch 標(biāo)準(zhǔn)中引入了周期性排隊(duì)與轉(zhuǎn)發(fā)機(jī)制。上述3 個(gè)標(biāo)準(zhǔn)可以保證檢測(cè)流在確定的時(shí)間內(nèi)到達(dá)控制器節(jié)點(diǎn)。IEEE 802.1 Qca 標(biāo)準(zhǔn)定義的路徑控制和保留，以及IEEE 802.1CB 標(biāo)準(zhǔn)定義的幀復(fù)制和消除可以控制每個(gè)檢測(cè)流的路由。

本文貢獻(xiàn)總結(jié)如下。

1) 基于工業(yè)控制拓?fù)涞膱?chǎng)景，本文提出了一種基于布爾網(wǎng)絡(luò)測(cè)繪的確定性局部多點(diǎn)故障檢測(cè)方法。本文提出的檢測(cè)框架可以針對(duì)工業(yè)拓?fù)渲鞲蛇B通度低、局部連通度高的特點(diǎn)，生成近似最優(yōu)的檢測(cè)路徑集，實(shí)現(xiàn)局部多點(diǎn)故障檢測(cè)。利用TSN 的確定性傳輸機(jī)制，該檢測(cè)過(guò)程時(shí)間上界是確定的。

2) 本文進(jìn)行了全面的實(shí)驗(yàn)來(lái)評(píng)估所提檢測(cè)方法。與已有的故障檢測(cè)方法相比，所提方法能夠在確定的時(shí)間內(nèi)準(zhǔn)確地識(shí)別出多個(gè)故障鏈路，生成的最小檢測(cè)路徑集優(yōu)于隨機(jī)游走法和 NACGT（non-adaptive combinatorial group testing）[18]法。

2 系統(tǒng)模型與問(wèn)題定義

2.1 網(wǎng)絡(luò)模型

網(wǎng)絡(luò)拓?fù)浔欢x為一個(gè)無(wú)向圖G(V,L)。所有交換機(jī)和端節(jié)點(diǎn)的集合由頂點(diǎn)表示。所有物理鏈路的集合由邊表示。

所有通過(guò)物理鏈路連接的頂點(diǎn)都可以直接通信，并且物理鏈路是全雙工的。鏈路連接節(jié)點(diǎn)vi∈V和節(jié)點(diǎn)vj∈V。因此，物理鏈路也可以表示為本文假設(shè)交換機(jī)和節(jié)點(diǎn)不會(huì)發(fā)生故障，僅物理鏈路可能發(fā)生故障。鏈路有2 種狀態(tài)：故障鏈路和正常鏈路。所有故障鏈路的集合稱為故障鏈路集，表示為F?L。

檢測(cè)路徑由一系列相鄰的鏈路組成，并且不包含環(huán)，定義為p。檢測(cè)路徑表示為路徑所經(jīng)過(guò)的物理鏈路集。如果鏈路lj被檢測(cè)路徑pi經(jīng)過(guò)，則lj∈pi。如果?lk∈pi,lk?pj，則pi≠pj。

因此，本文的目標(biāo)是通過(guò)一組檢測(cè)路徑P={pi|i=0,1,2,…,z} 來(lái)識(shí)別故障鏈路集F，其中z表示檢測(cè)路徑的數(shù)目。

2.2 布爾測(cè)繪圖和檢測(cè)矩陣

用布爾形式來(lái)表示物理鏈路的狀態(tài)，xi=0 表示鏈路正常，xi=1 表示鏈路故障。因此，物理鏈路li的狀態(tài)可定義為

用一個(gè)布爾狀態(tài)向量來(lái)表示整個(gè)網(wǎng)絡(luò)的鏈路狀態(tài)，鏈路狀態(tài)向量為x=(x1,x2,…,xm) ∈{0,1}m。

用一個(gè)布爾狀態(tài)向量來(lái)表示所有檢測(cè)流的狀態(tài)，檢測(cè)路徑的狀態(tài)向量為y=(y1,y2,…,yz)∈{0,1}z。

相應(yīng)地，可以得到鏈路狀態(tài)向量和檢測(cè)路徑狀態(tài)向量之間的關(guān)系為

其中，∨是邏輯或運(yùn)算。

布爾檢測(cè)矩陣可以根據(jù)一系列檢測(cè)路徑P有效地推斷鏈路的狀態(tài)x（故障或正常）。布爾檢測(cè)矩陣R是一個(gè)z×m的矩陣。如果鏈路lj被檢測(cè)路徑pi遍歷，則Ri,j=0。布爾檢測(cè)矩陣R的第i行表示一個(gè)檢測(cè)路徑pi，而第j列表示鏈路lj的二維編碼向量。式(3)轉(zhuǎn)換成矩陣形式為

2.3 K-identifiable 性質(zhì)

本節(jié)討論一個(gè)檢測(cè)矩陣R可以識(shí)別最多K個(gè)故障鏈路的充要條件。

假設(shè)網(wǎng)絡(luò)中有K個(gè)故障鏈路。不失一般性地，給定鏈路狀態(tài)向量x，其中，則檢測(cè)路徑狀態(tài)向量y可以表示為

也就是說(shuō)，對(duì)所有在故障鏈路集合中的鏈路li的二維編碼向量b(li)（li∈F）執(zhí)行邏輯或運(yùn)算。

布爾檢測(cè)矩陣R滿足K-identifiable 性質(zhì)，它的含義是：如果網(wǎng)絡(luò)中最多有K個(gè)故障鏈路，則由式(4)計(jì)算的所有y的結(jié)果都是不同的。這個(gè)結(jié)論可以描述為定理1[11]。

定理1給定一組檢測(cè)路徑P和一個(gè)鏈路li∈L，如果對(duì)于任何 2 個(gè)故障集F1和F2，F(xiàn)1∩{lj}≠F2∩{lj}，且Fi≤K(i∈{1,2})，滿足

則稱li相對(duì)于P滿足K-identifiable 性質(zhì)。

擴(kuò)展定理1 來(lái)研究單點(diǎn)故障識(shí)別問(wèn)題，考慮K=1，則得到引理1。

引理1鏈路li相對(duì)于P滿足1-identifiable 性質(zhì)，當(dāng)且僅當(dāng)b(li) ≠0，且?li≠lj,b(li)≠b(lj)。即其二維編碼不為空，且與任何其他鏈路的二維編碼不同。

對(duì)于一個(gè)滿足K-identifiable 性質(zhì)的檢測(cè)矩陣，如果存在不超過(guò)K條故障鏈路，那么所有故障鏈路都可以通過(guò)z條檢測(cè)路徑進(jìn)行準(zhǔn)確識(shí)別和定位。

2.4 局部K 點(diǎn)可檢測(cè)性質(zhì)

在工業(yè)控制網(wǎng)絡(luò)中，由于全局網(wǎng)絡(luò)的邊連通度較低，不滿足K-identifiable 性質(zhì)，但局部網(wǎng)絡(luò)往往具有較高的邊連通度。因此，更常用的情況是一個(gè)網(wǎng)絡(luò)滿足局部K點(diǎn)可檢測(cè)（local-K-identifiable）性質(zhì)。

也就是說(shuō)，對(duì)所有在簇內(nèi)故障鏈路集合中的鏈路li的二維編碼向量執(zhí)行邏輯或運(yùn)算。

如果一個(gè)簇C滿足local-K-identifiable 性質(zhì)，它的含義為，如果簇內(nèi)最多有K個(gè)故障鏈路，則由式(7)計(jì)算的所有ycr的結(jié)果都是不同的。通過(guò)引申定理1，該結(jié)論可以描述為引理2。

則稱li在簇cr內(nèi)相對(duì)于P滿足local-K-identifiable性質(zhì)。

2.5 問(wèn)題定義

由于全局網(wǎng)絡(luò)的邊連通度較低，可能不滿足K-identifiable 性質(zhì)。這會(huì)使一些網(wǎng)絡(luò)僅可以進(jìn)行單點(diǎn)故障檢測(cè)。但事實(shí)上，網(wǎng)絡(luò)的稠密是不均勻的，局部比較密集的網(wǎng)絡(luò)可以實(shí)現(xiàn)多點(diǎn)故障檢測(cè)?？梢詫⑦@些比較稠密的局部網(wǎng)絡(luò)識(shí)別為簇，對(duì)每個(gè)簇進(jìn)行多點(diǎn)故障識(shí)別。因此，需要設(shè)計(jì)一種有效的檢測(cè)矩陣構(gòu)造方法，使用盡可能少的檢測(cè)路徑，使每個(gè)簇滿足local-K-identifiable 性質(zhì)。該約束優(yōu)化問(wèn)題定義為

其中，C表示網(wǎng)絡(luò)中簇的集合；表示檢測(cè)簇cr的局部檢測(cè)矩陣；Rc表示檢測(cè)非簇鏈路的局部檢測(cè)矩陣；表示簇cr中最多有K個(gè)故障鏈路的所有故障鏈路集合；z表示布爾檢測(cè)矩陣R的總行數(shù)，z也是檢測(cè)流的總數(shù)量，它等于各個(gè)分簇的檢測(cè)流與非簇檢測(cè)流的數(shù)量之和。

3 確定性多點(diǎn)故障檢測(cè)機(jī)制

本節(jié)詳細(xì)介紹確定性多點(diǎn)故障檢測(cè)方法，方法流程如圖3 所示。該方法分為兩部分：離線檢測(cè)矩陣計(jì)算和在線故障檢測(cè)。

圖3 確定性多點(diǎn)故障檢測(cè)方法流程

離線檢測(cè)矩陣計(jì)算的目標(biāo)是構(gòu)造一個(gè)檢測(cè)矩陣，該矩陣在滿足K-identifiable 性質(zhì)的前提下，所需的檢測(cè)流數(shù)盡可能少。此階段進(jìn)一步分為3 個(gè)步驟。

步驟1基于馬爾可夫鏈（MC,Markov chain）采樣算法，提出了改進(jìn)的基于馬爾可夫鏈的采樣算法，以得到一組初始檢測(cè)路徑（用P0表示）。由初始檢測(cè)路徑P0所構(gòu)成的檢測(cè)矩陣被表示為初始檢測(cè)矩陣R0。

步驟2檢查R0是否滿足K-identifiable 性質(zhì)。如果是，則轉(zhuǎn)到步驟3；如果不滿足，則使用構(gòu)造性算法使其滿足。本文提出了一種構(gòu)造性算法，稱為矩陣修補(bǔ)算法。該算法的原理是：構(gòu)造新的檢測(cè)路徑并將其添加到P0，直到檢測(cè)矩陣滿足K-identifiable 性質(zhì)。通過(guò)該步驟獲得的一組檢測(cè)路徑被表示為P1，其相應(yīng)的檢測(cè)矩陣被表示為R1。

步驟 3本文采用一種迭代策略，在保持K-identifiable 性質(zhì)不變的情況下，安全地刪除P1中的檢測(cè)路徑，然后用更少的路徑得到滿足定理1 的一組近似最優(yōu)檢測(cè)路Popt和近似最優(yōu)檢測(cè)矩陣Ropt。

在線故障檢測(cè)在得到近似最優(yōu)檢測(cè)矩陣Ropt后，沿著從Ropt派生的路徑，并行地周期性發(fā)送檢測(cè)包，根據(jù)一定時(shí)間內(nèi)檢測(cè)包到達(dá)控制器的狀態(tài)來(lái)獲得路徑狀態(tài)向量y，并使用式(5)求解鏈路狀態(tài)向量x。在實(shí)際的檢測(cè)過(guò)程中，只需要將向量y存儲(chǔ)為Key，而將向量x對(duì)應(yīng)的故障鏈路集合F設(shè)置為Value，即可在線性時(shí)間內(nèi)找到所有的故障鏈路。

因此，確定性多點(diǎn)故障檢測(cè)機(jī)制的關(guān)鍵算法是改進(jìn)的基于馬爾可夫鏈的采樣算法（用于獲取初始檢測(cè)矩陣）和矩陣修補(bǔ)算法（基于初始檢測(cè)矩獲取滿足K-identifiable 性質(zhì)的檢測(cè)矩陣）。

3.1 改進(jìn)的基于馬爾可夫鏈的采樣算法

本文提出的檢測(cè)方法需要得到一個(gè)可以直接滿足K-identifiable 性質(zhì)的檢測(cè)路徑集。一個(gè)簡(jiǎn)單的思想是采樣。由于不可能枚舉所有合法的檢測(cè)路徑，因此傳統(tǒng)的基于概率的采樣方法（如高斯分布抽樣）是不適用的。一種實(shí)用的方法是隨機(jī)游走采樣。隨機(jī)游走采樣的本質(zhì)是一階馬爾可夫鏈，因此本文將其記為MC-采樣（Markov chain sampling）。

MC-采樣不能以高概率直接獲得滿足K-identifiable 性質(zhì)的初始檢測(cè)矩陣。因此，需要一種具有引導(dǎo)性的隨機(jī)游走抽樣方法。該方法能以較大的概率獲得滿足K-identifiable 性質(zhì)的初始檢測(cè)矩陣。

如果鏈路l1被大量的檢測(cè)路徑經(jīng)過(guò)，那么l1發(fā)生故障，這些路徑都將受到影響。如果檢測(cè)路徑之間的重疊度太大，則一條鏈路發(fā)生故障，將降低其他檢測(cè)路徑的檢測(cè)能力。因此，每個(gè)鏈路通過(guò)的路徑數(shù)應(yīng)該相對(duì)平均，并且每個(gè)檢測(cè)路徑之間的重疊應(yīng)該降低。本文提出的Weighted-MC 采樣算法如圖4 所示。

圖4 Weighted-MC 采樣算法

每個(gè)狀態(tài)跳轉(zhuǎn)到鄰居節(jié)點(diǎn)、跳回父節(jié)點(diǎn)或停留在其自身的概率與候選鄰居鏈路的通過(guò)檢測(cè)路徑數(shù)有關(guān)。如果該鏈路已經(jīng)通過(guò)大量檢測(cè)路徑，則其跳轉(zhuǎn)的概率將降低。設(shè)當(dāng)前節(jié)點(diǎn)i共有t個(gè)鄰居節(jié)點(diǎn)，對(duì)這t條邊按照通過(guò)的檢測(cè)路徑數(shù)目降序排列，當(dāng)前節(jié)點(diǎn)到相鄰節(jié)點(diǎn)的概率為

其中，qij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的轉(zhuǎn)移概率，nik表示通過(guò)以i和k為節(jié)點(diǎn)的邊路徑數(shù)量，q表示節(jié)點(diǎn)到自身的轉(zhuǎn)移概率。圖4 中，當(dāng)前狀態(tài)si對(duì)應(yīng)節(jié)點(diǎn)vi，其父節(jié)點(diǎn)是vi-1，鄰居節(jié)點(diǎn)是vi+1和vi+2。

3.2 矩陣修補(bǔ)算法

當(dāng)2 個(gè)鏈路狀態(tài)向量x通過(guò)檢測(cè)矩陣R0映射到同一路徑狀態(tài)向量y時(shí)，初始檢測(cè)矩陣R0不能滿足K-identifiable 性質(zhì)。解決該問(wèn)題的一個(gè)方法是添加新路徑。本節(jié)闡述了一種矩陣修補(bǔ)算法，通過(guò)構(gòu)造新的檢測(cè)路徑，使初始檢測(cè)矩陣滿足K-identifiable 性質(zhì)。

定理2假設(shè)在(K+1)-邊連通圖中構(gòu)造了滿足K-identifiable 性質(zhì)的檢測(cè)矩陣R，如果存在2 個(gè)不同的鏈路狀態(tài)向量x和x′，它們被檢測(cè)矩陣R映射到相同的檢測(cè)路徑狀態(tài)向量y，則可以構(gòu)造一個(gè)新的檢測(cè)路徑來(lái)區(qū)分x和x′。

證明假設(shè)由x和x′表示的故障鏈路集是Fi和Fj，F(xiàn)j≥Fi。Fi和Fj之間有3 種關(guān)系：Fi?Fj，F(xiàn)i∩Fj=?，F(xiàn)i∩Fj≠?,Fi?Fj。

1)Fi?Fj。由于檢測(cè)矩陣最多能識(shí)別K個(gè)故障鏈路，因此≤K。對(duì)于任何一個(gè)故障鏈路l∈Fj-Fi，l至少有一條新的路徑可以路由到控制器而不經(jīng)過(guò)Fi中的鏈路。因?yàn)樵谙薋i中的所有鏈路之后，整個(gè)網(wǎng)絡(luò)的邊連通度仍然為1。通過(guò)引入一條新的檢測(cè)路徑，被x映射的檢測(cè)路徑狀態(tài)向量變?yōu)閇y,0]，而被x′映射的檢測(cè)路徑狀態(tài)向量變?yōu)閇y,1]。由此，可以區(qū)分Fi和Fj。

2)Fi∩Fj=?和Fi∩Fj≠?,Fi?Fj同理可證。

因此，本文提出矩陣修補(bǔ)算法，如圖5 所示，枚舉所有鏈路狀態(tài)向量x，根據(jù)初始檢測(cè)矩陣R0將鏈路狀態(tài)向量映射到檢測(cè)路徑狀態(tài)向量y，然后對(duì)具有相同映射關(guān)系的每對(duì)向量，構(gòu)造新的檢測(cè)路徑來(lái)區(qū)分它們。構(gòu)造新的檢測(cè)路徑的方法如下：首先尋找一條鏈路l，l只屬于x對(duì)應(yīng)的故障集Fi或者l只屬于x′對(duì)應(yīng)的故障集Fj，若l∈Fj，則從控制點(diǎn)v0開(kāi)始進(jìn)行廣度優(yōu)先搜索，找到一條從v0到l的路徑p，p上所有邊均不屬于Fj；若l∈Fj，則從控制點(diǎn)v0開(kāi)始進(jìn)行搜索，找到一條從v0到l的路徑p，p上所有邊均不屬于Fj。矩陣修補(bǔ)算法得到的檢測(cè)路徑p即為滿足要求的新的檢測(cè)路徑。

圖5 矩陣修補(bǔ)算法

4 確定性局部多點(diǎn)故障檢測(cè)機(jī)制

并不是所有的拓?fù)涠紳M足K-identifiable 性質(zhì)，一些拓?fù)湔w的邊連通度不高，可能僅能滿足1-identifiable 性質(zhì)，但局部具有較高的邊連通度，可以形成一個(gè)局部的簇，如列車通信網(wǎng)絡(luò)。針對(duì)這種拓?fù)?，如果仍使用確定性多點(diǎn)故障檢測(cè)機(jī)制，則會(huì)將問(wèn)題降級(jí)為單點(diǎn)故障檢測(cè)問(wèn)題，損失了整個(gè)網(wǎng)絡(luò)故障識(shí)別的能力。本文提出的方法能夠在網(wǎng)絡(luò)中連通度較高的局部使用確定性多點(diǎn)故障檢測(cè)，在連通度較低的主干網(wǎng)絡(luò)實(shí)現(xiàn)單點(diǎn)故障檢測(cè)，提升了網(wǎng)絡(luò)整體的故障檢測(cè)能力。

本文將這種網(wǎng)絡(luò)抽象為圖6 所示的網(wǎng)絡(luò)拓?fù)洹Ｕ麄€(gè)網(wǎng)絡(luò)抽象為邊連通度較低的樹(shù)干和邊連通度較高的簇。圖6 中的×表示該鏈路發(fā)生故障。如果鏈路li發(fā)生故障，則無(wú)論簇內(nèi)的鏈路狀態(tài)如何，經(jīng)過(guò)簇內(nèi)的檢測(cè)路徑均會(huì)被li影響，不能到達(dá)控制器。因此，整個(gè)網(wǎng)絡(luò)降級(jí)為單點(diǎn)故障檢測(cè)。

圖6 連通度不均勻的網(wǎng)絡(luò)拓?fù)?/p>

本文的目的是設(shè)計(jì)一種確定性局部多點(diǎn)故障檢測(cè)機(jī)制，降低K-identifiable 性質(zhì)對(duì)該拓?fù)涞募s束，從而滿足樹(shù)干單點(diǎn)檢測(cè)、簇內(nèi)多點(diǎn)檢測(cè)的性質(zhì)，即滿足local-K-identifiable 性質(zhì)?；诖?，將網(wǎng)絡(luò)中的節(jié)點(diǎn)分為兩類，鏈路分為三類具體描述如下。

1) 樹(shù)干節(jié)點(diǎn)vtree，指一系列邊連通度較低的節(jié)點(diǎn)。樹(shù)干節(jié)點(diǎn)可以理解為一個(gè)網(wǎng)絡(luò)的交通樞紐，會(huì)以較高的流量被檢測(cè)路徑所經(jīng)過(guò)。

2) 簇節(jié)點(diǎn)vnon-tree，指一系列邊連通度較高的節(jié)點(diǎn)。本文將一個(gè)網(wǎng)絡(luò)中的非樹(shù)干節(jié)點(diǎn)都看作是簇節(jié)點(diǎn)。

3) 樹(shù)干鏈路ltree，樹(shù)干節(jié)點(diǎn)和樹(shù)干節(jié)點(diǎn)相連的鏈路稱為樹(shù)干鏈路。

4) 樹(shù)枝鏈路lbranch，樹(shù)干節(jié)點(diǎn)和簇節(jié)點(diǎn)相連的鏈路稱為樹(shù)枝鏈路。

5) 簇鏈路lcluster，簇節(jié)點(diǎn)和簇節(jié)點(diǎn)相連的鏈路稱為簇鏈路。

與全局性確定性多點(diǎn)故障檢測(cè)機(jī)制相同，該機(jī)制主要分為兩個(gè)階段：離線檢測(cè)矩陣計(jì)算階段和在線故障檢測(cè)階段。

離線檢測(cè)矩陣計(jì)算的目標(biāo)是構(gòu)造一個(gè)檢測(cè)矩陣，使在同一個(gè)簇內(nèi)的鏈路滿足local-K-identifiable性質(zhì)，不在任何簇內(nèi)的節(jié)點(diǎn)滿足單點(diǎn)故障檢測(cè)性質(zhì)，同時(shí)，其所需的檢測(cè)流數(shù)目盡可能少。此階段進(jìn)一步分為以下步驟。

步驟1對(duì)網(wǎng)絡(luò)拓?fù)溥M(jìn)行預(yù)處理，通過(guò)基于流量的樹(shù)干節(jié)點(diǎn)識(shí)別算法識(shí)別出所有的樹(shù)干節(jié)點(diǎn)，然后對(duì)剩余的節(jié)點(diǎn)進(jìn)行分簇，形成r個(gè)簇C={c0,c1,…,cr}，使具有較高連通度的節(jié)點(diǎn)們被分到一個(gè)簇內(nèi)。

步驟2對(duì)包含樹(shù)干鏈路、樹(shù)枝鏈路的簇外鏈路進(jìn)行檢測(cè)矩陣的生成。將生成的檢測(cè)矩陣稱為簇外檢測(cè)矩陣。該檢測(cè)能滿足對(duì)簇外鏈路的單點(diǎn)故障識(shí)別（K=1）。

步驟3對(duì)簇外檢測(cè)矩陣中的每一條連接簇的檢測(cè)路徑，利用針對(duì)簇的隨機(jī)游走采樣算法，對(duì)簇進(jìn)行延伸檢測(cè)，生成若干新的檢測(cè)路徑，稱為初始簇檢測(cè)路徑（用表示）。由初始簇檢測(cè)路徑所構(gòu)成的檢測(cè)矩陣被表示為初始簇檢測(cè)矩陣。

步驟4計(jì)算該簇的邊連通度為K+1，檢測(cè)是否滿足local-K-identifiable 性質(zhì)。如果滿足，則跳轉(zhuǎn)至步驟3。如果不滿足，則使用針對(duì)簇的矩陣修補(bǔ)算法對(duì)該簇進(jìn)行修補(bǔ)，通過(guò)構(gòu)造新的檢測(cè)路徑并將其添加到直至該簇滿足local-K-identifiable 性質(zhì)。將通過(guò)該步驟獲得的檢測(cè)路徑表示為，相應(yīng)的檢測(cè)矩陣表示為。

步驟 5采用迭代策略，在保持該簇local-K-identifiable 性質(zhì)不變的前提下，安全地刪除中的檢測(cè)路徑，獲得一組路徑數(shù)量更少的近似最優(yōu)簇檢測(cè)路徑和近似最優(yōu)簇檢測(cè)矩陣。

步驟6重復(fù)步驟3～步驟5 直至對(duì)所有的簇完成構(gòu)造，通過(guò)合并所有的檢測(cè)路徑，得到最后的檢測(cè)矩陣Ropt。

4.1 網(wǎng)絡(luò)預(yù)處理

本節(jié)對(duì)網(wǎng)絡(luò)拓?fù)溥M(jìn)行預(yù)處理，區(qū)分所有的樹(shù)干節(jié)點(diǎn)、簇節(jié)點(diǎn)、樹(shù)干鏈路、樹(shù)枝鏈路和簇鏈路。然后針對(duì)簇鏈路和非簇鏈路分別生成檢測(cè)路徑。該過(guò)程分為兩步：首先識(shí)別出所有的樹(shù)干節(jié)點(diǎn)，然后對(duì)剩余的節(jié)點(diǎn)進(jìn)行分簇。

分簇可以利用圖論的理論知識(shí)，將整張圖進(jìn)行分割。例如，統(tǒng)計(jì)出節(jié)點(diǎn)與節(jié)點(diǎn)之間的邊連通度，用二維矩陣表示，再利用相似度原理進(jìn)行分割。但節(jié)點(diǎn)與節(jié)點(diǎn)的邊連通度計(jì)算本身具有較高復(fù)雜度，相似度分割也會(huì)使問(wèn)題變得復(fù)雜。需要找到一個(gè)更加簡(jiǎn)便高效的樹(shù)干識(shí)別和分簇算法。因此提出基于流量的樹(shù)干節(jié)點(diǎn)識(shí)別算法和分簇算法。

4.1.1基于流量的樹(shù)干節(jié)點(diǎn)識(shí)別算法

基于流量的樹(shù)干節(jié)點(diǎn)識(shí)別算法如圖7 所示。簇內(nèi)的節(jié)點(diǎn)如果想與控制器通信，必須經(jīng)過(guò)樹(shù)干節(jié)點(diǎn)。因此，樹(shù)干節(jié)點(diǎn)具有較高的流量。一個(gè)簡(jiǎn)便可行的方法是基于概率的原理，以任意節(jié)點(diǎn)為起始節(jié)點(diǎn)，利用廣度優(yōu)先搜索（BFS,breadth first search）算法尋找其到控制器節(jié)點(diǎn)的一條檢測(cè)路徑，并將路徑上經(jīng)過(guò)的節(jié)點(diǎn)流量均加1。生成W條檢測(cè)路徑后，將所有節(jié)點(diǎn)按照被經(jīng)過(guò)的次數(shù)降序排列，選取前|V|δ個(gè)節(jié)點(diǎn)作為樹(shù)干節(jié)點(diǎn)，其中，|V|表示拓?fù)渲泄?jié)點(diǎn)個(gè)數(shù)；δ表示選出節(jié)點(diǎn)的比例，是取值范圍為(0,1)的超參數(shù)。

圖7 基于流量的樹(shù)干節(jié)點(diǎn)識(shí)別算法

4.1.2分簇算法

本節(jié)利用分簇算法對(duì)剩下的節(jié)點(diǎn)進(jìn)行分簇，識(shí)別出所有的簇。分簇算法的思想很簡(jiǎn)單，將所有連通的簇節(jié)點(diǎn)劃分為一個(gè)簇。因此，只要對(duì)所有的非簇節(jié)點(diǎn)遍歷，利用BFS 算法進(jìn)行劃分即可。

所有的非樹(shù)干節(jié)點(diǎn)被分簇，標(biāo)記每個(gè)簇的ID后，接下來(lái)對(duì)鏈路進(jìn)行分類。鏈路的分類很簡(jiǎn)單，只需要遍歷所有鏈路，確定該鏈路所連接的2 個(gè)節(jié)點(diǎn)的類型即可。連接樹(shù)干節(jié)點(diǎn)和樹(shù)干節(jié)點(diǎn)的鏈路被劃分為樹(shù)干鏈路，鏈接樹(shù)干節(jié)點(diǎn)和簇節(jié)點(diǎn)的鏈路被劃分為樹(shù)枝鏈路，鏈接簇節(jié)點(diǎn)和簇節(jié)點(diǎn)的鏈路劃分為簇鏈路。

4.2 離線檢測(cè)矩陣的計(jì)算

對(duì)所有的鏈路進(jìn)行分類后，即可以生成檢測(cè)矩陣。檢測(cè)矩陣的生成步驟與確定性多點(diǎn)故障檢測(cè)機(jī)制相似，不同的是，需要對(duì)不同的鏈路分別進(jìn)行檢測(cè)矩陣的生成。首先，利用簇外檢測(cè)矩陣生成算法對(duì)所有的樹(shù)干鏈路和樹(shù)枝鏈路進(jìn)行檢測(cè)矩陣的構(gòu)造，使其滿足單點(diǎn)故障檢測(cè)性質(zhì)。然后，利用針對(duì)簇的隨機(jī)游走采樣算法，針對(duì)簇的矩陣修補(bǔ)算法和針對(duì)簇的矩陣優(yōu)化算法對(duì)簇鏈路進(jìn)行檢測(cè)矩陣的生成，使每個(gè)簇滿足local-K-identifiable。

4.2.1初始檢測(cè)矩陣生成

樹(shù)干鏈路和樹(shù)枝鏈路會(huì)形成類似樹(shù)的結(jié)構(gòu)。則該問(wèn)題轉(zhuǎn)化為用最少的檢測(cè)路徑對(duì)一棵樹(shù)進(jìn)行單點(diǎn)故障檢測(cè)。簇外檢測(cè)矩陣生成算法拓?fù)滢D(zhuǎn)化如圖8 所示。對(duì)每個(gè)樹(shù)枝鏈路進(jìn)行檢測(cè)，需要生成一條以樹(shù)干鏈路為始的檢測(cè)流；同時(shí)，存在一些樹(shù)干鏈路無(wú)法被區(qū)分。因此，該問(wèn)題的實(shí)質(zhì)是以每個(gè)葉子節(jié)點(diǎn)和單個(gè)子節(jié)點(diǎn)為出發(fā)節(jié)點(diǎn)，生成檢測(cè)路徑。在圖8 中，虛線圈出的節(jié)點(diǎn)為需要生成檢測(cè)路徑的出發(fā)節(jié)點(diǎn)。

圖8 簇外檢測(cè)矩陣生成算法拓?fù)滢D(zhuǎn)化示意

基于上一步生成的簇外檢測(cè)矩陣，可以再對(duì)每一個(gè)簇的簇鏈路進(jìn)行檢測(cè)路徑的構(gòu)造。構(gòu)造的方式與確定性多點(diǎn)故障檢測(cè)機(jī)制相同，構(gòu)造馬爾可夫鏈，在簇內(nèi)采用隨機(jī)游走的策略，對(duì)檢測(cè)路徑進(jìn)行采樣，使其以較大的概率滿足local-K-identifiable性質(zhì)。

4.2.2簇檢測(cè)矩陣修補(bǔ)和優(yōu)化

4.3 在線故障檢測(cè)

在生成了近似最優(yōu)檢測(cè)矩陣Ropt后，將檢測(cè)矩陣轉(zhuǎn)化為檢測(cè)流，在網(wǎng)絡(luò)中周期性地由終端節(jié)點(diǎn)發(fā)送至控制器節(jié)點(diǎn)，控制器節(jié)點(diǎn)通過(guò)收集一定時(shí)間內(nèi)檢測(cè)報(bào)文的到達(dá)情況生成路徑狀態(tài)向量y。接著可以根據(jù)y，反推出鏈路狀態(tài)向量x，進(jìn)而得出故障鏈路集F。在確定性多點(diǎn)故障檢測(cè)機(jī)制中，根據(jù)式(4)，任何檢測(cè)路徑狀態(tài)向量y對(duì)應(yīng)于檢測(cè)矩陣Ropt中任意（k k≤K）個(gè)二維編碼b(li)的“或”操作。但是，在確定性局部多點(diǎn)故障檢測(cè)中，由于Ropt是由簇外檢測(cè)矩陣（單點(diǎn)故障檢測(cè)）和各個(gè)簇檢測(cè)矩陣（多點(diǎn)故障檢測(cè)）組成的，部分路徑狀態(tài)向量y是不存在的，因此不能直接反推出x。

本節(jié)提出離線含簇故障定位算法，枚舉所有可能的鏈路狀態(tài)向量x，通過(guò)Ropt映射得到所有合法的路徑狀態(tài)向量y，并將y存儲(chǔ)為Key，鏈路狀態(tài)向量x所對(duì)應(yīng)的故障鏈路集F存儲(chǔ)為Value。

步驟1簇外矩陣滿足單點(diǎn)故障檢測(cè)性質(zhì)。因此遍歷所有的樹(shù)干鏈路和樹(shù)枝鏈路，用表示，假設(shè)該鏈路故障，則所有包含該鏈路的檢測(cè)路徑均失敗，將檢測(cè)路徑對(duì)應(yīng)的位數(shù)表示為1，從而得到其對(duì)應(yīng)的路徑狀態(tài)向量y0。同時(shí)，將該鏈路放入故障鏈路集F中。該鏈路發(fā)生故障后，其相關(guān)聯(lián)的簇內(nèi)鏈路狀態(tài)無(wú)法進(jìn)行檢測(cè)，因此將與之相關(guān)聯(lián)的簇內(nèi)鏈路均視為故障鏈路，放入故障鏈路集合F中，如圖9 中的虛線圈內(nèi)鏈路所示。若所有的樹(shù)干鏈路和樹(shù)枝鏈路均未發(fā)生故障，則路徑狀態(tài)向量y0表示為全零向量，故障鏈路集表示為空。

圖9 離線含簇故障定位算法步驟1

步驟2各個(gè)簇滿足local-K-identifiable 性質(zhì)。因此，需要檢查各個(gè)簇是否發(fā)生多點(diǎn)故障，如圖10所示。對(duì)每個(gè)簇，假設(shè)該簇內(nèi)的任意（k k≤K）個(gè)鏈路發(fā)生故障，將這些鏈路加入故障鏈路集F中，并將包含該k個(gè)鏈路的檢測(cè)路徑均視為失敗，更新路徑狀態(tài)向量y0中這些檢測(cè)路徑相應(yīng)的位數(shù)為1，得到新的路徑狀態(tài)向量yupdate和Fupdate。遍歷所有簇（不包括步驟1 中的簇）后，即可得到最終的路徑狀態(tài)向量y和F。

圖10 離線含簇故障定位算法步驟2

5 系統(tǒng)驗(yàn)證

本文進(jìn)行了一系列實(shí)驗(yàn)來(lái)驗(yàn)證本文方法的以下優(yōu)勢(shì)：1) 在不同的工業(yè)控制拓?fù)渲?，與基線方法相比，本文方法生成的檢測(cè)路徑數(shù)量更少；2) 隨著鏈路數(shù)量的增加（即網(wǎng)絡(luò)規(guī)模增大），本文方法能產(chǎn)生合理數(shù)量的檢測(cè)路徑。

5.1 仿真實(shí)驗(yàn)

本文仿真實(shí)驗(yàn)使用Java 語(yǔ)言實(shí)現(xiàn)，并將網(wǎng)絡(luò)抽象為節(jié)點(diǎn)、鏈接等對(duì)象；使用二元連通矩陣來(lái)表示拓?fù)浣Y(jié)構(gòu)，作為整個(gè)網(wǎng)絡(luò)的輸入，同時(shí)控制采樣數(shù)、采樣方法等變量，對(duì)最小檢測(cè)路徑數(shù)z和最大可識(shí)別故障K指標(biāo)進(jìn)行了評(píng)價(jià)。

5.2 基線方法

本文采用以下算法作為基線方法。

1) 隨機(jī)游走。文獻(xiàn)[17]介紹了一種隨機(jī)游走構(gòu)造方法來(lái)構(gòu)造檢測(cè)矩陣。其目標(biāo)是設(shè)計(jì)一個(gè)最小行數(shù)的m×n布爾檢測(cè)矩陣。從本質(zhì)上說(shuō)，這是MC-采樣的概念。將這種方法應(yīng)用到本文的實(shí)驗(yàn)場(chǎng)景中，只需要保持采樣直到滿足K-identifiable 或local-K-identifiable。

2) NACGT[18]。NACGT 適用于2K+1 邊連通度的網(wǎng)絡(luò)拓?fù)鋪?lái)檢測(cè)至多K個(gè)故障。其思想是具有2K+1 邊連通性的網(wǎng)絡(luò)至少有K+1 個(gè)邊不相交的生成樹(shù)。因此，至少有一個(gè)生成樹(shù)不包含故障鏈路。使用樹(shù)作為“跳板”來(lái)訪問(wèn)樹(shù)外的鏈路。假設(shè)生成樹(shù)完好無(wú)損，當(dāng)且僅當(dāng)樹(shù)外鏈路為故障鏈路時(shí)時(shí)，該檢測(cè)包才會(huì)失敗。

5.3 幾種典型的工業(yè)控制拓?fù)?/h3>

為了驗(yàn)證該方法在工業(yè)控制領(lǐng)域的通用性和正確性，本文在2 種不同的應(yīng)用場(chǎng)景下進(jìn)行了仿真。這些應(yīng)用場(chǎng)景包括一種典型的工業(yè)網(wǎng)絡(luò)——列車通信網(wǎng)絡(luò)（如圖2 所示）、星形拓?fù)渚W(wǎng)絡(luò)（如圖11所示）和規(guī)模較大的工業(yè)控制網(wǎng)絡(luò)。設(shè)置采樣數(shù)為5m，m表示網(wǎng)絡(luò)拓?fù)渲墟溌返臄?shù)量，轉(zhuǎn)移迭代步長(zhǎng)為50。列車通信網(wǎng)絡(luò)由于拓?fù)潢P(guān)系，最多只能實(shí)現(xiàn)全局1-identifiable，而NACGT 方法不適用于這3 種拓?fù)洹?/p>

圖11 星形拓?fù)渚W(wǎng)絡(luò)

列車通信網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果如表1 所示。隨機(jī)游走方法對(duì)應(yīng)的最大K值為1，表示該方法只能適用于檢測(cè)故障數(shù)量為1 的情況，而本文方法最大K值為2，表示本文方法可檢測(cè)故障數(shù)量為1 或者2 的情況，所以相較于隨機(jī)游走算法，本文方法能夠適用于更多檢測(cè)場(chǎng)景，有更強(qiáng)的檢測(cè)能力。而本文方法最少檢測(cè)路徑多于隨機(jī)游走，是由于本文方法檢測(cè)了更多情況。實(shí)驗(yàn)結(jié)果證明了本文方法能夠?qū)崿F(xiàn)多點(diǎn)故障檢測(cè)，同時(shí)也證明了本文方法針對(duì)整體連通度低但局部連通度高的情況，有更強(qiáng)的檢測(cè)能力。

表1 列車通信網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果

針對(duì)星形拓?fù)渚W(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果如表2 所示。隨機(jī)游走于本文方法對(duì)應(yīng)的最大K值都為2，但是本文方法生成的最少路徑數(shù)量小于隨機(jī)游走。實(shí)驗(yàn)結(jié)果證明了本文方法生成的檢測(cè)流具有更高的效率，能夠更好地滿足網(wǎng)絡(luò)負(fù)載優(yōu)化的要求。

表2 星形拓?fù)渚W(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果

工業(yè)控制網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果如表3 所示。隨機(jī)游走于本文方法對(duì)應(yīng)的最大K值都為4，但是本文方法生成的最少路徑數(shù)量小于隨機(jī)游走。實(shí)驗(yàn)結(jié)果證明了本文方法具有更高的效率，能夠更好地滿足網(wǎng)絡(luò)負(fù)載優(yōu)化的要求。

表3 工業(yè)控制網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果

5.4 網(wǎng)絡(luò)規(guī)模性能對(duì)比

本節(jié)研究最少檢測(cè)路徑數(shù)隨鏈路數(shù)的增加而變化的趨勢(shì)。本文使用具有不同車廂數(shù)的列車通信網(wǎng)絡(luò)，設(shè)置采樣數(shù)為5m，m表示網(wǎng)絡(luò)拓?fù)渲墟溌返臄?shù)量，傳輸?shù)介L(zhǎng)為50，車廂數(shù)為7～11（對(duì)應(yīng)的鏈路數(shù)為35～55 條），每節(jié)車廂的連通度設(shè)置為2，實(shí)驗(yàn)結(jié)果如圖12 所示。隨著鏈路數(shù)的增加，優(yōu)化的近似最優(yōu)矩陣的最小數(shù)目，即最少測(cè)量路徑數(shù)線性增加。

圖12 最少檢測(cè)路徑數(shù)與鏈路數(shù)關(guān)系（連通度為2）

設(shè)置車廂數(shù)為7～11（對(duì)應(yīng)的鏈路數(shù)為56～88 條），每節(jié)車廂的連通度設(shè)置為3，實(shí)驗(yàn)結(jié)果如圖13 所示。隨著鏈路數(shù)的增加，優(yōu)化的近似最優(yōu)矩陣的最小數(shù)目仍線性增加。

圖13 最少檢測(cè)路徑數(shù)與鏈路數(shù)關(guān)系（連通度為3）

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

故障檢測(cè)一直是研究的熱點(diǎn)問(wèn)題。它對(duì)于可靠和實(shí)時(shí)的數(shù)據(jù)傳輸尤其重要?；赥SN 提出了故障檢測(cè)方法的要求：確定性檢測(cè)、網(wǎng)絡(luò)負(fù)載優(yōu)化、多點(diǎn)故障檢測(cè)機(jī)制和適用工業(yè)控制網(wǎng)絡(luò)。然而，現(xiàn)有的故障檢測(cè)方法都不能很好地滿足上述要求。本文設(shè)計(jì)了一個(gè)多點(diǎn)故障確定性檢測(cè)方法來(lái)尋找近似最優(yōu)的最小檢測(cè)路徑。本文方法能夠弱化拓?fù)浼s束，將單點(diǎn)故障檢測(cè)功能升級(jí)為局部多點(diǎn)故障檢測(cè)。算法分為離線檢測(cè)矩陣計(jì)算階段和在線故障檢測(cè)階段。離線檢測(cè)矩陣計(jì)算階段，預(yù)先生成檢測(cè)路徑集；在線故障檢測(cè)階段，控制器采集并檢測(cè)檢測(cè)包的到達(dá)狀態(tài)，并基于布爾網(wǎng)絡(luò)測(cè)繪模型進(jìn)行故障檢測(cè)和定位。最后通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了本文方法的優(yōu)越性。