# An Efficient Universal Generating Function-Based Analyzing Approach for Multistate System with Imperfect Coverage Failure

Authors: Zheng Li; Jinlei Qin
Journal: Complexity
 (2021)

---

## Abstract

A system with more than two states is called a multistate system (MSS), and such systems have already become a general trend in the arena of complex industrial products and/or systems. Fault-tolerant technology often plays a very important role in improving the reliability of an MSS. However, the existence of imperfect coverage failure (ICF) in a work-sharing group (WSG) decreases the reliability of MSS. A method is proposed to assess the reliability and sensitivity of an MSS with ICF. The components in a WSG can cooperate so as to improve overall efficiency by increasing performance levels. Using the technique of the universal generating function (UGF), a component’s UGF expression with ICF can be incorporated in two steps. During the computation of the system’s UGF, an algorithm based on matrix (ABM) is developed to reduce the computational complexity. Consequently, indices of reliability can be easily calculated based on the UGF expression of an MSS. Sensitivity analysis can help engineers judge which WSG should be eliminated first under various resource limitations. Examples illustrate and validate this method.


---

## Body

## 1. Introduction

The fault-tolerant system is a high-reliability system designed by incorporating redundant components for critical elements in order to prevent the overall system from failing even when some of its individual elements fail. Fault-tolerant systems are often used in life-critical applications such as flight control, nuclear plant monitoring, and space missions and in mission-critical computer monitoring systems and data storage systems [1]. In addition to redundancy, the implementation of fault tolerance also requires automatic recovery and reconfiguration mechanisms. That is to say, even if sufficient redundancy exists, if the system cannot adequately detect, locate, and recover from internal faults and/or errors that have occurred, the entire system or one of its subsystems can fail [2]. The degree of fault tolerance is determined by the proportion of faults from which a system automatically recovers, and these faults are said to be covered by the recovery strategy [3]. Therefore, the reliability analysis of such systems must take into account the process by which faults and errors are detected and recovered from, as well as the complex system structure.The problem of determining a system’s fault tolerance and its trend have been intensively explored, with special methods and analysis techniques to evaluate the system reliability having been put forward [4]. A new, simple, and efficient approach is presented for incorporating imperfect fault coverage into a combinational model [5]. The optimal design of some systems subjected to the imperfect fault coverage has been formulated for G: (k/n) structures [6]. Furthermore, the optimal reliability of systems subjected to the same reason, imperfect fault coverage, has already been generalized to more systems including parallel-series, series-parallel, parallel, etc., and the non s-identical component case [7]. According to the type of fault-tolerant techniques, the appropriate modeling method of multifault coverage is suggested for evaluating reliability indices in fault-tolerant system, and it is easy to be used in the case of hierarchy structure of fault-level coverage groups [8]. An approach based on a binary decision diagram is proposed to analyze the reliability and sensitivity of a benchmark network [9]. Based on the total probability theorem and a divide-and-conquer strategy, a new combinational approach to handling functional dependency has been put forward in the reliability analysis of imperfect coverage systems [10]. A long-neglected issue is that an initially relevant component could become irrelevant after the failures of other components, and this issue has been modeled through the coverage of irrelevant components in the system with imperfect fault coverage [11].The MSS reliability theory and related conceptions have been investigated from many aspects. In an MSS, the system and its elements can function at a range of different performance levels, e.g., from perfect operation to complete failure. A universal moment generating function is extended to incorporate common cause failure into MSS reliability estimation [12]. A new second-order reliability method without parabolic approximation of the fitted quadratic surface is presented to improve the accuracy of reliability analysis [13]. The reliability modeling of MSS with preventive maintenance and customer demand is proposed to improve the reliability of MSS [14]. Employing Kalman filtering approach to estimate system and degraded sensor state is the base to calculate reliability for making a dynamic maintenance decision [15]. A life cycle cost reliability model with copula is established for system with multiple dependent degradation processes and environmental influence [16]. Simulation is often used to evaluate MSS because of its computational complexity directly by analytical method [17]. Similarly, an efficient simulation method based on survival signature has been proposed for system reliability analysis [18]. A complex framework based on integrated direct partial logic derivative (DPLD), whose computational complexity correlates with the number of system components and does not dependent on the structural complexity of MSS, is developed for qualitative and quantitative analysis focusing on component criticality [19]. Calculating critical system state with DPLD, multivalued logic method is used for the reliability analysis of MSS [20]. Application of structural function is presented in time-dependent reliability analysis, and DPLDs can be also used to find formulae for computation of most commonly known time-dependent importance measures [21]. Besides those approaches mentioned above for reliability, it is also critical to determine the impact of each component on MSS performance. Due to the nonbinary state of MSS and their components as well as dependences among different states of the same component, the performability analysis of MSS becomes more difficult and multivalued decision diagram is presented as an efficient algorithm to analyze the MSS [22]. Degraded performance is a common phenomenon in industrial products, and reliability is a vital quality of the MSS for providing the required performance level. An integrated routing risk model is constructed and risk control performance is also proved by simulated algorithm [23]. Other risk assessment model and risky multicriteria decision-making steps are developed [24, 25]. Focusing on performance analysis and optimization, a wireless sensor network framework is constructed [26, 27]. Regarding industrial cyberphysical system, safety control and performance monitoring are also focused on to answer how urgent they are and what degrees of fault tolerance and fault recovery are needed [28–30]. Although many researchers devote efforts on different aspects of system reliability and performance, the issue of computational complexity for an MSS is often notorious one because of the curse of “dimension explosion.”An MSS can also be subjected to imperfect coverage failures that lead to the entire failure of the whole system or its subsystems. Based on the ordered binary decision diagram, an efficient algorithm for the reliability evaluation of an MSS with a combinational performance requirement subject to imperfect fault cover has been proposed [31]. Considering the importance of the system-component state of an MSS, Griffith’s importance measures and reliability are evaluated by the combination of conditional probability methods to find solutions for the multistate imperfect fault coverage model [32]. An optimal structure of an MSS with uncovered failure can attain maximum reliability through a proper balance between two types of task parallelization: parallel task execution with work sharing and redundant task execution [33]. The MSS with three different types of imperfect fault coverage, element-level coverage, fault-level coverage, and performance-dependent coverage, has been modeled for evaluating the reliability of the system [34]. Hereafter, the similar two types of parallelization of MSS with multifault coverage have been studied to obtain the optimal trade-off based on various settings of fault coverage factor [35]. Stochastic multivalue models are proposed to predict the reliability of a multistate phase-mission system with three different imperfect fault coverage conditions, and the efficiency of this model is compared with the universal generating function (UGF) technique [36]. Within a subsystem of MSS, when the effectiveness of recover mechanism depends on the entire performance level of the subsystem, the MSS performance distribution can be obtained by a recursive procedure based on the UGF [37]. A modification of generalized reliability block diagram method is suggested for the reliability assessment of MSS with imperfect multifault coverage [38]. However, the computational time of these models and methods is proportional to the number of components and, hence, is of high computational complexity. UGF is a tool for efficiently dealing with the performance distribution of a complex MSS [39], and many reliability assessment studies of MSS have adopted it as the primary analysis tool [40–43].The novelty of this paper lies in that a revised approach based on the UGF technique is proposed to assess the reliability of an MSS with imperfect coverage failures (ICFs). Here the ICF is modeled by incorporating a scheme of working-share group (WSG), which is similar to the parallel structure. However, they are two different types of data-transmitting schemes. During the assessment, an algorithm based on matrix (ABM) is developed to significantly reduce the computation complexity. This approach is compared with other methods on time consumption. Furthermore, the sensitivity analysis can be handled by the engineers to decide which work group with ICF should be eliminated first under the limited conditions.The remainder of this paper is organized as follows. Section2 describes the imperfect coverage failure model. In Section 3, the UGF technique is revised to incorporate the ICF in order to perform the reliability and sensitivity analysis for the MSS with ICF. In Section 4, this approach is illustrated by several applications. Section 5 includes the authors’ conclusions and suggests future research dealing with the reliability of MSS.


