Doctorat
Equipe : Parallélisme
Partitionnement dans les réseaux mobiles Ad-hoc : Conception et évaluation de protocoles auto-stabilisants robustes.
Début le 01/10/2008
Direction : JOHNEN, Colette
Ecole doctorale :
Etablissement d'inscription : Université Paris-Saclay
Lieu de déroulement : LaBRI Bordeaux
Soutenue le 12/12/2011 devant le jury composé de :
Vincent Villain (Rapporteur), Professeur, MIS, Université Picardie Jules
Verne.
Maria Gradinariu Potop-Butucaru (Rapporteur), Maitre de conférence (HDR),
LIP6, Université Paris-6.
Joffroy Beauquier (Examinateur), Professeur, LRI, Université Paris sud.
Serge Chaumette (Examinateur), Professeur, LaBRI, Université Bordeaux1.
Colette Johnen (Directrice de thèse), Professeur, LaBRI, Université
Bordeaux1.
Véronique Vèque (Directrice de thèse), Professeur, LSS, Supélec.
Activités de recherche :
- Algorithmique répartie
- Autostabilisation
- Réseaux mobiles
- Tolerance aux pannes
- Grappes
Résumé :
Cette thèse se positionne dans le cadre de l'algorithmique distribuée
tolérante aux pannes adaptée aux réseaux mobiles à grande échelle.
Pour remédier à l'éventuelle absence totale de service dans les systèmes
auto-stabilisants, nous avons introduit l'approche auto-stabilisation
robuste apportant une garantie de service pendant la phase de
stabilisation. Cette garantie de service est assurée via : (1) le délai de
reprise d'un service minimum, et (2) la préservation du service minimum
pendant la convergence vers un service optimum, et ce malgré l'occurrence
de certaines perturbations hautement tolérées.
Dans cette thèse, nous proposons, prouvons et évaluons une suite
protocolaire auto-stabilisante robuste.
Dans un premier temps, nous proposons deux protocoles auto-stabilisants
robustes pour les problèmes de partitionnement, et l'établissement et le
maintien de la connaissance des clusters voisins.
Le protocole de partitionnement, baptisé R-BSC, permet de partitionner le
réseau en clusters à 1-saut.
Les noeuds choisis pour être leaders sont les plus aptes à ce rôle, et les
clusters construits sont de taille bornée dans le but d'équilibrer la
charge entre leaders.
Le protocole R-BSC fournit rapidement, en 4 rounds seulement, un service
minimum où le réseau est complètement partitionné en clusters de taille
bornée. Pendant la convergence vers un service optimum, où les leaders
seront bien les noeuds les plus aptes et leur nombre sera réduit
localement, le service minimum restera préservé.
Le protocole de connaissance des clusters voisins, baptisé R-CNK, permet à
chaque leader de connaître l'identité des leaders des clusters voisins, les
chemins menant vers eux, ainsi que la composition (liste des noeuds
ordinaires) des clusters voisins.
Le service minimum de notre protocole R-CNK, atteint après 4 rounds
seulement, garantit que tout leader connaît toujours des chemins vers tous
les leaders des clusters voisins. Ce service minimum est maintenu en dépit
des changements de la structure hiérarchique : création / destruction des
clusters, changement de composition des clusters suite au départ / arrivé
des noeuds ordinaires.
Un deuxième aspect de nos travaux concerne l'évaluation des protocoles
conçus (R-BSC et R-CNK) dans le contexte des réseaux mobiles. Nous avons
mené une étude expérimentale sous le simulateur NS2 pour évaluer les
performances de nos protocoles, ainsi que ceux des protocoles
auto-stabilisants correspondants. Cette étude a montré que nos protocoles
R-BSC et R-CNK offrent de meilleurs performances en terme de garantie de
service.
