超立方體Qn在PMC模型下的2-條件診斷度

韓 妙,劉 杰,原 軍

(太原科技大學(xué)應(yīng)用科學(xué)學(xué)院,太原 030024)

隨著計(jì)算機(jī)的普及與發(fā)展,計(jì)算機(jī)系統(tǒng)越來越復(fù)雜,形成如今的多處理器系統(tǒng),雖然多處理器系統(tǒng)在計(jì)算等方面有著卓越的優(yōu)勢,但計(jì)算機(jī)系統(tǒng)發(fā)生故障的概率也大大增加。為了保證計(jì)算機(jī)系統(tǒng)的正常運(yùn)行,診斷出并替換掉故障處理器就至關(guān)重要。故障診斷需要依靠模型的建立,1967年,Preparata等[1]創(chuàng)建了系統(tǒng)級故障診斷理論,提出了一種系統(tǒng)級故障診斷模型——PMC模型。PMC模型是通過相鄰兩個(gè)處理器相互測來試實(shí)現(xiàn)故障診斷的。傳統(tǒng)的診斷度假定系統(tǒng)的每個(gè)結(jié)點(diǎn)的所有鄰點(diǎn)可能同時(shí)發(fā)生故障,但從實(shí)際角度出發(fā),發(fā)生這種事件的概率很小。因此傳統(tǒng)診斷度嚴(yán)重低估了系統(tǒng)的自我診斷能力。為改善傳統(tǒng)診斷度這一缺點(diǎn),很多學(xué)者提出了新的診斷度。2005年,Lai等[2]提出了條件診斷度的概念,它要求系統(tǒng)中每個(gè)結(jié)點(diǎn)至少有1個(gè)好鄰點(diǎn),并證明了超立方體Qn在PMC模型下的條件診斷度為4(n-2)+1,n≥5.2012年,Peng等[3]提出了g-好鄰條件診斷度的概念,它要求系統(tǒng)中每個(gè)非故障結(jié)點(diǎn)至少有g(shù)個(gè)好鄰點(diǎn),并證明了超立方體Qn在PMC模型下的g-好鄰條件診斷度為2g(n-g)+2g-1,0≤g≤n-3.g-好鄰條件診斷度的研究得到了學(xué)者的廣泛關(guān)注,取得了一系列的研究成果,參見文獻(xiàn)[3-5].在條件診斷度和g-好鄰條件診斷度概念的啟發(fā)下,我們提出了2-條件診斷度的概念,要求系統(tǒng)中每個(gè)結(jié)點(diǎn)至少有2個(gè)好鄰點(diǎn)。本文研究了超立方體Qn在PMC模型下的2-條件診斷度。

1 預(yù)備知識

Preparata等[1]提出的PMC模型是通過相鄰兩個(gè)處理器相互測試,即對應(yīng)到圖G中兩個(gè)處理器為頂點(diǎn)對(u,v),(u,v)表示從u到v進(jìn)行測試,則u為測試者,v為被測試者。用0和1代表是否出現(xiàn)故障,0代表未出現(xiàn)故障,1代表出現(xiàn)故障。若u為故障點(diǎn),則測試結(jié)果不可靠。系統(tǒng)在PMC模型下的測試過程就是對每對相鄰結(jié)點(diǎn)進(jìn)行相互測試,因此系統(tǒng)的測試結(jié)果是一個(gè)集合,稱為G的癥候,用σ表示,可以用一個(gè)有向圖T=(V,L)表示,其中(u,v)∈L代表u和v相鄰。所以一個(gè)癥候σ就是一個(gè)函數(shù)σ:L→{0,1}.對于給定的癥候σ,頂點(diǎn)集F?V(G),若癥候σ是由頂點(diǎn)集F滿足下列情況產(chǎn)生的,則稱σ與F一致。

(1) 若u,v∈V(G)-F,則σ(u,v)=0;