## 2. Modeling of Imperfect Coverage and MSS

### 2.1. Imperfect Coverage Model

There are many models developed for the ICF, such as element-level coverage models and fault-level coverage models. Here, the focused structure of the imperfect coverage failure model with single point failure can be modeled as shown in Figure1 for reliability analysis [10, 44]. The single point failure is also refereed as single fault at a component where its coverage probability is solely depended on the properties of the failed component. The entry point to the model signifies an occurrence of a single point failure with three types of possible outcomes. They are three types of exits—R, C, S—that signify, respectively, different possible outcomes with different exit probabilities r,c,ands. Exit R indicates that the offending failure is transient and can be handled without discarding the component. Exit C implies an occurrence of a permanent covered failure in the component that needs to be discarded for the normal operation of the system. Exit S is a single point failure signifying that the uncovered failure without discarding the component leads to the system failure. When a single point failure occurs, there are the three types of possible outcomes. So, they consist of a partitioning of the event space, and the three exit probabilities sum to one, namely, r+c+s=1. For the multipoint failures, it is to descript system failure because of concurrent faults on multiple components. And it will be modeled and studied in the future.Figure 1
Imperfect coverage model with single point failure of a component.In order to improve the reliability of a fault-tolerant system with imperfect coverage failures, a scheme of a work-sharing group (WSG) is introduced [33]. A WSG usually consists of several identical components that are connected in parallel and form a set. Every component will fulfill a different subtask so that its WSG can finish the entire task. For a multichannel data transmission system from A to B, as shown in Figure 2, the components C1 and C2 make up a WSG to share the work under the reconfiguration of a data exchange management system (DEMS). Here, the DEMS can be assumed that it does not fail because its form of existence can be implemented as built-in software or other forms. The WSG is parallel with component C3 so that they can undertake the data transmission task together. Because of the existence of DEMS, the same tasks that the data packages are transmitted by C3 as DP3 are divided into two sections, DP1 and DP2, according to the performance of components C1 and C2. Under this assumption, if one component in the WSG, such as C1, fails, the DEMS can discover it and will not assign data packages to it again. This type of failure can be defined as covered failure. The DEMS will then reassign the data transmission task to C2. The WSG will not completely fail, but its performance will decrease consequently. However, if C1 fails but the DEMS cannot discover it and continues to assign data transmission to C1, C1 will be in a state of exit s, namely, single point failure. The failure occurred in this situation can be defined as uncovered failure and the WSG cannot finish the task of data transmission.Figure 2
The working scheme of WSG.The sole purpose of a parallel structure is to improve the reliability of the system. However, if there is no DEMS, the data packages will not be divided, and the efficiency of the system cannot be improved to transmit the data packages. Introducing the WSG into the system will increase efficiency, but due to the change in the system structure, reliability may be affected.


### 2.2. Modeling of MSS

