Advances in Applied Mathematics
Vol.05 No.04(2016), Article ID:19087,10 pages
10.12677/AAM.2016.54084

The 1-Good-Neighbor Connectivity and Diagnosability of Möbius Cubes

Can Bai1, Shiying Wang1,2*, Zhenhua Wang1

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. 25th, 2016; published: Nov. 29th, 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

In the field of computers, the diagnosability of a multiprocessor is an important study topic. The traditional diagnosability allows that all neighbors of some vertices are faulty at the same time. However, in the processor system, the probability of this kind of situation is very small. Therefore, in 2012, Peng et al. proposed the g-good-neighbor diagnosability. It restrains every fault-free node containing at least g fault-free neighbors. As hypercube variants, the n-dimensional Möbius cube has some better properties than hypercubes. This paper shows that the 1-good-neighbor connectivity of is (), and the 1-good-neighbor diagnosability of is under the PMC model () and under the MM* model ().

Keywords:Interconnection Network, Möbius Cube, 1-Good-Neighbor Diagnosability

Möbius立方体的1好邻连通度和诊断度

白灿1,王世英1,2*,王贞化1

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

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

收稿日期:2016年11月10日;录用日期:2016年11月25日;发布日期:2016年11月29日

摘 要

在计算机领域,多处理器系统的诊断度是一项重要的研究课题。在传统的诊断度中,任一处理器的所有相邻处理器可以同时出现故障。但是,在处理器系统中,出现这种情况的概率极小。因此,peng等在2012年提出了g好邻诊断度,它限制每个非故障顶点至少有g个非故障邻点。作为超立方体的变形,n维Möbius立方体有着比超立方体更好的性质。本文证明了的1好邻连通度是,又证明了在PMC模型下()和在MM*模型下()的1好邻诊断度是

关键词 :互连网络,Möbius立方体,1好邻诊断度

1. 前言

近些年来,随着多处理器规模的扩大,处理器的稳定性对系统的正常运行起着至关重要的作用。为了保证系统的稳定性,一个处理器无论何时发生故障,它都应该及时地被非故障处理器所识别,我们把识别故障处理器的过程叫做系统的诊断。在一个系统中,如果所有的故障处理器能够被自我诊断出来,并且所诊断出的故障处理器的数量不超过,那么我们说这个系统是可诊断的。一个系统的诊断度指的是可诊断的的最大值。

为了识别系统中的故障处理器,一些诊断模型被提出,如PMC模型和MM*模型。PMC模型 [1] 是由Preparata等首次提出,它是通过两个相邻的处理器之间相互测试来实现的。Maeng和Malek提出了另一种比较诊断模型(MM*模型) [2] 。在MM*模型下,一个顶点分别给它的两个邻点发出相同的任务,然后比较它们反馈的结果。2005年,Lai等提出了多处理器系统的一种限制诊断度,命名为条件诊断度 [3] 。2012年,Peng等通过限制每个非故障顶点至少有个非故障邻点,提出了好邻诊断度 [4] ,并且他们证明了超立方体在PMC模型下的好邻诊断度是。王世英,韩威萍在文 [5] 中证明了维超立方体在MM*模型下的好邻诊断度。原军等在文 [6] 中证明出了立方体在PMC模型和MM*模型下的好邻诊断度是。他们在文 [7] 中还证明了3元立方体的好邻诊断度。对于条件诊断度来说,其假设故障和非故障点的邻域中均至少有一个是非故障的。而对于1好邻诊断度来说,其仅假设非故障点的邻域中至少有一个是非故障的。在实际中,为节约资源和提高运算效率,大规模多处理器系统中多采用模块化设计方式。局部处理器多共享如电源、存储空间等软硬件资源且相对地数据交换频率较高。这就意味着非故障点的邻域中至少存在一个非故障点的概率远大于故障点邻域中至少存在一个非故障点的概率。鉴于此种情况,1好邻诊断度较条件诊断度更为贴合实际。马晓蕾等在文 [8] 中证明了交叉立方体的1好邻连通度和诊断度。在文 [9] 中,王牟江山等证明了网络的1好邻诊断度不超过条件诊断度。我们在这篇文章中研究Möbius立方体的1好邻连通度和诊断度。本文第二部分是预备知识,第三部分证明了Möbius立方体的1好邻连通度是,第四部分又证明了Möbius立方体在PMC模型下和在MM*模型下的1好邻诊断度是,第五部分是结论。

2. 预备知识

在这部分,我们将给出文中需要的一些基本符号和概念,Möbius立方体、PMC模型、MM*模型在这部分将给出介绍。

