Optimal strategies in the average consensus problem

被引:25
作者
Delvenne, Jean-Charles [1 ]
Carli, Ruggero [2 ]
Zampieri, Sandro [2 ]
机构
[1] Catholic Univ Louvain, Dept Appl Math, B-1348 Louvain, Belgium
[2] Univ Padua, Dept Informat Engn, I-35131 Padua, Italy
关键词
Average consensus problems; de Bruijn graphs; Kronecker product; ALGORITHMS;
D O I
10.1016/j.sysconle.2009.08.005
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Let a set of communicating agents compute the average of their initial positions, where every agent is restricted to communicate to a given small number of other agents (average consensus problem). We prove that the optimal topology of communication is given by a de Bruijn graph. Consensus is then reached in finitely many steps. This solution is valid when the number of agents is an exact power of the out-degree of the communication graph. We introduce an algebraic tool, the shifted Kronecker product, and a more general family of strategies, also based on a de Bruijn communication graph. Those strategies are compared to Cayley strategies in terms of the speed of convergence. We also show that quantized communication between the agents still allows finite convergence, to a consensus, which is not in general the average of the initial positions. (C) 2009 Elsevier B.V. All rights reserved.
引用
收藏
页码:759 / 765
页数:7
相关论文
共 27 条
  • [1] [Anonymous], 2000, INTRO GRAPH THEORY
  • [2] Distributed average consensus using probabilistic quantization
    Aysal, Tuncer C.
    Coates, Mark
    Rabbat, Michael
    [J]. 2007 IEEE/SP 14TH WORKSHOP ON STATISTICAL SIGNAL PROCESSING, VOLS 1 AND 2, 2007, : 640 - 644
  • [3] Boyd S, 2005, IEEE INFOCOM SER, P1653
  • [4] Fastest mixing Markov chain on a graph
    Boyd, S
    Diaconis, P
    Xiao, L
    [J]. SIAM REVIEW, 2004, 46 (04) : 667 - 689
  • [5] Bullo F., 2008, DISTRIBUTED CONTROL
  • [6] CARLI R, 1852, EUR CONTR C
  • [7] Communication constraints in the average consensus problem
    Carli, Ruggero
    Fagnani, Fabio
    Speranzon, Alberto
    Zampieri, Sandro
    [J]. AUTOMATICA, 2008, 44 (03) : 671 - 684
  • [8] Quantized average consensus via dynamic coding/decoding schemes
    Carli, Ruggero
    Bullo, Francesco
    Zampieri, Sandro
    [J]. 47TH IEEE CONFERENCE ON DECISION AND CONTROL, 2008 (CDC 2008), 2008, : 4916 - 4921
  • [9] de Bruijn N.G., 1946, Koninklijke Nederlandse Akademie van Wetenschappen, V49
  • [10] EPPSTEIN D, DEBRUIJN GRAPH LINE