趙 昳，原 軍

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

目前，半導(dǎo)體技術(shù)的快速發(fā)展使得大規(guī)模計算機(jī)系統(tǒng)在各領(lǐng)域的應(yīng)用越來越廣泛。然而，要建立一個沒有缺陷的大規(guī)模計算機(jī)系統(tǒng)互連網(wǎng)絡(luò)是非常困難的。因為在系統(tǒng)中，所有的處理器要同時運(yùn)行，隨著處理器數(shù)目的急劇增加，網(wǎng)絡(luò)發(fā)生故障是不可避免的。因此，須及時發(fā)現(xiàn)并更換系統(tǒng)中壞掉的處理器，以此來保障計算機(jī)系統(tǒng)的可靠性。為此，我們可以用特定的方法，通過系統(tǒng)故障診斷這樣一個過程來識別出系統(tǒng)中那些出現(xiàn)故障的處理器。1967年，系統(tǒng)級故障診斷理論是被Preparata等[1]創(chuàng)建的。在研究故障診斷問題的過程中他們利用了圖論的方法。在此過程中，Preparata等[1]還提出了第一個該理論所依賴的測試模型——PMC模型。在系統(tǒng)級故障診斷理論中，通過診斷度這一個參數(shù)來衡量互連網(wǎng)絡(luò)系統(tǒng)的故障診斷能力。在一個互連網(wǎng)絡(luò)系統(tǒng)中，診斷度是該系統(tǒng)能夠診斷的最大故障結(jié)點機(jī)的數(shù)目。 經(jīng)典的診斷度總是不加區(qū)分地假定系統(tǒng)的每個結(jié)點子集都有可能同時發(fā)生故障。這樣就會產(chǎn)生一個問題，一般來說，大規(guī)模的互連網(wǎng)絡(luò)系統(tǒng)的一個結(jié)點上的所有鄰點發(fā)生故障的情況少之又少。 從而這樣就無法精確地度量大規(guī)?；ミB網(wǎng)絡(luò)系統(tǒng)的自我故障診斷能力。為了克服以上所述的問題，Lai等[2]對系統(tǒng)中結(jié)點的鄰點集的故障條件進(jìn)行約束，要求所有頂點的鄰點都不能同時發(fā)生故障，由此提出了條件診斷度的概念。類似地， Peng等[3]通過對系統(tǒng)中非故障結(jié)點的鄰點集的故障條件進(jìn)行限制，使得每個非故障頂點滿足至少有g(shù)個非故障鄰點的條件，由此提出了g好鄰條件診斷度。平衡立方體屬于超立方體變形網(wǎng)絡(luò)，相比超立方體它有更好的性質(zhì)。本文在前人研究基礎(chǔ)上，選取PMC模型對平衡立方體的1-好鄰條件診斷度進(jìn)行了研究。

1 基本概念及符號說明

計算機(jī)系統(tǒng)互連網(wǎng)絡(luò)可以用無向圖G=(V,E)來表示，其中圖G的頂點集V=V(G)代表網(wǎng)絡(luò)中的處理器, 邊集E=E(G)代表網(wǎng)絡(luò)中的處理器之間的連接。假設(shè)H是V的一個非空子集。頂點集用H表示，則邊集即為G中的兩端點均在H中的邊構(gòu)成的集合。滿足上述條件的頂點集和邊集構(gòu)成的全體的子圖，稱為H在G中的導(dǎo)出子圖，記為G[H]. 一般地，在圖G中與頂點v關(guān)聯(lián)的邊數(shù)，稱為頂點v在圖G中的度，記為dG(v).特別地，G的頂點的最小度和最大度分別記為δ(G)和Δ(G).若圖G中每個頂點的度都是k，稱圖G為k正則圖。給定圖G的一個頂點u,N(u)表示在圖G中與頂點u相鄰的頂點組成的集合。給定取圖G的任一頂點集S, 鄰集NG(S)是S在G中的與S的頂點相鄰的所有頂點的集合。若給定圖G的兩個頂點u,v, 則C(u,v)表示頂點u,v的公共鄰點組成的集合，即C(u,v)={w|w∈N(u),w∈N(v)}. 設(shè)F為G的任意頂點子集。G的g好鄰條件故障集是指頂點子集F滿足條件：V-F中的每一點v在G-F中的鄰點個數(shù)至少為g, 即V-F中的每一點v的最小度至少為g. 頂點集F稱為圖G的割若G-F不連通。如果頂點集F既是G的g好鄰條件故障集又滿足是G的割的定義，則稱F是一個g好鄰條件故障割。G的g好鄰條件連通度是指G中頂點數(shù)最少的g好鄰條件故障割的階數(shù)，記為κ(g)(G). 其余在本文中沒有定義的符號和術(shù)語參見文獻(xiàn)[4].

