Abstract
This paper describes and analyzes a hierarchical gossip algorithm for solving the distributed average consensus problem in wireless sensor networks. The network is recursively partitioned into subnetworks. Initially, nodes at the finest scale gossip to compute local averages. Then, using geographic routing to enable gossip between nodes that are not directly connected, these local averages are progressively fused up the hierarchy until the global average is computed. We show that the proposed hierarchical scheme with $k$ levels of hierarchy is competitive with state-of-the-art randomized gossip algorithms, in terms of message complexity, achieving $\epsilon$-accuracy with high probability after $O\big(n \log \log n \log \frac{kn}{\epsilon} \big)$ messages. Key to our analysis is the way in which the network is recursively partitioned. We find that the optimal scaling law is achieved when subnetworks at scale $j$ contain $O(n^{(2/3)^j})$ nodes; then the message complexity at any individual scale is $O(n \log \frac{kn}{\epsilon})$, and the total number of scales in the hierarchy grows slowly, as $\Theta(\log \log n)$. Another important consequence of hierarchical construction is that the longest distance over which messages are exchanged is $O(n^{1/3})$ hops (at the highest scale), and most messages (at lower scales) travel shorter distances. In networks that use link-level acknowledgements, this results in less congestion and resource usage by reducing message retransmissions. Simulations illustrate that the proposed scheme is more message-efficient than existing state-of-the-art randomized gossip algorithms based on averaging along paths.
Introduction
In decentralized networks such as wireless sensor arrays or smart grids, nodes often need to compute a global average of their initial values (e.g., temperature readings) without a central server. This is known as the distributed average consensus problem.
Standard "gossip" algorithms—where nodes trade and average values with immediate neighbors—scale poorly on common topologies like grids or Random Geometric Graphs (RGGs). While advanced techniques like "path averaging" improved efficiency to a linear scale, they rely on messages traveling across the entire diameter of the network. This creates two major issues: fragility due to link failures and congestion at the network center.
Methodology: The Multiscale Approach
The proposed algorithm utilizes a "divide-and-conquer" hierarchical structure. The network is recursively partitioned into smaller cells across multiple scales to balance communication costs.
The process works bottom-up:
- Recursive Partitioning: The network is divided into smaller and smaller cells.
- Local Gossip: Nodes within the smallest cells gossip to find a local average.
- Representative Election: Each cell elects a "representative" node to carry its local average to the next level.
- Overlay Gossip: Representatives form a logical grid at the next scale and gossip using multi-hop geographic routing.
- Dissemination: Once the coarsest scale reaches a global average, the value is pushed back down the hierarchy to all nodes.
A critical component of the analysis is the subdivision constant ($a = 2/3$). The authors prove that if a cell with $n$ nodes is split into $n^{1-a}$ sub-cells, the communication cost remains balanced across all levels of the hierarchy.
Key Insights and Scaling Laws
- Reduced Hop Distance: In path averaging, messages might travel $O(n^{1/2})$ hops (the network diameter). Multiscale Gossip limits the longest trip to $O(n^{1/3})$ hops. Shorter paths mean fewer retransmissions and higher reliability in lossy wireless environments.
- Load Balancing: Unlike path-based methods that create traffic bottlenecks at the center of the network, Multiscale Gossip distributes the communication load almost uniformly across all nodes.
- Near-Linear Scaling: The algorithm achieves $\epsilon$-accuracy with $O(n \log \log n \log \frac{1}{\epsilon})$ messages, which is practically indistinguishable from purely linear scaling for any realistic network size.
Results and Discussion
Simulations conducted on Random Geometric Graphs and 2D grids (ranging from 500 to 8,000 nodes) verify the efficiency of the scheme. Multiscale Gossip consistently uses fewer total transmissions than path averaging to reach a target accuracy of $0.0001$. Furthermore, in a "handshake" model where failed transmissions are retried, the algorithm is significantly faster because its shorter paths have a much higher probability of successful end-to-end delivery.
While the current version assumes node synchronization and static topologies, future work could adapt this to mobile networks via dynamic re-partitioning or utilize spectral clustering for more irregular network shapes.
Summary updated