分層立方網(wǎng)絡(luò)在MM*模型下的g好鄰條件診斷度

趙 昳，原 軍

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

分層立方網(wǎng)絡(luò)在MM*模型下的g好鄰條件診斷度

趙 昳，原 軍

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

診斷度在衡量互聯(lián)網(wǎng)絡(luò)可靠性方面有著重要的作用。許多著名網(wǎng)絡(luò)的診斷度已被研究。g好鄰條件診斷度擴(kuò)展了傳統(tǒng)診斷度的概念，它要求每個(gè)非故障處理器至少有g(shù)個(gè)非故障鄰點(diǎn)。本文證明了分層立方網(wǎng)絡(luò)HCNn在MM*模型下的1-好鄰條件診斷度為2n+1，2-好鄰條件診斷度為4n-1.

故障診斷；MM*模型；分層立方網(wǎng)絡(luò)；條件診斷度；g好鄰條件診斷度

隨著技術(shù)的發(fā)展，為了獲得更好的運(yùn)行效果，系統(tǒng)規(guī)模在逐漸擴(kuò)大。同時(shí)系統(tǒng)中的元件出現(xiàn)故障的可能性增大，這對系統(tǒng)的可靠性產(chǎn)生了不利的影響。因此，及時(shí)發(fā)現(xiàn)并替換掉這些故障元件變的尤為重要。

1967年，Preparata[1]等提出了系統(tǒng)級故障診斷理論，它能夠自動的檢測系統(tǒng)中的處理器。系統(tǒng)級故障診斷理論的研究依賴于測試模型的建立，許多測試模型已被提出。比較模型(MM模型)是一種重要的系統(tǒng)級故障診斷模型，它是由Maeng和Malek[2]共同提出來的。MM診斷模型是由某個(gè)處理機(jī)向它的兩個(gè)相鄰處理機(jī)發(fā)出相同的的測試任務(wù)，通過比較兩個(gè)被測試者在同一特定輸入下的運(yùn)算結(jié)果來判斷它們的故障情況。MM*模型是MM的一種特殊情況，在該模型下，每個(gè)結(jié)點(diǎn)機(jī)均對與它有直接物理連線相連的任意兩個(gè)不同結(jié)點(diǎn)機(jī)的運(yùn)算結(jié)果進(jìn)行比較。

Lai[3]等對已有的診斷度條件進(jìn)行了改進(jìn)，要求所有頂點(diǎn)的鄰點(diǎn)都不能同時(shí)發(fā)生故障，提出了條件診斷度的概念。類似地，Peng[4]等通過對系統(tǒng)中非故障結(jié)點(diǎn)的鄰點(diǎn)集的故障條件進(jìn)行限制，使得每個(gè)非故障頂點(diǎn)至少有g(shù)個(gè)非故障鄰點(diǎn)，提出了g好鄰條件診斷度。 隨著互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的不斷發(fā)展，許多以超立方體網(wǎng)絡(luò)為基礎(chǔ)的變形網(wǎng)絡(luò)也隨之產(chǎn)生，比如，交叉立方體，扭立方體，分層立方網(wǎng)絡(luò)，這些變形網(wǎng)絡(luò)比超立方體有更好的拓?fù)湫再|(zhì)。在本文中，采用MM*模型作為系統(tǒng)故障診斷模型，研究并得出了分層立方網(wǎng)絡(luò)在MM*模型下g時(shí)的G好鄰條件診斷度。

1 基本概念及符號說明

在MM模型下，一個(gè)處理器同時(shí)對它的兩個(gè)相鄰處理器進(jìn)行測試，然后比較它們的結(jié)果。為了與MM模型保持一致，我們有以下幾個(gè)假設(shè)：

(1)所有故障都是永恒的；

(2)故障處理器對于給定的任務(wù)都會給出錯(cuò)誤的輸出結(jié)果；

(3)有故障處理器產(chǎn)生的比較結(jié)果是不可靠的；

(4)給定同樣任務(wù)和輸入的兩個(gè)故障處理器不能產(chǎn)生同樣的輸出結(jié)果。