For the purpose of modeling an MSS, the characteristics of its elements must first be defined. Generally speaking, any elementi in MSS can have mi+1 different states corresponding to the performance levels that can be represented by the set ai=ai0,ai1,…,aimi, where ais is the performance level of element i in the state s, s∈0,1,…,mi. The current performance level Ai of element i at any instant in time is a discrete random variable that takes value from ai: Ai∈ai. The probabilities of each different state or performance level for element i can be denoted by the set pi=pi0,pi1,…,pimi, where(1)pis=PrAi=ais.Furthermore, the entire states of one element constitute a whole set whose states can be seen as mutually exclusive events. That is to say, the elementi will always be in one and only one of mi+1 states, such that(2)∑s=0mipis=1.The performance level distribution of elementi will be determined completely by the collection of pairs(3)CPi=ais,pis,s=0,1,…,mi.The system elements have certain performance levels corresponding to their respective states at one instant in time. The modeling of an MSS performance level is completely determined byCPi,i=1,2,…,n. Therefore, the states of an MSS are determined completely by the states of its components. Now, suppose that the MSS has k+1 different states and the performance level corresponding to one state of the MSS at a certain moment can be represented by wj,j=0,1,…,k. In this case, the MSS performance level is a random variable denoted by W that takes values from the set(4)W=w0,w1,…,wk.The probability mass function (PMF) of the MSS performance levels can be obtained as follows:(5)qj=PrW=wj,j=0,1,…,k.Using the Cartesian product operation, we can define the space of all possible combinations of performance levels for all system components as(6)Cn=∏i=1nai0,ai1,…,aimi.The MSS structure function is naturally introduced as(7)ΦA1,A2,…,An:Cn⟶W.The function is to map the space of the component’s performance levels into the space of the performance levels of an MSS.From the above analysis, we can see that the model of an MSS includes two parts: PMF of performance levels for all system components and the structure function of the system. These can be rewritten as follows:(8)ai,pi,0≤i≤n,W=ΦA1,A2,…,An.For an MSS whose performance level is defined as task completion time, its reliability can be expressed as the probability that the system satisfies the maximum allowed completion time ofδ. From (5), one can obtain(9)Rδ=∑j=0MqjΔwj,δ,where(10)Δwj,δ=1,ifwj≤δ,0,ifwj>δ.Another important measure is the conditional expected performanceΩδ. This expresses the system’s expected performance under the condition that the MSS is in an acceptable state. Having the system reliability Rδ, this measure can be calculated by(11)Ωδ=∑j=0MqjwjΔwj,δRδ.


## 2.1. Imperfect Coverage Model

There are many models developed for the ICF, such as element-level coverage models and fault-level coverage models. Here, the focused structure of the imperfect coverage failure model with single point failure can be modeled as shown in Figure1 for reliability analysis [10, 44]. The single point failure is also refereed as single fault at a component where its coverage probability is solely depended on the properties of the failed component. The entry point to the model signifies an occurrence of a single point failure with three types of possible outcomes. They are three types of exits—R, C, S—that signify, respectively, different possible outcomes with different exit probabilities r,c,ands. Exit R indicates that the offending failure is transient and can be handled without discarding the component. Exit C implies an occurrence of a permanent covered failure in the component that needs to be discarded for the normal operation of the system. Exit S is a single point failure signifying that the uncovered failure without discarding the component leads to the system failure. When a single point failure occurs, there are the three types of possible outcomes. So, they consist of a partitioning of the event space, and the three exit probabilities sum to one, namely, r+c+s=1. For the multipoint failures, it is to descript system failure because of concurrent faults on multiple components. And it will be modeled and studied in the future.Figure 1
Imperfect coverage model with single point failure of a component.In order to improve the reliability of a fault-tolerant system with imperfect coverage failures, a scheme of a work-sharing group (WSG) is introduced [33]. A WSG usually consists of several identical components that are connected in parallel and form a set. Every component will fulfill a different subtask so that its WSG can finish the entire task. For a multichannel data transmission system from A to B, as shown in Figure 2, the components C1 and C2 make up a WSG to share the work under the reconfiguration of a data exchange management system (DEMS). Here, the DEMS can be assumed that it does not fail because its form of existence can be implemented as built-in software or other forms. The WSG is parallel with component C3 so that they can undertake the data transmission task together. Because of the existence of DEMS, the same tasks that the data packages are transmitted by C3 as DP3 are divided into two sections, DP1 and DP2, according to the performance of components C1 and C2. Under this assumption, if one component in the WSG, such as C1, fails, the DEMS can discover it and will not assign data packages to it again. This type of failure can be defined as covered failure. The DEMS will then reassign the data transmission task to C2. The WSG will not completely fail, but its performance will decrease consequently. However, if C1 fails but the DEMS cannot discover it and continues to assign data transmission to C1, C1 will be in a state of exit s, namely, single point failure. The failure occurred in this situation can be defined as uncovered failure and the WSG cannot finish the task of data transmission.Figure 2
The working scheme of WSG.The sole purpose of a parallel structure is to improve the reliability of the system. However, if there is no DEMS, the data packages will not be divided, and the efficiency of the system cannot be improved to transmit the data packages. Introducing the WSG into the system will increase efficiency, but due to the change in the system structure, reliability may be affected.


## 2.2. Modeling of MSS

For the purpose of modeling an MSS, the characteristics of its elements must first be defined. Generally speaking, any elementi in MSS can have mi+1 different states corresponding to the performance levels that can be represented by the set ai=ai0,ai1,…,aimi, where ais is the performance level of element i in the state s, s∈0,1,…,mi. The current performance level Ai of element i at any instant in time is a discrete random variable that takes value from ai: Ai∈ai. The probabilities of each different state or performance level for element i can be denoted by the set pi=pi0,pi1,…,pimi, where(1)pis=PrAi=ais.Furthermore, the entire states of one element constitute a whole set whose states can be seen as mutually exclusive events. That is to say, the elementi will always be in one and only one of mi+1 states, such that(2)∑s=0mipis=1.The performance level distribution of elementi will be determined completely by the collection of pairs(3)CPi=ais,pis,s=0,1,…,mi.The system elements have certain performance levels corresponding to their respective states at one instant in time. The modeling of an MSS performance level is completely determined byCPi,i=1,2,…,n. Therefore, the states of an MSS are determined completely by the states of its components. Now, suppose that the MSS has k+1 different states and the performance level corresponding to one state of the MSS at a certain moment can be represented by wj,j=0,1,…,k. In this case, the MSS performance level is a random variable denoted by W that takes values from the set(4)W=w0,w1,…,wk.The probability mass function (PMF) of the MSS performance levels can be obtained as follows:(5)qj=PrW=wj,j=0,1,…,k.Using the Cartesian product operation, we can define the space of all possible combinations of performance levels for all system components as(6)Cn=∏i=1nai0,ai1,…,aimi.The MSS structure function is naturally introduced as(7)ΦA1,A2,…,An:Cn⟶W.The function is to map the space of the component’s performance levels into the space of the performance levels of an MSS.From the above analysis, we can see that the model of an MSS includes two parts: PMF of performance levels for all system components and the structure function of the system. These can be rewritten as follows:(8)ai,pi,0≤i≤n,W=ΦA1,A2,…,An.For an MSS whose performance level is defined as task completion time, its reliability can be expressed as the probability that the system satisfies the maximum allowed completion time ofδ. From (5), one can obtain(9)Rδ=∑j=0MqjΔwj,δ,where(10)Δwj,δ=1,ifwj≤δ,0,ifwj>δ.Another important measure is the conditional expected performanceΩδ. This expresses the system’s expected performance under the condition that the MSS is in an acceptable state. Having the system reliability Rδ, this measure can be calculated by(11)Ωδ=∑j=0MqjwjΔwj,δRδ.


