基于同构子网判定的结点不可靠网络可靠度计算方法

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

Evaluation of Reliability of Network with Unreliable Nodes Based on Isomorphism

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.