采用PMC模型對系統(tǒng)G的兩個處理器進(jìn)行測試時，這兩個處理器之間需有物理連線，即這兩個處理器要滿足相鄰的條件?？梢杂庙旤c對u,v∈V(G)這種方式來表示系統(tǒng)G中任意一對相鄰的結(jié)點。其中頂點對左側(cè)的σ(u,v)是測試者，頂點對右側(cè)的u是被測試者。通常用σ(u,v)表示測試結(jié)果，σ(u,v)可能是0或1. 假設(shè)u沒有發(fā)生故障。若v是故障的，則σ(u,v)為1;否則，σ(u,v)為0. 反之，假設(shè)u是故障處理器，即測試者是故障的，σ(u,v)可能隨機(jī)的出現(xiàn)0或1, 會得到不可靠的測試結(jié)果。所有測試結(jié)果的集合σ稱為系統(tǒng)G的校驗子。校驗子σ可以用一個有向圖T=(V(G),L)來表示， 其中頂點對(u,v)∈L的充要條件是u和v在圖G中相鄰。若要故障集F與校驗子σ一致需滿足下述條件：存在頂點子集F?V, 對于任意一條邊(u,v)∈L有σ(u,v)=1當(dāng)且僅當(dāng)v∈F. 若兩個不同的頂點子集F1和F2滿足σ(F1)和σ(F2)的交集非空, 則稱F1和F2是不可區(qū)分的，(F1,F2)是不可區(qū)分點對；否則，稱F1和F2是可區(qū)分的，(F1,F2)是可區(qū)分點對。

定義1 若系統(tǒng)G中，故障處理器的個數(shù)不超過t，所有的故障處理器通過一次測試全部正確識別出來，就稱G是t-可診斷的。在所有使得G是t-可診斷的數(shù)中，最大數(shù)t稱為G的診斷度，記為t(G).

Peng等在文獻(xiàn)[3]中對系統(tǒng)中未發(fā)生故障的結(jié)點的鄰集的故障情況加以限制，提出了g好鄰條件診斷度的概念。

定義2 設(shè)F1和F2是G中任意兩個g好鄰條件故障集且F1和F2的頂點數(shù)至多為t. 若F1,F2是可區(qū)分的，則稱G是g好鄰條件t-可診斷的。圖G的g好鄰條件診斷度tg(G)是使得G是g好鄰條件t-可診斷的t的最大值。

Peng等在文獻(xiàn)[3]中提出了G的兩個g好鄰條件故障集F1和F2可區(qū)分的充分必要條件并且研究了超立方體的g好鄰條件診斷度。

定理1設(shè)F1和F2是G中任意兩個相異的g好鄰條件故障集， 且|F1|≤t, |F2|≤t. 則G是g好鄰條件t-可診斷的當(dāng)且僅當(dāng)F1和F2是可區(qū)分的。

2012年，Peng等[3]研究了一種較為常見的互連網(wǎng)絡(luò)——超立方體的g好鄰條件診斷度，是在PMC模型的基礎(chǔ)上進(jìn)行研究的。Yuan等[5]在Peng的基礎(chǔ)上研究了k元n方體的g好鄰條件診斷度。目前，關(guān)于一些復(fù)雜的互連網(wǎng)絡(luò)的g好鄰條件診斷度的研究成果還較少。

本文研究平衡立方體的1-好鄰條件診斷度，下面給出平衡立方體的定義。

定義3 當(dāng)n≥1時，平衡立方體BHn有22n個點，記為(a0,a1,a2,…,an-1)，其中ai∈{0,1,2,3}，0≤i≤n-1. 每個點與下面2n個點相鄰：

(1)(a0±1,a1,a2,…,ai-1,ai,ai+1,…,an-1),

(2)(a0±1,a1,a2,…,ai-1,ai+(-1)a0,ai+1,…,an-1). 其中i是整數(shù)且1≤i≤n-1.

定義4 平衡立方體按照遞歸構(gòu)造定義如下：

(1)平衡立方體BH1是由四個點構(gòu)成的圈，四個點分別記為0,1,2,3.

圖1 平衡立方體BH1和BH2

Fig.1 Balanced hypercubesBH1andBH2

定理2[6]當(dāng)n≥2時，平衡立方體BHn的1-好鄰條件連通度連通度κ1(BHn)=4n-4.

