基于截断边扩展图的网络可靠度近似分析

小型网络可以快速计算出可靠度精确值,但对于大型网络,可靠性精确值的计算非常困难,因此提出一种基于截断边扩展图的网络可靠性近似分析算法。实验结果证明,该算法能够在生成较小边扩展图和等价BDD(Binary Decision Diagrams)的基础上得到误差较小的近似值。     

应用子网同构判定改进矩形网络可靠度计算

为改善矩形网络的可靠度计算效率,提出基于同构子网判定的矩形网络可靠度计算方法.在研究矩形网络结构特点的基础上,定义了不同的特殊矩形子网,并设计了识别其同构子网的hash表.在分解网络创建OBDD(OBDD,Ordered Binary Decision Diagram)时,对于首次出现的特殊矩形子网,其OBDD被记录进hash表中;再次出现的同构子网,其OBDD直接从hash表返回,避免为同构子网重复创建OBDD,从而减少冗余的可靠度计算.实验证明该方法不仅能正确计算矩形网络可靠度,而且能高效地分析一些大型矩形网络.     

计算节点不可靠网络可靠度的一种MDD算法

节点或边不可靠网络的可靠度分析问题是NP-hard问题,网络节点和边都不可靠的假设更接近现实。基于网络节点和边二元状态的假设,构建了节点和边不可靠网络的形式化模型,给出了分析节点和边不可靠网络可靠度的NEF_MDD算法。该算法将单个节点与其未访问邻接边划分为一个集合,通过枚举节点和边的不同组合,合并导致子网同构的冗余状态,获得简化后的状态向量和可靠度向量,并用一个多值决策图变量来表述。通过使用自定义的MDD操作算子,构建整个网络的MDD,遍历MDD节点,计算网络的可靠度。与二元决策图方法相比,该方法能够降低决策图层数和节点规模,有助于节点和边不可靠网络的可靠度分析。     

优先级边排序策略及其性能分析

网络可靠度BDD分析的计算复杂度与BDD尺度线性相关,而BDD尺度依赖边排序策略,边排序问题是BDD网络可靠度分析的重要问题。从网络结构特性出发,设计了优先级边排序策略并深入研究了在该策略下不同排序起点对BDD尺度的影响。实验结果表明:源点和网络中心不是高性能排序起点,最佳排序起点分布在网络边缘,网络中心点为最差排序起点。该结论可为揭示边排序影响BDD尺度的本质以及研究高效启发性边排序策略提供重要参考依据。     

带路径约束的双端网络可靠性分析磁

针对带路径约束的双端网络可靠性分析问题,即一个数据包从 S 点发送到 T 点,必须经过中间若干个节点,并且经过这些节点的先后顺序具有一定约束,提出了基于 BDD 的可靠性分析算法。该算法基于边扩展图实现路径约束,即在边扩展过程中只保留符合条件的约束路径,然后构建 BDD 以及进行双端网络可靠性分析。实例分析结果验证了算法的可行性和有效性。     

基于BDD的谓词分析与优化

为对带谓词的数据流进行准确而有效的分析,首先介绍了John W.Sias等人提出的一种基于二进制决策图(BDD)的谓词分析系统(PAS);然后在其基础上,提出了结合芯片自身体系结构特点的谓词优化算法。将PAS及优化算法在学院研制的FT_D4芯片的编译器上实现,实验结果表明,这种基于BDD的谓词分析与优化方法简化了程序控制结构,减少了对谓词寄存器的使用,缩短了代码执行时间,性能获得了较大的提高。     

一种新的启发式边排序策略及其性能分析

网络可靠度BDD分析方法的计算复杂度与BDD尺度线性相关,而BDD尺度严重依赖边排序质量。由于求解最优边排序是一个NP问题,在实际应用中,通常采用启发式边排序策略如BFS（Breadth First Search）和DFS（Depth First Search）。针对边排序问题,从分析基于边界集（Boundary Set）的BDD构建方法BDD BS出发,将边界集思想应用于边排序过程,提出了一种新的启发式边排序策略。性能分析和大量实验表明,新设计的边排序策略性能优于经典的DFS和BFS策略,该结果为网络可靠度BDD分析方法在大规模网络中的应用拓展了新的空间。     

网络可靠性分析中自顶向下的二叉决策图构造研究

采用边界分区标识网络的思想,实现基于边界分区的自顶向下K端可靠度二叉决策图(BDD)构建算法。针对BDD构建过程中存在的节点冗余问题,提出无效边冗余消除和K点非连通冗余消除2种处理技术。在规则网络和实际工程中的实验结果表明,利用无效边冗余消除和K点非连通消除技术后的BDD改进算法,在不影响算法时间性能的情况下,可大幅缩减BDD尺度,提升K端网络可靠度分析算法性能,适用于大规模的网络可靠度分析。     

