宣恒農(nóng)，張潤馳，何 濤，劉凌波

（1.南京財(cái)經(jīng)大學(xué)信息工程學(xué)院，江蘇 南京 210046；2.亞信科技（南京）有限公司，江蘇 南京 210036）

PMC模型下的一個(gè)貪婪診斷算法*

宣恒農(nóng)1，張潤馳1，何 濤2，劉凌波1

（1.南京財(cái)經(jīng)大學(xué)信息工程學(xué)院，江蘇 南京 210046；2.亞信科技（南京）有限公司，江蘇 南京 210036）

提出了一種PMC模型下基于矩陣運(yùn)算的貪婪診斷算法——MGFD算法。算法結(jié)合作者曾經(jīng)提出的“絕對故障基”思想，首先剔除絕對故障基，得到一個(gè)維度減小的矩陣，之后根據(jù)該矩陣求得集團(tuán)。在文獻(xiàn)［10］提出的四個(gè)貪婪診斷算法的基礎(chǔ)上，提出集團(tuán)的內(nèi)貪婪因子、外貪婪因子、綜合貪婪因子等概念，設(shè)計(jì)了新的貪婪準(zhǔn)則。論證了 MGFD算法的正確性，并對算法進(jìn)行了實(shí)驗(yàn)仿真。實(shí)驗(yàn)結(jié)果表明，MGFD算法相比文獻(xiàn)［10］提出的貪婪診斷算法，具有較高的診斷正確率。

系統(tǒng)級故障診斷；PMC模型；絕對故障基；集團(tuán)；貪婪診斷算法；綜合貪婪因子；MGFD算法

1 引言

隨著大數(shù)據(jù)時(shí)代的到來，計(jì)算機(jī)系統(tǒng)在社會(huì)生

活中扮演著越來越重要的角色，系統(tǒng)的可靠性和穩(wěn)

定性也成為人們?nèi)找骊P(guān)心的話題。尤其是在軍事、航天航空、電子商務(wù)等重要領(lǐng)域，系統(tǒng)發(fā)生故障經(jīng)常會(huì)引起災(zāi)難性的后果，同時(shí)造成巨大的經(jīng)濟(jì)損失，因 此故 障規(guī) 避［1，2］與 模塊冗 余［3］就成 了人們 解決這個(gè)問題的關(guān)鍵措施。然而，這兩種措施在具體實(shí)現(xiàn)上、在控制系統(tǒng)成本和維護(hù)開銷上，有很大的難度和一定的局限性。于是，通過測試、診斷來確定系統(tǒng)中故障單元的系統(tǒng)級故障診斷，就成為保證整個(gè)系統(tǒng)安全與穩(wěn)定非常重要的手段。

對系統(tǒng)級故障診斷的研究是建立在故障模型基礎(chǔ)之上的。當(dāng)前主要的研究模型包括PMC （Preparata-Metze-Chien）模型［4］、BGM模型、Chwa&Hakimi模型與Malek模型等。其中，根據(jù)PMC模型的定義，任意一對互測單元的測試結(jié)果根據(jù)雙方的故障狀態(tài)分為四種情況：正常單元測試正常單元，其結(jié)果必為正常；正常單元測試故障單元，其結(jié)果必為故障；故障單元測試正常單元或故障單元，其結(jié)果可能為正常，亦可能為故障。設(shè)存在一個(gè)由有限個(gè)單元組成的系統(tǒng)X=｛x1，x2…xn｝，?xi∈X，令xi=1表示xi正常，xi=—1表示xi存在故障，xi=0表示xi可能為正常，也可能為故障。令wij=1表示xi測試xj結(jié)果為正常，wij=—1表示xi測試xj結(jié)果為故障，wij=0表示xi對xj無測試。將全部這樣的wij以i為行號、j為列號的規(guī)則存儲在一個(gè)n行n列的矩陣A中，稱矩陣A為系統(tǒng)X的一個(gè)測試癥候矩陣。

