Computer Science ›› 2016, Vol. 43 ›› Issue (1): 154-158.doi: 10.11896/j.issn.1002-137X.2016.01.035

Previous Articles     Next Articles

Novel Reliability Analysis Algorithm Based on MDDs in Networks with Imperfect Nodes

WANG Hong-gang, DONG Rong-sheng and QIAN Jun-yan   

  • Online:2018-12-01 Published:2018-12-01

Abstract: The reliability of networks with imperfect nodes or edges is an NP-hard problem,and the assumption of networks with imperfect nodes and edges is closer to real life.A formal model of networks with binary state nodes and edges was constructed,and a novel network reliability analysis algorithm was proposed.Any node and its adjacent non-visi-ted edges’ combination states are enumerated to merge isomorphic sub-networks.Then,a MDD variable is used to represent the reduced state vector and corresponding probability vector.Finally,the MDD representing for the network is constructed by a custom operation.Experiment shows that the level and size of decision diagram generated by the proposed algorithm are less than the corresponding binary decision diagram.

Key words: Multi-valued decision diagram,Network reliability,Imperfect nodes,Imperfect edge

[1] Ball M O.Complexity of network reliability computations[J].Networks,1980,0(2):153-165
[2] Lin Y K.A simple algorithm for reliability evaluation of a stochastic-flow network with node failure[J].Computers & Operations Research,2001,28(13):1277-1285
[3] Lin Y K,Huang C F.Assessing reliability within error rate and time constraint for a stochastic node-imperfect computer network[J].Proceedings of the Institution of Mechanical Engineers Part O-Journal of Risk and Reliability,2013,227:80-85
[4] Yan Zong-shuai,Nie Chen-hua,Dong Rong-sheng,et al.A NovelOBDD-Based Reliability Evaluation Algorithm for Wireless Sensor Networks on the Multicast Model[J].Mathematical Pro-blems in Engineering,2015,2015:1-14
[5] Kuo S Y,Yeh F M,Lin H Y.Efficient and exact reliability eva-luation for networks with imperfect vertices[J].IEEE Trans.Reliability,2007,56(2):288-300
[6] Jiang Yi-nan,Li Rui-ying,Huang Ning,et al.Survey on network reliability evaluation methods[J].Computer Science,2012,9(5):9-13(in Chinese) 江逸楠,李瑞莹,黄宁,等.网络可靠性评估方法综述[J].计算机科学,2012,9(5):9-13
[7] Theologou O R,Carlier J G.Factoring and reductions for networks with imperfect vertices[J].IEEE Trans.Reliability,1991,40(2):210-217
[8] Sun Yan-rui,Cui Li-yan,Zhang De-xiang.A factoring algorithm for reliability evaluation of distributed networks with imperfect nodes[J].Computer Science,2002,29(4):111-113(in Chinese)孙艳蕊,崔立彦,张祥德.计算具有不可靠结点分布式网络可靠度的一个因子分解算法[J].计算机科学,2002,29(4):111-113
[9] Xiao Yu-feng.Reliability analysis of two terminals networkbased on discrete probability model [D].Beijing:Beijing University of Posts and Telecommunications,2009(in Chinese)肖宇峰.基于离散概率模型的二端网络可靠性分析[D].北京:北京邮电大学,2009
[10] Yeh W C.A simple heuristic algorithm for generating all minimal paths[J].IEEE Transactions on Reliability, 2007,56(3):488-494
[11] Sun Yan-rui.Reliability evaluation of stochastic-flow networkunder both time and cost constraints[J].Journal of Northeastern University (Natural Science),2013,1(34):1537-1541(in Chinese)孙艳蕊.带时间和成本约束的随机流网络可靠度的计算[J].东北大学学报(自然科学版),2013,1(34):1537-1541
[12] Nagayama S,Sasao T.On the optimization of heterogeneousMDDs[J].IEEE Trans.Computer-Aided Design of Integrated Circuits and Systems,2005,24(11):1645-1659
[13] Xing L,Dai Y.A new decision-diagram-based method for efficient analysis on multistate systems[J].IEEE Transactions on Dependable and Secure Computing,2009,6(3):161-174
[14] Herrmann J U,Soh S,West G,et al.Using Multi-valued Decision Diagrams to Solve the Expected Hop Count Problem[C]∥The IEEE 23rd International Conference on Advanced Information Networking and Applications(AINA 2009).Bradford,Uni-ted Kingdom,2009:419-424
[15] Bollig B,Wegener I.Improving the variable ordering of OBDDs is NP-complete[J].IEEE Trans.Computers,1996,45:993-1002

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .