Advances in Applied Mathematics
Vol.05 No.04(2016), Article ID:19119,8 pages
10.12677/AAM.2016.54087

The 1-Good-Neighbor Diagnosability of Augmented 3-Ary n-Cubes

Nan Zhao1, Shiying Wang1,2*

1School of Mathematics and Information Science, Henan Normal University, Xinxiang Henan

2Henan Engineering Laboratory for Big Data Statistical Analysis and Optimal Control, Henan Normal University, Xinxiang Henan

Received: Nov. 10th, 2016; accepted: Nov. 26th, 2016; published: Nov. 30th, 2016

Copyright © 2016 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

ABSTRACT

Diagnosability of a multiprocessor system is an important study topic. The g-good-neighbor diagnosability of the system was proposed by Peng et al. in 2012, which restrained every fault-free node containing at least g fault-free neighbors. As a favorable topology structure, the augmented 3-ary n-cubes graph has many good properties. In this paper, we prove that the 1-good-neighbor diagnosability of augmented 3-ary n-cube is under the PMC model and MM* model for.

Keywords:Interconnection Network, Augmented 3-Ary -Cubes, Connectivity, Diagnosability

扩张3元n立方的1好邻诊断度

赵楠1,王世英1,2*

1河南师范大学数学与信息科学学院,河南 新乡

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

收稿日期:2016年11月10日;录用日期:2016年11月26日;发布日期:2016年11月30日

摘 要

多重处理器系统的故障诊断是一个非常重要的研究课题。处理器系统的g好邻诊断度是在2012年被Peng等提出来的,它要求每个非故障顶点至少有g个非故障邻点。扩张3元n立方体是一个受欢迎的拓扑结构,它有许多好的性质。在本文中,我们证明了扩张3元n立方体在PMC模型和MM*模型下的1好邻诊断度都是

关键词 :互连网络,扩张3元n立方,连通度,诊断度

1. 引言

诊断度是多处理器系统故障分析的一个重要参数。它在衡量互联网络可靠性方面有着重要作用。在1997年,Preparata [1] 等首次提出了系统诊断度理论。它的优点在于能够自动地检测系统中的处理器。系统级故障理论的研究依赖于模型的建立,因此许多模型被提出。例如Preparat [1] 等提出了PMC模型;Maeng和Malek [2] 提出了MM*模型。在2005年,Lai [3] 等考虑到在一个系统中,某个处理器的所有与之相邻的处理器同时发生故障的概率很小,故而对传统诊断理论做了改进,提出了条件诊断度,它要求系统中每个处理器至少与一个非故障处理器相连。在2012年,Peng [4] 在条件诊断度的基础上,进一步提出了好邻条件诊断度。它要求每个非故障处理器至少与个非故障处理器相邻,并且证明了超立方

体在PMC模型下的好邻诊断度是。原军等在 [5] [6] 中分别证明了立方体在PMC模型下的好邻诊断度是和3元立方体在PMC模型和MM*模型下的好邻诊断度是(是偶数)和(是奇数)。在 [7] [8] 中,王牟江山等研究了在PMC模型和MM*模型下的好邻诊断度,

此时。在 [9] 中,王世英和韩威萍研究了维超立方体在MM*模型下的好邻诊断度。近些年来,许多基于超立方体的变形网络图被提出,例如,交叉立方体,分层立方网络,立方网络等,它们较之超立方体有着更好的拓扑性质,因此在某些领域更受青睐。在本文中,我们主要证明了在时,扩展3元立方网络图在PMC模型和MM*模型下的1好邻诊断度均为

2. 预备知识

2.1. 符号

我们用一个无向简单图来表示多重处理器系统,其中是图的顶点集,一个顶点代表了一个处理器,是图的边集,它表示了处理器之间的连接关系。对于任意的非空顶点子集,以为顶点集,以两端点均在中的边的全体为边集所组成的子图,称为中的导出子图,记作是顶点中关联的边的数目,表示中的度。表示的顶点的最小度。对于任意顶点,在中与相邻的所有顶点组成的集合称为的邻集,记作。若

的非空顶点子集,则的邻集为。对,令

。图被叫做-正则的,是指它的任意一点都有。对

于任意的,若中至少有个邻点,则称好邻故障集。如果不连通且的每个连通分支的最小度为,则称是一个好邻割。的所有好邻割中的最小顶点数称为好邻连通度,记作

在PMC模型中,相邻的处理器之间可以相互测试。图中,对于任意的表示用测试,其中是测试者,而是被测试者。若是非故障点而是故障点(或非故障点),则测试结果是1 (或0)。若是故障点,则测试结果不可靠。

在MM*模型下,一个结点同时向与它相邻的两个结点发出一个相同的测试任务,再把测试结果返回给结点会对返回的结果进行比较。用来表示,进行测试的比较结果。如果这两个结果是相同的,则;否则,。若是故障的,则测试结果无论是0或1都是不可靠的。

2.2. 扩展k元n立方体

。在 [10] 中,作者给出了扩展立方的两个定义。

