一種新的基于擴展星型結構的系統級故障診斷算法

周寧，梁家榮

（廣西大學計算機與電子信息學院，廣西南寧530004）

一種新的基于擴展星型結構的系統級故障診斷算法

周寧，梁家榮*

（廣西大學計算機與電子信息學院，廣西南寧530004）

網絡系統級故障診斷是一種重要的針對網絡節點進行故障診斷的方法.通過對網絡系統級故障診斷的PMC模型和MM模型的t可診斷性進行分析，在確定的網絡拓撲結構中構造擴展星型結構，利用圖論的方法對給定的PMC模型和MM模型下的癥狀進行分析和論證，判斷擴展星型結構根節點的狀態.最后基于擴展星型結構判斷網絡節點狀態的證明結果，提出一種新的針對已確定系統診斷度、并能構造出擴展星型結構的多處理器網絡系統的系統級診斷算法——擴展星型結構算法.通過理論證明和實驗結果表明：這種算法能夠簡單、快速并且正確地識別出處理器網絡系統的故障節點，其時間復雜度為O（N），N表示處理器網絡系統的節點個數.

系統級故障診斷；PMC模型；MM模型；擴展星型結構；多處理器網絡系統

0　引言

隨著超大規模集成電路技術的飛速發展，一個多處理器網絡系統可能包含幾百個甚至幾千個處理器；互連網絡高速頻數的交換信息及系統硬件規模的不斷擴大，使得網絡的處理器出現故障是不可避免的.為了確保網絡可靠性，在系統投計時應該考慮其有能力區分故障節點和無故障節點，以便用無故障節點替換故障節點.在故障診斷的過程中，雖然診斷的最終目標是要找出結點中發生故障的邏輯門或芯片，對它進行修復或更換，但如果一開始就把診斷范圍定位于此，不僅需要大量的診斷信息，難以達成目標，而且可能舍本逐末，無法確定故障；因此，需要提高診斷級別，將故障定位到系統級，即只需要識別出發生故障的結點機或通信鏈路，這樣不僅極大地減少了故障診斷所需要的信息，降低了測試費用和診斷難度，而且完全能夠滿足解決系統容錯性問題和維護問題對診斷功能的要求.

1967年Preparata等［1］首次提出了系統級故障診斷的概念和方法，并提出了系統級診斷模型，即PMC模型.PMC模型認為，讓系統中的每一個節點去測試它的鄰居節點，這種測試可能是一套微指令，或者是電子信號配合相應的硬件.如果一個節點認為另一個節點是有故障的，那么給出的測試結果為1；反之給出的測試結果為0，并約定一個無故障的節點所作出的評估總是可靠的，而有故障的節點給出的評估是不可靠的；所有測試結果的集合稱之為系統的癥狀.關于PMC模型下相關的故障診斷度問題已有大量成果［2－7］.

考慮到PMC模型在處理一些復雜網絡時存在的不足，如對于具有高結點度的網絡，利用PMC模型進行診斷，會耗費更多的測試資源，文獻［8］提出了另一種系統級的故障診斷模型，稱之為MM模型；其后，1992年文獻［9］進行了改進，并提出了一種特殊情況的比較模型MM＊故障模型.MM模型假定一個節點將同樣的測試任務分配給它的2個鄰居節點，并比較這2個鄰居節點的輸出.如果2個鄰居節點的輸出結果一致，則認為它們是無故障的；否則它們是有故障的.比較模型不再采用測試的方法來獲取測試結果，而是采用一種更實際的比較機制.由于比較2個結點的處理結果比結點間相互測試更容易，因此，MM比較模型與PMC模型相比更易于實現.對比較模型下的網絡故障診斷理論的研究也取得了不少成果［10－12］.

在網絡的故障診斷理論研究中，故障診斷度和故障診斷算法是2個重要的內容.人們對PMC模型下的故障診斷算法研究已取得了不少成果，如Dahbura等［13］利用最小覆蓋集及最大匹配集理論的時間復雜度為O（N2．5）的故障診斷算法；Kameda等［14］提出了一個基于分支限界法的故障診斷算法，該算法能夠在O（N3）的時間內確定系統的所有故障結點；另外Sullivan［15］提出了一個時間復雜度為O（t3＋｜E｜）的診斷算法.而在MM模型下的已有算法研究成果中，Sengupta等［9］提出了時間復雜度為O（N5）的算法；Yang等［16］則針對超立方體網絡提出了更為有效的、時間復雜度為O（N×Δ3×δ）的診斷算法.

