Reliability Analysis of Mobile Ad Hoc Networks Using Universal Generating Function

The proliferation of the wireless network over the last decade is one of the significant drivers for the increased deployment of mobile ad hoc networks (MANETs) in the battle field. It is not practically possible to build a fixed wired network infrastructure in battle field. But it is possible to create a mobile wireless network infrastructure because of the mobility of the soldiers. MANET is justified by the possibility of building a network where no infrastructure exists. MANET with group communication applications and multicasting can highly benefit from a networking environment such as military and emergency uses. In such applications, the used ad hoc networks need to be reliable and secure. In recent years, a specific technique called the universal generating function technique (UGFT) has been applied to determine the network reliability. The UGFT is based on an approach that is closely connected to generating functions that are widely used in probability theory. This work devotes to assess the MANET reliability using the UGFT. Reliability of the MANET is defined as the probability that the transformed message from the source can be passed successfully through the MANET and reached the target without any delay. Two kinds of UGFs are discussed in this work, and an algorithm has been proposed to execute the system reliability. This UGFT is illustrated with a case study in a battlefield environment. Copyright © 2014 John Wiley & Sons, Ltd.     

Reliability of lifeline networks under seismic hazard

Lifelines, such as pipelines, transportation, communication and power transmission systems, are networks which extend spatially over large geographical regions. The quantification of the reliability (survival probability) of a lifeline under seismic threat requires attention, as the proper functioning of these systems during or after a destructive earthquake is vital. In this study, a lifeline is idealized as an equivalent network with the capacity of its elements being random and spatially correlated and a comprehensive probabilistic model for the assessment of the reliability of lifelines under earthquake loads is developed. The seismic hazard that the network is exposed to is described by a probability distribution derived by using the past earthquake occurrence data. The seismic hazard analysis is based on the “classical” seismic hazard analysis model with some modifications. An efficient algorithm developed by Yoo and Deo (Yoo YB, Deo N. A comparison of algorithms for terminal pair reliability. IEEE Transactions on Reliability 1988; 37: 210–215) is utilized for the evaluation of the network reliability. This algorithm eliminates the CPU time and memory capacity problems for large networks. A comprehensive computer program, called is coded in Fortran language in order to carry out the numerical computations. Two detailed case studies are presented to show the implementation of the proposed model.     

A Parallel Strategy for the Logical‐probabilistic Calculus‐based Method to Calculate Two‐terminal Reliability

The theory of network reliability has been applied to many complicated network structures, such as computer and communication networks, piping systems, electricity networks, and traffic networks. The theory is used to evaluate the operational performance of networks that can be modeled by probabilistic graphs. Although evaluating network reliability is an Non‐deterministic Polynomial‐time hard problem, numerous solutions have been proposed. However, most of them are based on sequential computing, which under‐utilizes the benefits of multi‐core processor architectures. This paper addresses this limitation by proposing an efficient strategy for calculating the two‐terminal (terminal‐pair) reliability of a binary‐state network that uses parallel computing. Existing methods are analyzed. Then, an efficient method for calculating terminal‐pair reliability based on logical‐probabilistic calculus is proposed. Finally, a parallel version of the proposed algorithm is developed. This is the first study to implement an algorithm for estimating terminal‐pair reliability in parallel on multi‐core processor architectures. The experimental results show that the proposed algorithm and its parallel version outperform an existing sequential algorithm in terms of execution time. Copyright © 2015 John Wiley & Sons, Ltd.     

Element substitution algorithm for general two-terminal network reliability analyses

The computation of the reliability of two-terminal networks is a classical reliability problem. For these types of problems, one is interested, from a general perspective, in obtaining the probability that two specific nodes can communicate. This paper presents a holistic algorithm for the analysis of general networks that follow a two-terminal rationale. The algorithm is based on a set replacement approach and an element inheritance strategy that effectively obtains the minimal cut sets associated with a given network. The vast majority of methods available for obtaining two-terminal reliability are generally based on assumptions about the performance of the network. Some methods assume network components can be in one of two states: (i) either completely failed; or (ii) perfectly functioning, others usually assume that nodes are perfectly reliable and thus, these methods have to be complemented or transformed to account for node failure, and the remaining methods assume minimal cut sets can be readily computed in order to analyze more complex network and component behavior. The algorithm presented in this paper significantly differs from previous approaches available in the literature in the sense that it is based on a predecessor matrix and an element substitution technique that allows for the exact computation of minimal cut sets and the immediate inclusion of node failure without any changes to the pseudo-code. Several case networks are used to validate and illustrate the algorithms.     