## 3. UGF Technique and Reliability Evaluation

### 3.1. UGF Technique

UGF, also called asu-function or universal z-transform [45], has been proven to be an effective method for solving high-dimensional combinatorial problems. UGF of a multistate component i associated with its performance level PMF can be defined as a polynomial(12)uiz=∑hi=0mipihizaihi,i=1,2,…,n.The essential property of UGF enables the entire UGF for an MSS, whose components are connected in series or parallel, to be obtained using simple algebraic operations corresponding to the individual UGF of a multistate component. To represent the PMF of the stochastic variableW=ΦA1,A2,…,An, the composition operator ⊗ϕ is defined in the following equation:(13)Uz=⊗ϕu1z,u2z,…,unz=⊗ϕ∑h1=0m1p1h1za1h1,∑h2=0m2p2h2za2h2,…,∑hn=0mnpnhnzanhn=∑h1=0m1∑h2=0m2⋯∑hn=0mn∏i=1npihizϕa1h1,a2h2,…,anhn.Note that the polynomialUz represents all possible mutually exclusive combinations of individual independent components’ UGFs. The function ϕa1h1,a2h2,…,anhn is determined according to the physical nature of the interaction between the performances of components.Indeed, the derivation ofUz for various types of systems is usually a difficult computational task. As shown in [45], from the two perspectives of computational simplicity and derivation clarity, representing Uz in a recursive form is beneficial. In particular, when an MSS has a complex configuration, the entire system can be represented as the composition of subsystems corresponding to the subsets of multistate components. This property can be defined by(14)⊗ϕu1z,…,ukz,uk+1z,…,unz=⊗ϕ⊗ϕu1z,…,ukz,⊗ϕuk+1z,…,unz.The configuration of any MSS can always be represented as a composition of independent subsystems containing only components connected in parallel or in series. For any components connected in parallel or in series in the MSS, the composition operator can be applied recursively in order to obtain the UGF of the intermediate pure parallel or pure series structures.Consider one type of MSS system, a task processing computer system with its performance level defined as task completion time. For components connected in series, the system’s total completion time is the sum of completion time of all its components. If two independent components (i and j) work in series, the total completion time is the sum of their individual completion times. The function ϕs should calculate the sum of corresponding parameters. The performance of the pair of components in this case is defined as(15)Uijz=uiz⊗ϕsujz=∑hi=0mi∑hj=0mjpihipjhjzsumaihi,ajhj.For components connected in parallel, the total completion time is decided by the component with the shortest completion time. The functionϕp should obtain the minimum of all parameters. Therefore, the UGF in this case should take the following form:(16)Uijz=uiz⊗ϕpujz=∑hi=0mi∑hj=0mjpihipjhjzminaihi,ajhj.For components connected in parallel with WSG, the task processing can be divided in proportion to their processing speeds. That is to say, components can share the task according to their performance levels. The functionϕpw should be the inverse of its performance, and the UGF for this pair of components can be determined by the function(17)Uijz=uiz⊗ϕpwujz=∑hi=0mi∑hj=0mjpihipjhjzinvaihi,ajhj,where invaihi,ajhj=aihi−1+ajhj−1−1.


### 3.2. Reliability Analysis of MSS with ICF

For the MSS with ICF, its single point failure can usually be modeled as state 0 with assigned performance level [31]. The assigned performance level can coincide with component performance in the permanent coverage. The specific performance level is related to the system property, and here it might as well be assigned to x. According to (8), it can be expanded as(18)uiz=pi0zx+∑hi=1mipihizaihi=pi0zx+u^iz,where the second item u^iz represents the UGF of component i except for its single point failure state. If the component is not of the single point failure, uiz=u^iz.For the WSG with the single point failure, its UGFUw can be obtained in three steps:(1)
u^izi∈α of every component can be expressed according to (18), where α is the set of components in the WSG.(2)
U^w can be obtained based on the operation of components’ u^iz by (17).(3)
UGFUw will be calculated as follows:(19)Uwz=U^wz+1−∏i∈α1−ai0∗zx.Once the UGF of WSG with ICF is obtained, it can be seen as a common component to be operated with other components according to the structure of the system. The UGF of the entire system can now be expressed easily. By applying (9) and (11), the reliability indices can be calculated.During the calculation, the computation complexity of determining the UGF of two components is always high if it is only calculated manually. This is why the algorithm based on matrix (ABM) is developed. The seven steps of ABM, along with substeps, are as follows:Step 1: the UGF of two components can be expressed in matricesA and B, respectively. Both A and B are composed by two rows and n columns. The first row is the performance level, and the second row is its corresponding probability. The number of columns in A and B may be different.Step 2: define a matrixC with two rows. The number of C’s columns is equal to the product of A’s columns multiplied by B’s columns. Matrix C is used to store the primitive values of the multiplication of matrixes A and B according to specific calculation rules.Step 3: by applying the dual-iteration method, the elements in matrixC can be obtained from the following rules:(i)
Define the first column ofA and B as the outer and inner iteration variables, respectively. Let k represent the column order of matrix C and k = 1 at beginning.(ii)
The value of matrixC’s k column and first row should be calculated by the corresponding element of matrices A and B according to the function sum, min, or inv, based on (15)–(17).(iii)
The probability value of matrixC’s k column and second row can be obtained by multiplying the corresponding element values of matrices A and B. The value in C (2, k) is equal to the product of A (2, 1) and B (2, 1).(iv)
Assignk with k + 1, viz., k = k + 1.(v)
Modify the inner iteration variable to the second column ofB and repeat the above three steps until the end of B’s columns.(vi)
Modify the outer iteration variable to the second column ofA, and repeat the above four steps until the end of A’s columns.Step 4: sort the values ofC’s first rows in ascending order, i.e., performance level. The elements of the second row of matrix C can be reordered correspondingly.Step 5: abstract the unique elements from the first row of matrixC and form row vector E.Step 6: define a result matrixD whose first row is equal to E. The second row of D is constructed by the following iteration steps:(i)
Define the first column of matrixD as the iteration variable.(ii)
From the first column of matrixC’s first row, namely, C (1, 1), locate for the same value with the first column of D’s first row, namely, D (1, 1).(iii)
Add the corresponding probabilities at the location determined by the previous step to the first column ofD’s second row, namely, D (2, 1).(iv)
Modify the iteration variable to the second column, and then repeat the above two steps until the end of the number ofD’s columns.Step 7: the results of the operation of matricesA and B are stored in the matrix D with just the performance level and probability. According to this matrix D, it can be rewritten in the UGF expression.In the following examples, the ABM can be used frequently.