通過比較方法得到的診斷可以用一個(gè)帶標(biāo)記的圖MVG,L來表示，稱為比較圖，其中L表示被標(biāo)記的邊的集合。一條標(biāo)記邊u,vw表示一個(gè)從w到u,v的比較，這意味著u,w,v,w∈EG。在MVG,L中，所有比較的結(jié)果組成的集合稱為校驗(yàn)子，記作σ*.ru,vw表示被w比較的頂點(diǎn)u和v的比較結(jié)果。如果比較結(jié)果一致，用ru,vw=0 表示；否則，用ru,vw=1表示。因此，一個(gè)校驗(yàn)子是一個(gè)函數(shù)：σ:L→0,1。MM*模型是MM模型的一種特殊情況。在MM*模型下，若u,w,v,w∈EG，則u,vw∈L. 對于給定的校驗(yàn)子σ*，對于頂點(diǎn)集F?VG，如果校驗(yàn)子σ*是由頂點(diǎn)集F滿足下列情況產(chǎn)生的，則稱σ*與F一致。

(1)若u,v∈F,w∈VG-F，則σ*u,vw=1;

(2)若u∈F,v,w∈VG-F，則σ*u,vw=1;

(3)若u,v,w∈VG-F，則σ*u,vw=0

由于故障的比較器產(chǎn)生不可靠的結(jié)果，故一個(gè)故障集可以產(chǎn)生不同的校驗(yàn)子。令σ*F是與F一致的校驗(yàn)子的集合。對兩個(gè)不同的頂點(diǎn)子集F1和F2，若σF1∩σF2=?，則稱F1和F2是可區(qū)分的，t為可區(qū)分的點(diǎn)對；否則，稱G和t是不可區(qū)分的，t為不可區(qū)分的點(diǎn)對。

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

定義2 若G中任意兩個(gè)頂點(diǎn)數(shù)至多為t的g好鄰條件故障集F1，F(xiàn)2都是可區(qū)分的，則稱G是g好鄰條件t-可診斷的。 使得G是g好鄰條件t-可診斷的最大值t稱為G的g好鄰條件診斷度，記作tgG.

定理3 設(shè)F1和F2是G中任意兩個(gè)不同的頂點(diǎn)子集，且F1≤t，F(xiàn)2≤t. 則G是t-可診斷的當(dāng)且僅當(dāng)F1和F2是可區(qū)分的。

下面給出分層立方網(wǎng)絡(luò)的定義。

定義4 分層立方網(wǎng)絡(luò)HCNn中兩個(gè)結(jié)點(diǎn)u=x,y和v=w,z是相連的，當(dāng)且僅當(dāng)恰好以下三個(gè)條件之一成立：

(1)x=w且Hy,z=1；

(3)x=z且y=w.

引理57分層立方網(wǎng)絡(luò)HCNn有如下基本性質(zhì)：

HCNn的正則度為n+1；HCNn點(diǎn)連通度為n+1.

引理68當(dāng)n≥3時(shí)，分層立方網(wǎng)絡(luò)HCNn的R1連通度κ1HCNn=2n.

圖1 分層立方網(wǎng)絡(luò)HCN2

引理78當(dāng)n≥3時(shí)，分層立方網(wǎng)絡(luò)HCNn的R2連通度κ2HCNn=4n-4.

2 主要結(jié)果

定義頂點(diǎn)集F1和F2，F(xiàn)1和F2的對稱差F1ΔF2=F1-F2∪F2-F1. Sengupta和Dahbura9給出了判定在MM*模型下，F(xiàn)1和F2是否可區(qū)分的充要條件。

定理99設(shè)F1和F2是G中任意兩個(gè)不同的頂點(diǎn)子集，則在MM*模型下，F(xiàn)1和F2是可區(qū)分的當(dāng)且僅當(dāng)滿足下面三個(gè)條件之一：

(1)存在兩個(gè)頂點(diǎn)u,w∈VG-F1-F2，頂點(diǎn)v∈F1ΔF2，使得u,w∈E且v,w∈E.

