梁若舟，趙曦濱，萬海

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1) 檢測時間不確定?；诟怕实臋z測方法[5-7]預(yù)測鏈路失效或擁塞的概率，不能滿足確定性檢測的要求?；诓紶柧W(wǎng)絡(luò)測繪的方法[9-13]需要多輪迭代檢測，存在檢測時間不確定的問題。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 布爾測繪圖和檢測矩陣

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

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

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

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

其中，∨是邏輯或運算。

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

2.3 K-identifiable 性質(zhì)

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

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

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

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

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

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

擴(kuò)展定理1 來研究單點故障識別問題，考慮K=1，則得到引理1。

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

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

2.4 局部K 點可檢測性質(zhì)

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

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

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

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

2.5 問題定義

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

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

3 確定性多點故障檢測機制

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

圖3 確定性多點故障檢測方法流程

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

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

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

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

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

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

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

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

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

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

圖4 Weighted-MC 采樣算法

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

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

3.2 矩陣修補算法

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

定理2假設(shè)在(K+1)-邊連通圖中構(gòu)造了滿足K-identifiable 性質(zhì)的檢測矩陣R，如果存在2 個不同的鏈路狀態(tài)向量x和x′，它們被檢測矩陣R映射到相同的檢測路徑狀態(tài)向量y，則可以構(gòu)造一個新的檢測路徑來區(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。由于檢測矩陣最多能識別K個故障鏈路，因此≤K。對于任何一個故障鏈路l∈Fj-Fi，l至少有一條新的路徑可以路由到控制器而不經(jīng)過Fi中的鏈路。因為在消除了Fi中的所有鏈路之后，整個網(wǎng)絡(luò)的邊連通度仍然為1。通過引入一條新的檢測路徑，被x映射的檢測路徑狀態(tài)向量變?yōu)閇y,0]，而被x′映射的檢測路徑狀態(tài)向量變?yōu)閇y,1]。由此，可以區(qū)分Fi和Fj。

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

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

圖5 矩陣修補算法

4 確定性局部多點故障檢測機制

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

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

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

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

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

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

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

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

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

與全局性確定性多點故障檢測機制相同，該機制主要分為兩個階段：離線檢測矩陣計算階段和在線故障檢測階段。

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

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

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

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

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

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

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

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

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

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

4.1.1基于流量的樹干節(jié)點識別算法

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

圖7 基于流量的樹干節(jié)點識別算法

4.1.2分簇算法

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

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

4.2 離線檢測矩陣的計算

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

4.2.1初始檢測矩陣生成

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

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

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

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

4.3 在線故障檢測

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

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

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

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

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

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

5 系統(tǒng)驗證

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

5.1 仿真實驗

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

5.2 基線方法

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

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

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

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

為了驗證該方法在工業(yè)控制領(lǐng)域的通用性和正確性，本文在2 種不同的應(yīng)用場景下進(jìn)行了仿真。這些應(yī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)移迭代步長為50。列車通信網(wǎng)絡(luò)由于拓?fù)潢P(guān)系，最多只能實現(xiàn)全局1-identifiable，而NACGT 方法不適用于這3 種拓?fù)洹?/p>

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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