定理3[7]當(dāng)n≥1時令u是平衡立方體BHn的任意一點，則存在頂點v, 使得|C(u,v)|=0 或|C(u,v)|=2或 |C(u,v)|=2n，并且有且僅有一個頂點w, 使得|C(u,w)|=2n.

表1表示與頂點(0,0,…,0)距離為2的頂點，以及這些頂點與(0,0,…,0)的公共鄰點的個數(shù)。

表1 與頂點(0,0,…,0)距離為2的頂點，以及這些頂點與(0,0,…,0)的公共鄰點

Tab.1 Vertices with distance 2from vertex(0,0,…,0) and the neighbors vertexes

2 主要結(jié)果

先定義頂點集F1,F2以及它們的對稱差F1ΔF2=(F1-F2)∪(F2-F1). 下面給出一個由DahBura等在文獻(xiàn)[7]中提出充要條件，該充要條件是用來判定PMC模型下F1和F2是否可區(qū)分的。

定理4[7]F1和F2是G中任意兩個不同可區(qū)分的頂點子集當(dāng)且僅當(dāng)存在一個頂點u∈V-(F1∪F2),v∈F1ΔF2, 使得邊e=uv∈E. 如圖2所示。

圖2 點集對(F1,F2)在PMC模型下可區(qū)分

Fig.2 A distinguishable pair(F1,F2)

引理1 當(dāng)n≥2時，平衡立方體BHn在PMC模型下的1-好鄰條件診斷度t1(BHn)≤4n-1.

證明：在BHn中取a,b,c,d四個點，令a=(0,0,…,0),b=(1,0,…,0),c=(2,0,…,0),d=(3,0,…,0). 令H=(a,b,c,d), 則BHn[H]是一個長度為4的圈。 由定理3和圖2可知，N(a)=N(c),N(b)=N(d)且N(a)∩N(b)=?. 令F1=NBHn(H)，F(xiàn)2=H∪F1, 且BHn-NBHn(H)是不連通的，則|F1|=4n-4, |F2|=4n, 所以|F1|≤4n, |F2|≤4n. 因為H=F1ΔF2,F1=NBHn(H), 由定理4可知F1,F2是不可區(qū)分的。

證明F1和F2是1-好鄰條件故障集。令Y=V(BHn)-F1∪F2. 因為導(dǎo)出子圖BHn[H]是一個長度為4的圈，所以BHn[H]滿足最小度至少為1.現(xiàn)在考慮BHn[Y]中的頂點。令u∈Y，由平衡立方體BHn的定義可知，BHn中有且僅有一個頂點滿足|N(a)|=|N(c)|=2n，故|N(u)∩F1|<2n. 且平衡立方體是2n正則的。所以，u在Y=V(BHn)-F1∪F2中至少有一個鄰點。即BHn[Y]中的頂點滿足最小度至少為1.

所以F1和F2是1-好鄰條件故障集。

由于F1和F2是不可區(qū)分的，|F1|=4n-4, |F2|=4n, 故由定義2和定理1可知當(dāng)n≥2時，平衡立方體BHn在PMC模型下的1-好鄰條件診斷度t1(BHn)≤4n-1.

下面討論t1(BHn)的下界。

引理2 當(dāng)n≥2時，平衡立方體BHn在PMC模型下的1-好鄰條件診斷度t1(BHn)≥4n-1.

證明：由定義2可知，要證t1(BHn)≥4n-1,只需證明BHn是1-好鄰條件(4n-1)-診斷的，也就是要證明在BHn中任意頂點數(shù)至多為(4n-1)的兩個1-好鄰條件故障集F1，F(xiàn)2都是可區(qū)分的。

假設(shè)BHn中存在這樣的兩個1-好鄰條件故障集F1和F2，它們是不可區(qū)分的，并且F1和F2的頂點數(shù)不多于(4n-1).由定理4可知，F(xiàn)1和F2不可區(qū)分包含以下兩種情況：(1)V(BHn)=F1∪F2； (2)V(BHn)≠F1∪F2且V(BHn)-F1∪F2與F1ΔF2之間沒有邊。不失一般性，假設(shè)F2-F1≠?.

情況1：V(BHn)=F1∪F2.

因為n≥2且BHn的所有點都在F1∪F2中，所以 ：

22n=|V(BHn)|=|F1|+|F2|-|F1∩F2|≤2(4n-1).

矛盾；

情況2：V(BHn)≠F1∪F2,且V(BHn)-F1∪F2與F1ΔF2之間沒有邊。

因為F2-F1≠?，F(xiàn)1是1-好鄰條件故障集，所以F2-F1中的任意一點在F2-F1的導(dǎo)出子圖中至少有一個無故障鄰點，即δ(BHn[F2-F1])≥1. 故而|F2-F1|≥2.

