基于BDD的网络可靠性分析中边排序策略研究

发布时间：2018-11-27 20:43

【摘要】：在网络可靠性分析中,使用二元决策图(binary decision diagram, BDD)技术能够在很大程度上提高性能和效率。基于BDD的网络可靠性分析方法主要包含寻找一种较好的网络变量(本文仅考虑边失效,节点均是可靠的)排序序列、生成与原网络等价的BDD、计算网络的可靠度值三个方面。其中的关键性基础,就是选取一种高效的对网络中的边进行排序的策略,从而显著地提升基于BDD的网络可靠性分析算法的性能。已有的基于BDD的网络可靠性分析方法,通常采用深度优先排序策略(depth-first search, DFS)口广度优先排序策略(breadth-first search, BFS)两种启发式排序策略,并有研究者对这两种策略进行了性能比较,得出了BFS性能普遍优于DFS这一结论,也有研究者提出了新的边排序策略——优先级排序策略(priority ordering strategy, POS)。通过分析这些策略及其研究方法,我们发现主要存在这样三个方面的问题：(1)进行测试的网络模型及规模有限,策略性能的比较不够系统；(2)BFS是一种基于图广度遍历搜索的边排序策略,其排序结果依赖于图节点的编号,存在不合理性；(3)随着网络规模的增大,当以复杂网络作为网络模型时,已有的边排序策略不再能满足网络的需求,需要设计性能更优的边排序策略。本文的工作主要围绕基于BDD的网络可靠性分析中边排序策略主题,针对目前存在的三个问题进行深入研究,包括：(1)在规则网络中对BFS和POS两种边排序策略进行性能分析。基于不同的基准规则网络模型,采用BFS和POS策略分别进行BDD网络可靠性测试,由可靠度值、BDD尺度(空间性能)、运行时间(时间性能)三个重要的性能指标分析两种策略对网络的适应性,得出不同的策略适应于不同的网络这一结论,这将为特定的网络选择较好的边排序策略提供依据。(2)在复杂网络中对BFS策略进行改进。BFS策略是依赖于节点编号的一种排序策略,其排序质量的好坏与节点编号顺序紧密相关,因此BFS排序结果不仅受网络本身结构的影响,还受人为编号的影响,存在不稳定性。BFS策略在规则网络中的性能较好,但是随着网络规模的增加,BFS的性能却不是很理想。为避免人为因素的影响,同时使策略具有更强的适应性,利用优先队列改进BFS策略：以网络的节点度作为排序参数,用优先队列替代BFS策略中的普通队列,节点的未排序关联边数定义为该节点的优先级,设计了一种基于节点度的最好优先排序策略(degree-based best first search, DBFS)。实验结果表明,DBFS策略在复杂网络中较BFS性能提升了很多。(3)在边界集的基础上设计了一种新的高性能边排序策略Snooker。边界集是构建BDD过程中的一个有效参数,并且边界集及边界集的和值与边排序策略之间紧密相关。因此,提出了一种以“边界集和值最小”为原则,以节点度为主要排序参数的Snooker策略,并分别在规则网络模型和复杂网络模型中比较分析Snooker与 DBFS策略,实验结果表明：选取的网络样本无论是规则网络还是复杂网络,Snooker策略的性能均较DBFS更优。
[Abstract]:......
【学位授予单位】：浙江师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP393.08

【参考文献】