Distributed consensus algorithms for wireless sensor networksconvergence analysis and optimization

Resumo

Wireless sensor networks are developed to monitor areas of interest with the purpose of estimating physical parameters or/and detecting emergency events in a variety of military and civil applications. A wireless sensor network can be seen as a distributed computer, where spatially deployed sensor nodes are in charge of gathering measurements from the environment to compute a given function. The research areas for wireless sensor networks extend from the design of small, reliable hardware to low-complexity algorithms and energy saving communication protocols. Distributed consensus algorithms are low-complexity iterative schemes that have received increased attention in different fields due to a wide range of applications, where neighboring nodes communicate locally to compute the average of an initial set of measurements. Energy is a scarce resource in wireless sensor networks and therefore, the convergence of consensus algorithms, characterized by the total number of iterations until reaching a steady-state value, is an important topic of study. This PhD thesis addresses the problem of convergence and optimization of distributed consensus algorithms for the estimation of parameters in wireless sensor networks. The impact of quantization noise in the convergence is studied in networks with fixed topologies and symmetric communication links. In particular, a new scheme including quantization is proposed, whose mean square error with respect to the average consensus converges. The limit of the mean square error admits a closed-form expression and an upper bound for this limit depending on general network parameters is also derived. The convergence of consensus algorithms in networks with random topology is studied focusing particularly on convergence in expectation, mean square convergence and almost sure convergence. Closed-form expressions useful to minimize the convergence time of the algorithm are derived from the analysis. Regarding random networks with asymmetric links, closed-form expressions are provided for the mean square error of the state assuming equally probable uniform link weights, and mean square convergence to the statistical mean of the initial measurements is shown. Moreover, an upper bound for the mean square error is derived for the case of different probabilities of connection for the links, and a practical scheme with randomized transmission power exhibiting an improved performance in terms of energy consumption with respect to a fixed network with the same consumption on average is proposed. The mean square error expressions derived provide a means to characterize the deviation of the state vector with respect to the initial average when the instantaneous links are asymmetric. A useful criterion to minimize the convergence time in random networks with spatially correlated links is considered, establishing a sufficient condition for almost sure convergence to the consensus space. This criterion, valid also for topologies with spatially independent links, is based on the spectral radius of a positive semidefinite matrix for which we derive closed-form expressions assuming uniform link weights. The minimization of this spectral radius is a convex optimization problem and therefore, the optimum link weights minimizing the convergence time can be computed efficiently. The expressions derived are general and apply not only to random networks with instantaneous directed topologies but also to random networks with instantaneous undirected topologies. Furthermore, the general expressions can be particularized to obtain known protocols found in literature, showing that they can be seen as particular cases of the expressions derived in this thesis.