## 3.1. UGF Technique

UGF, also called asu-function or universal z-transform [45], has been proven to be an effective method for solving high-dimensional combinatorial problems. UGF of a multistate component i associated with its performance level PMF can be defined as a polynomial(12)uiz=∑hi=0mipihizaihi,i=1,2,…,n.The essential property of UGF enables the entire UGF for an MSS, whose components are connected in series or parallel, to be obtained using simple algebraic operations corresponding to the individual UGF of a multistate component. To represent the PMF of the stochastic variableW=ΦA1,A2,…,An, the composition operator ⊗ϕ is defined in the following equation:(13)Uz=⊗ϕu1z,u2z,…,unz=⊗ϕ∑h1=0m1p1h1za1h1,∑h2=0m2p2h2za2h2,…,∑hn=0mnpnhnzanhn=∑h1=0m1∑h2=0m2⋯∑hn=0mn∏i=1npihizϕa1h1,a2h2,…,anhn.Note that the polynomialUz represents all possible mutually exclusive combinations of individual independent components’ UGFs. The function ϕa1h1,a2h2,…,anhn is determined according to the physical nature of the interaction between the performances of components.Indeed, the derivation ofUz for various types of systems is usually a difficult computational task. As shown in [45], from the two perspectives of computational simplicity and derivation clarity, representing Uz in a recursive form is beneficial. In particular, when an MSS has a complex configuration, the entire system can be represented as the composition of subsystems corresponding to the subsets of multistate components. This property can be defined by(14)⊗ϕu1z,…,ukz,uk+1z,…,unz=⊗ϕ⊗ϕu1z,…,ukz,⊗ϕuk+1z,…,unz.The configuration of any MSS can always be represented as a composition of independent subsystems containing only components connected in parallel or in series. For any components connected in parallel or in series in the MSS, the composition operator can be applied recursively in order to obtain the UGF of the intermediate pure parallel or pure series structures.Consider one type of MSS system, a task processing computer system with its performance level defined as task completion time. For components connected in series, the system’s total completion time is the sum of completion time of all its components. If two independent components (i and j) work in series, the total completion time is the sum of their individual completion times. The function ϕs should calculate the sum of corresponding parameters. The performance of the pair of components in this case is defined as(15)Uijz=uiz⊗ϕsujz=∑hi=0mi∑hj=0mjpihipjhjzsumaihi,ajhj.For components connected in parallel, the total completion time is decided by the component with the shortest completion time. The functionϕp should obtain the minimum of all parameters. Therefore, the UGF in this case should take the following form:(16)Uijz=uiz⊗ϕpujz=∑hi=0mi∑hj=0mjpihipjhjzminaihi,ajhj.For components connected in parallel with WSG, the task processing can be divided in proportion to their processing speeds. That is to say, components can share the task according to their performance levels. The functionϕpw should be the inverse of its performance, and the UGF for this pair of components can be determined by the function(17)Uijz=uiz⊗ϕpwujz=∑hi=0mi∑hj=0mjpihipjhjzinvaihi,ajhj,where invaihi,ajhj=aihi−1+ajhj−1−1.


## 3.2. Reliability Analysis of MSS with ICF

For the MSS with ICF, its single point failure can usually be modeled as state 0 with assigned performance level [31]. The assigned performance level can coincide with component performance in the permanent coverage. The specific performance level is related to the system property, and here it might as well be assigned to x. According to (8), it can be expanded as(18)uiz=pi0zx+∑hi=1mipihizaihi=pi0zx+u^iz,where the second item u^iz represents the UGF of component i except for its single point failure state. If the component is not of the single point failure, uiz=u^iz.For the WSG with the single point failure, its UGFUw can be obtained in three steps:(1)
u^izi∈α of every component can be expressed according to (18), where α is the set of components in the WSG.(2)
U^w can be obtained based on the operation of components’ u^iz by (17).(3)
UGFUw will be calculated as follows:(19)Uwz=U^wz+1−∏i∈α1−ai0∗zx.Once the UGF of WSG with ICF is obtained, it can be seen as a common component to be operated with other components according to the structure of the system. The UGF of the entire system can now be expressed easily. By applying (9) and (11), the reliability indices can be calculated.During the calculation, the computation complexity of determining the UGF of two components is always high if it is only calculated manually. This is why the algorithm based on matrix (ABM) is developed. The seven steps of ABM, along with substeps, are as follows:Step 1: the UGF of two components can be expressed in matricesA and B, respectively. Both A and B are composed by two rows and n columns. The first row is the performance level, and the second row is its corresponding probability. The number of columns in A and B may be different.Step 2: define a matrixC with two rows. The number of C’s columns is equal to the product of A’s columns multiplied by B’s columns. Matrix C is used to store the primitive values of the multiplication of matrixes A and B according to specific calculation rules.Step 3: by applying the dual-iteration method, the elements in matrixC can be obtained from the following rules:(i)
Define the first column ofA and B as the outer and inner iteration variables, respectively. Let k represent the column order of matrix C and k = 1 at beginning.(ii)
The value of matrixC’s k column and first row should be calculated by the corresponding element of matrices A and B according to the function sum, min, or inv, based on (15)–(17).(iii)
The probability value of matrixC’s k column and second row can be obtained by multiplying the corresponding element values of matrices A and B. The value in C (2, k) is equal to the product of A (2, 1) and B (2, 1).(iv)
Assignk with k + 1, viz., k = k + 1.(v)
Modify the inner iteration variable to the second column ofB and repeat the above three steps until the end of B’s columns.(vi)
Modify the outer iteration variable to the second column ofA, and repeat the above four steps until the end of A’s columns.Step 4: sort the values ofC’s first rows in ascending order, i.e., performance level. The elements of the second row of matrix C can be reordered correspondingly.Step 5: abstract the unique elements from the first row of matrixC and form row vector E.Step 6: define a result matrixD whose first row is equal to E. The second row of D is constructed by the following iteration steps:(i)
Define the first column of matrixD as the iteration variable.(ii)
From the first column of matrixC’s first row, namely, C (1, 1), locate for the same value with the first column of D’s first row, namely, D (1, 1).(iii)
Add the corresponding probabilities at the location determined by the previous step to the first column ofD’s second row, namely, D (2, 1).(iv)
Modify the iteration variable to the second column, and then repeat the above two steps until the end of the number ofD’s columns.Step 7: the results of the operation of matricesA and B are stored in the matrix D with just the performance level and probability. According to this matrix D, it can be rewritten in the UGF expression.In the following examples, the ABM can be used frequently.


