一種新的基于擴展星型結(jié)構(gòu)的系統(tǒng)級故障診斷算法

周寧，梁家榮

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

一種新的基于擴展星型結(jié)構(gòu)的系統(tǒng)級故障診斷算法

周寧，梁家榮*

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

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

系統(tǒng)級故障診斷；PMC模型；MM模型；擴展星型結(jié)構(gòu)；多處理器網(wǎng)絡(luò)系統(tǒng)

0　引言

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

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

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

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

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

圖1　擴展星型結(jié)構(gòu)算法流程圖Fig．1 The algorithm of the extended star structure

1　預(yù)備知識

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

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

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

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

圖2　PMC模型Fig．2 The PMC model

圖3　MM模型Fig．3 The MM model

圖4　T型擴展星型結(jié)構(gòu)Fig．4 Type T extended star structure

2　在PMC下的擴展星型結(jié)構(gòu)算法

2.1相關(guān)定義

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

算法名稱：DVUPMC（G，v）

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

輸出：v的故障狀態(tài).算法輸出用0表示節(jié)點v無故障，用1表示節(jié)點v有故障.

算法開始：

1）t≤deg G（v），deg G（v）表示v的度數(shù)；

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

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

算法結(jié)束.

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

證明：令：

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

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

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

2.2多處理器網(wǎng)絡(luò)自診斷算法

算法名稱：t－PMC－DIAG

輸入：一個在PMC模型下，由故障節(jié)點個數(shù)不超過t的具體擴展星型結(jié)構(gòu)的多處理器的網(wǎng)絡(luò)產(chǎn)生的癥狀γ.

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

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

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

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

Step3返回序列（H，F(xiàn)）.

定理2在PMC模型下，在具體擴展星型結(jié)構(gòu)的多處理器網(wǎng)絡(luò)運行t－PMC－DIAG的時間復雜度為O（N），其中N表示多處理器網(wǎng)絡(luò)的節(jié)點個數(shù).

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

3　在MM模型下的擴展星型結(jié)構(gòu)算法

定義3令G＝（V，E）表示一個圖，v∈V，t是一個≥1的整數(shù).用Π（v，t）＝（V（v，t），E（v，t））表示一個圖G中以v為根節(jié)點按1到t次序擴展的星型結(jié)構(gòu)的子圖，其中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的任意一個節(jié)點v，存在以v為根節(jié)點的星型擴展結(jié)構(gòu)的子圖Π（v，t）.

輸出：v的故障狀態(tài).算法輸出用0表示節(jié)點v無故障，用1表示節(jié)點v有故障.

算法開始：

1）t≤deg G（v），deg G（v）表示v的度數(shù)；

2）構(gòu)造一個以v為根節(jié)點，度為t的星型擴展結(jié)構(gòu)的子圖Π（v，t）；

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

算法結(jié)束.

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

圖5　Π型擴展星型結(jié)構(gòu)Fig．5 Type Π extended star structure

證明：令：

首先，考慮節(jié)點v為故障節(jié)點的情況.用反正法證明，有n0≥n1.由此可以得到在Π（v，t）中的故障節(jié)點個數(shù)至少為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．這與題設(shè)的Π（v，t）中故障節(jié)點個數(shù)不超過t個相矛盾；因此，當節(jié)點v為故障節(jié)點時，有n0＜n1.

其次，考慮節(jié)點v為無故障節(jié)點的情況.用反正法證明，有n0＜n1.由此可以得到在Π（v，t）中的故障節(jié)點個數(shù)至少為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，這與題設(shè)Π（v，t）中故障節(jié)點個數(shù)不超過t個相矛盾；因此，當節(jié)點v無故障節(jié)點時，有n0≥n1.定理得證.

下面是在MM模型下針對具體擴展星型結(jié)構(gòu)的多處理器網(wǎng)絡(luò)的自診斷算法：

算法名稱：t－MM－DIAG

輸入：一個在MM模型下，由故障節(jié)點個數(shù)不超過t的具體擴展星型結(jié)構(gòu)的多處理器網(wǎng)絡(luò)產(chǎn)生的癥狀γ.

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

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

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

Step3返回序列（H，F(xiàn)）.

定理4在基于MM模型下，具體擴展星型結(jié)構(gòu)的多處理器網(wǎng)絡(luò)運行t－MM－DIAG的時間復雜度為O（N），其中N表示多處理器網(wǎng)絡(luò)的節(jié)點個數(shù).

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

4　實驗?zāi)M

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

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

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

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

5　結(jié)論

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

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

［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īng)網(wǎng)絡(luò)在網(wǎng)絡(luò)檢測中的應(yīng)用［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）資助．

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