基于BDD的网络可靠性分析方法研究

发布时间：2018-02-25 06:07

本文关键词： 网络可靠性二元决策图性能改进边排序　出处：《浙江师范大学》2014年硕士论文　论文类型：学位论文

【摘要】：随着人类文明的不断发展进步,网络逐渐成为人们生产和生活的重要工具。大数据时代的网络系统变得极其庞大复杂,因而亟需加强网络可靠性的建设。利用二元决策图(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分析算法进行优化,大大提高了网络可靠性分析方法的性能。
[Abstract]:With the continuous development and progress of human civilization, network has gradually become an important tool for people's production and life. In the era of big data, network system has become extremely huge and complex. Therefore, it is urgent to strengthen the construction of network reliability.
Using two binary decision diagrams (BDD) analysis technology can greatly improve the work efficiency and performance analysis of network reliability. The process mainly includes looking for a better performance ranking variable of the network construction and network, the original equivalent BDD, computing network reliability value of three steps. Sort the edges and nodes in the network selection a good strategy can greatly improve the reliability of BDD network analysis of the performance of the algorithm. According to the established rules of variable ordering, can use the network decomposition principle and method of generating original network reliability equivalent BDD. based on the BDD to calculate the reliability of the value of each node, and the recursive method to calculate the reliability of the whole BDD the value of the evaluation algorithm. Usually in time and space complexity as the basis, the two complexity coincided with the number of path length and node BDD in correspondence. To ensure that the test information is complete and accurate, we should aim at minimizing the number of BDD nodes and shortening the BDD path length when optimizing the algorithm and sorting variables.
Improving the performance of network reliability BDD analysis is a hot topic in the current research field. This paper makes some researches on improving the performance of analysis.
(1) on the basis of BDD construction algorithm to use Sy-Yen Kuo proposed boundary extension technology from the bottom, put forward improvement algorithm, mainly from two aspects: first, we propose a more efficient method of isomorphic subnets subnet - "nuclear" method, can be used to judge the destructor in the network net isomorphic process. Second, a redundancy elimination, propose S-T non connected edge expansion path and the redundant node type edge expansion path, and the realization of these two kinds of invalid extension path is eliminated.
(2) according to the Gary Hardy proposed BDD top-down edge contraction and edge deletion operation based on Algorithm of improved.Hardy algorithm is the core idea of "zoning", using the boundary partition Partition.Partition identifies the network can not only determine isomorphic sub networks, and the network information storage is more concise and accurate. The improved Gary Hardy algorithm the main work including: Based on "the same boundary partition two with the same sub network" of this theorem, a top-down K eliminate the redundant end reliability BDD construction algorithm. In the process of the construction of BDD using a hash operation for sub network sharing, greatly enhance the performance of the proposed algorithm.
(3) after the implementation of isomorphism identification, and eliminate the redundancy subgraph sharing technology, the performance of BDD construction algorithm is greatly improved, the number of BDD nodes generated decreased, but the scale is still large because BDD nodes greatly influence the edge ranking number, and the edge of the BDD scheduling problem is a NP the difficult problem, so in the fifth chapter, based on the strategy of ordering preferred ordinary depth sorting problem, discuss the rules of network, recently the best performance ranking starting point in the network neighbor and worst ranking starting point. Study the influence of network on the performance of BDD algorithm of sorting starting point, provides an important reference for the research of heuristic edge ranking.
In summary, this paper focuses on the analysis method of network reliability based on BDD, according to Kuo and Hardy algorithm for performance improvement, and based on the breadth first edge effect ranking strategy research on ranking performance analysis of starting point, to select the optimal variable ordering, create a empty BDD. using the bottom-up and top-down algorithm good, put forward subgraph isomorphism judgement, redundant subgraphs judgment and elimination method. From the edge ranking and redundant subgraphs to eliminate the two angles of the BDD analysis algorithm is optimized, greatly improving the performance analysis method of network reliability.

【学位授予单位】：浙江师范大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.08

【参考文献】