A distributed convergecast algorithm for dynamic mobile networks ; Un algorithme de diffusion convergente pour les réseaux dynamiques

International audience ; Some applications, like round-based consensus algorithms, require all the nodes from a system to send a message to the same node (the leader) at the same time. In a Mobile Ad-Hoc Network (MANET), this situation is likely to cause collisions and the loss of the messages converging to the leader. The loss of messages is critical in such a situation, since the leader needs to receive a quorum of messages to make a decision. This pattern of communications, called convergecast, can be trivially implemented with a unicast primitive. However, we show that a popular MANET unicast algorithm like Optimized Link State Routing (OLSR) loses a lot of messages, even in the presence of MAC-level collision avoidance mechanisms like CSMA/CA. We propose a new convergecast algorithm that locally schedules answers to a query in a fully distributed manner, in order to avoid their colliding with each other, and that aggregates these answers in order to further decrease the probability of collisions. We show that our algorithm creates far fewer collisions and retries than OLSR, allowing applications like consensus algorithms to reach their quorum sooner. ; Certaines applications comme les algorithmes de consensus à phase, supposent que tous les nœuds d'un système envoient un message à un même nœud (le coordinateur) en même temps. Dans un réseau mobile ad hoc (MANET), cette situation est très susceptible de causer des collisions et donc la perte les messages convergents vers le coordinateur. La perte des messages est critique dans une telle situation, parce que le coordinateur a besoin de recevoir un quorum de messages pour prendre une décision. Ce modèle de communication, appelé diffusion convergente, peut être implémenté trivialement sur une primitive de diffusion point-à-point. Cependant, nous montrons qu'un algorithme de diffusion point-à-point pour MANET populaire comme OLSR (Optimized Link State Routing) perd beaucoup de messages, et ce même en présence d'un mécanisme d'esquive des collisions de niveau MAC ...