To improve the efficiency in evaluating the reliability of a network with unreliable nodes, this paper proposes a computation method based on isomorphism determination. In analyzing the reliability, the CMP (characteristic mergence partition) is used to identify the isomorphic subnet generated by the network decomposition; the edge replacement operations are used to store unreliable nodes into the OBDD (ordered binary decision diagram). Not only the repeated computations from isomorphic subnets are reduced, but also the computation efficiency is enhanced by the efficient OBDD storage. On the experiment platform, this method takes less than 100 seconds for small and medium networks, and several hundreds seconds for networks with hundreds of nodes. Experiments show that this method can accurately evaluate the network reliability, and takes less than one-tenth time taken by the standard BDD (binary decision diagram) method for medium and large networks.
XIAO Yufeng
. Evaluation of Reliability of Network with Unreliable Nodes Based on Isomorphism[J]. Science & Technology Review, 2014
, 32(16)
: 39
-44
.
DOI: 10.3981/j.issn.1000-7857.2014.16.006
[1] Ball M O, Magnanti T L, Monma C L, et al. Network Models, volume 7 of Handbooks in operations research and management science[J]. Elservier Science Publishing Company, 1995(12): 2-7.
[2] 吴俊, 段东立, 赵娟. 网络系统可靠性研究现状与展望[J]. 复杂系统与 复杂性科学, 2011, 8(2): 77-86. Wu Jun, Duan Dongli, Zhao Juan. Status and prospects on network reliability[J]. Complex Systems and Complexity Science, 2011, 8(2): 77-86.
[3] 江逸楠, 李瑞莹, 黄宁. 网络可靠性评估方法综述[J]. 计算机科学, 2012, 39(5): 9-13. Jiang Yinan, Li Ruiying, Huang Ning. Survey on network reliability evaluation methods[J]. Computer Science, 2012, 39(5): 9-13.
[4] Xing L. An efficient binary-decision-diagram-based approach for network reliability and sensitivity analysis[J]. Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on, 2008, 38(1): 105-115.
[5] Singhal M. An alternate approach to compute the reliability of a network with imperfect nodes using binary decision diagrams[J]. Oriental Journal of Computer Science & Technology, 2012, 5(2): 181-188.
[6] Kuo S Y, Yeh F M, Lin H Y. Efficient and exact reliability evaluation for networks with imperfect vertices[J]. Reliability, IEEE Transactions on, 2007, 56(2): 288-300.
[7] Rodionov A, Migov D, Rodionova O. Improvements in the efficiency of cumulative updating of all-terminal network reliability[J]. Reliability, IEEE Transactions on, 2012, 61(2): 460-465.
[8] Kim Y, Kang W H. Network reliability analysis of complex systems using a non-simulation-based method[J]. Reliability Engineering & System Safety, 2013, 110(1): 80-88.
[9] Lin Y K, Chang P C. Maintenance reliability of a computer network with nodes failure in the cloud computing environment[J]. International Journal of Innovative Computing, Information and Control, 2012, 8(6): 4045-4058.
[10] Lin Y K, Chang P C. A novel reliability evaluation technique for stochastic-flow manufacturing networks with multiple production lines[J]. Reliability, IEEE Transactions on, 2013, 62(1): 92-104.
[11] Imai H, Sekine K, Imai K. Computational investigations of all-terminal network reliability via BDDs[J]. Transactions on Fundamentals, 1999, 82 (5): 714-721.
[12] Hardy G, Lucet C, Limnios N. K-terminal network reliability measures with binary decision diagrams[J]. Reliability, IEEE Transactions on, 2007, 56(3): 506-515.
[13] Andersen H R. An introduction to binary decision diagrams[M]. Amsterdam: Elsevier, 1997.
