Efficient construction of binary decision diagrams for network reliability with imperfect vertices
Efficient construction of binary decision diagrams for network reliability with imperfect vertices
复制标题
DOI：
10.1016/j.ress.2019.03.026
复制
发表时间：
2019-08
期刊：
影响因子：
--
通讯作者：
J. Kawahara;Koki Sonoda;Takeru Inoue;S. Kasahara
中科院分区：
文献类型：
--
作者：
J. Kawahara;Koki Sonoda;Takeru Inoue;S. Kasahara
本文讨论了具有不完美顶点的网络可靠性评估，它计算了在链路和节点可能出现故障的情况下节点子集可通信的概率。虽然如果仅假设链路故障，则可以利用二元决策图 (BDD) 有效地计算网络可靠性，但如果也考虑节点故障，则速度可能会慢 10 倍。这是因为现有的算法被设计为针对每个节点故障以逐步的方式重复更新BDD。本研究提出了一种无需冗余重复即可创建最终BDD的算法，大大提高了计算效率。此外，本文提出了链路和节点对应的变量之间更好的 BDD 变量顺序。在可变阶数下，使用包括真实通信网络在内的各种基准网络进行数值实验，将所提出的算法与现有算法进行比较。结果表明，该算法对于10×10网格图的运行速度比现有算法快198.2倍，对于具有12个顶点的完整图快1074.6倍，对于一些知名基准网络快65.6倍。对于某些网络实例，与现有顺序相比，所提出的变量顺序将 BDD 节点数量减少了 15-38%。本文表明，考虑不完美的顶点不会带来显着的性能开销。
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.