交換超立方網(wǎng)絡(luò)的(t,k)故障診斷度研究

熊茜，梁家榮，馬強(qiáng)

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

?

交換超立方網(wǎng)絡(luò)的(t,k)故障診斷度研究

熊茜，梁家榮，馬強(qiáng)

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

摘要：故障診斷是網(wǎng)絡(luò)系統(tǒng)修復(fù)的一個(gè)重要環(huán)節(jié)，PMC診斷模型是一種簡(jiǎn)單、易于理解的故障診斷模型。通過(guò)對(duì)以交換超立方網(wǎng)EH（s,p）（1≤s≤p）為拓?fù)淠Ｐ偷亩嗵幚砥飨到y(tǒng)進(jìn)行結(jié)構(gòu)分析，給出了該網(wǎng)絡(luò)系統(tǒng)的一般化的故障診斷方法——(t,k)診斷方法，證明了在PMC模型下交換超立方網(wǎng)絡(luò)EH（s,p）（1≤s≤p）是可診斷的，且是條件可診斷的。結(jié)果表明，交換超立方網(wǎng)的(t,k)診斷度大于其傳統(tǒng)診斷度s+1，條件(t,k)診斷度大于其傳統(tǒng)條件診斷度4s-3。這些結(jié)果為交換超立方網(wǎng)絡(luò)的故障診斷提供了重要的理論依據(jù)。

關(guān)鍵詞：交換超立方網(wǎng)；(t,k)診斷度；條件(t,k)診斷度；PMC模型

1 引言

隨著并行計(jì)算系統(tǒng)規(guī)模的不斷增大，系統(tǒng)中將不可避免地出現(xiàn)故障節(jié)點(diǎn)和故障鏈路，如何有效地識(shí)別和定位這些故障節(jié)點(diǎn)和故障鏈路以保證系統(tǒng)的可靠性已成為系統(tǒng)設(shè)計(jì)、維護(hù)工作中的重要部分。在系統(tǒng)中辨別處理器正確與否的過(guò)程為故障診斷。當(dāng)一個(gè)故障處理器被識(shí)別后，通常用一個(gè)正確處理器代替它，以維持系統(tǒng)的可靠性。在多處理器系統(tǒng)中，通過(guò)分析有效處理器間的測(cè)試結(jié)果而識(shí)別出故障處理器的過(guò)程，稱為系統(tǒng)級(jí)診斷，這種診斷已被廣泛研究[1～7]。系統(tǒng)級(jí)故障診斷的基本思想是：系統(tǒng)中的處理器之間相互測(cè)試，通過(guò)對(duì)測(cè)試結(jié)果進(jìn)行邏輯分析確定系統(tǒng)中的故障處理器。在系統(tǒng)中能識(shí)別出的最大故障節(jié)點(diǎn)個(gè)數(shù)，稱為系統(tǒng)的故障診斷度。在系統(tǒng)級(jí)故障診斷中PMC故障診斷模型是最常見(jiàn)的一種診斷模型。PMC模型是由Preparata等[8]在1967年提出的，PMC模型診斷的基本方法：對(duì)于網(wǎng)絡(luò)圖G(V,E)中任意一條邊(u,v)∈E，表示節(jié)點(diǎn)u可以測(cè)試節(jié)點(diǎn)v。當(dāng)用節(jié)點(diǎn)u測(cè)試節(jié)點(diǎn)v時(shí)，節(jié)點(diǎn)u稱為測(cè)試者，節(jié)點(diǎn)v稱為被測(cè)試者，節(jié)點(diǎn)u發(fā)給節(jié)點(diǎn)v一個(gè)測(cè)試任務(wù)，節(jié)點(diǎn)v回復(fù)一個(gè)響應(yīng)消息。如果響應(yīng)正確，則記錄節(jié)點(diǎn)u測(cè)試節(jié)點(diǎn)v的結(jié)果為0，記為σ(u,v)=0；若響應(yīng)故障，則記錄節(jié)點(diǎn)u測(cè)試節(jié)點(diǎn)v的結(jié)果為1，記為σ(u,v)=1。一次測(cè)試的所有結(jié)果的集合稱為網(wǎng)絡(luò)圖G(V,E)的一個(gè)癥狀，用σ來(lái)表示，它是網(wǎng)絡(luò)圖G(V,E)的邊集到｛0,1｝的映射。在PMC模型中，如果一個(gè)無(wú)故障的節(jié)點(diǎn)作為測(cè)試者，則它所產(chǎn)生的測(cè)試結(jié)果是可靠的；如果作為測(cè)試者的節(jié)點(diǎn)本身發(fā)生了故障，那么它所產(chǎn)生的測(cè)試結(jié)果是不可靠的。