在已有系統級診斷算法的研究成果中，可以發現這類算法或者時間復雜度較高，或者對網絡的拓撲結構有限定性的要求，或者算法的診斷過程較為復雜，難以實現.考慮到星型結構在大多數網絡中存在，提出一種新的適用于已確定診斷度并且能夠構造出擴展星型結構的多處理器網絡系統的系統級診斷算法，即擴展星型結構算法.該算法將網絡中的所有節點都構造一個擴展星型結構，然后遍歷網絡的所有節點并利用本文的證明結論判斷網絡節點的狀態，從而獲得無故障節點的集合和有故障節點的集合（該算法的流程框架如圖1所示）.擴展星型結構算法的特點是：1）基于PMC模型和MM模型；2）適用于能構造出擴展星型結構的t－可診斷系統；3）能夠快速、簡單、正確地診斷出系統中的所有故障節點.這種方法不需要使用專門的測試設備，在不增加系統額外成本的情況下就可以實現系統的快速自診斷.從這個意義上講，這樣的算法對網絡故障診斷理論是一種重要的補充，對網絡的故障診斷有重要的理論意義和應用價值.

圖1　擴展星型結構算法流程圖Fig．1 The algorithm of the extended star structure

1　預備知識

文中，用有向圖G來表示一個互連網絡，其中V（G）和E（G）分別表示圖G的頂點集和邊集.k（G）表示圖G的頂點連通度.

定義1［1］一個系統是t－可診斷的，只要系統中的故障節點數目不超過t個，那么系統中所有故障節點都能夠被正確地識別出來.

在PMC模型中，令有向圖G＝（V，E）表示一個系統，其中V表示系統中所有節點的集合，E表示系統中所有通信連接的集合.對于一對相鄰的節點u，v∈V，有序對（u，v）表示節點u測試節點v.如果節點u是正確的（錯誤的），那么測試結果為0（1），記為γ（u，v）＝0（γ（u，v）＝1）.正確的節點所做的評估總是可靠的，而錯誤的節點所做的評估是不可靠的（如圖2所示）.

在MM模型中，令有向圖G＝（V，E）表示一個系統，其中V表示系統中所有節點的集合，E表示系統中所有通信連接的集合.假定一個節點將同樣的測試任務分配給它的2個鄰居節點，并比較這2個鄰居節點的輸出.用（u；v，w）來表示節點u發送相同的任務給鄰居節點v和w去執行并觀察它們的運行結果.如果節點v和w的運行結果不一致的（一致），那么測試結果為1（0）（如圖3所示）.

圖2　PMC模型Fig．2 The PMC model

圖3　MM模型Fig．3 The MM model

圖4　T型擴展星型結構Fig．4 Type T extended star structure

2　在PMC下的擴展星型結構算法

2.1相關定義

定義2令G＝（V，E）表示一個圖，v∈V，t是一個≥1的整數.用T（v，t）＝（V（v，t），E（v，t））表示一個圖G中以v為根節點按1到t次序擴展的星型結構的子圖，其中V（v；t）＝｛v｝∪｛xi，yi，｜1≤i≤t｝以及E（v；t）＝｛｛v，xi｝，｛xi，yi｝｜1≤i≤t｝（如圖4所示）.

算法名稱：DVUPMC（G，v）

輸入：對于圖G的任意一個節點v，存在以v為根節點的星型擴展結構的子圖T（v，t）.

輸出：v的故障狀態.算法輸出用0表示節點v無故障，用1表示節點v有故障.

算法開始：

1）t≤deg G（v），deg G（v）表示v的度數；

2）構造一個以v為根節點按1到t次序星型擴展結構的子圖T（v，t）；

4）如果n0≥n1返回0，否則1.

算法結束.

定理1令G＝（V，E）表示一個圖，v∈V（G），t≤deg G（v）.假設圖G中存在以v為根節點并且按1到t次序擴展的星型結構的子圖，即T（v，t），那么只要子圖T（v，t）中故障節點的個數不超過t個，算法DVUPMC（G，v）能夠完全正確地判斷節點的故障狀態.

證明：令：

