作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2015, Vol. 41 ›› Issue (1): 87-91. doi: 10.3969/j.issn.1000-3428.2015.01.016

• 移动互联与通信技术 • 上一篇    下一篇

基于二元决策图的节点不可靠网络可靠度计算

肖宇峰a,b,张华a,b   

  1. 西南科技大学a.信息工程学院; b.特殊环境机器人技术四川省重点实验室,四川 绵阳 621010
  • 收稿日期:2014-01-20 修回日期:2014-03-20 出版日期:2015-01-15 发布日期:2015-01-16
  • 作者简介:肖宇峰(1978-),男,副研究员、博士,主研方向:网络通信,计算机系统可靠性评估;张 华,教授、博士。
  • 基金资助:
    国家核能开发科研基金资助项目([2011]1137);四川省科技支撑计划基金资助项目(2013GZX0152);四川省教育厅基金资助重点项目(14ZA0091)

Reliability Computation of Network with Unreliable Nodes Based on Binary Decision Diagram

XIAO Yufenga,b,ZHANG Huaa,b   

  1. a.Information Engineering School; b.Special Environment Robot Technology Key Laboratory of
    Sichuan Province,Southwest University of Science and Technology,Mianyang 621010,China
  • Received:2014-01-20 Revised:2014-03-20 Online:2015-01-15 Published:2015-01-16

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

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

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

中图分类号: