PROTOCOLE D’APPARTENANCE DE GROUPE DANS LES RESEAUX AD HOC

Télécharger le fichier pdf d’un mémoire de fin d’études

Exemples d’application avec mobilité physique

Les applications mobiles ayant recours aux réseaux de communication sans fil couvrent un très large spectre, incluant par exemple, les applications militaires, les applications véhicule-à-véhicule, ou des applications dans le domaine de la santé concernant la surveillance à distance de personnes. Certains proj ets ont porté sur le développement d’applications, telles que des guides de tourisme avec des dispositifs mobiles [GUIDE], [CYBERGUIDE], des applications véhicule-à-véhicule[COMeSafety], [PReVENT], [NOW], [Coopers], [HIDENETS], des services de sauvegarde [SUMO], [MoSAIC], des garanties de continuité de connexion pendant le déplacement d’unutilisateur [OpenMobileIS], etc.
A titre illustratif, prenons deux exemples de système mobile.
Le premier est une application véhicule-à-véhicule du domaine automobile dont les communications se font en mode ad hoc : la boîte noire répartie. Elle a été développéensdale cadre du projet européen HIDENETS (Highly Dependable ip-based Networks and Services). Le principe de cette boîte noire est identique à ce lle d’un avion. Elle enregistre à intervalle régulier des informations datées relatives à la vitesse, au freinage, à la position du conducteur, à l’environnement du véhicule, etc. sous forme de données. Dans cette application, les données sont répliquées temporairement sur des véhicules voisins du même réseau ad hoc qui sont croisés sur les routes et indéfiniment sur desserveurs dans le cas d’un accès à une infrastructure fixe. En cas d’accident d’un véhicule, les données pourront être récupérées à partir des autres véhicules et des serveurs.

Un autre exemple est une application qui s’inspire des guides touristiques et qui a été développée au cours d’un projet [GUIDE]. Elle utilise un serveur d’infrastructure. Un touriste qui visite un monument est équipé d’un assistant personnel numérique à son entrée sur le site. En se promenant dans les différents lieux du monument, il est guidé à l’aide des serveurs présents dans ces zones et peut obtenir certaines informations auxquelles il s’intéresse par interaction. Ces serveurs sont associés à des dispositifs spécifiques répartis sur le site qui détectent la présence des touristes et permettent insia de leur fournir les informations touristiques relatives à leur position.

Caractéristiques des systèmes mobiles

D’un point de vue théorique et technologique, les applications mobiles sont plus complexes que leurs homologues fixes car elles impliquent non seulement des aspects d’applications distribuées (par exemple, le parallélisme, la communication, la latence) mais aussi des caractéristiques propres aux systèmes mobiles. Les systèmes informatiques mobiles, et en particulier les systèmes mobiles ad hoc, se distinguent des systèmes distribués « traditionnels » par les aspects suivants : la dynamicité de la structure du système, la communication par diffusion, la dépendance vis-à-vis du contexte.

La dynamicité de la structure du système

Le nombre de nœuds dans un système mobile n’est pas fixe : il varie avec le temps. Cela est dû aux opérations (abstraites) dynamiques de création, suspension, disparition des nœuds (voir la Figure 2.a). C’est la conséquence du fait que les utilisateurs peuvent, entre autres, allumer/éteindre les dispositifs, les changer de mode d’opération pour réduire les coûts de connexion, économiser la batterie ou éviter des ruptures inopinées de connexions. En plus de cela, la liberté de mouvement des nœuds modifie constamment la connectivité car ils sont à même de joindre ou quitter le système de manière spontanée : la topologie du système n’est pas stable. Cependant, les changements topologiques peuvent être contraints par un modèle de mobilité : par exemple, si on veut étudier le comportement d’un système mobile composé de véhicules automobiles communicants, il faut considérer qu’ils se déplacent sur une route dans une ou deux directions à une vitesse limitée.

La communication avec les nœuds inconnus dans le voisinage local