(2) 若u∈F,v∈V(G)-F,則σ(u,v)=1;

(3) 若u∈V(G)-F,v∈F,則σ(u,v)=1;

(4) 若u,v∈F,則σ(u,v)=1.

令σ(F)是與F一致的癥候的集合。對于G中兩個(gè)不同的頂點(diǎn)子集F1和F2,如果σ(F1)∩σ(F2)=?,則稱F1和F2是可區(qū)分的;否則,稱F1和F2是不可區(qū)分的。

圖1 超立方體Q1、Q2、Q3Fig.1 Hypercubes Q1、Q2、Q3

由定義1.1可知,Qn是一個(gè)n正則圖,Qn中任意兩個(gè)相鄰頂點(diǎn)沒有公共鄰點(diǎn)。

定義1.2 在一個(gè)系統(tǒng)G=(V,E)中,對于任意兩個(gè)不同的2-條件故障集F1和F2,其中|F1|≤t和|F2|≤t,若F1和F2是可區(qū)分的,則G是t-可診斷的。使得G是t-可診斷的最大值t,稱為圖G的2-條件診斷度,記為t2(G).

引理1.3[7]若k≤n-2,Qk是Qn的一個(gè)子圖,且CQn(Qk)=NQn(Qk)∪V(Qk),則δ(Qn-CQn(Qk))≥n-2.

引理1.4[4]假設(shè)n≥3,且1≤g≤n-1,則κg(Qn)=(n-g)2g.

引理1.5 設(shè)H是n維超立方體的子圖,H?Q4且CQn(H)=NQn(H)∪V(H),其中n≥5,那么|NQn(H)|=16(n-4).

證明:令Q4=X40n-4,X∈(0,1).由定義1.1知,

|NQn(Q4)|=|V(X410n-5)∪V(X4010n-6)∪…∪V(X40n-51)|=|V(X410n-5)|+|V(X4010n-6)|+…+|X40n-51|=24(n-4)=16(n-4)

引理1.7[8]設(shè)A是Qn中每個(gè)點(diǎn)的度至少為g的子圖,則當(dāng)1≤g≤n時(shí),有|V(A)|≥2g.

2 主要結(jié)果

DahBura等[9]給出了PMC模型下F1和F2是可區(qū)分的充要條件。

引理2.1[10]設(shè)F1和F2是G中任意兩個(gè)不同的頂點(diǎn)子集,則F1和F2是可區(qū)分的當(dāng)且僅當(dāng)存在一個(gè)頂點(diǎn)u∈V(F1∪F2),v∈F1ΔF2,使得(u,v)∈E,如圖2所示。

引理2.2是由定義1.2和引理2.1得到PMC模型下2-條件t-可診斷的充要條件。

引理2.2[3]一個(gè)系統(tǒng)G=(V,E)在PMC模型下是2-條件t-可診斷的充要條件對于G的任意兩個(gè)2-條件故障集F1和F2(|F1|≤t,|F2|≤t),存在頂點(diǎn)u∈VF1∪F2,v∈F1ΔF2,使得(u,v)∈E,如圖2所示。

圖2 點(diǎn)集對(F1,F2)在PMC模型下可區(qū)分Fig.2 A distinguishable pair(F1,F2)under PMC model

首先討論超立方體Qn在PMC模型下t2(Qn)的上界。

引理2.3 設(shè)n≥7,則超立方體Qn在PMC模型下的2-條件診斷度t2(Qn)≤16n-57 .

證明:取超立方體Qn中的一個(gè)子圖H={A1,A2,B1,B2}?Q4,其中H1={A1,A2},H2={B1,B2},Ai,Bi?Q2,i∈{1,2}.圖H的構(gòu)造如下圖3所示。我們假設(shè)F1=H1∪NQn(H),F2=H2∪NQn(H),F=F1∪F2.

由引理1.5知,

|N(H)|=24(n-4)=16(n-4)

從而

