American Journal of Operations Research
Vol.07 No.03(2017), Article ID:76311,24 pages
10.4236/ajor.2017.73014

System Reliability Evaluation for Imperfect Networks Using Polygon-to-Chain Reduction

Mohamed-Larbi Rebaiaia, Daoud Ait-Kadi

Department of Mechanical Engineering/Interuniversity Research Center on Enterprise Networks, Logistics and Transportation, Laval University, Quebec, Canada

Copyright © 2017 by authors and Scientific Research Publishing Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

Received: August 5, 2015; Accepted: August 12, 2015; Published: May 22, 2017

ABSTRACT

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.

Keywords:

Reliability, Networks, Algorithms, Factorization, Polygon-to-Chain Reduction, Decomposition

1. Introduction

Over the last decades, the reliability evaluation of systems and networks has become a priority for all manufacturers, particularly in areas when human life is at stake. These areas are especial; aeronautics and telecommunication, nuclear and chemical industries, emissions of greenhouse gases, and many others where high level of service is needed. System reliability is supported very early of the design process. In fact, designers are always trying to develop the best possible product that takes into account its impact on the environment; that must be sustainable and safe, and competitive in term of robustness and evidently that generates earning. Several technical solutions are well-known by designers and engineers; they are included gradually during the life-cycle of products.

In the literature, dozens of applied methods and techniques have been proposed for determining the reliability of networks [1] . Several of them are called enumeration algorithms [2] - [12] , summation of disjoint products [5] [8] [13] , transformations of star-delta and delta-star structures [14] , factoring & Reduction techniques [11] [14] - [22] , binary decision diagrams methods [6] [7] [18] [23] [24] , Bayesian models [25] , etc. Simulation and approximating procedures have been used when the problem is tedious or when the exact value of the reliability is not necessary required [12] [26] . However, most of these solutions are very effective but unfortunately do not allow taking into account the complexity of systems and networks’ architecture. The problem is that, in practice, there is no general and unified mathematical expression that can represent the reliability from which an exact value can be determined, except for some specific architecture, such as parallel, series, series-parallel, standby, k-from-n, and others as discussed in the literature (see [27] ).

The problem of evaluating the reliability of networks has been verified to be NP-hard [28] and more specifically to be a counting problem or #-P-complete (number P-complete) problem ( [28] [29] [30] ). To avoid such complexity, several methods and techniques have been proposed, such as factoring and reductions algorithms. Some advised researchers like Wood reported in [31] some advantageous provided by factoring algorithms which require exponential time in the worst case and are at most quadratic in the size of the network because at most (the cardinal of E) modified copies of the network need ever be maintained in a stack at any time. He also noted that only a narrow range of reliability measures can be analysed and directed networks are problematic; they can only be handled in a limited way, and this, is considered as a disadvantage.

Moskowitz in 1958 introduced a clever technique based on the well-known Moore & Shannon theorem [15] [18] [32] [33] . Almost in the same time other researchers proposed a new category of methods which combines the factoring theorem and reduction operations using an efficient procedure that transforms a polygon structure into a simple chain and from which it becomes very easy to determine the reliability [2] [15] [16] [21] [23] [30] [33] [34] [35] . Satyanarana and Chang in [35] , Satyanarana and Wood in [21] and Wood in [31] for example, proposed a unified framework based on the factoring theorem to evaluate the reliability of networks whose only nodes are fully reliable, and where any edge is considered as the centerpiece that can be factored, it is called pivot or bridge. A little time later, Theologou and Carlier [22] proposed an original idea which provides a simple mathematical transformation to factoring either on nodes of on edges, but avoids the dependency problem between nodes and edges failures which consider the problem as the well-known common cause problem.

The purpose of this paper is to introduce a general framework for determining the reliability of complex networks whose nodes and edges may fail randomly. It consists of an extension of the work of Satyanarana et al. [20] [21] and those of Theologou and Carlier [22] . The central principle of this algorithm turns around the idea of decomposing the network structure into a well-distinctive component’s structure and then simplify these components directly into chains of type-1, type-2 until type-7 (see more closely [14] [18] to understand the type’s concept) by direct application of the factoring theorem as presented in Equation (3). Type-1 and type-2 are applicable to networks with a source node and a terminal node.

To explain the ideas developed in this article about the principle of transformation, we state two theorems that establish some mathematical concepts of transformation. Naturally, it would have been wiser to detail all the transformations of “polygon-to-chain” of any type, but due to the distinctive similarities of the generated mathematical formulas it is quite sufficient to present just type-1 and type-7 reductions, the rest is left as an application exercise to the readers. By against, a summary table reports the results of all these transformations, it is given at the end of this article.

The paper is organized as follows: Section 2 reviews some theoretical background and introduces the factoring theorem. Section 3 presents the operations of reduction polygons-to-chains for imperfect edges and nodes. In Section 4 a practical example is treated for determining the reliability of the proposed network, and Section 5 concludes the paper.

2. Backgrounds

2.1. Basic Knowledge

