计算机科学 ›› 2016, Vol. 43 ›› Issue (1): 154-158.doi: 10.11896/j.issn.1002-137X.2016.01.035
王泓刚,董荣胜,钱俊彦
WANG Hong-gang, DONG Rong-sheng and QIAN Jun-yan
摘要： 节点或边不可靠网络的可靠度分析问题是NP-hard问题,网络节点和边都不可靠的假设更接近现实。基于网络节点和边二元状态的假设,构建了节点和边不可靠网络的形式化模型,给出了分析节点和边不可靠网络可靠度的NEF_MDD算法。该算法将单个节点与其未访问邻接边划分为一个集合,通过枚举节点和边的不同组合,合并导致子网同构的冗余状态,获得简化后的状态向量和可靠度向量,并用一个多值决策图变量来表述。通过使用自定义的MDD操作算子,构建整个网络的MDD,遍历MDD节点,计算网络的可靠度。与二元决策图方法相比,该方法能够降低决策图层数和节点规模,有助于节点和边不可靠网络的可靠度分析。
| [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! |
|
||
首页