概率故障条件下平衡超立方体的子网络可靠性  

Subnetwork reliability of balanced hypercubes under probabilistic fault condition

作　　者：冯凯[1] 高红艳 FENG Kai;GAO Hongyan(School of Computer and Information Technology,Shanxi University,Taiyuan Shanxi 030006,China)

机构地区：[1]山西大学计算机与信息技术学院,太原030006

出　　处：《计算机应用》2024年第S01期175-182,共8页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61502286);山西省基础研究计划项目(20210302123438)。

摘　　要：平衡超立方体具有许多优良的拓扑结构性质,较适合用于构建实际多处理器系统。在发生故障的互连网络中对无故障子网络的存在性进行量化评估有重要的现实意义。为了刻画n维平衡超立方体中(n-1)维平衡超立方体子网络存在性的保持能力,在概率故障条件下估计了n维平衡超立方体中无故障(n-1)维平衡超立方体子网络的存在概率。对于不小于3的n,得出了n维平衡超立方体中存在无故障(n-1)维平衡超立方体子网络的概率的一个上界和一个下界,并给出了这一子网络可靠性的基于蒙特卡洛仿真的近似评估算法。结果表明,当无故障(n-1)维平衡超立方体子网络的存在概率的上下界相差不大时,该上下界和近似结果是一致的;否则近似结果是较为准确的。The balanced hypercube possesses many excellent topological structure properties,and it is relatively suitable to be used for building multiprocessor systems.In a faulty interconnection network,quantitative evaluation of existing some fault-free subnetworks in the interconnection network has important practical significance.In order to characterize the maintenance ability of existing(n-1)dimensional balanced hypercube subnetworks in an n dimensional balanced hypercube,the probability that at least one(n-1)dimensional balanced hypercube subnetwork was fault-free in an n dimensional balanced hypercube under the probabilistic fault condition was estimated.For n not less than three,an upper bound and a lower bound on the probability of existing fault-free(n-1)dimensional balanced hypercube subnetworks in an n dimensional balanced hypercube were obtained,and an approximate evaluation algorithm based on Monte Carlo simulation for calculating this subnetwork reliability was proposed.The results show that the upper and lower bounds on the probability of existing fault-free(n-1)dimensional balanced hypercube subnetworks are consistent with the approximate results when the difference between the upper and lower bounds is not large,otherwise the approximate results are relatively accurate.

关 键 词：互连网络 图 平衡超立方体 子网络 概率故障 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]