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


Lieu :LIP6, Campus Jussieu, 4 place Jussieu, 75005 Paris, France
Encadrant : Swan Dubois, Jean-Loup Guillaume, Clémence Magnien et Franck Petit Équipe ComplexNetworks et Équipe-projet Inria REGAL
Dates :04/2014 au 09/2014
Rémunération :Oui
Mots-clés : Parcours SAR autre qu’ATIAM, recherche

Description

Contexte

Les réseaux mobiles opportunistes ad-hoc [3] se forment lorsque des terminaux mobiles portés par des utilisateurs communiquent entre eux sans aucune infrastructure. À titre d’exemple, on peut penser à des applications utilisant des communications directes (WiFi ou Bluetooth) entre téléphones mobiles géographi- quement proches plutôt que des diffusions massives via le réseau 3G. Ces réseaux diffèrent ainsi largement des réseaux classiques comme Internet dont l’architecture suppose la disponibilité instantanée des chemins reliant les terminaux. À 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 stage constitue la première étape d’une recherche visant à formaliser ces réseaux opportunistes. À 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) [2].

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. Cependant, 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 [1] 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 de certains membres de l’équipe ComplexNetworks [5] ont montré la pertinence du calcul d’un ensemble dominant maximal dans le domaine des réseaux opportunistes. Des membres de l’équipe REGAL travaillent actuellement à un protocole pour résoudre ce problème dans les TVG. La pre- miè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 [4], un réseau de contacts établi le temps d’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 :
- Étude 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 oppor- tunistes.

Bibliographie

[1] Crawdad. http://crawdad.cs.dartmouth.edu/.

[2] Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. In Ad-hoc, Mobile, and Wireless Networks - 10th International Conference, ADHOC-NOW 2011, pages 346–359, 2011.

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

[4] 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 Trans. Mob. Comput., 10(12) :1755–1768, 2011.

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