网络可靠性中基于指标的BDD排序策略选择研究

发布时间：2017-10-04 05:04

  本文关键词：网络可靠性中基于指标的BDD排序策略选择研究

  更多相关文章： 二元决策图 网络可靠性 边排序 初始点 复杂网络

【摘要】：随着科学技术的不断发展进步,网络逐渐成为人们生产和生活的一部分。对网络的可靠性研究也成为一个热点问题。在众多网络可靠性分析方法中,基于二元决策图(binary decision diagram, BDD)的分析方法因其高效性常被用来进行网络可靠性分析。基于BDD的网络可靠性分析方法包含三个主要步骤,对网络变量排序、构建与原网络等价的BDD模型、计算网络的可靠度值。在进行网络可靠度计算时,BDD分析方法性能的好坏与BDD模型的尺度直接相关。大尺度的BDD模型会使BDD分析方法的效率降低。因此,在基于BDD的网络可靠性分析中,使用小尺度的BDD模型进行可靠度计算是非常必要的。在构建等价BDD模型时,首先需要选择一个启发式边排序策略对网络变量进行排序。然而,使用不同的启发式边排序策略排序后构造出的BDD模型的尺度可能存在着巨大的差异。而生成小尺度BDD模型的启发式边排序策略其性能较好。因此,如何选择小尺度的BDD模型进行网络可靠性计算的问题就等价成了如何寻找高性能启发式边排序策略的问题。在使用启发式边排序策略进行边排序之前,要先选择一个排序初始点,而且使用不同的排序初始点排序后生成的BDD模型的尺度也可能存在巨大的差别。因此,如何寻找高性能的排序初始点也同样重要。本文针对如何选择高性能的启发式边排序策略和初始点做了一些研究工作,具体内容如下：(1)在如何选择一个性能较好的启发式边排序策略方面。首先介绍了基于指标TSBS (Total Size of Boundary Set,边界集之和)的选择方法,随后介绍了新的选择指标Fmax与(Maximum Size of Boundary Sets,边界集最大值；Index of Fmax,Fmax出现的时机),最后在复杂网络中比较了两种选择指标的性能。发现大多数情况下,基于指标Fmax与IFmax的选择方法比基于指标TSBS的性能要好。不过,由于边排序问题本身就是NP问题,而且复杂网络又具有小世界性和无标度性,所以也不能保证使用所提出的选择方法进行网络可靠性分析时,每次都能得到最优的结果,但是大多数情况下会得到较优的结果。(2)在如何选择性能较好的排序初始点问题方面。首先介绍了在规则网络中已有的选择指标TSBS和IFBSH (Index of First Boundary Set Hit,第一次击中{s,t}的边界集的索引),随后在复杂网络中应用了两种选择指标。发现多数情况下,使用基于指标TSBS的选择方法就能选出一个性能较好的排序初始点。但是,TSBS值与{s,t)点无关,对于同一网络、同一边排序策略和同一初始点,不同的{s,t)点得到的TSBS值相同。而这种情况下,BDD模型的尺度往往不同,此时就要用到基于指标IFBSH的选择方法。不过,在选择初始点时,首先选择使用TSBS作为选择指标,IFBSH作为辅助。综上所述,本文研究了在复杂网络中进行基于BDD的网络可靠性分析时,如何选择高性能边排序策略和初始点的问题。给出了复杂网络中高性能边排序策略和初始点的选择方法,对使用BDD方法进行复杂网络的可靠性分析具有一定的指导作用。
【关键词】：二元决策图 网络可靠性 边排序 初始点 复杂网络
【学位授予单位】：浙江师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 摘要3-5
• ABSTRSCT5-9
• 1 绪论9-17
• 1.1 研究背景和意义9-10
• 1.2 研究现状10-14
• 1.2.1 网络可靠性研究现状10-12
• 1.2.2 排序策略选择研究现状12-14
• 1.3 本文主要工作和组织结构14-16
• 1.3.1 本文的主要工作14-15
• 1.3.2 本文的结构安排15-16
• 1.4 本章小结16-17
• 2 排序策略选择研究基础17-28
• 2.1 网络基础知识17-22
• 2.1.1 规则网络模型18-19
• 2.1.2 随机网络模型19
• 2.1.3 复杂网络模型19-22
• 2.2 BDD相关知识22-24
• 2.3 边界集BS(Boundary Set)24-25
• 2.4 启发式边排序策略25-27
• 2.4.1 DFS25
• 2.4.2 BFS25-26
• 2.4.3 NDS26-27
• 2.5 本章小结27-28
• 3 边排序策略选择方法28-43
• 3.1 基于TSBS的选择方法28-29
• 3.2 基于~(F_(max))与~(IF_(max))的选择方法29-30
• 3.3 指标性能分析与比较30-42
• 3.3.1 基于波士顿交通网的性能分析和比较30-34
• 3.3.2 基于美国佛罗里达州电力网的性能分析和比较34-38
• 3.3.3 基于贵州省电力网的性能分析和比较38-42
• 3.4 本章小结42-43
• 4 初始点选择方法43-51
• 4.1 基于TSBS的选择方法43-47
• 4.1.1 基于TSBS的初始点选择方法43-44
• 4.1.2 应用性能分析44-47
• 4.1.2.1 基于美国波士顿交通网的性能分析44-46
• 4.1.2.2 基于贵州省电力网的性能分析46-47
• 4.2 基于IFBSH的选择方法47-50
• 4.2.1 基于IFBSH的初始点选择方法47-48
• 4.2.2 应用性能分析48-50
• 4.3 本章小结50-51
• 5 工作总结与展望51-53
• 5.1 工作总结51-52
• 5.2 工作展望52-53
• 参考文献53-59
• 攻读学位期间取得的研究成果59-60
• 致谢60-62

【相似文献】

中国期刊全文数据库 前3条

1 曾令国;莫毓昌;;PMS故障树分析中的变量排序策略库研究[J];计算机工程;2011年20期

2 潘竹生;莫毓昌;赵建民;;网络可靠度BDD分析中2种边排序策略的性能比较[J];浙江师范大学学报(自然科学版);2013年01期

3 ;[J];;年期

中国硕士学位论文全文数据库 前4条

1 伍欢;基于BDD的网络可靠性分析中边排序策略研究[D];浙江师范大学;2015年

2 付玉书;网络可靠性中基于指标的BDD排序策略选择研究[D];浙江师范大学;2016年

3 王中锋;多Agent英式序贯拍卖排序策略研究[D];郑州大学;2007年

4 曲克伟;基于热点话题发现的BBS检索排序策略研究[D];北京邮电大学;2013年

，

本文编号：968744