超立方体网络的间歇性故障诊断度研究

冯 浩，梁家荣

(广西大学计算机与电子信息学院， 广西南宁530004)



超立方体网络的间歇性故障诊断度研究

冯 浩，梁家荣

(广西大学计算机与电子信息学院， 广西南宁530004)

网络系统的诊断度是判断其自我诊断能力的重要度量，网络的故障类型包括永久性故障与间歇性故障两大类。与永久性故障相比，间歇性故障更具隐秘性，更难诊断。超立方体网络是一个具有性能优越的网络拓扑结构并已得到广泛的应用。针对超立方体网络在间歇性故障诊断理论方面的缺失, 在本文中利用图论方法研究了超立方体网络(具有或不具有丢失边)的ti故障诊断度。应用所得到的结果，可以很容易判断整个超立方体或者其中一部分网络的间歇性故障诊断度，为超立方体网络的可靠性分析提供重要的理论依据。

超立方体;间歇性故障诊断度;多处理机网络系统;PMC模型

0 引 言

随着大型高性能多处理机网络系统高速发展，网络系统的规模会变得越来越大。在网络系统的运行过程中，处理器(结点)出现故障是难以避免的，故障的存在可能会使信息的通信迟缓甚至会导致系统瘫痪。因此，对系统结点的测试与故障诊断是具有重要意义的。目前故障的测试方法主要有系统级诊断和非系统级诊断，非系统级诊断主要采用的是硬件测试诊断，其优点是更换或修复方便，缺点是效率低，测试资源需求大且容易出错，尤其是对大规模的网络系统。而系统级诊断借助网络自身的处理器进行相互诊断，不影响系统的运行，效率高且不易出错，已为人们所采用。在系统级诊断中，1967年Preparata, Metze以及Chien (PMC) 等所提出的PMC模型是最早的系统级别故障诊断模型。PMC模型认为：在一个网络系统中，如果节点u与节点v相连，那么节点u就能够测试节点v是故障或无故障。测试结果可用0或1来表示，测试结果为0表示节点u测试节点v为无故障，结果1则节点u测试节点v为故障。如果测试节点u是正常节点，那么测试结果是可靠的，如果测试节点u是故障节点，那么测试结果是不可靠的。在永久性故障情形下，基于PMC模型的网络系统故障诊断理论研究已取得了大量的成果[1-4]。值得一提的是2005年Lai等在充分分析t可诊断系统的基础上，提出了强t故障可诊断系统的理论，该理论认为t故障可诊断系统必定是t可诊断的，并且几乎也是(t+1)-可诊断系统，只有当某一个节点的所有邻居节点全部故障的情况属例外。Lai等在文献[5]中还证明了一个t维度的MCN网络也是强t+1可诊断的，这为网络的故障诊断度理论提供了重要的内容。

在过去的几十年中，模拟多处理机系统的网络拓扑模型已有不少，规则互连网络是极富代表性的一种[6-11]。在规则互连网络中，超立方体网络是应用最为广泛的一种互连网络结构[12]，对超立方体网络各方面的研究工作已充分展开[13-15]。正如上面所提，故障诊断对超立方体网络的可靠性分析有着重要的意义，在永久性故障情形，超立方体的故障诊断理论已取得了不少成果。然而在间歇性故障情形，超立方体的故障诊断研究乏善可陈。

本文通过分析超立方体网络的结构入手，首先研究不存在故障边的情况下的超立方体网络的间歇性故障诊断问题，并借此进一步研究存在故障边(或者缺失边)情况下，超立方体网络的间歇性故障诊断度。

1 预备知识

文中使用G=(V,E)来代表一个无向图，其中V(G)、E(G)分别代表图G中的点集和边集。任一个多处理机系统都可以用一个图来表示，其中图G中的结点表示处理机，而边(vi,vj)表示边vi与vj联通之间的通信。本文中，有关图的相关概念与定义与文献[16]一致。

在一个图G中，一个结点v的度数指的是与结点v关联的边的条数，记为deg(v)。如果图G中的最大结点度数与最小结点度数相等，则称图G为一个正则图，如果这个度数是k，则称图G是一个k-正则图。G-S表示图G删掉S中的结点后的子图。设M是一个图G中的任意集，则使用NG(M)表示集合M的所有邻居结点组成的集合，即NG(M)={v|v∈V∧∃u∈M((u,v)∈E)}。一个故障集表示图G中所有故障结点组成的集合。识别所有故障结点的过程被称作系统诊断。在永久性故障情形下，能被识别出来的最大的故障集的基数称为系统的永久性故障诊断度，记为tp(G)。

定义1 一个系统称为n-tp-可诊断的如果所有的故障结点都是永久性故障，且只要系统中的故障结点的数量不超过n，所有的故障结点都能被识别[17]。

设F1,F2⊂V为两个不同的子集，记F1ΔF2=(F1-F2)∪(F2-F1)。Dahbura以及Masson在文献[18]中提出了判断一个系统是否是tp-可诊断的充要条件。

