节点不完全可靠无向网络k-端可靠度计算

可靠性是保障网络系统正常运行的必要条件,k-端可靠性问题是网络可靠性的最一般问题.通过对已有的计算2-端可靠度的方法进行扩展和改进,提出了一种计算节点不可靠无向网络k-端可靠度的方法.先将图的边定义为链路及其端点,然后通过矩阵变换运算,得到不相交的k-端路径,在此基础上,利用条件概率对k-端路径的概率进行求解以得到网络...     

考虑信号相关性的逻辑电路可靠度计算方法

随着集成电路特征尺寸不断缩小,软错误已经成为影响电路可靠性的关键因素.计算软错误影响下逻辑电路的信号概率能辅助评估电路的可靠性.引起逻辑电路信号概率计算复杂性的原因是电路中的扇出重汇聚结构,本文提出一种计算软错误影响下逻辑电路可靠度的方法,使用概率公式和多项式运算,对引发相关性问题的扇出源节点变量作降阶处理,再利用计算得到的输出信号概率评估电路可靠度.用LGSynth91基准电路、74系列电路和ISCAS85基准电路为对象进行实验,结果表明所提方法准确有效.     

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

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

通信网全端可靠性界的一种计算方法

用可靠性多项式计算网络全端可靠性的关键是多项式中系数的计算,精确计算各系数是一个NP难问题^[1].本文分析了网络的连通子网数与网络割集以及断集数的关系后,给出一种网络断集数的计算方法以及网络全端可靠性多项式系数上下界的公式,适用于任何网络.最后在网络链路寿命服从指数分布时分析了某SDH传输网络的全端可靠性以及界的计算,以说明本文的方法.     

基于NLB-RS策略的5G+网络终端直通通信安全可靠性分析

为了提高5G+网络终端直通通信的通信质量,文章提出基于最近位置的中继选择策略的5G+网络终端直通通信安全性及可靠性分析。以通信链路保密中断概率和通信中断概率分别作为5G+网络终端直通通信安全性及可靠性的分析指标,对5G+网络终端直通通信过程进行建模,基于最近位置的中继选择策略获取通信过程中的保密中断概率与中断概率,实现5G+网络终端直通通信安全性及可靠性定量分析。实验结果表明,设计方法所得5G+网络终端直通通信安全性及可靠性分析结果与实际情况相符,证实了该方法是正确的。     

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

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

通信网络的可靠性评估

通信网络的可靠性评估是一个难题。目前人们只对环型网和树型网进行可靠性分析。本文首先定义了通信网络的可靠性，依据图论提出了网络生成树的计算方法，以及网络可靠度的估算公式。最后给出了一个栅格型网的可靠度估算示例。     

可修复网络稳态可用度分析

本文提出了可修复网络稳态可用度的数学分析方法。通过证明得出不可修复网络的可靠性多项式适用于可修复网络的可用度，只需相应地把部件的可靠度改为部件的可用度，把部件的不可靠度改为部件的不可用度     

基于鱼群算法的全终端网络可靠性优化设计

鱼群算法是一种新型群智能优化方法,在分析鱼群算法实现原理的基础之上,将其与全终端网络可靠性优化问题有机融合,给出了求解全终端网络可靠性优化问题的鱼群算法设计.通过实例仿真比较,鱼群算法能够得到比遗传算法更满意的结果,从而验证了算法的可行性和有效性.     

基于概率转移矩阵的串行电路可靠度计算方法

概率转移矩阵(Probabilistic Transfer Matrix,PTM)方法是一种能够在门级比较精确地估计差错对电路可靠性影响的方法,但目前其实现方法只能适用于较小规模的电路.本文引入了电路划分的思想,先把电路分割成一组适宜用原始PTM方法直接计算其可靠度的模块,然后计算出这些模块的可靠度,再依据串行可靠度模型,将所有模块可靠度合成为整个电路的可靠度.本文用实验的方法通过对74系列电路的分析得到了合适的电路分割参数,即分割宽度,再进一步对ISCAS85基准电路进行了可靠度的计算,结果表明新方法可以适用于更大规模的无冗余组合电路.通过与依据美军标MIL-HDBK-217所算得的可靠度的比较,验证了本文所提出的方法的合理性.     

All-Terminal Network Reliability Using Recursive Truncation Algorithm

Exact calculation of all-terminal network reliability is a hard problem; its computational complexity grows exponentially with the number of nodes and links in the network. We propose the Recursive Truncation Algorithm (RTA), a bounding approximation algorithm, to estimate the all-terminal reliability of a given network with a pre-specified accuracy. RTA scans all minimal cutsets of the graph representing the network, and finds the weak cutsets of the graph by comparing failure probabilities of cutsets to an adaptive threshold which depends on the approximation accuracy. We calculate the unreliability of the network versus the probabilities of occurrence of failure in the weak cutsets, and the probabilities of co-occurrence of failure in several weak cutsets, simultaneously. In addition to the all-terminal reliability, the RTA computes an upper, and a lower bound for the estimated reliability. We demonstrate that the estimated all-terminal reliability of a given network is within a pre-specified accuracy, and is more precise than those obtained by existing methods.      

A unified domination approach for reliability analysis of networkswith arbitrary logic in vertices

