Communication primitives for dynamic networks : broadcast and convergecast

Cette thèse a pour objectif de proposer des primitives de communication pour les réseaux dynamiques sans infrastructure qui soient suffisamment performantes pour permettre l'implémentation de services de support très coûteux en messages, comme le consensus, l'élection de coordinateur ou le verrou distribué. Ces services sont habituellement implémentés dans des réseaux filaires et fixes typiques de l'informatique en nuage. Ils requièrent l'utilisation de deux primitives de communications, la diffusion globale (un pour tous) et la diffusion convergente (tous pour un), qui sont particulièrement coûteuses en énergie et sensibles aux collisions fréquentes dans les réseaux dynamiques sans infrastructure. Cette thèse présente donc deux contributions : - MPR alternant, une variante de l'algorithme de diffusion globale MPR. Celui-ci, s'il est capable de bien restreindre l'ensemble des nœuds chargés de retransmettre les messages, ce qui permet des économies en nombre de messages et en énergie, a tendance à toujours solliciter les mêmes nœuds, amenant leur mort prématurée. Notre contribution, MPR alternant, construit plusieurs ensembles de relais et les utilise à tour de rôle. De cette manière, nous sommes capables de répartir plus équitablement la charge des retransmissions, sans dégrader le taux de couverture, et pour un coût en messages très faible. - Convergecast distribué, un algorithme de diffusion convergente complètement distribué utilisant uniquement des informations de voisinage locales. Là où des algorithmes de diffusion point-à-point populaires comme OLSR perdent énormément de messages quand les transmissions sont synchronisées et convergent vers un unique nœud, notre algorithme utilise les informations de voisinage pour ordonnancer les messages convergents localement et les agréger sur le chemin de la destination. Notre algorithme cause beaucoup moins de collisions que OLSR, tout en étant moins cher en messages et présentant une meilleure latence.