Publication
Wireless sensor networks have emerged a few years ago, enabling large scale sensing at low cost. There are many interesting problems related to this new sensing tool: designing robust and small hardware, defining adapted routing protocols, minimizing the energy consumption of each component, synchronizing the sensors, etc. In this thesis, we focus on the processing of the sensed data within the network itself. We study a specific network signal processing problem, called distributed average consensus. In this problem, the sensors, which are connected in a wireless network, need to know the average of all the measurements in the network. Instead of gathering the data at a central node, which would compute the average and broadcast it to the network, average consensus algorithms offer a distributed solution to the averaging problem. By local message passing and iterative local computations only, nodes can learn the average of the measurements. More precisely, in average consensus algorithms, nodes iteratively compute local weighted averages that conserve the global average of the estimates in the network. The estimates at each node contract until they all converge to the average. Many distributed average consensus algorithms were designed and the literature is vast. This thesis starts by classifying the existing algorithms. Then it describes a small number of useful techniques, which can handle the analysis of all the algorithms. Preexisting algorithms as well as algorithms that we designed are revisited with these unifying and simple techniques. In addition, the performance of the algorithms depends on the topology of the network, and a variety of networks are explored: simple graphs as circles or trees, lattices, random geometric graphs, complete graphs etc. Finally, an extension of average consensus to voting consensus is derived. In particular, we show that with two bits of memory at each node, a network can reach consensus in finite time on majority, when the initial measurements are binary. Distributed algorithms to compute majority with finite memory for ternary and quaternary signals are also given.