Distributed average consensus with dithered quantization

被引:222
作者
Aysal, Tuncer Can [1 ]
Coates, Mark J. [2 ]
Rabbat, Michael G. [2 ]
机构
[1] Cornell Univ, Sch Elect & Comp Engn, Commun Res Signal Proc Grp, Ithaca, NY 14853 USA
[2] McGill Univ, Dept Elect & Comp Engn, Telecommun & Signal Proc Comp Networks Lab, Montreal, PQ H3A 2A7, Canada
关键词
average consensus; distributed algorithms; dithering; probabilistic quantization; sensor networks;
D O I
10.1109/TSP.2008.927071
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
In this paper, we develop algorithms for distributed computation of averages of the node data over networks with bandwidth/power constraints or large volumes of data. Distributed averaging algorithms fail to achieve consensus when deterministic uniform quantization is adopted. We propose a distributed algorithm in which the nodes utilize probabilistically quantized information, i.e., dithered quantization, to communicate with each other. The algorithm we develop is a dynamical system that generates sequences achieving a consensus at one of the quantization values almost surely. In addition, we show that the expected value of the consensus is equal to the average of the original sensor data. We derive an upper bound on the mean-square-error performance of the probabilistically quantized distributed averaging (PQDA). Moreover, we show that the convergence of the PQDA is monotonic by studying the evolution of the minimum-length interval containing the node values. We reveal that the length of this interval is a monotonically nonincreasing function with limit zero. We also demonstrate that all the node values, in the worst case, converge to the final two quantization bins at the same rate as standard unquantized consensus. Finally, we report the results of simulations conducted to evaluate the behavior and the effectiveness of the proposed algorithm in various scenarios.
引用
收藏
页码:4905 / 4918
页数:14
相关论文
共 29 条
  • [1] [Anonymous], 2000, ACM IEEE INT C MOB C
  • [2] UPPER (LOWER) BOUNDS ON THE MEAN OF THE MAXIMUM (MINIMUM) OF A NUMBER OF RANDOM-VARIABLES
    AVEN, T
    [J]. JOURNAL OF APPLIED PROBABILITY, 1985, 22 (03) : 723 - 728
  • [3] Aysal T. C., 2007, IEEE STAT SIGN PROC
  • [4] AYSAL TC, 2007, ALL C COMM CONTR COM
  • [5] Devroye L. P., 1979, Mathematics of Operations Research, V4, P441, DOI 10.1287/moor.4.4.441
  • [6] Kallenberg O, 2002, FDN MODERN PROBABILI
  • [7] Quantized consensus
    Kashyap, Akshay
    Basar, Tamer
    Srikant, R.
    [J]. AUTOMATICA, 2007, 43 (07) : 1192 - 1203
  • [8] Lynch N.A., 1996, Distributed Algorithms
  • [9] MADDEN SR, 2002, WORKSH MOB COMP SYST
  • [10] Consensus propagation
    Moallemi, Ciamac C.
    Van Roy, Benjamin
    [J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (11) : 4753 - 4766