一种计算Ad hoc网络K-终端可靠性的线性时间算法

研究计算Ad hoe网络K-终端可靠性的线性时间算法,可以快速计算Ad hoe网络K-终端可靠性。为了计算Ad hoe网络分级结构尽终端可靠性,可以采用无向概率图表示Ad hoe网络的分级结构。每个簇头由已知失效率的结点表示,并且当且仅当两个簇相邻时,两个结点间的互连由边表示。这个概率图的链路完全可靠,并且已知结点的失效率。此图的K-终端可靠性为给定K-结点集是互连的概率。文中提出了基于合适区间图计算尽终端可靠性的一种线性时间算法。本算法可用来计算Ad hoe网络的K-终端可靠性。其时间复杂度为O（｜V｜＋｜E｜）。     

基于动态计算可观测性无关项的OBDD变量序算法

OBDD是一种表示和操纵布尔函数的有效方法。由于许多布尔运算都可以转换为OBDD图的运算，因此，OBDD在集成电路设计领域，如逻辑综合、验证以及测试生成等，得到了广泛的应用。但是，OBDD的大小则严重依赖于变量序，为了实现OBDD的有效操作，寻找一个好的变量序是非常重要的基。基于此，文章提出了一个新的寻找OBDD变量序的启发式算法，它通过动态计算原始输入变量的可观测性无关项来确定一个好的变量序。实验结果表明，对于大部分电路，应用该算法都可以找到一个好的变量序。     

基于路径函数和BDD的网络可靠度分析

现有的二终端网络可靠度评估方法，多数基于不交积和，由于没有充分利用普遍存在的同构子网特性，导致存在大量冗余计算，无法适用于大型网络．为此，本文提出了一种基于路径函数和BDD的网络可靠度分析方法，利用图Hash技术识别同构子网，从而简化路径函数的构建，再利用BDD高效地操纵路径函数计算网络可靠度．实验结果表明，该方法性能稳定且高效，适用于更大规模的网络可靠性分析．     

航空电子系统FDDI互连的可靠性研究

对于光纤分布式数据接口(FDDI)互连的航空电子系统可靠性问题,从FDDI互连系统的基本拓扑结构出发,提出了基于任务的系统可靠性分析方法,建立了FDDI互连系统的可靠性模型;根据系统可靠度矩阵,给出了FDDI互连系统平均可靠度计算公式。针对系统故障时可靠性问题,依据系统可靠度矩阵和系统平均可靠度计算公式,推导出FDDI互连系统不同单一故障状态时的系统平均可靠度计算公式。最后通过应用分析,对不同状态时系统平均可靠度计算公式进行了验证,验证了模型和算法的有效性和正确性,为航空电子系统的可靠性计算提供依据。     

网络系统可靠度的BDD算法

文中研究3-状态设备网络系统2-终端可靠度的计算问题。BDD是布尔函数的图形表示形式。武小悦和沙基昌提出了一个采用BDD方法求2-状态网络系统的不交化最小路集,从而直接计算网络系统可靠度的算法。通过引入简化技术,结合归约公式和BDD技术,给出了一个计算3-状态设备网络2-终端可靠度的一个新算法;算法有效地消除了冗余项,并且产生的分枝树具有结点少,可有效得到可靠度符号表达式。     

网络端端可靠度的上下界计算研究

考虑精确计算较大规模网络的端端可靠度属于NP—hard问题,提出一种计算网络端端可靠度的近似方法,算法分别基于最小路集和不交最短路集来计算网络端端可靠度的上下界,并在此基础上给出了示例来阐明算法的有效性,该计算方法的算法实现简单,能快速计算出网络的端端相对可靠度。     

边失效概率不同情况下网络全终端可靠度的近似计算

用可靠性多项式计算网络全终端可靠度是评估网络拓扑结构德定程度的重要依据,精确计算可靠性多项式是一个NP-hard问题.本文通过对基于产生孤立点的概率随机事件的定义,运用概率不等式变换,给出了点可靠、边以不同的概率相互独立失效时,网络全终端可靠度的上界表达式,在可靠度近似计算过程中避免了对网络边割集和路集的搜索.最后,在...     

“遗传算法”在计算机网络可靠度优化计算中的作用

以保证计算机网络传输系统的可靠作为前提,怎样有效地降低网络结点链路成本,逐渐成为了当前计算机网络可靠度优化的主要方向。而遗传算法相对于传统的算法来说,有着搜索高效、求解便捷和算法结构简便等优点,做全局的计算时能够得到最优的相似值。文章在确保计算机网络链路介质成本与网络可靠度数学模型因素之时,对遗传算法在计算机网络可靠度优化计算中的作用进行了分析。     

