摘要
节点或边不可靠网络的可靠度分析问题是NP-hard问题,网络节点和边都不可靠的假设更接近现实。基于网络节点和边二元状态的假设,构建了节点和边不可靠网络的形式化模型,给出了分析节点和边不可靠网络可靠度的NEF_MDD算法。该算法将单个节点与其未访问邻接边划分为一个集合,通过枚举节点和边的不同组合,合并导致子网同构的冗余状态,获得简化后的状态向量和可靠度向量,并用一个多值决策图变量来表述。通过使用自定义的MDD操作算子,构建整个网络的MDD,遍历MDD节点,计算网络的可靠度。与二元决策图方法相比,该方法能够降低决策图层数和节点规模,有助于节点和边不可靠网络的可靠度分析。
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-visited 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.
出处
《计算机科学》
CSCD
北大核心
2016年第1期154-158,共5页
Computer Science
基金
国家自然科学基金(61363070)
广西可信软件重点实验室资助课题(kx201401)
广西高等学校高水平创新团队及卓越学者计划
桂林电子科技大学创新团队资助
关键词
多值决策图
网络可靠度
不可靠节点
不可靠边
Multi-valued decision diagram
Network reliability
Imperfect nodes
Imperfect edge
