论文部分内容阅读
随着信息技术的飞快发展,网络逐渐成为人类生产、生活所必需的一种载体和工具。网络一旦发生故障,将给人们带来重大的影响,因此加强网络可靠性建设迫在眉睫。在分析网络可靠性时,采用二元决策图BDD(binary decision diagram)技术能够有效地提高性能和工作效率。基于BDD的网络可靠性分析主要是先寻找一种性能较好的网络变量排序序列,然后利用边扩展图EED(edge expansion diagram)构建与原网络等价的BDD,最后计算网络的可靠度值。本文选定一种合适的边排序策略,使用网络分解原理等方法生成与原网络可靠度等价的BDD,通过递归方法计算出整个网络的可靠度值。在生活中出现很多有关约束方面的问题,为了更好的解决这些问题,本文根据已有的基于BDD网络可靠性分析的研究,对此做了一些研究,具体工作主要包括：(1)带路径约束的双端网络可靠性分析算法。针对带路径约束的双端网络可靠性分析问题,即一个数据包从S点发送到T点,必须经过中间若干个节点,并且经过这些节点的先后顺序具有一定约束,提出了基于BDD的可靠性分析算法。该算法基于边扩展图实现路径约束,即在边扩展过程中只保留符合条件的约束路径,然后构建BDD以及进行双端网络可靠性分析。这些将有效地解决实际路径约束的很多问题,特别是用于电子政务和电子商务中路径约束的点对点通信问题,具有较强的实际意义。(2)带长度约束的K端网络可靠性分析算法。在网络视频和实时通信应用中需要研究带长度约束的K端网络可靠性分析问题,即任意两端点之间在给定时间延迟D约束内的K端网络可靠性。基于传统不带路径约束的双端和K端网络可靠性研究基础上,提出了基于截断的路径约束方法；并根据该方法构造BDD模型进行带约束的K端网络可靠性分析。该研究方法适用于视频会议和数据传输等后对点对点信息流在一定时间延迟下的完成传输问题,具有较强的实际意义。综上所述,本文提出基于BDD的带约束的网络连通可靠性分析的研究方法主要是针对不同的实际问题,对Kuo等提出的算法进行改进,从而解决这些实际问题。