La coloration de graphes est un problème central de l'optimisation combinatoire. C'est un domaine très attractif par ses nombreuses applications. Différentes variantes et généralisations du problème de la coloration de graphes ont été proposées et étudiées. La coloration d'arêtes d'un graphe consiste à attribuer une couleur à chaque arête du graphe de sorte que deux arêtes ayant un sommet commun n'ont jamais la même couleur, le tout en utilisant le moins de couleurs possibles. Dans la première partie de cette thèse, nous étudions le problème de la coloration d'arêtes ℓ-distance, qui est une généralisation de la coloration d'arêtes classique. Nous menons une étude combinatoire et algorithmique du paramètre. L'étude porte sur les classes de graphes suivantes : les chaines, les grilles, les hypercubes, les arbres et des graphes puissances. Le paramètre de la coloration d'arêtes ℓ-distance permet de modéliser des problèmes dans des réseaux assez grands. Cependant, avec la multiplication du nombre de nœuds, les réseaux sont de plus en plus vulnérables aux défaillances (ou pannes). Dans la deuxième partie, nous nous intéressons aux algorithmes tolérants aux pannes et en particulier les algorithmes auto-stabilisants. Nous proposons un algorithme auto-stabilisant pour la coloration propre d'arêtes. Notre solution se base sur le résultat de vizing pour utiliser un minimum de couleurs possibles. Par la suite, nous proposons un algorithme auto-stabilisant de clustering destine a des applications dans le domaine de la sécurité dans les réseaux mobiles Ad hoc. La solution que nous proposons est un partitionnement en clusters base sur les relations de confiance qui existent entre nœuds. Nous proposons aussi un algorithme de gestion de clés de groupe dans les réseaux mobiles ad hoc qui s'appuie sur la topologie de clusters préalablement construite. La sécurité de notre protocole est renforcée par son critère de clustering qui surveille en permanence les relations de confiance et expulse les nœuds malveillants de la session de diffusion.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00736580 |
| Date | 14 December 2010 |
| Creators | Drira, Kaouther |
| Publisher | Université Claude Bernard - Lyon I |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.002 seconds