系統(tǒng)級故障診斷近幾年的主要研究成果包括基于圖論 的 診 斷 算 法［5～10］和基 于 方 程 的 診 斷算法［11～14］兩 大 類 ?；?圖 論 的 診 斷算 法 將 測試 癥 候矩陣與圖論原理相結(jié)合，通過邏輯推導(dǎo)與圖論運(yùn)算，求出各單元的故障狀態(tài)；基于方程的診斷算法將系統(tǒng)級故障診斷問題以方程的形式表現(xiàn)出來，通過對測試癥候矩陣的方程運(yùn)算求得相容解。相關(guān)理論分析與實(shí)驗(yàn)仿真均表明：當(dāng)系統(tǒng)中故障單元數(shù)遠(yuǎn)小于總單元數(shù)的一半時(shí)，基于圖論的診斷算法具有較高的診斷正確率，尤其是文獻(xiàn)［10］提出的貪婪算法1，其診斷正確率接近100%，且時(shí)間復(fù)雜度不高；當(dāng)系統(tǒng)中故障單元數(shù)遠(yuǎn)大于總單元數(shù)的一半時(shí)，基于圖論的診斷算法正確率明顯下降，此時(shí)文獻(xiàn)［11～14］提出的基于方程的診斷算法具有較高的診斷正確率。然而，當(dāng)故障單元數(shù)接近系統(tǒng)中總單元數(shù)的一半時(shí)，上述各算法均不能得到較為滿意的診斷結(jié)果。本文在文獻(xiàn)［9～12］的基礎(chǔ)上，提出了一個(gè)在PMC模型下基于矩陣運(yùn)算的貪婪診斷算法——MGFD（Matrix based Greedy Fault Diagnosis）算法。

MGFD算法主要分為三個(gè)步驟：首先，結(jié)合作者曾經(jīng)提出的“絕對故障基”概念，通過剔除絕對故障基，降低測試癥候矩陣的維數(shù)；接著，根據(jù)降維后的測試癥候矩陣求出集團(tuán)；最后，以提出的“綜合貪婪因子”作為算法的貪婪準(zhǔn)則，進(jìn)行貪婪診斷。經(jīng)實(shí)驗(yàn)驗(yàn)證，當(dāng)系統(tǒng)中故障單元數(shù)接近一半時(shí)，MGFD算法具有明顯的優(yōu)越性。

2 貪婪診斷算法