文獻(xiàn)[8]介紹了多處理器網(wǎng)絡(luò)系統(tǒng)的2種故障診斷方法：一步診斷和連續(xù)診斷。一步診斷也被稱為無(wú)修復(fù)診斷，關(guān)于一步診斷的研究已取得了不少成果，具體可參考文獻(xiàn)[9～15]。連續(xù)診斷則被稱為可修復(fù)診斷，用迭代的方式識(shí)別故障節(jié)點(diǎn)子集，其中，在每次迭代中至少識(shí)別出一個(gè)故障節(jié)點(diǎn)。并且，在一次迭代結(jié)束后和下一次迭代開(kāi)始前，對(duì)所有識(shí)別出的故障節(jié)點(diǎn)需要修復(fù)或取代，這個(gè)進(jìn)程一直重復(fù)直到所有的故障節(jié)點(diǎn)都被修復(fù)或取代，可以說(shuō)連續(xù)診斷是一種“分散難度的診斷”。從具體的故障檢測(cè)而言，一步診斷盡管能一次性診斷出所有的故障節(jié)點(diǎn)，然而它對(duì)網(wǎng)絡(luò)連接難度或者說(shuō)網(wǎng)絡(luò)的成本開(kāi)銷要求也極高，更多的人們傾向于關(guān)注連續(xù)診斷。在連續(xù)故障診斷研究中，有一種稱之為(t,k)診斷的連續(xù)診斷（其中，t≥k，系統(tǒng)中的故障節(jié)點(diǎn)個(gè)數(shù)不超過(guò)t），它是由Arika和Shibata[16]提出的一種連續(xù)診斷的一般化診斷。(t,k)診斷認(rèn)為，通過(guò)迭代的方式對(duì)系統(tǒng)中所有故障節(jié)點(diǎn)進(jìn)行識(shí)別并修復(fù)，在每一次迭代中，(t,k)診斷至少能識(shí)別出k個(gè)故障節(jié)點(diǎn)（或剩余故障節(jié)點(diǎn)數(shù)小于k時(shí)，所有故障節(jié)點(diǎn)都將被識(shí)別出），相比普通的連續(xù)診斷每次至少識(shí)別出一個(gè)故障節(jié)點(diǎn)而言，(t,k)診斷在時(shí)間復(fù)雜性上有所改善。關(guān)于(t,k)診斷已有一些研究成果，如Chen和Hsieh[17]計(jì)算并證明了組件網(wǎng)絡(luò)基于比較模型下的(t,k)診斷度。Chang[18]證明了n-維正則網(wǎng)G是(t,k)可診斷的，當(dāng)，其中，N為G中節(jié)點(diǎn)數(shù)，B表示最大故障集合體中的節(jié)點(diǎn)數(shù)。Chang和Chen證明了d-維網(wǎng)格和圓環(huán)面分別是可診斷和可診斷的，其中，N為系統(tǒng)中的節(jié)點(diǎn)總數(shù)[19]。此外，在傳統(tǒng)的故障診斷研究中，所考慮的故障節(jié)點(diǎn)是隨機(jī)分布的，本文稱此種故障模式為隨機(jī)故障模式；然而，有時(shí)如果不對(duì)故障節(jié)點(diǎn)的分布進(jìn)行限制，會(huì)給診斷增加極大的難度，在許多情況下，對(duì)故障節(jié)點(diǎn)分布做適當(dāng)?shù)南拗?，有利于故障?jié)點(diǎn)的識(shí)別，同時(shí)不會(huì)對(duì)網(wǎng)絡(luò)的故障診斷產(chǎn)生太大影響，事實(shí)上像“網(wǎng)絡(luò)中任一節(jié)點(diǎn)的鄰居節(jié)點(diǎn)不全是故障節(jié)點(diǎn)的限制”就具有比較客觀的意義，例如，對(duì)于一個(gè)n維超立方體網(wǎng)絡(luò)，Qn包含個(gè)含有n個(gè)元素的子集，在這些子集中只有2n個(gè)子集包含某些節(jié)點(diǎn)的所有鄰居，當(dāng)n足夠大時(shí)，比率是很小的，即Qn的基數(shù)為n的故障集包含任意一個(gè)節(jié)點(diǎn)所有的鄰居節(jié)點(diǎn)的概率是很小的。為此，2005年Lai等在文獻(xiàn)[20]中提出一種新的故障診斷方法——條件故障診斷。條件診斷假設(shè)系統(tǒng)中任何一個(gè)節(jié)點(diǎn)的所有相鄰節(jié)點(diǎn)不能同時(shí)發(fā)生故障，即一個(gè)系統(tǒng)中的任何一個(gè)節(jié)點(diǎn)的所有相鄰節(jié)點(diǎn)至少有一個(gè)是正確的。關(guān)于條件故障診斷的研究已取得了一些成果[4,5,9,11,14,21]。