|F1|=16(n-4)+8=16n-56,

|F2|=16(n-4)+8=16n-56

由2條件故障集的定義知,對任意的u∈V(Qn),都有|NQn-F(u)|≥2.不失一般性,假設(shè)H?Q4=X40n-4,下面分三種情形討論:

情形一:u∈H1∪H2.

不妨設(shè)u∈H1,由于H?Q4,如圖3,故|NQn-F1(u)|=|NF2-F1(u)|=2.同理,u∈H2時(shí),|NQn-F2(u)|=|NF1-F2(u)|=2.

情形二:u∈N(H).

易看出NQn(H)=V(X410n-5)∪V(X4010n-6)∪…∪V(X40n-51).不妨設(shè)u∈V(X410n-5),令u=u1u2u3u410n-5,則|NH(u)|=1;|NQn[X410n-5](u)|=4,即|NN(H)(u)|=4.因此,當(dāng)n≥7時(shí),|NQn-F(u)|=n-5≥2.

情形三:u∈V-(F1∪F2).

由引理1.3,當(dāng)n≥4時(shí),δ(V-F1∪F2)≥n-2≥2.也就是說,|NQn-F(u)|≥n-2≥2.

結(jié)合三種情形可得,F1和F2是2-條件故障集。

又因?yàn)镹(H)?F1∩F2,所以對任意u∈F1ΔF2,v∈V(Qn)-(F1∪F2),有(u,v)?E(Qn).由引理2.1知,F1和F2不可分。再由引理2.2知,超立方體Qn在PMC模型下不是2-條件(16n-56)-可診斷的,即t2(Qn)≤16n-57.引理得證。

圖3 圖H及頂點(diǎn)集F1和F2Fig.3 Graph H and vertex sets F1 and F2

下面討論超立方體Qn在PMC模型下t2(Qn)的下界。

引理2.4 設(shè)n≥7,假設(shè)超立方體Qn中的任意兩個(gè)2-條件故障集F1和F2都有F1∩F2是Qn的一個(gè)4-好鄰割,則超立方體Qn在PMC模型下的2-條件診斷度:t2(Qn)≥16n-57.

證明:欲證明t2(Qn)≥16n-57,則只需要證明Qn是2-條件(16n-57)-可診斷的,根據(jù)引理2.1和引理2.2,等價(jià)于證明V(Qn)中任意兩個(gè)不同的2-條件故障集F1,F2,其中|F1|≤16n-57,|F2|≤16n-57,存在u∈V(Qn)(F1∪F2),v∈F1ΔF2,使得(u,v)∈E(Qn).采用反證法,假設(shè)存在兩個(gè)不同的2-條件故障集F1,F2(|F1|≤16n-57,|F2|≤16n-57).對于任意的u∈V(Qn)(F1∪F2),v∈F1ΔF2,都有(u,v)?E(Qn).不失一般性,假設(shè)F2F1≠?,分以下兩種情形進(jìn)行討論。

情形一:V(Qn)=F1∪F2.

令f(n)=2n-32n+114,則導(dǎo)數(shù)f′(n)=n2n-1-32,當(dāng)n≥5時(shí),f(n)′>0,從而f(n)是一個(gè)增函數(shù)。故當(dāng)n≥7時(shí),f(n)>0.即當(dāng)n≥7時(shí),2n≥32n-114.

另一方面:

2n=|V(Qn)|=|F1|+|F2|-|F1∩F2|≤

|F1|+|F2|=2(16n-57)=32n-114,

矛盾。

情形二:V(Qn)≠F1∪F2.

根據(jù)假設(shè)V(Qn)(F1∪F2)與F1ΔF2之間沒有邊,F2ΔF1≠?且F1和F2是2-條件故障集,可得δ(F1ΔF2)≥4,由引理1.7可知,|F1ΔF2|≥24=16,可知F1-F2和F2-F1中有一個(gè)點(diǎn)的個(gè)數(shù)至少為8,不妨設(shè)|F2-F1|≥8.由題設(shè)可知F1∩F2是Qn的一個(gè)4-好鄰割,再由引理1.4知,