根據(jù)診斷結(jié)果的精確程度，診斷算法可分為確定性診斷與概率性診斷兩類。確定性診斷算法能夠診斷出系統(tǒng)中的所有故障單元（完全診斷），且無正常單元被誤診斷為故障單元（正確診斷），但往往具有較高的時(shí)間復(fù)雜度，且對系統(tǒng)的結(jié)構(gòu)與連通度具有一定的要求；概率性診斷以犧牲診斷結(jié)果的精度為代價(jià)，換取診斷過程的低開銷，同時(shí)診斷結(jié)果的正確性也保持在可接受的范圍之內(nèi)，從而提高算法的診斷能力，因此應(yīng)用范圍較廣。貪婪診斷算法作為概率性診斷算法的一種，其特點(diǎn)是算法的每一次迭代均以當(dāng)前信息為基礎(chǔ)，根據(jù)某個(gè)貪婪準(zhǔn)則作出當(dāng)前最優(yōu)選擇，而不考慮各種后續(xù)步驟的情況，從而省去了為搜索全局最優(yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。每做一次選擇，就將所求問題簡化為一個(gè)規(guī)模更小的子問題，通過每一步的貪心迭代，得到問題的一個(gè)最優(yōu)解。與其它診斷算法相比，貪婪診斷算法具有實(shí)現(xiàn)簡單、時(shí)間復(fù)雜度低、診斷正確率較高等特點(diǎn)。

文獻(xiàn)［9］提出了集團(tuán)的概念：

對任一連通圖G（U，E）（其中U為圖中單元集，E為圖中單元間邊集），H叫做連通圖G（U，E）的一個(gè)集團(tuán)，當(dāng)且僅當(dāng)：

（1）H中如果多于一個(gè)單元時(shí)，H中任意兩單元之間至少有一條權(quán)全為1/1的通路。

（2）對任意一個(gè)單元xi∈H，如果與H外的單元xj相鄰接，則wij、wji不同時(shí)為0。

集團(tuán)的性質(zhì)1 集團(tuán)H中的所有單元，要么同時(shí)為正常單元，要么同時(shí)為故障單元。

集團(tuán)的性質(zhì)2 正常集團(tuán)的鄰接集全部為故障集團(tuán)。

文獻(xiàn)［10］提出了四個(gè)基于集團(tuán)理論的貪婪診斷算法，四個(gè)貪婪診斷算法的差別在于貪婪準(zhǔn)則不同，這四個(gè)算法也同樣適用于PMC模型。其中，算法1與算法2分別以各集團(tuán)所含單元數(shù)目的大小作為算法的貪婪準(zhǔn)則：算法1優(yōu)先選取包含單元數(shù)最多的集團(tuán)為正常集團(tuán)，算法2優(yōu)先選取包含單元數(shù)最少的集團(tuán)為故障集團(tuán)。算法3與算法4分別以各集團(tuán)的相鄰集團(tuán)所含單元數(shù)目的大小作為算法的貪婪準(zhǔn)則：算法3優(yōu)先選取相鄰集團(tuán)包含單元數(shù)最少的集團(tuán)為正常集團(tuán)，算法4優(yōu)先選取相鄰集團(tuán)包含單元數(shù)最多的集團(tuán)為故障集團(tuán)。四個(gè)貪婪算法中，算法1的診斷正確率相對最高。若記第i個(gè)集團(tuán)為Hi，集團(tuán)Hi的鄰接集為C（Hi），Hi中的單元數(shù)目為|Hi|，則算法1的主要過程可表述如下：

步驟1 根據(jù)測試癥候矩陣生成集團(tuán)。

步驟2 識別絕對故障集團(tuán)。

步驟3 對剩余集團(tuán)按各自節(jié)單元數(shù)進(jìn)行排序，設(shè)排序后滿足|H1|≥|H2|≥…≥|Hi|。

步驟4 選擇包含單元最多的集團(tuán)為正常集團(tuán)，其相鄰基團(tuán)置為故障集團(tuán)。若存在兩個(gè)集團(tuán)|Hp|=|Hp+1|，設(shè)C（H'）為 C（H）中 已 判 定 為 故 障 集 團(tuán) 的 集 團(tuán)，若|C（Hp）|—|C（H'p）|≤|C（Hp+1）|—|C（H'p+1）|，則置Hp為正常集團(tuán)。

步驟5 若還存在未被確定狀態(tài)的集團(tuán)，重復(fù)步驟4；否則，算法結(jié)束。

3 MGFD算法的主要過程

3.1 剔除絕對故障基

文獻(xiàn)［11］提出了絕對故障基的概念。同時(shí)，文獻(xiàn)［12］給出了基于測試癥候矩陣的絕對故障基求法。設(shè)A為一個(gè)n維PMC模型的測試癥候矩陣，TA為關(guān)于A的絕對故障基（即包含所有必存在故障的單元的集合），則TA可按如下方式得到：

將A—A'中元素2所在行的行數(shù)代表的單元［11］合并組成TA。其中A'為A的轉(zhuǎn)置矩陣。

在求得絕對故障基TA后，將測試癥候矩陣A中各絕對故障單元所在的行、列刪除，得到不包含絕對故障單元的癥候矩陣B。矩陣B相對于測試癥候矩陣A降低了維數(shù)，減少了后續(xù)運(yùn)算的數(shù)據(jù)量。

3.2 求集團(tuán)

文獻(xiàn)［9］提出了一種求集團(tuán)的算法，該算法的時(shí)間復(fù)雜度為O（n2）。在求得各集團(tuán)后，將各集團(tuán)中所有的點(diǎn)歸并為一個(gè)集團(tuán)點(diǎn)，按矩陣B中的連接方式相連，形成集團(tuán)間的測試矩陣C。

3.3 設(shè)計(jì)貪婪準(zhǔn)則

概率性診斷算法以“相信大多數(shù)”作為基本診斷原理，即“相信系統(tǒng)中大多數(shù)單元為正常單元，從而接受大多數(shù)單元的測試結(jié)果”。若與集團(tuán)的思想相結(jié)合，其診斷原理可引申為：某一集團(tuán)所含單元數(shù)越多，且其鄰接集包含的單元數(shù)越少，該集團(tuán)為正常集團(tuán)的可能性越大。假設(shè)系統(tǒng)中各單元是否出現(xiàn)故障是隨機(jī)且相互獨(dú)立的，系統(tǒng)中每一單元xi出現(xiàn)故障的概率為p，該系統(tǒng)可根據(jù)矩陣B劃分為若干個(gè)集團(tuán)，對其中的任一 集團(tuán)Hi，用ni表示集團(tuán)Hi所含單元的數(shù)目，mi表示集團(tuán)Hi的鄰接集C（Hi）中各集團(tuán)所含單元數(shù)之和，P（Hi=1）表示Hi為正常集團(tuán)的概率，P（C（Hi）=—1）表示Hi的鄰接集所含集團(tuán)均為故障集團(tuán)的概率。在不考慮各集團(tuán)中實(shí)際連接邊數(shù)等前提下，可將“相信大多數(shù)”的診斷原理歸納為以下兩個(gè)診斷準(zhǔn)則：

診斷準(zhǔn)則1 對任意兩個(gè)集團(tuán)Hi、Hj，若mi=mj且ni＞nj，則P（Hi=1）＞P（Hj=1）。

診斷準(zhǔn)則2 對任意兩個(gè)集團(tuán)Hi、Hj，若ni= nj且mi＞mj，則P（Hi=1）＜P（Hj=1）。

證明 先暫不考慮各集團(tuán)鄰接集的存在。根據(jù)集團(tuán)的性質(zhì)1，對任一集團(tuán) Hi，若其為故障集團(tuán)，則集團(tuán)中的每個(gè)單元均為故障單元，又由于系統(tǒng)中各單元是否出現(xiàn)故障是隨機(jī)且相互獨(dú)立的，有Hi為故障集團(tuán)的概率為pmi；又由于“Hi為故障集團(tuán)”與“Hi為正常集團(tuán)”構(gòu)成一對對立事件，其概率和為1，故Hi為正常單元的概率為

現(xiàn)考慮存在鄰接集的情況。根據(jù)集團(tuán)的性質(zhì)2，可知對任一集團(tuán)Hi，Hi與C（Hi）的故障分布只可能有以下三種情況：Hi為正常集團(tuán)且C（Hi）為故障集團(tuán)、Hi為故障集團(tuán)且C（Hi）為正常集團(tuán)、Hi與C（Hi）均 為 故 障 集團(tuán)。此 時(shí)，有，同理，對集團(tuán)Hj，有由于p∈（0，1），當(dāng)mi=mj， ni＞nj時(shí)，故P（Hi= 1）＞P（Hj=1），診斷準(zhǔn)則1得證；當(dāng)ni=nj，mi＞ mj時(shí)，因?yàn)椋蔖（Hi= 1）＜P（Hj=1），診斷準(zhǔn)則2得證。

