Advances in Applied Mathematics
Vol.05 No.04(2016), Article ID:19120,11
pages
10.12677/AAM.2016.54088
The 1-Good-Neighbor Diagnosability of Augmented k-Ary n-Cubes
Yanli Hao1, 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. 9h, 2016; accepted: Nov. 25th, 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
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,王世英1,2*
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模型下
Figure 1. A distinguishable pair under the PMC model
图1. 在PMC模型下可区分
Figure 2. All the neighboring vertices of u and v respectively
图2. u和v的全部邻点
Figure 3. An illustration about the proofs of the Lemma 3.5 and 4.2
图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-好邻条件
可诊断的。故
。
Figure 4. A distinguishable pair under the MM* model
图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)
- 1. 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
- 2. 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
- 3. 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.
- 4. Joon, M. and Miroslaw, M. (1981) A Comparison Connection Assignment for Self-Diagnosis of Multipro-cessor Systems. Proceeding of 11th International Symposium on Fault-Tolerant Computing, Portland, June 1981, 173-175.
- 5. Chang, N.W., Cheng, E. and Hsieh, S. (2015) Conditional Diagnosability of Cayley Graphs Generated by Transposition Trees under the PMC Model. ACM Transactions on Design Automation of Electronic Systems, 20, 1-16. https://doi.org/10.1145/2699854
- 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. 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
- 8. 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 Com-puter Science, 622, 144-162.
- 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. Wang, M., Guo, Y.B. and Wang, S.Y. (2015) The 1-Good-Neighbor Di-agnosability 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
- 11. 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
- 12. Bondy, J.A. and Murty, U.S.R. (2007) Graph Theory. Springer, New York.
- 13. 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
*通讯作者。