ABSTRACT

Nowadays, diagnosability is an important research topic and parameter in measuring the fault diagnosis of multiprocessor systems. In 2012, Peng et al. proposed a new measure for fault diagnosis of the system, which was called g-good-neighbor diagnosability that restrained every fault-free node containing at least g fault-free neighbors. The n-dimensional augmented k-ary n-cube is an important variant of the hypercube. In this paper, we prove that the 1-good-neighbor diagnosibility of augmented k-ary n-cubes under the PMC model and the MM* model is for,.

Keywords:Interconnection Network, Graph, Diagnosability, PMC Model, MM* Model, Augmented k-Ary n-Cubes

扩展k元n立方体的1-好邻诊断度

郝燕丽¹，王世英^1,2*

¹河南师范大学数学与信息科学学院，河南 新乡

²河南师范大学，河南省大数据统计分析与优化控制工程实验室，河南 新乡

收稿日期：2016年11月9日；录用日期：2016年11月25日；发布日期：2016年11月30日

摘 要

现如今，一个多重处理器系统的诊断度是一个非常重要的研究课题，它是度量多重处理器系统故障诊断能力的重要参数。2012年，Peng等人提出了一个新的系统故障诊断方法，称为g好邻诊断度，它限制每个非故障顶点至少有g个非故障邻点。n维扩展k元n立方体是超立方体的一个重要变形。在本文中，我们证明了扩展k元n立方体在PMC模型下和MM*模型下的1-好邻诊断度是。

关键词 :互连网络，图，诊断度，PMC模型，MM*模型，扩展k元n立方体

1. 引言

大部分的多重处理器系统都以互联网络作为基本的拓扑结构并且通常用图来表示一个互联网络，其中的顶点代表处理器，边代表处理器之间的通信线路。我们用图和网络互换。对于多重处理系统来说，其网络拓扑性质的研究是非常重要的。诊断度是度量多处理器系统故障诊断能力的重要参数，它们是互联网络中热门的研究课题之一。此外，在系统中，一些处理器可能是故障的。所以，为了保证计算机系统的可靠性，系统中的故障处理器应该被诊断出来。处理故障系统的第一步是从非故障处理器识别故障处理器。识别过程被称为系统诊断。在没有更换的前提下，如果所有故障处理器都可以被识别，并且被诊断出的故障处理器个数不超，那么这个系统称为-可诊断。系统的诊断度是所有-可诊断中的最大值 [1] [2] 。为了测量多重处理系统的诊断度，很多诊断模型已经被提出。尤其是PMC模型 [3] 和MM*模型 [4] ，这两个模型被广泛使用。PMC模型是通过两个相邻的处理器之间相互测试来完成系统的诊断。MM*模型下，一个顶点分别给它相邻的两个顶点发出相同的任务，然后比较它们反馈的结果。在PMC模型和MM*模型下已经有无数的研究 [5] [6] 。

传统的诊断度允许点的邻点全为故障点，但是在大型多处理器系统中这种故障出现的概率极小。因此Lai [2] 等提出了系统的条件诊断度，它限制系统中任意一个处理器至少与一个非故障处理器相邻。近些年，Peng [7] 等提出了系统的g-好邻诊断度，它限制每个非故障顶点都至少有g个非故障邻点与之相邻，并且研究了超立方体在PMC模型下的g好邻诊断度。随后，很多学者在PMC模型和MM*模型下研究了更多网络的g-好邻诊断度 [6] [8] [9] 。作为一个良好的互连网络拓扑结构，扩展k元n立方体有许多好的性质。在文献 [10] 中，王牟江山等证明了网络的1-好邻诊断不超过条件诊断度。因此，研究网络的1-好邻诊断度也是很有意义的。近些年来，扩展k元n立方体 [11] 被Xiang和Stewart提出应用与并行运算。在本文中，我们采用PMC模型和MM*模型作为故障诊断模型，来研究扩展k元n立方体在PMC模型和MM*模型下的1-好邻诊断度，最后得出扩展k元n立方体在PMC模型和MM*模型下的1-好邻诊断度。

2. 预备知识

在这一节，我们将介绍一些基本概念、符号、PMC模型、MM*模型及扩展k元n立方体。

2.1. 基本概念及符号说明

我们用一个无向简单图是来表示一个多重处理系统，其中，分别表示网络中的处理器和处理器之间的连接。对于任意的非空顶点子集，则以两端点均在中的边的全体为边集所组成的子图，称为在中的导出子图，记作。是指中与关联边的数目，和分别表示中顶点的最小度和最大度。对于中任意一个顶点，都有，则称图是正则的。对于任意，表示中与相邻的所有顶点组成的集合。若，则。定义。对于任意两点，表示中与均相邻的点的个数，也即为。