Ad Hoc网络管理系统可靠性评估

针对Ad Hoc网络管理系统,提出了一种可靠性评估算法,首先确定Ad Hoc网管系统可靠性三要素,然后利用最小定点割集确定Ad Hoc网络中的重要区域,同时根据生成树算法确定各个网管子系统的权重系数,分析Ad Hoc网络管理系统特点确定失效判据,依据失效判据进行可靠性建模,选择合适的可靠性模型,从而可以计算出Ad Hoc网络管理系统的可靠度。最后通过实例说明某Ad Hoc网络管理系统的可靠性评估。     

一个计算无圈有向网络可靠度的新算法

本文对无圈有向网络的可靠度计算进行了研究。提出了加权有序根树的概念，给出了路径集合的一种特殊排序方法，导出一个计算无圈有向网络可靠度的拓扑公式。在该公式的基础上提出了一个新的计算无圈有向网络可靠度的不交积和算法，算法可以生成简洁的可靠度表达式，从而可以有效地计算无圈有向网络的可靠度。同时验证了算法的有效性。     

Reliability evaluation of wireless sensor networks using an enhanced OBDD algorithm

An enhanced ordered binary decision diagram (EOBDD) algorithm is proposed to evaluate the reliability of wireless sensor networks (WSNs), based on the considerations of the common cause failure (CCF) and a large number of nodes in WSNs. The EOBDD algorithm analyzes the common cause event (CCE) and the network structure when CCE takes place according to the stochastic graph and the CCF model of WSNs. After constructing the ordered binary decision diagram (OBDD) of the original network with node expansion, it uses a set of OBDD variables (SOV) to guide reliability computations along this OBDD. The two steps about OBDD can decrease the cost of OBDD constructions and storage. Furthermore, the efficient OBDD structure and Hash tables can greatly decrease redundant computations of isomorphs. The experiment results show that the EOBDD can be used to evaluate the reliability of WSN efficiently.     

Determining terminal-pair reliability based on edge expansiondiagrams using OBDD

For calculating terminal-pair reliability, most published algorithms are based on the sum of disjoint products. However, these tree-based partitions lack the capability to avoid redundant computation due to the isomorphic sub-problems. To overcome these problems, an efficient methodology to evaluate the terminal-pair reliability, based on edge expansion diagrams using OBDD (ordered binary decision diagram) is presented. First, the success path function of a given network is constructed based on OBDD by traversing the network with diagram-based edge expansion. Then the reliability of the network is obtained by directly evaluating on this OBDD recursively. The effectiveness of this approach is demonstrated by performing experiments on benchmarks collected by previous works including the larger networks (from 4 to 2 ⁹⁹ paths). A dramatic improvement, as demonstrated by the experimental results for a 2-by-n lattice network is that the number of OBDD nodes is only linearly proportional to the number of stages, and is much better than previous algorithms which have exponential complexity by using the sum of disjoint products. The CPU time of reliability calculation for a 100-stage lattice network is only about 2.5 seconds with 595 nodes generated on a SPARC 20 workstation with 128 MBytes of memory. Thus, with this approach, the terminal-pair reliability of large networks can be efficiently evaluated better than thought possible     

OBDD-based network reliability calculation

An efficient method for evaluating the terminal-pair reliability based on an edge expansion tree and using an OBDD (ordered binary decision diagram) is presented. The effectiveness of the algorithm is demonstrated on the larger benchmarks collected in previous work. One notable case of the experimental results for a 2×20 lattice network is that the number of nodes in the OBDD is linearly proportional to the number of stages. This is significantly superior to previous algorithms which are based on the sum of disjoint products and has exponential complexity     

Adaptive reliability satisfaction in wireless sensor networks through controlling the number of active routing paths

The number of active paths in multipath routing scenarios (with concurrent data transmission over the established paths) affects the provided reliability degree as well as the imposed overhead of path management. Since the reliability of individual links varies over the time, adaptively setting the sufficient number of active paths turns out to be essential. In this paper, we first propose a Reliability Estimation for WSNs (RE-WSNs) algorithm, based on ordered binary decision diagram (OBDD) data structure, which gives the network reliability in terms of the reliability of all individual links. Second, we propose a novel algorithm called adaptive reliability satisfaction–multipath routing (ARS–MR) which adaptively sets the sufficient number of active paths, aiming at keeping the network reliability within a desired quantitative range and minimizing path management overhead. In activation/inactivation process it further takes into account energy efficiency considerations. The proposed ARS–MR algorithm can be used in conjunction with any arbitrary multipath algorithm in WSNs. Simulation results with NS-2 reveal that ARS–MR is quite successful in timely reacting to variations of links reliability. Indeed, it manages the number of active paths and keeps the reliability of the network satisfactory over the course of network lifetime.     