Dans un réseau mobile ad hoc, une communication « naturelle » est la communication par diffusion dans le voisinage. En général, elle ste utilisée comme une brique de base pour la découverte du voisinage dans les applications et les services mobiles, par exemple, le service de découverte de nœuds pour les protocoles d’appartenance de groupe ou la découverte de routes dans les protocoles de routage. Dans ce type de communication, un nœud émet un message à son voisinage et tous les nœuds qui sont dans sa portée de transmission peuvent recevoir le message (voir la Figure 2.b). Comme la topologie du système n’est pas connue, l’émetteur ne connaît pas a priori le nombre et l’identité des récepteurs potentiels .N’importe qui à portée de transmission de l’émetteur peut recevoir et traiter le message.

La dépendance du contexte

Dans un système, chaque nœud devrait avoir une définition explicite du contexte, des politiques pour le mettre à jour et réagir à ses changements. Le contexte inclut tout attribut approprié et détectable d’un dispositif, de ses interactions avec les autres dispositifs et de son environnement proche à tout instant (voir la Figure 2.c). Par exemple, le contexte peut être des informations sur les dispositifs eux-mêmes comme la mémoire, des informations récoltées au moyen de capteurs physiques comme la localisation, le temps, la vitesse de déplacement, ou encore des informations sur l’environnement opérationnel comme les paramètres du réseau, la bande passante, la latence, la topologie de connectivité, etc. En conséquence, du fait de la mobilité, le contexte est constamment en évolution. Il est donc important que les applications mobiles s’aperçoivent de ces changements et s’y adaptent.
Ces caractéristiques des systèmes mobiles posent de nouveaux défis pour le développement des applications mobiles en général, et pour la modélisation en particulier, sujet qui sera abordé dans le paragraphe suivant.

Modélisation de systèmes mobiles

La modélisation de systèmes mobiles doit prendre encompte non seulement des aspects comportementaux comme dans les systèmes classiques, mais aussi des aspects topologiques et contextuels. Divers travaux ont été effectués concernant la modélisation des systèmes mobiles. Ils concernent : la représentation de l’architecture de systèmes, les modèles de mobilité, les formalismes comportementaux incluant la mobilité et/ou la modélisation de contexte.

Représentation de l’architecture du système

Si on ne considère que la structure dynamique d’un système mobile, on pourrait argumenter que les graphes et les algorithmes de graphes constituent un cadre convenable de modélisation. Cependant, de tels formalismes ne capturent pas les aspects comportementaux des applications. A l’origine, les formalismes de graphes ont été largement utilisés pour spécifier des architectures logicielles dynamiques [Le Métayer 98] et ils peuvent être appliqués aussi pour modéliser la topologie d’un système mobile. Par exemple, dans [Nickerson 05], les graphes sont utilisés pour abstraire les relations spatiales et les distances de communication entre les nœuds mobiles. Les arêtes montrent une liaison physique (connecté/déconnecté), ainsi que la latence de communication (le temps pour qu’un message soit délivré). L’application de ces approches est discutée dans des situations mobiles, comme la mobilité dans un environnement réseau ad hoc, par exemple pour définir un algorithme pour la planification des routes.
Les algorithmes de transformation de graphes peuvent être appliqués pour spécifier l’évolution du contexte d’un système mobile. Le travail dans [Lei et Zhang 05] applique les théories des graphesconceptuels [Baget et Mugnier 02] pour modéliser les contextesmobiles. Un graphe conceptuel est un graphe étiqueté qui contient deux classes de sommets : une pour représenter les objets contextuels et l’autre pour les relations entre les objets. Des règles de transformation de graphe sont définies pour ajouter/supprimer des sommets dans un graphe et sont utilisées pour indiquer comment le contexte du système évolue. Les auteurs ont défini quatre règles à appliquer dans un système mobile : insertion, suppression, activation et désactivation des services. Ces règles ont été utilisées dans l’implémentation d’un prototype de guide touristique portable de musée.
D’autres langages graphiques permettent de décrire l’architecture d’un système mobile. Le langage graphique CML (Context Modelling Language), présenté dans [Henricksen et Indulska 06], permet aux développeurs de spécifieret d’explorer des exigences contextuelles. Ce langage fournit des primitives pour définir les types des informations contextuelles, leurs classifications, les méta-données quantitatives et les dépendances entre les types des informations. Un exemple simple est fourni dans la Figure 3. Le premier diagramme indique que l’entité Person peut être localisée alternativement dans plusieursélémentsLocation. Le deuxième diagramme indique que Person participe, au maximum, à une activité à un instant donné.
Figure 3. Un exemple d’utilisation de CML
Le langage UML constitue aussi un cadre approprié pour modéliser l’architecture d’applications dépendantes du contexte de part sa structure générique et ses différents diagrammes. Un exemple l’illustre dans [Sheng et Benatallah 05]. Ce travail se focalise sur un méta-modèle pour modéliser les Services Web en modifiant les méta-classes de UML.

