Multistate-node acyclic networks reliability evaluation based on MC

A multistate-node acyclic network (MNAN) is a generalization of the tree-structured multistate-node system that does not satisfy the flow conservation law. The current known existing methods used to evaluate MNAN reliability are based on the minimal tree (MT) set. Instead of using the MT, an intuitive algorithm was developed in this to find the minimal cut (MC) set. The MNAN reliability can then be computed in terms of MCs. The proposed algorithm is simpler and more efficient compared to the best-known existing methods. The computational complexity of the proposed algorithm is analyzed and compared with the best-known existing methods. One example is used to show how all MCs are generated using the proposed algorithm. The corresponding reliabilities in this example are computed.     

Approximate multi-state reliability expressions using a new machine learning technique

The machine-learning-based methodology, previously proposed by the authors for approximating binary reliability expressions, is now extended to develop a new algorithm, based on the procedure of Hamming Clustering, which is capable to deal with multi-state systems and any success criterion. The proposed technique is presented in details and verified on literature cases: experiment results show that the new algorithm yields excellent predictions.     

A simple minimal path method for estimating the weighted multi-commodity multistate unreliable networks reliability

The weighted multicommodity multistate unreliable network (WMMUN) is a novel network composed of multistate unreliable components (arcs and nodes) capable of transmitting different types of commodities in which capacity weight varies with components. It is an extension of the multistate network. The current method for evaluating the directed WMMUN reliability has been derived from minimal cut (MC) based algorithm. The existing best-known method needed extensive comparison and verification, and failed to find the real directed WMMUN reliability. A very simple algorithm based on minimal paths (MPs) is developed for the WMMUN reliability problem. The correctness and computational complexity of the proposed algorithm will be analyzed and proven. An example is given to illustrate how the WMMUN reliability is evaluated using the proposed algorithm. The relationships among all different versions of MPs are also clarified.     

Approximating network reliability estimates using linear and quadratic unreliability of minimal cuts

A new algorithm is proposed to approximate the terminal-pair network reliability based on minimal cut theory. Unlike many existing models that decompose the network into a series–parallel or parallel–series structure based on minimal cuts or minimal paths, the new model estimates the reliability by summing the linear and quadratic unreliability of each minimal cut set. Given component test data, the new model provides tight moment bounds for the network reliability estimate. Those moment bounds can be used to quantify the network estimation uncertainty propagating from component level estimates. Simulations and numerical examples show that the new model generally outperforms Esary-Proschan and Edge-Packing bounds, especially for high reliability systems.     

Search for all MCs in networks with unreliable nodes and arcs

A simple method is proposed to search for all minimal cutsets (MCs ) for imperfect networks reliability subject to both arc and node failures under the condition that all of the MCs in the network with perfect nodes are given in advance. The proposed method does not require re-enumeration for all of the MCs for additional node failure consideration. All of the MC candidates found in the proposed algorithm are actual MCs without any need for further verification. This algorithm is more effective than the existing algorithm in which every MC candidate is not verified as a MC. No identical MCs are found using the proposed algorithm, which does not duplicate MCs and is more efficient than the existing methods. Only simple concepts are used to implement the proposed algorithm, which makes it easier to understand and implement. With considering unreliable nodes, the proposed method is also more realistic and valuable for reliability analysis in an existing network. The correctness of the proposed algorithm will be analyzed and proven. One example is used to illustrate how all MCs are generated in a network with arc and node failures solved using the proposed algorithm.     

用OBDD算法评估无线传感网的可靠度和结点重要性

基于有序二叉判定图(OBDD),提出用结点扩张(NE)算法来评估无线传感网的可靠度和结点重要性.NE算法执行结点扩张操作来处理不可靠结点,从两方面增强了计算效率:利用OBDD结构表示网络状态,减少了大量冗余的等价状态;利用Hash表存储同构子网的OBDD,减少了同构子网的重复计算.另外,该算法对结点重要性进行了评估,为脆弱结点的保护提供参考.实验结果表明NE算法的计算开销比传统的factoring算法低,能有效评估无线传感网的可靠度.     

Reliability assessment of embedded digital system using multi-state function

This work describes a combinatorial model for estimating the reliability of the embedded digital system by means of multi-state function. This model includes a coverage model for fault-handling techniques implemented in digital systems. The fault-handling techniques make it difficult for many types of components in digital system to be treated as binary state, good or bad. The multi-state function provides a complete analysis of multi-state systems as which the digital systems can be regarded. Through adaptation of software operational profile flow to multi-state function, the HW/SW interaction is also considered for estimation of the reliability of digital system. Using this model, we evaluate the reliability of one board controller in a digital system, Interposing Logic System (ILS), which is installed in YGN nuclear power units 3 and 4. Since the proposed model is a generalized combinatorial model, the simplification of this model becomes the conventional model that treats the system as binary state. This modeling method is particularly attractive for embedded systems in which small sized application software is implemented since it will require very laborious work for this method to be applied to systems with large software.     