定义 1 [10] 令是整数,扩展立方点,每个点用一组维字符串表示,即,其中。如果相邻当且仅当满足下列条件中的一个:

1) (或),对,而,对,那么这种边被称为一条边(或边);

2) 存在某个 (或),,对所有的成立,则这种边被叫做边(或边)。

扩展立方也可以按照如下定义。

定义 2 [10] 令,扩展元1立方的顶点集为相邻当且仅当或者。令,扩展立方是由个扩展立方构成的,其中第中的点的第位皆为一个固定的数。且对,点将增加四条边,即边,边,边,边。

引理 1 [10] 令为扩展立方,且是整数。

1) 对,由第位是的所有点构成的的导出子图,被定义为,它同构与

2)是点传递的,是边传递的,而且

3)之间的边组成的集合被定义为,并且

4) 令 (其中),那么

为了方便,我们采用下面的方法来表示一个点在中的邻点。令。 那么,的邻点分别是:当,或; 当,或

引理2 [11] 如果的一条边,的一条边,那么下列条件成立:

1) 当时,

2) 当

如果

如果

3) 当

如果,那么

如果,那么

如果,那么

如果,那么

4) 当

如果,那么

如果,那么

如果,那么

如果,那么

引理3 [11] 令是扩展立方, 其中均为整数。令中的两个不同的点,那么:

1),当

2),当

3),当

引理4 [11] 令是扩展3元立方,当时,的1好邻连通度

3.在PMC模型下的1好邻诊断度

定理1 [12] 一个系统在PMC模型下是好邻-可诊断的当且仅当对于中任意两个不同的顶点数至多为好邻故障集,存在,使得(如图1)。

Figure 1. A distinguishable pair under the PMC model

图1. 在PMC模型下可区分对

引理5 [11] 当时,对任意的,若相邻,则有;若不相邻,则有

引理6 当时,设,那么有,且

证明 因为,所以。又因为,所以。根据引理5知,中的公共邻点数达到最大。又因为,所以

下面我们证明

任取,根据引理5,任意一对不相邻的顶点至多有6个公共邻点,即。因此,。又因为,所以当时有。于是有当

有两个部分:。因为,所以

引理7 当时,在PMC模型下的1好邻诊断度

证明 令集合的定义与引理6相同,。根据引理6,。因此,的1好邻故障集。因为,所以在中,不存在从的边。根据定理1,不是1好邻-可诊断的。因此,

引理8 当时,在PMC模型下的1好邻诊断度

证明 由1好邻诊断度的定义,我们只需要证明是1好邻-可诊断的。根据定理1,等价于证明对于任意两个不同的好邻故障集,其中,存在,使得。反证法。假设是两个不同的1好邻故障集,并且。但是这个点集对不满足定理1的任何条件。不失一般性,我们假设。如果,那么,这显然与矛盾。因此,。然后由于从没有边和的一个1好邻故障集,所以。同理,若,那么。由于从没有边,所以是一个1好邻割。根据引理4,有。又因为,所以,这显然是矛盾的。因此是1好邻-可诊断的,即

定理2在PMC模型下的1好邻诊断度

4.在MM*模型下的1好邻诊断度

定理3 [12] 一个系统在MM*模型下是好邻-可诊断的当且仅当对中任意两个不同的顶点数至多为好邻故障集,满足以下其中一个条件(如图2)。

Figure 2. A distinguishable pair under the MM* model

图2. 在MM*模型下可区分对

1) 存在满足

2) 存在满足

3) 存在满足

引理9 当时,在MM*模型下的1好邻诊断度

证明 令集合的定义与引理6相同,。根据引理6,。因此,好邻故障集。因为,所以在中,不存在从的边。根据定理1,不是1好邻-可诊断的。因此,

引理10 当时,在MM*模型下的1好邻诊断度

证明 根据1好邻诊断度的定义,需要证明是1好邻-可诊断的。反证法。根据定理3,假设是两个不同的1好邻故障集,并且。但是这个点集对不满足定理3的任何一个条件。不失一般性,我们假设。按照下面的情况进行讨论:

情形1

因为,所以,这显然与矛盾。因此,

情形2

断言1没有孤立点。

反证法。假设至少有一个孤立点。因为是一个1 好邻故障集,所以至少存在一点使得。因为不满足定理3中的(3),所以至多存在一点使得。因此仅有一点使得。如果时,那么。因为是一个1好邻故障集,所以,这与是一个孤立点矛盾。因此,。类似地,我们可以断定仅有一点使得。设中的孤立点集,。对任意的,在中有个邻点。因为,所以可得。假设,那么,这显然与矛盾。所以,。因为不满足定理 3中的(1)且的任意一点在中不是孤立点,所以之间不存在边相连。因此,的一个点割且,即的一个1好邻割。由引理4知,。因为都非空,所以。再根据引理3,即任意一对不相邻的顶点至多有6个公共邻点,所以,。于是,我们来考虑下面三种情况:

情形2.1

。因为,所以我们来考虑中的邻点个数。不失一般性,令。由引理2和3知,中任意两点在中的公共邻点个数分别为:。又因为均有邻点在中,所以。因此,。而这与矛盾。所以

