A distributed classification/estimation algorithm for sensor networks

Technical Summary: A Distributed Classification/Estimation Algorithm for Sensor Networks

Problem Statement
The paper addresses the challenge of simultaneous classification and estimation of hidden parameters within a sensor network subject to communication constraints. The system consists of a network of $N$ noisy sensors measuring a common, unknown scalar parameter $\theta^\star$. A fraction of these sensors are assumed to be "faulty," characterized by a high noise variance, while the remainder are "non-faulty" with low noise variance. The status of each sensor, denoted by $\omega_i^\star \in \{\alpha, \beta\}$, is unknown to the node itself. The objective for each node is to simultaneously estimate the global parameter $\theta^\star$ and identify its own class (faulty or non-faulty) in a fully distributed manner, without a central data fusion center. The measurements follow a Gaussian mixture model where the noise variance depends on the sensor's hidden state.

Methodology
The authors propose a novel cooperative iterative algorithm termed the Input Driven Consensus Algorithm (IA). This approach is designed to approximate the Maximum Likelihood (ML) solution of the centralized problem while adhering to local communication constraints.

The algorithm operates in two alternating steps at each time iteration $t$:

1. Averaging Step (Input Driven Consensus): Nodes update their estimates of $\theta$ using a consensus protocol driven by local inputs rather than initial conditions. Each node $i$ maintains two internal states, $\mu_i^{(t)}$ and $\nu_i^{(t)}$, which are updated by mixing information from neighbors (via a stochastic matrix $P$ adapted to the communication graph) with local weighted measurements. The local estimate is computed as the ratio $\hat{\theta}_i^{(t+1)} = \mu_i^{(t+1)} / \nu_i^{(t+1)}$. The weighting of the local input is controlled by a decaying sequence $\gamma(t)$.
2. Classification Step: Based on the current estimate $\hat{\theta}_i^{(t+1)}$, each node autonomously updates its classification of its own status $\hat{\omega}_i^{(t+1)}$. This is performed via a simple threshold rule: if the measurement $y_i$ is within a distance $\delta$ of the estimated $\theta$, the sensor is classified as non-faulty ($\alpha$); otherwise, it is classified as faulty ($\beta$).

The threshold $\delta$ is derived from the log-likelihood function and depends on the prior probability of faulty sensors and the noise variances.

Key Contributions and Theoretical Results
The paper provides a rigorous theoretical analysis of the proposed algorithm, distinguishing it from existing distributed Expectation-Maximization (EM) approaches where convergence guarantees are often lacking.

• Convergence to Local ML Maximum: Theorem 4.1 establishes that under specific conditions on the step-size sequence $\gamma(t)$ and the communication matrix $P$ (symmetric, stochastic, primitive with positive eigenvalues), the algorithm converges almost surely. The limit estimates $(\hat{\theta}_{IA}, \hat{\omega}_{IA})$ satisfy the fixed-point relations of the centralized ML solution, meaning the algorithm converges to a local maximum of the log-likelihood function $L_N(\theta, \omega)$.
• Asymptotic Consistency: Theorem 4.2 and Corollary 4.3 analyze the behavior as the number of sensors $N \to \infty$. The authors prove that the set of local maxima of the log-likelihood function concentrates around the true parameter $\theta^\star$. Consequently, the distributed estimate $\hat{\theta}_{IA}$ converges to the true value $\theta^\star$ in both the almost sure and mean square senses, matching the performance of the optimal centralized ML estimator in the limit.
• Classification Error Characterization: Proposition 4.4 characterizes the limit of the relative classification error as $N \to \infty$. The error converges to a constant $q(p, \alpha, \beta)$, which is identical to the error of the optimal centralized ML estimator. The paper notes that while the classification error does not vanish as $N \to \infty$ (due to the simultaneous increase in variables to be estimated), it vanishes as the fraction of faulty sensors $p \to 0$ or as the ratio of noise variances $\beta/\alpha \to \infty$.

Numerical Results and Comparisons
The authors validate the theoretical findings through numerical simulations on various graph topologies, including complete graphs, rings, torus-grids, and random geometric graphs.

• Performance: The IA algorithm demonstrates remarkable performance. For small network sizes, IA outperforms both the centralized Iterative Maximum Likelihood (IML) and the centralized EM algorithms in terms of classification error and mean square error. For large networks, its performance becomes comparable to the optimal centralized EM solution.
• Robustness to Topology: While the theoretical convergence proof requires the communication matrix to have positive eigenvalues, simulations on ring graphs (which possess non-positive eigenvalues) suggest that the algorithm converges under weaker conditions than strictly required by the proof.
• Parameter Sensitivity: The choice of the decaying sequence $\gamma(t)$ is critical. The simulations indicate that a slower decay (smaller $\zeta$ in $\gamma(t) = t^{-\zeta}$) can improve classification accuracy, though an excessively slow decay may degrade performance, suggesting a trade-off between consensus speed and input weighting.

Significance
The paper claims significance primarily through the provision of a rigorous convergence proof for a distributed algorithm solving a coupled estimation and classification problem, a feature missing in many distributed EM variants. By utilizing an Input Driven Consensus mechanism, the algorithm effectively leverages the "innovation" from nodes updating their status classifications over time. The results demonstrate that a fully distributed approach can achieve performance asymptotically equivalent to the optimal centralized solution, offering a scalable and energy-efficient alternative for sensor networks where centralized data fusion is impractical. The authors conclude that the strategy offers a favorable trade-off in terms of robustness, convergence speed, and implementation simplicity compared to existing methods.