|F1∩F2|≥24(n-4)=16n-64.

從而有：

|F2|=|F2-F1|+|F1∩F2|≥

8+16n-64=16n-56.

這與已知條件中的|F2|≤16n-57矛盾。

綜上所述,兩種情況都產(chǎn)生矛盾,故即當(dāng)n≥7時(shí),Qn是2-條件(16n-57)-可診斷的,即t2(Qn)≥16n-57.

結(jié)合引理2.3和引理2.4可得以下定理:

定理2.5 設(shè)n≥7,假設(shè)超立方體Qn中的任意兩個(gè)2-條件故障集F1和F2都有F1∩F2是Qn的一個(gè)4-好鄰割,則超立方體Qn在PMC模型下的2-條件診斷度:t2(Qn)=16n-57.

下面對超立方體Qn在PMC模型下的2-條件診斷度做進(jìn)一步的討論。

引理2.6 設(shè)n≥61,則超立方體Qn在PMC模型下的2-條件診斷度:t2(Qn)≥16n-57.

證明:欲證明t2(Qn)≥16n-57,則只需要證明Qn是2-條件(16n-57)-可診斷的,根據(jù)引理2.1和引理2.2,等價(jià)于證明V(Qn)中任意兩個(gè)不同的2-條件故障集F1,F2,其中|F1|≤16n-57,|F2|≤16n-57,存在u∈V(Qn)(F1∪F2),v∈F1ΔF2,使得(u,v)∈E(Qn).采用反證法,假設(shè)存在兩個(gè)不同的2-條件故障集F1,F2,其中|F1|≤16n-57,|F2|≤16n-57.對于任意的u∈V(Qn)(F1∪F2),v∈F1ΔF2,都有(u,v)?E(Qn).

由引理1.7知,|F1ΔF2|≥24.令V(Qn)-(F1∪F2)=S,則

|S|=|V(Qn)-(F1∪F2)|≥2n-2(16n-57).

由引理2.4情形一知,當(dāng)n≥7時(shí),|V(Qn)-(F1∪F2)|≥24.由題設(shè)可知F1和F2不可分,所以NQn(F1ΔF2)?F1∩F2.換言之,Qn[V(Qn)-(F1∩F2)]的每個(gè)分支的頂點(diǎn)個(gè)數(shù)不少于24.令F1ΔF2=B,則|B|≥24,|V(Qn-CQn(B))|≥24.由引理1.6得,

另一方面:

2(16n-57)-24≥|F1|+|F2|-

|F1ΔF2|=|F1∩F2|≥

矛盾。

綜上所述,當(dāng)n≥61時(shí),Qn是2-條件(16n-57)-可診斷的,即t2(Qn)≥16n-57.

結(jié)合引理2.3和引理2.6可得以下定理:

定理2.7 設(shè)n≥61,則超立方體Qn在PMC模型下的2-條件診斷度:t2(Qn)=16n-57.

3 結(jié)論

提出了2-條件診斷度的概念,它是條件診斷度概念的一個(gè)推廣。本文首先證明了:若超立方體Qn中的任意兩個(gè)2-條件故障集F1和F2都有F1∩F2是Qn的一個(gè)4-好鄰割,其中n≥7,則超立方體Qn在PMC模型下的2-條件診斷度:t2(Qn)=16n-57.進(jìn)一步,得到當(dāng)n≥61時(shí),超立方體Qn在PMC模型下的2-條件診斷度:t2(Qn)=16n-57.結(jié)果表明,當(dāng)要求每個(gè)結(jié)點(diǎn)的非故障鄰點(diǎn)至少為2時(shí),超立方體能診斷出故障結(jié)點(diǎn)數(shù)較條件診斷度有顯著提升。