(2)存在兩個(gè)頂點(diǎn)u,v∈F1-F2,頂點(diǎn)w∈VG-F1-F2，使得u,w∈E且v,w∈E.

(3)存在兩個(gè)頂點(diǎn)u,v∈F2-F1,頂點(diǎn)w∈VG-F1-F2，使得u,w∈E且v,w∈E.

由定理9和定義2可得到下面的定理。

定理10 設(shè)F1和F2是G中任意兩個(gè)不同的g好鄰條件故障集，且F1≤t，F(xiàn)2≤t，則在MM*模型下，系統(tǒng)G是g好鄰條件t-可診斷的當(dāng)且僅當(dāng)滿足下列三個(gè)條件之一：

(1)存在兩個(gè)頂點(diǎn)u,w∈VG-F1-F2，頂點(diǎn)v∈F1ΔF2，使得u,w∈E且v,w∈E.

(2)存在兩個(gè)頂點(diǎn)u,v∈F1-F2,頂點(diǎn)w∈VG-F1-F2，使得u,w∈E且v,w∈E.

(3)存在兩個(gè)頂點(diǎn)u,v∈F2-F1,頂點(diǎn)w∈VG-F1-F2，使得u,w∈E且v,w∈E.

引理11 當(dāng)n≥3時(shí)，分層立方網(wǎng)絡(luò)HCNn在MM*模型下的1-好鄰條件診斷度t1HCNn≤2n+1.

證明：取HCNn中的一條邊u,v，令H=u,v，F(xiàn)1=NHCNnH，F(xiàn)2=NHCNnH∪VH.由引理5可知NHCNnu,v=2n，且HCNn-Nu,v是不連通的，知F1=2n，F(xiàn)2=2n+2，所以F1≤2n+2，F(xiàn)2≤2n+2. 因?yàn)镠=F1ΔF2，F(xiàn)1=NHCNnH，由定理9可知F1和F2是不可區(qū)分的。

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

由于F1和F2是不可區(qū)分的，F(xiàn)1=2n，F(xiàn)2=2n+2，故由定義2和定理3可知當(dāng)n≥3時(shí)，分層立方網(wǎng)絡(luò)HCNn在MM*模型下的1-好鄰條件診斷度t1HCNn≤2n+1.

引理12 當(dāng)n≥3時(shí)，分層立方網(wǎng)絡(luò)HCNn在MM*模型下的1-好鄰條件診斷度t1HCNn≥2n+1.證明：由定理3可知，只需證明HCNn是1-好鄰條件2n+1-診斷的。要證HCNn是1-好鄰條件2n+1-診斷的，只需證明在HCNn中任意兩個(gè)頂點(diǎn)數(shù)至多為2n+1的1-好鄰條件故障集F1，F(xiàn)2都是可區(qū)分的。

假設(shè)HCNn中存在這樣的兩個(gè)1-好鄰條件故障集F1和F2，它們是不可區(qū)分的，并且F1和F2的頂點(diǎn)數(shù)不多于2n+1. 不失一般性，假設(shè)F2-F1≠φ. 討論下面兩種情況。

情況1VHCNn=F1∪F2.

由VHCNn=F1∪F2,

22n=VHCNn=F1+F2-F1∩F2≤F1+F2,≤22n+1≤5n. 因?yàn)閚≥3，這顯然是矛盾的。

情況2VHCNn≠F1∪F2

首先給出一個(gè)斷言。

斷言HCNn-F1-F2不含孤立點(diǎn)。

2nn+1，可知W≤2n+4. 假設(shè)H=?，則：

22n=VHCNn=F1∪F2+W≤F1+F2+W≤

22n+1+2n+6=6n+8. 由n≥3可知矛盾。所以H≠?.