Exact reliability evaluation of infrastructure networks using graph theory

Reliability analysis of Infrastructure Networks (INs) is gaining recognition in the research literature. However, most of the work on reliability evaluation of INs have focused on simulation analysis and, therefore, unable to calculate the exact reliability. Additionally, these methods lack the capability of achieving a closer adherence to INs. The presented paper aims at filling these gaps by simplifying the process of computing the exact reliability of an IN through the decomposition of the network into a set of series and parallel configuration of its elements. In exemplifying the method, an illustrative example is presented and a brief discussion on the usefulness and limitation of the method is described.     

A new reliability evaluation method for networks with imperfect vertices using BDD

As an efficient data structure for representation and manipulation of Boolean functions, binary decision diagrams (BDDs) have been applied to network reliability analysis. However, most of the existing BDD methods on network reliability analysis have assumed perfectly reliable vertices, which is often not true for real‐world networks where the vertices can fail because of factors such as limited resources (eg, power and memory) or harsh operating environments. Extensions have been made to the existing BDD methods (particularly, edge expansion diagram and boundary set–based methods) to address imperfect vertices. But these extended methods have various constraints leading to problems in accuracy or space efficiency. To overcome these constraints, in this paper, we propose a new BDD‐based algorithm called ordered BDD dependency test for K‐terminal network reliability analysis considering both edge and vertex failures. Based on a newly defined concept “dependency set”, the proposed algorithm can accurately compute the reliability of networks with imperfect vertices. In addition, the proposed algorithm has no restrictions on the starting vertex for the BDD model construction. Comprehensive examples and experiments are provided to show effectiveness of the proposed approach.     

An improved algorithm for searching all minimal cuts in modified networks

A modified network is an updated network after inserting a branch string (a special path) between two nodes in the original network. Modifications are common for network expansion or reinforcement evaluation and planning. The problem of searching all minimal cuts (MCs) in a modified network is discussed and solved in this study. The existing best-known methods for solving this problem either needed extensive comparison and verification or failed to solve some special but important cases. Therefore, a more efficient, intuitive and generalized method for searching all MCs without an extensive research procedure is proposed. In this study, we first develop an intuitive algorithm based upon the reformation of all MCs in the original network to search for all MCs in a modified network. Next, the correctness of the proposed algorithm will be analyzed and proven. The computational complexity of the proposed algorithm is analyzed and compared with the existing best-known methods. Finally, two examples illustrate how all MCs are generated in a modified network using the information of all of the MCs in the corresponding original network.     

Estimation of the importance measures of multi-state elements by Monte Carlo simulation

A generalization of some frequently used importance measures has been proposed by some of the authors for application to multi-state systems constituted by multi-state elements. This paper deals with the Monte Carlo (MC) estimation of these measures, which entails evaluating the system output performance under restrictions on the performance levels of its multi-state elements. Simulation procedures are proposed according to two different performance-restriction approaches. Further, the flexibility of the MC method is exploited to account for load-sharing and operational dependencies among parallel elements. The approach is tested on a multi-state transmission system of literature.     

Importance and sensitivity analysis of multi-state systems using the universal generating function method

A method for the evaluation of element reliability importance in a multi-state system is proposed. The method is based on the universal generating function technique. It provides an effective importance analysis tool for complex series–parallel multi-state systems with a different physical nature of performance and takes into account a required performance (demand). The method is also extended for the sensitivity analysis of important multi-state system output performance measures: mean system performance and mean unsupplied demand during operating period. Numerical examples are given.     

多状态可修复k/n系统的随时间响应可靠性研究

利用离散时间的马尔科夫链和半马尔科夫链对复杂的多状态可修复k/n系统元件的多样性进行了分析,给出了元件状态变化以及在状态逗留时间的概率分布计算公式,然后给出了元件在状态变化、状态寿命变化的一步概率转移矩阵,最后根据对元件的分析,导出了系统的可靠度与可用度的预测模型。算例表明,得出的模型易行、有效。     

A simple algorithm for evaluating the k-out-of-n network reliability

Evaluating the network reliability is an important topic in the planning, designing, and control of systems. The minimal cut set (MC, an edge set) is one of the major and fundamental tools for evaluating network reliability. A k-out-of-n MC is a special MC in a k-out-of-n network in which some nodes must receive at least k flows from their n input edges, where k is an integer number between 1 and n. In this study, an alternative method is given first to define a MC using a node set (called MCN) in k-out-of-n networks. A very simple algorithm based on some intuitive theorems that characterize the structure of the MCN and the relationship between MC and MCN is developed to solve the k-out-of-n network reliability by finding the k-out-of-n MCs between two special nodes. The proposed algorithm is not only easier to understand and implement, but is also better than the existing algorithm. The correctness of the proposed algorithm will be analyzed and proven. Two examples are illustrated to show how all k-out-of-n MCs are generated and verified in a k-out-of-n network using the proposed algorithm. The reliability of one example is then computing using one example.     

