DOI: 10.5176/2251-1938_ORS16.18
Authors: Rohan Shah and Radislav Vaisman
Abstract:
Residual connectedness reliability plays an important role in the analysis of Radio Broadcast and Mobile Ad hoc networks. In this paper we focus on binary systems with identical component reliabilities. The reliability of such systems depends solely on an invariant called the spectra. Calculation of the spectra is considered to be computationally hard, since it is equivalent to the problem of counting the number of connected subgraphs of every size. As a consequence one has to rely on approximation techniques. However for a general network the efficiency of such methods depends on their ability to handle rare-event probability estimation. To cope with this challenge, we study a combination of two Monte Carlo methods. Namely, a well-known Permutation Monte Carlo and the recently pioneered Stochastic Enumeration algorithm. In particular, we show that the former is able to solve easier problems while providing provable theoretical performance guarantees to the delivered estimator, and the latter can successfully handle hard problems under the rare-event setting. Finally, our numerical results imply that these algorithms can provide fast and reliable estimators to the residual connectivity problem.
Keywords: Residual connectedness reliability, System structure function, Permutation Monte Carlo, Stochastic Enumeration, Rare Events.
Updating...