Modèles de mobilité

En plus de leur utilisation pour modéliser l’architecture d’un système, les graphes peuvent être utilisés pour modéliser la mobilitésdenœuds. Par exemple, dans [Tian et al. 02], les auteurs utilisent les graphes pour représenterdes contraintes sur les déplacements qui sont imposées par les infrastructures. Les sommets du graphe représentent des lieux que les utilisateurs peuvent visiter, par exemple, les monuments d’un centre ville. Les arêtes représentent les connexions entre ces lieux, par exemple, les moyens de transport ou les rues. Le déplacement d’un nœud suit généralement le chemin le plus court entre deux sommets.
Cependant, l’application des formalismes de graphes aux modèles de mobilité est parfois trop abstraite et devient complexe si on veut détailler certains paramètres du mouvement d’un nœud tels que la position, la vitesse, etc. Afin d’ avoir une vue cohérente entre les différents paramètres qui caractérisent la mobilité d’un nœud, des modèles spécifiques ont été conçus. Leur utilisation principale se situe dans le domaine de l’évaluation de protocoles.
Les modèles de mobilité ont pour objectif de décrire des configurations de mouvements des dispositifs/nœuds mobiles. De plus, ils montren t comment la localisation, la vitesse et l’accélération évoluent au cours du déplacement desnœuds. Il est donc nécessaire que les modèles émulent le plus précisément possible les nfigurationsco réelles. Dans les travaux de recherche sur les protocoles de communication, des modèles de mobilité ont été proposés. Ils peuvent être classés dans quatre catégories [Bai alet. 03] : les modèles aléatoires, les modèles avec dépendances temporelles, les modèles avec dépendances spatiales et les modèles avec restrictions géographiques.
Concernant les modèles aléatoires, un exemple simple est Random Waypoint Mobility [Broch et al. 98]. Les nœuds se déplacent librement , sans aucune restriction. La destination, la vitesse et la direction sont choisies aléatoirementet indépendamment des autres nœuds.
Pour les modèles avec des dépendances temporelles, comme Gauss-Markov Mobility [Liang et Haas 99] ou Smooth Random Mobility [Bettstetter 01], des contraintes pour la vitesse, l’accélération et le taux de changement dedirection sont introduites. La vitesse d’un nœud dépend donc de la vitesse précédente et par conséquent, les vitesses d’un nœud aux différents instants sont corrélées.

Dans les modèles avec des dépendances spatiales, Reference Point Group Mobility [Hong et al. 99] par exemple, la mobilité d’un nœud peut être influencée par les paramètres de ses voisins, ou de son leader, ce qui mène à une corrélation spatiale.
Dans certaines applications, nous avons pu constater que le mouvement d’un nœud est contraint par des restrictions géographiques, par exemple, le déplacement de véhicules sur une autoroute ou celui de personnes dans un bâtiment. D es travaux récents tiennent compte de ces caractéristiques et intègrent des chemins et des obstacles dans les modèles de mobilité comme dans Freeway Mobility, Manhattan Mobility [Bai et al. 03].

Les formalismes comportementaux incluant la mobilité

