超立方體網(wǎng)絡(luò)的間歇性故障診斷度研究

馮 浩，梁家榮

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

?

超立方體網(wǎng)絡(luò)的間歇性故障診斷度研究

馮 浩，梁家榮

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

網(wǎng)絡(luò)系統(tǒng)的診斷度是判斷其自我診斷能力的重要度量，網(wǎng)絡(luò)的故障類型包括永久性故障與間歇性故障兩大類。與永久性故障相比，間歇性故障更具隱秘性，更難診斷。超立方體網(wǎng)絡(luò)是一個具有性能優(yōu)越的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)并已得到廣泛的應(yīng)用。針對超立方體網(wǎng)絡(luò)在間歇性故障診斷理論方面的缺失, 在本文中利用圖論方法研究了超立方體網(wǎng)絡(luò)(具有或不具有丟失邊)的ti故障診斷度。應(yīng)用所得到的結(jié)果，可以很容易判斷整個超立方體或者其中一部分網(wǎng)絡(luò)的間歇性故障診斷度，為超立方體網(wǎng)絡(luò)的可靠性分析提供重要的理論依據(jù)。

超立方體;間歇性故障診斷度;多處理機(jī)網(wǎng)絡(luò)系統(tǒng);PMC模型

0 引 言

隨著大型高性能多處理機(jī)網(wǎng)絡(luò)系統(tǒng)高速發(fā)展，網(wǎng)絡(luò)系統(tǒng)的規(guī)模會變得越來越大。在網(wǎng)絡(luò)系統(tǒng)的運(yùn)行過程中，處理器(結(jié)點(diǎn))出現(xiàn)故障是難以避免的，故障的存在可能會使信息的通信遲緩甚至?xí)?dǎo)致系統(tǒng)癱瘓。因此，對系統(tǒng)結(jié)點(diǎn)的測試與故障診斷是具有重要意義的。目前故障的測試方法主要有系統(tǒng)級診斷和非系統(tǒng)級診斷，非系統(tǒng)級診斷主要采用的是硬件測試診斷，其優(yōu)點(diǎn)是更換或修復(fù)方便，缺點(diǎn)是效率低，測試資源需求大且容易出錯，尤其是對大規(guī)模的網(wǎng)絡(luò)系統(tǒng)。而系統(tǒng)級診斷借助網(wǎng)絡(luò)自身的處理器進(jìn)行相互診斷，不影響系統(tǒng)的運(yùn)行，效率高且不易出錯，已為人們所采用。在系統(tǒng)級診斷中，1967年P(guān)reparata, Metze以及Chien (PMC) 等所提出的PMC模型是最早的系統(tǒng)級別故障診斷模型。PMC模型認(rèn)為：在一個網(wǎng)絡(luò)系統(tǒng)中，如果節(jié)點(diǎn)u與節(jié)點(diǎn)v相連，那么節(jié)點(diǎn)u就能夠測試節(jié)點(diǎn)v是故障或無故障。測試結(jié)果可用0或1來表示，測試結(jié)果為0表示節(jié)點(diǎn)u測試節(jié)點(diǎn)v為無故障，結(jié)果1則節(jié)點(diǎn)u測試節(jié)點(diǎn)v為故障。如果測試節(jié)點(diǎn)u是正常節(jié)點(diǎn)，那么測試結(jié)果是可靠的，如果測試節(jié)點(diǎn)u是故障節(jié)點(diǎn)，那么測試結(jié)果是不可靠的。在永久性故障情形下，基于PMC模型的網(wǎng)絡(luò)系統(tǒng)故障診斷理論研究已取得了大量的成果[1-4]。值得一提的是2005年Lai等在充分分析t可診斷系統(tǒng)的基礎(chǔ)上，提出了強(qiáng)t故障可診斷系統(tǒng)的理論，該理論認(rèn)為t故障可診斷系統(tǒng)必定是t可診斷的，并且?guī)缀跻彩?t+1)-可診斷系統(tǒng)，只有當(dāng)某一個節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)全部故障的情況屬例外。Lai等在文獻(xiàn)[5]中還證明了一個t維度的MCN網(wǎng)絡(luò)也是強(qiáng)t+1可診斷的，這為網(wǎng)絡(luò)的故障診斷度理論提供了重要的內(nèi)容。

在過去的幾十年中，模擬多處理機(jī)系統(tǒng)的網(wǎng)絡(luò)拓?fù)淠Ｐ鸵延胁簧伲?guī)則互連網(wǎng)絡(luò)是極富代表性的一種[6-11]。在規(guī)則互連網(wǎng)絡(luò)中，超立方體網(wǎng)絡(luò)是應(yīng)用最為廣泛的一種互連網(wǎng)絡(luò)結(jié)構(gòu)[12]，對超立方體網(wǎng)絡(luò)各方面的研究工作已充分展開[13-15]。正如上面所提，故障診斷對超立方體網(wǎng)絡(luò)的可靠性分析有著重要的意義，在永久性故障情形，超立方體的故障診斷理論已取得了不少成果。然而在間歇性故障情形，超立方體的故障診斷研究乏善可陳。