顯然，依照假定有：t＝n0＋n1＋n2＋n3.

首先，考慮節點v為故障節點的情況.用反正法證明，有n0≥n1.由此可以得到在T（v，t）中的故障節點個數至少為2n0＋n1＋n2＋n3＋1，而2n0＋n1＋n2＋n3＋1≥n0＋n1＋n2＋n3＋1＝t＋1，這與題設的T（v，t）中故障節點個數不超過t個相矛盾；因此，當節點v為故障節點時，有n0＜n1.

其次，考慮節點v為無故障節點的情況.用反正法證明，有n0＜n1.由此可以得到在T（v，t）中的故障節點個數至少為2n1＋n2＋n3＋1，而2n1＋n2＋n3＋1≥n0＋n1＋n2＋n3＋1＝t＋1，這與題設的T（v，t）中故障節點個數不超過t個相矛盾；因此，當節點v為無故障節點時，有n0≥n1.定理得證.

2.2多處理器網絡自診斷算法

算法名稱：t－PMC－DIAG

輸入：一個在PMC模型下，由故障節點個數不超過t的具體擴展星型結構的多處理器的網絡產生的癥狀γ.

輸出：一個序列（H，F），H表示被診斷為無故障的節點的集合，F表示被診斷為有故障的節點的集合.

Step1初始化H和F，即H←φ，F←φ；U＝V（G），其中φ表示空集合；

Step2對于多處理器網絡中的每一個節點v，構造一個擴展星型結構，即T（v，t）；然后用算法DVUPMC（G，v）判斷節點v的狀態，如果輸出的狀態為0，則將節點v添加到集合H中，即H←H∪｛v｝；

否則將節點v添加到集合F中，即F←F∪｛v｝；

Step3返回序列（H，F）.

定理2在PMC模型下，在具體擴展星型結構的多處理器網絡運行t－PMC－DIAG的時間復雜度為O（N），其中N表示多處理器網絡的節點個數.

證明：Step1的時間復雜度為O（1），Step2中，因為每個節點都要構造一次擴展星型結構，假設多處理器網絡的節點總數為N個，那么該步驟的時間復雜度為O（N），Step3的時間復雜度為O（1）.綜合Step1～Step3，整個算法的時間復雜度為O（N）.

3　在MM模型下的擴展星型結構算法

定義3令G＝（V，E）表示一個圖，v∈V，t是一個≥1的整數.用Π（v，t）＝（V（v，t），E（v，t））表示一個圖G中以v為根節點按1到t次序擴展的星型結構的子圖，其中V（v；t）＝｛v｝∪｛xi，yi，zi，wi｜1≤i≤t｝以及E（v；t）＝｛｛v，xi｝，｛xi，yi｝，｛yi，zi｝，｛zi，wi｝｜1≤i≤t｝（如圖5所示）.

算法名稱：DVUMM（G，v）

輸入：對于圖G的任意一個節點v，存在以v為根節點的星型擴展結構的子圖Π（v，t）.

輸出：v的故障狀態.算法輸出用0表示節點v無故障，用1表示節點v有故障.

算法開始：

1）t≤deg G（v），deg G（v）表示v的度數；

2）構造一個以v為根節點，度為t的星型擴展結構的子圖Π（v，t）；

4）如果n0≥n1，返回0；否則1.

算法結束.

定理3令G＝（V，E）表示一個圖，v∈V（G），t≤deg G（v）.假設圖G中存在以v為根節點并且按1到t次序擴展的星型結構的子圖，即Π（v，t），那么只要子圖Π（v，t）中故障節點的個數不超過t個，算法DVUMM（G，v）能夠完全正確地判斷節點的故障狀態.

圖5　Π型擴展星型結構Fig．5 Type Π extended star structure

證明：令：

首先，考慮節點v為故障節點的情況.用反正法證明，有n0≥n1.由此可以得到在Π（v，t）中的故障節點個數至少為3n0＋n2＋2n3＋2n4＋n5＋n6＋2n7＋1；而n0＋n2＋2n3＋2n4＋n5＋n6＋2n7＋1≥（n0＋n1＋n2＋n3＋n4＋n5＋n6＋n7）＋2n0＋n3＋n4＋n7＋1≥t＋1．這與題設的Π（v，t）中故障節點個數不超過t個相矛盾；因此，當節點v為故障節點時，有n0＜n1.