交換超立方網(wǎng)絡(luò)作為超立方體網(wǎng)絡(luò)的一種變型網(wǎng)絡(luò)[22]，有效降低了網(wǎng)絡(luò)規(guī)模增大時(shí)所需要的拓?fù)溥B接的開(kāi)銷，是一種性能優(yōu)越的網(wǎng)絡(luò)。隨著交換超立方網(wǎng)絡(luò)EH(s,p)網(wǎng)絡(luò)規(guī)模和維數(shù)的增大，加之網(wǎng)絡(luò)的高速運(yùn)行，出現(xiàn)故障節(jié)點(diǎn)是不可避免的。如何識(shí)別交換超立方網(wǎng)絡(luò)EH(s,p)的故障節(jié)點(diǎn)，進(jìn)而進(jìn)行修復(fù)，以使該網(wǎng)絡(luò)能正常通信，是交換超立方網(wǎng)絡(luò)EH(s,p)面臨的重要問(wèn)題。在交換超立方網(wǎng)絡(luò)EH(s,p)故障診斷理論研究中，診斷度無(wú)疑是一個(gè)研究重點(diǎn)，因?yàn)樵\斷度體現(xiàn)了該網(wǎng)絡(luò)最多能識(shí)別的故障節(jié)點(diǎn)數(shù)的上界，它是故障診斷算法設(shè)計(jì)與選擇的重要基礎(chǔ)。目前，關(guān)于交換超立方網(wǎng)絡(luò)的診斷度的研究已取得了一些成果，如文獻(xiàn)[23]研究了交換超立方網(wǎng)絡(luò)悲觀一步診斷策略下的診斷度問(wèn)題，文獻(xiàn)[24]研究了交換超立方體網(wǎng)絡(luò)的超連通度。然而在這些診斷度的算法中，由于每次迭代只能給出一個(gè)故障節(jié)點(diǎn)進(jìn)行修復(fù)，因而其時(shí)間復(fù)雜性可達(dá)O(2s+p+1)。顯然，當(dāng)交換超立方網(wǎng)絡(luò)EH（s,p）（1≤s≤p）規(guī)模較大時(shí)，會(huì)給交換超立方網(wǎng)絡(luò)的故障診斷帶來(lái)極大的時(shí)間開(kāi)銷。為此本文考慮更為廣泛意義的連續(xù)診斷以及更為實(shí)際的條件診斷問(wèn)題，本文提出2種適用于交換超立方網(wǎng)的基于PMC模型下的診斷方法：(t,k)診斷和條件(t,k)診斷，這2種方法得到的診斷度遠(yuǎn)遠(yuǎn)大于其傳統(tǒng)診斷度，且在時(shí)間復(fù)雜性上是傳統(tǒng)診斷的。此外，開(kāi)展交換超立方網(wǎng)絡(luò)基于PMC模型下的(t,k)診斷度和條件(t,k)診斷度的研究，對(duì)豐富和發(fā)展交換超立方網(wǎng)絡(luò)的故障診斷理論具有重要的學(xué)術(shù)意義，為交換超立方網(wǎng)絡(luò)運(yùn)行的可靠性研究提供重要的理論支撐。

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

在多處理器系統(tǒng)的研究中，一個(gè)系統(tǒng)的基礎(chǔ)拓?fù)浣Y(jié)構(gòu)通常用圖G(V,E)表示，其中，任意節(jié)點(diǎn)v∈V表示一個(gè)處理器，任意邊（u,v）∈E表示節(jié)點(diǎn)u和v之間的一條通信連接。節(jié)點(diǎn)u的鄰居表示的是和u互連的任意節(jié)點(diǎn)，并用N(u)表示節(jié)點(diǎn)u的所有鄰居節(jié)點(diǎn)集合，即N(u)=｛v|（u,v）∈E｝。對(duì)于一個(gè)子集U?V，N（U）表示的是U中所有節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合，即有N（U）=∪u∈UN（u）-U，且其在點(diǎn)集W?V中的鄰居節(jié)點(diǎn)集合表示為N（U,W）=｛v|（u,v）∈E,u∈U且v∈W｝。其中，節(jié)點(diǎn)u的度表示和u相連邊的數(shù)目。如果G是一個(gè)無(wú)向圖且圖中任意2個(gè)節(jié)點(diǎn)都是連通的，那么稱G為連通圖；如果G是一個(gè)有向圖且滿足上述條件，則G是一個(gè)強(qiáng)連通圖。如果G是非連通的，那么在G中的最大連通子圖即為G的連通分支，如果某個(gè)連通分支僅含一個(gè)節(jié)點(diǎn)，稱此連通分支為平凡連通分支；否則為非平凡連通分支。從G中移除一個(gè)點(diǎn)集S，如果移除節(jié)點(diǎn)后的G是非連通的或僅剩一個(gè)節(jié)點(diǎn)，那么稱S可達(dá)到的最小基數(shù)為圖G的連通度，表示為k(G)。系統(tǒng)S的故障節(jié)點(diǎn)集即為所有故障節(jié)點(diǎn)的集合，它可以是V的任意子集。在PMC模型下的故障診斷的意義如引言所述。