## 4. Illustrative Examples

### 4.1. Reliability Evaluation

Consider a task processing system with the structure as shown in Figure2, in which components C1 and C2 comprise the WSG. After C3 is connected with the WSG in parallel, C4 is connected in series. These components are statistically independent. The data package can be transmitted through C3 and C4 in 15 seconds and 20 seconds with the probability of 0.7 and 0.75, respectively. The performance levels of C1 and C2 are the same. Their completion time and probability are both 15 seconds and 0.7. Their detected and undetected failures have equal probabilities, namely, 0.15. These parameters are listed in Table 1.Table 1
Parameters of components.
ComponentStatesProbabilityPerformance level (time: s)With or without ICF (Y/N)C1/C200.15∞Y00.15∞N10.715—C300.3∞N10.715—C400.05∞N10.225—20.7520—In this case, WSGα=C1,C2 is affected by the ICF. According to the steps above, the UGF of these components’ performance distribution can be represented as follows.Based on the above analysis, the UGF of every component can be represented as(20)uc1z=uc2z=0.7∗z15+0.15∗z∞+0.15∗zx,uc3z=0.7∗z15+0.3∗z∞,uc4z=0.75∗z20+0.2∗z25+0.05∗z∞,where u^c1z=u^c2z=0.7∗z15+0.15∗z∞. Because the WSG consists of C1 and C2, they finish the data transmission task by sharing. Applying (17), such that(21)U^wz=u^c1z⊗ϕpwu^c2z=0.7∗z15+0.15∗z∞⊗ϕpw0.7∗z15+0.15∗z∞=0.49∗z7.5+0.21∗z15+0.0225∗z∞.A component’s single point failure also leads to its lowest performance level, namely, infinity of task completion timex=∞. According to (19),(22)Uwz=U^wz+1−∏i∈C1,C21−ai0∗zx=U^wz+1−1−0.152∗z∞=U^wz+0.2775∗z∞=0.49∗z7.5+0.21∗z15+0.3∗z∞.Based on the reliability block diagram, because the WSG is connected withC3 in parallel, (16) is adopted first. Component C4 is connected by series, and then (15) needs to be applied. The UGF of the system can be expressed as follows:(23)Usysz=Uwz⊗ϕpuc3z⊗ϕsuc4z=0.49∗z7.5+0.42∗z15+0.09∗z∞⊗ϕsuc4z=0.3675∗z27.5+0.098∗z32.5+0.315∗z35+0.084∗z40+0.1355∗z∞.According to (9) and (11), the probability that system can transmit data packages within δ=40s and the conditional expected performance are(24)R40=1−0.1355=0.8645,Ω40=0.3675∗27.5+0.098∗32.5+0.315∗35+0.084∗400.8645=32.0142.If there is no WSG in this system, that is to say, if componentsC1, C2, and C3 are connected in parallel, then the UGF of C1 and C2 is expressed as(25)uc1′z=uc2′z=0.7∗z15+0.3∗z∞.The UGF of the system can be calculated by(26)Usys′z=uc1′z⊗ϕpuc2′z⊗ϕpuc3z⊗ϕsuc4z=0.72975∗z35+0.1946∗z40+0.07565∗z∞.Similarly, the reliability and conditional expected performance can be calculated as(27)R′40=0.92435,Ω′40=0.72975∗35+0.1946∗400.92435=36.0526.From the comparison of (24) and (27), it can be seen that the reliability of the system with ICF is decreased. However, its expected task completion time is less than that of the system without WSG. In other words, the system with WSG has higher efficiency to complete the transmission of data packages. However, because of the existence of ICF, its reliability has declined.In order to compare the efficiency of the above analyzing method with multivalued decision diagram (MDD) derived from reference [22], the system in Figure 2 and some parameters in Table 1 are still used for the reliability calculation. The other assumptions and parameters needed in MDD are in concert with those in the mentioned reference. Here, the focus is to compare the time consumption during the calculation for reliability. In the same configuration of computing environments, those results calculated by MDD are approaching to ones in (24). There is a distance on the time consuming between those two methods. From the validation listed in Table 2, it shows the ABM is less time consuming than MDD.Table 2
Comparison of results for two different methods.
MethodR40Ω40Time consumption (s)ABM0.864532.01421.0385MDD0.853932.13255.7862


### 4.2. Sensitivity Analysis

