A simulation Method for Network Performability Estimation using Heuristically-computed Pathsets and Cutsets
Résumé
Consider a set of terminal nodes K that belong to a network whose nodes are connected by links that fail independently with known probabilities. We introduce a method for estimating any performability measure that depends on the hop distance between terminal nodes. It generalises previously introduced Monte Carlo methods for estimation of the K-reliability of networks with variance reduction compared to crude Monte Carlo. They are based on using sets of edges named d-pathsets and d-cutsets for reducing the variance of the estimator. These sets of edges, considered as a priori known in previous literature, heaviliy affect the attained performance; we hereby introduce and compare a family of heuristics for their selection. Numerical examples are presented, showing the significant efficiency improvements that can be obtained by chaining the edge set selection heuristics to the proposed Monte Carlo sampling plan.
Considérez un ensemble de noeuds terminaux K appartenant à un réseau dont les noeuds sont reliés par des liaisons qui échouent indépendamment avec des probabilités connues. Nous présentons une méthode pour estimer n'importe quelle mesure de performabilité qui dépend de la distance en sauts entre les noeuds terminaux. Elle généralise des méthodes de Monte Carlo précédemment introduites pour l'estimation de la K-fiabilité des réseaux avec réduction de la variance par rapport à Monte Carlo standard. Ces méthodes sont basées sur l'utilisation d'ensembles d'arêtes désignés d-pathsets et d-cutsets pour réduire la variance de l'estimateur. Ces ensembles d'arêtes, considérés comme connus a priori dans la littérature précédente, affectent fortement les performances atteintes ; nous introduisons et comparons une famille d'heuristiques pour leur sélection. Des exemples numériques sont présentés, montrant les importantes améliorations dans l'efficacité qui peuvent être obtenues par le chaînage de ces heuristiques avec le plan d'échantillonnage de Monte Carlo proposé.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...