Lossless image compression using ordered binary-decision diagrams

A lossless compression algorithm for images based on ordered binary-decision diagrams (OBDDs) is presented. The algorithm finds an OBDD which represents the image exactly and then codes the OBDD efficiently. The results obtained show a great improvement with respect to a previous work     

OBDD-based evaluation of k-terminal network reliability

An efficient approach to determining the reliability of an undirected k-terminal network based on 2-terminal reliability functions is presented. First, a feasible set of (k-1) terminal-pairs is chosen, and the 2-terminal reliability functions of the (k-1) terminal-pairs are generated based on the edge expansion diagram using an OBDD (ordered binary decision diagram). Then the k-terminal reliability function can be efficiently constructed by combining these (k-1) reliability expressions with the Boolean and operation. Because building 2-terminal reliability functions and reducing redundant computations by merging reliability functions can be done very efficiently, the proposed approaches are much faster than those which directly expand the entire network or directly factor the k-terminal networks. The effectiveness of this approach is demonstrated by performing experiments on several large benchmark networks. An example of appreciable improvement is that the evaluation of the reliability of a source-terminal 3/spl times/10 all-terminal network took only 2.4 seconds on a SPARC 20 workstation. This is much faster than previous factoring-algorithms.     

神经网络在电磁无损检测中的应用

研究了在涡流检测中用神经网络对经过不同热处理工艺所得工件进行分类的方法,针对BP神经网络学习算法的不足,提出了改进算法,提高了网络分类的可靠性。做到了所需特征参数少,且快速准确。     

一种基于流内与流间网络编码的无线路由算法

 网络编码能极大提高网络吞吐量和可靠性.该文提出了一种基于流内网络编码与流间网络编码的无线路由算法,首先用改进的流间网络编码策略寻找一条固定路由,发现尽可能多的编码机会以减少传输次数;再用流内网络编码与局部机会路由结合的方法实施每跳的数据包传输,减少数据包的重传次数.理论分析和仿真实验表明,此算法比传统的编码感知路由算法具有更高的吞吐量和可靠性.     

一种改进的用于可靠性分析的神经网络的实现

针对容错系统的可靠性问题,建立基于马尔科夫模型的三层前馈神经网络。提出一种改进的神经网络训练算法,用于包含永久过错．瞬态过错和周期过错影响的一个三模冗余（TMR,Triple Modular Redundancy）系统的可靠性分析。一个全连接的三层神经网络表示一个容错系统的离散时间n状态马尔科夫模型的可靠性。将系统的期望可靠性反馈入网络,当神经网络收敛时,从神经网络的权值中得出设计参数。仿真结果显示,与四层神经网络相比．三层神经网络收敛得更快．收敛可靠十牛更椿沂期望可靠性。     

Using ordered binary decision diagrams to factorize multi-level logic

A novel approach that employs ordered binary decision diagrams (OBDDs) is contributed to factorize multi-level logic functions by requiring as few literals as possible. A logic function with PLA format is represented as an OBDD form first. A heuristic decision method of variable ordering, called theorder lookahead method, is derived for the construction of OBDDs. This method is based on the constant cofactor and the number of erasable logic terms for each input variable. The total execution time of the OBDD construction by the above ordering decisions is very fast for some MCNC benchmarks. With the above OBDDs, we introduce a simple yet effective graph manipulation, calledEXT, to obtain a minimal number of literals in the Boolean function. This greedyEXT algorithm consists mainly of two phases. The first phase, calledgraph analysis, identifies the similarities between nodes on the same level in the OBDD. The second phase, calledtree analysis, utilizes the above features to extract the common parts of the nodes. TheEXT procedure runs from the bottom level up to the top level of the OBDD. The computational complexity depends on the number of nodes in the OBDD. The results of simulations show thatEXT has a very fast CPU execution time and a competitive literal ratio with other methods for some MCNC benchmarks.EXT will produce the smallest literal number, especially for structured or symmetric circuits.This work was supported, in part, by the National Science Council, Republic of China, under contract number NSC 83-0404-E009-010.