分层超立方网络的可靠性评估

doi:10.11959/j.issn.1000-436x.2021064

通信学报 ›› 2021, Vol. 42 ›› Issue (3): 111-121.doi: 10.11959/j.issn.1000-436x.2021064

分层超立方网络的可靠性评估

刘西蒙¹^,², 张郁芳¹^,², 周书明³, 李小燕¹^,²

¹ 福州大学数学与计算机科学学院，福建福州 350108
² 福州大学网络安全福建省高校重点实验室，福建福州 350108
³ 福建师范大学数学与信息学院，福建福州 350007

修回日期:2020-12-16 出版日期:2021-03-25 发布日期:2021-03-01
作者简介:刘西蒙（1988- ），男，陕西西安人，博士，福州大学研究员，主要研究方向为隐私计算、密文数据挖掘、大数据隐私保护、可搜索加密等。
张郁芳（1997- ），女，湖南岳阳人，福州大学硕士生，主要研究方向为互连网络的故障诊断、网络安全等。
周书明（1972- ），男，湖北麻城人，博士，福建师范大学教授，主要研究方向为图论与网络优化、并行分布式计算、故障诊断及检测、容错计算等。
李小燕（1989- ），女，福建福州人，博士，福州大学讲师，主要研究方向为数据中心网络、网络安全、算法设计与分析等。
基金资助:
国家自然科学基金资助项目(62002062);国家自然科学基金资助项目(62072109);福建省教育厅中青年教师教育科研基金资助项目(JAT190031)

Reliability evaluation of hierarchical hypercube network

Ximeng LIU¹^,², Yufang ZHANG¹^,², Shuming ZHOU³, Xiaoyan LI¹^,²

¹ College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108, China
² Fujian Provincial Key Laboratory of Information Security of Network Systems, Fuzhou University, Fuzhou 350108, China
³ School of Mathematics and Information, Fujian Normal University, Fuzhou 350007, China

Revised:2020-12-16 Online:2021-03-25 Published:2021-03-01
Supported by:
The National Natural Science Foundation of China(62002062);The National Natural Science Foundation of China(62072109);Education and Scientic Research Project of Young and Middle-aged Teachers of Fujian Provincial Education Department(JAT190031)

摘要/Abstract

摘要：

针对目前关于分层超立方网络的可靠性研究不够系统，严重制约了其应用和推广的问题，以分层超立方网络为研究对象，在得到分层超立方网络相关拓扑性质的基础上，通过理论推导得到了n维分层超立方（HHC_n）在PMC模型和MM*模型下的h-额外条件诊断度和t/s-诊断度。此外，设计了HHC_n在PMC模型和MM*模型下的t/s-诊断算法，并分析了其时间复杂度。研究结果表明，HHC_n的h-额外条件诊断度是其传统诊断度的约h+1倍， t/s-诊断度是其传统诊断度约 s+1 倍。该结果进一步完善了分层超立方网络的可靠性指标，为其应用和推广提供了重要的理论依据。

关键词: h?额外条件诊断度, t/s?诊断度, t/s?诊断算法, 分层超立方网络, 可靠性

Abstract:

Aiming at the problem that the reliability research on hierarchical hypercube networks was not yet systematic, which severely restricted its application and popularization, the hierarchical hypercube network was taken as studying object, on the basis of obtaining the relevant topological properties of the hierarchical hypercube network, the h-extra conditional diagnosability and t/s-diagnosability of the n-dimension hierarchical hypercube (HHC_n) network under the PMC model and MM* model were obtained by theoretical deduction.In addition, the t/s-diagnosis algorithm of HHC_n under the PMC model and MM* model was designed and its time complexity was analyzed.The research results show that the h-extra conditional diagnosability of HHC_n is about h+1 times of its traditional diagnosability, and the t/s-diagnosability of HHC_n is about s+1 times of its traditional diagnosability.Those results improve the reliability index of the hierarchical hypercube network and provide an important theoretical basis for its application and popularization.

Key words: h-extra conditional diagnosability, t/s-diagnosability, t/s-diagnosis algorithm, hierarchical hypercube network, reliability

中图分类号:

TP301

刘西蒙, 张郁芳, 周书明, 李小燕. 分层超立方网络的可靠性评估[J]. 通信学报, 2021, 42(3): 111-121.