Consider an undirected stochastic network (graph) G = ( V , E , P ) where V is a finite set of nodes, E is a finite set of edges, and P represents the probability domain such that each edge/node takes its value from P . In other words, it is associated to each edge and/or to each node a real value p i (i: represents the name given to any arc/node). Mathematically speaking, “ p i / q i ” corresponds to the magnitude given to the probability of functioning/failing of the component i. In this paper, we consider that when a component fails, this does not necessary leads other components to fail, which means that all the components are independent and the notion of common cause of failure is prohibited. We consider the alphabetic characters s and t for representing the source and the sink nodes of the network. We denote the reliability of the network by R ( G K ) , where K is a specified subset of V with | K | 2 . If cardinality of K is equal to 2, the problem is called 2-terminal reliability. A success set, is a minimal set of edges of G such that all the vertices in K are connected. The set is minimal if the deletion of any edge causes the vertices in K to be disconnected and thus the reliability of the network cannot be determined. Two nodes v 1 and v 2 of the network are connected if there exists a sequence of nodes and edges of the form v 1 , ( v 1 , e 1 ) , e 1 , ( e 1 , e 2 ) , , ( e i , v 2 ) , v 2 (s.t. e i E ). Such a sequence is called a path if the edges are direct. A set of nodes K V is connected if there exists a path between all pair of nodes in K. A chain is an alternating sequence of distinct nodes and edges, v 1 , ( v 1 , v 2 ) , v 2 , ( v 2 , v 3 ) , v 3 , , ( e i 1 , e i ) , e i such as the internal nodes are of degree 2. Two distinct chains with common end-nodes, their union constitutes a polygon. Note that a chain or a path can be interpreted mathematically as a set of elements (nodes and edges). Topologically, a success set is a minimal tree of G covering all vertices in K. Also, we define parallel edges as edges with the same extremities and two adjacent edges are in series if their common nodes are of degree 2 and not in K. We note that replacing a pair of series (parallel) edges by a single edge is called series (parallel) reduction. So, If e is an edge of end-nodes u and v, then [ G e ] (Figure 1: right) is a subgraph of G obtained by deleting e from G and [ G e ] represents a subgraph of G obtained by contracting edge e from G (Figure 1: right). Edge e is considered as a keystone edge or the pivot. The edge pivot cannot be chosen arbitrarily [2] . For that, several techniques have been proposed in the literature [3] [12] . For some networks, the K-nodes are represented by solid circles because they are perfect which means that their reliability value is equal to 1. The rest of the nodes are represented by empty circles and their reliability takes its value in ] 0 , 1 [ ; they are imperfect. When K = E , the problem is treated as: all-terminal reliability, which mean that all nodes are perfect and the reliability calculus must considers all the relations (paths) between any two nodes of the networks.

In practice, to reduce the size of the network structure, several reduction rules have been proposed from which series and parallel are the well-known. They are applied only if the network is reducible. In the opposite case, the graph must support any other transformations such as polygon-to-chain reductions (see Figure 1: left).

2.2. The Factoring Principle

The reduction by factorization is based on the factoring theorem of Moore & Shannon theorem [33] , which is considered by several authors as the basis for a class of algorithms for computing K-terminal reliability [27] [31] . It consists of decomposing a graph by making assumptions about the state of a component (edge/node) until a simple configuration is obtained. The theorem of total probabilities is then applied to calculate the reliability of this last generated graph. The idea behind this process is to consider an edge e in a graph and to suppose that is still working. This statement is represented mathematically by the function ( Φ ( X ( t ) ) = 1 | x e = 1 ) where Φ ( ) represents the structure function of the network, and X ( t ) is a vector determining the state of the system.

Figure 1. (Left) reducible 2-terminal graph; (center) 2-terminal irreducible graph; (right): reduction/factoring).

In other words, it means that the communication through the edge e is provided. In a directed graph, perfect communication between two nodes means that, it is possible to gather them into a single node and the impossibility of communicating through an edge means that the edge must be deleted (see Figure 1 (right part)). Using the theorem of total probabilities (Equation (1)), we can easily compute the reliability of the network.

Note that theorems of Moore & Shannon [33] or the well-known theorem of Bayes [25] and those of Total probabilities are equivalent in our context. We can provide easily mathematical relations between them.

Consider a graph G and a component e E selected arbitrary. The theorem of total probabilities allows for a component e to express the reliability of G as a conditional probability using Equation (1).

R ( G ) = Pr ( Φ ( X ( t ) ) = 1 ) = Pr ( Φ ( X ( t ) ) = 1 | x e 1 ) Pr ( x e = 1 ) + Pr ( Φ ( X ( t ) ) = 1 | x e = 0 ) Pr ( x e = 0 ) (1)

where Pr ( x e = 1 ) is the probability that the component e works and Pr ( x e = 0 ) otherwise, and where Φ ( X ( t ) ) defines the structure function which represents the state of the system. In other word, the reliability of the system can be related with the expected mathematical expression which is R ( G ) = E { Φ ( X ) } (see. [27] ) for explanations.

It follows that if we substitute Pr ( x e = 1 ) by ( p e ) and Pr ( x e = 0 ) by ( 1 p e ) , yields to the expression of the reliability given by Equation (2).

R ( G ) = Pr ( Φ ( X ( t ) ) = 1 ) = Pr ( Φ ( X ( t ) ) = 1 | x e = 1 ) p e + Pr ( Φ ( X ( t ) ) = 1 | x e = 0 ) ( 1 p e ) (2)

This decomposition process continues as many times as it is necessary (recursively), until a simple structure is found (if any) and whose reliability is easy to be evaluated. It should be noted that the selection of certain components may sometimes decreases the process of reduction, and therefore the solution is obtained more quickly.

From Equation (2), it can be established the validity of the factoring theorem following conditional reliability formula as given by Equation (3):

R ( G ) = p e R ( G e ) + q e R ( G e ) (3)

where,

R ( G ) : The network reliability.

R ( G e ) : The probability that the system works when the component e works (edge e is contracted).

R ( G e ) : The probability that the system works when the component e is down (edge e is removed).

q e = 1 p e : The edge-failure probability.

It is easy to say by comparing the Equations (2) and (3) that R ( G e ) and R ( G e ) are none other than Pr ( Φ ( X ( t ) ) = 1 | x e = 1 ) and Pr ( Φ ( X ( t ) ) = 1 | x e = 0 ) .

The example depicted in Figure 2 illustrates the application of the factoring theorem using component 1 as a pivot. We assume that the node source corresponds to the node a and the terminal node is node c. If we apply Equation (3), we obtain the following expression of the reliability:

R ( G ) = p e R ( G e ) + q e R ( G e ) = p 1 [ p 2 + p 3 p 2 p 3 ] + q e [ p 2 ] = p 2 + p 1 p 3 p 1 p 2 p 3

Note that the factoring operation is a special case of pivotal decomposition of a binary system as stated in [16] [17] .

3. Factorization of Networks with Imperfect Nodes and Edges

For all the underlying development, we assume the following assumptions:

・ The edges and nodes can fail with a probability q = 1 p .

・ The components are s-independent with known probabilities.

・ All K-nodes are perfectly reliable ( p = 1 ).

3.1. Polygon-to-Chain Reduction