本文通過分析超立方體網(wǎng)絡(luò)的結(jié)構(gòu)入手，首先研究不存在故障邊的情況下的超立方體網(wǎng)絡(luò)的間歇性故障診斷問題，并借此進(jìn)一步研究存在故障邊(或者缺失邊)情況下，超立方體網(wǎng)絡(luò)的間歇性故障診斷度。

1 預(yù)備知識

文中使用G=(V,E)來代表一個無向圖，其中V(G)、E(G)分別代表圖G中的點(diǎn)集和邊集。任一個多處理機(jī)系統(tǒng)都可以用一個圖來表示，其中圖G中的結(jié)點(diǎn)表示處理機(jī)，而邊(vi,vj)表示邊vi與vj聯(lián)通之間的通信。本文中，有關(guān)圖的相關(guān)概念與定義與文獻(xiàn)[16]一致。

在一個圖G中，一個結(jié)點(diǎn)v的度數(shù)指的是與結(jié)點(diǎn)v關(guān)聯(lián)的邊的條數(shù)，記為deg(v)。如果圖G中的最大結(jié)點(diǎn)度數(shù)與最小結(jié)點(diǎn)度數(shù)相等，則稱圖G為一個正則圖，如果這個度數(shù)是k，則稱圖G是一個k-正則圖。G-S表示圖G刪掉S中的結(jié)點(diǎn)后的子圖。設(shè)M是一個圖G中的任意集，則使用NG(M)表示集合M的所有鄰居結(jié)點(diǎn)組成的集合，即NG(M)={v|v∈V∧?u∈M((u,v)∈E)}。一個故障集表示圖G中所有故障結(jié)點(diǎn)組成的集合。識別所有故障結(jié)點(diǎn)的過程被稱作系統(tǒng)診斷。在永久性故障情形下，能被識別出來的最大的故障集的基數(shù)稱為系統(tǒng)的永久性故障診斷度，記為tp(G)。

定義1 一個系統(tǒng)稱為n-tp-可診斷的如果所有的故障結(jié)點(diǎn)都是永久性故障，且只要系統(tǒng)中的故障結(jié)點(diǎn)的數(shù)量不超過n，所有的故障結(jié)點(diǎn)都能被識別[17]。

設(shè)F1,F2?V為兩個不同的子集，記F1ΔF2=(F1-F2)∪(F2-F1)。Dahbura以及Masson在文獻(xiàn)[18]中提出了判斷一個系統(tǒng)是否是tp-可診斷的充要條件。

對于間歇性故障情形，故障結(jié)點(diǎn)的狀態(tài)有時是正常的，有時是故障的，要識別這樣的結(jié)點(diǎn)可能要測試多次。稱一個診斷策略是不完全的如果一些間歇性故障結(jié)點(diǎn)被識別為正常結(jié)點(diǎn)的，而稱一個診斷策略是不正確的如果它把一些正常的結(jié)點(diǎn)識別為故障的。為此，應(yīng)避免不正確的診斷，因?yàn)橛袝r不正確的診斷會導(dǎo)致系統(tǒng)級別的崩潰。

定義2 一個系統(tǒng)G=(V,E)稱為m-ti-可診斷的如果對于任意的診斷:①任一個正常的結(jié)點(diǎn)都不會被診斷為故障的；②這個診斷只能是不完全的，不會是不正確的，只要間歇性故障結(jié)點(diǎn)的數(shù)量不超過m。

相似于永久性故障情形，Mallela以及 Masson提出了一個檢驗(yàn)一個系統(tǒng)是否是ti-故障可診斷的充分必要條件，并給出了一個系統(tǒng)中tp和ti的診斷度的數(shù)量關(guān)系。

引理3 如果一個系統(tǒng)是n-tp-可診斷的，同時也是m-ti-可診斷的，那么如下不等式成立[19]：

一個n維超立方體網(wǎng)絡(luò)G=(V,E)可表示為Qn，V由2n結(jié)點(diǎn)組成，每個結(jié)點(diǎn)地址可用一個n位的二進(jìn)制數(shù)來表示，(vi,vj)∈E當(dāng)且僅當(dāng)vi與vj之間有且只有一個不同的比特位。一個n+1維超立方體可以看成是由兩個n維超立方體所構(gòu)成，用oan…a2a1(obn…b2b1)分別表示第一(第二)個n維超立方體網(wǎng)絡(luò)的結(jié)點(diǎn)。圖1展示出了Q3以及Q4(3維超立方體及4維超立方體)，每一條無向邊表示其兩個端結(jié)點(diǎn)可以互相測試。每一個結(jié)點(diǎn)都都關(guān)聯(lián)著n條邊。

