Performance comparison of randomized gossip, broadcast gossip and collection tree protocol for distributed averaging in wireless sensor networks

Wireless sensor networks consisting of low cost and battery-powered sensors are used for a multitude of applications from environmental monitoring to target tracking. The large number of sensors deployed in often inaccessible or hostile environments generates the need for fault-tolerant, asynchronous distributed systems and protocols. The problem of distributed averaging, in which nodes communicate with only their neighbors to calculate the network-wide average of their data value, is a basic building block for many more complex applications such as distributed optimization and compression. Gossip algorithms and tree-based aggregation are two popular paradigms for solving distributed averaging. In this thesis, we present and compare the performance of three algorithms: broadcast gossip, randomized gossip and the collection tree protocol. We first present algorithm implementations that address several issues in current literature such as lack of self-termination. This makes our implementations more suitable for practical deployment. We then optimize individual parameter values and investigate the performance of the three algorithms in terms of efficiency (communication overhead, latency and energy consumption) and accuracy (error and standard deviation) in wireless networks modeled as random geometric graphs. We show through simulations that increasing network size degrades the performance of all three algorithms and that uni-directional links degrade the performance of randomized gossip and the collection tree protocol, but they have a limited impact on broadcast gossip. We also compare the three algorithms side by side and show that broadcast gossip has the highest efficiency, but lowest accuracy. Finally, we show through simulations the impact of value initializations and node transmission power.Les reseaux des capteurs sans fil comprennent des capteurs a piles de faible cout. Ils sont utilises pour une multitude d'applications comme la surveillance d'environnementet le suivi des cibles. Le grand nombre des capteurs deployes dans l'environnement inaccessbile ou meme hostile necessite le developpement des applications distribuees asynchronoes peu affecte par la perte des capteurs dans le reseau. Dans le probleme de calcul distribue de moyenne, les capteurs peuvent seulement communiquer avec leurs voisins pour calculer la moyenne de toutes leurs donnees. Cette application est la base de beaucoup d'applications distribuees avancees comme l'optimization distribuee. Les algorithmes epidemiques (gossip) et l'agregation avec utilisation d'arbre sont deux solutions preferees. Dans cette these, nous presentons et comparons trois algorithmes: le "broadcast gossip", le "randomized gossip" et le "collection tree protocol". Nous presentons d'abord les implementations des trois algorithmes plus adaptees pour une utilisation pratique. Ensuite nous optimimizons les valeurs des parameters de chaque algorithme et comparons les performances des trois algorithmes en considerant l'efficacite (nombre de transmissions, le temps et l'energie requis) et la precision (l'erreur et l'ecart type). Nous demontrons par simulations que le "broadcast gossip" a la meilleure efficacite et la pire precision. Nous montrons aussi que les liens uni-directionels affectent negativement les performances de "randomized gossip" et "collection tree protocol". Nous montrons finalement l'influence des valeurs initiales et la puissance de transmission