通過(guò)引言中對(duì)(t,k)診斷的描述，本文給出以下定義。

定義1給定系統(tǒng)S的故障節(jié)點(diǎn)集為F，σ為S在F下的任一癥狀，如果：1）當(dāng)時(shí)，所有故障節(jié)點(diǎn)可被識(shí)別；2）當(dāng)時(shí)，至少k個(gè)故障節(jié)點(diǎn)可被識(shí)別，那么S就是(t,k)可診斷的。

由定義不難得知，一步診斷和連續(xù)診斷是(t,k)診斷的2個(gè)特例。當(dāng)t=k時(shí)，(t,k)診斷即為一步診斷；當(dāng)k=1時(shí)，(t,k)診斷為連續(xù)診斷。

如果系統(tǒng)S的子集A滿足下面2個(gè)條件，則可稱A為癥狀σ的可允許故障集。

直觀上，A是關(guān)于σ的一個(gè)可允許故障集，當(dāng)且僅當(dāng)A中的節(jié)點(diǎn)都是故障的，且不屬于A的節(jié)點(diǎn)都是正確的，并在此假設(shè)下A能產(chǎn)生一個(gè)和σ相同的癥狀。顯然，S的故障節(jié)點(diǎn)集是關(guān)于σ的一個(gè)可允許故障集。那么，所有基數(shù)不超過(guò)t的關(guān)于癥狀σ的可允許故障集的交集就是S的故障節(jié)點(diǎn)集的一個(gè)子集，即有下列引理。

引理1[16]對(duì)于故障節(jié)點(diǎn)數(shù)不超過(guò)t的系統(tǒng)S，給定任意癥狀σ，

Ψσ,t={F| F 是關(guān)于癥狀σ的一個(gè)可允許故障集,且≤t} ，那么S是(t,k)可診斷的當(dāng)且僅當(dāng)

下面的內(nèi)容描述了交換超立方網(wǎng)的定義和相關(guān)性質(zhì)。

定義2[22]交換超立方網(wǎng)是一個(gè)無(wú)向圖EH(s,p)=(V,E)(s≥1,p≥1)。其中，V是節(jié)點(diǎn)集。

V={as-1…a0bp-1…b0c| ai,bj,c∈｛0,1｝,其中,i∈［0,s）,j∈［0,p）}；E表示邊集。

其中，⊕為異或符號(hào)；v［ x: y］表示字符串v從x位到y(tǒng)位的部分字符串；H（x,y）表示節(jié)點(diǎn)x到節(jié)點(diǎn)y的海明距離，并且（x,y）∈V×V。圖1給出交換超立方網(wǎng)的EH(1,1)和EH(1,2)。

引理2[22]EH(s,p)可以分解成2個(gè)EH(s-1,p)或EH(s,p-1)。

圖1 交換超立方網(wǎng)EH(1,1)和EH(1,2)

3 交換超立方網(wǎng)的(t,k)診斷度

本文將使用一個(gè)有向圖G（V,E）以表示交換超立方網(wǎng)EH(s,p)（1≤s≤p）。假設(shè)（u1,u2,…,um）是G中從節(jié)點(diǎn)u1到節(jié)點(diǎn)um的有向路徑，且σ是G對(duì)應(yīng)的一種癥狀。當(dāng)σ（ui,ui+1）=0，其中，1≤i≤m-1，那么u1是故障的或u1,u2,…,um都是正確的。使用G+表示G的一個(gè)生成子圖，其中，所有邊（ui,uj）都滿足條件，即G+=（V+,E+），其中，V+=V且E+=｛（ui,uj）|（ui,uj）∈E且σ（ui,uj）=0｝。并且使用C表示G+中所有強(qiáng)連通分支的集合。