由于點(diǎn)對F1,F2不滿足定理9的條件(1)，且VH不含孤立點(diǎn)，可知在H與F1ΔF2之間沒有邊。因此F1∩F2是HCNn的一個(gè)割，且δHCNn-F1∩F2≥1，即F1∩F2是1-好鄰條件故障割，由引理6可知，當(dāng)g=1時(shí)F1∩F2≥2n. 注意到F1≤2n+1，F(xiàn)2≤2n+1，且F1-F2和F2-F1都非空，所以F1-F2=F2-F1=1. 令F1-F2=v1，F(xiàn)2-F1=v2. 對于任何頂點(diǎn)w∈W，w與v1，v2相鄰。由于在HCNn中任意不相鄰的兩點(diǎn)至多有兩個(gè)共同鄰點(diǎn)，故在VHCNn-F1-F2中至多存在兩個(gè)孤立點(diǎn)。

設(shè)v為孤立點(diǎn)，則在VHCNn-F1-F2中，v與v1，v2相鄰。顯然，NHCNnv-v1,v2?F1∩F2，因?yàn)榉謱恿⒎骄W(wǎng)絡(luò)是無三角圖，所以NHCNnv1-v?F1∩F2，NHCNnv2-v?F1∩F2，NHCNnv-v1,v2∩NHCNnv1-v=?,NHCNnv-v1,v2∩NHCNnv2-v=?. 由于在HCNn中任意兩個(gè)頂點(diǎn)至多有兩個(gè)公共鄰點(diǎn)，故NHCNnv1-v∩NHCNnv2-v≤1. 因此，F(xiàn)1∩F2≥NHCNnv-v1,v2+NHCNnv1-v+

NHCNnv2-v-1=n-1+n+n-1=3n-2可知F2=F2-F1+F1∩F2≥1+3n-2=3n-1>2n+1

n≥3與F1≤2n+1矛盾。

所以當(dāng)n≥3,HCNn在MM*模型下的1-好鄰條件診斷度tg(HCNn)≥2n+1. 證畢。

結(jié)合引理11和引理12，我們可以得到分層立方網(wǎng)絡(luò)HCNn在MM*模型下的1-好鄰條件診斷度。

定理13 當(dāng)n≥3時(shí)，分層立方網(wǎng)絡(luò)HCNn在MM*模型下的1-好鄰條件診斷度t1HCNn=2n+1.

引理14 當(dāng)n≥3時(shí)，分層立方網(wǎng)絡(luò)HCNn在MM*模型下的2-好鄰條件診斷度t2HCNn≤4n-1.

由于F1和F2是不可區(qū)分的，且F1=4n-4，F(xiàn)2=4n，故由定義2和定理3可知當(dāng)g=2，n≥3時(shí)，在MM*模型下，t2HCNn≤4n-1.

引理15 當(dāng)n≥3時(shí)，分層立方網(wǎng)絡(luò)HCNn在MM*模型下的2-好鄰條件診斷度t1HCNn≥4n-1.

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

假設(shè)HCNn中存在這樣的兩個(gè)2-好鄰條件故障集F1和F2，它們是不可區(qū)分的，并且F1和F2的頂點(diǎn)數(shù)不多于4n-1. 不失一般性，假設(shè)F2-F1≠φ. 討論下面兩種情況。

情況1VHCNn=F1∪F2.

因?yàn)閚≥3，VHCNn=F1∪F2

22n=VHCNn=F1+F2-F1∩F2≤F1+F2≤24n-1<8n，矛盾。

情況2VHCNn≠F1∪F2

首先給出一個(gè)斷言。

斷言HCNn-F1-F2不含孤立點(diǎn)。

當(dāng)g=2時(shí)，因?yàn)镕2-F1≠?，F(xiàn)1為2-好鄰條件故障集，且對任意x∈VHCNn-F1，有：NHCNn-F1x≥2.注意到點(diǎn)對F1,F2不滿足定理9的任何一種情況，由定理9(3)可得，對任何兩個(gè)相鄰頂點(diǎn)u,v，不存在頂點(diǎn)w∈VHCNn-F1-F2使得u,w,v,w∈EHCNn.因此在VHCNn-F1-F2中任一頂點(diǎn)w在F2-F1中至多有一個(gè)鄰點(diǎn)。因此，對任意頂點(diǎn)w∈VHCNn-F1-F2，有NHCNn-F1-F2w≥2-1≥1，即VHCNn-F1-F2不含孤立點(diǎn)。斷言證畢。

