The purpose of this paper is to propose a computational technique for evaluating the reliability of networks subject to stochastic failures. In this computation, a mathematical model is provided using a technique whic...The purpose of this paper is to propose a computational technique for evaluating the reliability of networks subject to stochastic failures. In this computation, a mathematical model is provided using a technique which incorporates the effect of the factoring decomposition theorem using polygon-to-chain and series-parallel reductions. The algorithm proceeds by identifying iteratively one of seven polygons and when it is discovered, the polygon is immediately removed and replaced by a simple chain after having changed the individual values of the reliability of each edge and each node of the polygon. Theoretically, the mathematical development follows the results presented by Satyanarayana & Wood and Theologou & Carlier. The computation process is recursively performed and less constrained in term of execution time and memory space, and generates an exact value of the reliability.展开更多
The seismic reliability evaluation of lifeline networks has received considerable attention and been widely studied. In this paper, on the basis of an original recursive decomposition algorithm, an improved analytical...The seismic reliability evaluation of lifeline networks has received considerable attention and been widely studied. In this paper, on the basis of an original recursive decomposition algorithm, an improved analytical approach to evaluate the seismic reliability of large lifeline systems is presented. The proposed algorithm takes the shortest path from the source to the sink of a network as decomposition policy. Using the Boolean laws of set operation and the probabilistic operation principal, a recursive decomposition process is constructed in which the disjoint minimal path set and the disjoint minimal cut set are simultaneously enumerated. As the result, a probabilistic inequality can be used to provide results that satisfy a prescribed error bound. During the decomposition process, different from the original recursive decomposition algorithm which only removes edges to simplify the network, the proposed algorithm simplifies the network by merging nodes into sources and removing edges. As a result, the proposed algorithm can obtain simpler networks. Moreover, for a network owning s-independent components in its component set, two network reduction techniques are introduced to speed up the proposed algorithm. A series of case studies, including an actual water distribution network and a large urban gas system, are calculated using the proposed algorithm. The results indicate that the proposed algorithm provides a useful probabilistic analysis method for the seismic reliability evaluation of lifeline networks.展开更多
This paper presents a factoring algorithm for computing source-to- K terminal (SKT) reliability, the probability that a source s can send message to a specified set of terminals K, in acyclic directed networks (AD-net...This paper presents a factoring algorithm for computing source-to- K terminal (SKT) reliability, the probability that a source s can send message to a specified set of terminals K, in acyclic directed networks (AD-networks) in which both nodes and edges can fail. Based on Pivotal decomposition theorem, a new formula is derived for computing the SKT reliability of AD-networks. By establishing a topological property of AD-networks, it is shown that the SKT reliability of AD- networks can be computed by recursively applying this formula. Two new Reliability- Preserving Reductions are also introduced. The recursion tree generated by the presented algorithm has at most 2 leaf nodes, where V and K are the numbers of nodes and terminals, respectively, while C is the number of the nodes satisfying some specified conditions. The computation complexity of the new algorithm is O (E. V. 2) in the worst case, where E is the number of edges. For source-to-all-terminal (SAT) reliability, its computation complexity is O(E). Comparison of the new algorithm with the existing ones indicates that the new algorithm is more efficient for computing the SKT reliability of AD-networks.展开更多
1引言
随着计算机技术的迅速发展,计算机已在各个领域得到广泛的应用.越来越多的部门,象通讯、金融、国防、工业控制等领域,对计算机产生了很强的依赖性.这些系统的计算机一旦发生故障,将带来不可估量的损失.分布式网络以其可靠、坚固...1引言
随着计算机技术的迅速发展,计算机已在各个领域得到广泛的应用.越来越多的部门,象通讯、金融、国防、工业控制等领域,对计算机产生了很强的依赖性.这些系统的计算机一旦发生故障,将带来不可估量的损失.分布式网络以其可靠、坚固、快速响应、易于修改和扩充、资源共享等优点,而被广泛应用,其可靠度的计算成为人们关注的重要课题.目前,国内外学者对一般网络可靠度进行了较多的研究[1～4,8,9],但对于具有不可靠结点的分布式网络的分布程序可靠度(Distribut-ed Program Reliability,DPR)的研究还不多见[6,7].展开更多
文摘The purpose of this paper is to propose a computational technique for evaluating the reliability of networks subject to stochastic failures. In this computation, a mathematical model is provided using a technique which incorporates the effect of the factoring decomposition theorem using polygon-to-chain and series-parallel reductions. The algorithm proceeds by identifying iteratively one of seven polygons and when it is discovered, the polygon is immediately removed and replaced by a simple chain after having changed the individual values of the reliability of each edge and each node of the polygon. Theoretically, the mathematical development follows the results presented by Satyanarayana & Wood and Theologou & Carlier. The computation process is recursively performed and less constrained in term of execution time and memory space, and generates an exact value of the reliability.
基金Natural Science Funds for the Innovative Research Group of China Under Grant No.50621062
文摘The seismic reliability evaluation of lifeline networks has received considerable attention and been widely studied. In this paper, on the basis of an original recursive decomposition algorithm, an improved analytical approach to evaluate the seismic reliability of large lifeline systems is presented. The proposed algorithm takes the shortest path from the source to the sink of a network as decomposition policy. Using the Boolean laws of set operation and the probabilistic operation principal, a recursive decomposition process is constructed in which the disjoint minimal path set and the disjoint minimal cut set are simultaneously enumerated. As the result, a probabilistic inequality can be used to provide results that satisfy a prescribed error bound. During the decomposition process, different from the original recursive decomposition algorithm which only removes edges to simplify the network, the proposed algorithm simplifies the network by merging nodes into sources and removing edges. As a result, the proposed algorithm can obtain simpler networks. Moreover, for a network owning s-independent components in its component set, two network reduction techniques are introduced to speed up the proposed algorithm. A series of case studies, including an actual water distribution network and a large urban gas system, are calculated using the proposed algorithm. The results indicate that the proposed algorithm provides a useful probabilistic analysis method for the seismic reliability evaluation of lifeline networks.
文摘This paper presents a factoring algorithm for computing source-to- K terminal (SKT) reliability, the probability that a source s can send message to a specified set of terminals K, in acyclic directed networks (AD-networks) in which both nodes and edges can fail. Based on Pivotal decomposition theorem, a new formula is derived for computing the SKT reliability of AD-networks. By establishing a topological property of AD-networks, it is shown that the SKT reliability of AD- networks can be computed by recursively applying this formula. Two new Reliability- Preserving Reductions are also introduced. The recursion tree generated by the presented algorithm has at most 2 leaf nodes, where V and K are the numbers of nodes and terminals, respectively, while C is the number of the nodes satisfying some specified conditions. The computation complexity of the new algorithm is O (E. V. 2) in the worst case, where E is the number of edges. For source-to-all-terminal (SAT) reliability, its computation complexity is O(E). Comparison of the new algorithm with the existing ones indicates that the new algorithm is more efficient for computing the SKT reliability of AD-networks.
文摘1引言
随着计算机技术的迅速发展,计算机已在各个领域得到广泛的应用.越来越多的部门,象通讯、金融、国防、工业控制等领域,对计算机产生了很强的依赖性.这些系统的计算机一旦发生故障,将带来不可估量的损失.分布式网络以其可靠、坚固、快速响应、易于修改和扩充、资源共享等优点,而被广泛应用,其可靠度的计算成为人们关注的重要课题.目前,国内外学者对一般网络可靠度进行了较多的研究[1～4,8,9],但对于具有不可靠结点的分布式网络的分布程序可靠度(Distribut-ed Program Reliability,DPR)的研究还不多见[6,7].
