Using hierarchical decomposition to speed up average consensus

Michael Epstein, Kevin M. Lynch, Karl Henrik Johansson, Richard M. Murray

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 Scopus citations

Abstract

We study the continuous-time consensus problem where nodes on a graph attempt to reach average consensus. We consider communication graphs that can be decomposed into a hierarchical structure and present a consensus scheme that exploits this hierarchical topology. The scheme consists of splitting the overall graph into layers of smaller connected subgraphs. Consensus is performed within the individual subgraphs starting with those of the lowest layer of the hierarchy and moving upwards. Certain 'leader' nodes bridge the layers of the hierarchy. By exploiting the increased convergence speed of the smaller subgraphs, we show how this scheme can achieve faster overall convergence than the standard single-stage consensus algorithm running on the full graph topology. The result presents some fundamentals on how the communication architecture influences the global performance of a networked system. Analytical performance bounds are derived and simulations provided to illustrate the effectiveness of the scheme.

Original languageEnglish (US)
Title of host publicationProceedings of the 17th World Congress, International Federation of Automatic Control, IFAC
Edition1 PART 1
DOIs
StatePublished - 2008
Event17th World Congress, International Federation of Automatic Control, IFAC - Seoul, Korea, Republic of
Duration: Jul 6 2008Jul 11 2008

Publication series

NameIFAC Proceedings Volumes (IFAC-PapersOnline)
Number1 PART 1
Volume17
ISSN (Print)1474-6670

Other

Other17th World Congress, International Federation of Automatic Control, IFAC
CountryKorea, Republic of
CitySeoul
Period7/6/087/11/08

Keywords

  • Distributed control and estimation
  • Multi-agent systems
  • Sensor networks

ASJC Scopus subject areas

  • Control and Systems Engineering

Fingerprint Dive into the research topics of 'Using hierarchical decomposition to speed up average consensus'. Together they form a unique fingerprint.

Cite this