Partage de données en mode pair à pair sur réseaux mobiles Ad Hoc

Les terminaux légers équipés de modules de communications sans fil, comme les smartphones (iPhone, HTC Magic) ou les subnotebooks (EEE PC), sont désormais des objets de consommation courante. Les utilisateurs de ces terminaux sont maintenant habitués à utiliser des applications collaboratives, accessibles via le web (comme par exemple un wiki [60]) ou par d’autres moyens (comme l’éditeur de texte collaboratif SubEthaEdit [87]). Cependant, pour utiliser ces applications, il est bien souvent nécessaire que les terminaux soient connectés à travers une infrastructure réseau, comme un LAN ou un réseau cellulaire. Les terminaux pouvant communiquer entre eux sans fil, il est possible à plusieurs utilisateurs de collaborer même en l’absence d’infrastructure. Cela nécessite toutefois de modifier la pile réseau car, par défaut, les terminaux n’ont pas la capacité de relayer l’information ce qui est nécessaire en l’absence d’infrastructure. Pour ce faire, plusieurs protocoles de routage ont été créés permettant aux terminaux de se constituer spontanément en réseau. Ces réseaux mobiles ad hoc, appelés aussi MANet  , possèdent donc de nombreuses caractéristiques les différenciant des réseaux filaires classiques [23]. En l’absence d’infrastructure, la gestion du réseau (routage, contrôle de congestion), doit être distribuée. Par ailleurs, la capacité de stockage des terminaux tels que smartphone et netbook est moindre que celle de serveurs ou de stations de travail, et la durée de vie d’une session de travail est limitée par la batterie. Enfin, le réseau est susceptible de voir sa topologie et sa capacité de transport évoluer du fait de la mobilité. Les applications collaboratives pour MANet doivent s’adapter à la topologie dynamique de ceux-ci et pouvoir tolérer une partition du réseau. Par ailleurs, comme les terminaux ont des capacités limitées, ces systèmes doivent limiter leur usage des ressources réseaux et de la mémoire. Enfin, comme il n’existe pas de terminal fiable qui puisse faire office de serveur, il est plus sûr de concevoir les applications de façon entièrement distribuée. Dans cette thèse nous nous intéressons plus particulièrement au problème de partage de données dans les MANets. Une offre de partage de données doit assurer l’accessibilité et la pérennité des données. Pour ce faire, comme dans notre contexte on ne dispose pas de serveur fiable, les données sont répliquées dans le réseau. Cela nécessite donc d’en assurer la cohérence, la sécurité et la confidentialité, ainsi qu’une politique de remplacement de cache. Un service de localisation, permettant de retrouver une réplique à partir de l’identifiant d’une donnée, et un service de recherche sont aussi nécessaires. Enfin, pour pouvoir gérer la mobilité des terminaux, nous avons besoin d’un algorithme capable de classifier les terminaux de mobilité similaire en grappes (clustering).

Exemple : un wiki distribué nomade

Dans une école, chaque élève est muni d’un terminal mobile léger et solide, équipé de connectivité WiFi. Durant leur scolarité les élèves sont amenés à faire des exposés, des fiches de lectures ou des comptes rendus d’expérience. Ils partagent leurs résultats au sein d’un wiki accessible par tous les élèves et administré par les professeurs. Chaque année des excursions et des voyages scolaires sont organisés, au musée ou en classe verte. Les élèves peuvent bien sûr continuer à travailler individuellement, mais il est souhaitable qu’ils puissent continuer à collaborer même hors de portée du serveur.

Pour cela, il faut tout d’abord des protocoles de communication permettant aux terminaux d’interagir en absence d’une infrastructure réseau, ce que permettent les protocoles de routage de réseaux mobiles ad hoc. Le wiki doit ensuite être déployé sur les terminaux des élèves. Dans ce contexte de mobilité, il n’existe pas de terminal fiable auquel tous les utilisateurs seraient sûrs de pouvoir être connectés. Une architecture Client/Serveur est donc proscrite, car elle engendrerait trop de problèmes d’accessibilité. Par ailleurs, les terminaux sont susceptibles de disparaître et de réapparaître par intermittence. Enfin, la plupart des terminaux n’ont sans doute pas les ressources nécessaires pour héberger l’ensemble des articles. Il faut donc, pour fournir ce service de wiki, créer un système de partage de données pair à pair, tenant compte des ressources des terminaux ainsi que de leur mobilité.

La majorité des systèmes de partage de données existants ne sont pas conçus pour les systèmes mobiles et ne prennent donc pas en compte les caractéristiques spécifiques des MANets. Il existe cependant des systèmes de partages de données pour MANets. La majorité de ces systèmes sont spécialisés pour des applications spécifiques, comme des réseaux de capteurs avec une modification périodique des données, ou des groupes d’intervention de crise fortement connectés. Ils ne conviennent donc pas non plus à notre situation. Enfin, certains systèmes plus généralistes existent, tels que XMiddle [69] ou adHocFS [14] mais ils n’offrent pas toutes les fonctionnalités que nous souhaitons.

