最快路径问题下的网络可靠度OBDD算法  

OBDD algorithm for network reliability under quickest path problem

作　　者：方春林[1] 董荣胜[1] 赵岭忠[1] 

机构地区：[1]桂林电子科技大学计算机科学与工程学院,广西桂林541004

出　　处：《计算机工程与设计》2016年第8期2032-2036,2056,共6页Computer Engineering and Design

基　　金：国家自然科学基金项目(61363070);广西高等学校高水平创新团队及卓越学者计划基金项目;桂林电子科技大学创新团队基金项目

摘　　要：针对Theologou等给出的求解网络可靠度的factoring算法,分析该算法存在的冗余计算问题,给出DTN_OBDD算法。基于边排序策略的邻接终点矩阵方法,有效计算最小路集,将边失效特性引入网络可靠度分析中;基于最快路径求解公式,提高容量和时延约束下可行路径的筛选效率;构建所有可行路径的符号OBDD表示,遍历OBDD计算网络可靠度。以Python的igraph包生成的5组随机网络图为例,验证了DTN_OBDD算法的有效性,其中50个节点、201条边、状态空间为250的网络可靠度求解时间不超过80s。The redundant computations cannot be avoided in Theologou＇s factoring algorithm.To solve the problem,an OBDDbased algorithm DTN_OBDD was presented.The traditional adjacency matrix method was extended,which was used to enumerate 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 network 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 effectiveness of DTN_OBDD,it takes less than 80 sto calculate the reliability of the network with 50 nodes,201edges and 250 network states.

关 键 词：网络可靠度 有序二叉决策图 最快路径问题 容量 时延 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]