Ximeng LIU, Yufang ZHANG, Shuming ZHOU, Xiaoyan LI. Reliability evaluation of hierarchical hypercube network[J]. Journal on Communications, 2021, 42(3): 111-121.

图/表 6

图1

图2

图3

图4

图5

图6

参考文献 27

[1]	PREPARATA F P , METZE G , CHIEN R T . On the connection assignment problem of diagnosable systems[J]. IEEE Transactions on Electron Devices, 1967,16(6): 848-854.
[2]	MAENG M , MALEK M . A comparison connection assignment for diagnosis of multiprocessor systems[C]// Proceedings of the 11th International Fault-Tolerant Computing. New York:ACM Press, 1981: 173-175.
[3]	SENGUPTA A , DAHBURA A T . On self-diagnosable multiprocessor systems:diagnosis by the comparison approach[J]. IEEE Transactions on Computers, 1992,41(11): 1386-1396.
[4]	ZHANG S R , YANG W H . The g-extra conditional diagnosability and t/k-diagosability of hypercubes[J]. International Journal of Computer Mathematics, 2016,93(3): 482-497.
[5]	LIN L M , XU L , CHEN R Q ,et al. Relating extra connectivity and extra conditional diagnosability regular networks[J]. IEEE Transactions on Dependable and Secure Computing, 2019,16(6): 1086-1097.
[6]	HUANG Y Z , LIN L M , XU L ,et al. Extra diagnosability and good-neighbor diagnosability of n-dimensional alternating group graph AG_nunder the PMC model[J]. Theoretical Computer Science, 2019,795: 36-49.
[7]	LIU H Q , ZHANY S Z , LI D . On g-extra conditional diagnosability of hierarchical cubic networks[J]. Theoretical Computer Science, 2019,790: 66-79.
[8]	LYU M J , FAN J X , ZHOU J Y ,et al. The extra connectivity and extra diagnosability of regular interconnection networks[J]. Theoretical Computer Science, 2020,809: 88-102.
[9]	SUN X L , ZHOU S M , GU Z D ,et al. Reliability evaluation of complete cubic networks[J]. International Journal of Parallel,Emergent and Distributed Systems, 2020,35(1): 42-56.
[10]	SOMANI A K , PELEG O . On diagnosability of large fault sets in regular topology-based computer systems[J]. IEEE Transactions on Computers, 1996,45(8): 892-903.
[11]	FAN J X , LIN X L . The t/k-diagnosability of the BC graphs[J]. IEEE Transactions on Computers, 2005,54(2): 176-184.
[12]	YANG X F , TANG Y Y . A (4n-9)/3-diagnosis algorithm on n-dimensional cube network[J]. Information Sciences, 2007,177(8): 1771-1781.
[13]	ZHOU S M , LIN L M , XU L ,et al. The t/k-diagnosability of star graph networks[J]. IEEE Transactions on Computers, 2015,64(2): 547-555.
[14]	LIN L M , XU L , ZHOU S M ,et al. The t/k-diagnosability for regular networks[J]. IEEE Transactions on Computers, 2016,65(10): 3157-3170.
[15]	LIANG J R , ZHANG Q . The t/s-diagnosability of hypercube networks under the PMC and comparison models[J]. IEEE Access, 2017,5: 5340-5346.
[16]	XIE M , YE L C , LIANG J R . A t/k-diagnosis algorithm on hypercube-like networks[J]. Concurrency and Computation:Practice and Experience, 2018,30(6): 1-8.
[17]	LI X Y , JIA X H , FAN J X ,et al. Reliability analysis of data center networks based on precise and imprecise diagnosis strategies[J]. Theoretical Computer Science, 2020,809: 189-203.
[18]	MALLUHI Q M , BAYOUMI M A . The hierarchical hypercube:a new interconnection topology for massively parallel systems[J]. IEEE Transactions on Parallel and Distributed Systems, 1994,5(1): 17-30.
[19]	XU J M . Topological structure and analysis of interconnection networks[M]. Berlin: Springer, 2013.
[20]	DAHBURA A T , MASSON G M . An O(n^2.5) faulty identification algorithm for diagnosable systems[J]. IEEE Transactions on Computers, 1984,33(6): 486-492.
[21]	PREPARATA F P , VUILLEMIN J . The cube-connected-cycles:a versatile network for parallel computation[J]. Communications of the ACM, 1981,24(5): 300-309.
[22]	LI X Y , LIN C K , FAN J X ,et al. Relationship between extra connectivity and component connectivity in networks[J]. The Computer Journal, 2021,64(1): 38-53.
[23]	ZHOU S M , LIN L M , XU J M . Conditional fault diagnosis of hierarchical hypercubes[J]. International Journal of Computer Mathematics, 2012,89(16): 2152-2164.
[24]	YANG W H , MENG J X . Extraconnectivity of hypercubes[J]. Applied Mathematics Letters, 2009,22(6): 887-891.
[25]	CHENG E , QIU K , SHEN Z Z . The h-extra diagnosability of the generalized exchanged hypercube[J]. International Journal of Computer Mathematics:Computer Systems Theory, 2020,5(2): 112-123.
[26]	郭晨, 肖志芳, 冷明 ,等. 交换交叉立方网络在PMC模型下的(t,k)诊断度研究[J]. 通信学报, 2019,40(6): 190-202.
	GUO C , XIAO Z F , LENG M ,et al. (t,k)-diagnosability of exchanged crossed cube under the PMC model[J]. Journal on Communications, 2019,40(6): 190-202.
