Accelerated Multi-Stage Discrete Time Dynamic Average Consensus

This letter presents a novel solution for the discrete time dynamic average consensus problem. Given a set of time-varying input signals over the nodes of an undirected graph, the proposed algorithm tracks, at each node, the input signals’ average. The algorithm is based on a sequence of consensus stages combined with a second order diffusive protocol. The former overcomes the need of k-th order differences of the inputs and conservation of the network state average, while the latter overcomes the trade-off between speed and accuracy of the consensus stages by just storing the previous estimate at each node. The result is a protocol that is fast, arbitrarily accurate, and robust against input noises and initializations. The protocol is extended to an asynchronous and randomized version that follows a gossiping scheme that is robust against potential delays and packet losses. We study the convergence properties of the algorithms and validate them via simulations.

I. Introduction

The problem of consensus in control theory [1] consists of finding a protocol such that a set of nodes in a network agree on the value of a certain quantity of interest. In particular, the discrete time dynamic average consensus [2] is interesting because the tracked signals usually evolve with time, and protocols are implemented in computing units that work in discrete steps. Despite the existing literature, current solutions still suffer from some of the following issues: (i) integral and difference input terms are not robust against input and initialization noise, or changes of network size; (ii) trade-off between convergence speed and steady-state accuracy; (iii) absence of robustness against packet losses and communication delays. These aspects affect the applicability of consensus in real-world scenarios such as smart grids [3] or sensor networks [4]. To overcome these issues, we propose a novel algorithm that combines a multi-stage consensus protocol and a second order diffusion method, along with its asynchronous and randomized version.