论文部分内容阅读
随着科学技术的不断发展进步,网络逐渐成为人们生产和生活的一部分。对网络的可靠性研究也成为一个热点问题。在众多网络可靠性分析方法中,基于二元决策图(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方法进行复杂网络的可靠性分析具有一定的指导作用。