针对Theologou等给出的求解网络可靠度的 factoring算法，分析该算法存在的冗余计算问题，给出 DTN_ OBDD算法。基于边排序策略的邻接终点矩阵方法，有效计算最小路集，将边失效特性引入网络可靠度分析中；基于最快路径求解公式，提高容量和时延约束下可行路径的筛选效率；构建所有可行路径的符号 OBDD 表示，遍历 OBDD 计算网络可靠度。以Python的 igraph包生成的5组随机网络图为例，验证了 DTN_ OBDD算法的有效性，其中50个节点、201条边、状态空间为250的网络可靠度求解时间不超过80 s。%The redundant computations cannot be avoided in Theologou’s factoring algorithm.To solve the problem,an OBDD-based algorithm DTN_OBDD was presented.The traditional adjacency matrix method was extended,which was used to enu-merate minimal paths efficiently,to evaluate the reliability of a network with imperfect nodes and links based on edge ordering strategy.To enhance the computing efficiency,the quickest path problem was introduced to compute the feasible path.The net-work reliability was computed by traversing the OBDD which was constructed by all feasible paths.Five sets random networks were generated by Python’s igraph library to validate the performance of the algorithm.Experimental results show the effective-ness of DTN_OBDD,it takes less than 80 s to calculate the reliability of the network with 50 nodes,201 edges and 250 network states.
展开▼
