PMC模型下的h-边容错诊断数

发布时间：2021-12-11 17:20

　　系统级诊断是多处理器系统设计和维护中的重要方面,通过诊断参数来衡量系统的容错性能。传统的诊断参数都是在假设系统中仅有处理器发生故障的情形下得到的,但是在实际情形中,系统中的处理器和链接都可能发生故障。该文研究了新的系统级诊断参数—h-边容错诊断数。当系统G中的故障边数不超过h时,G中包含的可以被全部识别的最大故障点数称为系统G的h-边容错诊断数。通过对一般图中公共邻点数的限制,证明了PMC模型下一般图的h边容错诊断数。文中确定了k-元n-方体、平衡立方体、交换立方体和交换折叠立方体4类网络在PMC模型下的h-边容错诊断数,为衡量系统在点边混合故障情形下的容错性能提供了有效参数。 

【文章来源】：西北大学学报(自然科学版). 2020,50(05)北大核心CSCD

【文章页数】：6 页

【部分图文】：

F1,F2可区分的两种情形

假设u∈V满足d(u)=δ(G),u的邻点集合为NG(u)={u1,u2,…,uδ(G)}。令F1={uh+1,uh+2,…,uδ(G)},F2={u,uh+1,…,uδ(G)},Fe={uu1,uu2,…,uuh}(见图2)。显然,|F1|=δ(G)-h,|F2|=δ(G)-h+1,|Fe|=h且F1ΔF2={u}。因为G-Fe中不存在V-(F1∪F2)和F1ΔF2之间的边,由引理1得,F1和F2在G-Fe中是不可区分的。因此,在PMC模型中,t h e (G)≤max{|F1|,|F2|}-1=δ(G)-h。引理3 在PMC模型中,若图G=(V,E)满足nc(G)≤δ(G)-h-2,则t h e (G)≥δ(G)-h,其中, 1 2 δ(G)≤h≤δ(G)-1 。

不失一般性,令|F1-F2|=1,|F2-F1|=0。假设F1-F2={u}。对任意一点v∈Nv-F1∪F2(u),因为F1和F2在G-Fe中是不可区分的,由引理2可得,uv∈Fe(见图3)。因为|Fe|≤h,所以u至少有δ(u)-h个邻点在F2中,即|F2|≥δ(G)-h。因此,|F1|=|F2∪{u}|=δ(G)-h+1与|F1|≤δ(G)-h是矛盾的。情况2 |F1-F2|=1且|F2-F1|=1。

【参考文献】：
期刊论文
[1]交换折叠超立方体的连通度[J]. 蔡学鹏,杨伟,任佰通,冯苗苗.  井冈山大学学报(自然科学版). 2019(04)
[2]k元n立方体的条件容错强Menger边连通性[J]. 翟登鑫.  沈阳大学学报(自然科学版). 2019(02)
[3]平衡立方体的h-额外连通度及h-额外条件诊断数[J]. 张兴,李莉莉,陈敬,李巧萍.  高校应用数学学报A辑. 2019(01)
[4]交错群图AGn的5类子图可靠性研究[J]. 谭秋月.  西南师范大学学报(自然科学版). 2017(11)



本文编号：3535075