Informations sémantiques

Nous proposons d’utiliser des informations sémantiques qualifiant le contenu sémantique des données et les centres d’intérêts des utilisateurs afin d’offrir une gestion intelligente des données. Dans de nombreuses applications collaboratives, comme par exemple Flickr [1], les motsclés sont utilisés pour faire de la recherche de données, de la classification et de la recommandation [70]. Nous voulons donc décrire les intérêts des utilisateurs par des mots-clés et utiliser ces informations pour calculer l’intérêt d’un utilisateur pour une donnée, et prédire ses accès. Dans le cadre d’une communauté de taille restreinte, partageant des documents avec des annotations sémantiques, un tel calcul peut être appliqué sur l’ensemble, ou au moins une grande partie des données. Une telle solution ne peut cependant pas être généralisée à tous les systèmes de partage de données. Dans le cas d’une mémoire partagée distribuée, la donnée étant un mot-mémoire, on ne peut pas lui attribuer d’information sémantique ; un tel système serait par ailleurs trop lourd pour ce type de système. A l’autre bout du spectre, dans le cadre d’un système de cache web, la quantité d’informations disponibles est trop importante pour qu’on puisse tout analyser, même s’il existe des systèmes de caches sémantiques. Enfin, pour déterminer les intérêts des utilisateurs, nous examinons leurs accès aux données afin d’en extraire des motifs s’ils existent. Nous évaluons notre système sur une base d’accès d’utilisateurs à des documents. Nous avons tout d’abord examiné les premiers accès pour lesquels nous avons déterminé des mots-clés décrivant les utilisateurs avant de vérifier nos prédictions sur le reste de la base.

Gestion de la mobilité : création de groupes de mobilité

Nous proposons un algorithme de création de groupes de mobilité stables dans le temps qui, en utilisant les informations des tables d’un algorithme de routage pro-actif, ne nécessite aucun échange de message. Dans un MANet, un développeur d’application est amené à prendre en compte la mobilité des terminaux :

– Peut-on prévoir une partition à venir et répliquer un service pour en maintenir la disponibilité ?
– Peut-on prévoir les terminaux se déplaçant de concert, afin de mettre en place des algorithmes collaboratifs ?

Bien que les terminaux soient mobiles, on peut souvent compter sur l’apparition de groupes stables, c’est à dire dont les terminaux restent en communication pendant un certain temps, ceci étant dû à la nature collaborative des applications. Dans notre exemple, la classe se sépare en plusieurs groupes d’activités, chaque groupe restant à portée de communication afin de travailler ensemble. Comme nous le verrons ci-après divers algorithmes ont été proposés pour gérer la mobilité au sein d’un MANet. Ces algorithmes utilisent différentes métriques pour définir la stabilité d’un lien : prédiction de trajectoire en utilisant des coordonnées GPS, détection de boucle au sein du graphe de routage et distance moyenne. Notre algorithme prédit la stabilité d’un lien entre deux terminaux en examinant son évolution dans le temps : si un lien était stable dans le passé, alors il le sera dans le futur ; si un lien était volatil dans le passé, alors on ne le considère pas comme stable. Ceci est fait en utilisant des informations issues des tables de routage. Nous avons fait ce choix d’utiliser des informations inter-couches afin d’être plus efficace : en choisissant un protocole de routage pro-actif, qui maintient les routes, nous savons quels terminaux peuvent être contactés sans avoir à échanger de messages. Pour créer des grappes, trois types d’approche sont envisagés dans l’état de l’art. Le premier type d’approche consiste à créer des grappes au sein d’un groupe dense de terminaux : le problème est de sélectionner un ensemble de pairs stables (les têtes de grappes) pour placer sur chacun un service, puis d’agréger les pairs par proximité autour de ces têtes de grappes, comme dans [113], où ce choix se base sur les capacités (batterie, stockage, des pairs). Ces techniques ne prennent pas en compte la possibilité de partition. Le second type d’approche consiste à prédire les partitions dans le réseau en se basant sur les positions passées des terminaux, avec des informations GPS ou les informations de routages, comme proposé dans [24], [103] ou [97]. Ces techniques sont coûteuses en calcul car elles supposent de reconstruire les trajectoires des terminaux ; elles nécessitent, par ailleurs, l’échange d’informations de position. Enfin, le troisième type d’approche, dans laquelle nous nous inscrivons, est de créer des groupes stables entre terminaux. Dans [103], ceci est fait en calculant la distance moyenne aux autres pairs dans le graphe de routage, tandis que dans [38], l’algorithme cherche les boucles dans le graphe de routage. En terme de surcharge réseau, notre algorithme est optimal, puisqu’il ne nécessite aucun échange de message. Le calcul effectué est une comparaison de deux listes, ce qui est moins coûteux que la recherche de boucle dans le graphe de routage, et aussi complexe que le calcul de distance moyenne. Notre algorithme passe donc à l’échelle grâce au fait que nous nous appuyons sur l’implémentation du protocole OLSR [22].