由于同一強(qiáng)連通分支中的2個(gè)不同節(jié)點(diǎn)u和v之間，總是存在著一條從u到v的有向路徑，所以在C中的每個(gè)連通分支的所有節(jié)點(diǎn)都是正確或都是故障的。如果一個(gè)連通分支中的所有節(jié)點(diǎn)都是正確的，則稱此連通分支為正確的連通分支；否則稱其為故障的連通分支。如果，那么V中所有節(jié)點(diǎn)都是正確或都是故障的，這與實(shí)際情況不符。所以在此可以得知。將C中任一連通分支當(dāng)成一個(gè)點(diǎn)，對(duì)于連通分支X和Y，當(dāng)節(jié)點(diǎn)x∈X、節(jié)點(diǎn)y∈Y且存在（x,y）∈E時(shí)，那么表明X和Y可通過(guò)邊（x,y）連接。本文構(gòu)造圖，其中，且如果,N（X）則表示X在中的鄰居連通分支的集合，即N（X,W）則表示X在中的鄰居連通分支的集合，即

通過(guò)上述內(nèi)容，本文引申出下列幾個(gè)引理，用于判斷連通分支是否正確。

證明由于Y∈N（X），即存在（x,y）∈E,其中，x∈X且y∈Y 。假設(shè)X和Y都是正確的，那么X和Y屬于同一個(gè)連通分支，這與假設(shè)不符，所以Y是一個(gè)故障的連通分支。

證明如果X是故障的，那么G中故障節(jié)點(diǎn)個(gè)數(shù)將大于或等于t+1，這與假設(shè)不符，所以X是正確的連通分支。

Khanna和Fuchs[5]定義了函數(shù)Φ用以研究連續(xù)診斷。下文中將擴(kuò)展Φ的定義，使得此函數(shù)適用于(t,k)診斷。

圖2 EH(1,2)的圖G生成子圖G+

通常來(lái)說(shuō)，對(duì)于一個(gè)給定系統(tǒng)，求出Φ函數(shù)是比較困難的。為了將上述的方法能得以實(shí)現(xiàn)，本文將尋找滿足條件的t值和k值。下節(jié)內(nèi)容求算了交換超立方網(wǎng)EH（s,p）基于PMC模型下滿足(t,k)診斷的t值。

3.1 可取的t值

定義I（α）=max|{(z1,z2)|z1∈Z,z2∈Z且，即在基數(shù)為α的子集內(nèi)，計(jì)算出端點(diǎn)都在此子集內(nèi)的邊，其中，I（α）為在G中選取不同子集而計(jì)算出的最大值。顯然I（1）=0。在本文中，假設(shè)對(duì)數(shù)函數(shù)以2為底。

引理5 在交換超立方網(wǎng)中，I（α）≤αlbα

證明根據(jù)引理2可得，EH（s,p）可拆分成2個(gè)EH（s-1,p）或2個(gè)EH（s,p-1）。在本節(jié)中，將EH（s,p）拆分成2個(gè)EH（s-1,p），并記做EHa（s-1,p）和EHb（s-1,p）,將EH（s,p）記做（s+p）維交換超立方網(wǎng)，EH（s-1,p）記為（s+p-1）維交換超立方網(wǎng)。假設(shè)X是G的一個(gè)子集，即X?V，且，其中，設(shè)Xa為X與 EHa（s-1,p）的交集，Xb為X與EHb（s-1,p）的交集，即有

在下列內(nèi)容中，本文將結(jié)合交換超立方網(wǎng)的結(jié)構(gòu)性質(zhì)和上述相關(guān)內(nèi)容，求算出Ψ（t+1）的不等式關(guān)系，并根據(jù)此不等式關(guān)系求算出滿足(t,k)診斷的t值，即系統(tǒng)的(t,k)診斷度。

證明假設(shè)F=｛Y1,Y2…Yd｝且其中，。在交換超立方網(wǎng)EH（s,p）（1≤s≤p ）中，每個(gè)節(jié)點(diǎn)的度為s+1或p+1,即所有節(jié)點(diǎn)的度都小于或等于p+1。由于與F中任意節(jié)點(diǎn)相連的邊的數(shù)目不超過(guò)，其中，為2個(gè)端點(diǎn)都在F內(nèi)的邊數(shù)，那么就有F與(V-F)之間的邊數(shù)小于或等于

化解不等式有

下節(jié)內(nèi)容論述了交換超立方網(wǎng)EH（s,p）基于PMC模型下滿足(t,k)診斷可取的k值。

3.2 可取的k值

引理8 對(duì)于圖G=（V,E），如果U是V的一個(gè)子集，且W?V-U是V-U的一個(gè)連通分支，那么

證明 因?yàn)閃?V-U且W是連通分支，所以在W和V-U-W之間不存在任何邊。如果，那么W不能成為V-U的一個(gè)連通分支，這與假設(shè)相矛盾，所以

