針對工業控制拓撲的確定性局部多點故障檢測方法

梁若舟，趙曦濱，萬海

（清華大學軟件學院，北京 100084）

1 引言

時間敏感網絡（TSN，time-sensitive networking）是一種確定性傳輸網絡。它確保了可靠、確定和實時的網絡數據傳輸，滿足了工業控制應用對實時性、確定性的需求。TSN 根據預先計算的調度表傳輸實時數據。調度表是根據網絡拓撲結構和應用數據傳輸要求獲得的。當網絡發生故障（如鏈路故障）時，網絡拓撲會發生改變，從而導致調度表失效，引起實時數據傳輸服務的降級。當網絡發生故障時，為了重新計算調度表，TSN 需要對發生故障的鏈路或節點進行定位，以獲得最新的網絡拓撲。調度表的重新配置將中斷實時數據傳輸。因此，需要在確定的時間內盡快獲得最新的網絡拓撲。

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

圖1 布爾網絡測繪模型

Duffield[15]提出的方法是檢測網絡故障的經典方法。它通過檢測不同端到端路徑的狀態來推斷單個鏈路是擁塞還是失敗。文獻[16]提出了一種應用于一般網絡拓撲中布爾網絡測繪問題的經典方法，主要分為兩類：非自適應檢測和自適應檢測。非自適應檢測[17-19]在鏈路故障檢測過程中并行地發送所有數據包。自適應檢測[10,20-22]根據已經獲得的檢測數據包的結果依次建立檢測路徑。

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

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

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

在工業控制拓撲的應用場景中，一種理想的鏈路故障檢測方法應具有以下性質。

1) 確定性檢測。此處的確定性有兩層含義：①拓撲發現所用的時間是有界的；②方法檢測到的鏈路狀態是確定性的，而不是概率性的。

2) 網絡負載優化。檢測方法應使用盡可能少的檢測包，以減少帶寬消耗。

3) 多點故障檢測。檢測方法應盡可能多地發現故障。

4) 適用于工業控制拓撲。工業控制拓撲具有局部連通度高、整體連通度低的特點。例如，在圖2所示的工業控制拓撲中，在路徑S0—S1—S8—S12—S16—S20—S24中只能實現單點故障檢測，但在局部如Car1中可以實現多點故障檢測。

圖2 一種工業控制拓撲

目前的方法并不能完全滿足工業控制拓撲鏈路故障檢測的上述4 個性質。具體而言，它們具有以下不足之處。

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

2) 未對網絡負載優化。當前方法未對生成的檢測包數量進行優化，影響性能。

3) 無法應對多點故障檢測場景。Bai 等[10]提出的基于二元觀測模型進行網絡監測的兩階段方法只能應用于單點故障檢測。

4) 無法適應工業控制拓撲特點。當前方法未針對工業控制拓撲整體連通度低、局部連通度高的特點進行優化，降低了對于局部高連通度部分的檢測能力。

針對以上不足之處，本文提出了一種針對工業控制拓撲的確定性局部多點故障檢測方法。該方法的基本思路如下。

首先，根據當前網絡拓撲結構，識別網絡中連通度較低的主干部分和連通度較高的簇，對主干部分使用單點故障檢測方法生成檢測流，對簇使用多點故障檢測方法生成檢測流。然后利用檢測流優化算法減少檢測流的數量。每個檢測流從某個節點開始，經過指定的路由，最后到達TSN 控制器。

其次，為每個檢測流分配一個傳輸周期和最壞時延，并在此基礎上生成檢測流的TSN 調度表。當網絡運行時，每個檢測包從起始節點按照預定的時間周期與檢測流一起周期性地發送，并到達TSN 控制器。當故障發生時，一些檢測包將無法到達TSN控制器。TSN 控制器定期收集每個檢測包的到達或故障狀態信息，并使用拓撲發現算法獲得鏈路狀態和網絡拓撲。

此外，為了保證整個故障檢測過程的時間確定性，檢測流需要在確定的時間范圍內到達控制器。本文將檢測流實現為TSN 數據流，從而實現了檢測流傳輸的時間確定性。IEEE 802.1Qav 標準中闡述了隊列及轉發協議能夠確保傳輸時延控制在一定的范圍內；IEEE 802.1Qbv 標準中使用了時間感知整形器，保障業務流消息的傳輸時延是確定的；IEEE 802.1Qch 標準中引入了周期性排隊與轉發機制。上述3 個標準可以保證檢測流在確定的時間內到達控制器節點。IEEE 802.1 Qca 標準定義的路徑控制和保留，以及IEEE 802.1CB 標準定義的幀復制和消除可以控制每個檢測流的路由。