对于任意的一个故障集，若对于每一个非故障点均有，则称为的g-好邻故障集。如果不连通且为的g-好邻故障集，则称是一个g-好邻割。的g-好邻连通度等于中最小g-好邻割所含的顶点数，记作。文中其它未定义而直接使用的符号和术语参见文献 [12] 。

2.2. PMC模型和MM*模型

在PMC模型 [3] 中，相邻两点之间可以相互测试。图中，对于任意的表示从到的测试，其中是测试者而是被测试者。若是非故障点而是故障点(或非故障点)，则测试结果是1 (或0)。在PMC模型中，我们假定，若测试点是非故障点，则测试结果可靠。否则，测试结果不可靠。它可以用一个有向图表示,其中表示。所有测试结果的集合称为系统的症候，记作。一个症候是一个函数。

1) 若，，；

2) 若，。

对两不同的顶点子集，若，则称和是可区分的，记为可区分的点对;否则，称和是不可区分的，记为不可区分的点对。

在MM*模型下，与一个结点相邻的两个结点，被分配一个相同的任务，再把测试结果返回给结点，再对这两个结点返回的结果进行比较。用来表示比较,输出的比较结果，如果这两个结果是相同的，则；否则，。全部的测试结果叫做这个系统的比较症候，记作。

1) 若，，；

2) 若，，；

3) 若，。

在一个系统中，对于任意两个不同的g好邻故障集，，其中和，若,是可区分的，则是g-好邻条件t-可诊断的。的g好邻诊断度是使得是g-好邻条件t-可诊断的最大值。

2.3. 扩展k元n立方体

扩展k元n立方体一直被称为著名的拓扑结构。在文献 [11] 中，作者介绍了如下的定义和一些有用的性质。

定义1扩展k元n立方体的顶点集为，两个顶点，相邻当且仅当满足以下条件之一。

1) (或者)，且；则称为-边(或者-边)。

2) (或者)，且；则称为-边(或者-边)。

性质1 当时，是点传递的，且。

性质2表示由中顶点的第位都是的顶点生成的子图，且。

性质3 如果，分别是的一条-边和-边，则：

1) 当且时

；

.

2) 当且时

；

；

。

3) 当且时

；

；

；

。

4) 当且时

；

；

；

。

对于-边和-边，这个结果也是类似的。

性质4 当时，且均为整数，设是中任意两个不同的点，则有：

1) 当时，；

2) 当时，；

3) 当时，。

3. 扩展k元n立方体在PMC模型下的1-好邻诊断度

在这一节，我们将证明扩展k元n立方体在PMC模型下的1-好邻诊断度。

在一个系统中，对于中任意两个不同的子集，，我们定义对称差。Yuan [6] 提出了一个系统在PMC模型下是g-好邻t-可诊断的充分必要条件。

定理3.1 一个系统在PMC模型下是g-好邻t-可诊断的当且仅当对于中任意两个不同的g-好邻故障集，及其和，存在和，使得(如图1)。

引理3.2 最小度为1的图至少有两个顶点。

引理3.3 [13] 当时，扩展k元n立方体的1-好邻连通度。

引理3.4 当时，设，，，，，则，，，。

证明：由性质4(3)，当时，，其中，是中任意两个不同的点。设，显然，相邻，所以，，同时由图2可知：

，因此达到了最大。

则，。

首先，我们先证明。

对任意的，由性质4可知：当时，，。因此，。于是，当，。所以，当时，。由于有2部分：，。注意到，又因为。所以，。

引理3.5 当时，扩展k元n立方体的在PMC模型下的1好邻诊断度。

证明 令，，由引理3.4定义(如图3)。由引理3.4可知：，，，。因此，和都是的1-好邻故障集。因为，，且和之间没有边。由定理3.1，我们可知在PMC模型下

图1. 在PMC模型下可区分

图2. u和v的全部邻点

图3. 关于引理3.5和4.2的证明

不是1-好邻-可诊断的。所以，根据1-好邻诊断度的定义，我们可知在PMC模型下的1好邻诊断度小于，也即为。

引理3.6 当时，扩展k元n立方体在PMC模型下的1好邻诊断度。

证明 根据1好邻诊断度的定义，需要证明是1-好邻-可诊断的。根据定理3.1，等价于证明任意两个不同的1-好邻故障集，，其中和，存在和，使得。

反证法。假设存在两个不同的1-好邻故障集，，其中和，对任意的和，使得。不失一般性，假设。分以下两种情况进行讨论：

情形1。

。当时，上述不等式矛盾。

情形2。

根据假设与之间没有边和是1-好邻条件故障集，由于由于有2部分：，。因此可得和。同理，当，。所以，也是1-好邻条件故障集。又因为与之间没有边，所以是的1-好邻割。根据引理3.3，可得。根据引理3.2，可得。因此，。这与相矛盾。

由于以上两种情况都产生矛盾，故是1-好邻-可诊断的。于是，。

