Le calcul de la fiabilité des réseaux est en général un problème NP-difficile. On peut par exemple, s'intéresser à la fiabilité des systèmes de télécommunications où l'on veut évaluer la probabilité qu'un groupe sélectionné de noeuds (qui peut être juste une paire) puissent communiquer, ou s'intéresser aux systèmes d'alimentation électriques où l'on veut estimer le risque que l'électricité n'est pas fournie à certains noeuds, ou encore, étudier la fiabilité des systèmes de transport, où les liens représentent les routes et sont soumis à des dommages. Dans tous ces cas, un ensemble de noeuds déconnectés peut avoir des conséquences critiques, que ce soit financières ou au niveau de la sécurité. Une estimation précise de la fiabilité est ainsi nécessaire. Les réseaux de communication moderne se caractérisent par leur grande taille, donc l'estimation via la simulation de Monte Carlo devient souvent un choix favorable. Un algorithme de Monte Carlo sous sa forme standard, échantillonne N réalisations du graphe (représentant le réseau) indépendantes, et la défiabilité est estimée à partir de la proportion des N réalisations pour lesquelles les noeuds sélectionnés ne sont pas connectés. Dans ces réseaux, les probabilités de défaillance des liens (arcs) sont généralement petites et donc les pannes d'un réseau deviennent des événements rares. Cela pose un défi majeur pour estimer la fiabilité d'un réseau. Dans cette thèse, nous présentons différentes techniques basées sur l'échantillonnage préférentiel (Importance Sampling en anglais IS), pour l'estimation de la fiabilité d'un réseau. Grace à cette technique les probabilités originales d'échantillonnage des arcs sont remplacées par de nouvelles probabilités, puis multiplier l'ancien estimateur par le quotient de vraisemblance (likelihood ratio) pour rester sans biais. On s'intéresse tout particulièrement à l'étude et au calcul de la fiabilité des réseaux hautement fiables et représentés par des graphes statiques. Dans ce cas la défiabilité est très petite, parfois de l'ordre de 10−10, ce qui rend l'approche standard de Monte Carlo inutile, car pour pouvoir estimer cette probabilité il nous faut un échantillon de taille supérieure à dix milliards. Pour une bonne estimation de la fiabilité des réseaux au moindre coût, nous avons étudié, analysé et développé les points suivants : - En premier lieu nous avons développé une méthode basée sur l'échantillonnage préférentiel. Le processus d'échantillonnage de tous les arcs du graphe sous la nouvelle probabilité est représenté par une chaîne de Markov, telle qu'à chaque étape on détermine l'état d'un arc avec une nouvelle probabilité déterminée en fonction de l'état de tous les arcs précédemment échantillonnés. Les fonctions valeurs de la nouvelle probabilité sont approchées par les coupes minimales possédant la plus grande probabilité de défiabilité, elle est le produit des défiabilités des arcs de la coupe. Des preuves de bonnes propriétés de l'estimateur basé sur l'échantillonnage préférentiel sont faites. - Un deuxième point a été abordé et développé, consiste à appliquer des techniques de réduction série-parallèle à chaque étape de l'échantillonnage IS précédemment décrit, afin de réduire substantiellement et la variance et le temps de simulation. - Le dernier point consiste à combiner pour approximation de l'estimateur à variance nulle, l'approximation de la défiabilité par une coupe minimale qui sous-estime la défiabilité avec une autre approximation basée sur les chemins minimaux qui la sur-estime. Des algorithmes d'optimisation sont utilisés pour rechercher le facteur optimal d'ajustement des deux approximations pour minimiser la variance.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00940140 |
| Date | 08 July 2013 |
| Creators | Saggadi, Samira |
| Publisher | Université Rennes 1 |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0019 seconds