The objective of substituting a polygon by a chain is an action used to reduce the calculation of the reliability when traditional algorithms are not able to provide a finite solution or when the graph is irreducible. For that, Satyanarayana and Wood have identified seven types of polygons and presented their equivalent mathematical expressions [21] [31] . A table covering these polygons and their equivalences is published in [21] just for networks with perfect nodes.

The reduction polygon-to chain in the case of imperfect graphs is further

Figure 2. Application of the factorisation.

complicated because the transformation must to take into account the statements of nodes and edges at the same time. Several authors have mentioned this difficulty [2] [3] [23] [30] [36] . Theologou and Carlier [22] first, have argued that when pivoting on a node, the transformation problem becomes more complex and consequently the graph augments in its size.

In this paper we propose an algorithm which combines the reduction polygon-to-chain using the works of Theologou and Carlier [22] , those of Satyanarayana and Wood [21] , Simard [14] and Rebaiaia and Ait-Kadi [27] , in the sense that a combination of Satyanarayana and Wood [21] and of Theologou and Carlier [22] are provided. We find the work of Theologou and Carlier [22] very interesting because their technique avoids the problem of dependency between the network components’ failures. These assumptions are summarized as follows:

Consider the link e = ( u , v ) , where u and v are two imperfect nodes. We suppose that any link l works with a probability p l when e, u and v work with their respective probabilities p i ( i = e , u , v ) . Then p l can be written using the following equation:

p l = p e p u p v (4)

We note that the pivoting on the link l by applying the factoring theorem produces the contraction of the edge e and the merging of edges u and v, and this operation creates a new perfect node. By cons, if the link fails, the cause of the failure cannot be known a priori, because it could be that one of the three components of the link has failed, and the relative conditional probabilities are given by Equations (5) and (6). Anyway, this link will be lost and therefore it will be deleted.

After this operation of pivoting, the reliabilities of nodes v and u will be identified by the following new expressions:

p v = Pr ( v works | v or e or u aredown ) = p v ( q u + p u q e ) q v + p v q u + p v p u q e (5)

p u = Pr ( u works | u or e or v aredown ) = p u ( q v + p v q e ) q u + p u q v + p u p v q e (6)

We can remark that Equations (5) and (6) show clearly that u and v are intimately connected. Thus, to avoid such dependency and for respecting the initial assumptions, Theologou and Carlier in [22] proposed a new expression representing the probability of u and v. The idea is as follows:

Suppose that all the K-nodes of the graph are full connected between themselves, that is, if this is not the case, the reliability of the original network is equal to,

R ( G K ) = v K p v R ( G K ) (7)

where G K and G K contain K-imperfect nodes. They are the initial graph and its reduced one. Then there exists at least two K-nodes and it is always possible to find an edge in the graph with one of its end-node be perfect.

Let e be a such link with u (perfect) and v (imperfect). Replacing in (6) p u = 1 and because p v 1 , the relation (8) is then obtained.

p v = p v q e ( q v + p v q e ) (8)

Note that in the present state, the failure node v depends only on the link e and therefore e, u and v are now independent.

As the node v remains in the graph or the link l is down, then the other links that have one of their extremities as node v can now be factored and the failure of node v depends only on the failure of these edges. Therefore, we can now determine the general formulation for representing the reliability of the imperfect node v at any stage of the factoring process when edges ( e 1 , e 2 , , e r ) incident to v are factored. Consequently we obtain the reliability p v after applying the factoring theorem as given by Equation (9).

p v = Pr ( v fonctionne | ( v ou e 1 enpanne ) ( v ou e r enpanne ) ) = p v j = 1 r q e j q v + p v j = 1 r q e j (9)

In the sequel, we present the first transformation of polygon-to-chain using the factoring process. Here the polygon of type-1 is a triangle and a chain is two successive edges that can be reduced to one edge with its end-points (see Figure 3). As you can see in Figure 3, the triangle structure must contain at least one perfect node. If it contains two perfect nodes, it is named polygon of type-2.

3.1.1. Polygon-to-Chain Reduction of Type-1 (Type-2) for a K-Terminal Reliability

Consider a graph containing a polygon of type-1 or of type-2 as presented in Figure 3 (left, up/down) and let p s , p a et p b be the individual reliabilities at nodes s, a and b. Remember that the node s is the initial node and it is perfect, while a and b are imperfect. Note that type-1 polygon is a partial-graph and type-2 is a 2-terminal network [36] . Both of them are also known as triangle-network. Note also that this paper considers that nodes and edge both of

Figure 3. Type-1 (up) and type-2 (down) polygon-to-chain reductions.

them maybe subject to random failures.

We can now state the following theorem:

Theorem 1.

Suppose G be a graph containing a polygon of type-1 as shown if Figure 3 (up/left). Let G denotes the reduced graph generated after transforming G by replacing edges e 1 and e 2 by edges e 1 and e 2 of reliabilities p 1 and p 2 (e3 is simply deleted). Suppose also that the reliability at node a and b are respectively p a and p 2 (Figure 3 (up/right)), and let Ω be the multiplier factor also called the transformation factor. Then the reliability of the network is:

R ( G ) = Ω R ( G ) (10)

where Ω = ( δ + A ) ( δ + B ) / δ , p 1 = δ / ( δ + A C ) , p 2 = δ / ( δ + B D ) , p a = ( δ + A C ) / ( δ + A ) , p b = ( δ + B D ) / ( δ + B ) such that:

