PaperlayerView exact revision on arXiv

Source-linked AI summary

Likelihood Consensus and Its Application to Distributed Particle Filtering

Ondrej Hlinka, Ondrej Sluciak, Franz Hlawatsch, Petar M. Djuric, Markus Rupp

arXiv:1108.6214v4stat.APcs.IT

TL;DR

The paper addresses global state estimation in wireless sensor networks without a fusion center, where each sensor needs the joint likelihood of all measurements. It proposes likelihood consensus to compute an approximate JLF locally, then uses it in distributed particle filters; simulations show performance close to centralized particle filters in multiple-target tracking.

  • Problem

    Global particle filtering without a fusion center requires every sensor to know the joint likelihood function while using only local processing and neighbor communication.

  • Method

    Likelihood consensus uses iterative consensus algorithms to compute an approximate JLF at each sensor for exponential-family local likelihoods, then supplies particle-weight updates in distributed particle filters.

  • Results

    In multiple-target tracking, the proposed distributed particle filters achieved performance close to centralized particle filters.

  • Takeaways & Limitations

    Likelihood consensus enables each sensor to compute a global state estimate from all sensors’ measurements using local neighbor communications.

Abstract

from arXiv · show

We consider distributed state estimation in a wireless sensor network without a fusion center. Each sensor performs a global estimation task---based on the past and current measurements of all sensors---using only local processing and local communications with its neighbors. In this estimation task, the joint (all-sensors) likelihood function (JLF) plays a central role as it epitomizes the measurements of all sensors. We propose a distributed method for computing, at each sensor, an approximation of the JLF by means of consensus algorithms. This "likelihood consensus" method is applicable if the local likelihood functions of the various sensors (viewed as conditional probability density functions of the local measurements) belong to the exponential family of distributions. We then use the likelihood consensus method to implement a distributed particle filter and a distributed Gaussian particle filter. Each sensor runs a local particle filter, or a local Gaussian particle filter, that computes a global state estimate. The weight update in each local (Gaussian) particle filter employs the JLF, which is obtained through the likelihood consensus scheme. For the distributed Gaussian particle filter, the number of particles can be significantly reduced by means of an additional consensus scheme. Simulation results are presented to assess the performance of the proposed distributed particle filters for a multiple target tracking problem.

I. INTRODUCTION

The paper targets global state estimation in wireless sensor networks without a fusion center, where each sensor must access the all-sensors likelihood using local computation and neighbor communication. It introduces likelihood consensus and applies it to distributed particle-filtering methods.

  • Motivation: Centralized estimation can suffer poor scalability, reduced robustness, and limited local availability because sensor data must reach a fusion center.Decentralized approaches instead use in-network processing and neighbor-to-neighbor communication.
  • Problem: Each sensor performs a global estimation task using all sensors’ measurements, requiring knowledge of the joint likelihood function (JLF).A global particle filter evaluates the JLF at particles during weight updates.
  • Contribution: Likelihood consensus computes the JLF or its approximation at every sensor using consensus sums for exponential-family local likelihoods.The method supports local processing and communications among neighboring sensors.
  • Distributed filtering: Each sensor runs a local particle filter or Gaussian particle filter that incorporates all sensor measurements into a global state estimate.The approximate JLF supplies the particle-weight updates at each sensor.
  • Scope: The method also applies to distributed statistical inference tasks requiring pointwise JLF evaluation at individual sensors.Distributed sequential Bayesian estimation and particle filtering are presented as motivating applications.

III. APPROXIMATION OF THE JOINT LIKELIHOOD FUNCTION

This section develops an approximation that converts state-dependent local likelihood terms into a form whose global coefficients can be computed by consensus. The resulting sufficient statistic describes the approximate JLF as a function of the state.

  • Exponential-family model: Likelihood consensus applies generally when local likelihood functions belong to the exponential family, typically requiring approximation of the local likelihoods and JLF.Additive Gaussian measurement noise is included, while a special class can avoid approximation.
  • Motivation: Direct consensus cannot generally calculate the state-dependent sum because its terms depend on the unknown state.The method therefore approximates state-dependent functions using shared basis functions.
  • Sufficient statistic: The combined coefficients form a sufficient statistic that fully describes the approximate JLF as a function of the state within the approximation.A sensor can evaluate the approximate JLF for all state values once it knows these coefficients.
  • Distributed representation: After substitution and rearrangement, the approximate JLF depends on coefficient sums containing only local sensor information and state-independent coefficients.The state enters only through sensor-independent, commonly known basis functions.
  • Basis expansion: Basis expansions approximate the local exponential-family functions, with monomials, orthogonal polynomials, and Fourier functions offering different accuracy and communication trade-offs.Polynomial approximation is developed as a concrete example.

