计算节点不可靠网络可靠度的一种MDD算法

发布时间：2018-01-19 21:19

本文关键词： 多值决策图网络可靠度不可靠节点不可靠边　出处：《计算机科学》2016年01期 　论文类型：期刊论文

【摘要】：节点或边不可靠网络的可靠度分析问题是NP-hard问题,网络节点和边都不可靠的假设更接近现实。基于网络节点和边二元状态的假设,构建了节点和边不可靠网络的形式化模型,给出了分析节点和边不可靠网络可靠度的NEF_MDD算法。该算法将单个节点与其未访问邻接边划分为一个集合,通过枚举节点和边的不同组合,合并导致子网同构的冗余状态,获得简化后的状态向量和可靠度向量,并用一个多值决策图变量来表述。通过使用自定义的MDD操作算子,构建整个网络的MDD,遍历MDD节点,计算网络的可靠度。与二元决策图方法相比,该方法能够降低决策图层数和节点规模,有助于节点和边不可靠网络的可靠度分析。
[Abstract]:The reliability analysis problem of nodes or edge unreliable networks is a NP-hard problem. The assumption that both nodes and edges are unreliable is closer to reality, and it is based on the assumption of network nodes and edge binary states. The formal model of node and edge unreliable network is constructed. The NEF_MDD algorithm for analyzing the reliability of nodes and edge unreliable networks is presented. The algorithm divides a single node and its unvisited adjacent edges into a set and enumerates different combinations of nodes and edges. The redundant state of subnet isomorphism is combined to obtain the simplified state vector and reliability vector, and to express them with a multi-valued decision graph variable. By using the custom MDD operator. The MDD of the whole network is constructed, the MDD nodes are traversed, and the reliability of the network is calculated. Compared with the binary decision graph method, this method can reduce the number of decision layers and the scale of nodes. It is helpful to the reliability analysis of node and edge unreliable networks.
【作者单位】：桂林电子科技大学广西可信软件重点实验室;
【基金】：国家自然科学基金(61363070) 广西可信软件重点实验室资助课题(kx201401) 广西高等学校高水平创新团队及卓越学者计划桂林电子科技大学创新团队资助
【分类号】：TP393.02
【正文快照】： 行不交化处理求解网络的可靠度。文献[2,3]需要找出网络1　引言的所有最小路径,这是一个NP-hard问题[2,10]。同时,容斥原网络可靠度分析是网络设计、验证和维护阶段的一个关理在扩展过程中会生成很多相互抵消的项,导致冗余计键问题,广泛应用于无线传感器网络、随机流网络等领

【相似文献】