A Local Average Consensus Algorithm for Wireless Sensor Networks

Presented at the Workshop on Localized Algorithms and Protocols for Wireless Sensor Networks (LOCALGOS 2011)International audienceIn many application scenarios sensors need to calculate the average of some local values, e.g. of local measurements. A possible solution is to rely on consensus algorithms. In this case each sensor maintains a local estimate of the global average, and keeps improving it by performing a weighted sum of the estimates of all its neighbors. The number of iterations needed to reach an accurate estimate depends on the weights used at each sensor. Speeding up the convergence rate is important also to reduce the number of messages exchanged among neighbors and then the energetic cost of these algorithms. While it is possible in principle to calculate the optimal weights, the known algorithm requires a single sensor to discover the topology of the whole network and perform the calculations. This may be unfeasible for large and dynamic sensor networks, because of sensor computational constraints and of the communication overhead due to the need to acquire the new topology after each change. In this paper we propose a new average consensus algorithm, where each sensor selects its own weights on the basis of some local information about its neighborhood. Our algorithm is tailored for networks having cluster structure, like it is common for wireless sensor networks. In realistic sensor network topologies, the algorithm shows faster convergence than other existing consensus protocols