Two-terminal reliability analyses for a mobile ad hoc wireless network

Reliability is one of the most important performance measures for emerging technologies. For these systems, shortcomings are often overlooked in early releases as the cutting edge technology overshadows a fragile design. Currently, the proliferation of the mobile ad hoc wireless networks (MAWN) is moving from cutting edge to commodity and thus, reliable performance will be expected. Generally, ad hoc networking is applied for the flexibility and mobility it provides. As a result, military and first responders employ this network scheme and the reliability of the network becomes paramount. To ensure reliability is achieved, one must first be able to analyze and calculate the reliability of the MAWN. This work describes the unique attributes of the MAWN and how the classical analysis of network reliability, where the network configuration is known a priori, can be adjusted to model and analyze this type of network. The methods developed acknowledge the dynamic and scalable nature of the MAWN along with its absence of infrastructure. Thus, the methods rely on a modeling approach that considers the probabilistic formation of different network configurations in a MAWN. Hence, this paper proposes reliability analysis methods that consider the effect of node mobility and the continuous changes in the network's connectivity.     

A unified methodology for reliability assessment of systems with active redundancy

The reliability of engineering systems is usually improved by the inclusion of redundant components in the design. Often, the redundant components must all contribute actively to the operation of the system. Examples include structures, water and power distribution systems, and communication networks. For these systems, the failure of each successive component defines a different topological configuration for the system. A reliable system should perform adequately in as many of these configurations as possible. Consequently, the reliability of a system with active redundancy depends on two factors: the probability, considering component failures, that a functional system topology is maintained; and the probability of adequate system performance in each functional configuration. To date, no single reliability measure exists which combines both of these factors, but such a measure would be useful for comparison of alternative redundant designs. Current methods for reliability assessment have been tailored to the purposes of individual engineering disciplines and reflect the inherent physical properties of specific types of systems. However, an increasing need for reliability analysis of large, complex, multidisciplinary systems requires a more general and unified approach. In this paper, we propose a unified, model-based methodology for reliability-based design which provides a single, second moment reliability index for systems with active redundancy. The reliability index of a redundant pipe network is calculated as an illustrative example.     

Stochastic network interdiction optimization via capacitated network reliability modeling and probabilistic solution discovery

This paper introduces an evolutionary optimization approach that can be readily applied to solve stochastic network interdiction problems (SNIP). The network interdiction problem solved considers the minimization of the cost associated with an interdiction strategy such that the maximum flow that can be transmitted between a source node and a sink node for a fixed network design is greater than or equal to a given reliability requirement. Furthermore, the model assumes that the nominal capacity of each network link and the cost associated with their interdiction can change from link to link and that such interdiction has a probability of being successful. This version of the SNIP is for the first time modeled as a capacitated network reliability problem allowing for the implementation of computation and solution techniques previously unavailable. The solution process is based on an evolutionary algorithm that implements: (1) Monte-Carlo simulation, to generate potential network interdiction strategies, (2) capacitated network reliability techniques to analyze strategies’ source-sink flow reliability and, (3) an evolutionary optimization technique to define, in probabilistic terms, how likely a link is to appear in the final interdiction strategy. Examples for different sizes of networks are used throughout the paper to illustrate the approach.     

An evaluation of the multi-state node networks reliability using the traditional binary-state networks reliability algorithm

A system where the components and system itself are allowed to have a number of performance levels is called the Multi-state system (MSS). A multi-state node network (MNN) is a generalization of the MSS without satisfying the flow conservation law. Evaluating the MNN reliability arises at the design and exploitation stage of many types of technical systems. Up to now, the known existing methods can only evaluate a special MNN reliability called the multi-state node acyclic network (MNAN) in which no cyclic is allowed. However, no method exists for evaluating the general MNN reliability. The main purpose of this article is to show first that each MNN reliability can be solved using any the traditional binary-state networks (TBSN) reliability algorithm with a special code for the state probability. A simple heuristic SDP algorithm based on minimal cuts (MC) for estimating the MNN reliability is presented as an example to show how the TBSN reliability algorithm is revised to solve the MNN reliability problem. To the author's knowledge, this study is the first to discuss the relationships between MNN and TBSN and also the first to present methods to solve the exact and approximated MNN reliability. One example is illustrated to show how the exact MNN reliability is obtained using the proposed algorithm.     

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.     