C. Least Squares Approximation

Least-squares fitting estimates the coefficients of the basis expansions from state–function-value pairs selected to cover regions where the JLF will be evaluated. In distributed particle filtering, the predicted particles provide those state points.

  • Coefficient fitting: Least-squares fitting calculates basis-expansion coefficients by minimizing the sum of squared approximation errors at selected state points.The coefficient matrix provides the corresponding fitted vectors.
  • State-point selection: The selected state points should cover regions of state space where the JLF is expected to be evaluated.For distributed particle filtering, these points are the predicted particles.
  • Conditions: The number of fitting points must satisfy J ≥ Ra for the an,k approximation and J ≥ Rd for the dn,k approximation.Together, the stated requirement is J ≥ max{Ra, Rd}.

IV. LIKELIHOOD CONSENSUS

The LC algorithm uses synchronized consensus iterations to aggregate state-independent coefficient sums at every sensor. After convergence, each sensor can evaluate the approximate JLF locally for any state value.

  • Communication: Consensus iterations use neighbor states and broadcasts, requiring only local communications and no routing protocol.The network must be connected for the local states to converge to the network average.
  • Convergence: After convergence, the consensus states recover the global coefficient sums, enabling every sensor to construct the approximate JLF.Finite iterations produce an approximation whose accuracy depends on the chosen iteration count.
  • Algorithm: The LC algorithm runs one consensus process for each coefficient An,r(zn) and Γn,r, with all processes executed simultaneously.Each sensor initializes local states from its own measurements and approximation coefficients, then exchanges states with neighbors.
  • Complexity: The LC algorithm executes Nc = Ra + Rd consensus algorithms and broadcasts the same number of real numbers per iteration.Communication requirements do not depend on measurement dimension Nn,k, although Ra and Rd generally grow with state dimension and approximation complexity.
  • Normalization: The normalization factor Cn(zn) can also be computed distributively through consensus when required.Its logarithm is obtained from a sum of locally known terms.

B. Distributed Calculation of the Exact JLF

The paper shows that a structured joint likelihood function can be computed exactly in a distributed manner, aside from errors from limited consensus iterations. This relies on sufficient statistics decomposable into sums of sensor-local terms.

  • B. Distributed Calculation of the Exact JLF: The exact JLF can be computed distributively when it has a special structure, avoiding the basis expansion approximations.The remaining errors are due only to the limited number of consensus iterations.
  • B. Distributed Calculation of the Exact JLF: A sufficient statistic captures the total measurement because it lets a sensor evaluate the JLF for any state value, up to an irrelevant factor.This follows from the Neyman-Fisher factorization, with the state-independent factor typically disregarded.
  • B. Distributed Calculation of the Exact JLF: Each statistic component is a sum of sensor-local functions, so neighboring-sensor consensus can calculate the statistic and hence the JLF.Each sensor knows its own local functions but not those of other sensors.
  • B. Distributed Calculation of the Exact JLF: The exponential-family case is an example in which the exact JLF calculation is possible when the relevant functions admit exact basis expansions.This case is compatible with, but does not exhaust, the broader special structure described.

V. SPECIAL CASE: GAUSSIAN MEASUREMENT NOISE

The Gaussian-noise special case models each measurement as a nonlinear sensor function plus independent additive Gaussian noise. The resulting likelihood remains suitable for likelihood consensus, with indirect coefficient calculation reducing computational complexity.

  • V. SPECIAL CASE: GAUSSIAN MEASUREMENT NOISE: Measurements are modeled as zn,k = hn,k(xn) + vn,k, with zero-mean Gaussian noise independent across sensor-time pairs and of the state.These assumptions make measurements conditionally independent given xn.
  • V. SPECIAL CASE: GAUSSIAN MEASUREMENT NOISE: Conditional independence yields the JLF as the product of the local Gaussian likelihood functions, placing the model within the exponential family.The local likelihood is identified as a special case of the exponential-family form.
  • V. SPECIAL CASE: GAUSSIAN MEASUREMENT NOISE: Truncated basis expansions approximate the measurement function and the associated likelihood terms in the Gaussian model.Approximating the measurement function is equivalent to approximating the likelihood mean; the second term can then be obtained indirectly.
  • V. SPECIAL CASE: GAUSSIAN MEASUREMENT NOISE: Indirect coefficient calculation reduces computational complexity compared with directly calculating the coefficients, although the resulting coefficients can differ.The resulting approximate JLF is nevertheless a valid pdf, integrating exactly to one.
  • V. SPECIAL CASE: GAUSSIAN MEASUREMENT NOISE: The number of consensus algorithms is Nc = Ra + Rd = Ra + R2a and does not depend on the measurement-vector dimensions Nn,k.This follows because Ra does not depend on Nn,k.