Figure3 shows a more complex system, composed of three subsystems. Within each subsystem, a WSG is configured to improve task processing efficiency.Figure 3
Sensitivity analysis diagram.Because the components are of several states in each subsystem, the performance levels of task processing time and other parameters of these components are listed in the form of a five-element tuple, as shown in Table3.Table 3
Five-element tuple of components.
Component(States, probability, performance level (time: s), with or without ICF (Y/N))FirstsecondThirdFourthFifthC11(0, 0.15, ∞, N)(1, 0.8, 10, −)(2, 0.05, 15, −)——C12(0, 0.05, ∞, Y)(0, 0.05, ∞, N)(1, 0.7, 8, −)(2, 0.15, 10, −)(3, 0.05, 13, −)C13(0, 0.06, ∞, Y)(0, 0.05, ∞, N)(1, 0.7, 15, −)(2, 0.1, 18, −)(3, 0.09, 20, −)C21(0, 0.05, ∞, Y)(0, 0.1, ∞, N)(1, 0.8, 5, −)(2, 0.05, 10, −)—C22(0, 0.02, ∞, Y)(0, 0.03, ∞, N)(1, 0.7, 5, −)(2, 0.2, 12, −)(3, 0.05, 17, −)C31(0, 0.1, ∞, N)(1, 0.75, 10, −)(2, 0.1, 13, −)(3, 0.05, 16, −)—C32(0, 0.08, ∞, Y)(0, 0.06, ∞, N)(1, 0.65, 8, −)(2, 0.1, 15, −)(3, 0.11, 18, −)C33(0, 0.10, ∞, Y)(0, 0.06, ∞, N)(1, 0.7, 9, −)(2, 0.1, 12, −)(3, 0.04, 15, −)C34(0, 0.2, ∞, N)(1, 0.7, 10, −)(2, 0.1, 13, −)——Based on the above method and these parameters, the system reliability satisfying the maximum allowed completion time can be calculated by (9). Consider four different cases:A: the WSG in each subsystem is operating and works wellB: the WSG1 is eliminated and componentsC12 and C13 work in parallelC: the WSG2 is eliminated and componentsC21 and C22 work in parallelD: WSG3 is eliminated and componentsC32 and C33 work in parallelThe system reliability curves for these four cases are shown in Figure4. Figure 4(a) shows the entire curve of the four cases. From Figure 4(b), which is a partial curve scaled in [25], [55], it can be seen that case A has the lowest reliability of the four cases. The sequence of reliability improvement for the other three cases, from low to high, is D, B, and C.Figure 4
Reliability curves for four cases.
(a)(b)For the purpose of quantitative analysis of reliability improvements, those results are listed in Table4. It can be seen that Case C improves the reliability the most. At the same time, its expected performance is the lowest of the four cases. Although Cases B and D have the almost same reduction in expected performance, Case B shows higher improvement of reliability than Case D. It can be also seen that the results of reliability improvement from the quantitative analysis are in agreement with those from the above figures.Table 4
Quantitative analysis.
CaseR (55)Improvement (%)Ω (55)Reduction (%)A0.909552—15.85966—B0.9232151.50%18.2134814.84%C0.972776.95%17.8795112.74%D0.9123490.31%18.213814.84%By applying the above analysis, the reliability engineer can choose the optimal scheme according to the indices of reliability or expected performance. Moreover, in this example, the sensitivity analysis is aimed only at the single WSG. In fact, combination of several WSGs is also a suitable mechanism for further sensitivity analysis based on this approach.


## 4.1. Reliability Evaluation

Consider a task processing system with the structure as shown in Figure2, in which components C1 and C2 comprise the WSG. After C3 is connected with the WSG in parallel, C4 is connected in series. These components are statistically independent. The data package can be transmitted through C3 and C4 in 15 seconds and 20 seconds with the probability of 0.7 and 0.75, respectively. The performance levels of C1 and C2 are the same. Their completion time and probability are both 15 seconds and 0.7. Their detected and undetected failures have equal probabilities, namely, 0.15. These parameters are listed in Table 1.Table 1
Parameters of components.
ComponentStatesProbabilityPerformance level (time: s)With or without ICF (Y/N)C1/C200.15∞Y00.15∞N10.715—C300.3∞N10.715—C400.05∞N10.225—20.7520—In this case, WSGα=C1,C2 is affected by the ICF. According to the steps above, the UGF of these components’ performance distribution can be represented as follows.Based on the above analysis, the UGF of every component can be represented as(20)uc1z=uc2z=0.7∗z15+0.15∗z∞+0.15∗zx,uc3z=0.7∗z15+0.3∗z∞,uc4z=0.75∗z20+0.2∗z25+0.05∗z∞,where u^c1z=u^c2z=0.7∗z15+0.15∗z∞. Because the WSG consists of C1 and C2, they finish the data transmission task by sharing. Applying (17), such that(21)U^wz=u^c1z⊗ϕpwu^c2z=0.7∗z15+0.15∗z∞⊗ϕpw0.7∗z15+0.15∗z∞=0.49∗z7.5+0.21∗z15+0.0225∗z∞.A component’s single point failure also leads to its lowest performance level, namely, infinity of task completion timex=∞. According to (19),(22)Uwz=U^wz+1−∏i∈C1,C21−ai0∗zx=U^wz+1−1−0.152∗z∞=U^wz+0.2775∗z∞=0.49∗z7.5+0.21∗z15+0.3∗z∞.Based on the reliability block diagram, because the WSG is connected withC3 in parallel, (16) is adopted first. Component C4 is connected by series, and then (15) needs to be applied. The UGF of the system can be expressed as follows:(23)Usysz=Uwz⊗ϕpuc3z⊗ϕsuc4z=0.49∗z7.5+0.42∗z15+0.09∗z∞⊗ϕsuc4z=0.3675∗z27.5+0.098∗z32.5+0.315∗z35+0.084∗z40+0.1355∗z∞.According to (9) and (11), the probability that system can transmit data packages within δ=40s and the conditional expected performance are(24)R40=1−0.1355=0.8645,Ω40=0.3675∗27.5+0.098∗32.5+0.315∗35+0.084∗400.8645=32.0142.If there is no WSG in this system, that is to say, if componentsC1, C2, and C3 are connected in parallel, then the UGF of C1 and C2 is expressed as(25)uc1′z=uc2′z=0.7∗z15+0.3∗z∞.The UGF of the system can be calculated by(26)Usys′z=uc1′z⊗ϕpuc2′z⊗ϕpuc3z⊗ϕsuc4z=0.72975∗z35+0.1946∗z40+0.07565∗z∞.Similarly, the reliability and conditional expected performance can be calculated as(27)R′40=0.92435,Ω′40=0.72975∗35+0.1946∗400.92435=36.0526.From the comparison of (24) and (27), it can be seen that the reliability of the system with ICF is decreased. However, its expected task completion time is less than that of the system without WSG. In other words, the system with WSG has higher efficiency to complete the transmission of data packages. However, because of the existence of ICF, its reliability has declined.In order to compare the efficiency of the above analyzing method with multivalued decision diagram (MDD) derived from reference [22], the system in Figure 2 and some parameters in Table 1 are still used for the reliability calculation. The other assumptions and parameters needed in MDD are in concert with those in the mentioned reference. Here, the focus is to compare the time consumption during the calculation for reliability. In the same configuration of computing environments, those results calculated by MDD are approaching to ones in (24). There is a distance on the time consuming between those two methods. From the validation listed in Table 2, it shows the ABM is less time consuming than MDD.Table 2
Comparison of results for two different methods.
MethodR40Ω40Time consumption (s)ABM0.864532.01421.0385MDD0.853932.13255.7862


