为提高结点不可靠网络的可靠度计算效率，提出一种基于子网同构判定的高效计算方法。在生成有序二元决策图（OBDD）的因子分解过程中，利用特征合并划分（CMP）识别网络分解产生的同构子网，然后根据网络中边和节点的逻辑联系，执行边替换操作将不可靠结点存储于OBDD；通过遍历OBDD 计算网络的可靠度。结果显示，该方法减少了同构子网带来的重复计算，并充分利用OBDD 的存储结构进一步增强了计算效率，计算中小型网络可靠度的时间保持在100 s 以下，计算数百结点网络可靠度的时间保持在百秒级，且计算中大型网络的开销远低于标准二元决策图（BDD）方法。
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.
[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.