本文貢獻總結如下。

1) 基于工業控制拓撲的場景，本文提出了一種基于布爾網絡測繪的確定性局部多點故障檢測方法。本文提出的檢測框架可以針對工業拓撲主干連通度低、局部連通度高的特點，生成近似最優的檢測路徑集，實現局部多點故障檢測。利用TSN 的確定性傳輸機制，該檢測過程時間上界是確定的。

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

2 系統模型與問題定義

2.1 網絡模型

網絡拓撲被定義為一個無向圖G(V,L)。所有交換機和端節點的集合由頂點表示。所有物理鏈路的集合由邊表示。

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

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

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

2.2 布爾測繪圖和檢測矩陣

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

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

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

相應地，可以得到鏈路狀態向量和檢測路徑狀態向量之間的關系為

其中，∨是邏輯或運算。

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

2.3 K-identifiable 性質

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

假設網絡中有K個故障鏈路。不失一般性地，給定鏈路狀態向量x，其中，則檢測路徑狀態向量y可以表示為

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

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

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

則稱li相對于P滿足K-identifiable 性質。

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

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

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

2.4 局部K 點可檢測性質

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

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

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

則稱li在簇cr內相對于P滿足local-K-identifiable性質。

2.5 問題定義

由于全局網絡的邊連通度較低，可能不滿足K-identifiable 性質。這會使一些網絡僅可以進行單點故障檢測。但事實上，網絡的稠密是不均勻的，局部比較密集的網絡可以實現多點故障檢測。可以將這些比較稠密的局部網絡識別為簇，對每個簇進行多點故障識別。因此，需要設計一種有效的檢測矩陣構造方法，使用盡可能少的檢測路徑，使每個簇滿足local-K-identifiable 性質。該約束優化問題定義為

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

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

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

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

離線檢測矩陣計算的目標是構造一個檢測矩陣，該矩陣在滿足K-identifiable 性質的前提下，所需的檢測流數盡可能少。此階段進一步分為3 個步驟。

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

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

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

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

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

3.1 改進的基于馬爾可夫鏈的采樣算法

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

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

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

圖4 Weighted-MC 采樣算法

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

其中，qij表示節點i到節點j的轉移概率，nik表示通過以i和k為節點的邊路徑數量，q表示節點到自身的轉移概率。圖4 中，當前狀態si對應節點vi，其父節點是vi-1，鄰居節點是vi+1和vi+2。

3.2 矩陣修補算法

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

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

證明假設由x和x′表示的故障鏈路集是Fi和Fj，Fj≥Fi。Fi和Fj之間有3 種關系：Fi?Fj，Fi∩Fj=?，Fi∩Fj≠?,Fi?Fj。

1)Fi?Fj。由于檢測矩陣最多能識別K個故障鏈路，因此≤K。對于任何一個故障鏈路l∈Fj-Fi，l至少有一條新的路徑可以路由到控制器而不經過Fi中的鏈路。因為在消除了Fi中的所有鏈路之后，整個網絡的邊連通度仍然為1。通過引入一條新的檢測路徑，被x映射的檢測路徑狀態向量變為[y,0]，而被x′映射的檢測路徑狀態向量變為[y,1]。由此，可以區分Fi和Fj。

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

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

圖5 矩陣修補算法

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

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

本文將這種網絡抽象為圖6 所示的網絡拓撲。整個網絡抽象為邊連通度較低的樹干和邊連通度較高的簇。圖6 中的×表示該鏈路發生故障。如果鏈路li發生故障，則無論簇內的鏈路狀態如何，經過簇內的檢測路徑均會被li影響，不能到達控制器。因此，整個網絡降級為單點故障檢測。

圖6 連通度不均勻的網絡拓撲

本文的目的是設計一種確定性局部多點故障檢測機制，降低K-identifiable 性質對該拓撲的約束，從而滿足樹干單點檢測、簇內多點檢測的性質，即滿足local-K-identifiable 性質。基于此，將網絡中的節點分為兩類，鏈路分為三類具體描述如下。

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

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

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

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

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

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

離線檢測矩陣計算的目標是構造一個檢測矩陣，使在同一個簇內的鏈路滿足local-K-identifiable性質，不在任何簇內的節點滿足單點故障檢測性質，同時，其所需的檢測流數目盡可能少。此階段進一步分為以下步驟。

步驟1對網絡拓撲進行預處理，通過基于流量的樹干節點識別算法識別出所有的樹干節點，然后對剩余的節點進行分簇，形成r個簇C={c0,c1,…,cr}，使具有較高連通度的節點們被分到一個簇內。

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

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

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

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

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

