Mobile Edition
Print
Get the Mag
Weekly Updates1. Introduction
Ever since the initial development of reliability engineering, network reliability has been an area of considerable research activity. Network reliability theory has been extensively applied to many real-world systems including computer and communication systems, power transmission and distribution systems, transportation systems, oil/gas production systems, computer networks, cellular telephone networks, etc.
The evaluation of network reliability is a NP-hard problem (Colbourn, 1987; Shier, 1991). Reliability evaluation approaches exploit a variety of tools for system modeling and reliability index calculation. The network reliability is defined as the probability of the connection of the source node with target nodes. Depending on how the method used to transfer the flow (or signal) satisfies the flow conservation law there are two categories of network reliability problems that can be defined: the Multi-state Arc Network (MAN) (Shen, 1995; Nahman, 1997; Lin, 2004, 2006; Soh, 2005; Sohn, 2005; Yeh, 2005) and the Multi-state node network (MNN) (Malinowski and Preuss, 1996; Levitin, 2001, 2005; Lisnianski and Levitin, 2003; Yeh, 2003a, 2006a). In a MAN each arc has a non-negative integer-valued random variable capacity (multi-state arc) and all flows in the network obey the conservation law. Conversely, all nodes in a MNN violate the conservation law. It has a source node (position) where the signal source is located, a number of sink nodes that only receive the signal and a number of intermediate nodes that retransmit the received signal to other nodes. A non-sink node has a number of states that are determined by the set nodes that directly receive a signal from it. These approaches have their own applications, for example electrical power distribution can be modeled as a MAN, and computer networks or cellular telephone networks can be modeled as a MNN (Levitin, 2001; Yeh, 2003b).
Many methods had been developed to solve the MAN reliability problem including methods based on cut/path sets (Nahman, 1997; Lin, 2004, 2006; Soh, 2005; Sohn, 2005; Yeh, 2005) which can calculate the exact value for the reliability, and approximate methods (Marseguerra et al., 2005; Rocco and Zio, 2005; Boudali and Dugan, 2006; Yeh, 2007), which can estimate an approximate value for the network reliability and thus avoid the NP-hard problem faced by the cut/path-based methods. To the author's best knowledge, Acylic MNNs (AMNNs) were first investigated by Malinowski and Preuss (1996). For the one-to-all targets (between the source node and all target subsets) the best-known algorithm for AMNN reliability evaluation was proposed by Levitin (2001) using a Universal Generating Function (UGF). Yeh (2003b) proposed an arts-based algorithm for the one-to-one AMNN reliability evaluation problem. Yeh (2006a) improved the UGF approach using a simple technique, and also showed that every AMNN reliability problem could be solved using any of the existing traditional binary-state network reliability algorithms using a special code for the state probability (Levitin, 2001; Yeh, 2003b).
The UGF Method (UGFM) was introduced in Ushakov (1986) and it has proved to be very effective in evaluating the reliability of different types of multi-state networks (Levitin, 2001, 2005; Lisnianski and Levitin, 2003; Yeh. 2006a), and it does not require a great computational effort. The UGFM is straightforward, effective and universal (Levitin, 2005). It involves intuitively simple recursive procedures combined with simplification techniques. The best known UGFM for the one-to-all MNN reliability evaluation problem was proposed by Yeh (2006a), however, it is only effective for AMNN problems. MNNs are more practical and reasonable than AMNNs. In real-life cases, many networks such as computer and telecommunications networks include cycles for redundancy and overload prevention. Thus, there is a need for a new UGFM to evaluate the reliability of one-to-all MNNs.
[FIGURE 1 OMITTED]
[FIGURE 3 OMITTED]
Assumptions The MNN satisfies the following assumptions.
1. Each arc is perfectly reliable.
2. The signal can be retransmitted without following the flow conservation law.
3. All of these state probabilities for each non-sink node are random variables according to a given distribution and assumed to be statistically independent.
4. The network is connected and free of self-loops.
3. An introduction to the UGF method
Before introducing the proposed UGFM, a brief introduction to the original UGFM with some useful properties is given here. The detailed description of the existing known UGFMs applied to network reliability estimation problems is presented by Levitin (2005). There are two types of UGFs used in traditional UGFMs: one is the individual UGF (called the node UGF here) and the other is the group UGF (called the subnetwork UGF) which is formed by unifying the node UGFs in a recursive way using special operators, e.g., the multiplication operator. Each time a new node UGF is produced it is merged into the current subnetwork until all possible node UGFs are in the final subnetwork UGF. Both kinds of UGFs record all their own possible states. The node UGF is defined as a polynomial function of z:
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)
where the exponent I is a state of i, i.e., a node subset emanating from node i, and coefficient [p.sub.i]:I is the probability that node i can send a signal to I. The subnetwork UGF U(i) of [G.sub.i], is defined also by a polynomial function of z:
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)
where i [??] T, the exponent I [[subset].bar] V - [V.sub.i] is a node subset (state) which can receive a signal via [G.sub.i], and the coefficient [[pi].sub.[[upsilon]-1:I]] is a MTP which is the probability that the signal can reach state I from node 1 via [G.sub.i].
Whether in the node UGF or in the subnetwork UGF, each exponent represents the state and each coefficient shows the event probability of the state listed in the exponent. It is trivial that the following relationships between u(i) and U(i) are true.
Property 1. The following statements are true.
1. [p.sub.1]:[empty set][Z.sup.[empty.set]] [??] u (1).
2. u(1) = U (1).
3. If [e.sub.ij] [member of] E, then the terms [p.sub.i:j][Z.sup.j] and [[pi].sub.i:j][Z.sup.j] are always in u(i) and U(i), respectively.
4. The terms with respect to [z.sup.i] are not in the final result of U(i).
To obtain the subnetwork UGF U(i), a recursive expression and the multiplication operator [cross product] are introduced as follows:
U(i) = U(i - 1) [cross product] u(i) (3)
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)
where
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)
otherwise.
For example, let
u(1) = [p.sub.1:2][z.sup.2] + [p.sub.1:3][z.sup.3] + [p.sub.1:23][z.sup.23] (note that [p.sub.1:[empty set]][z.sup.[empty set]] [??] u(1)), (7)
u(2) = [p.sub.2:[empty set]][z.sup.[empty set]] + [p.sub.2:3][z.sup.3] + [p.sub.2:5][z.sup.5] + [p.sub.2:35][z.sup.35], (8)
then
U(2) = U(1)[cross product]u(2) (9)
= u(1)[cross product]u(2) (10)
= ([p.sub.1:2][z.sup.2] + [p.sub.1:3][z.sup.3] + [p.sub.1:23][z.sup.23])[cross product]([p.sub.2:[empty set]][z.sup.[empty set]] + [p.sub.2:3][z.sup.3] + [p.sub.2:5][z.sup.5] + [p.sub.2:35][z.sup.35]) (11)
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)
= [[pi].sub.2:[empty set]][z.sup.[empty set]] + [[pi].sub.2:3][z.sup.3] + [[pi].sub.2:5][z.sup.5] + [[pi].sub.2:35][z.sup.35], (13)
where (after collecting like terms)
[[pi].sub.2:[empty set]] = [p.sub.1:2][p.sub.2:[empty set]], (14)
[[pi].sub.2:3] = [p.sub.1:2][p.sub.2:3] + [p.sub.1:3][p.sub.2:[empty set]] + [p.sub.1:3][p.sub.2:3] + [p.sub.1:23][p.sub.2:[empty set]] + [p.sub.1:23][p.sub.2:3], (15)
[[pi].sub.2:5] = [p.sub.1:2][p.sub.2:5] + [p.sub.1:3][p.sub.2:5] + [p.sub.1:23][p.sub.2:5], (16)
[[pi].sub.2:35] = [p.sub.1:2][p.sub.3:5] + [p.sub.1:3][p.sub.2:35] + [p.sub.1:23][p.sub.2:35], (17)
The multiplication operator [cross product] is very similar to multiplication except the exponent part of the z. It plays a central role in UGFMs. It also satisfies the commutate rule and associated law.
Property 2. A [cross product] B = B [cross product] A, and (A + B) [cross product] C = A [cross product] C + B [cross product] C, where A, B, and C are either a UGF or terms of a UGF (e.g., [p.sub.i:I][Z.sup.I] and/or [[pi].sub.i:I][Z.sup.I]).
After locating U(V - T|), the coefficients of [z.sup.J], i.e., [[pi].sub.[V - T:J]], are determined for all non-empty target subsets J. The last step is to calculate the exact reliability between node 1 and each non-empty target subset in terms of [[pi].sub.[V - T:J]] The next property discusses the relationships between [pi], r and R.
Property 3. [[pi].sub.[V - T:J]] = [[gamma].sub.J] for all non-empty target subsets J, and [r.sub.T] = [R.sub.T].
The following theorem is very important. It is implemented in the final step of all UGFMs including the proposed UGFM for calculating the exact AMNN reliability. It follows immediately from the fundamental property of set theory and reliability theory (Levitin, 2005). Its proof is omitted and it is employed in the example of Section 5 to evaluate the MNN reliability.
Theorem 1. The MNN reliability from node 1 to the nonempty target subset J is given by
[R.sub.J] = [[union].sub.[J[subset]1]][r.sub.1] for all I [[subset].bar] T. (18)
The UGFM is a complete examination of all possible states of each node/subnetwork UGF which implies its correctness. From the above discussion, the key point to successful implementation of the UGFM is that each state of the nodes and subnetworks must be correct and completely included in the UGF. The node UGF is a fundamental properly of the UGFM, and the subnetwork UGF is developed using the multiplication operator. Hence, the node UGF and the multiplication operator of UGFMs need to be carefully redefined to achieve the key point for MNN reliability evaluation.
FEED