Abstract: According to the inefficient reliability computation of network with unreliable nodes,this paper proposes a network reliability computation method based on Binary Decision Diagram(BDD).After the Ordered Binary Decision Diagram(OBDD) construction with factoring theorem,this method executes the edge replacements to OBDD variables of edges with the relation between nodes and edges,and the OBDD of network with unreliable nodes is constructed.Based on efficient OBDD structure,the computations about unreliable nodes are improved.Furthermore,a hash table is used to avoid the repeated access to same node when the reliability is calculated with OBDD traversal.Therefore,the redundant calculations are reduced,and the reliability computation efficiency of network with unreliable nodes is enhanced.Experiments are arranged on benchmark networks,and data analysis shows that this method can accurately calculate network reliability and quickly analyze some large networks.

Key words: network reliability, Binary Decision Diagram(BDD), unreliable node, factoring, Boolean variable

摘要： 针对节点不可靠网络可靠度计算效率较低的问题,提出一种基于二元决策图的网络可靠度计算方法。通过因子分解得到节点可靠网络的有序二元决策图(OBDD),根据节点和边的关系对边的变量节点执行边替换操作,生成节点不可靠网络的OBDD,并利用其高效存储结构提高不可靠节点的处理效率。在遍历OBDD计算可靠度时,引入Hash表以避免对同一节点的重复访问,从而减少冗余计算,进一步提高计算效率。在基准网络中的对比实验结果表明,该方法不仅能正确计算网络可靠度,而且能快速分析大型网络。

关键词: 网络可靠度, 二元决策图, 不可靠节点, 因子分解, 布尔变量

CLC Number: 

• TP393