分层立方网络在MM*模型下的g好邻条件诊断度

赵 昳，原 军

(太原科技大学 应用科学学院，太原 030024)

分层立方网络在MM*模型下的g好邻条件诊断度

赵 昳，原 军

(太原科技大学 应用科学学院，太原 030024)

诊断度在衡量互联网络可靠性方面有着重要的作用。许多著名网络的诊断度已被研究。g好邻条件诊断度扩展了传统诊断度的概念，它要求每个非故障处理器至少有g个非故障邻点。本文证明了分层立方网络HCNn在MM*模型下的1-好邻条件诊断度为2n+1，2-好邻条件诊断度为4n-1.

故障诊断；MM*模型；分层立方网络；条件诊断度；g好邻条件诊断度

随着技术的发展，为了获得更好的运行效果，系统规模在逐渐扩大。同时系统中的元件出现故障的可能性增大，这对系统的可靠性产生了不利的影响。因此，及时发现并替换掉这些故障元件变的尤为重要。

1967年，Preparata[1]等提出了系统级故障诊断理论，它能够自动的检测系统中的处理器。系统级故障诊断理论的研究依赖于测试模型的建立，许多测试模型已被提出。比较模型(MM模型)是一种重要的系统级故障诊断模型，它是由Maeng和Malek[2]共同提出来的。MM诊断模型是由某个处理机向它的两个相邻处理机发出相同的的测试任务，通过比较两个被测试者在同一特定输入下的运算结果来判断它们的故障情况。MM*模型是MM的一种特殊情况，在该模型下，每个结点机均对与它有直接物理连线相连的任意两个不同结点机的运算结果进行比较。

Lai[3]等对已有的诊断度条件进行了改进，要求所有顶点的邻点都不能同时发生故障，提出了条件诊断度的概念。类似地，Peng[4]等通过对系统中非故障结点的邻点集的故障条件进行限制，使得每个非故障顶点至少有g个非故障邻点，提出了g好邻条件诊断度。 随着互连网络拓扑结构的不断发展，许多以超立方体网络为基础的变形网络也随之产生，比如，交叉立方体，扭立方体，分层立方网络，这些变形网络比超立方体有更好的拓扑性质。在本文中，采用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是可区分的，t为可区分的点对；否则，称G和t是不可区分的，t为不可区分的点对。

定义1 若系统G中，故障处理器的个数不超过t，所有的故障处理器通过一次测试全部被正确识别出来，就称G是t-可诊断的。在所有使得G是t-可诊断的数中，最大数t称为G的诊断度，记为tG.

定义2 若G中任意两个顶点数至多为t的g好邻条件故障集F1，F2都是可区分的，则称G是g好邻条件t-可诊断的。 使得G是g好邻条件t-可诊断的最大值t称为G的g好邻条件诊断度，记作tgG.

定理3 设F1和F2是G中任意两个不同的顶点子集，且F1≤t，F2≤t. 则G是t-可诊断的当且仅当F1和F2是可区分的。

下面给出分层立方网络的定义。

定义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是否可区分的充要条件。

定理99设F1和F2是G中任意两个不同的顶点子集，则在MM*模型下，F1和F2是可区分的当且仅当满足下面三个条件之一：

(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是不可区分的。

所以F1和F2是1-好邻条件故障集。

由于F1和F2是不可区分的，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都是可区分的。

假设HCNn中存在这样的两个1-好邻条件故障集F1和F2，它们是不可区分的，并且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是不可区分的，且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都是可区分的。

假设HCNn中存在这样的两个2-好邻条件故障集F1和F2，它们是不可区分的，并且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