情形2.2

。因为,所以我们来考虑中的邻点个数。由引理2和3知,中任意两点在中的公共邻点数分别为:。又因为均有邻点在中。所以,。因此,。而这与矛盾。所以

情形2.3

。由引理2和3知,中任意两点在中的公共邻点数分别为:。又因为邻点在中,各有邻点在中,所以,。因此,。这与矛盾。所以,。断言1证明完毕。

,根据断言1,中至少有一个邻点。因为不满足定理3,根据定理3的(3),所以中没有邻点。因为中间没有边和是一个1好邻故障集,所以。又因为中间没有边,所以的一个1好邻割。根据引理4,。由于,那么,,矛盾。因此,是1好邻-可诊断的。故

结合引理9和引理10可得以下定理:

定理4在MM*模型下的1好邻诊断度

5. 结束语

在这篇文章中,我们研究了扩展3元立方在PMC和MM*模型下的1好邻诊断度。我们证明了当时,扩展3元立方在PMC和MM*模型下的1好邻诊断度都是。这为今后进一步研究扩展3元立方网络的好邻连通度、诊断度和相关诊断算法提供了理论基础。

基金项目

国家自然科学基金资助项目(61370001),教育部博士点基金(博导类)资助项目(20111401110005)。

文章引用

赵楠,王世英. 扩张3元n立方的1好邻诊断度
The 1-Good-Neighbor Diagnosability of Augmented 3-Ary n-Cubes[J]. 应用数学进展, 2016, 05(04): 754-761. http://dx.doi.org/10.12677/AAM.2016.54087

参考文献 (References)

  1. 1. Preparata, F., Metze, G. and Chien, R.T. (1968) On the Connection Assignment Problem of Diagnosable Systems. IEEE Transactions on Electronic Computers, 12, 848-854.

  2. 2. Joon, M. and Miroslaw, M. (1981) A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor Systems. Proceeding of 11th International Symposium on Fault-Tolerant Computing, Portland, June 1981, Vol. 11, 173-175.

  3. 3. Lai, P.-L., Tan, J.J.M., Chang, C.-P. and Hsu, L.-H. (2005) Conditional Diagnosability Measures for Large Multiprocessor Systems. IEEE Transactions on Computers, 54, 165-175. https://doi.org/10.1109/TC.2005.19

  4. 4. Peng, S.-L., Lin, C.-K., Tan, J.J.M. and Hsu, L.-H. (2012) The g-Good-Neighbor Conditional Diagnosability of Hypercube under the PMC Model. Applied Mathematics and Computation, 218, 10406-10412. https://doi.org/10.1016/j.amc.2012.03.092

  5. 5. Yuan, J., Liu, A.X., Ma, X., Liu, X.L., Qin, X. and Zhang, J.F. (2015) The g-Good-Neighbor Conditional Diagnosability of k-Ary n-Cubes under the PMC Model and MM* Model. IEEE Transactions on Pa-rallel and Distributed Systems, 26, 1165-1177. https://doi.org/10.1109/TPDS.2014.2318305

  6. 6. Yuan, J., Liu, A.X., Qin, X., Li, J. and Zhang, J.F. (2016) The g-Good-Neighbor Conditional Diagnosability of 3-Ary n-Cubes under the PMC Model and MM* Model. Theoretical Computer Science, 622, 144-162.

  7. 7. Wang, M., Lin, Y.Q. and Wang, S.Y. (2016) The 2-Good-Neighbor Diagnosability of Cayley Graphs Generated by Transposition Trees under the PMC Model and MM* Model. Theoretical Computer Science, 628, 92-100. https://doi.org/10.1016/j.tcs.2016.03.019

  8. 8. Wang, M., Guo, Y.B. and Wang, S.Y. (2015) The 1-Good-Neighbor Diagnosa-bility of Cayley Graphs Generated by Transposition Trees under the PMC Model and MM* Model. International Journal of Computer Mathematics, 1-12. https://doi.org/10.1080/00207160.2015.1119817

  9. 9. Wang, S.Y. and Han, W.P. (2016) The g-Good-Neighbor Conditional Diagnosability of n-Dimentional Hypercubes under the PMC Model and MM* Model. International Processing Letters, 116, 574-577. https://doi.org/10.1016/j.ipl.2016.04.005

  10. 10. Xiang, Y.L. and Stewart, L.A. (2011) Augmented k-Ary n-Cubes. Information Science, 181, 239-256. https://doi.org/10.1016/j.ins.2010.09.005

  11. 11. Lin, R.Z. and Zhang, H.P. (2015) The Restricted Edge-Connectivity and Restricted Connectivity of Augmented k-Ary n-Cubes. International Journal of Computer Mathematics, 93, 1281-1298. https://doi.org/10.1080/00207160.2015.1067690

  12. 12. Dahbura, A.T. and Masson, G.M. (1984) An Fault Identification Algorithm for Diagnosable Systems. IEEE Transactions on Computers, 33, 486-492. https://doi.org/10.1109/TC.1984.1676472

*通讯作者。

期刊菜单