由于貪婪診斷算法按照貪婪準(zhǔn)則，每做一次貪婪選擇后，結(jié)果不可改變，后一次貪婪選擇在前一次貪婪選擇結(jié)果的基礎(chǔ)上進(jìn)行，因此算法診斷效果的好壞主要與算法的貪婪準(zhǔn)則選取有關(guān)。較好的貪婪準(zhǔn)則使得算法具有較好的爬坡能力，能夠得到與最優(yōu)解十分近似的較優(yōu)解。我們結(jié)合文獻(xiàn)［10］提出的四個(gè)貪婪診斷算法的診斷思想與概率性診斷的診斷準(zhǔn)則1、診斷準(zhǔn)則2，對貪婪準(zhǔn)則進(jìn)行優(yōu)化，以“綜合貪婪因子”作為算法的貪婪準(zhǔn)則，兼顧了各集團(tuán)本身所含單元數(shù)目與鄰接集中單元數(shù)目對貪婪準(zhǔn)則的綜合影響。

首先，給出對每一集團(tuán)Hi的內(nèi)貪婪因子αi、外貪婪因子βi與綜合貪婪因子gre_index［i］的定義：

集團(tuán)Hi的內(nèi)貪婪因子αi=f（ni）；

集團(tuán)Hi的外貪婪因子βi=g（ni，mi）；

