论文部分内容阅读
随着人类文明的不断发展进步,网络逐渐成为人们生产和生活的重要工具。大数据时代的网络系统变得极其庞大复杂,因而亟需加强网络可靠性的建设。利用二元决策图(BDD)技术分析网络可靠性能够大大提高分析性能和工作效率。该过程主要包含寻找一种性能较好的网络变量排序、构建与原网络等价的BDD、计算网络的可靠度值三个步骤。选择一种优秀的策略对网络中的边和节点进行排序,能够极大地提升网络可靠性BDD分析算法的性能。根据既定的变量排序规则,可以利用网络分解原理等方法生成与原网络可靠度等价的BDD。根据生成的BDD计算出每个节点的可靠度值,并且通过递归方法计算出整个BDD的可靠度值。通常对算法的评价主要以时间复杂度和空间复杂度为依据,这两个复杂度恰好与BDD的路径长度和节点数目一一对应。因此在保证所测试信息完整和准确的前提下,对算法进行性能优化以及研究变量排序时,应以尽量减小BDD节点数目和缩短BDD路径长度为目标。提高网络可靠度BDD分析方法的性能是当前研究领域的一个热点,本文在提高分析性能上做出一些研究,具体工作主要包括：(1)依据Sy-Yen Kuo等提出的利用边扩展技术的自底向上BDD构建算法,提出算法改进工作,主要从两个方面着手：第一,提出一种更加简洁高效的同构子网判别方法——子网“核”方法,可用于判断在网络解构过程中产生的子网是否同构。第二,关于冗余消除,提出s-t非连通边扩展路径和冗余节点型边扩展路径的概念,并且实现了这两类无效扩展路径的消除。(2)依据Gary Hardy提出的基于边收缩和边删除操作的自顶向下BDD构建算法作出改进。Hardy算法的核心思想是“分区划分”,采用边界分区Partition标识网络。Partition不仅可以判断同构子网,而且对网络信息的存储更加简洁准确。改进Gary Hardy算法的工作主要包括：在“相同边界分区的两个同层子网相同”这一定理的基础上,实现一种带冗余消除的自顶向下K端可靠度BDD构建算法。在BDD构建过程中使用哈希操作实现子网共享,大大提升了算法性能。(3)实现同构识别、冗余消除以及子图共享等技术之后,BDD构建算法的性能得到较大提升,网络生成的BDD节点数目有所减小,但是规模依然较大由于边排序的质量极大地影响所构建的BDD节点数目,并且BDD边排序问题是一个NP难问题,因此本文第五章基于普通广度优先排序策略研究边排序问题,讨论规则网络、最近邻网络中的性能最佳排序起点和最差排序起点。研究网络排序起点对BDD算法的性能影响,为研究启发式边排序提供了重要参考依据。综上所述,本文围绕基于BDD的网络可靠性分析方法,针对Kuo和Hardy算法作了性能改进工作,并基于广度优先边排序策略研究排序起点对分析性能的影响,争取选取最优变量排序,创建具有良好时空性的BDD。利用自底向上和自顶向下的算法,提出同构子图判定、冗余子图判定及消除方法。从边排序和冗余子图消除两个角度对BDD分析算法进行优化,大大提高了网络可靠性分析方法的性能。