其次，考慮節點v為無故障節點的情況.用反正法證明，有n0＜n1.由此可以得到在Π（v，t）中的故障節點個數至少為2n1＋n2＋n3＋n4＋n5＋n6＋n7；而2 n1＋n2＋n3＋n4＋n5＋n6＋n7≥（n0＋n1＋n2＋n3＋n4＋n5＋n6＋n7）＋1≥t＋1，這與題設Π（v，t）中故障節點個數不超過t個相矛盾；因此，當節點v無故障節點時，有n0≥n1.定理得證.

下面是在MM模型下針對具體擴展星型結構的多處理器網絡的自診斷算法：

算法名稱：t－MM－DIAG

輸入：一個在MM模型下，由故障節點個數不超過t的具體擴展星型結構的多處理器網絡產生的癥狀γ.

輸出：一個序列（H，F），H表示被診斷為無故障的節點的集合，F表示被診斷為有故障的節點的集合.

Step1初始化H和F，即H←φ，F←φ；U＝V（G），其中φ表示空集合；

Step2對于多處理器網絡中的每一個節點v，構造一個擴展星型結構，即Π（v，t）中.然后用算法DVUMM（G，v）判斷節點v的狀態，如果輸出的狀態為0，則將節點v添加到集合H中，即H←H∪｛v｝，否則將節點v添加到集合F中，即F←F∪｛v｝；

Step3返回序列（H，F）.

定理4在基于MM模型下，具體擴展星型結構的多處理器網絡運行t－MM－DIAG的時間復雜度為O（N），其中N表示多處理器網絡的節點個數.

證明：Step1的時間復雜度為O（1），Step2中，因為每個節點都要構造一次擴展星型結構，假設多處理器網絡的節點總數為N個，那么該步驟的時間復雜度為O（N），Step3的時間復雜度為O（1）.綜合Step1～Step3，整個算法的時間復雜度為O（N）.

4　實驗模擬

圖6　算法的執行時間隨維度n的變化情況Fig．6 The execution time of algorithm as dimension n

通過計算機模擬t－MM－DIAG算法和t－MM－DIAG算法的執行，對其正確性和性能進行評估.

首先，選擇超立方體作為網絡系統結構，已知n維的超立方體的診斷度為n并且能構造出擴展星型結構；接著，搭建運行算法的軟硬件環境.選擇的硬件為：戴爾Precision T7910系列工作站，軟件為：Linux 64位操作系統，hadoop集群框架，VMware11虛擬機.在VMware11虛擬機中安裝若干Linux 64位操作系統，并用hadoop框架搭建成一個集群，使它們構成一個超立方體網絡；最后，將算法提交到hadoop集群構成的超立方體網絡執行.從3維到10維的超立方體執行算法的時間復雜度如圖6所示.表1表示從3維超立方體到10維超立方體故障節點被檢測出來的個數.從實驗結果可以印證t－MM－DIAG算法和t－MM－DIAG算法是完全正確的，并且相較于Dahbura等［13］提出的故障診斷算法有了大幅的提升.

表1　通過算法檢測出的故障節點的數量Tab.1 The number of faulty nodes detected by the algorithm

5　結論

系統級診斷就是利用網絡系統自身的節點識別出系統中其它節點的狀態，進而將故障的節點替換或者從邏輯上刪除.本文在PMC模型和MM模型下，分別提出了基于擴展星型結構的新的系統級診斷算法.該算法在系統中的故障節點個數不超過t情況下，為系統中的每個節點在系統范圍內構造一個擴展星型結構，然后用DVUPMC算法或DVUMM算法獲得節點的狀態結構，進而獲取整個系統的無故障節點集合和故障節點集合.通過實驗模擬也驗證了算法的正確性.

系統需要周期性的進入診斷模式，以確保系統能夠掌握每一個節點的狀態，不會將任務分配給錯誤的節點.系統級診斷是一個非常重要的研究領域，目前還有許多開放的研究點待研究.

［1］PREPARATA FP，METZE G.CHIEN RT.On the Connection Assignment Problem of Diagnosable Systems［J］．IEEE Transactions on Electronic Computers，1967，16（6）：848－854．

