Accelerated Distributed Average Consensus Via Localized Node State Prediction

TitleAccelerated Distributed Average Consensus Via Localized Node State Prediction
Publication TypeReport
Year of Publication2007
AuthorsAysal, T. C., B. N. Oreshkin, and M. J. Coates
Date Published10/2007
InstitutionDepartment of Electrical and Computer Engineering, McGill University
CityMontreal, QC, Canada
TypeTechnical Report
Keywordsaverage consensus, distributed signal processing, linear prediction

The problem of distributed consensus has recently received a lot of attention, particularly in the framework of ad hoc sensor networks. The average consensus problem in the distributed signal processing context is addressed by linear iterative algorithms, with asymptotic convergence to the consensus. The convergence of the average consensus for an arbitrary weight matrix satisfying the convergence conditions is unfortunately slow refraining the use of the developed algorithms in applications. In this paper, we propose the use of extrapolation methods in order to accelerate distributed linear iterations. We utilize a linear operator to predict the future node state values and then combine the prediction with the current node state value in a convex fashion driving overall system state closer to the true consensus value faster than the standard consensus algorithms. A faster convergence is, hence, achieved by the bypassing of redundant states. The proposed method is linear and computationally effective. We focus on a special case of the proposed framework and derive the optimal mixing parameter. Noting that the optimal mixing parameter requires knowledge about the eigenvalues of the arbitrary weight matrix, we present a bound on the optimal parameter requiring only local information, and prove the validity of the suboptimal solution in the practical cases by showing that its performance is close–to–optimal and it is feasible in practical scenarios. Finally, we provide simulation results that demonstrate the validity and effectiveness of the proposed scheme. These results also indicate that in general situation the consensus based on the proposed approach significantly outperforms the optimum algorithm based on weight matrix optimization relying on semidefinite programming paradigm.

Refereed DesignationDoes Not Apply
aysal_TechReport07.pdf196.67 KB