Manuscrit de thèse - Yoann Pigné

©Yoann Pigné, 2008

Description

Manuscrit de thèse - Yoann Pigné

Sujets

• Sciences et techniques

Informations

• Publié par: ikukucex
• Nombre de lectures: 160
• Langue: Français
• Poids de l'ouvrage: 2 Mo

Extrait

UNIVERSITÉ DU HAVRE UFR Sciences et Techniques THÈSE pour obtenir le grade de DOCTEUR DE L’UNIVERSITÉ DU HAVRE Discipline : Informatique Yoann PIGNÉ le 4 décembre 2008 MODÉLISATION ET TRAITEMENT DÉCENTRALISÉ DES GRAPHES DYNAMIQUES – APPLICATION AUX RÉSEAUX MOBILES AD HOC Directeur : Frédéric GUINAND Professeur à l’université du Havre Raporteurs : Pascal BOUVRY Professeur à l’université du Luxembourg Serge CHAUMETTE Professeur à l’université de Bordeaux 1 Examinatrices : Isabelle GUÉRIN-LASSOUS Professeure à l’université de Lyon 1 Clémence MAGNIEN Chargée de recherche CNRS à l’université de Paris 6 Invité : Alain CARDON Professeur de première classe retraité de l’université du HavreREMERCIEMENTS Vous commencez ici la lecture de cette thèse, moi, c’est par ces remerciements que j’en termine la rédaction. Difficile en une page d’énumérer, sans en oublier, toutes les personnes qui ont, de près ou de loin, eu une importance dans cette aventure, et à qui je dois un "Merci !". L’exercice est d’autant plus délicat que c’est peut-être la seule page que vous lirez (c’est la seule page que je lis d’ordinaire dans une thèse... enfin presque). Je commencerai donc de manière assez conventionnelle mais avec un réel plaisir par remercier Frédéric GUINAND pour m’avoir permis de travailler avec lui. Notre collabora- tion a commencé avant cette thèse et se prolongera encore après, je l’espère. Merci Fred pour ta disponibilité, pour ta générosité, pour ton optimisme infaillible et pour ton goût pour la bonne chère. Merci à Pascal BOUVRY et à Serge CHAUMETTE pour avoir accepté de rapporter sur cette thèse. Par votre travail de lecture et d’analyse vous représentez la première valida- tion de mon travail hors de l’équipe et je vous en suis très reconnaissant. Merci à Isabelle GUÉRIN-LASSOUS, à Clémence MAGNIEN et à Alain CARDON pour avoir accepté de par- ticiper au jury. Je tiens à remercier les membres de l’équipe RI C qui m’ont accueilli et avec qui j’ai2 pu travailler. Damien, merci pour ton esprit de groupe et pour ta vision noble (et re- motivante quand il le faut) de la recherche. Cyrille, merci pour tout ce que tu fais pour l’équipe et pour le labo et bravo pour tes goûts en pâtisseries orientales et autres tabacs à narguilé. Stefan, tu vas bientôt savoir mieux parler havrais que moi. Véronique, grâce à toi j’ai découvert que j’étais baryton, la classe ! Merci pour les relectures de mon travail et bravo pour ta maîtrise spectaculaire des lettres. Jean-Luc, si tu ne devais en choisir qu’une (lettre), je sais laquelle ce serait. Mon respect indéfectible pour ta blague de la petite fille et de sa grand-mère. Antoine, mon maître geek, je suis très fier de notre projet commun mais le truc le plus classe est quand même de t’avoir converti à Gentoo. Pier- rick, bravo pour ta quête de la-connaissance-de-tout-sur-absolument-tout, tu t’en sors pas mal. Tu as rendu nos trajets en train moins ennuyeux. Merci pour ça et merci pour le Métal. Merci à la team Urban Terror : Butcher, Obama, Razi3l, Ichitaka, MasterKekete, Virus, Kamikaze, Astra, Ciao16Coups et Mobutu pour cette ambiance de travail si har- monieuse et paisible qui a toujours garanti une productivité optimale dans mon travail. Un peu plus loin de l’équipe et du labo, il y a toutes les rencontres faites au détourd’une conférence ou plus simplement d’un couloir. Merci Djamila, Nathalie, Arnaud, Luc, Apivadee, Louisa, you all are so great, my friends. Il y a les potes de toujours, ceux que j’ai saoulés et que je saoulerai encore en es- sayant d’expliquer ce que je fais. Merci Anelise, Quentin, Antoine, Nicolas, Yannis, Valéry, Mélanie, Alexia, Lucie, Matthieu. Il y a aussi la famille qui m’a toujours fait confiance, Gilbert, Marie, Tony, Max, Chris- tine, Frédo, Hélène, Vinie, Romu et bien-sûr mes parents qui m’ont toujours soutenu et encouragé. Enfin, il y a Toi. Merci pour tout ce qu’on a eu.À mes parents.TABLE DES MATIÈRES Table des matières v Table des figures vii Liste des définitions ix 1 Introduction 1 1.1 Systèmes complexes et graphes dynamiques . . . . . . . . . . . . . . . . . 1 1.2 Les réseaux mobiles ad hoc . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 I Graphes dynamiques 7 2 État de l’art 11 2.1 Quelques modèles de graphes dynamiques . . . . . . . . . . . . . . . . . . 12 2.2 Analyse des différents modèles . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3 Relations entre modèles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3 Modèles et métriques pour les graphes dynamiques 29 3.1 Définition générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.2 Exemples de graphes dynamiques . . . . . . . . . . . . . . . . . . . . . . . 31 3.3 Métriques pour les graphes dynamiques . . . . . . . . . . . . . . . . . . . . 36 II Graphes dynamiques : traitement et optimisation décentralisés 43 4 État de l’art des méthodes à base de fourmis 49 4.1 Les principales approches à base de fourmis . . . . . . . . . . . . . . . . . 50 4.2 Les différentes classes de problèmes abordés . . . . . . . . . . . . . . . . . 59 4.3 Les problèmes ouverts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 vTABLE DES MATIÈRES 5 Approche générale d’optimisation décentralisée pour les graphes dynamiques 69 5.1 Approche générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.2 Identification des structures . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 5.3 Le modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 III Applications aux réseaux mobilesadhoc 77 6 Des réseaux mobilesadhoc aux graphes dynamiques 81 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 6.2 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 6.3 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 6.4 Environnements et modèles de mobilité . . . . . . . . . . . . . . . . . . . . 89 6.5 Des MANETs aux graphes dynamiques . . . . . . . . . . . . . . . . . . . . . 93 7 Le probleme du chemin le plus court et le plus robuste 97 7.1 Problématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 7.2 Quel service pour quel réseau ? . . . . . . . . . . . . . . . . . . . . . . . . . 99 7.3 État de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 7.4 Approche fourmi pour le plus court chemin robuste . . . . . . . . . . . . . 110 8 Forêt couvrante dans un MANET 131 8.1 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 8.2 Algorithme initial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 8.3 Simulations et améliorations . . . . . . . . . . . . . . . . . . . . . . . . . . 134 8.4 Analyses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 8.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 9 Conclusion 147 9.1 Autour des graphes dynamiques . . . . . . . . . . . . . . . . . . . . . . . . 147 9.2 Autour des méthodes d’intelligence collectives . . . . . . . . . . . . . . . . 148 9.3 Autour des problématiques de réseaux mobiles ad hoc . . . . . . . . . . . 148 9.4 Perspectives de ce travail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 Bibliographie 151 Publications 161 Index 163 viTABLE DES FIGURES 1.1 Quelea Flock par Alastair Rae. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.1 L’allure générale du Web selon A. Z. BRODER et al. en forme de nœud papillon. 14 2.2 Quatre graphes statiques montrant les différentes étapes de l’évolution d’un réseau dynamique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3 Un graphe évolutif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4 Ligne du temps dans l’évolution d’un réseau dynamique. . . . . . . . . . . . . 17 2.5 Réseau à topologie fixe où le poids des arête évolue . . . . . . . . . . . . . . . 23 2.6 Graphe Space-Time d’un réseau de la figure 2.5 . . . . . . . . . . . . . . . . . . 23 2.7 Le graphe évolutif correspondant au réseau de la figure 2.5. . . . . . . . . . . 26 2.8 Inclusions entre les différents modèles de graphes dynamiques. . . . . . . . . 27 2.9 Analyse diférée des modèles de graphes par graphes évolutifs. . . . . . . . . . 27 3.1 Volatilité d’un élément en fonction du nombre d’apparitions et de son âge cumulé. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.2 Exemple de Graphe DynamiqueG . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.1 Graphe d’héritage entre les ACOs . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.1 Principe général de résolution de problèmes à l’aide d’un système complexe matérialisé par une colonie de fourmis. . . . . . . . . . . . . . . . . . . . . . . 71 5.2 Exemple de deux structures différentes dans un même graphe qui sont aussi deux solutions pour différents problèmes. . . . . . . . . . . . . . . . . . . . . 72 7.1 ChronoSPT produit à partir du Space-Time Network de la figure 2.6. . . . . . 105 7.2 Voisinage et sélection MPR d’un nœd. . . . . . . . . . . . . . . . . . . . . . . . 106 7.3 Un réseau et les sélecteurs MPR associés à chaque sommet. . . . . . . . . . . 107 7.4 Exemple de structure robuste. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 7.5 Phénomène d’impasse dans le parcours d’une fourmi. . . . . . . . . . . . . . 119 7.6 Échantillon du réseau de communication obtenu par la simulation du scé- nario « volatilité ». . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 7.7 Simulation du s