通過(guò)上述求算出可取的t值和k值，且有交換超立方網(wǎng)EH(s,p)(1≤s≤p)的點(diǎn)連通度k(G)=s+1，即可以得出定理1。

由定理1可知，交換超立方網(wǎng)基于PMC模型下的(t,k)診斷度為，而交換超立方網(wǎng)的傳統(tǒng)診斷度已知為k(G)，其中，,很顯然，所以交換超立方網(wǎng)基于PMC模型下的(t,k)診斷度大于其傳統(tǒng)診斷度。

4 交換超立方網(wǎng)的條件(t,k)診斷度

在本節(jié)中，將討論交換超立方網(wǎng)EH(s,p)的條件(t,k)診斷度，即在交換超立方網(wǎng)中的任意一個(gè)節(jié)點(diǎn)存在至少一個(gè)正確鄰居節(jié)點(diǎn)的限制條件下，對(duì)交換超立方網(wǎng)進(jìn)行(t,k)診斷方法得到的診斷度。和第3節(jié)類似，首先將構(gòu)造出G的生成子圖G+，并在G+中劃分出各個(gè)連通分支。下面介紹幾個(gè)引理，用以判斷某些連通分支是否正確。

引理10 X是G+中的一個(gè)連通分支，如果存在節(jié)點(diǎn)x∈X且N（x）?X，那么X是正確的連通分支。

證明 假設(shè)X是故障的連通分支，即節(jié)點(diǎn)x是故障節(jié)點(diǎn)。由于在G+中E+={(ui,uj)|(ui,uj)∈E且σ(ui,uj)=0}，根據(jù)PMC模型的測(cè)試規(guī)則可知，N(x)中所有節(jié)點(diǎn)都是故障的，這與條件故障模型的條件相矛盾，所以X是正確連通分支。

引理11 假設(shè)X=｛x｝是G+中的一個(gè)平凡連通分支，那么x是故障節(jié)點(diǎn)。

證明假設(shè)x是正確節(jié)點(diǎn)，由上述引理可知，N(x)中所有節(jié)點(diǎn)都是故障的，這無(wú)疑和假設(shè)條件是矛盾的；如果N(x)中存在正確節(jié)點(diǎn)，那么X就不是平凡連通分支，這同樣是矛盾的，所以X是故障連通分支，即x是故障節(jié)點(diǎn)。

引理10和引理11提供了2個(gè)充分條件，用以判斷連通分支是否故障，本文稱能被上述2個(gè)引理判斷是否故障的連通分支為顯性連通分支,如圖2(b)所示，圖中存在一個(gè)正確的顯性連通分支和一個(gè)故障的顯性連通分支。下面將給出條件(t,k)診斷的方法：和(t,k)診斷方法類似，本文將首先構(gòu)造出G+，再由引理10和引理11識(shí)別出G+中所有顯性連通分支，對(duì)故障的顯性連通分支進(jìn)行修復(fù)或取代，最后由正確的連通分支確定其鄰居連通分支，即故障連通分支，至此一次迭代才算完成?；谏鲜龇椒?，下面本文將求算出滿足條件(t,k)診斷的t值和k值。

引理12 在交換超立方網(wǎng)EH(s,p)（1≤s≤p）中，如果故障節(jié)點(diǎn)集F滿足條件，那么G+中一定存在顯性連通分支。

證明 在此使用反證法，假設(shè)G+中不存在顯性連通分支。由于，即正確節(jié)點(diǎn)集V-F滿足條件。由顯性連通分支的定義可知，V-F中任意節(jié)點(diǎn)至少和F中的一個(gè)節(jié)點(diǎn)相連，且F中不存在平凡連通分支，即如果x∈F，那么一定存在（x,y）∈E+，其中，y∈F。在此設(shè)V-F到F的邊集為ERF，F(xiàn)到V-F的邊集為EFR，顯然。由上述內(nèi)容可知，即這顯然是矛盾。所以G+一定存在顯性連通分支。

引理13假設(shè)在G+中存在顯性連通分支且其都是故障的連通分支。如果，那么G+中至少存在m個(gè)顯性連通分支，其中，m是一個(gè)正整數(shù)。