[27]	熊茜, 梁家荣, 马强 . 交换超立方网络的 (t,k)-诊断度研究[J]. 通信学报, 2016,37(3): 190-198.
	XIONG X , LIANG J R , MA Q . Research on (t,k)-diagnosability for exchanged hypercube network[J]. Journal on Communications, 2016,37(3): 190-198.

分层超立方网络的可靠性评估

Reliability evaluation of hierarchical hypercube network

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 27

相关文章 15

Metrics

推荐阅读 0

[1]	张朝阳, 吴佳佳, 王珏, 周楚. 联合时域-波束域非正交多址接入[J]. 通信学报, 2021, 42(4): 76-88.
[2]	徐朝农,吴建雄,徐勇军. 时延有界的PD-NOMA物联网高可靠接入算法[J]. 通信学报, 2020, 41(9): 210-221.
[3]	王汝言,高毅爽,陈霄. 带有区分保护的虚拟化FiWi网络可靠传输机制[J]. 通信学报, 2019, 40(3): 36-47.
[4]	兰巨龙,金子晋,孙鹏浩,江逸茗,王月. 基于可靠性的服务功能链构建算法[J]. 通信学报, 2019, 40(1): 64-70.
[5]	王哲,李陶深,叶进,葛志辉,吴敏. 基于不确定理论的能量收集可靠性建模及规划[J]. 通信学报, 2018, 39(5): 166-176.
[6]	程子敬,赵俊楠,崔玉文,石乐义. 基于纳什议价解的地外驻留平台网络可靠性与效用代价分析[J]. 通信学报, 2017, 38(2): 10-15.
[7]	胡涛,张建辉,马腾,赵伟. SDN中基于可靠性评估的多控制器均衡部署策略[J]. 通信学报, 2017, 38(11): 188-198.
[8]	石悦,邱雪松,郭少勇,亓峰. 基于改进遗传算法的电力光传输网规划方法[J]. 通信学报, 2016, 37(1): 116-122.
[9]	胡国兵,徐立中,鲍安平,吴珊珊,高燕. 基于LMP检验的正弦波频率估计可靠性评估[J]. 通信学报, 2015, 36(5): 89-97.
[10]	黄昌勤，李源，吴洪艳，汤庸，罗旋. 云存储系统中数据副本服务的可靠性保障研究[J]. 通信学报, 2014, 35(10): 11-97.
[11]	黄昌勤,李源,吴洪艳,汤庸,罗旋. 云存储系统中数据副本服务的可靠性保障研究[J]. 通信学报, 2014, 35(10): 89-97.
[12]	陈权，高宏. RSPEED：无线传感器网络中基于不确定延迟的可靠实时路由[J]. 通信学报, 2013, 34(8): 15-119.
[13]	陈权,高宏. RSPEED：无线传感器网络中基于不确定延迟的可靠实时路由[J]. 通信学报, 2013, 34(8): 110-119.
[14]	项菲,刘川意,方滨兴,王春露,钟睿明. 新的基于云计算环境的数据容灾策略[J]. 通信学报, 2013, 34(6): 92-101.
[15]	项菲1,2，刘川意2,3，方滨兴1,2，王春露1,2，钟睿明1,2. 新的基于云计算环境的数据容灾策略[J]. 通信学报, 2013, 34(6): 11-101.