B. Polynomial Approximation

The polynomial approximation applies basis expansions to the Gaussian-measurement likelihood representation. Its coefficients can be computed by consensus, with one state-independent coefficient omitted as irrelevant.

  • B. Polynomial Approximation: The polynomial approximation is applied to the Gaussian-measurement case to construct approximations of the likelihood representation.The construction uses the basis-expansion relation introduced earlier.
  • B. Polynomial Approximation: The coefficients Bn,r(zn) in the polynomial representation can be calculated using a consensus algorithm.This produces parallel consensus computations for the coefficients at each time n.
  • B. Polynomial Approximation: The coefficient Bn,0(zn) is omitted because it corresponds to a JLF factor independent of xn and is therefore irrelevant.The number of required consensus computations is reduced by one.

A. Review of Centralized Particle Filtering

The distributed particle filter has each sensor maintain a particle representation of the global posterior and estimate the state from all sensors’ measurements. Likelihood consensus supplies the JLF approximation needed for local weight updates.

  • A. Review of Centralized Particle Filtering: At each time step, new particles and weights are calculated using the particle-filter recursion after the measurement vector becomes available.The centralized filter assumes access to all-sensor measurements and the JLF.
  • A. Review of Centralized Particle Filtering: A centralized sequential importance resampling filter initializes particles from a prior and repeatedly performs resampling, sampling, and weight updating.The weighted particles approximate the posterior, whose mean provides an MMSE state estimate.
  • Distributed PF: Each sensor runs a local PF that tracks the global posterior and produces a state estimate based on the past and current measurements of all sensors.Thus, every sensor locally computes a global estimate without a fusion center.
  • Distributed PF: Likelihood consensus provides each sensor with an approximate JLF for pointwise evaluation during local particle-weight updates.Only broadcasts to neighboring sensors are needed; measurements and other local data are not routed.
  • Distributed PF: Differences between sensors’ state estimates arise from nonsynchronized particle sampling and insufficiently converged consensus algorithms.The distributed recursion is initialized independently at each sensor with prior-sampled particles and equal weights.

C. Communication Requirements

The LC-DPF replaces measurement dissemination with consensus-based likelihood computation, making communication independent of measurement dimension but increasing local computation and introducing approximation loss.

  • Communication requirements: Centralized PF communication can deplete batteries of sensors near the fusion center because multihop data pass through them.
  • Communication requirements: The LC-DPF transmits KINc real numbers per time n, independent of measurement dimensions Nn,k.I is the number of consensus iterations, and Nc is the number of parallel consensus algorithms.
  • Communication-computation trade-off: The LC-DPF performs more local computation than the S-DPF because each sensor computes an approximate JLF.The additional computation is especially relevant for high-dimensional measurements or likelihood parametrizations.
  • Communication-computation trade-off: Lower communication energy can extend network lifetime, but approximate JLFs cause performance loss relative to the CPF or S-DPF.
  • Distributed Gaussian PF: The distributed Gaussian PF tracks each sensor’s global posterior approximation through a local mean and covariance estimate.

B. Reduced-Complexity Method

The reduced-complexity LC-DGPF distributes particles across sensors and combines their partial estimates by consensus, substantially reducing local computation while retaining the virtual global particle count.

  • Reduced-complexity method: Each sensor uses J′ = J/K particles, and consensus combines local particle sets into a virtual global GPF with J = KJ′ particles.The method distributes particles that the original LC-DGPF would use separately at every sensor.
  • Trade-off: Using J′ particles reduces local GPF and likelihood-fitting complexity, while added consensus communication offsets part of the savings.
  • Algorithm: Local processing samples particles, evaluates approximate-JLF weights, and forms partial means and correlations before global consensus.
  • Algorithm: All sensors obtain identical state estimates and covariances when the consensus algorithms sufficiently converge.The shared estimate is denoted ˆxn = µn and covariance Cn.
  • Trade-off: Using only J′ predicted particles for local least-squares fitting makes the approximate local likelihoods and JLF less accurate, causing some performance degradation.The paper states that simulations show this degradation is very small.