对于间歇性故障情形，故障结点的状态有时是正常的，有时是故障的，要识别这样的结点可能要测试多次。称一个诊断策略是不完全的如果一些间歇性故障结点被识别为正常结点的，而称一个诊断策略是不正确的如果它把一些正常的结点识别为故障的。为此，应避免不正确的诊断，因为有时不正确的诊断会导致系统级别的崩溃。

定义2 一个系统G=(V,E)称为m-ti-可诊断的如果对于任意的诊断:①任一个正常的结点都不会被诊断为故障的；②这个诊断只能是不完全的，不会是不正确的，只要间歇性故障结点的数量不超过m。

相似于永久性故障情形，Mallela以及 Masson提出了一个检验一个系统是否是ti-故障可诊断的充分必要条件，并给出了一个系统中tp和ti的诊断度的数量关系。

引理3 如果一个系统是n-tp-可诊断的，同时也是m-ti-可诊断的，那么如下不等式成立[19]：

一个n维超立方体网络G=(V,E)可表示为Qn，V由2n结点组成，每个结点地址可用一个n位的二进制数来表示，(vi,vj)∈E当且仅当vi与vj之间有且只有一个不同的比特位。一个n+1维超立方体可以看成是由两个n维超立方体所构成，用oan…a2a1(obn…b2b1)分别表示第一(第二)个n维超立方体网络的结点。图1展示出了Q3以及Q4(3维超立方体及4维超立方体)，每一条无向边表示其两个端结点可以互相测试。每一个结点都都关联着n条边。

(a)Q3

(b)Q4

图1 一个3维超立方体Q3以及一个4维超立方体Q4

Fig.1 A 3-dimension hypercube and a 4-dimension hypercube

2 超立方体网络的间歇性故障诊断度

在这一部分，主要讨论超立方体Qn的间歇性故障诊断度，也就是ti值。由引理2可知，超立方体的永久性故障诊断度总是等于它的维度n，也等于每个结点v的度数deg(v)。从引理3可知，在一个相互测试的无向图中，ti值永远不会超过tp值。这也意味着，在超立方体中，间歇性故障诊断度最多只能与永久性故障诊断度相等。下面，将进一步讨论Qn中的ti与tp的关系。

引理4 对于一个超立方体Qn(n≥3)，ti

进一步对ti值进行研究以观察它最大能达到多少，得出下面的结论。

定理1 在超立方体Qn(n≥3)中，间歇性故障诊断度ti=tp-1。

为了证明定理1，需要用到如下引理。

引理5证毕。

3 具有丢失边的超立方体的间歇性故障诊断度

通过上面的讨论可以获得：在PMC模型下超立方体的间歇性故障诊断度为n-1(永久性故障诊断度为n)。应该说明的，这个诊断度是在n维超立方体所有边都能有效的进行通信情况下才成立的，即间歇性故障诊断度为n-1的前提为不会存在丢失边。如果n维超立方体存在边故障或者说有些边丢失，那么其故障诊断度如何？这是值得期待研究的问题。在文献[7]中能得到以下关于n维超立方体永久性故障诊断度的结论。

引理6 给出一个n维具有丢失边的超立方体网络，表示为G=(V,E)。如果min{deg(v)|v∈V}=r且r≥3，则此系统为r-tp-可诊断的[1]。

引理7 一个n-维超立方体Qn不存在长度为3的环(无3环)并且任两点最多有两个共同邻居结点[1]。

接着检验在具有丢失边的超立方体中ti值是否依然等于tp-1。

定理2 在具有丢失边的超立方体中，如果min{deg(v)|v∈V}=r并且r≥2,那么此系统的间歇性故障诊断度ti=r-1。

在证明定理2之前，需要如下引理。

证明 通过划分为以下几种情况来证明这个引理：

情形1M中任意两个结点均不相邻。

情形2 在M中存在着一些相互连接的结点对。

让v1与v2表示其中一对互相连接的结点。因为每个结点的度至少为r，假设：

deg(v1)=r+m1,

deg(v2)=r+m2(0≤m1,m2≤n-r),

因为v1与v2相连并且在超立方体中不存在长度为3的环(引理7)。因此这r+m1个连接着v1的结点与连接着v2个结点不会有交集[如图2(b)]。于是有：

并且同样的,

显然得出:

NG(v1,v2)=r+m1+r+m2-2=2r+m1+m2-2,

(a) 情形1

(b) 情形2

图2 引理8证明图例

Fig.2 Case of lemma 8

图3 一个四维正则图Fig.3 A 4-regular graph

4 结 语

超立方体的容错能力一直是一个关键性研究热点，至今却仍没有一个能快速简单判断超立方体间歇性故障诊断度的方法。应用本文的研究结果，所有n≥3的超立方体ti故障诊断度都能一目了然即ti=n-1。并且，本文还进一步研究了具有丢失边的超立方体的ti值，假若具有丢失边的不完整的超立方体满足min{deg(v)|v∈V}=r并且r≥2,那么此系统的间歇性故障诊断度为ti=r-1。应用本文的结果可以对某些不完全超立方体进行间歇故障诊断度判断，或者对某些连接失效的超立方体和只想进行部分诊断的超立方体进行ti值的判断研究。