斷言：F1∩F2是BHn的1-好鄰條件故障割。

首先，假設(shè)F1?F2. 因為F2是1-好鄰條件故障集，所以δ(BHn-F2)≥1. 又因為δ(BHn[F2-F1])≥1, 所以F1∩F2是1-好鄰條件故障集。由于V(BHn)-F1∪F2與F1ΔF2之間沒有邊，故V(BHn)-F2與F2-F1不連通。因此，當(dāng)F1?F2時，F(xiàn)1∩F2是BHn的1-好鄰條件故障割。

假設(shè)F1?F2，即F2-F1≠?，且F1-F2≠?，因為F1和F2都是1-好鄰條件故障集，且V(BHn)-F1∪F2與F1ΔF2之間沒有邊，所以δ(BHn[F1-F2])≥1,δ(BHn[F2-F1])≥1. 又因為δ(BHn-F1∪F2)≥1, 所以，F(xiàn)1∩F2是BHn的1-好鄰條件故障集。由于V(BHn)-F1∪F2與F1ΔF2之間沒有邊，故V(BHn)-F1-F2與F1ΔF2不連通。因此，當(dāng)F1?F2時，F(xiàn)1∩F2是BHn的1-好鄰條件故障割。斷言成立。

由定理2可知κ1(BHn)=4n-4. 因為F1∩F2是BHn的1-好鄰條件故障割，所以|F1∩F2|≥4n-4. 而|F2|=|F2-F1|+|F1∩F2|, 且|F2-F1|≥2. 因為V(BHn)-F1∪F2與F1ΔF2之間沒有邊，故N(F2-F1)?F1∩F2, 所以有|N(F2-F1)|≤|F1∩F2|.當(dāng)|F2-F1|=2時，|N(F2-F1)|=4n-2,此時|F1∩F2|≥4n-2. 故|F2|=|F2-F1|+|F1∩F2|=2+4n-2=4n與假設(shè)|F2|≤4n-1矛盾。

當(dāng)|F2-F1|=3時，|N(F2-F1)|≥6n-max{2,2n}=4n,此時|F1∩F2|≥4n. 故|F2|=|F2-F1|+|F1∩F2|=3+

4n與假設(shè)|F2|≤4n-1矛盾。

當(dāng)|F2-F1|≥4時，必有|F2|=|F2-F1|+|F1∩F2|=4+4n-4=4n成立，與假設(shè)|F2|≤4n-1矛盾。

證畢。

通過引理1和引理2分別討論了當(dāng)n≥2時，平衡立方體BHn在PMC模型下的1-好鄰條件診斷度有的上、下界。 綜上，有：

定理1 當(dāng)n≥2時，平衡立方體BHn在PMC模型下的1-好鄰條件診斷度t1(BHn)=4n-1.

參考文獻(xiàn)：

[1] PRETARATA F P, METZE G, CHIEN R T. On the connection assignment problem of diagnosis systems[J].IEEE Transactions on Computers, 1967, 16: 848-854.

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

[3] PENG S L, LIN C K, TAN J J M, et al. The g-good-neighbor conditional diagnosability of hypercube under PMC model[J]. Applied Mathematics and Computation, 2012, 218: 10406 -10412.

[4] BONDY J A, MURTY U S R. Graph Theory with Applications[M]. New York: The Macmillan Press Ltd, 1976.

[5] YUAN J, LIU A X, MA X, et al. The g-good-neighbor conditional diagnosability ofk-aryn-cubes under the PMC model and MM* model[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26:1165-1177.

[6] YANG M C. Super connectivity of balanced hypercube[J]. Applied mathematics and computation. 2012, 219:970-975.

[7] YANG M C, YANG MH. Reliability analysis of balanced hypercubes[C]// Proceeding of computing, communications and applications conference, London,UK,2012, 376-379.

[8] DAHBURA A T, MASSON G M. AnO(n2.5) faulty identification algorithm for diagnosable systems[J]. IEEE Transactions on Computers,1984, 33:486-492.

[9] LATIFI S, HEDGE M, NARAGHI POUR M. Conditional connectivity measures for large multiprocessor systems[J]. IEEE Transactions on Computers, 1994, 43:218-222.

[10] HAKIMI S L, AMIN A T. Characterization of connection assignment diagnosable systems[J]. IEEE Transactions on Computers, 1974, 23:86-88.

[11] 劉秀麗，原軍，馬雪. 交換超立方體在PMC模型下的g-好鄰條件診斷度[J] .太原科技大學(xué)學(xué)報 ，2014, 35(5):390-394.