趙 昳，原 軍

(太原科技大學 應用科學學院，太原 030024)

分層立方網絡在MM*模型下的g好鄰條件診斷度

趙 昳，原 軍

(太原科技大學 應用科學學院，太原 030024)

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

故障診斷；MM*模型；分層立方網絡；條件診斷度；g好鄰條件診斷度

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

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

Lai[3]等對已有的診斷度條件進行了改進，要求所有頂點的鄰點都不能同時發(fā)生故障，提出了條件診斷度的概念。類似地，Peng[4]等通過對系統中非故障結點的鄰點集的故障條件進行限制，使得每個非故障頂點至少有g個非故障鄰點，提出了g好鄰條件診斷度。 隨著互連網絡拓撲結構的不斷發(fā)展，許多以超立方體網絡為基礎的變形網絡也隨之產生，比如，交叉立方體，扭立方體，分層立方網絡，這些變形網絡比超立方體有更好的拓撲性質。在本文中，采用MM*模型作為系統故障診斷模型，研究并得出了分層立方網絡在MM*模型下g時的G好鄰條件診斷度。

1 基本概念及符號說明

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

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

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

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

(4)給定同樣任務和輸入的兩個故障處理器不能產生同樣的輸出結果。

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

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

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

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

定理3 設F1和F2是G中任意兩個不同的頂點子集，且F1≤t，F2≤t. 則G是t-可診斷的當且僅當F1和F2是可區(qū)分的。

下面給出分層立方網絡的定義。

定義4 分層立方網絡HCNn中兩個結點u=x,y和v=w,z是相連的，當且僅當恰好以下三個條件之一成立：

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

(3)x=z且y=w.

引理57分層立方網絡HCNn有如下基本性質：

HCNn的正則度為n+1；HCNn點連通度為n+1.

引理68當n≥3時，分層立方網絡HCNn的R1連通度κ1HCNn=2n.

圖1 分層立方網絡HCN2

引理78當n≥3時，分層立方網絡HCNn的R2連通度κ2HCNn=4n-4.

2 主要結果

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

定理99設F1和F2是G中任意兩個不同的頂點子集，則在MM*模型下，F1和F2是可區(qū)分的當且僅當滿足下面三個條件之一：

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

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

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

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

定理10 設F1和F2是G中任意兩個不同的g好鄰條件故障集，且F1≤t，F2≤t，則在MM*模型下，系統G是g好鄰條件t-可診斷的當且僅當滿足下列三個條件之一：

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

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

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

引理11 當n≥3時，分層立方網絡HCNn在MM*模型下的1-好鄰條件診斷度t1HCNn≤2n+1.

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

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

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

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

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

情況1VHCNn=F1∪F2.

由VHCNn=F1∪F2,

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

情況2VHCNn≠F1∪F2

首先給出一個斷言。

斷言HCNn-F1-F2不含孤立點。

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

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

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

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

設v為孤立點，則在VHCNn-F1-F2中，v與v1，v2相鄰。顯然，NHCNnv-v1,v2?F1∩F2，因為分層立方網絡是無三角圖，所以NHCNnv1-v?F1∩F2，NHCNnv2-v?F1∩F2，NHCNnv-v1,v2∩NHCNnv1-v=?,NHCNnv-v1,v2∩NHCNnv2-v=?. 由于在HCNn中任意兩個頂點至多有兩個公共鄰點，故NHCNnv1-v∩NHCNnv2-v≤1. 因此，F1∩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矛盾。

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

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

定理13 當n≥3時，分層立方網絡HCNn在MM*模型下的1-好鄰條件診斷度t1HCNn=2n+1.

引理14 當n≥3時，分層立方網絡HCNn在MM*模型下的2-好鄰條件診斷度t2HCNn≤4n-1.

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

引理15 當n≥3時，分層立方網絡HCNn在MM*模型下的2-好鄰條件診斷度t1HCNn≥4n-1.

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

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

情況1VHCNn=F1∪F2.

因為n≥3，VHCNn=F1∪F2

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

情況2VHCNn≠F1∪F2

首先給出一個斷言。

斷言HCNn-F1-F2不含孤立點。

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

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

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

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

證畢。

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

定理16 當n≥3時，分層立方網絡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].太原科技大學學報，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

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

趙昳(1991-)，女，碩士研究生，主要研究方向為圖論及泛函分析。

O157.5

A

10.3969/j.issn.1673-2057.2018.01.012