Distributed Estimation Via a Roaming Token
For multi-agent networks, this provides a communication-efficient distributed estimation method with provable optimality, though incremental over existing consensus-based approaches.
The paper proposes a roaming token algorithm for distributed linear parameter estimation in a network, achieving asymptotic optimality with MSE decay rate approaching the centralized case. Simulations show it outperforms consensus+innovations algorithms in MSE at each iteration.
We present an algorithm for the problem of linear distributed estimation of a parameter in a network where a set of agents are successively taking measurements. The approach considers a roaming token in a network that carries the estimate, and jumps from one agent to another in its vicinity according to the probabilities of a Markov chain. When the token is at an agent it records the agent's local information. We analyze the proposed algorithm and show that it is consistent and asymptotically optimal, in the sense that its mean-square-error (MSE) rate of decay approaches the centralized one as the number of iterations increases. We show these results for a scenario where the network changes over time, and we consider two different set of assumptions on the network instantiations: they are i.i.d. and connected on the average, or they are deterministic and strongly connected for every finite time window of a fixed size. Simulations show our algorithm is competitive with consensus+innovations type algorithms, achieving a smaller MSE at each iteration in all considered scenarios.