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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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
*通讯作者。