Consensus Trade-offs in Wireless Sensor Networks

As more and more everyday electronic devices become equipped with the combined re- sources of computation, sensing, and wireless communications, possible platforms for implementation of wireless sensor networks have become ubiquitous. The combination of these three main capabilities of such a network present the opportunity to for example gather high resolution measurement data, or cooperatively perform advanced computa- tional tasks. The size of these wireless sensor networks are often said to be on the order of hundreds to several thousands nodes. To harness the capabilities of these networks, there is a need to design and implement efficient distributed algorithms. In this thesis we study a family of distributed algorithms referred to as consensus algorithms. These algorithms work by nodes in the network locally exchanging informa- tion with the goal of reaching an agreement (consensus) on something. They then use the information received from their neighbors to update their information according to an update rule determined by the algorithm. This is done repeatedly until consensus on the information is reached, or we decide to stop the algorithm. Specifically, we study design choices, or trade-offs, that should be considered when implementing consensus algorithms to solve certain distributed problems in wireless sensor networks. The trade- offs investigated in this thesis and the appended papers deal with the metrics of time, communication resource usage, and information disagreement. In the overview part of the thesis we give an introduction to some consensus algo- rithms, and show how the convergence properties can be analyzed using spectral analysis of matrices. We also briefly introduce two trade-offs, and give some intuition of the mechanics behind their behaviors. In the appended papers, we present an application of consensus algorithms to in-network compression using the theory of compressed sensing. We derive upper bounds for the reconstruction performance. These bounds are then used to formulate a trade-off between two communication costs, one cost for sensor-to-sensor communication and one for sensor-to-sink communication, given a reconstruction error threshold. Furthermore, we evaluate the optimal system design given the cost ratio of the two communication costs. We also use a consensus algorithm in combination with a distributed particle filter to perform distributed tracking. The trade-off considered for this scenario is one weighing tracking performance against time delay, with the design parameter being the communication range affecting both of these metrics