(a)Q3

(b)Q4

圖1 一個3維超立方體Q3以及一個4維超立方體Q4

Fig.1 A 3-dimension hypercube and a 4-dimension hypercube

2 超立方體網(wǎng)絡(luò)的間歇性故障診斷度

在這一部分，主要討論超立方體Qn的間歇性故障診斷度，也就是ti值。由引理2可知，超立方體的永久性故障診斷度總是等于它的維度n，也等于每個結(jié)點(diǎn)v的度數(shù)deg(v)。從引理3可知，在一個相互測試的無向圖中，ti值永遠(yuǎn)不會超過tp值。這也意味著，在超立方體中，間歇性故障診斷度最多只能與永久性故障診斷度相等。下面，將進(jìn)一步討論Qn中的ti與tp的關(guān)系。

引理4 對于一個超立方體Qn(n≥3)，ti

進(jìn)一步對ti值進(jìn)行研究以觀察它最大能達(dá)到多少，得出下面的結(jié)論。

定理1 在超立方體Qn(n≥3)中，間歇性故障診斷度ti=tp-1。

為了證明定理1，需要用到如下引理。

引理5證畢。

3 具有丟失邊的超立方體的間歇性故障診斷度

通過上面的討論可以獲得：在PMC模型下超立方體的間歇性故障診斷度為n-1(永久性故障診斷度為n)。應(yīng)該說明的，這個診斷度是在n維超立方體所有邊都能有效的進(jìn)行通信情況下才成立的，即間歇性故障診斷度為n-1的前提為不會存在丟失邊。如果n維超立方體存在邊故障或者說有些邊丟失，那么其故障診斷度如何？這是值得期待研究的問題。在文獻(xiàn)[7]中能得到以下關(guān)于n維超立方體永久性故障診斷度的結(jié)論。

引理6 給出一個n維具有丟失邊的超立方體網(wǎng)絡(luò)，表示為G=(V,E)。如果min{deg(v)|v∈V}=r且r≥3，則此系統(tǒng)為r-tp-可診斷的[1]。

引理7 一個n-維超立方體Qn不存在長度為3的環(huán)(無3環(huán))并且任兩點(diǎn)最多有兩個共同鄰居結(jié)點(diǎn)[1]。

接著檢驗(yàn)在具有丟失邊的超立方體中ti值是否依然等于tp-1。

定理2 在具有丟失邊的超立方體中，如果min{deg(v)|v∈V}=r并且r≥2,那么此系統(tǒng)的間歇性故障診斷度ti=r-1。

在證明定理2之前，需要如下引理。

證明 通過劃分為以下幾種情況來證明這個引理：

情形1M中任意兩個結(jié)點(diǎn)均不相鄰。

情形2 在M中存在著一些相互連接的結(jié)點(diǎn)對。

讓v1與v2表示其中一對互相連接的結(jié)點(diǎn)。因?yàn)槊總€結(jié)點(diǎn)的度至少為r，假設(shè)：

deg(v1)=r+m1,

deg(v2)=r+m2(0≤m1,m2≤n-r),

因?yàn)関1與v2相連并且在超立方體中不存在長度為3的環(huán)(引理7)。因此這r+m1個連接著v1的結(jié)點(diǎn)與連接著v2個結(jié)點(diǎn)不會有交集[如圖2(b)]。于是有：

并且同樣的,

顯然得出:

NG(v1,v2)=r+m1+r+m2-2=2r+m1+m2-2,

(a) 情形1

(b) 情形2

圖2 引理8證明圖例

Fig.2 Case of lemma 8

圖3 一個四維正則圖Fig.3 A 4-regular graph

4 結(jié) 語

超立方體的容錯能力一直是一個關(guān)鍵性研究熱點(diǎn)，至今卻仍沒有一個能快速簡單判斷超立方體間歇性故障診斷度的方法。應(yīng)用本文的研究結(jié)果，所有n≥3的超立方體ti故障診斷度都能一目了然即ti=n-1。并且，本文還進(jìn)一步研究了具有丟失邊的超立方體的ti值，假若具有丟失邊的不完整的超立方體滿足min{deg(v)|v∈V}=r并且r≥2,那么此系統(tǒng)的間歇性故障診斷度為ti=r-1。應(yīng)用本文的結(jié)果可以對某些不完全超立方體進(jìn)行間歇故障診斷度判斷，或者對某些連接失效的超立方體和只想進(jìn)行部分診斷的超立方體進(jìn)行ti值的判斷研究。

[1] NG D.The diagnosability of hypercubes with arbitraily missing links[J]. Journal of Systems Architecture, 2000, 46(3): 519-527.

