摘要
针对传统算法求解动态拓扑网络可靠度会对没有受到拓扑变化影响的最小路集进行重新计算的问题,在Kuo的边扩展算法基础上,提出一种基于OBDD的动态拓扑网络2-终端可靠度算法。根据网络的变化,算法不再对没有受到变化影响的最小路集重新构建OBDD,而是在原始网络最小路集OBDD表示的基础上进行修正,得到变化后网络最小路集的OBDD表示,基于得到的OBDD表示进行网络可靠度计算。与Kuo的边扩展算法进行了实验对比,实验结果表明,对于非稀疏网络图,该算法要优于Kuo的算法。
Network reliability is an important performance indicator of network.For dynamic topology network,it is possible to recalculate the minimal path set which is not affected by topology changes by using static network reliability algorithms.Based on Kuo′s edge expansion algorithm,a new algorithm which deals with dynamic topology network 2-Terminal reliability algorithm using OBDD is proposed.According to the changes in the network,there is no recalculation on the minimal path set which is not affected by the changes,but the correction work has been done to the original network path function.The network reliability is calculated from the changed network path function′s OBDD.The comparison has been carried between Kuo′s algorithm and this new algorithm.The experimental results show that the new algorithm is obviously better than Kuo′s algorithm for non-sparse network diagram.
出处
《桂林电子科技大学学报》
2013年第6期466-472,共7页
Journal of Guilin University of Electronic Technology
基金
广西可信软件重点实验室开放基金(kx201119)