互联网络的拓扑结构我们用图来表示,其中顶点表示处理器,边表示两处理器之间的通信链路。对于一个顶点中的度,表示在中与相关联的边数。对于任意一点,与相邻的所有顶点的集合称作的邻集,记作。假设,那么的邻集表示为。设中两个不同的子集。我们将对称差记作。一条路是一个所有顶点互不相同的相邻的顶点序列。如果是图的边子集,且中的任意两条边没有公共顶点,则称的一个匹配。如果是图中包含边数最多的匹配,称的一个最大匹配。特别地,若最大匹配饱和了的所有顶点,称它是的一个完美匹配。任意一个故障集,对于任意一点,如果,那么称作好邻故障集。如果好邻故障集使得不连通,那么是一个好邻割。的所有好邻割中的最小顶点数称为好邻连通度,记作。文中其它未定义而直接使用的基本符号和概念参见文献 [10] 。

在PMC模型中,为了诊断系统,在中相邻的两点之间可以相互测试。在中,两个相邻的顶点表示从的测试,其中是测试者,是被测试者,我们用表示测试结果。在PMC模型下,所有的测试结果如表1所示。在MM*模型下,结点给它相邻的两个结点分配同一个的任务,再把测试结果反馈给结点对这两个结点反馈的结果进行比较。全部的测试结果叫做这个系统的比较症候,记作。我们用来表示测试结果。在MM*模型下,所有可能出现的比较结果如表2所示。

维超立方体是一种很受欢迎的拓扑结构,Möbius立方体作为超立方体的一种重要变形,它有着比超立方体更好的性质。在文献 [11] 中已经给出了维Möbius立方体的概念,维Möbius立方体是一个有个顶点和条边的正则图。的直径大约是维超立方体的一半。在中,点之间的平均通信步大约是超立方体的2/3,比超立方体有着更强的动态性能。因此也是一种很好的网络拓扑结构,值得我们研究。

维Möbius立方体作为超立方体的变形,其有两种形式,0型维Möbius立方体和1型维Möbius立方体,分别记作

定义1维Möbius立方体,表示为,它的顶点集是。在中,两个顶点相邻当且仅当(a)存在()满足:

(1) 如果,那么

(2) 如果,那么

(b)满足

中,两个结点相邻当且仅当(a)存在()满足:

(1) 如果,那么

(2) 如果,那么

(b)满足

图1给出了4维的0型Möbius立方体,图2给出了4维的1型Möbius立方体。

Table 1. The test results in the PMC model

表1. 在PMC模型下测试结果

Table 2. The test results in the MM* model

表2. 在MM*模型下测试结果

Figure 1. 4 dimensional 0 type Möbius cube

图1. 4维0型Möbius立方体

Figure 2. 4 dimensional 1 type Möbius cube

图2. 4维1型Möbius立方体

都是维Möbius立方体,本文只讨论,并把它记为

3. n维Möbius立方体的1好邻连通度

引理 3.1 [12] 当时,不包含三圈。

根据定义1,两个顶点相邻当且仅当条件(b)成立,即,当时满足,此时我们称顶点之间的连边是的第维边。我们将沿着最高维分解,是通过删除中所有第维的边,将其分解成两个维子图,显然他们都同构于。我们称之间的连边为交叉边,这些交叉边的集合是的一个完美匹配。

引理 3.2维Möbius立方体中任意两个顶点之间至多有两个公共邻点。

证明根据引理3.1,任意两个相邻的顶点没有公共邻点。设中任意两个不相邻的顶点。用归纳法证明。当时,是一个四圈,此时结论成立。我们假设时结论都成立,即,中任意两个顶点之间至多有两个公共邻点当。将沿最高维分解成两个维子图,它们同构于之间存在完美匹配。若在同一个维的子图中,不失一般性,假设。由归纳假设中至多有两个公共邻点。因为之间交叉边是一个完美匹配,所以中没有公共邻点。若分别在两个维的子图中,不失一般性,假设。因为之间交叉边是一个完美匹配,所以中均至多有一个公共邻点。因此,中至多有两个公共邻点。由的任意性,中任意两个不相邻的顶点至多有两个公共邻点。

引理 3.3 [12] 维Möbius立方体的连通度

引理3.4 当时,对任意的,设,则

证明要证,我们只需证明不含孤立点。当或4时,结论显然成立。当时,用反证法证明。假设中的孤立点,则。因为,所以。根据引理3.2,可得。于是,。因为正则图,所以。因此,至少存在一个邻点不在中,这与矛盾。所以不含孤立点。故

引理 3.5维Möbius立方体的1好邻连通度

证明 令的定义与引理3.4相同,则的一个割。因为没有三圈,可以得到。根据引理3.4,可以推出,又因为。因此,是一个1好邻割。故可以推出

引理 3.6令的一个点割。当时,恰有两个分支,一个是平凡分支,另一个是非平凡分支。

证明将沿最高维分解成两个()维的子图,它们同构于。设,则。不失一般性,我们假设