Communication Reliability Analysis of Wireless Sensor Networks Using Phased‐Mission Model

Communication reliability of wireless sensor networks (WSNs) is essential to ensure the correct and reliable operation of the network. Two distinct communication paradigms exist in WSNs: infrastructure communication and application communication, and a practical communication task typically involves both types of communications. To the best of our knowledge, no reliability studies on WSNs have been dedicated to combining the two communication paradigms. In this paper, we advance the state‐of‐the‐art by proposing a phased‐mission framework to analyze the communication reliability of WSNs considering both infrastructure communication and application communication, as well as K‐coverage requirements. WSNs containing two types of sensor nodes (energy harvesting sensor nodes and battery‐powered sensor nodes) are modeled. Corresponding to the two types of sensor nodes, two different link reliability models are first presented. Binary decision diagram (BDD) based algorithms are then developed for the phased‐mission communication reliability analysis of WSNs. Case studies are given to illustrate the application of the proposed algorithms. Copyright © 2016 John Wiley & Sons, Ltd.     

General network reliability problem and its efficient solution by Subset Simulation

Complex technological networks designed for distribution of some resource or commodity are a pervasive feature of modern society. Moreover, the dependence of our society on modern technological networks constantly grows. As a result, there is an increasing demand for these networks to be highly reliable in delivering their service. As a consequence, there is a pressing need for efficient computational methods that can quantitatively assess the reliability of technological networks to enhance their design and operation in the presence of uncertainty in their future demand, supply and capacity. In this paper, we propose a stochastic framework for quantitative assessment of the reliability of network service, formulate a general network reliability problem within this framework, and then show how to calculate the service reliability using Subset Simulation, an efficient Markov chain Monte Carlo method that was originally developed for estimating small failure probabilities of complex dynamic systems. The efficiency of the method is demonstrated with an illustrative example where two small-world network generation models are compared in terms of the maximum-flow reliability of the networks that they produce.     

Reliability based design optimization using response surfaces in application to multidisciplinary systems

Traditionally, reliability based design optimization (RBDO) is formulated as a nested optimization problem. For these problems the objective is to minimize a cost function while satisfying the reliability constraints. The reliability constraints are usually formulated as constraints on the probability of failure corresponding to each of the failure modes or a single constraint on the system probability of failure. The probability of failure is usually estimated by performing a reliability analysis. The difficulty in evaluating reliability constraints comes from the fact that modern reliability analysis methods are themselves formulated as an optimization problem. Solving such nested optimization problems is extremely expensive for large scale multidisciplinary systems which are likewise computationally intensive. In this research, a framework for performing reliability based multidisciplinary design optimization using approximations is developed. Response surface approximations (RSA) of the limit state functions are used to estimate the probability of failure. An outer loop is incorporated to ensure that the approximate RBDO converges to the actual most probable point of failure. The framework is compared with the exact RBDO procedure. In the proposed methodology, RSAs are employed to significantly reduce the computational expense associated with traditional RBDO. The proposed approach is implemented in application to multidisciplinary test problems, and the computational savings and benefits are discussed.     

A study of service reliability and availability for distributed systems

Distributed systems are usually designed and developed to provide certain important services such as in computing and communication systems. In this paper, a general model is presented for a centralized heterogeneous distributed system, which is widely used in distributed system design. Based on this model, the distributed service reliability which is defined as the probability of successfully providing the service in a distributed environment, an important performance measure for this type of systems, is investigated. An application example is used to illustrate the procedure. Furthermore, with the help of the model, various issues such as the release time to achieve a service reliability requirement, and the sensitivity of model parameters are studied. This type of analysis is important in the application of this type of models.     

Reliability-oriented multi-resource allocation in a stochastic-flow network

