Sujet de Master Recherche Informatique 2005-2006 (RD2P/POPS#2)
Synchronisation d'horloge dans les réseaux de capteurs
Filière Conception de Systèmes Embarqués ou
Applications Réparties
Encadrants
Sujet
Ce sujet est proposé par le projet commun CNRS/INRIA/USTL POPS en partenariat l'Université de Reims.
La synchronisation d'horloge est un problème bien connu dans les sytèmes distribués. De nombreuses applications nécessitent une synchronisation entre les éléments d'un réseau. Par exemple, déterminer la vitesse d'un objet mobile, utiliser TDMA comme méthode d'accès à des canaux de communication ou plus généralement tous les algorithmes nécessitant une dicrétisation du temps en slot. Tous ces algorithmes sont plus ou moins sensibles à la dérive de l'horloge interne des éléments du réseau. Il existe plusieurs types de synchronisation : elle peut être absolue ou relative, ou encore globale (tout le réseau) ou locale (un voisinage) en fonction des besoins. Certaines solutions utilisent le GPS, d'autres n'utilise que les informations fournit par l'environnement proche.
Le but de ce stage sera dans un premier temps d'étudier l'impact d'une dérive des horloges internes des éléments d'un réseau sur l'application. Une seconde étape sera de recenser les différentes méthodes de synchronisation existantes actuellement. Une analyse de ces méthodes permettra ensuite de détermminer lesquelles seront les meilleurs candidates à un passage à l'échelle pour une utilisation dans un environnement dense de type réseaux de capteurs.
Travail demandé
- Evaluation par simulation de l'impact d'une dérive d'horloge interne sur des algorihtmes distribués (notamment des algorithmes de couverture de surface) ;
- Recenser les différentes méthodes de synchronisation ;
- étude, évaluation et comparaison de ces méthodes.
La dernière phase du stage est bien sûr ouverte aux propositions d'extension et à la nouveauté. Le stagiaire pourra alors tester ses propositions par simulation ou par expérimentation sur des capteurs de type MICAZ.
Références bibliographiques
- R. Fan, and N. Lynch. Gradient Clock Synchronization. In Proc. of Principle Of Distributed Computing (PODC'04), pp. 320--327.
- J. Elson and D. Estrin. Time Synchronization for Wireless Sensor Networks. In Proc. of the 2001 International Parallel and Distributed Processing Symposium (IPDPS), Workshop on Parallel and Distributed Computing Issues in Wireless Networks and Mobile Computing, April 2001, San Francisco, USA, pp. 1965--1970.
- T.K. Srikanth, and S. Toueg. Optimal Clock Synchronization. In Journal of Association for Computing Machinery (ACM), Vol. 34, N° 3, july 1987, pp 626--645