Abstract
In decentralized networks such as sensor arrays or drone swarms, achieving a global average of local measurements is a fundamental requirement for collective decision-making. However, real-world communication is constrained by finite-bit quantization. This paper addresses the challenge of distributed average consensus using bounded quantizers, specifically focusing on scenarios where initial data may exceed the quantizer's range. By leveraging the Alternating Direction Method of Multipliers (ADMM), we propose the BQ-CADMM and EBQ-CADMM algorithms. We demonstrate that these methods achieve error bounds comparable to infinite-range quantizers and provide an adaptive strategy for parameter selection to optimize convergence speed.
Introduction
Distributed average consensus is the process by which a network of agents calculates the global mean of their individual measurements using only local, peer-to-peer communication. While theoretical models often assume nodes can exchange real numbers with infinite precision, physical hardware is limited by bandwidth and power, necessitating the use of quantization—converting continuous signals into discrete bits.
Most existing literature on quantized consensus assumes "unbounded" quantizers (which have an infinite number of levels) or requires that the input data be pre-constrained within a known, finite range. In practical applications like signal detection in Gaussian noise, measurements can be theoretically infinite, rendering standard bounded quantizers ineffective. This paper bridges this gap by introducing a robust framework for consensus with finite-bit quantizers and unbounded input data.
Algorithmic Framework: BQ-CADMM and EBQ-CADMM
The proposed solution utilizes the Alternating Direction Method of Multipliers (ADMM), a powerful optimization framework, to manage the constraints imposed by quantization. Two primary algorithms are developed:
1. Bounded Quantizer Consensus ADMM (BQ-CADMM)
In BQ-CADMM, nodes update their local estimates by projecting their values onto a compact convex set defined by the quantizer’s range. These values are then rounded to the nearest quantization level. The authors prove that this iterative process is mathematically equivalent to solving a constrained least-squares problem, ensuring that the network moves toward a common value despite the loss of precision during communication.
2. Extended BQ-CADMM (EBQ-CADMM)
A significant challenge arises when the true global average lies outside the physical range of the quantizer. To solve this, EBQ-CADMM runs the base algorithm iteratively. Nodes first reach a consensus at the boundary of the quantizer's range, calculate the residual (the difference between their data and that boundary), and then run the algorithm again on the residual. This "multi-pass" approach allows the network to eventually shift the residual average into the quantizer's high-resolution "sweet spot."
Convergence and Error Analysis
A unique characteristic of finite-bit systems is that they may not settle on a single static value. The paper identifies two possible outcomes for the agent variables:
- Convergence: All nodes settle on the same quantization level.
- Stable Cycling: Nodes enter a periodic cycle where values oscillate around the true average.
Crucially, the authors show that even during cycling, the sample average of these oscillations over one period provides a consistent and accurate consensus value across all nodes. Furthermore, the analysis reveals that if the ADMM step size ($\rho$) is chosen correctly, the consensus error bound for this bounded system is identical to that of a system using an infinite-range quantizer. This error bound is notably independent of the total number of agents or the magnitude of the initial data, ensuring high scalability for large-scale networks.
Parameter Selection and Performance
The performance of ADMM-based algorithms is highly sensitive to the step size parameter, $\rho$. The authors provide a practical heuristic for selecting this value based on the network topology: $$\rho = \frac{n}{m}$$ where $n$ is the number of nodes and $m$ is the number of edges. Simulations across various topologies—including star, random, and complete graphs—demonstrate that this heuristic effectively balances convergence speed and accuracy.
Key results from numerical simulations include:
- High Accuracy: In a 50-node network, the observed consensus error (0.20) was significantly lower than the theoretical upper bound (2.5).
- Efficiency: EBQ-CADMM typically requires only a few iterations to handle data significantly outside the quantizer range.
- Robustness: The algorithm successfully reaches consensus even with very low-resolution quantizers (e.g., representing a range of [-25, 25] with integer steps).
Conclusion and Future Work
This research provides a mathematically rigorous yet practical approach to distributed consensus in bandwidth-constrained environments. By enabling bounded quantizers to handle unbounded inputs, it brings distributed averaging closer to real-world implementation in ad hoc networks.
Future research will address the limitations of the current synchronous framework, exploring how these algorithms perform under asynchronous communication, link failures, and noisy channels. Additionally, while the current $\rho$ selection is an effective heuristic, a more formal strategy for optimal parameter selection remains an open area for investigation.
Summary updated