一种基于有序二元决策图和布尔函数性质计算网络可靠性的算法  

A Novel Network Reliability Evaluating Algorithm with Ordered Binary Decision Diagram Based on Boolean Function

作　　者：熊飞[1] 乔迪[2] 王宏祥[2] 赵子岩[1] 杨洪[1] 沈亮[1] 

机构地区：[1]国家电网公司信息通信分公司,北京100761 [2]北京邮电大学信息与通信工程学院,北京100876

出　　处：《电子与信息学报》2014年第11期2786-2790,共5页Journal of Electronics & Information Technology

基　　金：国家863计划项目(2012AA011302);国家科技重大专项(2012ZX 03003007);国家电网公司科技项目(SGIT2012335)资助课题

摘　　要：有序二元决策图(OBDD)被广泛用到网络可靠度的计算中,在基于OBDD计算网络可靠度时,其计算时间主要取决于参与操作的OBDD的大小,而OBDD的大小严重依赖于OBDD的变量序。该文根据布尔函数的性质和OBDD原理提出一种优化计算网络可靠性的算法(BF-OBDD),提高计算网络可靠性的效率。实验结果表明改进的算法有较少的OBDD节点数量,在计算网络可靠性时,花费的时间较少。Ordered Binary Decision Diagram （OBDD） is commonly used in network reliability calculation. When evaluating the network reliability based on OBDD, computation time mainly depends on the size of the operating OBDD, which mostly relies on the variable ordering of OBDD. An algorithm is called BF-OBDD which is considered as the Boolean Function-OBDD, and it is the optimization algorithm for computing the reliability of the network. This paper shows that the reliability of network can be improved considerably by using of the proposed BF-OBDD algorithm. The experimental results demonstrate that the improved algorithm has less OBDD node numbers which cost less time when calculating the network reliability.

关 键 词：计算机网络 可靠性 网络拓扑图 有序二元决策图 变量序 布尔函数 

分 类 号：TN915[电子电信—通信与信息系统]