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

《基于bdd的网络可靠性分析方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据BDD—BASEDNETWORKRELIABILITYANALYSISMETHoDSRESEARCHThesisSubmittedtoZhejiangNormalUniversityInpartialfulfillmentoftherequirementForthedegreeofMasterofScienceinEngineeringRong-genChen(ComputerSoftwareandTheory)ThesisSupervisor：AssociateProfessorYu-changMoJune，2014万方数据基于BDD的网络可靠

2、性分析方法研究摘要fIIIIIIIIIIllllIIIIIIIIIIIIIIY2664101随着人类文明的不断发展进步，网络逐渐成为人们生产和生活的重要工具。大数据时代的网络系统变得极其庞大复杂，因而亟需加强网络可靠性的建设。利用二元决策图(BDD)技术分析网络可靠性能够大大提高分析性能和工作效率。该过程主要包含寻找一种性能较好的网络变量排序、构建与原网络等价的BDD、计算网络的可靠度值三个步骤。选择一种优秀的策略对网络中的边和节点进行排序，能够极大地提升网络可靠性BDD分析算法的性能。根据既定的变量排序规则，可以利用网络分解原理等方法生成与原网络可靠度

3、等价的BDD。根据生成的BDD计算出每个节点的可靠度值，并且通过递归方法计算出整个BDD的可靠度值。通常对算法的评价主要以时间复杂度和空间复杂度为依据，这两个复杂度恰好与BDD的路径长度和节点数目一一对应。因此在保证所测试信息完整和准确的前提下，对算法进行性能优化以及研究变量排序时，应以尽量减小BDD节点数目和缩短BDD路径长度为目标。提高网络可靠度BDD分析方法的性能是当前研究领域的一个热点，本文在提高分析性能上做出一些研究，具体工作主要包括：(1)依据Sy-YenKuo等提出的利用边扩展技术的自底向上BDD构建算法，提出算法改进工作，主要从两个方面着

4、手：第一，提出一种更加简洁高效的同构子网判别方法一子网“核”方法，可用于判断在网络解构过程中产生的子网是否同构。第二，关于冗余消除，提出s—t非连通边扩展路径和冗余节点型边扩展路径的概念，并且实现了这两类无效扩展路径的消除。(2)依据GaryHardy提出的基于边收缩和边删除操作的自顶向下BDD构建算法作出改进。Hardy算法的核心思想是“分区划分”，采用边界分区Partition标识网络。Partition不仅可以判断同构予网，而且对网络信息的存储更加简洁准确。改进GaryHardy算法的工作主要包括：在“相同边界分区的两个同层子网相同”这一定理的基础

5、上，实现一种带冗余消除的自顶向下K端可靠度BDD构建算法。在BDD构建过程中使用哈希操作实现子网共享，大大提升了算法性能。(3)实现同构识别、冗余消除以及子图共享等技术之后，BDD构建算法的I万方数据性能得到较大提升，网络生成的BDD节点数目有所减小，但是规模依然较大。由于边排序的质量极大地影响所构建的BDD节点数目，并且BDD边排序问题是一个NP难问题，因此本文第五章基于普通广度优先排序策略研究边排序问题，讨论规则网络、最近邻网络中的性能最佳排序起点和最差排序起点。研究网络排序起点对BDD算法的性能影响，为研究启发式边排序提供了重要参考依据。综上所述，

6、本文围绕基于BDD的网络可靠性分析方法，针对Kuo和Hardy算法作了性能改进工作，并基于广度优先边排序策略研究排序起点对分析性能的影响，争取选取最优变量排序，创建具有良好时空性的BDD。利用自底向上和自顶向下的算法，提出同构子图判定、冗余子图判定及消除方法。从边排序和冗余子图消除两个角度对BDD分析算法进行优化，大大提高了网络可靠性分析方法的性能。关键词：网络可靠性；二元决策图；性能改进；边排序万方数据BDD—BASEDNETWORKRELIABILITYANALySISⅣ匝THODSRESEARCHABSTRACTWiththedevelopment

7、ofhumancivilization，net、№rkhasbeenaveryimportantpartinOUrdailylivesandindustricalproduction．DuetotheBigDatatechniques，networksystemsbecomelargerandmorecomplex．Thus，thereliabilityanalysisofnetworksbecomesmoreandmoreimportant．UsingBinaryDecisionDiagram(BDD)techniquetoanalyzethereli

8、abilityofnetworkcangreatlyimprovetheperf