[1] NG D.The diagnosability of hypercubes with arbitraily missing links[J]. Journal of Systems Architecture, 2000, 46(3): 519-527.

[2] 郭晨,梁家荣,葛志辉,等.基于互测PMC模型的条件诊断算法[J]. 电子学报, 2015, 43(2): 255-261.

[3] NAI W C,SUN Y H.Structural properties and conditional diagnosability of star graphs by using the PMC model[J]. IEEE Transaction on Parallel and Distributed systems, 2014, 25(11): 3002-3011.

[4] 黄莹,梁家荣,叶良程.交换超立方体网络的t1/k-诊断度研究[J]. 小型微型计算机系统, 2015, 36(9): 2054-2057.

[5] LAI P L, TAN J JM, CHANG C P.Conditional diagnosability measures for large multiprocessor systems[J]. IEEE Transaction on Computer, 2005, 54(2): 165-175.

[6] 谢春萍,梁家荣.星型网络的几种故障诊断度研究[J]. 广西大学学报(自然科学版), 2015,40(3):699-704.

[7] EFE K.The crossed cube architecture for parallel computation[J]. IEEE Transaction on Parallel and Distributed Systems, 1992, 3(5) : 513-524.

[8] PAUL C, SHAWN M L.The Möbiuscubes[J]. IEEE Transaction on Computer, 1995, 44(5): 647-659.

[9] ABDOL H E, LIONEL M N, BRUCE E S.The twisted n-cube with application to multiprocessing[J]. IEEE Transaction on Computer,1991, 40(1): 88-93.

[10]LI J, TAN X.The Diagnosability of Augmented Cubes under PMC Model[J]. IEEE Transaction on Parallel and Distributed Systems, 2010, 10(2): 301-304.

[11]LIANG J R, HUANG Y, YE L C.Diagnosabilities of exchanged hypercube networks under the pessimistic one-step diagnosis strategy[J]. Journal of Systems Engineering and Electronics, 2015, 30(2): 415-420.

[12]JOHN P H.Architecture of a hypercube supercomputer[J]. IEEE Transaction on Computer, 1986, 10(2): 653-660.

[13]CHANG H T.A Quick pessimistic diagnosis algorithm for hypercube-like multiprocessor systems under the PMC model[J]. IEEE Transaction on Computer, 2013, 62(2): 259-267.

[14]WANG D, WANG Z.Minimum assignment of test links for hypercubes with lower fault bounds[J]. IEEE Transaction on Parallel and Distributed Systems,1997,40(2):185-193.

[15]HSU G H, CHIANG C F, SHIH L M, et al.Conditional diagnosability of hypercubes under the comparison diagnosis model[J]. IEEE Transaction on Computer, 2009, 55(2): 140-146.

[16]DOUGLAS B W, Introduction to Graph Theory[M]. USA: Prentice Hall, 2001.

[17]FRANC P P, GERNOT M, ROBERT T C.On the connection assignment problem of diagnosable system[J]. IEEE Transaction on Electronic Computers, 1967, 16(6): 848-854.

[18]ANTON T D, GERALD M.An O(N2.5) Fault identification algorithm for diagnosable systems[J]. IEEETransaction on Computer, 1984, 33(6): 486-492.

[19]SIVANARAYANA M, GERALD M M.Diagnosable systems for intermittent faults[J]. IEEE Transaction on Computer,1978, 27(3): 360-366.

(责任编辑 梁碧芬)

Research on intermittent fault diagnosability of hypercube networks

FENG Hao, LIANG Jia-rong

(School of Computer, Electronics Information, Guangxi University, Nanning 530004, China)

Diagnosability of networks is one key measure to judge its self-diagnose capability. Fault type of networks includes the permanent fault and the intermittent fault. Compared with the permanent fault, the intermittent fault is easier to be hided and harder to be diagnosed. The hypercube network is a kind of network topology with superior performances and has been used widely. In view of the absence of intermittent fault diagnosis theory in hypercube network, theti-fault diagnosability of hypercube (with or without missing links) is studied, by employing graph theory. By using the presented method, the intermittent fault diagnosability of one hypercube or just part of it can be determined, which provides an important theoretical basis for reliability analysis of hypercube networks.

hypercube; intermittent fault diagnosis; multi-processor network; PMC model

2016-06-11；

2016-07-28

国家自然科学基金资助项目(61363002)

梁家荣(1966—)，广西玉林人，广西大学教授，博士生导师；E-mail:13977106752@163.com。

冯浩，梁家荣.超立方体网络的间歇性故障诊断度研究[J].广西大学学报(自然科学版)，2016，41(5)：1560-1566.

10.13624/j.cnki.issn.1001-7445.2016.1560

TP393

A

1001-7445(2016)05-1560-07