Les travaux présentés dans les paragraphes 3.1 et .32 ne traitent que de l’aspect topologique des systèmes, et de l’évolution de cett topologie. Afin de concevoir des applications mobiles, il faut pouvoir exprimer leur aspect comportemental. Dans la littérature, l’utilisation de certains formalismes traditionnels pour exprimer le comportement des applications a été étendue pour prendre en comptea l mobilité. Nous présentons ici les formalismes les plus connus avec les mobile ambients, les extensions d’UML, Mobicharts et MobileUNITY.
Les mobile ambients. Les algèbres de processus qui possèdent une notionexplicite de localisation, sont capables de couvrir à la fois le s aspects comportementaux et structurels. Nous pouvons citer des travaux tels que pi-calculus [Milner et al. 92], join-calculus [Fournet et Gonthier 96], LLinda[De Nicolas et al. 97], Obliq [Boudol 92], spi-calculus [Abadi et Gordon 97]. Dans ce domaine, le calcul des ambients, « ambient calculus » [Cardelli et Gordon 00], est probablement le plus connu. Par définition, unambient est une place bornée, « une boîte », où des calculs s’exécutent. Les ambients peuvent être emboîtés, ce qui conduit à une hiérarchie des localisations. Cette hiérarchieest modifiable par l’action de processus qui peuvent créer, détruire ou déplacer les ambients. esL auteurs ont défini des primitives pour cela, comme les primitives d’entrée et de sortie d’un ambient. La Figure 4 illustre l’effet de la primitive d’entrée in, en représentant graphiquement les ambients par des boîtes. La primitive in indique que l’ambient n entre dans l’ambient m. L’ambient n change donc de niveau hiérarchique pour devenir un sous-ambient de m. Ensuite, au sein de n, l’exécution se poursuit avec le processus P|Q.
Le calcul des ambients possède une sémantique formelle. De plus, des propriétés déclaratives peuvent être exprimées en utilisant eunlogique avec des modalités spatiales et temporelles [Cardelli et Gordon 00 b]. En pratique, le calcul des ambients est plus conçu pour des études théoriques que pour spécifier des systèmes. Il offre un ensemble minimal de primitives de base ce qui rend l’encodage d’une application réelle relativement lourd. Le calcul des ambients peut plutôt être utilisé comme un cadre de base pour des formalismes de plus haut niveau. Il est toutefois important de noter que la vue sous-jacente de la mobilité n’est pas appropriée à toutes les applications. Comme indiqué précédemment, il se focalise sur l’entrée et la sortie de domaines « administratifs » qui sont organisés de manière hiérarchique. Cette vue est adéquate pour exprimersoit la mobilité logique, soit la mobilité physique depuis un point d’accès de l’infrastructure à un autre. Cependant, elle ne nous paraît pas adaptée pour prendre en compte la dynamique d’un réseau ad-hoc.

Le principe des ambients a fortement inspiré les auteurs travaillant sur la définition de formalismes de haut niveau utilisables par des ingénieurs.
Les extensions d’UML . Les extensions d’UML proposées dans [Baumeister et al. 03] et [Grassi et al. 04] ont une définition stéréotypée de la localisation qui ressemble au concept des ambients. Les différents travaux sur les extensions diffèrentes sur la manière dont elles influent sur les notations de UML.
L’extension proposée dans [Baumeister et al. 03] modifie la syntaxe des diagrammes d’activités et de séquence, afin de pouvoir exprime des scénarios contenant les aspects mobile et comportemental. La mobilité des objets est décrite par des descriptions d’états placées dans une boîte en dessous du nom de l’objet, et la localisation de l’objet est indiquée par l’affectation [atLoc = localisation] (voir la Figure 5).
Quand un objet se déplace, il modifie son état et li faut créer une nouvelle boîte. Un nouveau type de message avec le stéréotype <<become>> permet de représenter les changements de localisation. Par exemple, dans la Figure 5, les messages board(), deplane() et fly() sont des artifices de modélisation pour exprimer la mobilité (ou le changement de localisation) des objets ps et ap. Par contre, le message notice() exprime une communication entre les objets, comme dans UML standard.

