周寧，梁家榮

（廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西南寧530004）

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

周寧，梁家榮*

（廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西南寧530004）

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

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

0　引言

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

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

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

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

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

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

1　預(yù)備知識(shí)

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

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

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

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

圖2　PMC模型Fig．2 The PMC model

圖3　MM模型Fig．3 The MM model

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

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

2.1相關(guān)定義

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

算法名稱(chēng)：DVUPMC（G，v）

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

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

算法開(kāi)始：

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

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

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

算法結(jié)束.

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

證明：令：

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

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

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

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

算法名稱(chēng)：t－PMC－DIAG

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

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

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

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

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

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

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

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

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

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

算法名稱(chēng)：DVUMM（G，v）

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

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

算法開(kāi)始：

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

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

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

算法結(jié)束.

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

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

證明：令：

首先，考慮節(jié)點(diǎn)v為故障節(jié)點(diǎn)的情況.用反正法證明，有n0≥n1.由此可以得到在Π（v，t）中的故障節(jié)點(diǎn)個(gè)數(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é)點(diǎn)個(gè)數(shù)不超過(guò)t個(gè)相矛盾；因此，當(dāng)節(jié)點(diǎn)v為故障節(jié)點(diǎn)時(shí)，有n0＜n1.

其次，考慮節(jié)點(diǎn)v為無(wú)故障節(jié)點(diǎn)的情況.用反正法證明，有n0＜n1.由此可以得到在Π（v，t）中的故障節(jié)點(diǎn)個(gè)數(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é)點(diǎn)個(gè)數(shù)不超過(guò)t個(gè)相矛盾；因此，當(dāng)節(jié)點(diǎn)v無(wú)故障節(jié)點(diǎn)時(shí)，有n0≥n1.定理得證.

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

算法名稱(chēng)：t－MM－DIAG

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

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

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

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

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

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

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

4　實(shí)驗(yàn)?zāi)M

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

通過(guò)計(jì)算機(jī)模擬t－MM－DIAG算法和t－MM－DIAG算法的執(zhí)行，對(duì)其正確性和性能進(jìn)行評(píng)估.

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

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

5　結(jié)論

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

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

［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－均值的分布式聚類(lèi)算法［J］．廣西科技大學(xué)學(xué)報(bào)，2013，24（1）：89－93．

［7］陳偉，孔峰，陶金．神經(jīng)網(wǎng)絡(luò)在網(wǎng)絡(luò)檢測(cè)中的應(yīng)用［J］．廣西科技大學(xué)學(xué)報(bào)，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．

（學(xué)科編輯：黎婭）

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

國(guó)家自然科學(xué)基金項(xiàng)目（61363002）資助．

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