Efficient reliability modeling of the heterogeneous autonomous decentralized systems

The heterogeneous autonomous decentralized system technology offers a way t o integrate different types of context-related autonomous decentralized (su b) systems into a coherent system. The aim of this research is to model and evaluate the communication capacity among the subsystems connected, by com munication gateways of a heterogeneous autonomous decentralized system. Fai lures of subsystems and communication gateways in the system are taken into account. We use graphs to represent the topologies of heterogeneous autono mous decentralized systems and use the residual connectedness reliability ( RCR) to characterize the communication capacity among its subsystems connec ted by its gateways. This model enables us to share research results obtain ed in residual connectedness reliability study in graph theory. Not to our surprise, we learnt soon that computing RCR of general graphs is NP-hard. B ut to our surprise, there exist no efficient approximation algorithms that can give a good estimation of RCR for an arbitrary graph when both vertices and edges may fail. We proposed in this paper a simulation scheme that gav e us good results for small to large graphs but failed for very large graph s. Then we applied a theoretical bounding approach. We obtained expressions for, upper and lower bounds of RCR for arbitrary graphs. Both upper and lo wer bound expressions can be computed in polynomial time. We applied these expressions to several typical graphs and showed that the differences betwe en the upper and lower bounds tend to zero as the sizes of graphs tend to i nfinite. The contributions of this research are twofold, we find an efficie nt way to model and evaluate the communication capacity of heterogeneous au tonomous decentralized systems; we contribute an efficient algorithm to est imate RCR in general graph theory.