99-these-malville

Informations

• Publié par: Nachung
• Nombre de lectures: 86
• Langue: Français

Extrait

UNIVERSITE DE SAVOIE
Nº attribué par la bibliothèque
THESE
Pour obtenir le grade de
DOCTEUR DE L’UNIVERSITE DE SAVOIE
Discipline : Informatique
par
Eric MALVILLE
le 25 mars 1999
Titre :
L’auto-organisation de groupes pour l’allocation de
tâches dans les Systèmes Multi-Agents :
Application à CORBA
Directeur de thèse :
M. Michel RIVEILL
JURY
M. Yves DEMAZEAU Chargé de recherche au CNRS (IMAG) rapporteur
M. Hervé GUYENNET Professeur de l’Université de Besançon rapporteur
M. Pierre ROLIN Professeur de l’ENST Bretagne président
M. François BOURDON Professeur de l’Université de Caen
M. Michel RIVEILL Profersité de Savoie2REMERCIEMENTS
Je tiens en tout premier lieu à remercier la direction du SEPT (Service d'Etudes communes de
La Poste et de France Telecom) et du CNET (Centre National d'Etudes des Télécommunica-
tions) pour m'avoir permis de réaliser cette thèse dans des conditions idéales.
Je remercie Philippe Maurice, ancien responsable du groupement SCE, ainsi que Marc Girault
et Fabrice Clerc, responsables actuels de l'URD SPR, qui m'ont accueilli au sein de leur équipe
et qui m'ont permis d'accomplir cette thèse dans les meilleures conditions.
Je remercie M. Yves Demazeau et M. Hervé Guyennet pour l'attention qu'ils ont bien voulu por-
ter à cette thèse et pour l'honneur qu'ils m'ont fait d'en être rapporteurs.
Je remercie M. Pierre Rolin qui a bien voulu s'intéresser à ces travaux et qui a accepté de par-
ticiper au jury de thèse.
Je remercie Anne Beguin et Anne Lille pour m'avoir fait découvrir des sujets passionnants et
pour m'avoir encadré au cours des années que j'ai passées au SEPT et au CNET.
Je remercie tous mes collègues, et en particulier ceux du département SCE/ARC et des équipes
APERO et PALEO, qui ont su créer une ambiance de travail aussi stimulante qu'agréable. Je
remercie Bruno Dillenseger (le concepteur des protocoles de groupes d'artisans), Christophe
Trompette et Emmanuel Hym, qui m'ont bien souvent écouté, conseillé et dépanné.
Je remercie Michel Riveill pour avoir accepté d'être le directeur de cette thèse et qui, malgré
les 1000 Km qui nous séparaient, a su m'apporter des conseils et un soutien précieux.
J'exprime toute ma gratitude à François Bourdon pour son aide, ses conseils et ses discussions.
Ses nombreuses idées, son enthousiasme et son énergie font du domaine de la recherche un uni-
vers passionnant. Encore merci !
Enfin, je remercie mes amis et ma famille pour leur aide, leur soutien et leur compréhension.
34SOMMAIRE
Liste des figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Chapitre 1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
PARTIE 1
Chapitre 2 Les organisations en IAD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19
Chapitre 3 L’auto-organisation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
PARTIE 2
Chapitre 4 Les groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
Chapitre 5 L’abstraction de groupe dans CORBA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
PARTIE 3
Chapitre 6 Matisse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
Chapitre 7 Exemple de mise en œuvre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
Chapitre 8 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
Chapitre 9 Conclusion et perspectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
Bibliographie. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
Table des matières. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
ANNEXES
Annexe A La gestion des objets groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
Annexe B Mise en œuvre et configuration d’une simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
56LISTE DES FIGURES
Chapitre 2 Les organisations en IAD
Fig. 2.1 Exemples de hiérarchies. ..................................................................................................... 23
Fig. 2.2 Le réseau contractuel ........................................................................................................... 25
Fig. 2.3 Les étapes du processus de courtage ................................................................................... 27
Fig. 2.4 Le marché centralisé............................................................................................................ 28
Fig. 2.5 Gestion interne de la structure de groupe ............................................................................ 29
Fig. 2.6 Invocation de la structure de groupe avec une requête complète ........................................ 30
Chapitre 3 L’auto-organisation
Fig. 3.1 Principe de la relaxation restreinte... 39
Fig. 3.2 Exemple de calcul du seuil permettant de déterminer les agents pertinents........................ 40
Fig. 3.3 Les accointances d’un agent ................................................................................................ 42
Fig. 3.4 Les plans logiques de services et de courtiers ..................................................................... 43
Fig. 3.5 Les trois points de vue ......................................................................................................... 45
Fig. 3.6 Le modèle client / serveur.................................................................................................... 46
Fig. 3.7 Définition du champ gravitationnel autour d’une charge.................................................... 48
Fig. 3.8 La décomposition et la composition.................................................................................... 48
Chapitre 4 Les groupes
Fig. 4.1 (a) Problèmes d’ordre de livraison des messages. (b) Problème du transfert d’état............ 62
Fig. 4.2 La synchronisation virtuelle. ............................................................................................... 64
Fig. 4.3 Les horloges logiques. ......................................................................................................... 66
Fig. 4.4 Les horloges vectorielles. .................................................................................................... 67
Fig. 4.5 Utilisation d’horloges vectorielles pour retarder la livraison des messages........................ 67
Fig. 4.6 Livraison causale des messages pour le recouvrement de groupes. .................................... 73
Chapitre 5 L’abstraction de groupe dans CORBA
Fig. 5.1 L’architecture OMA. ........................................................................................................... 77
Fig. 5.2 L’architecture CORBA........................................................................................................ 77
Fig. 5.3 Les classesBOA etEnvironment d’Electra. ................................................................... 80
Fig. 5.4 Exemple de génération de talon dans Electra...................................................................... 81
Fig. 5.5 Le modèle d’Orbix+Isis....................................................................................................... 81
Fig. 5.6 L’approche service........... 82
Fig. 5.7 Le module mGroupAccess ..................................................................................................83
Fig. 5.8 Le modulemGroupAdmin .......................................84
Fig. 5.9 Le module84
Fig. 5.10 InterfaceSGstruct...........................................85
Fig. 5.11 InterfaceSGlocal............................................86
Fig. 5.12 Les interfaces du service de groupe de COOL-ORB......................................................... 87
Fig. 5.13 L’architecture d’Electra..................................................................................................... 89
Chapitre 6 Matisse
Fig. 6.1 Inscription d’un nouveau membre : principe général........................................................ 100
Fig. 6.2 Inscription simultanée de deux serveurs............................................................................ 100
Fig. 6.3 La livraison en ordre total.................................................................................................. 101
7Fig. 6.4 La panne du coordinateur .................................................................................................. 102
Fig. 6.5 L’atomici