论文部分内容阅读
为提高结点不可靠网络的可靠度计算效率,提出一种基于子网同构判定的高效计算方法。在生成有序二元决策图(OBDD)的因子分解过程中,利用特征合并划分(CMP)识别网络分解产生的同构子网,然后根据网络中边和节点的逻辑联系,执行边替换操作将不可靠结点存储于OBDD;通过遍历OBDD计算网络的可靠度。结果显示,该方法减少了同构子网带来的重复计算,并充分利用OBDD的存储结构进一步增强了计算效率,计算中小型网络可靠度的时间保持在100 s以下,计算数百结点网络可靠度的时间保持在百秒级,且计算中大型网络的开销远低于标准二元决策图(BDD)方法。
In order to improve the computational efficiency of reliability of untrustworthy networks, an efficient computation method based on sub-network isomorphism is proposed. During the factorization process of generating the ordered binary decision diagram (OBDD), a feature isomorphic partition (CMP) is used to identify isomorphic subnets generated by network decomposition. Then according to the logical connection between edges and nodes in the network, the edge replacement operation is performed Unreliable nodes are stored in OBDD; the reliability of the network is calculated by traversing OBDD. The results show that this method reduces the repeated computation caused by isomorphic subnets and makes full use of the memory structure of OBDD to further enhance the computational efficiency. The time for calculating the reliability of small and medium networks remains below 100 s, and the calculation of hundreds of nodes The reliability time is kept at a hundred-second level, and the computation overhead of large networks is much lower than that of the standard binary decision graph (BDD) method.