An efficient algorithm for computing global reliability of anetwork

Global reliability of a network is defined and then evaluated using spanning trees of the network graph. An algorithm for generating spanning trees (termed, appended spanning trees) that are mutually disjoint is proposed. Each appended spanning tree represents a probability term in the final global reliability expression. The algorithm gives the global reliability of a network directly. It is illustrated with an example. The algorithm is fast, requires very little memory, is adaptable to multiprocessors, and can be terminated at an appropriate stage for an approximate value of global reliability     

一种计算具有不可靠结点分布式计算网络可靠性的算法

提出了几个保持可靠性不变的缩减,结合这些缩减,利用因子分解公式建立了一个计算具有不可靠结点的分布式计算网络分布程序可靠性的有效算法,算法的时间复杂性是O(N·(V+E)),并对一些网络在Pentium 120 计算机上作了计算,结果显示用本文算法计算DPR所产生的N和所用时间比其它算法的要小得多。     

Algebraical algorithm for computing complex systems reliability

This paper describes the use of a graph theoretical approach called Latin Multiplication, for finding the success paths for any reliability network whose elements are statistically independent.     

Fast algorithm for computing the reliability of a communication network

This paper presents a fast algorithm for computing the reliability of a communication network when each link has the same probability of success. The computational complexity of existing algorithms increases exponentially as the number of links increases. Our algorithm is based on combinatorics and we conclude, for the case when links have the same survival probabilities, that the computational complexity grows subexponentially as the number of links increases. Furthermore, the algorithm is mostly algebraic in nature.     

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

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

A linear-time algorithm for computing K-terminal reliability onproper interval graphs

Consider a probabilistic graph in which the edges are perfectly reliable, but vertices can fail with some known probabilities. The K-terminal reliability of this graph is the probability that a given set of vertices K is connected. This reliability problem is #P-complete for general graphs, and remains #P-complete for chordal graphs and comparability graphs. This paper presents a linear-time algorithm for computing K-terminal reliability on proper interval graphs. A graph G = (V, E) is a proper interval graph if there exists a mapping from V to a class of intervals I of the real line with the properties that two vertices in G are adjacent if their corresponding intervals overlap and no interval in I properly contains another. This algorithm can be implemented in O(|V| + |E|) time     

An improved Boolean algebra method for computing the network reliability

This paper presents a new method, the HHL 91 algorithm, for calculating the network system reliability by sum of disjoint products (sdp). The main feature of the HHL 91 is its ability to properly arrange the order of minimal paths as well as to apply inversion to products of several variables. While the Abraham algorithm and its successors yield relatively short sdp forms of the structure functions of coherent network systems, this new method generates shorter disjoint products than any other known sdp method. Because the system reliability formula is considerably reduced in size, there will be a sharp decrease both in computation time and in rounding errors.     

An improved algorithm for coherent-system reliability

This paper presents a simpler and more efficient algorithm (LVT), based on the one proposed by Veeraraghavan and Trivedi (VT), to calculate system reliability using `sum of disjoint products' and `multiple variable inversion' (MVI) techniques. A proposition, a state space division idea, and a theorem are introduced. To compare LVT with several well known MVI algorithms (viz. VT, KDH88, CAREL) the 4 algorithms are implemented on the same platform (Solaris), and the execution-time comparison shows the computational saving achieved by LVT is appreciable     

A memory-effective fast algorithm for computing the reliability of complex systems/networks

Boolean reliability analysis of complex technical systems, as well as of technical net-systems (such as telecommunication systems), leads to the problem of computing the terminal pair reliability R^s,t of a netgraph. Among the fastest methods of computing R^s,t is the path method. In enumerates all minimal s−t paths of the net and then makes the paths mutually disjoint. Unfortunately, all paths and all disjoint terms must be available (stored) at the same time. Therefore, the computer memory effort for that method increases exponentially. In contrast, the reliability branching algorithm (RBA) that builds up a branching tree with disjoint tree-nodes (corresponding to the terms of a symbolic reliability expression) is also effective and needs only a low, quadratically increasing memory effort.The present paper gives a new method for symbolic reliability analysis. It is a fusion of the RBA with the path method. We search for one s−t path and compute its reliability. Then we formulate conditions that ensure disjointness for all paths we search on that condition and so on. A condition always reduces the network. The new method combines the advantages of the path method (fast) and the RBA (low memory effort). The algorithm is simple for computation by hand and effective for the use of computers.     

A new algorithm for computing the reliability of complex networks by the cut method

It is well known that computing network reliability is equivalent to computing network unreliability. A fusion of the reliability branching algorithm (RBA) with the path method has given a new method for symbolic reliability analysis. The present paper gives a new method for symbolic unreliability; it is a combination of the RBA with the cut method. The algorithm is simple for computing by hand and has easy execution for the use of computers.     

An algorithm for computing the distance spectrum of trellis codes

