Distributed Consensus Over Wireless Sensor Networks Affected by Multipath Fading

Gesualdo Scutari, Sergio Barbarossa

Abstract

The design of sensor networks capable of reaching a consensus on a globally optimal decision test, without the need for a fusion center, is a problem that has received considerable attention in the last years. Many consensus algorithms have been proposed, with convergence conditions depending on the graph describing the interaction among the nodes. In most works, the graph is undirected and there are no propagation delays. Only recently, the analysis has been extended to consensus algorithms incorporating propagation delays. In this correspondence, we propose a consensus algorithm able to converge to a globally optimal decision statistic, using a wideband wireless network, governed by a fairly simple MAC mechanism, where each link is a multipath, frequency-selective, channel. The main contribution of the correspondence is to derive necessary and sufficient conditions on the network topology and sufficient conditions on the channel transfer functions guaranteeing the exponential convergence of the consensus algorithm to a globally optimal decision value, for any bounded delay condition.

Introduction

In the field of distributed systems, achieving a "global consensus"—a state where every node in a decentralized network agrees on a single, mathematically optimal decision—is often considered a primary objective. In Wireless Sensor Networks (WSNs), achieving this without a central "brain" or fusion center is notoriously difficult. While theoretical consensus algorithms abound, they frequently rely on idealized assumptions: undirected graphs, perfect links, and zero propagation delay.

This research addresses the practical realities of WSNs, where signals bounce off obstacles (multipath fading), links are often asymmetric, and signal travel time (propagation delay) is non-negligible. The authors propose a robust algorithm designed to reach a globally optimal decision statistic even under these severe conditions.

The Problem: Real-World Network Constraints

In a perfect environment, distributed consensus is straightforward: nodes simply average their values with their neighbors until everyone reaches the same number. However, physical wireless channels introduce several complications:

  1. Multipath Fading: Signals reflect off the environment, creating frequency-selective interference.
  2. Asymmetry: Communication links are often one-way or vary in strength, meaning node A might hear node B better than vice versa.
  3. Propagation Delays: The time it takes for a signal to travel between nodes can cause standard algorithms to oscillate or fail to converge entirely.

Most existing algorithms only reach a general "agreement" (a common value) rather than the "globally optimal decision"—the specific value a central computer would have calculated if it had access to all raw data simultaneously.

Methodology: Consensus on the State Derivative

The key innovation of this paper is the shift from synchronizing sensor states ($x_i$) to synchronizing the state derivatives ($\dot{x}_i$).

Linear Interaction Model

The authors introduce a model based on differential equations where each node updates its state based on its local measurement and a weighted sum of the differences between its own state and the delayed states of its neighbors. By forcing the rate of change of each sensor's state to converge to a common value, the system becomes remarkably resilient to the stability issues usually triggered by propagation delays.

Handling Channel Interference and Bias

To manage the inherent "noise" of the wireless medium, the paper employs two strategic approaches:

  • Multipath Modeling: Each link is treated as a frequency-selective filter (FIR filter), allowing the algorithm to treat multipath components as part of the signal rather than just interference.
  • Two-Step Bias Compensation: Because channel delays and amplitudes naturally bias the final result, the authors propose a two-step protocol. The network runs the algorithm twice—once with the actual data and once with a constant reference input. By taking the ratio of these two results, each node can implicitly cancel out the network's bias without needing to estimate channel coefficients.

Network Topology and Convergence

The paper establishes that for a network to reach consensus, it must be Quasi-Strongly Connected (QSC). In a QSC graph, there is at least one node that has a directed path to every other node in the network.

The authors mathematically prove that if the network is QSC and certain conditions on the channel transfer functions are met, the algorithm will achieve exponential convergence. Crucially, this convergence is guaranteed for any set of finite propagation delays, meaning the delay might slow the process but will never prevent the final agreement.

Key Insights

  • Implicit Coherence: The algorithm naturally performs a "coherent combination" of multipath signals, similar to a Rake receiver in traditional communications, but distributed across the entire network.
  • Minimal MAC Requirements: Because the algorithm accepts linear combinations of signals, it does not require complex Medium Access Control (MAC) protocols to prevent "collisions." Nodes can transmit simultaneously, and the mathematical framework still holds.
  • Optimality: Through the compensation technique, the decentralized network reaches the exact same decision statistic as a centralized system with error-free access to all data.

Results and Limitations

Numerical simulations using 14-node topologies confirmed the theoretical findings. Even when propagation delays were set to 30 times the sampling time, the algorithm remained stable and accurate.

However, some practical limitations remain:

  • Channel Stationarity: The method assumes a "slowly varying" channel. If sensors or environmental obstacles move too quickly, the algorithm may not reach consensus before the channel state changes.
  • Coordination Overhead: The requirement to run the process twice for bias compensation adds energy and time costs.
  • Hardware Implementation: While the mathematical foundation is solid, further study is required to map these differential equations to physical radio signals, such as Impulse Radio Pulse-Position Modulation.

Summary updated

Abstract

The design of sensor networks capable of reaching a consensus on a globally optimal decision test, without the need for a fusion center, is a problem that has received considerable attention in the last years. Many consensus algorithms have been proposed, with convergence conditions depending on the graph describing the interaction among the nodes. In most works, the graph is undirected and there are no propagation delays. Only recently, the analysis has been extended to consensus algorithms incorporating propagation delays. In this correspondence, we propose a consensus algorithm able to converge to a <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">globally</i> <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">optimal</i> decision statistic, using a <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">wideband</i> wireless network, governed by a fairly simple MAC mechanism, where each link is a multipath, frequency-selective, channel. The main contribution of the correspondence is to derive necessary and sufficient conditions on the network topology and sufficient conditions on the channel transfer functions guaranteeing the exponential convergence of the consensus algorithm to a globally optimal decision value, for <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">any</i> bounded delay condition.
BibTeX
@article{scutari2008distributed,
  author = {Gesualdo Scutari and Sergio Barbarossa},
  title = {{Distributed Consensus Over Wireless Sensor Networks Affected by Multipath Fading}},
  journal = {IEEE Trans. Signal Process.},
  year = {2008},
  url = {https://openreview.net/forum?id=re0V9YnDNON},
}
Figure