[2] 郭晨,梁家榮,葛志輝,等.基于互測PMC模型的條件診斷算法[J]. 電子學(xué)報, 2015, 43(2): 255-261.

[3] NAI W C,SUN Y H.Structural properties and conditional diagnosability of star graphs by using the PMC model[J]. IEEE Transaction on Parallel and Distributed systems, 2014, 25(11): 3002-3011.

[4] 黃瑩,梁家榮,葉良程.交換超立方體網(wǎng)絡(luò)的t1/k-診斷度研究[J]. 小型微型計算機(jī)系統(tǒng), 2015, 36(9): 2054-2057.

[5] LAI P L, TAN J JM, CHANG C P.Conditional diagnosability measures for large multiprocessor systems[J]. IEEE Transaction on Computer, 2005, 54(2): 165-175.

[6] 謝春萍,梁家榮.星型網(wǎng)絡(luò)的幾種故障診斷度研究[J]. 廣西大學(xué)學(xué)報(自然科學(xué)版), 2015,40(3):699-704.

[7] EFE K.The crossed cube architecture for parallel computation[J]. IEEE Transaction on Parallel and Distributed Systems, 1992, 3(5) : 513-524.

[8] PAUL C, SHAWN M L.The M?biuscubes[J]. IEEE Transaction on Computer, 1995, 44(5): 647-659.

[9] ABDOL H E, LIONEL M N, BRUCE E S.The twisted n-cube with application to multiprocessing[J]. IEEE Transaction on Computer,1991, 40(1): 88-93.

[10]LI J, TAN X.The Diagnosability of Augmented Cubes under PMC Model[J]. IEEE Transaction on Parallel and Distributed Systems, 2010, 10(2): 301-304.

[11]LIANG J R, HUANG Y, YE L C.Diagnosabilities of exchanged hypercube networks under the pessimistic one-step diagnosis strategy[J]. Journal of Systems Engineering and Electronics, 2015, 30(2): 415-420.

[12]JOHN P H.Architecture of a hypercube supercomputer[J]. IEEE Transaction on Computer, 1986, 10(2): 653-660.

[13]CHANG H T.A Quick pessimistic diagnosis algorithm for hypercube-like multiprocessor systems under the PMC model[J]. IEEE Transaction on Computer, 2013, 62(2): 259-267.

[14]WANG D, WANG Z.Minimum assignment of test links for hypercubes with lower fault bounds[J]. IEEE Transaction on Parallel and Distributed Systems,1997,40(2):185-193.

[15]HSU G H, CHIANG C F, SHIH L M, et al.Conditional diagnosability of hypercubes under the comparison diagnosis model[J]. IEEE Transaction on Computer, 2009, 55(2): 140-146.

[16]DOUGLAS B W, Introduction to Graph Theory[M]. USA: Prentice Hall, 2001.

[17]FRANC P P, GERNOT M, ROBERT T C.On the connection assignment problem of diagnosable system[J]. IEEE Transaction on Electronic Computers, 1967, 16(6): 848-854.

[18]ANTON T D, GERALD M.An O(N2.5) Fault identification algorithm for diagnosable systems[J]. IEEETransaction on Computer, 1984, 33(6): 486-492.

[19]SIVANARAYANA M, GERALD M M.Diagnosable systems for intermittent faults[J]. IEEE Transaction on Computer,1978, 27(3): 360-366.

(責(zé)任編輯 梁碧芬)

Research on intermittent fault diagnosability of hypercube networks

FENG Hao, LIANG Jia-rong

(School of Computer, Electronics Information, Guangxi University, Nanning 530004, China)

Diagnosability of networks is one key measure to judge its self-diagnose capability. Fault type of networks includes the permanent fault and the intermittent fault. Compared with the permanent fault, the intermittent fault is easier to be hided and harder to be diagnosed. The hypercube network is a kind of network topology with superior performances and has been used widely. In view of the absence of intermittent fault diagnosis theory in hypercube network, theti-fault diagnosability of hypercube (with or without missing links) is studied, by employing graph theory. By using the presented method, the intermittent fault diagnosability of one hypercube or just part of it can be determined, which provides an important theoretical basis for reliability analysis of hypercube networks.

hypercube; intermittent fault diagnosis; multi-processor network; PMC model

2016-06-11；

2016-07-28

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

梁家榮(1966—)，廣西玉林人，廣西大學(xué)教授，博士生導(dǎo)師；E-mail:13977106752@163.com。

馮浩，梁家榮.超立方體網(wǎng)絡(luò)的間歇性故障診斷度研究[J].廣西大學(xué)學(xué)報(自然科學(xué)版)，2016，41(5)：1560-1566.

10.13624/j.cnki.issn.1001-7445.2016.1560

TP393

A

1001-7445(2016)05-1560-07