论文部分内容阅读
网络可靠度计算在网络的设计、使用和维护等方面都具有重要的意义。目前,网络可靠度计算问题的研究已经取得了大量的成果,其中基于有序二叉决策图(OBDD, OrderedBinary Decision Diagram)和图分解技术的算法具有较高的执行效率。这类方法通过引入符号技术使得可以处理的问题规模得到了极大的扩展,但该类算法在执行过程中对分解产生的大量子图利用传统的邻接矩阵、邻接表等数据结构进行存储,由此,随着问题规模的增大,分解得到的子图数量也急剧增长,从而产生组合爆炸问题。此外,基于OBDD和图分解技术的K uo的算法是目前效率较高的网络可靠度求解算法,然而该算法在求解动态拓扑网络可靠度时会产生对没有受到拓扑变化影响的最小路集进行重新计算的问题。 代数决策图(ADD,Algebraic Decision Diagram)是OBDD的一种扩展形式,是伪布尔函数描述的一种有效的数据结构,已成功应用于大规模的网络最大流问题、最短路径计算等问题的求解。鉴于此,本文基于符号技术对网络可靠度求解算法及动态拓扑网络的可靠度求解算法进行了研究,其主要内容如下: (1)基于符号 ADD技术对网络可靠度求解算法进行了研究。通过对网络图中的结点进行二进制编码,给出了网络图的ADD表示,进而给出了基于广度优先的符号ADD网络可靠度求解算法和基于深度优先的符号ADD网络可靠度求解算法。通过将两种符号AD D算法和K uo的边扩展算法进行实验对比,验证了算法的正确性,并对算法的实验结果进行了分析。 (2)针对 K uo的算法在求解动态拓扑网络可靠度时会对没有受到拓扑变化影响的最小路集进行重新计算的问题,在 Kuo的算法的基础上,提出了一种新的基于O BDD的动态拓扑网络可靠度求解算法。算法首先根据网络的变化,不再对没有受到变化影响的最小路集重新构建O BD D,而是在原始网络最小路集O BD D表示的基础上进行修正,得到变化后网络最小路集的O BD D,然后基于得到的O BD D进行网络可靠度计算。最后,与 Kuo的算法进行了大量实验对比,实验结果表明,对于非稀疏网络图,该算法要优于Kuo的算法。 (3)为了满足网络设计、使用、部署调动等情况下,对拓扑动态变化的网络进行可靠度求解的需求,开发了动态拓扑网络可靠度评估系统。该系统可以根据网络拓扑变化的不同情况,通过调用不同的算法以提供给用户更快的响应速度,并且具有评估模式设置和设计比对功能,以满足用户不同的评估需求。