## 4.2. Sensitivity Analysis

Figure3 shows a more complex system, composed of three subsystems. Within each subsystem, a WSG is configured to improve task processing efficiency.Figure 3
Sensitivity analysis diagram.Because the components are of several states in each subsystem, the performance levels of task processing time and other parameters of these components are listed in the form of a five-element tuple, as shown in Table3.Table 3
Five-element tuple of components.
Component(States, probability, performance level (time: s), with or without ICF (Y/N))FirstsecondThirdFourthFifthC11(0, 0.15, ∞, N)(1, 0.8, 10, −)(2, 0.05, 15, −)——C12(0, 0.05, ∞, Y)(0, 0.05, ∞, N)(1, 0.7, 8, −)(2, 0.15, 10, −)(3, 0.05, 13, −)C13(0, 0.06, ∞, Y)(0, 0.05, ∞, N)(1, 0.7, 15, −)(2, 0.1, 18, −)(3, 0.09, 20, −)C21(0, 0.05, ∞, Y)(0, 0.1, ∞, N)(1, 0.8, 5, −)(2, 0.05, 10, −)—C22(0, 0.02, ∞, Y)(0, 0.03, ∞, N)(1, 0.7, 5, −)(2, 0.2, 12, −)(3, 0.05, 17, −)C31(0, 0.1, ∞, N)(1, 0.75, 10, −)(2, 0.1, 13, −)(3, 0.05, 16, −)—C32(0, 0.08, ∞, Y)(0, 0.06, ∞, N)(1, 0.65, 8, −)(2, 0.1, 15, −)(3, 0.11, 18, −)C33(0, 0.10, ∞, Y)(0, 0.06, ∞, N)(1, 0.7, 9, −)(2, 0.1, 12, −)(3, 0.04, 15, −)C34(0, 0.2, ∞, N)(1, 0.7, 10, −)(2, 0.1, 13, −)——Based on the above method and these parameters, the system reliability satisfying the maximum allowed completion time can be calculated by (9). Consider four different cases:A: the WSG in each subsystem is operating and works wellB: the WSG1 is eliminated and componentsC12 and C13 work in parallelC: the WSG2 is eliminated and componentsC21 and C22 work in parallelD: WSG3 is eliminated and componentsC32 and C33 work in parallelThe system reliability curves for these four cases are shown in Figure4. Figure 4(a) shows the entire curve of the four cases. From Figure 4(b), which is a partial curve scaled in [25], [55], it can be seen that case A has the lowest reliability of the four cases. The sequence of reliability improvement for the other three cases, from low to high, is D, B, and C.Figure 4
Reliability curves for four cases.
(a)(b)For the purpose of quantitative analysis of reliability improvements, those results are listed in Table4. It can be seen that Case C improves the reliability the most. At the same time, its expected performance is the lowest of the four cases. Although Cases B and D have the almost same reduction in expected performance, Case B shows higher improvement of reliability than Case D. It can be also seen that the results of reliability improvement from the quantitative analysis are in agreement with those from the above figures.Table 4
Quantitative analysis.
CaseR (55)Improvement (%)Ω (55)Reduction (%)A0.909552—15.85966—B0.9232151.50%18.2134814.84%C0.972776.95%17.8795112.74%D0.9123490.31%18.213814.84%By applying the above analysis, the reliability engineer can choose the optimal scheme according to the indices of reliability or expected performance. Moreover, in this example, the sensitivity analysis is aimed only at the single WSG. In fact, combination of several WSGs is also a suitable mechanism for further sensitivity analysis based on this approach.


## 5. Concluding Remarks

In this paper, a reliability and sensitivity analysis approach is proposed for an MSS with ICF. In order to improve transmission efficiency, the components within a WSG can share a task such as data transmission according to its processing time. During the task sharing, the system may fail to detect the failure of one component, in which case, system reliability will be reduced and could even lead to the failure of task transmission. Based on the technique of UGF, the impact of ICF is incorporated in the expression of its UGF and its calculation methods for reliability and sensitivity analysis are also suggested. During the computation, the ABM algorithm is developed in order to significantly reduce the computational complexity. Two examples in this paper illustrate the application of the suggested approach. A reliability engineer can easily apply this approach to decide the optimal scheme under limited resources. In the above analysis, only the series-parallel MSS is considered. More complex MSS topologies, such as bridge and G: (k/n) structures, should be the focus. For other ICF models with different structures, they will be also explored in the future research.



---

*Source: 5560555-2021-06-14.xml*