Modèle de calcul, primitives, et applications de référence, pour le domaine des réseaux ad hoc fortement mobiles, Process calculus, programming interface and reference applications, for highly mobile ad hoc networks

Numéro d’ordre: 4169
THÈSE
PRÉSENTÉE À
L’UNIVERSITÉ BORDEAUX I
ÉCOLE DOCTORALE DE MATHÉMATIQUES ET
D’INFORMATIQUE
ParJérémie Albert
POUR OBTENIR LE GRADE DE
DOCTEUR
SPÉCIALITÉ : INFORMATIQUE
Modèle de calcul, primitives, et applications de référence,
pour le domaine des réseaux ad hoc fortement mobiles
Soutenue le : 13 décembre 2010
Après avis des rapporteurs :
Pascal Bouvry ..... Professeur
Rachid Guerraoui Professeur
Devant la commission d’examen composée de :
Olivier Beaumont Directeur de recherche Président
Pascal Bouvry ..... Professeur ................... Rapporteur
Isabelle Demeure . Professeur ................... Examinatrice
Serge Chaumette Professeur ................... Directeur de thèse
2010Remerciements
Les remerciements ont souvent été la première partie que je lisais lorsque je m’attaquais
à la lecture d’une thèse. Seule partie informelle d’un mémoire de thèse, c’est sans aucun
doute la partie qui en dit le plus sur l’auteur, permettant notamment au lecteur d’avoir
un aperçu du contexte dans lequel s’est déroulé ce travail.
Pourcommencercettelonguelistederemerciements,jetiensàexprimermareconnaissance
à mes rapporteurs, Pascal Bouvry et Rachid Guerraoui d’avoir accepté cette tâche, pour
leurs remarques sur le document et leurs disponibilités lors de nos échanges.
Merci aussi à Isabelle Demeure d’avoir accepté de participer à mon jury de thèse et à
Olivier Beaumont d’avoir accepté, en plus d’y participer, de le présider.
Je tiens bien sûr aussi à remercier mon directeur de thèse Serge Chaumette de m’avoir
proposé, il y a 3 ans, un sujet de thèse suffisament souple et adaptable pour me permettre
de l’emmener là où je le souhaitais.
Je tiens aussi à remercier toutes les personnes liées à mon environnement de travail -
collègues de CVT et leurs conjoint(e)s - qui ont su rendre mon quotidien si agréable. Je
pense notamment à Arnaud, Lucile, Lionel, Amélie, Eve, Armand, Fabien, Alice, Rémi,
Joinjoin et Julien pour les “anciens” et à Jo, Rémi, Renaud, Damien, Hugo, Mauricio,
Bissyandé et Cyril pour les “moins anciens”.
Merci aussi à ma famille (dont l’architecture n’est pas triviale) de m’avoir entouré et
encouragé sans m’avoir jamais fait ressentir une quelconque pression. Merci donc aux
quatre membres permanents de ma famille compsicoise (33) et aux deux membres par
intérim’ plaisirois (78) ainsi qu’aux cinq membres de ma famille colombienne (92). Un
merci tout particulier à mon oncle toulousain (31) qui a su faire naître en moi une grande
curiosité pour ces étranges machines qu’étaient les premiers ordinateurs personnels il y a
maintenant plus de 20 ans! Merci aussi à ma famille d’adoption blayaise et francilienne
d’avoir fait le déplacement pour endurer ma soutenance de thèse.
Je tiens aussi à remercier mes amis “gerboisiens”, Bobo, Boyan et Damien d’être venu
assister à ma soutenance mais aussi à Buendon, Émilie, Hélène, Hélène, Julie, Kiki et
Vianney pour les moments de détente que nous avons pu partager et qui me permettaient
certainement inconsciemment de trier les bonnes idées que j’avais en tête des mauvaises.
Merci aussi aux non gerboisiens Maëlle et Pierre, Jess et Kevin et aux Lulus.
Enfin, un énorme merci à Carole d’avoir réussi à supporter le rythme étrange qu’implique
la compagnie d’un thésard, surtout en période de rédaction!
iiiTable des matières
Introduction 1
1 Définition du contexte 5
1.1 Hypothèses fréquentes dans l’étude des MANets . . . . . . . . . . . . . . . . 5
1.1.1 H : Le monde est plat . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
1.1.2 H : Une zone de transmission radio est circulaire . . . . . . . . . . . 72
1.1.3 H : Toutes les radios possèdent la même portée . . . . . . . . . . . . 73
1.1.4 H : La relation de voisinage est symétrique . . . . . . . . . . . . . . 84
1.1.5 H : La force du signal perçuepar un nœudest uniquement fonction5
de la distance entre les nœuds. . . . . . . . . . . . . . . . . . . . . . . 8
1.1.6 H : Les nœuds sont capables de détecter localement la perte d’un6
message . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1.7 H : La mobilité des nœuds est très simplement exprimable . . . . . 97
1.1.8 H : Les nœuds possèdent un identifiant unique . . . . . . . . . . . . 108
1.1.9 H : Il existe des mécanismes de routage efficaces dans les MANets 129
1.1.10 H : Le réseau est quasiment toujours connecté . . . . . . . . . . . . 1310
1.2 Notre contexte de recherche : les iMANets . . . . . . . . . . . . . . . . . . . . 14
2 Modèles de calcul et middlewares existants 15
2.1 État de l’art des modèles de calcul . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.1 Introduction aux systèmes de transitions étiquetées . . . . . . . . . . 15
2.1.2 Modélisation des systèmes communicants . . . . . . . . . . . . . . . . 16
2.1.3 Modèles de calcul pour réseaux mobiles ad hoc . . . . . . . . . . . . 17
2.1.4 Bilan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2 État de l’art des middlewares . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.1 Paradigmes de communication . . . . . . . . . . . . . . . . . . . . . . 22
2.2.2 Middleware existants . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
iiiiv TABLE DES MATIÈRES
3 CiMAN, un modèle formel pour les iMANets 57
Glossaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.1 Vision intuitive du modèle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.1.1 Les processus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.1.2 Les unités de calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.1.3 Les nœuds et les messages . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.1.4 Le monde réel tel que nous le voyons . . . . . . . . . . . . . . . . . . 64
3.2 Définitions générales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.2.1 Définitions des éléments de base . . . . . . . . . . . . . . . . . . . . . 65
3.2.2 Système de transitions étiquetées . . . . . . . . . . . . . . . . . . . . . 66
3.2.3 Sorte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.2.4 Relations d’équivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.3 Les processus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.3.1 Grammaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.3.2 Transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.3.3 Sorte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.3.4 Congruence observationnelle . . . . . . . . . . . . . . . . . . . . . . . . 75
3.3.5 Relations entre processus. . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.4 Les unités de calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.4.1 Grammaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.4.2 Transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.4.3 Sorte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.4.4 Congruence observationnelle . . . . . . . . . . . . . . . . . . . . . . . . 82
3.4.5 Relations entre processus et unités de calcul . . . . . . . . . . . . . . 83
3.4.6 Relations entre unités de calcul . . . . . . . . . . . . . . . . . . . . . . 84
3.4.7 Exemples d’utilisation du niveau unité de calcul . . . . . . . . . . . . 84
3.5 Les nœuds et les messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.5.1 Grammaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.5.2 Notations, définitions utiles . . . . . . . . . . . . . . . . . . . . . . . . 90
3.5.3 Transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.5.4 Sorte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.5.5 Congruence observationnelle . . . . . . . . . . . . . . . . . . . . . . . . 95
3.5.6 Relations entre unités de calcul et nœuds . . . . . . . . . . . . . . . . 96
3.5.7 Relations entre nœuds . . . . . . . . . . . . . . . . . . . . . . . . . . . 97TABLE DES MATIÈRES v
3.5.8 Gestion de la mobilité . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.5.9 Perspectives de recherche . . . . . . . . . . . . . . . . . . . . . . . . . 101
4 Primitives, support d’exécution et applications 105
4.1 Définitions d’éléments de sécurité . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.1.1 Identité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.1.2 Identifiant.