情形1或者

不失一般性,我们假设。此时。因为之间的交叉边是的一个完美匹配,所以是连通的。这与的一个点割矛盾。

情形2

情形2.1

根据引理3.3,,所以是连通的。

情形2.1.1

根据引理3.3,,所以是连通的。因为以及之间的交叉边是的一个完美匹配,所以是连通的,即,是连通的。这与的一个点割矛盾。

情形2.1.2

此时。假设是连通的,证明同情形2.1.1。因此是不连通。注意到,又因为之间的交叉边是的一个完美匹配,所以中除孤立点外的分支一定与连通。因此,恰有两个分支,一个是平凡分支,另一个是非平凡分支。

情形2.2

此时。此情形证明同情形2.1.2。

综上所述,结论成立。

引理 3.7令的一个点割。当时,恰有两个分支,一个是平凡的,另一个是非平凡的。

证明 将沿最高维分解成两个()维的子图。显然,它们同构于。设,则。我们采用归纳法证明。当时,。根据引理3.6,恰有两个分支,一个是平凡的,另一个是非平凡的。假设时结论也成立,即,的一个点割且当时,恰有两个分支,一个是平凡的,另一个是非平凡的。下面证明时结论也成立。不失一般性,假设,因为,所以

情形1

根据引理3.3,,则都连通。因为之间的交叉边是的一个完美匹配,所以是连通的,即,是连通的。这与的一个点割矛盾。

情形2

根据引理3.3,。则连通。

情形2.1

连通,证明同情形1。故不连通。由归纳假设,恰有两个分支,一个是平凡分支,另一个是非平凡分支。因此,。注意到。又因为之间的交叉边是的一个完美匹配,所以。因此,中至少有一点与中的点相连。则连通。若中的任意一点相连,那么连通,这与的一个点割矛盾。故恰有两个分支,一个是平凡分支,另一个是非平凡分支。

情形2.2

情形2.2.1

在这种情况下,。根据引理3.3,连通。若连通,证明同情形1。故不连通。注意到,又因为之间的交叉边是的一个完美匹配,所以中除孤立点外的分支一定与连通。因此,恰有两个分支,一个是平凡分支,另一个是非平凡分支。

情形2.2.2

在这种情况下,。因为之间的交叉边是的一个完美匹配,所以连通。这与的一个点割矛盾。

综上所述,结论成立。

引理 3.8维Möbius立方体的1好邻连通度

证明我们用反证法证明,假设是一个1好邻割且。则没有孤立点且不连通。根据引理3.7,当恰有两个分支,一个是平凡的,另一个是非平凡的。这与没有孤立点矛盾。因此,结论成立。

结合引理3.5和引理3.8可得以下定理:

定理 3.9 维Möbius立方体的1好邻连通度

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

定理4.1 [6] 在一个系统中,对于任意两个不同的且顶点个数不超过好邻故障集,若是可区分的,则好邻条件-可诊断的,使得好邻条件-可诊断的最大值叫做好邻诊断度,记作

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

定理4.3 [6] 一个系统在MM*模型下是好邻-可诊断的当且仅当对中任意两个不同的顶点数不超过好邻故障集,满足以下其中一个条件(如图4):

(1) 存在满足

(2) 存在满足

(3) 存在满足

Figure 3. A distinguishable pair under the PMC model

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

Figure 4. A distinguishable pair under the MM* model

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

引理4.4 维Möbius立方体在PMC模型下和MM*模型下的1好邻诊断度

证明 对任意的,设。因为没有三圈,所以。根据引理3.4,。因此,的两个1好邻故障集。因为,所以在之间没有边。由定理4.2定理4.3,我们可以推出在PMC模型下和MM*模型下不是1好邻-可诊断的。因此,由1好邻诊断度的定义可知的1好邻诊断度小于,即

引理4.5 维Möbius立方体在PMC模型下的1好邻诊断度

证明由1好邻诊断度的定义,需要证明是1好邻-可诊断的。根据定理4.2,证明是1好邻-可诊断的等价于证明任意两个不同的且顶点个数不超过的1好邻故障集,存在,使得

采用反证法证明。假设在中有两个不同的且顶点个数不超过的1好邻故障集,根据定理4.2,对任意的使得。不失一般性,假设。可以分以下两种情况进行讨论:

情形1

因为,我们可以推出。当时,上述不等式矛盾。

情形 2

根据假设之间没有边和好邻故障集,可得。同理,若,则。因为都是1好邻故障集,所以也是一个好邻故障集。又因为在之间没有边,所以不连通。故的1好邻割。根据引理3.8,可得。因此,。这与相矛盾。因为以上两种情况都产生矛盾,所以是1好邻-可诊断的。由的定义可得,