集團(tuán)Hi的綜合貪婪因子gre_index［i］=αi* βi；

其中，f（·）為ni正相關(guān)的函數(shù)，g（·）為與ni正相關(guān)、與mi負(fù)相關(guān)的函數(shù)。內(nèi)貪婪因子αi體現(xiàn)的是診斷準(zhǔn)則1對貪婪準(zhǔn)則的影響，外貪婪因子βi體現(xiàn)的是診斷準(zhǔn)則2對貪婪準(zhǔn)則的影響。顯然，綜合貪婪因子越大，則該集團(tuán)為正常集團(tuán)的概率亦越大。

我們對若干組不同的f（·）、g（·）目標(biāo)函數(shù)（包括取線性、指數(shù)、對數(shù)等）進(jìn)行了組合實(shí)驗(yàn)，選取了一個(gè)實(shí)驗(yàn)結(jié)果最好的綜合貪婪因子目標(biāo)函數(shù)：

αi=f（ni）=log ni，βi=g（ni，mi）=ni/mi，綜合貪婪因子：

結(jié)合式（1），顯然對任意ni＞0，mi＞0，我們有：

即gre_index［i］為關(guān)于ni的遞增函數(shù)，亦為關(guān)于mi的遞減函數(shù)。對任意兩集團(tuán)Hi、Hj，若mi=mj且ni＞nj，有g(shù)re_index［i］＞gre_index［j］，即P（Hi=1）＞P（Hj=1），符合診斷準(zhǔn)則1；若ni=nj且mi＞mj，有g(shù)re_index［i］＜gre_index［j］，即P（Hi=1）＜P（Hj=1），符合診斷準(zhǔn)則2。

在劃分出各集團(tuán)之后，分別求出各集團(tuán)的綜合貪婪因子gre_index［i］，接著以綜合貪婪因子作為算法的貪婪準(zhǔn)則，進(jìn)行集團(tuán)的劃分。

4 算法步驟與效率分析

在上一部分的基礎(chǔ)上，我們將 MGFD算法的完整步驟總結(jié)如下：

輸入：測試癥候矩陣A。

輸出：各單元的經(jīng)診斷的故障狀態(tài)。

步驟1 按文獻(xiàn)［12］的方式，通過A—A'運(yùn)算，求得絕對故障基TA。

步驟2 將測試癥候矩陣A中各絕對故障單元所在的行、列刪除，得到矩陣B。

步驟3 根據(jù)矩陣B，求得集團(tuán)，并得到集團(tuán)連接矩陣。

步驟4 按式（1）求出各集團(tuán)的綜合貪婪因子，對輸入的各集團(tuán)按綜合貪婪因子從大到小排序，結(jié)果存儲在隊(duì)列Q中，并初始化各集團(tuán)故障狀態(tài)值，統(tǒng)一置為0。

步驟5 取Q中的隊(duì)列頭部（以下簡稱“隊(duì)頭”）集團(tuán)，若隊(duì)頭集團(tuán)的狀態(tài)值為0，則將該集團(tuán)判斷為正常集團(tuán)，同時(shí)其鄰接集中各集團(tuán)判斷為故障集團(tuán)；否則（隊(duì)頭集團(tuán)已被判斷），重復(fù)步驟5。

步驟6 若隊(duì)列非空，重復(fù)步驟5；否則，繼續(xù)步驟7；

步驟7 將各集團(tuán)的診斷結(jié)果映射為各單元的診斷結(jié)果，同時(shí)與步驟1求得的絕對故障基結(jié)果相結(jié)合，得到所有單元的診斷結(jié)果，并輸出。

顯然，上述七個(gè)步驟順序執(zhí)行，則最復(fù)雜步驟的時(shí)間復(fù)雜度代表了算法的整體時(shí)間復(fù)雜度。其中，步驟1與步驟3的時(shí)間復(fù)雜 度最大，均為O（n2），故算法的整體時(shí)間復(fù)雜度為O（n2）。