Le travail présenté dans [Grassiet al. 04] conserve les notations inchangées pour être compatible avec le standard UML 2.0. Des diagrammes de déploiement sont utilisés pour indiquer les configurations potentielles de localisations et la logique de la mobilité est modélisée par des diagrammes de type statechart, cette logique étant gardée séparément de la logique de l’application.
Aucune de ces extensions proposées ne fournit de sémantique formelle.
Mobicharts [Acharya et al. 04] est un cadre plus formel pour la modélisation des systèmes mobiles. Il fournit une notation graphique basée surObjectChart [Ernst et al. 95] qui est enrichie d’une notion de localisation. Cette notion s’inspire aussi de celle utilisée dans le concept des ambients. Mobicharts a été essentiellement utilisé pour modéliser des services pour la mobilité logique, comme la réplication ou al migration de tâches. Concernant la mobilité physique des dispositifs, Mobicharts se limite à décrire des fonctionnements en mode infrastructure avec des zones prédéfinies pour le déplacement des nœuds où une zone est définie comme une boîte. Comme la notation graphique ne peut pas fournir une sémantique précise, une spécification formelle des services a été donnée dans le langage de spécification RAISE [Nielsen et Geogre 98].

Les formalismes précédents, tous inspirés des ambients, considèrent une abstraction du mouvement en termes d’entrée et de sortie de boîtes. Parmi les formalismes offrant une autre vue de la mobilité, nous pouvons mentionnerMobileUNITY [Roman et McCann 98] qui est une extension du langage de programmation Unity [Chandy et Mirsa 98]. Dans MobileUNITY, chaque processus a une variable qui modélise sa localisation, par exemple, la variable peut contenir les coordonnées physiques. Le mouvement est alors abstrait par l’attribution de valeurs aux variables. Des primitives de coordination sont proposées afin de faciliter la représentation des interactions entre les processus mobiles. Par exemple, la réception d’un message diffusé localement peut êtrereprésentée en utilisant une instruction réactive gardée par un prédicat sur les localisations de l’émetteur et du récepteur. MobileUNITY a une spécification formelle et une logique de preuve pour permettre la modélisation et la vérification des mouvements, des partages de données et des synchronisations dans un contexte mobile.

Table des matières