结合引理4.4和引理4.5,可得以下定理:

定理 4.6维Möbius立方体在PMC模型下的1好邻诊断度

引理 4.7 维Möbius立方体在MM*模型下的1好邻诊断度

证明根据1好邻诊断度的定义,等价于证明是1好邻-可诊断的。采用反证法证明。根据定理4.3,假设中存在两个不同的且顶点个数不超过的1好邻故障集不满足定理4.3中的(1)-(3)。不失一般性,假设。分以下两种情况进行讨论:

情形 1

证明同引理4.5的情形1。

情形 2

断言 1 没有孤立点。

为了证明结论成立我们采用反证法。设至少有一个孤立点。因为是一个1好邻故障集,所以至少存在一点使得相邻。另一方面,因为不满足定理4.3中的(1)~(3)中的任意一种条件,所以至多存在一点使得。因此仅有一点使得。因为是一个1好邻故障集,所以至少有一个邻点,即。同理,仅有一点使得。设中的孤立点集,令是由点集导出的子图。因此,对任意的,存在个邻点在中。由于,故。因为,所以。假设,有。当时,上式矛盾,故。因为不满足定理4.3中的(1)且的任意一点是不孤立的,所以可以推出之间不存在边相连。因此,的点割且,即的一个1好邻割。根据定理3.8,。 因为,并且都是非空的,所以。于是,设。所以对于任意的满足。根据引理3.2,中至多有两个公共邻点。因此, 至多有两个孤立点。

假设中恰有一个孤立点,则中与相邻。显然,。根据引理3.2,至多有两个公共邻点,所以。因此,。于是,。这与矛盾。

假设在中还有另外一个孤立点,则。根据引理3.1,可以得到。又因为在中任意两点至多有两个公共邻点,所以中任意两个集合在中都没有公共点。因此。于是,,这与矛盾。断言1证明完毕。

。根据断言1,中至少有一个邻点。因为不满足定理4.3中的(1)~(3)中的任意一种条件,根据定理4.3(1),所以对于任意一对相邻的点,不存在使得。因此,我们可以得到中没有邻点。由的任意性,之间没有边。因为是一个1好邻故障集且,所以,则。因为都是1好邻故障集并且之间没有边,所以的一个1好邻割。根据引理3.6,有。因此,。这与矛盾。于是,是1好邻-可诊断的。故

结合引理4.4和引理4.7可得以下定理:

定理 4.8 维Möbius立方体在MM*模型下的1好邻诊断度

5. 结论

在这篇文章中,我们研究了维Möbius立方体在两种模型下的1好邻诊断度问题。本文证明了Möbius立方体的1好邻连通度是,又证明了Möbius立方体在PMC模型下的1好邻诊断度是和在MM*模型下的1 好邻诊断度是。1好邻诊断度是假设每个非故障点至少有1个好的邻点,好邻诊断度是假设每个非故障点至少有个好的邻点。这项工作将对后面研究Möbius立方体网络的好邻连通度、诊断度和相关诊断算法提供很好的帮助。

基金项目

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

文章引用

白灿,王世英,王贞化. Mo¨bius立方体的1好邻连通度和诊断度
The 1-Good-Neighbor Connectivity and Diagnosability of Mo¨bius Cubes[J]. 应用数学进展, 2016, 05(04): 728-737. http://dx.doi.org/10.12677/AAM.2016.54084

参考文献 (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, 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 Computation, 218, 10406-10412. https://doi.org/10.1016/j.amc.2012.03.092

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

  6. 6. 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 Parallel and Distributed Systems, 26, 1165-1177. https://doi.org/10.1109/TPDS.2014.2318305

  7. 7. Yuan, J., Liu, A.X., Qin, X., Zhang, J.F. and Li, J. (2016) g-Good-Neighbor Conditional Diagnosability Measure of 3-Ary n-Cube Networks. Theoretical Computer Science, 626, 144-162

  8. 8. Ma, X.L., Wang, S.Y. and Wang, Z.H. (2016) The 1-Good-Neighbor Connectivity and Diagnosability of Crossed Cube. Advance in Applied Mathematics, 5, 282-290.

  9. 9. Wang, M., Guo, Y.B. and Wang, S.Y. (2015) The 1-Good-Neighbor Diagnosability 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

  10. 10. Bondy, J.A. and Murty, U.S.R. (2007) Graph Theory. Springer, New York.

  11. 11. Cull, P. and Larson, S.M. (1995) The Möbius Cubes. IEEE Transactions on Computers, 44, 647-659. https://doi.org/10.1109/12.381950

  12. 12. Fan, J.X. (1998) Diagnosability of Möbius Cubes. IEEE Transactions on Parallel and Distributed Systems, 9, 923-928. https://doi.org/10.1109/71.722224

*通讯作者。

期刊菜单