A class of quasiregular codesis defined for which the distance spectrum can be calculated from the codeword corresponding to the all-zero information sequence. Convolutional codes and regular codes are both quasiregular, as well as most of the best known trellis codes. An algorithm to compute the distance spectrum of linear, regular, and quasiregular trellis codes is presented. In particular, it can calculate the weight spectrum of convolutional (linear trellis) codes and the distance spectrum of most of the best known trellis codes. The codes do not have to be linear or regular, and the signals do not have to be used with equal probabilities. The algorithm is derived from a bidirectional stack algorithm, although it could also be based on the Viterbi algorithm. The algorithm is used to calculate the beginning of the distance spectrum of some of the best known trellis codes and to compute tight estimates on the first-event-error probability and on the bit-error probability     

An improved algorithm for symbolic reliability analysis

The authors describe an efficient Boolean algebraic algorithm to compute the probability of a union of nondisjoint sets as applied to symbolic reliability analysis. Coherent networks and fault-trees with statistically-independent components characterized by their minimal pathsets or cutsets are used as examples for generating the nondisjoint sets. The algorithm uses the concept of multiple variable inversion originally proposed by A. Grnarov et al. (1979). The authors illustrate improvements in the use of the multiple variable inversion technique for this problem using two examples. The algorithm is extended to compute the reliability importance of a given component (sensitivity of system reliability to the component reliability). A computer program implementing the modified algorithm is used to solve and obtain measured time complexities for a large set of network and fault tree models     

An approximate method for computing performance-related reliability of gracefully degrading systems

Using existing methods, the computation of performance-related reliability (PRR) of large-scale gracefully degrading systems is very tedious and time consuming. In this paper, the behaviour of such systems is respectively modeled as two types of diffusion processes according to their reconfiguration coverage. If the coverage is 1 (i.e. the reconfiguration is always successful), it is modeled as a regular diffusion. If, on the other hand, the coverage is less than one, it is modeled as diffusion with killing. Kolmogorov backward equations for regular diffusion processes and for diffusions with killing are then applied to compute the PRR. The methods have been applied in several examples, and the results satisfactorily agree with the accurate results.     

An algorithm for lower reliability bounds of multistate two-terminal networks

Network reliability is extensively used to measure the degree of stability of the quality of infrastructure services. The performance of an infrastructure network and its components degrades over time in real situations. Multi-state reliability modeling that allows a finite number of different states for the performance of the network and its components is more appropriate for the reliability assessment, and provides a more realistic view of the network performance than the traditional binary reliability modeling. Due to the computational complexity of the enumerative methods in evaluating the multi-state reliability, the problem can be reduced to searching lower boundary points, and using them to evaluate reliability. Lower boundary points can be used to compute the exact reliability value and reliability bounds. We present an algorithm to search for lower boundary points. The proposed algorithm has considerable improvement in terms of computational efficiency by significantly reducing the number of iterations to obtain lower reliability bounds.     

An efficient and versatile algorithm for computing the covariancefunction of an ARMA process

Computation of an ARMA covariance function is a common ingredient in analysis and synthesis of various problems in stochastic control, estimation, and signal processing. Several approaches can be used for this purpose. In this paper, we present an algorithm based on simple polynomial calculations. Compared with alternative strategies, it has small computational load, shows good numerical robustness, and can be extended to handle multivariable ARMA processes, even with complex-valued coefficients     

A simulation approach for computing systems reliability

The basis of the concept of reliability is that a given component has a certain stress-resisting capacity; if the stress induced by the operating conditions exceeds this capacity, failure results. Most of the published results in this area are based upon analytical modelling of stress and strength, using various probability distributions, and then trying to find an exact expression for system reliability, which can be very difficult to obtain sometimes. The approach used in this paper is very simple and uses simulation techniques to repeatedly generate stress and strength of a system by the computer, using a random number generator and methods such as the inverse transformation technique. The advantage of this approach is that it can be used for any stress-strength distribution functions. Finally, numerical results obtained from using this approach are compared with results obtained using the analytical methods for various strength-stress distribution functions, such as exponential, normal, log normal, gamma and Weibull. Results show the viability of the simulation approach.     

A direct algorithm for computing reliability of a consecutive-k cycle

A consecutive-k cycle is a circular system such that the system fails if and only if any i consecutive components all fail. Reliabilities for consecutive-k cycles are usually computed by recursive equations. However, most recursive equations proposed so far for the cycle involve reliabilities for consecutive-k lines, requiring two passes where the first pass computes only the line reliabilities. A recursive equation involving cycles only is proposed that is simpler in form but much harder to understand on intuitive grounds. Another advantage is that the proposed cycle recursion has the same form as a line recursion previously proposed. Thus a uniform treatment of lines and cycles is possible. This uniform approach is used to obtain some explicit solutions of both line and cycle reliabilities for 2⩽k⩽4     

电磁加固设计余量可靠度与置信度评估算法分析

介绍了系统抗电磁脉冲性能评估的主要任务以及系统抗电磁脉冲加固性能的统计性描述方法,根据评估水平(或目标)的不同,将电磁脉冲试验分为4种类型,在此基础上分析了电磁加固设计余量评估中的随机误差来源,分析了总误差标准偏差的评定方法,介绍了一种设计余量下限估计及其对应可靠度与置信度的评定方法,分析了该方法应用的前提条件,并以某屏蔽舱内电子设备的加固设计余量评估计算为例,说明了算法的使用过程及注意事项。