带有丢失弧的双向超立方体网络的诊断度

超立方体因其特殊的结构和良好的性质成为多处理机系统最常用的互联网络之一.在实际的超立方体网络中两个处理器间的双向连接常常是通过两个方向相反的单向信道物理实现的.诊断度是度量系统识别故障能力的指标,而PMC模型是一种基于测试的系统级故障诊断模型.研究了当丢失一些单向信道时双向超立方体网络在PMC模型下的诊断度并确定了具有特定诊断度的双向超立方体所需的最小测试数.     

超立方体Q_n在PMC模型下的2-条件诊断度

诊断度是衡量多处理器系统自我诊断能力的重要参数,是多处理器系统互连网络能够诊断出故障点的最大数。2-条件诊断度的概念是条件诊断度概念的一个推广,要求系统中的每个结点至少有2个好邻点。研究了超立方体Q_n在PMC模型下的2-条件诊断度并证明了Q_n在PMC模型下的2-条件诊断度为16n-57.     

交换折叠超立方体的2-额外边连通度

g-额外边连通度是衡量大型互连网络可靠性和容错性的一个重要参数.设G是连通图且g是非负整数,如果图G中存在某种边子集,使得G中删除这种边子集后得到的图不连通并且每个分支的点数超过g,则所有这种边子集中基数最小的边子集的基数称为图G的g-额外边连通度,记作λ_g(G).一个新的网络交换折叠超立方体网络记为EFH(s,t).本文利用2-额外边连通度作为评价可靠性的重要度量,对交换折叠超立方体网络的可靠性进行了分析,得到了交换折叠超立方体网络的2-额外边连通度.证明了:EFH(s,t)的2-额外边连通度等于3s+2(6≤s≤t).这个结果意味着:为了使EFH(s,t)不连通且每个分支都至少包含3个顶点,至少有3s+2条边要同时发生故障.     

交换超立方体在PMC模型下的g好邻条件诊断度

诊断度是多处理器系统互连网络能够诊断的最大故障结点的个数,它是度量多处理器系统故障诊断能力的一种参数。g好邻条件诊断度是2012年提出的一种新的诊断度,它要求每个非故障顶点至少有g个非故障邻点。研究了交换超立方体EH(s,t)在PMC模型下的g好邻条件诊断度,证明了EH(s,t)(1≤s≤t,0≤g≤s)在PMC模型下的g好邻条件诊断度为2g(s+2-g)-1.     

加强立方网络的条件诊断度

多处理系统规模的扩大会增加系统某些元件的脆弱性.故障诊断就是系统通过内部测试来识别故障处理机的过程,故障诊断度是衡量互联网络可靠性的重要参数.条件诊断作为新的容错性的度量能更好地评估互联网络真实的诊断能力.求出了加强立方体网络EQ n,k(4≤k≤n)在PMC模型下的条件诊断度.     

交换折叠超立方体的超连通度

超连通度(超边连通度)是衡量大型互连网络可靠性和容错性的一个重要参数。设G是连通图,图G的超连通度(超边连通度)是指从G中删除最小数目的点(边)使得G不连通,且G的每个连通分支中都至少包含两个顶点。李等人(2015)提出了一个新的网络交换折叠超立方体网络EFH(s,t)。该文利用超连通度和超边连通度作为评价可靠性的重要度量,对交换折叠超立方体网络的可靠性进行分析,得到了交换折叠超立方体网络的超连通度和超边连通度,证明了EFH(s,t)的超连通度和超边连通度等于2s+2,1≤s≤t。这个结果意味着,为了使EFH(s,t)不连通且不含孤立点,至少有2s+2个点(边)要同时发生故障。     

平衡立方体在PMC模型下的1-好邻条件诊断度

诊断度的确定是实现系统级故障诊断的一个重要前提。g好邻条件诊断度推广了经典的诊断度的概念,它要求每个非故障结点没有发生故障的邻点个数至少有g个。以PMC为模型,对平衡立方体BHn的1-好邻条件诊断度的上、下界进行讨论,最终得到了BHn在PMC模型下的1-好邻条件诊断度为(4n-1).     

折叠交叉立方体的限制连通度

限制性连通度作为评估互联网络容错性的最佳参数之一,在多处理器系统中对可靠性计算起着重要作用.给定一个连通图G=(V,E)和一个非负整数h,子集F?V(G)(F?E(G))(如果存在)称为h-限制点割(h-限制边割),如果G-F不连通,并且G-F中的每个连通分支至少有h+1个顶点,其中最小的h-限制点割(h-限制边割)的...     

BC网络的g-超条件诊断度

多处理器系统的故障诊断是一个重要的研究课题。g-超条件诊断度是于2016年提出的度量系统自我故障诊断能力的一类新的参数,它是在每个非故障结点组成的分支至少包含g+1个顶点的假设下,系统G能够一次性识别的故障结点的个数。g-超条件诊断度能够更精确地度量异构环境下系统互连网络的自我故障诊断能力。文章研究了n-维双射连接(BC)网络在PMC和MM*模型下的g-超条件诊断度,给出了n-维BC网络在两种模型下g-超条件诊断度的下界。在此基础上,确定了超立方体在PMC和MM*模型下g-超条件诊断度,改进了相关结果。最后,我们给出了当1≤g≤3时,BC网络在PMC和MM*模型下的g-超条件诊断度的计算公式。     