A stochastic-flow network consists of a set of nodes, including source nodes which supply various resources and sink nodes at which resource demands take place, and a collection of arcs whose capacities have multiple operational states. The network reliability of such a stochastic-flow network is the probability that resources can be successfully transmitted from source nodes through multi-capacitated arcs to sink nodes. Although the evaluation schemes of network reliability in stochastic-flow networks have been extensively studied in the literature, how to allocate various resources at source nodes in a reliable means remains unanswered. In this study, a resource allocation problem in a stochastic-flow network is formulated that aims to determine the optimal resource allocation policy at source nodes subject to given resource demands at sink nodes such that the network reliability of the stochastic-flow network is maximized, and an algorithm for computing the optimal resource allocation is proposed that incorporates the principle of minimal path vectors. A numerical example is given to illustrate the proposed algorithm.     

Reliability analysis of laminated composite structures using finite elements and neural networks

Saving of computer processing time on the reliability analysis of laminated composite structures using artificial neural networks is the main objective of this work. This subject is particularly important when the reliability index is a constraint in the optimization of structural performance, because the task of looking for an optimum structural design demands also a very high processing time. Reliability methods, such as Standard Monte Carlo (SMC), Monte Carlo with Importance Sampling (MC–IS), First Order Reliability Method (FORM) and FORM with Multiple Check Points (FORM–MCPs) are used to compare the solution and the processing time when the Finite Element Method (FEM) is employed and when the finite element analysis (FEA) is substituted by trained artificial neural networks (ANNs). Two ANN are used here: the Multilayer Perceptron Network (MPN) and the Radial Basis Network (RBN). Several examples are presented, including a shell with geometrically non-linear behavior, which shows the advantages using this methodology.     

合肥17层高楼爆破网路设计及可靠度分析

合肥一栋17层高楼拟予爆破拆除.因炮孔总数高达53000个,为防止因起爆网路失效而导致爆破任务失败,根据现场实际情况采用了孔内导爆管雷管簇并联,每层楼由四通联成2个多通路闭合网路,层间8通路的自下而上顺序0.5 s延期的起爆网路.用概率论的方法计算了每层主要网路的可靠度.理论计算和爆破实践表明该网路设计是可靠的,能满足巨大炮孔数量楼房拆除爆破的需要.     

Reliability analysis of cluster-based ad-hoc networks

The mobile ad-hoc wireless network (MAWN) is a new and emerging network scheme that is being employed in a variety of applications. The MAWN varies from traditional networks because it is a self-forming and dynamic network. The MAWN is free of infrastructure and, as such, only the mobile nodes comprise the network. Pairs of nodes communicate either directly or through other nodes. To do so, each node acts, in turn, as a source, destination, and relay of messages. The virtue of a MAWN is the flexibility this provides; however, the challenge for reliability analyses is also brought about by this unique feature. The variability and volatility of the MAWN configuration makes typical reliability methods (e.g. reliability block diagram) inappropriate because no single structure or configuration represents all manifestations of a MAWN. For this reason, new methods are being developed to analyze the reliability of this new networking technology. New published methods adapt to this feature by treating the configuration probabilistically or by inclusion of embedded mobility models. This paper joins both methods together and expands upon these works by modifying the problem formulation to address the reliability analysis of a cluster-based MAWN. The cluster-based MAWN is deployed in applications with constraints on networking resources such as bandwidth and energy. This paper presents the problem's formulation, a discussion of applicable reliability metrics for the MAWN, and illustration of a Monte Carlo simulation method through the analysis of several example networks.     

Cutset enumeration of network systems with link and node failures

Network reliability analysis has received considerable attention and is thus widely studied to predict and prevent any network failure. However, most of such works presume perfectly reliable nodes. Although a few studies have considered both link and node failures, none of these methods has utilized the minimal paths or cuts, which are considered as fundamental approaches in the network reliability evaluation. An efficient method for deducing the minimal cutsets of a system subject to both link and node failures from the minimal cutsets of the system, which assumes perfect node reliability, is presented. The proposed method does not require re-enumeration of minimal cutsets for the additional consideration of the node failures. For a simple extension of such a method, the proposed approach can be embedded in any exact or approximate algorithm to account for link failures as well as node failures. As a result, the application of this method would be more realistic and valuable in practice for the reliability evaluation of networks with unreliable nodes.     

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.