［2］LIANG JR，HUANG Y，YE LC．Diagnosabilities of Exchanged Hypercube Networks under the Pessimistic One－Step Diagnosis Strategy［J］．Journal of Systems Engineering an Electronics，2015，26（2）：415－420．

［3］Y E LC，L IANG JR．Five－Round Adaptive Diagnosis in Hamiltonian Networks［J］．IEEE Trans actions on Parallel and Distributed Systems，2015，26（9）：2459－2464．

［4］ZHU Q，GUO G，WANG D．Relating Diagnosability，Strong Diagnosability and Conditional Diagnosability of Strong Networks［J］．IEEE Transactions on Computers，2014，63（7）：881－885．

［5］HSU HC，WU KS，LIN CK，et al．A Linear Time Pessimistic Diagnosis Algorithm for Hypermesh Multiprocessor Systems under the PMC M odel［J］．IEEE Transactions on Computers，2014，63（12）：2894－2904．

［6］洪月華．基于粗糙k－均值的分布式聚類算法［J］．廣西科技大學學報，2013，24（1）：89－93．

［7］陳偉，孔峰，陶金．神經網絡在網絡檢測中的應用［J］．廣西科技大學學報，2011，22（1）：78－81．

［8］MAENG J，MALEK M．A Comparison Connection Assignment for Self－Diagnosis of Multiprocessor Systems［J］．Symposium on Fault Tolerant Computing，1981，30：173－175．

［9］SENGUPTA A，DANBURA AT．On Self－Diagnosable Multiprocessor Systems：Diagnosis by the Comparison Approach［J］．IEEE Trans actions on Computers，1992，41（11）：1386－1396．

［10］YELC，LIANG JR，LIN HX．A Fast Pessimistic Diagnosis Algorithm for Hypercube－Like Networks under the Comparison Model［J］．IEEE Transactions on Computers，2016：2884-2888．

［11］CHEN CA，CHANG GY，HSIEH SY．Conditional（t，k）－Diagnosis in Graphs by U sing the Comparison Diagnosis Model［J］．IEEE Trans actions on Computers，2015，64（6）：1622－1632．

［12］YE TL，HSIEH SY．A Scalable Comparison－Based Diagnosis Algorithm for Hypercube－Like Networks［J］．IEEE Trans actions on Reliability，2013，62（4）：789－799．

［13］DAHBURA AT，MASSON GM．An O（N2．5）Fault Identication Algorithm for Diagnosable Systems［J］．IEEE Trans actions on Com-puters，1984，33（6）：486－492．

［14］KAMEDA L，TOIDA S，ALLAN F J．A Diagnosing Algorithm for Networks［J］．Information and Control，1975，29（2）：141－148．

［15］SULLIVAN GF．A O（t3＋｜E｜）Fault Identication Algorithm for Diagnosable Systems［J］．IEEE Transactions on Computers，1988，37（4）：388－397．

［16］YANG X，TANG Y．Efficient Fault Identication of Diagnosable Systems under the Comparison Model［J］．IEEE Trans actions on Computers，2007，56（12）：1612－1618．

（學科編輯：黎婭）

A new algorithm of system level fault diagnosis based on extended star structure

ZHOU Ning，LIANG Jia－rong*
（School of Computer and Electronic Information，Guangxi University，Nanning530004，China）

Abstarct：Level fault diagnosis is a kind of important fault diagnosis in network system.By analyzing the property of t-fault conditional diagnosis of PMC fault model and MM fault model,we structure an extended star structure in a defined network topology and use the graph theory to analyze and demonstrate the symptoms of a given PMC model and MM model,then identify the state of the root node of the extended star structure.In the end,we propose a new system level fault diagnosis called extended star structure algorithm for the multi processor network system with extended star structure and certain diagnosis.The theoretical demonstration and experimental results show that this algorithm can easily,fast and correctly identify all faulty nodes in the multiprocessor network system,whose time complexity of the algorithm is O(N),where N is the number of the all nodes of the network.

system-level diagnosis;PMC model;MM model;extended star structure;multiprocessor network system

TP301

A

2095-7335（2016）04-0038-07

10.16375/j.cnki.cn45-1395/t.2016.04.008

2016－05－20

國家自然科學基金項目（61363002）資助．

梁家榮，教授，博士生導師，研究方向：互連網絡的故障診斷理論與應用，E－mail：liangjr＠gxu．edu．cn．