• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Reliability Engineering & System Safety >Efficient construction of binary decision diagrams for network reliability with imperfect vertices
【24h】

Efficient construction of binary decision diagrams for network reliability with imperfect vertices

机译：具有不完美顶点的网络可靠性的二进制决策图的高效构造

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

This paper discusses evaluation of the network reliability with imperfect vertices, which computes the probability that a subset of nodes is communicable under possible failures of links and nodes. Although the network reliability is efficiently computed utilizing a binary decision diagram (BDD) if assuming link failures only, it can be 10 times slower if considering node failures as well. This is because existing algorithms are designed to repeatedly update a BDD for every node failure in a step-by-step manner. This research proposes an algorithm that creates the final BDD without the redundant repetitions, which greatly improves the computation efficiency. Moreover, this paper presents a better variable order of BDDs among variables corresponding to links and nodes. Under the variable order, the proposed algorithm is compared with existing ones by numerical experiments using various benchmark networks including real communication networks. The results show that the proposed algorithm runs 198.2 times faster than the existing ones for the 10-by-10 grid graph, 1074.6 times faster for the complete graph with 12 vertices, and 65.6 times faster for some well-known benchmark network. For some network instances, the proposed variable order reduces the number of BDD nodes by 15-38% compared with the existing order. This paper reveals that considering imperfect vertices does not impose significant performance overheads.
机译：本文讨论了具有不完美顶点的网络可靠性评估，该评估计算了在链路和节点可能出现故障的情况下节点子集可通信的概率。尽管仅假设链路故障，利用二进制决策图（BDD）可以有效地计算网络可靠性，但是如果考虑节点故障，网络可靠性可能会慢10倍。这是因为现有算法旨在逐步为每个节点故障重复更新BDD。这项研究提出了一种算法，该算法可以创建没有冗余重复的最终BDD，从而大大提高了计算效率。此外，本文提出了与链接和节点相对应的变量中BDD的更好的变量顺序。在可变阶数下，使用包括实际通信网络在内的各种基准网络，通过数值实验将所提出的算法与现有算法进行比较。结果表明，对于10×10网格图，该算法的运行速度比现有算法快198.2倍；对于具有12个顶点的完整图，该算法的运行速度为1074.6倍；对于某些知名基准网络，该算法的运行速度为65.6倍。对于某些网络实例，与现有顺序相比，建议的可变顺序将BDD节点的数量减少了15-38％。本文揭示了考虑不完美的顶点不会带来明显的性能开销。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号