證明 假設(shè)G+中存在m-1個(gè)顯性連通分支。由于，即。設(shè)G+中故障的且非顯性的連通分支個(gè)數(shù)為S，即有運(yùn)用和引理12相同原理可得，且通過(guò)運(yùn)算可得（p+1）p≥（p+1）（p+2），這顯然是矛盾的，所以G+中至少存在m個(gè)顯性連通分支。

定理2 基于PMC模型下，交換超立方網(wǎng)EH(s,p)（1≤s≤p）是條件可診斷的。

由上述定理可得，交換超立方網(wǎng)基于PMC模型下的條件(t,k)診斷度為，而已知其在傳統(tǒng)診斷方法下的條件診斷度為4s-3，通過(guò)運(yùn)算可知，即條件(t,k)診斷度大于傳統(tǒng)的條件診斷度。

5 結(jié)束語(yǔ)

本文研究了交換超立方網(wǎng)EH（s,p）（1≤s≤p）在PMC模型下的(t,k)診斷度和條件(t,k)診斷度。給出了一個(gè)交換超立方網(wǎng)EH（s,p）（1≤s≤p）是可診斷的。本文結(jié)果顯示交換超立方網(wǎng)的(t,k)診斷度大于其傳統(tǒng)診斷度s+1。計(jì)算交換超立方網(wǎng)EH（s,p）（1≤s≤p）的(t,k)診斷度的最大的困難在于選取合適的t值和k值，使Φ（t+1,k）≥t 。為了給出滿足Φ（t+1,k）≥t 的t值和k值，一方面需要計(jì)算I（α），另一方面需要考慮與交換超立方網(wǎng)的網(wǎng)絡(luò)結(jié)構(gòu)特性的結(jié)合。此外，本文考慮了任意一個(gè)節(jié)點(diǎn)至少存在一個(gè)正確鄰居節(jié)點(diǎn)條件下交換超立方網(wǎng)EH（s,p）（1≤s≤p）的故障診斷即條件診斷問(wèn)題，得出了交換超立方網(wǎng)EH（s,p）（1≤s≤p）是條件可診斷的,其中，條件(t,k)診斷度

由于篇幅及時(shí)間所限，本文只考慮了在PMC診斷模型下交換立方網(wǎng)的(t,k)-故障診斷問(wèn)題，另一個(gè)影響較為廣泛的比較故障模型下的交換超立方網(wǎng)的故障診斷問(wèn)題是下一個(gè)研究的重點(diǎn)。

參考文獻(xiàn)：

[1]MALEK M.A comparison connection assignment for diagnosable of multiprocessor systems[C]//The 7th Annual Symposium on Computer Architecture.New York,United States,c1980:31-36.

[2]MAENG J,MALEKM.A comparison connection assignmentfor self-diagnosis of multiprocessor systems[C]//The 11th InternationalSymposium on Fault Tolerant Computing.Edinburgh,Scotland,c1981: 173-175.

[3]SENGUPTAA,DANBURAAT.Onself-diagnosable multiprocessorsystems:diagnosis by the comparison approach[J].IEEE Transactions on Computers.1992,41(11):1386-1396.

[4]HONG W S,HSIEH S Y.Strong diagnosability and conditional diagnosability of augmented cubes under the comparison diagnosis model[J].IEEE Transactions on Reliability,2012,61(1):140-148.

[5]KHANNNA S,PUCHS W K.A Graph partitioning approach to sequential diagnosis[J].IEEE Transactions on Computers,1997,46(1):39-47.

[6]LEE C W,HSIEH S Y.Diagnosability of two-matching composition network under the MM*model[J].IEEE Transactions on Dependable and Secure Computing.2011,8(2):246-255.

[7]HSIEH S Y,CHEN Y S.Strongly diagnosable product networks under the comparison diagnosis model[J].IEEE Transactions on Computers,2008,57(6):721-732.

[8]PREPARATAFP,METZEG,CHIENRT.Onthe connectionassignmentproblemofdiagnosablesystems[J].IEEE Transactions on Electronic Computers,1967,16(6):848-854.

[9]CHANG N W,HSIEH S Y.Conditional diagnosability of augmented cubes under the PMC model[J].IEEE Transactions on Dependable and Secure Computing,2012,9(1):46-60.

[10]ZHU Q.The conditional diagnosability of crossed cubes under the comparison model[J].International Journal of Computer Mathematics,2010,87(15):3387-3396.

[11]LIN C K,KUNG T L,TAN J J M.An algorithmic approach to conditional-faultlocaldiagnosisofregularmultiprocessor interconnected systems under the PMC model[J].IEEE Transactions onComputers,2013,62(3):439-451.