令u為VHCNn-F1-F2的一個(gè)頂點(diǎn)，由斷言可知，u在VHCNn-F1-F2中至少存在一個(gè)鄰點(diǎn)。由于點(diǎn)對F1,F2不滿足定理9中任何一種情況，由定理10(1)可知，對任何兩個(gè)相鄰頂點(diǎn)u,w∈VHCNn-F1-F2，不存在頂點(diǎn)v∈F1ΔF2，使得u,w∈EHCNn或v,w∈EHCNn. 則可知u在F1ΔF2中不存在鄰點(diǎn)。由u的任意性可知，在VHCNn-F1-F2與F1ΔF2之間沒有邊。

由于F2-F1≠?，F(xiàn)1為2-好鄰條件故障集，且δHCNnF2-F1≥2，所以F2-F1≥4. 因?yàn)镕1和F2是HCNn的2-好鄰條件故障集，且VHCNn-F1-F2不含孤立點(diǎn)，所以在VHCNn-F1-F2與F1ΔF2之間沒有邊，因此F1∩F2是2-好鄰條件故障集。由引理7可知κ2HCNn=4n-4.所以F1∩F2≥4n-4.因此F2=F2-F1+F1∩F2≥4n，與假設(shè)F2≤4n-1矛盾。

所以當(dāng)g=2，n≥3時(shí)，HCNn在MM*模型下的2-好鄰條件診斷度，t2HCNn≥4n-1.

證畢。

結(jié)合引理14和引理15，我們可以得到分層立方網(wǎng)絡(luò)HCNn在MM*模型下的2-好鄰條件診斷度。

定理16 當(dāng)n≥3時(shí)，分層立方網(wǎng)絡(luò)HCNn在MM*模型下的2-好鄰條件診斷度t2HCNn=4n-1.

[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] MAENG J，MALEK M. A comparison connection assignment for self-diagnosis of multiprocessor system[C].//Proceeding of 11th International Symposium on Fault-Tolerant Computing，1981;173-175.

[3] 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:165-175.

[4] 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.

[5] LIN L M，XU L，ZHOU S M. Relating the extra connectivity and the conditional diagnosability of regular graphs under the comparison model[J]. Theoretical Computer Science，2016，618:21-29.

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

[7] GJPSE K，DESAI K R. Hierarchical cubic network[J]. IEEE Transactions On Parallel and Distributed System.1995，6:427-435.

[8] ZHOU S M，SONG S L，YANG X X，et al. On conditional fault tolerance and diagnosability of hierarchical cubic networks[J].Theoretical Computer Science，2016，609:421-433.

[9] SENGUPTA A，DAHBURA A. On self-diagnosable multiprocessor system:Diagnosis by the comparison approach[J]. IEEE Transaction on Computers，1992，11:1386-1396.

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

Theg-good-neighborConditionalDiagnosabilityofHierarchicalCubicNetworksUnderMM*Model

ZHAO Yi, YUAN Jun

(School of Applied Sciences, Taiyuan University of Science and Technology, Taiyuan 030024, China)

Diagnosability has an important effect on the reliability of an interconnection network, and the diagnosability of many well-known networks has been explored. Theg-good-neighbor conditional diagnosability is the popularization of the classical diagnosability. It restricts every healthy vertex and has at leastgfault-free neighboring vertices. In this paper, we show that theg-good-neighbor conditional diagnosability ofHCNnunder the MM*model is 2n+1，4n-1 respectively forg=1,g=2 .

fault diagnosis, MM*model, hierarchical cubic networks, conditional diagnosability,g-good-neighbor conditional diagnosability

1673-2057(2018)01-0063-06

2016-08-22

國家自然科學(xué)基金(61402317)；國家數(shù)學(xué)天元基金(11126076)；山西省青年自然科學(xué)基金(2012021001-2)

趙昳(1991-)，女，碩士研究生，主要研究方向?yàn)閳D論及泛函分析。

O157.5

A

10.3969/j.issn.1673-2057.2018.01.012