Algorithme de création de groupes stables

Algorithme de création de groupes stables

Dans les MANets, des événements tels que la disparition ou l’apparition de pairs et la partition du réseau, surviennent de manière fréquente.C’est un problème quand on veut développer des applications distribuées pour réseaux mobiles :– on ne peut pas considérer que l’ensemble des terminaux participants vont rester présents, – on ne peut donc pas considérer la disparition d’un terminal comme un événement ex- ceptionnel et permanent.Dans ce chapitre nous présentons donc notre approche pour gérer la mobilité.Nous voyons tout d’abord nos hypothèses de travail concernant la nature du réseau et le comportement des pairs le constituant. Nous motivons ensuite le choix de conception d’utiliser des informations inter-couches et présentons les éléments du protocole de la couche réseau avec laquelle notre algorithme interagit, OLSR [22].Dans les sections suivantes, nous présentons les structures de données utilisées puis l’al- gorithme lui même, illustré par un exemple, avant de discuter du paramètrage de cet algorithme.Enfin, nous détaillons notre méthode de validation avant de présenter nos résultats puis de conclure. Dans cette proposition, nous faisons différentes hypothèses sur le comportement des utili- sateurs, les protocoles réseaux utilisés par les terminaux, ainsi que sur les communications. Nous les présentons dans cette section. Notre proposition est destinée à des utilisateurs piétons, qui collaborent via des terminaux mobiles équipés de cartes wifi et de protocoles réseaux ad hoc. Ils se déplacent en groupe et leur organisation peut être décrite par le modèle de mobilité Reference Point Mobility Group (RPGM) [41]. Leur vitesse varie entre 0 km/h et 4km/h.de communication du RP, comme illustré par 5.1. Ce modèle est utilisé dans d’autres travaux proposant des algorithmes de construction de groupes mobiles, comme [43].Par construction, la topologie du réseau est donc confinée dans un disque de 2 portées de communications de large, décrit par deux terminaux à portée maximale de communication du RP et situés à des positions diamétralement opposées . Cependant, comme il peut être plus économique d’effectuer deux communications de courte portée plutôt qu’une longue, les routes construites ne sont pas nécessairement de longueur inférieure à 2.

Protocoles réseaux et communications

Les terminaux des utilisateurs sont équipés de carte wifi utilisant 802.11b, la norme wifi la plus couramment utilisée. La portée de communication maximale théorique en extérieur est de 100m.Les communications sont symétriques : à un instant, si A est à portée de communication de B, alors B est à portée de communication de A.Nous faisons l’hypothèse d’un protocole de routage pro-actif, qui maintient les routes en l’absence de messages échangés et nous avons basé nos expérimentations sur le protocole OLSR [22]. Celui ci est présenté plus en détail dans la section suivante. Nous verrons notamment que OLSR construit des groupes de terminaux dont les communications sont symétriques.Cette hypothèse est nécessaire car ici l’algorithme proposé utilise des informations inter- couche, issues de la couche de routage. Dans la section suivante, nous expliquons ce choix.L’algorithme proposé cherche à construire des groupes de terminaux, les voisins, stables dans le temps.Nous définissons un groupe stable comme un groupe de terminaux capables de communi- quer en continu sur une période.En d’autres termes, pour être des voisins stables à t, A et B doivent avoir été en contact depuis au moins δ On préfère habituellement (e.g. pile OSI) maintenir chaque tâche différente dans un couche séparée, afin d’être modulable. Cependant l’utilisation d’information inter-couche (cross- layering), permet d’optimiser l’utilisation des ressources en évitant de reconstruire plusieurs fois la même information.Cette technique est très utilisée dans les protocoles pour réseaux mobiles ad hoc.

C’est le cas par exemple de Chapar [52] le système d’événements développé pour Trans- humance [81]. Il utilise les nœuds MPRs d’OLSR, que nous présentons plus bas, comme distributeurs d’événements en se basant sur leur propriété d’accessibilité par les autres membres du réseau.Plusieurs algorithmes de création de grappes, que nous avons présentés dans l’état de l’art, utilisent la puissance du signal reçu, une information issue de la couche physique, pour déterminer la distance à l’émetteur.Dans nos travaux, nous proposons un protocole de niveau applicatif qui interagit avec la couche de routage OLSR pour y récupérer des informations de présence. Dans un réseau, un protocole de routage permet de choisir un chemin, c’est à dire une suite de nœuds du réseau, pour acheminer un paquet entre la source d’un message et son destinataire.Notre travail s’inscrit dans les travaux de recherche menés lors du projet ANR Transhu- mance, destinés à produire un intergiciel pour MANets.La proposition d’un nouvel algorithme de routage ne relevant pas du projet Transhumance, les membres du projet ont été amenés à choisir un algorithme de routage, le protocole et son implantation se devant d’être complètement validés.Bien que de nombreux algorithmes aient été proposés dans la littérature, la plupart n’offrent pas d’implantation et sont validés par simulation uniquement. Ceux qui ont été implantés l’ont souvent été à des fins de prototypages, et ne sont pas utilisables. Seuls les protocoles DSR [49], AODV [83] et OLSR [22] bénéficient de véritables implantations, et le choix de l’équipe Transhumance s’est porté sur OLSR du fait de sa solide implantation OLSR-Unik [65], et de sa communauté active, notamment sur la liste IETF-manet.OLSR est un protocole de routage pro-actif à état de lien proposé par le projet HIPER- COM-INRIA en 2001. Dans un protocole à état de lien, comme OSPF [76] – qu’on oppose aux protocoles à vecteurs de distances, comme RIP [40] et aux protocoles à vecteurs de chemin comme BGP [64] – tous les terminaux inondent le réseau avec la liste de leurs voisins, afin que chacun puisse reconstituer le graphe de routage.Le terme pro-actif signifie que les routes sont maintenues, par opposition aux protocoles réactifs, tel que AODV, où les routes sont construites à la demande. Il existe d’autres types de protocoles, mais ces deux classes sont les plus génériques. Les deux approches ont leurs avantages et leurs inconvénients, et [46] montre que pour un trafic sporadique, les algorithmes pro-actifs sont plus adaptés.Les travaux dans lesquels s’inscrit notre algorithme visent au support d’applications col- laboratives sur MANet, et le trafic, étant généré par des utilisateurs humains, est donc sporadique.