The concept of a probabilistic graph G has been used as a universal model for network reliability. Most of the literature on this subject concentrates on computing various reliability measures (such as k-terminal reliability or all-terminal reliability) which are the probability that vertices of G can communicate with other specified vertices. Primarily, this paper provides a common theoretical framework for addressing k-terminal reliability problems. To this end, it extends the model admitting vertex functions of G to be arbitrary monotone Boolean functions: in this case G is called a monotone (S,t)-graph. In such graphs the signal passability across a node is carried out in accordance with collections of signals delivered on the node inputs from other ones, the collections are subjected to some logic principle realized by a Boolean function. Monotone (S,t)-graphs include all known classes of directed multi-terminal network reliability models. The main result of this paper is the reliability expression for computing the probability of an acyclic monotone (S,t)-graph G being operational. The expression uses the local domination parameters introduced here. That reduces the system level of consideration to the element level, providing a unifying understanding of the combinatorial nature of some results based on the domination theory and developed earlier for ordinary networks     

A linear-time algorithm to compute the reliability of planarcube-free networks

A planar graph G=(V,E) is a cube-free graph (CF graph) if it has no subgraph homomorphic to the cube. The cube is the graph whose vertices and edges are the vertices and edges of the three dimensional geometric cube. The all-terminal reliability of a graph G whose edges can fail (with known probabilities) is the probability that G is connected. The problem of computing the all-terminal reliability of a general graph is NP-hard. An O(| V|) time algorithm for computing the all-terminal reliability of CF graphs is presented     

High-reliability topological architectures for networks under stress

In this paper, we consider the design of a physical network topology that meets a high level of reliability using unreliable network elements. We are motivated by the use of networks and, in particular, all-optical networks, for high-reliability applications which involve unusual and catastrophic stresses. Our network model is one in which nodes are invulnerable and links are subject to failure - a good approximation for optical networks with passive nodes and vulnerable fiber under stress of disconnection - and we focus on statistically independent link failures with initial steps taken toward generalization to dependent link failures. Our reliability metrics are the all-terminal connectedness measure and the less commonly considered two-terminal connectedness measure. We compare in the low and high stress regimes, via analytical approximations and simulations, common commercial architectures designed for all-terminal reliability when links are very reliable with alternative architectures which are mindful of both of our reliability metrics and regimes of stress. We derive new results especially for one of these alternative architectures, Harary graphs, which have been shown to possess attractive reliability properties. Furthermore, we show that for independent link failures network design should be optimized with respect to reliability under high stress, as reliability under low stress is less sensitive to graph structure; and that under high stress, very high node degrees and small network diameters are required to achieve moderate reliability performance. Finally, in our discussion of correlated failure models, we show the danger in relying on an independent failure model and the need for the network architect to minimize component failure dependencies.     

Reliability analysis of the double counter-rotating ring withconcentrator attachments

The inherently weak reliability behavior of the ring architecture has led network designers to consider various design choices to improve network reliability. We assess the impact of provisions such as node bypass, secondary ring and concentrator trees on network reliability. For this reason, we develop closed-form expressions for the reliability and the mean time-to-failure of the double counter-rotating ring architecture. For our comparisons we adopt the 2-terminal, and the all-terminal reliability criteria. Our network reliability expressions are valid for any time-to-failure distributions of links and nodes     

Using the Decomposition-Tree of a Network in Reliability Computation

Available algorithms for measures of network reliability require computation time f(n) where f is at least exponential in n, the number of failure-prone elements in the system. Modularization is a familiar method of decomposing a network reliability problem into a set of subproblems. This decomposition reduces required computation time from f(n) to a sum of f(ni), ni < n, usually a considerable saving. For a 2-terminal communication network, the decomposition tree of a network provides the identity of the modules and an easily read map of the relations among them. The decomposition tree is derived by finding the triconnected components of the underlying graph. Reducing computation time by finding and analyzing the triconnected components of a network has been proposed for the reliability problems of 2-terminal communication, all-terminal communication, and feasible transportation flow. This paper introduces the use of the decomposition tree for reliability computation purposes, presents a general algorithm based on the tree, and demonstrates its application to the problems named above, as well as to the problem of feasible shortest path.     

通信网中链路重要性的评价方法

本文提出了一种通信网链路重要性的评价方法,该方法可以评价全网范围内的链路重要性.最重要的链路是将其进行边收缩操作后,得到的图的生成树数目最多.通过比较生成树的数目,我们可以判断通信网中任意两条链路的相对重要性.基于生成树数目的边收缩方法反映了某条链路处于正常工作时,对整个通信网的贡献大小.实验结果和理论分析均证明了该方法的有效性和可行性.     

Inflection points for network reliability

Given a finite, undirected graph G (possibly with multiple edges), we assume that the vertices are operational, but the edges are each independently operational with probability p. The (all-terminal) reliability, \(\operatorname{Rel}(G,p)\) , of G is the probability that the spanning subgraph of operational edges is connected. It has been conjectured that reliability functions have at most one point of inflection in (0,1). We show that the all-terminal reliability of almost every simple graph of order n has a point of inflection, and there are indeed infinite families of graphs (both simple and otherwise) with more than one point of inflection.     

Finding the most vital edges with respect to the number of spanningtrees

A most vital edge of a graph (w.r.t. the spanning trees) is an edge whose deletion most drastically decreases the number of spanning trees. We present an algorithm for determining the most vital edges based on Kirchoff's matrix-tree theorem whose asymptotic time-complexity can be reduced to that of the fastest matrix multiplication routine, currently O(n^2.376). The foundation for this approach is a more general algorithm for directed graphs for counting the rooted spanning arborescences containing each of the arcs of a digraph. A network can be modeled as a probabilistic graph. Under one such model proposed by Kel'mans, the all-terminal network reliability, maximizing the number of spanning trees is critical to maximizing reliability when edges are very unreliable. For this model, the most vital edges characterize the locations where an improvement of the reliability of the link most improves the reliability of the network