INTRODUCTION GÉNERALE
CHAPITRE 1 . CADRE DES TRAVAUX ET ETAT DE L’ART
1. Introduction
2. Introduction aux systèmes mobiles
2.1. Définition et classes de systèmes mobiles
2.2. Exemples d’application avec mobilité physique
2.3. Caractéristiques des systèmes mobiles
2.3.1. La dynamicité de la structure du système
2.3.2. La communication avec les noeuds inconnus dans le voisinage local
2.3.3. La dépendance du contexte
3. Modélisation de systèmes mobiles
3.1. Représentation de l’architecture du système
3.2. Modèles de mobilité
3.3. Les formalismes comportementaux incluant la mobilité
3.4. Modélisation du contexte
3.5. Discussion
4. Test des systèmes mobiles
4.1. Positionnement du test parmi les techniques de vérification
4.2. Détermination des niveaux de test
4.2.1. Détermination des niveaux de test dans les applications traditionnelles
4.2.2. Détermination du niveau de test dans les systèmes mobiles
4.3. Sélection de cas de test
4.3.1. Test structurel
4.3.2. Test fonctionnel
4.4. Problème de l’oracle
4.4.1. Solutions classiques pour l’oracle
4.4.2. Le problème de l’oracle dans les systèmes mobiles
4.5. Test et représentations graphiques de scénarios
5. Plate-forme expérimentale
5.1. Discussion sur l’environnement de test des applications mobiles
5.2. Simulateur de réseau de communication
5.3. Simulateur de contexte
5.4. Exemples de plates-formes expérimentales
5.4.1. Exemple dans le domaine de la santé
5.4.2. Exemple dans le domaine des véhicules intelligents
5.4.3. Un exemple d’émulateur
5.4.4. Flying Emulator : simuler la mobilité physique par la mobilité logique
5.5. Discussion des environnements de simulation
6. Conclusion
CHAPITRE 2 . CAS D’ETUDE : UN PROTOCOLE D’APPARTENANCE DE GROUPE DANS LES RESEAUX AD HOC
1. Introduction
2. Présentation du GMP étudié
2.1. Principe du GMP
2.2. Propriétés attendues du GMP
2.3. Algorithme du GMP
2.4. Code source du GMP
3. Analyse du GMP
3.1. Analyse de la spécification
3.1.1. Analyse des propriétés
3.1.2. Analyse du calcul de la Distance de Sécurité
3.1.3. Analyse de la spécification détaillée du GMP
3.2. Analyse de l’implémentation
3.2.1. Comparaison avec la spécification détaillée
3.2.2. Recherche de fautes dans l’implémentation
4. Test du GMP
4.1. Plate-forme de test
4.2. Paramétrage des expériences de test
4.3. Résultats de test
5. Discussion à l’issue de l’étude de cas
5.1. Conclusions sur le GMP étudié
5.2. Enseignements tirés de l’étude de cas
5.2.1. Discussion sur la plate-forme de test
5.2.2. Modélisation des interactions dans les systèmes mobiles
5.2.3. Des stratégies passives aux stratégies actives de test
6. Conclusion
CHAPITRE 3 . APPROCHE DE TEST BASEE SUR DES DESCRIPTIONS DE SCENARIOS
1. Introduction
2. Vue générale de l’approche de test basée sur les scénarios
3. Extensions proposées pour les langages de scénario dans le cadre de systèmes mobiles
4. Exemples de scénarios utilisant nos extensions
4.1. Exemples de scénarios d’exigence
4.1.1. Illustration sur le GMP
4.1.2. Illustration sur la boîte noire
4.2. Exemples d’objectifs de test
4.2.1. Illustration sur le GMP
4.2.2. Illustration sur la boîte noire
4.3. Exemple de cas de test
4.4. Discussion
5. Traitements automatisés des descriptions de scénario
5.1. Traitements associés aux scénarios d’exigence et aux objectifs de test
5.2. Aide à l’implémentation des cas de test
6. Conclusion
CHAPITRE 4 . GRAPHSEQ : UN OUTIL D’APPARIEMENT DE GRAPHES POUR L’EXTRACTION DES MOTIFS DE MOBILITE
1. Introduction
2. Comparaison de deux graphes
2.1. Définition de graphe
2.2. Définition d’homomorphisme de graphes
2.3. Discussion de nos besoins
2.4. Outil retenu
2.5. Comparaison de deux graphes avec l’outil
3. Principe de GraphSeq
3.1. Forme des solutions recherchées par GraphSeq
3.2. Propriétés attendues
4. Algorithme de GraphSeq pour un ensemble fixe de noeuds dans les motifs
4.1. Structure de contrôle
4.2. Détail des étapes de l’algorithme
4.2.1. Exemple illustratif
4.2.2. Création de matchs partiels de profondeur 1
4.2.3. Extension des matchs partiels
5. Algorithme avec les créations/disparitions de noeuds
5.1. Structure de contrôle
5.2. Détail des étapes de l’algorithme
5.2.1. Exemple illustratif
5.2.2. Prétraitement des graphes motifs
5.2.3. Impact sur la construction des matchs partiels de profondeur 1
5.2.4. Impact sur l’extension d’un match partiel
6. Conclusion
CHAPITRE 5 . GRAPHSEQ : COMPLEXITE, VALIDATION ET EXPERIMENTATION
1. Introduction
2. Analyse de complexité de GraphSeq
2.1. Analyse de complexité de l’algorithme de recherche d’homomorphismes
2.1.1. Le meilleur cas
2.1.2. Le pire cas
2.2. Analyse de complexité de GraphSeq
2.2.1. Complexité des fonctions auxiliaires
2.2.2. La complexité de l’algorithme de GraphSeq
2.3. Discussion
3. Validation de GraphSeq
3.1. Analyse des exemples illustratifs
3.2. Validation par un outil
4. Application de GraphSeq
4.1. Connexion à un simulateur de mobilité
4.1.1. Principe
4.1.2. Modèle des expérimentations
4.1.3. Expérimentation avec le modèle Freeway
4.1.4. Expérimentation avec le modèle RPGM
4.1.5. Discussion
4.2. Application de GraphSeq au cas d’étude GMP
5. Conclusion
CONCLUSION
BIBLIOGRAPHIES

Télécharger le rapport complet