基于故障树的无线传感器网络可靠度符号计算

以无线传感器网络（WSN ）中应用通信可靠性（ACR）为背景,利用故障树模型中的事件元素与逻辑门元素,建立基于故障树的WSN可靠性结构。为降低WSN可靠度计算的复杂性,给出从WSN可靠性结构转换到二元决策图BDD结构的算法,利用BDD算法优化计算过程。以分层簇型网络中可用路径以及节点冗余下的应用通信可靠性问题为例,给出其可靠性结构,利用CUDD软件包给出用递归方法实现构建基于故障树的WSN可靠性结构的BDD算法,计算以上两种情况下的WSN可靠度。实验结果表明,该方法具有可行性。     

边排序质量影响因素研究

网络可靠度BDD分析方法的计算性能与BDD尺度紧密相关,而BDD尺度严重依赖边排序质量。因此,边排序问题是网络可靠度BDD分析方法的重要问题。由于求解最优边排序是一个NP问题,在实际网络可靠度分析中,通常采用启发式边排序策略如BFS和DFS,它们适用不同类型的网络。然而,对于给定网络,采用何种边排序策略更优,有哪些因素影响边排序质量,迄今没有给出评判依据。利用边界集思想,提出"边界长度(BSL)"概念,并用边界长度BSL表征边排序质量,揭示边界长度BSL和BDD尺度(节点数目)之间的关系。实验结果表明,边界长度BSL与BDD尺度具有正相关性,即较小BSL对应的BDD尺度较小,较大BSL对应的BDD尺度较大,多数情况下,BSL取最值时,BDD尺度能取到(或接近)最值。这为特定网络选择(或设计)高性能边排序提供了重要的参考依据。     

基于最小路集的网络可靠性分析方法研究

基于最小路集的网络可靠性分析方法是研究网络可靠度的重要算法之一,研究表明,在最小路集基础上求解网络可靠性是一个典型的NP-hard问题,其主要计算方法有三类：容斥原理法、不交积和法以及二叉决策图法。该文重点阐述了这三类计算方法的研究进展,并对其进行总结,对网络可靠性的未来发展方向进行了展望。     

基于改进的不交化最小路集的网络系统可靠性算法

本文根据不交化布尔代数及BDD原理提出了一种简化的求解不交化最小路集的改进算法。对最小路集的路长进行排序,按最小路集的不同路长分两种方法不交化:对于长度为n-1的最小路集,在保持原有弧不变外,将网络图中其余未包含在该条最小路内的弧取逆加入,直接获得不交化运算结果;其余最小路集采用BDD方法进行不交化。最后的实例计算表明,改进的算法有较小的分枝树、较高的计算效率和精度,为大型网络系统的可靠性分析提供了一种新的途径。     

基于BDD的增量启发式搜索

增量搜索是一种利用先前的搜索信息提高本次搜索效率的方法,通常可以用来解决动态环境下的重规划问题.在人工智能领域,一些实时系统常常需要根据外界环境的变化不断修正自身,这样就会产生一系列变化较小的相似问题,此时应用增量搜索将会非常有效.另外,基于BDD(binary decision diagram)的启发式搜索,结合了基于BDD的搜索和启发式搜索这两种方法的优点.它既用BDD这一紧凑的数据结构来表示系统的状态空间,又通过使用启发信息来进一步压缩搜索树的大小.在介绍基于BDD的启发式搜索和增量搜索之后,结合这两种方法给出了基于BDD的增量启发式搜索算法--BDDRPA*.大量的实验结果表明,BDDRPA*算法是非常有效的,它可以被广泛地应用到智能规划、移动机器人问题等领域中.     

基于遗传禁忌混合策略的二叉判定图最小化算法研究

提出了一种新的动态启发式二叉判定图（BDD）最小化算法．该算法将遗传算法的全局搜索能力和禁忌搜索的邻域搜索策略相结合来寻找BDD的最优变量排序，以实现BDD结点规模最小化．实验结果表明该算法性能优于其它启发式算法．     

用改进的OBDD方法计算通信网可靠度*

提出一种改进的OBDD（ordered binary decision diagram）方法来计算通信网可靠度。该方法考虑了网络共因失效带来的部件故障,使得计算更加准确。在创建原始网络的OBDD结构后,根据共因变量集来计算网络可靠度。由于只创建并保存一个OBDD结构,可节省大量的计算时间和存储空间。实验证明,该方法能有效计算网络可靠度,其计算时间和存储空间要低于一般的OBDD方法。