[12]LIN C K,PENG S L,TAN J J M,et al.The diagnosability of g-good-neighbor conditional-fault hypercube under PMC model[C]//2010 International Conference on Parallel and Distributed Processing Techniques and Applications(PDPTA’10).Las Vegas,USA,c2010: 494-499.

[13]CHANG G Y,CHANG G J,CHEN G H.Diagnosability of regular networks[J].IEEE Transactions on Parallel and Distributed Systems,2005,16(4):314-323.

[14]XU M,THULASIRAMAN K,XU X D.Conditional diagnosability of matching composition networks under the PMC model[J].IEEE Transactions on Circuits and Systems-II:Express Briefs,2009,56(11): 875-879.

[15]LIN C K,KUNG T L,TAN J J M.Conditional-fault diagnosability of multiprocessor systems with an efficient local diagnosis algorithm under the PMC model[J].IEEE Transactions on Computers,2011,22(10):1669-1680.

[16]ARAKI T,SHIBATA Y.(t,k)-Diagnosable system:a generalization of the PMC models[J].IEEE Transactions on Computers,2003,52(7): 971-975.

[17]CHEN C,HESIH S Y.(t,k)-diagnosis for component-composition graphs under theMM*model[J].IEEE Transactions on Computers,2011,60(12):1704-1717.

[18]CHANG G Y.(t,k)-diagnosability for regular networks[J].IEEE Transactions on Computers,2010,59(9):1153-1157.

[19]CHANGGY,CHENGH.(t,k)-Diagnosabilityof multiprocessorsystems with applications to grids and toris[J].Siam Journal on Computing,2007,37(4):1280-1298.

[20]LAI P L,TAN J J M,CHANG C P,et al.Conditional diagnosability measures for large multiprocessor systems[J].IEEE Transactions on Computers,2005,54(2):165-175.

[21]郭晨,梁家榮,葛志輝,等.基于互測(cè)PMC模型的條件診斷算法[J].電子學(xué)報(bào),2015,43(2):255-261.GUO C,LIANG J R,GE Z H,et al.A conditional diagnosis algorithm based on ex-test PMC model[J].Chinese Journal of Electronics,2015,43(2):255-261.

[22]LOH P K K,HSU W J,PAN Y.The exchange hypercube[J].IEEE Transactions on Parallel and Distributed Systems,2005,16(9): 866-874.

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

[24]MA MJ,ZHUL Y.Thesuperconnectivityofexchanged hypercubes[J].Information Processing Letters,2011,111(8):360-364.

[25]LI X J,XU J M.Generalized measures of fault tolerance in exchanged hypercubes[J].InformationProcessingLetters,2013,113(14): 533-537.

Research on(t,k)-diagnosability for exchanged hypercube network

XIONG Xi,LIANG Jia-rong,MAQiang
(School of Computer and Electronic Information,Guangxi University,Nanning 530004,China)

Abstract:Fault diagnosis was an important part in the processing of network system repair.PMC was a diagnosis model which was simple and easy to be understood.Through analysis of the structure of exchanged hypercube,a generalization measure of fault diagnosis for the network system was provided,called(t,k)-fault diagnosis method.By computing,it is shown that EH（s,p）is-diagnosable and conditional-diagnosable,where1≤s≤p.The result shows that the(t,k)-diagnosability of EH(s,p)is,which is bigger than its ordinary diagnosability s+1,and the conditional(t,k)-diagnosability is,which is bigger than its ordinary conditional diagnosability 4s-3.Above results present the important theory basis for fault diagnosis of exchanged hypercube network.

Key words:exchanged hypercube network,(t,k)-diagnosability,conditional(t,k)-diagnosability,PMC model

TP393

A

10.11959/j.issn.1000-436x.2016067

2015-03-26；

2015-09-29

梁家榮，972303617@qq.com

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

The National Natural Science Foundation of China(No.61363002)

熊茜（1990-），男，江西豐城人，廣西大學(xué)碩士生，主要研究方向?yàn)榛ヂ?lián)網(wǎng)絡(luò)的故障診斷、并行與網(wǎng)絡(luò)計(jì)算。

梁家榮（1966-），男，廣西玉林人，博士，廣西大學(xué)教授，主要研究方向?yàn)榛ヂ?lián)網(wǎng)絡(luò)的故障診斷、并行與網(wǎng)絡(luò)計(jì)算、算法設(shè)計(jì)與分析。

馬強(qiáng)（1990-），男，甘肅隴南人，廣西大學(xué)碩士生，主要研究方向?yàn)閳D論、互聯(lián)網(wǎng)絡(luò)的故障診斷。