5 實(shí)驗(yàn)仿真

文獻(xiàn)［10］對提出的四個(gè)貪婪診斷算法進(jìn)行了實(shí)驗(yàn)仿真，其實(shí)驗(yàn)結(jié)果表明：在相同參數(shù)條件下，貪婪算法1的診斷正確率遠(yuǎn)高于其它三個(gè)貪婪算法，故我們只與貪婪算法1進(jìn)行比較。為便于比較，所選測試圖與文獻(xiàn)［10］一致，均為k-正則圖。實(shí)驗(yàn)參數(shù)完全采用文獻(xiàn)［10］中的設(shè)置：單元總數(shù)均為100，故障單元隨機(jī)產(chǎn)生，故障單元數(shù)從1到60變化，對每一種組合，各做1 000次實(shí)驗(yàn)，取其平均診斷正確率。

首先，我們分別在連通度為2、4、6、8的隨機(jī)生成測試圖中對 MGFD算法的診斷效果進(jìn)行了獨(dú)立實(shí)驗(yàn)，MGFD算法在不同連通度下的診斷正確率如圖1所示。

接著，我們對MGFD算法與文獻(xiàn)［10］提出的貪婪算法1分別在不同連通度的隨機(jī)測試圖中進(jìn)行了比較實(shí)驗(yàn)。圖2a、圖2b、圖3a、圖3b分別展示了兩個(gè)算法在連通度為2、4、6、8時(shí)的診斷正確率。

分析以上的實(shí)驗(yàn)結(jié)果，我們得到如下的結(jié)論：

（1）在同一個(gè)測試圖中，當(dāng)故障單元數(shù)較少時(shí)，MGFD算法與貪婪算法1的診斷正確率均接近100%；當(dāng)故障單元數(shù)約為系統(tǒng)中單元總數(shù)一半左右時(shí)，MGFD算法的診斷正確率明顯高于文獻(xiàn)［10］提出的貪婪算法1。

（2）當(dāng)系統(tǒng)中單元數(shù)目固定時(shí)，隨著系統(tǒng)連通度的上升，更多的故障單元可能被檢測出屬于絕對故障基，或表現(xiàn)出更明顯的故障特征，測試癥候矩陣所含信息價(jià)值更大，因此集團(tuán)的劃分愈精確，MGFD算法的診斷正確率逐漸升高。

（3）在相同的系統(tǒng)中，隨著故障單元數(shù)目的上升，MGFD算法的診斷正確率逐漸降低，但在高連通度的系統(tǒng)中算法診斷正確率降低的幅度明顯小于在低連通度系統(tǒng)中降低的幅度。

實(shí)驗(yàn)表明了當(dāng)系統(tǒng)中故障單元數(shù)目較少時(shí)，MGFD算法的診斷正確率接近100%；當(dāng)故障單元數(shù)目接近系統(tǒng)中總單元數(shù)的一半時(shí)，MGFD算法相比較于貪婪算法1，確實(shí)具有優(yōu)越性。

6 結(jié)束語

本文提出了一個(gè)在PMC模型下基于矩陣運(yùn)算的貪婪診斷算法——MGFD算法。算法適用于高維診斷模型與故障單元數(shù)目接近系統(tǒng)中總單元數(shù)的一半時(shí)的情形。

算法首先剔除絕對故障基，再求集團(tuán)，由此降低了測試癥候矩陣的維數(shù)，進(jìn)而提高了診斷效率，因此尤其適用于高維診斷模型。同時(shí)，相關(guān)研究表明：當(dāng)故障單元數(shù)目接近系統(tǒng)中總單元數(shù)的一半時(shí)，基于圖論的診斷算法與基于方程的診斷算法均不能取得讓人較為滿意的診斷結(jié)果。MGFD算法有機(jī)地結(jié)合了圖論診斷與方程診斷的部分思想，設(shè)計(jì)出基于綜合貪婪因子的貪婪準(zhǔn)則。實(shí)驗(yàn)表明，當(dāng)故障單元數(shù)較少時(shí)，MGFD算法的診斷正確率能夠達(dá)到100%；當(dāng)故障單元數(shù)目接近系統(tǒng)中總單元數(shù)的一半時(shí)，診斷正確率隨著網(wǎng)絡(luò)連通度的提高而逐漸上升，且始終高于現(xiàn)有的貪婪診斷算法。