{ δ = p a p b [ p 1 p 2 + p 1 p 3 + p 2 p 3 2 p 1 p 2 p 3 ] A = p 2 p b [ 1 p 1 p a p 3 p a + p 1 p 3 p a ] B = p 1 p a [ 1 p 2 p b p 3 p b + p 2 p 3 p b ] C = p a q 1 q 3 ( q a + p a q 1 q 3 ) D = p b q 2 q 3 ( q b + p b q 2 q 3 ) (11)

Proof:

Assume that we are in the presence of a graph G which contains at least one polygon of type-1. Then the reduced subgraphs ( G e 1 ) and ( G e 1 ) are obtained by applying the factoring theorem (Equation (3)) using the link ( s , e 1 , a ) as a pivot and are used to determine the reliability expression of the graph G in Equation (12).

R ( G ) = p 1 p a R ( G e 1 ) + ( 1 p 1 p a ) R ( G e 1 ) (12)

Assume now that a is a node pivot. After applying Equation (8) to the node a the reliability of the node a in the subgraph ( G e 1 ) is represented by Equation (13):

p a = p a q 1 ( q a + p a q 1 ) (13)

Then, when pivoting on the link ( s , e 2 , b ) , the factoring on the reduced subgraphs G e 1 and G e 1 , generates the new reduced subgraphs ( ( G e 1 ) e 2 ) , ( ( G e 1 ) e 2 ) , ( ( G e 1 ) e 2 ) and ( ( G e 1 ) e 2 ) . The last subgraph is systematically eliminated because at this level of development, the link between node s and node a, and node s and node b are broken. The reliability expression of the graph G at this step becomes:

R ( G ) = p 1 p a [ p 2 p b R ( ( G e 1 ) e 2 ) + ( 1 p 2 p b ) R ( ( G e 1 ) e 2 ) ] + ( 1 p 1 p a ) [ p 2 p b R ( ( G e 1 ) * e 2 ) ] (14)

Similar to the node a, the new reliability expression of the node b in the subgraph ( G e 1 ) e 2 is given by Equation (15).

p b = p b q 2 ( q b + p b q 2 ) (15)

By decomposing successively on the link ( s , e 3 , b ) in the reduced graph ( G e 1 ) e 2 and on the link ( s , e 3 , a ) in the reduced graph ( G e 1 ) e 2 , then, the new expression of the system reliability is:

R ( G ) = p 1 p a [ p 2 p b R ( ( G e 1 ) e 2 ) + ( 1 p 2 p b ) [ p 3 p b R ( ( ( G e 1 ) e 2 ) e 3 ) + ( 1 p 3 p b ) R ( ( ( G e 1 ) e 2 ) e 3 ) [ p 2 p b R ( ( G e 1 ) e 2 ) ] ] ] + ( 1 p 1 p a ) [ p 2 p b [ p 3 p a R ( ( G e 1 ) e 2 ) e 3 + ( 1 p 3 p a ) R ( ( G e 1 ) e 2 ) e 3 ] ] (16)

In the sub-graph ( ( G e 1 ) e 2 ) e 3 generated in Equation (16), the new value of the reliability of the node a is equal to:

p a = p a q 1 q 3 ( q a + p a q 1 q 3 ) (17)

Likewise for the graph ( ( G e 1 ) e 2 ) e 3 , the reliability of the node b is:

p b = p b q 2 q 3 ( q b + p b q 2 q 3 ) (18)

Note that several states can induce the same graph. To get an idea on the concept of equivalence in this direction (see Figure 4 (terms A, B and C)) to recover the equivalent substructures in terms of reliability. We can now establish the following equalities:

Figure 4. Graph of type-1 and its series of successive transformations par application of the factoring theorem.

R ( ( G e 1 ) e 2 ) = R ( ( ( G e 1 ) e 2 ) e 3 ) = R ( ( ( G e 1 ) e 2 ) e 3 ) (19)

By grouping (A, B, C and D, E) and eliminating the configuration F, the system reliability becomes:

R( G )= p a p b [ p 1 p 2 + p 1 p 3 + p 2 p 3 2 p 1 p 2 p 3 ]R( ( G e 1 ) e 2 ) + p 1 p a [ 1 p 2 p b p 3 p b + p 2 p 3 p b ]R( ( ( G e 1 ) e 2 ) e 3 ) + p 2 p b [ 1 p 1 p a p 3 p a + p 1 p 3 p a ]R( ( ( G e 1 ) e 2 ) e 3 ) (20)

Assume G is obtained from G after the reduction process. Then by factoring on the link ( s , e 1 , a ) , the reliability of the system G is:

R ( G ) = p 1 p a R ( G e 1 ) + ( 1 p 1 p a ) R ( G e 1 ) (21)

The reliability of the node a in the graph ( G e 1 ) is equal to:

( p a ) = p a q 1 ( q a + p a q 1 ) (22)

A similar way is applied to the node b giving the following reliability expression as shown in (23):

( p b ) = p b q 2 ( q b + p b q 2 ) (23)

Finally, the reliability expression of G is given by Equation (24).

R( G )= p 1 p a [ p 2 p b R( ( G e 1 )* e 2 )+( 1 p 2 p b )R( ( G e 1 ) e 2 ) ] (24)

Because the graphs G and G are equivalent respecting to relation (10), we get the following equalities’:

R ( ( G e 1 ) e 2 ) = R ( ( G e 1 ) e 2 ) (25)

R ( ( ( G e 1 ) e 2 ) e 3 ) = R ( ( G e 1 ) e 2 ) (26)

Now, we remark that Equation (26) is valid if and only if the relations (27), (28) and (29) are respected.

p a = ( p a ) (27)

R ( ( ( G e 1 ) e 2 ) e 3 ) = R ( ( G e 1 ) e 2 ) (28)

p b = ( p b ) (29)

Due to Equations (10), (25) and (26), we can determine the following system:

{ p a p b [ p 1 p 2 + p 1 p 3 + p 2 p 3 2 p 1 p 2 p 3 ] = Ω [ p 1 p 2 p a p b ] p 1 p a [ 1 p 2 p b p 1 p 3 + p 3 p b + p 2 p 3 p b ] = Ω [ p 1 p a ( 1 p 2 p b ) ] p 2 p b [ 1 p 1 p a p 3 p a + p 1 p 3 p a ] = Ω [ p 1 p b ( 1 p 2 p a ) ] p a q 1 q 3 ( q a + p a q 1 q 3 ) = p a q 1 ( q a + p a q 1 ) p b q 2 q 3 ( q b + p b q 2 q 3 ) = p b q 2 ( q b + p b q 2 ) (30)

By solving the system in (30), the values of Ω , p 1 , p 2 , p a and p b are updated according to:

{ Ω = ( δ + A ) ( δ + B ) δ p 1 = δ ( δ + A C ) p 2 = δ ( δ + B D ) p a = ( δ + A C ) ( δ + A ) p b = ( δ + B D ) ( δ + B ) (31)

where δ, A, B, C and D are identified by the following relations:

{ δ = p a p b [ p 1 p 2 + p 1 p 3 + p 2 p 3 2 p 1 p 2 p 3 ] A = p 2 p b [ 1 p 1 p a p 3 p a + p 1 p 3 p a ] B = p 1 p a [ 1 p 2 p b p 3 p b + p 2 p 3 p b ] C = p a q 1 q 3 ( q a + p a q 1 q 3 ) D = p b q 2 q 3 ( q b + p b q 2 q 3 ) (32)

Finally, we note that it is possible to derive a simplified topology from another more complex by applying a series of reductions using the factoring theorem while keeping unchanged the value of the reliability of a network. The problem that may arise is how to automating the recognition of such topologies whose calculations can be deduced easily. The idea is very beneficial provided to design algorithms that easily skip such a critical stage of the calculation process, or at least to determine the necessary means to seek equivalencies between structures. To deal with such problems, two interesting productions challenge us; they have been reported independently in [19] and [22] .

Now, we skip the determination of the mathematical relations between the original graph and its reduced graph for the cases of type-2 to type-6, the reasoning scheme is particularly the same as of type-7. At the end of the paper a table is provided to resume the reductions relative to polygon-to-chain of type-1 to type-7.

Note that type-2 polygon-to-chain reduction generates the same mathematical relations given in systems (31) and (32). The verification is left to the reader.

3.1.2. Polygon-to-Chain Reduction of Type-7

We keep the same principle of factoring process used in the case of polygon-to-chain reduction of type-1, however, with a slight difference. Now, we can notice that the number of events has increased significantly; it went from five events ( e 1 , e 2 , e 3 , e a , e b ) to eight events ( e 1 , e 2 , e 3 , e 4 , e 5 , e 6 , e a , e b ) leading the states space to be multiplied (See Figure 6). A matrix solution is needed in this case to represent the subgraphs, events-states and all the reductions, they are represented in Table 1. Before that, we present the following theorem which states the principle of polygon-to-chain of type-7 reduction. It provides all the equivalence expressions. To prove the theorem, we proceed by factoring the edges and nodes of the graph G, and then, on the reduced graph G . Finally we establish the equivalences by correspondence using Equation (10).

Theorem 2.

Let G be a graph containing a polygon of type-7 as presented in Figure 5, and G be the reduced graph generated after transforming G by replacing edges e 1 , e 2 , e 3 , e 4 , e 5 , e 6 of reliabilities p 1 , p 2 , p 3 , p 4 , p 5 , p 6 by edges e 1 and e 2 of reliabilities p 1 and p 2 , and nodes a and b of reliabilities p a and p b by the updated reliabilities p a and p b (See Figure 6). If Ω is the multiplier factor,

Figure 5. Polygon-to-chain reduction of type-7.

Figure 6. The graphs induced using the reduction polygon- to-chain of type-7.

Table 1. Reduced graphs, state vectors and their corresponding probabilities.

then the reliability of the original graph G is determined using the following relations:

{ Ω = ( γ + α ) ( γ + β ) ( δ + γ ) γ 2 p 1 = γ γ + α C p 2 = γ γ + β p 3 = γ γ + D δ p a = γ + α C γ + α p b = γ + D δ γ + δ (33)

and such that:

{ α = p 1 p 2 p 3 p 5 p 6 p b [ 1 p 1 p a p 4 p a + p 1 p 4 p a ] β = p 1 p 2 p 3 p 4 p 5 p 6 p a p b [ q 3 q 4 p 3 p 4 + q 2 q 5 p 2 p 5 + q 2 q 4 p 2 p 4 + q 1 q 5 p 1 p 5 + q 1 q 6 p 1 p 6 + q 3 q 5 p 3 p 5 + q 2 q 6 p 2 p 6 ] γ = p 1 p 2 p 3 p 4 p 5 p 6 p a p b [ 1 + q 1 p 1 + q 2 p 2 + q 3 p 3 + q 4 p 4 + q 5 p 5 + q 6 p 6 ] δ = p 1 p 2 p 4 p 5 p a [ 1 p 3 p b p 6 p b + p 3 p 6 p b ] (34)

Proof:

Consider a graph containing a polygon of type-7 as depicted in Figure 5 (G). By pivoting successively on edges e 1 , e 2 , e 3 , e 4 , e 5 and e 6 , we obtain the subgraphs reported in Figure 6; they are five. The corresponding events and probabilities are presented in Table 1.

Because the decomposition process uses the links e 1 and e 4 as pivots in the reduced graphs B1 (Table 1) and uses the links e 3 and e 6 as pivots in the graph C1 (Table 1), then the new reliabilities of the nodes a and bare given by the following equations:

p a = p a q 1 q 4 q a + p a q 1 q 4 (35)

p b = p b q 3 q 6 q b + p b q 3 q 6 (36)

Continuing the application of the factoring theorem on the reduced graph G of G (polygon of type-7) and let e 1 , e 2 and e 3 the edges of G . Table 2 gives the subgraphs generated by the decomposition, and their relative state vectors and probabilities.

The following graph in Figure 7 shows how the state’s formulas and their probabilities are determined. The results of the transformations are presented in Table 2.

Note that, for the graphs B’ and C’, the conditional probabilities for node a and the link e 1 (graph B’), and for node b and the link e 3 (graph C’) are given by the following equations:

Table 2. Non-defaulting states and the probabilities induced by the decomposition process of the graph G K .

Figure 7. Transformation of the reduced graph G’ by applying the factoring theorem.

p a = ( p a ) = p a q 1 ( q a + p a q 1 ) (37)

p b = ( p b ) = p b q 3 ( q b + p b q 3 ) (38)

We can use now the relation R ( G ) = Ω R ( G ) (Equation (10)) to identify from Equations (38), (39), (40) and system (41) the coefficients α , β , δ and γ as presented in the theorem statement.

Using Equation (10), we obtain the following relations:

α R ( G B , K B ) + δ R ( G C , K C ) + β R ( G D , K D ) + γ R ( G E , K E ) = Ω [ α R ( G B , K B ) + β R ( G C , K C ) + δ R ( G D , K D ) + γ R ( G E , K E ) ] (39)

Using Equations (35), (37) and (38) we can identify the following relations:

p a q 1 q 4 q a + p a q 1 q 4 = p a q 1 ( q a + p a q 1 ) (40)

p a q 1 q 4 q a + p a q 1 q 4 = p a q 1 ( q a + p a q 1 ) (41)

We equate now the terms of the Equation (39), it follows the following relations:

{ p 1 p 2 p 3 p 4 p 5 p 6 p a p b [ 1 + q 1 p 1 + q 2 p 2 + q 3 p 3 + q 4 p 4 + q 5 p 5 + q 6 p 6 ] = Ω p 1 p 2 p 3 p a p b p 1 p 2 p 3 p 4 p 5 p 6 p a p b [ q 3 q 4 p 3 p 4 + q 2 q 5 p 2 p 5 + q 2 q 4 p 2 p 4 + q 1 q 5 p 1 p 5 + q 1 q 6 p 1 p 6 + q 3 q 5 p 3 p 5 + q 2 q 6 p 2 p 6 ] = Ω p 1 q 2 p 3 p a p b p 1 p 2 p 4 p 5 p a [ 1 p 3 p b p 6 p b + p 3 p 6 p b ] = Ω ( 1 p 3 p b ) p 1 p 2 p a p 1 p 2 p 3 p 5 p 6 p b [ 1 p 1 p a p 4 p a + p 1 p 4 p a ] = Ω ( 1 p 1 p a ) p 2 p 3 p b p a q 1 q 4 ( q a + p a q 1 q 4 ) = p a q 1 ( q a + p a q 1 ) p b q 3 q 6 ( q b + p b q 3 q 6 ) = p b q 3 ( q b + p b q 3 ) (42)

By solving the system (42), we identify the expressions of α , β , δ and γ stated in the Theorem 2 and from which it can be deduced the values of probabilities of the reduced graph.

{ α = p 1 p 2 p 3 p 5 p 6 p b [ 1 p 1 p a p 4 p a + p 1 p 4 p a ] β = p 1 p 2 p 3 p 4 p 5 p 6 p a p b [ q 3 q 4 p 3 p 4 + q 2 q 5 p 2 p 5 + q 2 q 4 p 2 p 4 + q 1 q 5 p 1 p 5 + q 1 q 6 p 1 p 6 + q 3 q 5 p 3 p 5 + q 2 q 6 p 2 p 6 ] γ = p 1 p 2 p 3 p 4 p 5 p 6 p a p b [ 1 + q 1 p 1 + q 2 p 2 + q 3 p 3 + q 4 p 4 + q 5 p 5 + q 6 p 6 ] δ = p 1 p 2 p 4 p 5 p a [ 1 p 3 p b p 6 p b + p 3 p 6 p b ]

Ω = ( γ + α ) ( γ + β ) ( δ + γ ) γ 2 ; p 1 = γ γ + α C ; p 2 = γ γ + β ;

p 3 = γ γ + D δ ; p a = γ + α C γ + α ; p b = γ + D δ γ + δ

At this step, we state that all the mathematical relations are clearly identified, and the values of the probabilities of the reduced graph components (nodes and edges) can be calculated at each step of the reduction process until the final reduced graph which corresponds to a chain.

Thus, the following algorithm presents the different steps to reach the solution.

3.2. Algorithm Description

Begin

Input data: structure of the graph and the probability of nodes and edges

G = ( V , E ) : Graph must be composed by one connected component (V: nodes; E: Edges)

P i , j = ( E i , E j ) : Associated matrix constructed from the edges of the graph

K V , | K | 2

M = 1

While there is a simple reduction of the following types:

Call procedures:

-Series reductions: P i = P j × P k ; remove the link ( E i , E j ) and updating the probability vector and the matrix associated with the graph.

-Parallel reduction R ( G ) = Ω R ( G ) : P i = 1 ( 1 P j ) × ( 1 P k ) ; re- move one of the links and update the vector of probabilities and the matrix associated with the graph.

-Reduction of degree 2. Let M = M × Ω for each reduction.

end_while.

Start by exploring the complex substructure (polygons).

Let s the initial node.

Determine the ascending nodes of the first, the second level and the lower levels, according to the polygon type)

While a polygon exists

If a polygon of type T exists, apply the corresponding reduction of this type of subgraph. Note: One always begins with seeking that of type 1, type 2, etc.

- Store in a stack the links to be removed.

- Remove the corresponding links in the graph associated matrix.

- Rebuilt the new chains from the links stored by forging the links in the matrix of associated graph

- Update the vector of probabilities with the new values for each type T.

- Update the vector of probabilities.

- Update the associated matrix of the graph.

end-if

end-while

Construct the graph from the resulting matrix.

if the obtained matrix is a simple one

Calculating the reliability as the product of probability links

else

Print “Matrix is no longer decomposable”

Apply any other algorithm that calculates the reliability (SDP BDD…)

end_if

Display the reliability value of the graph G

end_of_the algorithm.

4. Application

Suppose that the nodes and edges all are imperfect except the initial and the terminal nodes (s, t). We consider that their associated probability values are equal to 0.9. The probabilities value of nodes s and t are equal to 1. Using the following network

The associated matrix and the probabilities vectors relative to the graph in Figure 8 are:

G = [ e 1 e 2 e 3 e 5 e 4 ] ; P e d g e = ( p 1 , p 2 , p 3 , p 4 , p 5 ) ;

P N o d e s = ( p s = 1 , p a , p b , p t = 1 )

Node_inital = S; Stack = Node_inital

List-succ(s) = (a, b)

Stack = Stack È List-succ(s) (queue = {s, a, b}

X = pop(Stack) = {b}

Y = List-succ(X) = {a, t}

if Y ¹t

Z = X Ç Stack = (b) Ç (s, a) = (a)

Then the polygon is of type 1

Updating of the vectors and the matrix:

G = [ e 1 e 2 e 5 e 4 ] ; P e d g e = ( p 1 = δ δ + A C , p 2 = δ δ + B D , 0 , p 4 , p 5 ) ;

P N o d e s = ( 1 , p a = δ + A C δ + A , p b = δ + B D δ + B , 1 )

X = pop(Stack) = {a}

Y = Liste-succ(X) = {t}

if Y = t

Prob = Prob × Prob(X, t) = 1 × p 5 = p 5

Stack = pop(Stack) = {s}

Prob = Prob×Prob(Pile, X) = p 5 × p 1 × p a

end

(a) (b)

Figure 8. A simple testing graph: (a) the original graph, (center) parallel-series reduction, (b) the reduced graph (chain).

Updating of the vectors and the matrix:

e 1 = ( s , a )

G = [ e 2 e 1 e 4 ] ; P e d g e = ( p 1 = P r o b , p 2 = δ δ + B . D , 0 , p 4 , 0 ) ;

Prob = 1

Liste-succ(s) = {b}

Stack = Stack È Liste-succ(S) ( then Stack = (s, b))

X = pop(Pile) = {b}

Y = Liste-succ(X) ={t}

if Y = t

Prob = Prob × Prob(X, t) = 1 × p 4 = p 4

Stack = pop(Stack) = {s}

Prob = Prob × Prob(Pile, X) = p 4 × p 2 × p b

Updating of the vectors and the matrix:

e 2 = ( s , t )

G [ e 1 e 2 ] ; P e d g e = ( p 1 = P r o b , p 2 = P r o b , 0 , 0 , 0 ) ;

P e d g e = ( p 1 = 1 ( 1 q 1 ) × ( 1 q 1 ) , 0 , 0 , 0 , 0 )

end_if

end_Algorithm

Calculus:

function imperfect()

p1 = .9

p2 = .9

p3 =.9

pa = .9

pb = .9

A = p2*pb*(1-p1*pa-p3*pa+p1*p3*pa)

B = p1*pa*(1-p2*pb-p3*pb+p2*p3*pb)

delta = pa*pb*(p1*p2+p1*p3+p2*p3-2*p1*p3*pa)

C=(pa*(1-p1)*(1-p3))/((1-pa) +pa*(1-p1)*(1-p3))

D=(pb*(1-p2)*(1-p3))/((1-pb) +pb*(1-p2)*(1-p3))

omega = (delta + A)*( delta + B)/ delta

p1p = delta /( delta + A*C)

p2p = delta /( delta + B*D)

pap = (delta + A*C)/( delta + A)

pbp = (delta + B*D)/( delta + B)

x = 1-(1-p1p*pbp*.9)*(1-p2p*pap*.9)

y = x*.81*omega

end

A = B = 0.08829; eta = 0.78732; C = D = 0.0825688073394495; p1p = p2p = 0.990825688073394; pap = pbp = 0.907493061979649; omega = 0.9738008333333333.

As the graph turned into two parallel chains, the reliability of the network is computed as follows:

R = 1 - (1 - p2p*pbp * p4)*(1 - p1p*pap * p4) = 0.963614702184995

R(G) = R * omega * Ps * Pt = 0.963614702184995 * 0.9738008333333333 * 0.9 * 0.9 * = 0.760078728.

5. Conclusion

This paper presents a computational technique determining the reliability of networks. In such networks, it is considered that edges and nodes can fail randomly and the failure events are supposed to be s-independent or not. The used techniques combine some algorithms based on the factoring theorem and series-parallel reductions. The algorithm tries first to identify seven types of structures if possible and when one of them is found, such structure is removed and replaced by a more simple chain. Logically, all the remained components’ values are substituted by new values determined by the derived mathematical expressions. The correctness of the algorithm is not hard to show and it can be observed that at most 2 | E | | V | can ever pass through T (T is a stack structure) before T becomes empty (Satyanarayana and Wood (1985)) and the algorithm still of linear complexity. These techniques are very easy to be integrated to a large software reliability system that can also determine solutions for optimizing the reliability, the availability and the maintainability of critical systems’ design. Future extensions of this work consist of determining some efficient procedures and heuristics to select edges and nodes that can be primary used as pivot for generating the most possible fast solution.

Cite this paper

Rebaiaia, M.-L. and Ait-Kadi, D. (2017) System Reliability Evaluation for Imperfect Networks Using Polygon-to-Chain Reduction. American Journal of Operations Research, 7, 201-224. https://doi.org/10.4236/ajor.2017.73014

References

  1. 1. Institute of Electrical and Electronics Engineers (1990) IEEE Standard Computer Dictionary: A Compilation of IEEE Standard Computer Glossaries. IEEE Std 610, 1-217.

  2. 2. Deo, N. and Medidi, M. (1992) Parallel Algorithms for Terminal-Pair Reliability. IEEE Transactions on Reliability, 41, 201-209. https://doi.org/10.1109/24.257782

  3. 3. Dotson, W.P. and Gobien, J. (1979) A New Analysis Technique for Probabilistic Graphs. IEEE Transactions Circuits and Systems, 26, 855-865. https://doi.org/10.1109/TCS.1979.1084573

  4. 4. Fratta, L. and Montanari, U.G. (1973) A Boolean Algebra Method for Computing the Terminal Reliability in a Communication Network. IEEE Transactions on Circuit Theory, 20, 203-211. https://doi.org/10.1109/TCT.1973.1083657

  5. 5. Heidtmann, K.D. (1989) Smaller Sums of Disjoint Products by Subproduct Inversion. IEEE Transactions on Reliability, 38, 305-311. https://doi.org/10.1109/24.44172

  6. 6. Kuo, S.Y., Yeh, F.M. and Lin, H.Y. (2007) Efficient and Exact Reliability Evaluation for Networks with Imperfect Vertices. IEEE Transactions on Reliability, 56, 288-298. https://doi.org/10.1109/TR.2007.896770

  7. 7. Lin, H.Y., Kuo, S.Y. and Yeh, F.M. (2003) Minimal Cutset Enumeration and Network Reliability Evaluation by Recursive Merge and BDD. Proceedings of the 8th IEEE International Symposium on Computers and Communication, 2, 1530-1346.

  8. 8. Liu, H.H., Yang, W.T. and Liu, C.C. (1993) An Improved Minimizing Algorithm for the Summation of Disjoint Products by Shannon’s Expansion. Microelectronic Reliability, 33, 599-613.

  9. 9. Misra, K.B. (1970) An Algorithm for the Reliability Evaluation of Redundant Networks. Transactions on Reliability, R-9, 146-151. https://doi.org/10.1109/TR.1970.5216434

  10. 10. Tarjan, R.E. (1972) Depth First Search and Linear Graph Algorithms. SIAM Journal of Computing, 1, 146-160. https://doi.org/10.1137/0201010

  11. 11. Yan, L. and Taha, H.A. (1994) A Recursive Approach for Enumerating Minimal Cutsets in a Network. IEEE Transaction on Reliability, 43, 383-388. https://doi.org/10.1109/24.326430

  12. 12. Yoo, Y.B. and Deo, N. (1988) A Comparison of Algorithms for Terminal-Pair Reliability. IEEE Transactions on Reliability, 37, 210-215. https://doi.org/10.1109/24.3743

  13. 13. Locks, M.O. and Wilson, J.M. (1992) Note on Disjoint Products Algorithms. IEEE Transactions on Reliability, 41, 81-84. https://doi.org/10.1109/24.126676

  14. 14. Simard, C. (1996) Contribution au problèmed’évaluation de la fiabilité des réseaux. Master Thesis, Laval University, Quebec, Canada, TJ-7.5-UL-1996.

  15. 15. Moskowitz, F. (1958) The Analysis of Redundancy Networks. Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics, 77, 627-632.

  16. 16. Page, L.B. and Perry, J.E. (1988) A Practical Implementation of the Factoring Theorem for Network Reliability. IEEE Transactions on Reliability, 37, 259-267. https://doi.org/10.1109/24.3752

  17. 17. Page, L.B. and Perry, J.E. (1989) Reliability of Directed Network Using the Factoring Theorem. IEEE Transactions on Reliability, 38, 556-562. https://doi.org/10.1109/24.46479

  18. 18. Rebaiaia M.L. (2011) A Contribution to the Evaluation and Optimization of Networks Reliability. PhD Thesis, Laval University, Canada.

  19. 19. Resende, M.G.C. (1986) A Program for Reliability Evaluation of Undirected Networks via Polygon-to-Chain Reductions. IEEE Transaction on Reliability, 35, 24-29. https://doi.org/10.1109/TR.1986.4335334

  20. 20. Satyanarayana. A. and Chang M. (1983) Network Reliability and the Factoring Theorems. Networks, 13, 107-120. https://doi.org/10.1002/net.3230130107

  21. 21. Satyanarayana, A. and Wood, R.K. (1985) A Linear-Time Algorithm for Computing K-Terminal Reliability in Series-Parallel Networks. SIAM Journal on Computing, 14, 818-832. https://doi.org/10.1137/0214057

  22. 22. Theologou, R. and Carlier, J.G. (1991) Factoring & Reduction for Networks with Imperfect Vertices. IEEE Transactions on Reliability, 40, 210-217. https://doi.org/10.1109/24.87131

  23. 23. Hardy, G., Lucet, C. and Limnios, N. (2007) K-Terminal Network Reliability Measures with Binary Decision Diagrams. IEEE Transaction on Reliability, 56, 506-515. https://doi.org/10.1109/TR.2007.898572

  24. 24. Rudell, R. (1993) Dynamic Variable Ordering for Ordered Binary Decision Diagrams. Proceedings of the IEEE International Conference on Computer Aided Design, Santa Clara, CA, 7-11 November 1993, 42-47.

  25. 25. Nakazawa, H. (1976) Bayesian Decomposition Method for Computing Reliability of Oriented Network. IEEE Transactions on Reliability, R-25, 77-80. https://doi.org/10.1109/TR.1976.5214983

  26. 26. Kubat, B. (1989) Estimation of Reliability for Communication/Computer Networks-Simulation/Analytic Approach. IEEE Transactions on Reliability, 37, 927-933. https://doi.org/10.1109/26.35372

  27. 27. Rebaiaia, M.-L. and Ait-Kadi, D. (2015) Reliability Evaluation of Imperfect K-Terminal Stochastic Networks Using Polygon-to-Chain and Series-Parallel Reductions. Proceedings of the 11th ACM Symposium on QoS and Security for Wireless and Mobile Networks, Cancun, Mexico, 2-6 November 2015, 115-122.

  28. 28. Valian, L.G. (1979) The Complexity of Enumerating and Reliability Problems. SIAM Journal of Computing, 8, 410-421. https://doi.org/10.1137/0208032

  29. 29. Ball, M.O. (1986) Computational Complexity of Network Reliability Analysis: An Overview. IEEE Transactions on Reliability, 35, 230-239. https://doi.org/10.1109/TR.1986.4335422

  30. 30. Rosenthal, A. (1974) Computing Reliability of Complex Systems. PhD Thesis, University of California, Berkeley.

  31. 31. Wood, R.K. (1986) Factoring Algorithms for Computing K-Terminal Network Reliability. IEEE Transactions on Reliability, 35, 269-278. https://doi.org/10.1109/TR.1986.4335431

  32. 32. Barlow, E.B. and Proschan, F. (1975) Statistical Theory of Reliability and Life Testing: Probability Models (International Series in Decision Processes), (Ed.) Rinehart & Winston, Holt.

  33. 33. Moore, E.F. and Shannon, C.E. (1956) Reliable Circuits Using Less Reliable Relay. Journal of the Franklin Institute, 262, 281-297.

  34. 34. Murchland, J. (1973) Calculating the Probability That a Graph Is Disconnected. Working Paper No. 18.

  35. 35. Wang, S.-D. and Sun, C.-H. (1996) Transformations of Star-Delta and Delta-Star Reliability Networks. IEEE Transactions on Reliability, 45, 120-126. https://doi.org/10.1109/24.488927

  36. 36. Choi, M.S and Jun, C-H. (1995) Some Variants of Polygon-to-Chain in Evaluating Reliability of Undirected Networks. Microelectronics Reliability, 35, 1-11. https://doi.org/10.1016/0026-2714(94)P1833-X

Appendices A: Table Representing Seven Polygon-to-Chain Reductions