Master 2014 2015
Stages de la spécialité SAR
Validation de protocoles répartis pour réseaux opportunistes


Site :Trac-Validation de protocoles répartis pour réseaux opportunistes
Lieu :LIP6, Campus Jussieu, 4 place Jussieu, 75005 Paris, France
Encadrant : Swan Dubois, Louisa Harutyunyan et Matthieu Latapy Equipe ComplexNetworks et Equipe-projet Inria REGAL <Prenom>.<Nom>@lip6.fr
Dates :01/03/2015 au 31/08/2015
Rémunération :Gratification standard
Mots-clés : Master SAR, autre qu’ATIAM

Description

Contexte

Les réseaux mobiles opportunistes ad-hoc se forment lorsque des terminaux mobiles portés par des utilisateurs communiquent entre eux sans aucune infrastructure. C’est par exemple le cas lorsque des applications utilisent des communications directes (WiFi ou Bluetooth) entre téléphones mobiles géographiquement proches plutôt que des diffusions massives via le réseau 3G. Ces réseaux diffèrent ainsi largement des réseaux classiques (Internet, réseau de téléphonie mobile,...) dont l’architecture suppose la disponibilité spontanée des chemins reliant les terminaux. A l’inverse, dans les réseaux opportunistes, la mobilité des terminaux induit de nombreuses déconnexions et modifications de la topologie du réseau.

Ce projet constitue la première étape d’une recherche visant à formaliser ces réseaux opportunistes. A terme, l’objectif de cette recherche est de fournir un modèle théorique de ce type de réseaux. En effet, un tel modèle est la pierre angulaire de toute étude formelle. Cependant, les contraintes de dynamique et de communication opportuniste considérées ici requièrent de nouveaux modèles afin de prendre en compte les caractéristiques propres de ces systèmes comme la mobilité des utilisateurs. Ces dernières années, un modèle semble s’imposer pour l’étude des systèmes répartis dynamiques : les Time Varying Graphs (TVG).

Bien que ce modèle soit suffisamment expressif pour décrire la dynamique d’un réseau opportuniste (entre autres), il souffre d’une limitation due à sa définition. En effet, toute exécution d’un système modélisé par un TVG est supposée être infinie. Or, cette hypothèse n’est pas nécessairement satisfaite par un réseau opportuniste. En particulier, les traces collectées lors d’expérimentations sur de tels réseaux sont par nature de durée limitée.

Objectifs du stage

L’objectif de ce stage est d’étudier la possibilité de porter des résultats obtenus sur les TVG sur des réseaux opportunistes. En d’autres termes, des algorithmes conçus pour des exécutions infinies (cas des TVG) peuvent-ils être transposés dans un cadre où les exécutions sont finies (cas des réseaux opportunistes) ?

Des résultats précédents ont montré la pertinence du calcul d’un ensemble dominant maximal dans le domaine des réseaux opportunistes. Des membres de l’équipe REGAL ont proposé une solution à ce problème dans les TVG. La première étape de ce projet consistera à implémenter ce protocole de manière à pouvoir le valider et l’évaluer en utilisant des traces d’exécutions de réseaux opportunistes réels (par exemple, RollerNet, un réseau de contacts établi durant une randonnée à rollers).

Selon les résultats obtenus lors de cette première phase et les affinités du stagiaire, le stage pourra ensuite emprunter une (ou plusieurs) des pistes suivantes :

  • Etude des traces afin d’évaluer la validité des hypothèses du modèle des TVG.
  • Correction/optimisation du protocole de calcul d’un ensemble dominant maximal.
  • Extension du modèle des TVG aux exécutions finies.
  • Validation et évaluation d’autres protocoles définis pour les TVG dans le contexte des réseaux opportunistes.

Bibliographie

A. Casteigts, P. Flocchini, W. Quattrociocchi, and N. Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems, 27(5) :387–408, 2012.

Crawdad. http://crawdad.cs.dartmouth.edu/

Mieso K. Denko. Mobile Opportunistic Networks : Architectures, Protocols and Applications. Auerbach Publications, 2011.

Swan Dubois, Mohamed-Hamza Kaaouachi, and Franck Petit. Enabling minimal dominating set in highly dynamic distributed systems. Technical report, Inria - to appear, 2014.

Pierre-Ugo Tournoux, Jeremie Leguay, Farid Benbadis, John Whitbeck, Vania Conan, and Marcelo Dias de Amorim. Density-aware routing in highly dynamic DTNs : The rollernet case. IEEE Transactions on Mobile Computing, 10(12) :1755–1768, 2011.

John Whitbeck, Marcelo Dias de Amorim, Vania Conan, and Jean-Loup Guillaume. Temporal reachability graphs. In The 18th Annual International Conference on Mobile Computing and Networking - Mobicom’12, pages 377–388, 2012.