MGFD算法不僅適用于PMC模型，只要根據(jù)特定模型的特性，對該算法稍作修改，即可應(yīng)用于BMG模型、Chwa&Hakimi模型和Malek模型，因篇幅所限，在此不再贅述。接下來的研究主要有綜合貪婪因子合適目標(biāo)函數(shù)的定量選取，基于高維診斷模型的實(shí)驗(yàn)仿真等。

［1］ Sun Y，Chen M，Liu B，et al.FAR：A fault-avoidance routing method for data center networks with regular topology［C］∥Proc of 2013 ACM/IEEE Symposium on Architectures for Networking and Communications Systems（ANCS），2013：181-189.

［2］ Amagasaki M，Inoue K，Zhao Q，et al.Defect-robust FPGA architectures for intellectual property cores in system LSI［C］∥Proc of 2013 the 23rd International Conference on Field Programmable Logic and Applications（FPL），2013：1-7.

［3］ Yin P Y，Chen Y H，Lu C W，et al.A multi-stage fault-tolerant multiplier with triple module redundancy（TMR）technique［C］∥Proc of 2013 the 4th IEEE International Conference on Intelligent Systems Modelling&Simulation（ISMS），2013：636-641.

［4］ Preparata F P，Metze G，Chien R T.On the connection assignment problem of diagnosable system［J］.IEEE Transactions on Electronic Computer，1967，16（12）：848-854.

［5］ Falcon R，Almeida M，Nayak A.A binary particle swarm optimization approach to fault diagnosis in parallel and distributed systems［C］∥Proc of 2010 IEEE Congress on Evolutionary Computation（CEC），2010：1-8.

［6］ Elhadef M.Solving the PMC-based system-level fault diagnosis problem using hopfield neural networks［C］∥Proc of 2011 IEEE International Conference on Advanced Information Networking and Applications（AINA），2011：216-223.

［7］ Srivastava H O，Gupta S C.Effect of fault patterns on systems level diagnosis of mesh networks［C］∥Proc of 2013 the 10th International Conference on Wireless and Optical Communications Networks（WOCN），2013：1-4.

［8］ He Q Y，Qiu J，Liu G J，et al.System-level BITs fault diagnosis and isolation based on diagnostic tree and Bayesian network［J］.Key Engineering Materials，2014（584）：102-106.

［9］ Zhang Da-fang，Xie Gao-gang，Min Ying-hua.Node grouping in system-level fault diagnosis［J］.Journal of Computer Science&Technology，2001，24（5）：474-479.

［10］ Liu Bing，Zhang Da-fang，Duan Zhi-yong.A probabilistic algorithm of system-level fault diagnosis based on greedy principle［J］.Acta Electronica Sinica，2004，32（8）：1360-1363.（in Chinese）

［11］ Xuan Heng-nong，Zhang Da-fang，Zhang Ming.PMC fault model diagnostic equation［J］.Acta Electronica Sinica，2003，31（5）：694-697.（in Chinese）

［12］ Xuan Heng-nong，Han Zhong-yuan，Zhang Da-fang.PMC model-based fault diagnosis method and its application［J］. Acta Electronica Sinica，2007，35（5）：987-990.（in Chinese）

［13］ Xuan Heng-nong.On the system-level fault diagnosis［J］. Computer Engineering，2001，27（4）：12-13.（in Chinese）

［14］ Wen Xue-zhi，Xuan Heng-nong，Xu Hong.An application of equation diagnosis algorithm in Malek fault models［J］. Computer Engineering，2006，32（1）：46-47.（in Chinese）

附中文參考文獻(xiàn)：

［10］ 劉兵，張大方，段智勇，等.基于貪婪算法的系統(tǒng)級故障的概率診斷［J］.電子學(xué)報(bào)，2004，32（8）：1360-1363.