结合引理3.5和引理3.6，可得以下定理：

定理3.7 当时，扩展k元n立方体在PMC模型下的1-好邻诊断度。

4. 扩展k元n立方体在MM*模型下的1-好邻诊断度

定理4.1 [7] 一个系统在MM*模型下是好邻t-可诊断的当且仅当对于中任意两个不同的g-好邻故障集，及其和，满足以下其中一个条件(如图4)：

1) 存在和满足。

2) 存在和满足。

3) 存在和满足。

引理4.2 当时，扩展k元n立方体在MM*模型下的1-好邻诊断度。

证明 令，，由引理3.4定义(如图3)。由引理3.4可知：，，，。因此，和都是的1-好邻故障集。由和的定义可知：，由于，和，因此不满足定理4.1中的(1)~(3)。所以，不是1-好邻条件可诊断的。故。

图4. 在MM*模型下可区分

引理4.3 当时，扩展k元n立方体在MM*模型下的1-好邻诊断度。

证明 根据1-好邻诊断度的定义，只需要证明是是1-好邻条件可诊断的。用反证法证明。根据定理4.1，假设中存在两个不同的g-好邻故障集，及其和，但不满足定理4.1中的(1)~(3)。不失一般性，假设。类似于在引理3.6对讨论可知：

断言1 没有孤立点。

反证法。假设至少有一个孤立点。因为是一个1-好邻故障集，所以至少存在一点使得。因为不满足定理4.1中的(1)~(3)，所以至多存在一点使得。因此仅有一点使得。同理，如果，那么。因为是一个1-好邻故障集，所以有，这与是一个孤立点矛盾。因此，我们可以得到点。同理可知，仅有一点使得。设是中的孤立点集，。因此，对任意的，存在个邻点在中。由于，故。因为，所以。假设，由于因此，。显然，当时，这是矛盾的。因此。因为顶点对不满足定理4.1中的(1)~(3)且中任意一点都不是孤立点，所以我们可以得到与之间没有边。因此，是的点割。由于和是的1-好邻故障集，因此，和是的一个1-好邻割。根据引理3.4，。因为和，且和，所以。于是，不妨设和。故对于任意的满足。根据性质4，当时，中任意一对顶点至多有四个公共邻点。因此，至多有四个孤立点，即为。

情形1。

设，则。因为包含三圈，所以需要进一步讨论是否相邻。

情形1.1相邻。

，，。根据性质4，当时，中任意一对顶点至多有四个公共邻点。因此，，，，则

于是，与矛盾。

情形1.2不相邻。

，，。根据性质4，当时，中任意一对顶点至多有四个公共邻点。因此，，，，则

于是，与矛盾。

情形2 。

设，则。因为包含三圈，所以需要进一步讨论是否相邻。

情形2.1相邻。

，，，。根据性质4，当时，中任意一对顶点至多有四个公共邻点。因此，，，，，，，

则

于是，与矛盾。

情形2.2不相邻。

，，，。根据性质4，当时，中任意一对顶点至多有四个公共邻点。因此，，，，，，，

则

于是，与矛盾。

情形3。

设，则。

，，。根据性质4，当时，中任意一对顶点至多有四个公共邻点。因此，，，，则 。

于是，与矛盾。

情形4。

设，则。

，，，。根据性质4，当时，中任意一对顶点至多有四个公共邻点。因此，，，，，，，

则

于是，与矛盾。

若，则。因为是一个1-好邻故障集，所以没有孤立点。断言1证明完毕。

设。根据断言1，在中至少有一个邻点。因为顶点对不满足定理4.1的任何一个条件，根据定理4.1(1)，所以对于任意一对相邻的点，不存在使得和。因此，在中没有邻点。根据的任意性，与中间没有边。由于，是一个1-好邻故障集，所以。根据引理3.2，。因为和都是1-好邻故障集且与之间没有边，所以是的一个1-好邻割。根据引理3.3，。因此，。这与矛盾。于是，是一个1-好邻-可诊断的。故。

由引理4.2和引理4.3可得以下定理：

定理4.4 当时，扩展k元n立方体在MM*模型下的1-好邻诊断度。

5. 结束语

诊断度是互联网络容错的重要指标，本文研究了扩展k元n立方体在PMC模型下和MM*模型下的1好邻诊断度，这项工作将帮助工程师可根据应用环境、网络拓扑结构、网络的可靠性和故障模式的相关统计开发更多不同的测量1-好邻诊断度的措施。

文章引用

郝燕丽,王世英. 扩展k元n立方体的1-好邻诊断度
The 1-Good-Neighbor Diagnosability of Augmented k-Ary n-Cubes[J]. 应用数学进展, 2016, 05(04): 762-772. http://dx.doi.org/10.12677/AAM.2016.54088

参考文献 (References)