C. Computational Complexity and Communication Requirements

The reduced-complexity method trades computation for consensus communication and can reduce latency or power use depending on operating priorities, while high-dimensional states increase its communication burden.

  • Computational complexity: Reducing particles from J to J′ = J/K reduces local GPF and least-squares approximation complexity by a factor of K.
  • Communication requirements: R-LC-DGPF communication overhead depends mainly on the convergence speed of its additional consensus algorithms.
  • Communication requirements: The additional consensus count scales as N′c = M + M(M + 1)/2 + 1, making R-LC-DGPF disadvantageous for high-dimensional states.
  • Trade-off: Reduced operation count can lower latency or power consumption, but faster processing raises power use through increased communications.
  • Simulation context: The simulations track multiple independently moving targets with acoustic amplitude sensors and compare proposed distributed filters with centralized and state-of-the-art distributed PFs.

B. Simulation Setting

The simulations evaluate proposed distributed particle filters in a 25-sensor acoustic tracking network, using RMSE-based accuracy and cross-sensor variation measures over repeated runs.

  • Target and dynamics: Simulations use P = 2 targets unless otherwise stated, with identical system matrices and equal known target amplitudes Ap = 10.
  • Illustration: Figure 1 visualizes the network topology, local and joint likelihoods for one target, and two-target trajectories tracked by the LC-DPF.
  • Network and model: The network contains K = 25 acoustic amplitude sensors on a jittered 40m × 40m grid, with an 18m communication range.
  • Consensus configuration: Likelihood consensus uses a degree-Rp = 2 polynomial approximation, 69 parallel consensus algorithms, and I = 8 iterations unless noted otherwise.
  • Compared methods: The comparison includes LC-DPF, LC-DGPF, R-LC-DGPF, CPF, CGPF, and other distributed PFs, with J = 5000 generally and J′ = 200 for R-LC-DGPF.
  • Evaluation metrics: Performance is measured using time-dependent RMSE, average RMSE over 200 time instants, and standard deviation of sensor-dependent error across 5000 simulation runs.

C. Simulation Results

Simulations show that the proposed distributed particle filters achieve estimation performance close to centralized filters and generally comparable to or better than competing distributed methods. Communication costs are method- and setting-dependent, while additional consensus can reduce Gaussian-filter particle counts and approach exact-sum performance.

  • Estimation performance: The proposed distributed PFs achieve track loss adjusted ARMSEs close to centralized methods and generally comparable to or better than competing distributed PFs.Their performance is slightly worse than FRG-DPF, slightly better than OC-DPF, and about half that of GSHL-DPF.
  • Communication requirements: Distributed PFs require more communication than centralized methods in the reported low-dimensional measurement setting, but their relative costs vary across algorithms.The proposed methods communicate more than GSHL-DPF and OC-DPF, less than FRG-DPF, and R-LC-DGPF costs about 65% more than LC-DPF and LC-DGPF.
  • Estimation performance: LC-DGPF nearly matches FRG-DPF and CGPF in track loss adjusted RMSEn while outperforming GSHL-DPF and OC-DPF.The comparison uses eight consensus iterations for the distributed filters.
  • Consensus effects: Eight consensus iterations cause moderate performance degradation for LC-DPF relative to exact sum calculation, with track loss percentages of 0.95%, 0.29%, and 0% for LC-DPF, exact-sum LC-DPF, and CPF.The degradation arises from the LS approximation and insufficiently converged consensus, respectively.
  • Consensus effects: R-LC-DGPF essentially reaches exact-sum performance at about 7 iterations, whereas LC-DGPF requires about 10 iterations.R-LC-DGPF uses 200 particles instead of 5000 and outperforms LC-DGPF through 10 iterations before LC-DGPF slightly leads at higher iteration counts.
  • Particle reduction: With 400 particles per sensor, R-LC-DGPF uses only 16 particles per sensor, reducing its particle representation but degrading the performance of all methods.The reduced-particle setting also produces high ARMSE and track-loss values for several methods, indicating divergence.
Loading 1108.6214v4…