［11］ 宣恒農(nóng)，張大方，張明.PMC故障模型的方程診斷［J］.電子學(xué)報(bào)，2003，31（5）：694-697.

［12］ 宣恒農(nóng)，韓忠愿，張大方.基于互測PMC模型的故障診斷方法及其應(yīng)用［J］.電子學(xué)報(bào)，2007，35（5）：987-990.

［13］ 宣恒農(nóng).關(guān)于系統(tǒng)級故障診斷［J］.計(jì)算機(jī)工程，2001，27 （4）：12-13.

［14］ 文學(xué)志，宣恒農(nóng)，許宏.方程診斷算法在Malek故障模型中的應(yīng)用［J］.計(jì)算機(jī)工程，2006，32（1）：46-47.

宣恒農(nóng)（1958 ），男，江蘇淮安人，教授，研究方向?yàn)橄到y(tǒng)級故障診斷、未來網(wǎng)絡(luò)和符號計(jì)算。E-mail：13913891389@163. com

XUAN Heng-nong，born in 1958，professor，his research interests include system-level fault diagnosis，future network，and symbol computing.

張潤馳（1990 ），男，江蘇南京人，碩士，研究方向?yàn)橄到y(tǒng)級故障診斷、數(shù)據(jù)挖掘和量化交易。E-mail：zhangrunchi@ aliyun.com

ZHANG Run-chi，born in 1990，MS， his research interests include system-level fault diagnosis，data mining，and quantitative trading.

何濤（1983），男，河南鄭州人，碩士，軟件工程師，研究方向?yàn)橄到y(tǒng)級故障診斷和符號計(jì)算。E-mail：hetao.1983@yahoo. com.cn

He Tao，born in 1983，MS，software engineer，his research interests include system-level fault diagnosis，and symbol computing.

劉凌波（1973 ），女，河南商丘人，碩士，副教授，研究方向?yàn)橄到y(tǒng)級故障診斷和符號計(jì)算。E-mail：djbllb@126.com

LIU Ling-bo，born in 1973，MS，associate professor，her research interests include system-level fault diagnosis，and symbol computing.

A greedy diagnosis algorithm for PMC model

XUAN Heng-nong1，ZHANG Run-chi1，HE Tao2，LIU Ling-bo1
（1.School of Information Engineering，Nanjing University of Finance and Economics，Nanjing 210046；
2.AsiaInfo Linkage Technology Co.，Ltd.Nanjing Branch，Nanjing 210036，China）

We propose a greedy diagnosis algorithm based on the matrix operations called Matrix based Greedy Fault Diagnosis（MGFD）algorithm under the PMC model.With the“absolute fault base“concept put forward by the authors in paper［11］，we remove the absolute fault units to obtain a matrix of reduced dimensions and then get the groups accordingly.On the base of the four existing greedy diagnostic algorithms proposed by paper［10］，we define the concepts of inner greed factors，outer greed factors，comprehensive greed factors of each group，and we also design some new greedy criteria.We demonstrate the correctness of the MGFD algorithm，and design several simulation experiments for the algorithm.Experimental results show that the MGFD algorithm has a higher diagnostic accuracy in comparison with the existing greedy diagnostic algorithm proposed by paper［10］.

system-level fault diagnosis；PMC model；absolute failure base；group；greedy diagnosis algorithm；comprehensive greedy factor；MGFD algorithm

TP301

A

10.3969/j.issn.1007-130X.2015.08.003

1007-130X（2015）08-1430-06

2014-08-11；

2014-10-15

國家自然科學(xué)基金重大研究計(jì)劃資助項(xiàng)目（90718008）；國家自然科學(xué)基金重點(diǎn)項(xiàng)目（61133015）；江蘇省自然科學(xué)基金資

助項(xiàng)目（2004119）

通信地址：210046江蘇省南京市南京財(cái)經(jīng)大學(xué)信息工程學(xué)院

Address：School of Information Engineering，Nanjing University of Finance and Economics，Nanjing 210046，Jiangsu，P.R.China