An improved sum-of-disjoint-products technique for the symbolic network reliability analysis with known minimal paths

Evaluating the network reliability is an important topic in the planning, designing, and control of systems. The sum-of-disjoint products technique (SDP) is a major fundamental tool for evaluating stochastic network reliability. In this study, a new SDP based on some intuitive properties that characterize the structure of minimal paths (MPs), and the relationships between MPs and subpaths are developed to improved SDP. The proposed SDP is easier to understand and implement, and better than the existing best- known SDP based algorithms under some special situation. The correctness of the proposed algorithm will be analyzed and proven. One bench example is illustrated to show how the network reliability with known MPs is determined using the proposed SDP.     

Extended great deluge algorithm for the imperfect preventive maintenance optimization of multi-state systems

This paper deals with preventive maintenance optimization problem for multi-state systems (MSS). This problem was initially addressed and solved by Levitin and Lisnianski [Optimization of imperfect preventive maintenance for multi-state systems. Reliab Eng Syst Saf 2000;67:193–203]. It consists on finding an optimal sequence of maintenance actions which minimizes maintenance cost while providing the desired system reliability level. This paper proposes an approach which improves the results obtained by genetic algorithm (GENITOR) in Levitin and Lisnianski [Optimization of imperfect preventive maintenance for multi-state systems. Reliab Eng Syst Saf 2000;67:193–203]. The considered MSS have a range of performance levels and their reliability is defined to be the ability to meet a given demand. This reliability is evaluated by using the universal generating function technique. An optimization method based on the extended great deluge algorithm is proposed. This method has the advantage over other methods to be simple and requires less effort for its implementation. The developed algorithm is compared to than in Levitin and Lisnianski [Optimization of imperfect preventive maintenance for multi-state systems. Reliab Eng Syst Saf 2000;67:193–203] by using a reference example and two newly generated examples. This comparison shows that the extended great deluge gives the best solutions (i.e. those with minimal costs) for 8 instances among 10.     

A universal generating function approach for the analysis of multi-state systems with dependent elements

The paper extends the universal generating function technique used for the analysis of multi-state systems to the case when the performance distributions of some elements depend on states of another element or group of elements.     

End user–oriented node resource allocation: An application‐based method

For a network, how to allocate limited resources to achieve high network reliability has been concerned by engineers. From the perspective of the users, the quality of applications is the most intuitive perception of network reliability. Previous allocation methods focus little on applications, which makes it difficult to optimize resource with given application requirements. This paper proposes an application‐based resource allocation method during network design. Under given application scenario and resource constraints, the allocation model is constructed to maximize application reliability, which is presented as a novel user‐oriented metric to assess the quality of applications. Furthermore, improved genetic algorithm (GA) is adopted to obtain optimal allocation strategy. To improve the efficiency of the algorithm, application‐affected node importance is evaluated to generate initial population. Simulation results demonstrate that the proposed method can achieve higher application reliability than the other three allocation methods when applied to an Avionics Full Duplex Switched Ethernet (AFDX) case. This makes it possible to optimize resource allocation in the light of different application demands in network design.     

A Monte Carlo simulation approach to the availability assessment of multi-state systems with operational dependencies

This paper deals with multi-state systems (MSS), whose performance can settle on different levels, e.g. 100%, 80%, 50% of the nominal capacity, depending on the operative conditions of the constitutive multi-state elements. Examples are manufacturing, production, power generation and gas and oil transportation systems. Often in practice, MSS are such that operational dependencies exist between the system state and the state of its components. For example, in a production line of nodal series structure, with no buffers between the nodes, if one of the nodes throughput changes (e.g. switches from 100% to 50% due to a deterministic or stochastic transition of one of its components), the other nodes must be reconfigured (i.e. their components must deterministically change their states) so as to provide the same throughput.In this paper, we present a Monte Carlo simulation technique which allows modelling the complex dynamics of multi-state components subject to operational dependencies with the system overall state. A correlation method is tailored to model the automatic change of state of the relevant components following a change in one of the system nodes. The proposed technique is verified on a simple case study of literature.     

Monte Carlo simulation analysis of the effects of different system performance levels on the importance of multi-state components

In the present paper, we consider some frequently used importance measures, in their generalized form proposed by the authors for application to multi-state systems constituted by multi-state components. To catch the dynamics of multi-state systems, Monte Carlo simulation has been utilized. A simulation approach has been presented which allows estimating of all the importance measures of the components at a given performance level in a single simulation, provided that the components are independent. The effects of different performance demands made on the system on the importance of its multi-state components have been examined with respect to a simple multi-state series–parallel system. The results have shown that a performance level of a component may be more critical for the achievement of a system performance and less critical for another.