交叉立方体的限制性连通度（英文）

G是一个图,h是一个正整数,一个图G的h-限制性连通度是使得G删除G中的某个点集使得G不连通且每个分支中点的度数至少是h的最小点集的基数.交叉立方体网络是超立方体的一个变形,在平行计算系统当中交叉立方体是最重要的网络之一.该文证明了n维交叉立方体2-和3-限制性连通度分别是4n-8(n≥4)和8n-24(n≥5).     

折叠交叉立方体的1-好邻诊断度

诊断度是多处理器系统互连网络能够诊断的最大故障结点的个数,它是度量多处理器系统故障诊断能力的一个重要参数.2012年,Peng等提出了一种新的诊断方法g-好邻诊断度,它要求每个非故障顶点至少有g个非故障邻点.n-维折叠交叉立方体网络FCQ_n是由交叉立方体网络CQ_n增加2^n-1条边后所得.该文利用1-好邻诊断度作为评价可靠性的重要度量,对折叠交叉立方体网络的可靠性进行分析,得到折叠交叉立方体网络的1-好邻诊断度.证明了在PMC模型与MM^*模型下FCQ_n的1-好邻诊断度分别等于2n+1,n≥5和2n+1,n≥6.     

一种基于PMC模型下的概率性矩阵诊断算法

系统级故障诊断是提高多处理器系统可靠性的必要手段。为了有效定位多处理系统中的故障单元,该文建立了一种基于PMC模型t可诊断条件下的概率性矩阵诊断算法。首先对一般概率性矩阵诊断算法进行仿真分析获悉其具有较高的误检率,在诊断过程中引进绝对故障基和节点集团思想,通过计算绝对故障基以寻找系统中的部分故障处理机,集团用于将不确定状态的节点单元分类以补充正常节点集合,改善了原诊断的限制条件。仿真实验验证:改进后的概率性矩阵诊断算法保持了很高的检测精度,并且随着节点数的增多极大地降低了误检率,提高了诊断效果,使得该算法具有广泛的适用性。     

修正泡型图的条件匹配排除

一个图G的条件匹配排除数是最少的边的数量,使得删去这些边后形成的图既没有孤立点也没有完美匹配和几乎完美匹配.任何一个这样的边集称为G的一个最优条件匹配排除集.条件匹配排除数是衡量网络在边故障情况下的鲁棒性的参数之一.主要给出了修正泡型图的条件匹配排除数是2n-2(n≥5).     

折叠超立方体的边邻域连通度

折叠超立方体是最受关注的网络模型之一.设e是图G的一条边, 如果从图G中删掉以e为中心的双星子图,则称e"倒戈".设S为一个边集, 如果S中的边全部倒戈, 若剩下的子图或者不连通, 或者是一个孤立点, 或者是空集, 则称S为G的割边策略.G的最小割边策略所含的边数为边邻域连通度.该文主要证明了折叠超立方体FQn的边邻域连通度为n.     

超立方体网络中基于LIP的广播容错路由算法

论文给出超立方体网络中的LIP容锆模型,基于该模型提出三个重要的性质定理,并给出超立方体网络中基于该模型的广播容错路由算法.该算法能容许大量的错误节点,且算法所需时间步仅与LIP节点数有关而与故障节点数无关,因此具有较大的优越性.     

缺边分裂星图在比较模型下的诊断性

多处理器系统的诊断性是一个重要的研究课题,系统的可诊断性是衡量互连网络容错性的重要指标.互连网络在多处理器系统中发挥着重要作用,且互连网络通常由一个图来表示,其节点(顶点)表示处理器,链路(边)表示处理器之间的通信链路.分裂星图S2n有许多良好的性质,本文研究了比较模型下S2n的诊断性.根据局部诊断性的概念,强局部诊断...     

h≥n/2的n阶极大临界h-连通图的特征

本文就h≥n/2的情形证明了H.J.krol和H.J.Veldman在文中提出的猜想:对一切h≥3都有,n阶级大临界h连通图中每一点都不得与一个h度顶点相邻,从而其边数为1/2其中k_n=[(h-1)/h]当n≠h mod 2h ((h-1)/h)n-1 当n=h mod 2h     

关于笛卡尔乘积图边容错直径的研究

笛卡尔乘积是从若干特定的小网络构造大网络的有效方法,边容错直径是衡量一个网络可靠性和效用性的重要标准,研究了笛卡尔乘积网络的边容错直径,并且得到了一个相关的结果.对任何t1,t2≥1,若G1,G2分别是t1边连通的和t2边连通的,则它们的笛卡尔乘积图的边容错直径D’t1+t2(G1×G2)≤D’t1(G1)+D’t2(G2)+1.并且,该不等式中的上界是最好的.     

关于图的符号边全控制

设γ’st(G)表示图G的符号边全控制数,给出了一般图G和超立方体的符号边全控制数的一个下界和一个上界,计算了等完全二部图的符号边全控制数的精确值。     

交叉立方体的可靠性分析（英文）

h-限制性边连通度是衡量大型互连网络可靠性和容错性的一个重要参数.交叉立方体网络是超立方体网络的一个变形,在平行计算系统当中交叉立方体网络是最重要的网络之一.该文研究了交叉立方体网络的限制性边连通度.