Soutenance mémoire
Les ADLs
Les langages de description des architectures (Architecture Description Language : ADL) ont pour objectif de fournir des notations expressives an de représenter la structure conceptuelle d’un système. De tels langages ont pour ambition d’aider à communiquer et à raisonner sur les systèmes et doivent pour cela dénir : 1) une syntaxe et une sémantique précises pour résoudre les ambiguïtés et aider à la détection des inconsistances, et 2) un ensemble de techniques et d’outils pour raisonner sur les propriétés des systèmes décrits. Nous retrouvons, dans la littérature, un nombre considérable d’ADLs qui peuvent être classés en ADLs spécialisés ou généralistes. Nous pouvons citer parmi les ADLs spécialisés, les AADLs (Avionics ADL) [AAD06] tels que le langage MetaH [VB93, McD01] traitant la description des applications temps-réel embarquées et le langage Cotre [FBB+03, COT06] développé en partie au LAAS-CNRS et chez Airbus. On peut citer aussi le langage SADL (Structural ADL) [MR97] visant la description et la vérication d’architectures hiérarchiques et multi-niveaux, et C2SADL [MRT99] qui traite de la description des architectures dynamiques. Parmi les ADLs généralistes on retrouve les langages Rapide [LKA+95, LV95], Darwin [MDK92, MDEK95], et Wright [All97]. La totalité des ADLs intègre la notion du composant qui permet de modéliser des unités de calcul ou de communication indépendantes et réutilisables ou d’autres objets du niveau utilisateur tels que des fichiers ou des bases de données. Ces composants sont définis selon l’approche boîte noire où leur structure interne et leur implémentation sont cachées et seule leur interface d’intéraction est visible par les autres composants. Concernant les connexions, nous retrouvons globalement deux visions : la première vision considère une connexion comme un simple lien entre exactement deux composants (c’est le cas notamment de Darwin et Rapide), tandis qu’une deuxième vision introduit une entité spécifique appelée connecteur qui les définitions sont citées dans l’ordre chronologique de leur publication.Le connecteur offre la possibilité, en plus de spécifier le lien de communication qu’il matérialise, de décrire le protocole d’interaction liant les composants qu’il connecte (i.e. le type des messages échangés et l’ordre causal de leur envoi et de leur réception). La considération de l’entité connecteur ou sa non prise en compte n’est cependant pas une caractéristique déterminante pour la puissance d’expression des ADLs. Les connecteurs peuvent être simulés, dans la description, par des composants qui décrivent le protocole d’interaction qui leur correspond.
L’approche DPO
Dans l’autre approche classique appelée DPO (Double PushOut), la règle est de la forme (L, K, R), où K permet de spécifier clairement la partie à préserver après l’application de la règle (au lieu de la déduire par l’opération L ∩ R). Une règle de type DPO est applicable à un graphe G s’il y’a une occurrence de L dans G. Une différence capitale avec l’approche SPO est que l’application de cette règle est subordonnée à une condition supplémentaire appelée la condition de suspension (« Dangling Condition »). Cette condition stipule que la règle ne peut être appliquée que si son application ne va pas entraîner l’apparition d’arcs suspendus. Si les deux conditions d’existence de l’occurrence et d’absence d’arcs suspendus sont réunies, l’application de la règle implique la suppression du graphe correspondant à l’occurrence de Del = (L\K) et le rajout d’une copie du graphe Add = (R \ K). Un exemple de l’application d’une règle de type DPO est donné dans la figure 1.13. On notera que le graphe hôte de cet exemple (noté G2) est un peu différent de celui de l’exemple donné pour l’approche SPO (noté G1). La différence réside dans le fait que le graphe G2 ne contient plus l’arc reliant les noeuds 4 et 3 dans le graphe G1. Ceci est dû au fait que si on maintient cet arc dans G2, la règle R3 ne serait plus applicable parce que son application violerait la condition de suspension.
Les algorithmes de recherche d’homomorphismes de graphes
La vérification de l’existence du graphe mère dans le graphe hôte est traduite mathématiquement par l’existence d’un homomorphisme entre ces deux graphes. Cette problématique est, donc, centrale dans toutes les approches impliquant des grammaires de graphes ou plus généralement la réécriture de graphes. Nous présentons dans cette section, en premier lieu, les bases mathématiques pour la spécification des isomorphismes et homomorphismes de graphes. Ensuite, nous présentons les algorithmes les plus performants qui implémentent la recherche des homomorphismes et étudions leur complexité. Deux graphes sont isomorphes s’il existe une correspondance bijective entre leurs ensembles de nœuds qui préserve la structure. C’est-à-dire que si deux nœuds d’un graphe sont reliés par une arête alors les deux nœuds qui leur correspondent par cette bijection sont aussi reliés par une arête. On obtient, donc, la définition formelle qui suit.
Définition 1 (Isomorphisme de graphes) Deux graphes G1 = (N1, A1) et G2 = (N2, A2) sont isomorphes s’il existe une bijection F ⊆ N1 × N2 telle que pour chaque paire ni , nj ∈ N1 et mi , mj ∈ N2 avec F(ni) = mi et F(nj ) = mj , alors l’arête {ni , nj} ∈ A1, si et seulement si l’arête {mi , mj} ∈ A2. F est, dans ce cas, un isomorphisme de graphes entre G1 et G2. Une généralisation des isomorphismes de graphes est le concept d’homomorphisme de graphes appelé aussi isomorphisme de sous graphes (subgraphisomorphism). La problématique concerne le fait de déterminer si un graphe est isomorphe à un sous graphe d’un autre graphe. On parlera, dans ce qui suit, de morphismes pour désigner le cas général englobant les isomorphismes et les homomorphismes .
Définition 2 (Homomorphisme de graphes) Un homomorphisme d’un graphe G1 = (N1, A1) vers un graphe G2 = (N2, A2) est une injection F ⊆ N1 × N2 telle que pour chaque paire ni , nj ∈ N1, si {ni , nj} ∈ A1, alors {F(ni), F(nj )} ∈ A2. F est, dans ce cas, un homomorphisme de graphes de G1 vers G2. Les définitions précédentes sont données pour le cas de base impliquant des graphes non orientés et non étiquetés. La prise en compte de graphes étiquetés ou flabellés implique des contraintes supplémentaires pour la détection d’isomorphismes ou d’homomorphismes. La préservation de la structure qui impliquait, dans le cas non orienté, l’existence d’une arête entre chaque paire de nœuds dans le graphe hôte dans le cas ou les deux correspondants dans le graphe mère étaient connectés par une arête, implique, dans le cas orienté, l’existence d’un arc entre deux nœuds nh1 et nh2 du graphe hôte si les deux nœuds nm1 et nm2 qui leur correspondent respectivement dans le graphe mère sont reliés par un arc. Les deux arcs doivent en plus respecter le sens. Ceci signifie que si l’arc est dans le sens nm1 vers nm2 alors on doit vérifier l’existence d’un arc de nh1 vers nh2 et vice-versa. On retrouve les deux définitions suivantes pour le cas orienté.
Définition 3 (Isomorphisme de graphes orientés) Deux graphes G1 = (N1, A1) et G2 = (N2, A2) sont isomorphes s’il existe une bijection F ⊆ N1 × N2 telle que pour chaque paire ni , nj ∈ N1 et mi , mj ∈ N2 avec F(ni) = mi et F(nj ) = mj , l’arc (ni , nj ) ∈ A1, si et seulement si l’arc (mi , mj ) ∈ A2.
Définition 4 (Homomorphisme de graphes orientés) Un homomorphisme de G1 = (N1, A1) vers G2 = (N2, A2) est une injection F ⊆ N1 × N2 telle que pour chaque paire ni , nj ∈ N1, si (ni , nj ) ∈ A1, alors (F(ni), F(nj )) ∈ A2. Dans le cas des graphes avec des nœuds flabelés ou des arcs étiquetés, la contrainte sur la préservation de la structure reste nécessaire mais une contrainte supplémentaire aux niveaux des labels est aussi considérée. Dans le cas des graphes avec nœuds flabellés, La fonction F (bijective dans le cas des isomorphismes et injective dans le cas des homomorphismes) est construite de telle manière que deux nœuds nm et nh appartenant respectivement au graphe mère et au graphe hôte avec F(nm) = nh doivent avoir le même label.
Définition 5 (Morphisme de graphes orientés avec des noeuds flabellés) Un isomorphisme (repectivement, un homomorphisme) d’un graphe G1 = (N1, A1, Lab1) vers un graphe G2 = (N2, A2, Lab2) est une bijection (respectivement, une injection) F ⊆ N1 × N2 qui vérifie : 1- pour chaque nœud n ∈ N1 et chaque n÷ud m ∈ N2 tel que F(ni) = mi alors Lab(n) = Lab(m), et 2- pour chaque paire ni , nj ∈ N1 et mi , mj ∈ N2 avec F(ni) = mi et F(nj ) = mj , alors l’arc (mi , mj ) ∈ A2, si et seulement si (respectivement, si) l’arc (ni , nj ) ∈ A1. Dans le cas d’un graphe étiqueté, la contrainte supplémentaire implique, en plus de la préservation de la structure, la préservation des étiquettes des arêtes ou des arcs. C’est-à-dire que l’étiquette d’un arc reliant deux nœud du graphe mère doit être égale à l’étiquette de l’arc reliant les deux nœud correspondants dans le graphe hôte. Cela donne la définition suivante.
Définition 6 (Morphisme de graphes orientés avec arcs flabellés) Un isomorphisme (repectivement, un homomorphisme) d’un graphe G1 = (N1, A1, Etiq1) vers un graphe G2 = (N2, A2, Etiq2) est une bijection (respectivement, une injection) F ⊆ N1 × N2 qui vérifie pour chaque paire ni , nj ∈ N1 et mi , mj ∈ N2 avec F(ni) = mi et F(nj ) = mj : 1- l’arc (mi , mj ) ∈ A2, si et seulement si (respectivement, si) l’arc (ni , nj ) ∈ A1, et 2- Etiq((mi , mj )) = Etiq((ni , nj )).
La définition de morphismes pour les différents types de graphes (non orientés avec noeuds flabellés, non orientés avec arcs étiquetés, avec noeuds flabellés et arcs étiquetés etc . . . ) sont facilement déductibles en combinant les dénitions précédentes. Mais, dans tous les cas, si on considère des graphes quelconques qui n’impliquent des restrictions sur aucun de paramètres du graphe, le problème de savoir si deux graphes sont homomorphes est un problème NP-Complet tandis qu’il est généralement admis dans la littérature que le problème de savoir si deux graphes sont isomorphes est un des rare problèmes NP11 qui ne sont ni dans la classe P 12 ni dans la classe NP-complet 13 . Nous allons présenter dans ce qui suit les algorithmes les plus connus permettant la recherche d’homomorphismes entre les graphes. On commencera par introduire la technique générale de retour en arrière (backtracking) qui constitue l’approche de base pour de la majorité algorithmes qu’on trouve dans la littérature. Ensuite, nous présenterons l’algorithme d’Ullmann qui est la référence des algorithmes de recherche d’homomorphismes dans les graphes. Puis, nous présentons une approche basée sur une recherche des homomorphismes en largeur d’abord. Nous présenterons, en dernier lieu, l’algorithme de détection de cliques (clique detection) qui se base sur la transformation du problème de recherche d’homomorphismes entre deux graphes vers un problème de détection des cliques maximales dans un graphe associé.
Description de l’architecture au niveau application
Le niveau application (A) constitue le plus haut niveau d’abstraction considéré dans notre étude. Il décrit les rôles des participants et les types de données de haut niveau échangées entre les participants ainsi que les exigences et contraintes relatives à la structure dynamique de l’architecture globale. Pour notre exemple, la coopération est basée sur l’échange de données entre des participants, notamment des données d’observation et des données d’analyse, produites périodiquement ou immédiatement après un événement particulier. Une équipe d’intervention d’urgence est ainsi constituée de participants ayant différents rôles : un contrôleur de la mission, plusieurs coordinateurs, et plusieurs sections d’investigateurs. Le contrôleur de la mission gère l’ensemble des coordinateurs et chaque coordinateur dirige une section d’investigateurs. À chaque rôle correspondent les fonctions suivantes :
Un contrôleur a pour fonction de diriger et d’autoriser les actions qui sont déléguées aux coordinateurs. Le contrôleur est l’entité qui supervise toute l’application, il attend des rapports de tous ses coordinateurs qui synthétisent le contexte courant de l’application et l’informent du déroulement de la mission. Le coordinateur est déployé sur une machine xe, il dispose d’un accès à l’énergie permanent et de capacités de communication et de CPU conséquentes.
Selon les actions et les objectifs assignés par le contrôleur, un coordinateur doit diriger ses investigateurs en leur assignant des tâches à exécuter. Il doit également collecter, interpréter et synthétiser les informations reçues des investigateurs et les diuser vers le contrôleur. Les coordinateurs sont eux aussi déployés sur des machines xes.
Les investigateurs ont pour fonction d’explorer le champ opérationnel, d’observer, d’analyser et de faire un rapport décrivant la situation aux coordinateurs qui les contrôlent. Ils sont déployés sur des machines mobiles et disposent, donc, de ressources limitées en énergie et en CPU. Les fonctions assignées aux participants impliquent d’Observer (O) le champ d’investigation et de Rapporter (R) sur ce qui est observé. Les données de retour O sont des données descriptives tandis que les données de retour R sont des données produites et expriment l’analyse de la situation par un investigateur ou un coordinateur. Le contrôleur supervise l’ensemble de la mission, en décidant des actions à exécuter en fonction des objectifs opérationnels et de l’analyse des retours R transmis par les coordinateurs. Il possède sous ses ordres, au moins un coordinateur, et chaque coordinateur possède au moins un investigateur. Un coordinateur est en charge de la partie de la mission qui lui a été assignée par le contrôleur. Il décide localement des actions à exécuter en fonction de l’observation et de l’analyse des données O transmises par les investigateurs. Pour prendre cette décision, le coordinateur peut également utiliser les données R transmises par les investigateurs. Les coordinateurs rapportent l’évolution de la sous mission au contrôleur en utilisant des données de retour de type R.
|
Table des matières
1 État de l’Art
1.1 Introduction
1.2 Description des architectures logicielles
1.2.1 Les ADLs
1.3 Description des architectures logicielles dynamiques
1.3.1 Description de l’évolution dynamique des architectures dans les ADLs
1.3.2 La description des architectures dynamiques par les graphes
1.4 Les grammaires de graphes
1.4.1 La transformation de graphes
1.4.2 Approches basées sur les instructions de connexion
1.5 Les algorithmes de recherche d’homomorphismes de graphes
1.5.1 Technique de retour en arrière (backtracking)
1.5.2 Algorithme d’Ullmann
1.5.3 Algorithme de Messmer & Bunke
1.5.4 Algorithme par détection de cliques
1.6 Conclusion
2 Un Méta-Modèle pour les Architectures Dynamiques
2.1 Introduction
2.2 Description des architectures dynamiques
2.2.1 Description d’une instance de l’architecture
2.2.2 Description des styles architecturaux
2.3 Raffinement et abstraction des architectures
2.3.1 Le cadre formel
2.3.2 Exemple de transformation verticale, raffinement de la composition des Services Web
2.4 Évolution dynamique de l’architecture
2.4.1 Cadre formel
2.4.2 Le protocole de reconguration
2.5 Caractérisation des propriétés architecturales
2.6 Problématiques de validation et de vérication
2.7 Conclusion
3 Cas d’Étude, Activités Coopératives pour les Opérations d’Intervention d’Urgence
3.1 Introduction
3.2 Description de l’architecture au niveau application
3.2.1 Le style architectural correspondant à la phase d’exploration
3.2.2 Le style architectural correspondant à la phase d’action
3.3 Description de l’architecture au niveau middleware
3.3.1 La phase d’exploration
3.3.2 La phase d’action
3.4 Raffinement et Abstraction entre les niveaux application et middleware
3.4.1 Raffinement du niveau application vers le niveau middleware (phase d’exploration)
3.4.2 Abstraction du niveau middleware vers le niveau application (phase d’exploration)
3.4.3 Raffinement du niveau application vers le niveau middleware (phase d’action)
3.4.4 Abstraction du niveau middleware vers le niveau application (phase d’action)
3.5 Description de l’architecture dynamique au niveau réseau
3.5.1 Description au niveau réseau en phase d’exploration
3.5.2 Description au niveau réseau et en phase d’action
3.6 Gestion de l’architecture dynamique
3.6.1 Le niveau application
3.6.2 Le niveau middleware
3.7 Conclusion
4 Algorithmes de Recherche d’Homomorphismes et de Transformation de Graphes
4.1 Introduction
4.2 Définitions et notations
4.3 Algorithmes génériques
4.3.1 Algorithme pour la recherche des homomorphismes de graphes
4.3.2 Application à la transformation de graphes
4.4 Analyse de complexité de l’algorithme générique
4.4.1 Analyse de complexité avec labels constants
4.4.2 Complexité dans le pire cas avec labels variables
4.5 Mesures expérimentales
4.5.1 Génération des entrées pour les expérimentations
4.5.2 Résultats expérimentaux
4.6 Algorithmes basés sur la mise-à-jour des arbres de recherche
4.6.1 Algorithmes de recherche d’homomorphismes
4.6.2 Mise à jour de l’arbre de recherche
4.7 Analyse de complexité, comparaison avec l’algorithme de base
4.7.1 Impact de la suppression de noeuds sur l’arbre de recherche
4.7.2 Impact de la suppression des arcs sur l’arbre de recherche
4.7.3 Impact de l’introduction de noeuds sur l’arbre de recherche
4.7.4 Impact de l’introduction d’arcs sur l’arbre de recherche
4.7.5 Gain obtenu avec le nouvel algorithme
4.8 Conclusion
5 Implémentations et Réalisations
5.1 Introduction
5.2 Structures générales des données
5.2.1 Structures de données pour les noeuds
5.2.2 Structures de données pour les graphes hôtes
5.2.3 Structure de données pour les règles de réécriture
5.3 Première couche logicielle: l’Algorithme de Transformation de Graphes (ATG)
5.3.1 Comparaison de performances avec l’outil AGG
5.4 Deuxième couche logicielle: le Moteur de Transformation de Graphes (MTG)
5.5 Le Protocole de Reconguration de l’Architecture (PRA)
5.6 Conclusion et perspectives
Conclusion
1 Rappel des contributions
2 Perspectives
Annexe
Télécharger le rapport complet