4.1 網絡預處理

本節對網絡拓撲進行預處理，區分所有的樹干節點、簇節點、樹干鏈路、樹枝鏈路和簇鏈路。然后針對簇鏈路和非簇鏈路分別生成檢測路徑。該過程分為兩步：首先識別出所有的樹干節點，然后對剩余的節點進行分簇。

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

4.1.1基于流量的樹干節點識別算法

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

圖7 基于流量的樹干節點識別算法

4.1.2分簇算法

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

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

4.2 離線檢測矩陣的計算

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

4.2.1初始檢測矩陣生成

樹干鏈路和樹枝鏈路會形成類似樹的結構。則該問題轉化為用最少的檢測路徑對一棵樹進行單點故障檢測。簇外檢測矩陣生成算法拓撲轉化如圖8 所示。對每個樹枝鏈路進行檢測，需要生成一條以樹干鏈路為始的檢測流；同時，存在一些樹干鏈路無法被區分。因此，該問題的實質是以每個葉子節點和單個子節點為出發節點，生成檢測路徑。在圖8 中，虛線圈出的節點為需要生成檢測路徑的出發節點。

圖8 簇外檢測矩陣生成算法拓撲轉化示意

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

4.2.2簇檢測矩陣修補和優化

4.3 在線故障檢測

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

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

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

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

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

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

5 系統驗證

本文進行了一系列實驗來驗證本文方法的以下優勢：1) 在不同的工業控制拓撲中，與基線方法相比，本文方法生成的檢測路徑數量更少；2) 隨著鏈路數量的增加（即網絡規模增大），本文方法能產生合理數量的檢測路徑。

5.1 仿真實驗

本文仿真實驗使用Java 語言實現，并將網絡抽象為節點、鏈接等對象；使用二元連通矩陣來表示拓撲結構，作為整個網絡的輸入，同時控制采樣數、采樣方法等變量，對最小檢測路徑數z和最大可識別故障K指標進行了評價。

5.2 基線方法

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

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

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

5.3 幾種典型的工業控制拓撲

為了驗證該方法在工業控制領域的通用性和正確性，本文在2 種不同的應用場景下進行了仿真。這些應用場景包括一種典型的工業網絡——列車通信網絡（如圖2 所示）、星形拓撲網絡（如圖11所示）和規模較大的工業控制網絡。設置采樣數為5m，m表示網絡拓撲中鏈路的數量，轉移迭代步長為50。列車通信網絡由于拓撲關系，最多只能實現全局1-identifiable，而NACGT 方法不適用于這3 種拓撲。

圖11 星形拓撲網絡

列車通信網絡的實驗結果如表1 所示。隨機游走方法對應的最大K值為1，表示該方法只能適用于檢測故障數量為1 的情況，而本文方法最大K值為2，表示本文方法可檢測故障數量為1 或者2 的情況，所以相較于隨機游走算法，本文方法能夠適用于更多檢測場景，有更強的檢測能力。而本文方法最少檢測路徑多于隨機游走，是由于本文方法檢測了更多情況。實驗結果證明了本文方法能夠實現多點故障檢測，同時也證明了本文方法針對整體連通度低但局部連通度高的情況，有更強的檢測能力。

表1 列車通信網絡的實驗結果

針對星形拓撲網絡的實驗結果如表2 所示。隨機游走于本文方法對應的最大K值都為2，但是本文方法生成的最少路徑數量小于隨機游走。實驗結果證明了本文方法生成的檢測流具有更高的效率，能夠更好地滿足網絡負載優化的要求。

表2 星形拓撲網絡的實驗結果

工業控制網絡的實驗結果如表3 所示。隨機游走于本文方法對應的最大K值都為4，但是本文方法生成的最少路徑數量小于隨機游走。實驗結果證明了本文方法具有更高的效率，能夠更好地滿足網絡負載優化的要求。

表3 工業控制網絡的實驗結果

5.4 網絡規模性能對比

本節研究最少檢測路徑數隨鏈路數的增加而變化的趨勢。本文使用具有不同車廂數的列車通信網絡，設置采樣數為5m，m表示網絡拓撲中鏈路的數量，傳輸迭代步長為50，車廂數為7～11（對應的鏈路數為35～55 條），每節車廂的連通度設置為2，實驗結果如圖12 所示。隨著鏈路數的增加，優化的近似最優矩陣的最小數目，即最少測量路徑數線性增加。

圖12 最少檢測路徑數與鏈路數關系（連通度為2）

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

圖13 最少檢測路徑數與鏈路數關系（連通度為3）

6 結束語

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