平衡立方體在PMC模型下的1-好鄰條件診斷度

趙 昳，原 軍

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

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

1 基本概念及符號(hào)說(shuō)明

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

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

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

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

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

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

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

2012年，Peng等[3]研究了一種較為常見(jiàn)的互連網(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時(shí)，平衡立方體BHn有22n個(gè)點(diǎn)，記為(a0,a1,a2,…,an-1)，其中ai∈{0,1,2,3}，0≤i≤n-1. 每個(gè)點(diǎn)與下面2n個(gè)點(diǎn)相鄰：

(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è)點(diǎn)構(gòu)成的圈，四個(gè)點(diǎn)分別記為0,1,2,3.

圖1 平衡立方體BH1和BH2

Fig.1 Balanced hypercubesBH1andBH2

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

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

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

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

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

2 主要結(jié)果

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

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

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

Fig.2 A distinguishable pair(F1,F2)

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

證明：在BHn中取a,b,c,d四個(gè)點(diǎn)，令a=(0,0,…,0),b=(1,0,…,0),c=(2,0,…,0),d=(3,0,…,0). 令H=(a,b,c,d), 則BHn[H]是一個(gè)長(zhǎng)度為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. 因?yàn)镠=F1ΔF2,F1=NBHn(H), 由定理4可知F1,F2是不可區(qū)分的。

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

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

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

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

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

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

假設(shè)BHn中存在這樣的兩個(gè)1-好鄰條件故障集F1和F2，它們是不可區(qū)分的，并且F1和F2的頂點(diǎn)數(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之間沒(méi)有邊。不失一般性，假設(shè)F2-F1≠?.

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

因?yàn)閚≥2且BHn的所有點(diǎn)都在F1∪F2中，所以 ：

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

矛盾；

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

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

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

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

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

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

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

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

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

證畢。

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

定理1 當(dāng)n≥2時(shí)，平衡立方體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é)報(bào) ，2014, 35(5):390-394.