PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Maximum Likelihood Sensor Network Localization

Andrea Simonetto, Geert Leus

arXiv:1309.2502v2cs.IT

TL;DR

Sensor network localization is difficult because its ML formulation is generally non-convex, while existing convex relaxations do not comprehensively characterize noise-model effects or distributed convergence guarantees. The paper develops noise-dependent ML convex relaxations, an edge-based formulation, and a distributed ADMM algorithm that reaches the centralized solution using local neighbor communication and remains robust to asynchrony and computation errors.

  • Problem

    Existing ML-based relaxations do not comprehensively characterize how different measurement-noise PDFs affect performance, and distributed methods lack broad convergence and robustness guarantees for asynchronous, computation-limited sensor networks.

  • Method

    The paper derives a noise-dependent ML convex relaxation, converts it to an edge-based formulation, and solves it distributively with ADMM using communication among neighboring sensors.

  • Results

    The ADMM algorithm converges to the centralized solution at O(1/t), with network-size-independent local communication cost, and is proven robust to asynchronous communication and computation errors.

  • Takeaways & Limitations

    Relaxation tightness can matter more than exact noise-model correctness, while ADMM provides convergence and robustness properties suited to real and large-scale sensor networks.

Abstract

from arXiv · show

We propose a class of convex relaxations to solve the sensor network localization problem, based on a maximum likelihood (ML) formulation. This class, as well as the tightness of the relaxations, depends on the noise probability density function (PDF) of the collected measurements. We derive a computational efficient edge-based version of this ML convex relaxation class and we design a distributed algorithm that enables the sensor nodes to solve these edge-based convex programs locally by communicating only with their close neighbors. This algorithm relies on the alternating direction method of multipliers (ADMM), it converges to the centralized solution, it can run asynchronously, and it is computation error-resilient. Finally, we compare our proposed distributed scheme with other available methods, both analytically and numerically, and we argue the added value of ADMM, especially for large-scale networks.

EDICS Category: SEN-DIST, SEN-COLB

The paper formulates sensor network localization as a maximum-likelihood problem and develops convex, edge-based relaxations that support distributed solution by neighboring sensors. It addresses the non-convex, NP-hard formulation by analyzing noise-dependent relaxation tightness and an ADMM algorithm designed for scalable, asynchronous, and computation-limited networks.

  • Motivation: Existing ML-based convex relaxations lack a comprehensive characterization across noise models and often focus mainly on Gaussian noise.The paper identifies this as a gap in understanding how the noise PDF affects relaxation performance.
  • Convex relaxations: The proposed relaxation class is derived from the ML formulation, depends on the measurement-noise PDF, and is transformed into an edge-based program for lower computation and distribution.Under log-concave sensing PDFs, the objective becomes convex after variable changes, while Schur complements relax the remaining non-convex constraints.
  • Convex relaxations: Relaxation tightness can affect the performance of the edge-based program more than correctness of the noise model.The paper specifically relates this effect to whether the relaxation is derived from a rank-D relaxation.
  • Distributed algorithm: ADMM enables sensors to solve the edge-based relaxation using only neighboring communication, without requiring knowledge of the whole network.The communication graph connects sensors with available range measurements, and each node communicates only with its neighbors.
  • Distributed algorithm: The distributed ADMM algorithm converges to the centralized solution at O(1/t) and remains convergent under asynchronous communication and computation errors.Its per-iteration computation and communication depend on neighborhood size rather than total network size.
  • Problem: Sensor network localization estimates node positions from noisy inter-sensor and anchor measurements, but the likelihood formulation is generally non-convex and NP-hard.The network may be anchor-free, and positions can in some cases be determined only up to an orthogonal transformation.

III. CONVEX RELAXATIONS

The paper constructs ML-based convex relaxations by introducing auxiliary variables, rewriting the objective, and relaxing non-convex constraints. The resulting programs remain noise-model dependent and can have different tightness properties.

  • Maximum Likelihood Relaxation: The derivation introduces Y = X^TX and stacked distance-related variables before rewriting the ML objective in terms of scalar measurement variables.The variables are then linked back to X and the auxiliary variables through constrained optimization.
  • Maximum Likelihood Relaxation: Schur-complement manipulations convert the non-convex constraint set into a convex relaxation whose objective remains convex under the stated assumption.The original constraints impose pairwise distance relations and enforce the change of variables.
  • Maximum Likelihood Relaxation: The convex program is a rank relaxation, and its optimum provides a lower bound for the original non-convex ML estimator.The relaxed constraints replace the corresponding original constraints with rank-relaxed versions.
  • Maximum Likelihood Relaxation: The ML formulation models the noise distribution, while rank-D formulations based only on squared distances generally do not capture that distribution.For common noise PDFs, the ML relaxation can also be transformed into a rank-D relaxation.
  • Maximum Likelihood Relaxation: Tighter relaxations may yield lower position-estimation error even when their noise models are less accurate.The paper discusses this relationship through simulation results.
  • Gaussian Noise Relaxation: Under Gaussian noise, the resulting semidefinite program is a rank-D relaxation of the original non-convex optimization problem.The proof establishes that the relaxed constraints become equivalent to the original constraints at optimality.

C. Example 2– Quantized Observation Relaxation

The quantized-observation relaxation incorporates interval-valued measurement outcomes into the ML convex program. Its rank properties depend on the noise model: Gaussian quantized measurements admit rank-D relaxation, whereas Laplacian noise does not.

  • Quantized Observation Relaxation: Quantized range and anchor measurements are represented by one-hot indicators over the cells of a convex tessellation of R+.Each indicator records whether a measurement lies in its corresponding quantization set.
  • Quantized Observation Relaxation: The quantized-observation cost is convex because integrating a log-concave function over a convex set preserves log-concavity.The resulting cost is used in the convex relaxation with the standard relaxed constraints.
  • Quantized Observation Relaxation: The general quantized-observation relaxation is a rank relaxation but not generally a rank-D relaxation.With Gaussian noise and the corresponding variable enforcement, it becomes a rank-D relaxation.
  • Laplacian Noise Relaxation: The Laplacian-noise ML relaxation correctly models Laplacian PDFs but is neither rank-D nor transformable into a rank-D relaxation by variable enforcement.Laplacian noise is used to model outliers and signal-interference errors in range measurements.

E. Example 4- Uniform Noise Relaxation

The uniform-noise ML convex relaxation correctly models bounded measurement errors, but it is not a rank-D relaxation. Edge-based relaxations address distributed-solution challenges caused by long-range semidefinite coupling and high centralized complexity.

  • Uniform Noise Relaxation: Uniform noise PDFs model measurements when the error source is unknown and only a noise-level bound is available.The relaxation uses intervals centered at measured distances, with bounds ±σ for sensor-sensor and anchor-sensor measurements.
  • Uniform Noise Relaxation: The uniform-noise ML relaxation is neither rank-D nor transformable into one through cost-function variable enforcement.It nevertheless correctly models uniform noise distributions.
  • Edge-Based Relaxation: The original convex relaxations couple arbitrarily distant sensors through an LMI constraint, complicating distributed optimization.The edge-based relaxation retains the coupling constraint only on graph edges, following the ESDP idea.
  • Edge-Based Relaxation: At least O(n^3) complexity makes the centralized semidefinite program potentially infeasible for large-scale networks.The edge-based relaxation is introduced to reduce the difficulty of handling the long-range coupling constraint.
  • Distributed Solution: ADMM solves the edge-based convex relaxation while converging to the centralized optimizer at O(1/t).The algorithm also supports asynchronous communication and computation errors, with per-node work depending only on neighborhood size.

VI. PROPOSED DISTRIBUTED APPROACH

The edge-based relaxation is reformulated into local variables and convex sets so that shared edge variables become the only complicating variables. This structure makes the problem suitable for distributed ADMM optimization.

  • Problem Reformulation: The compact reformulation introduces shared edge vectors and local vectors assembled from neighboring measurement variables.Each node maintains local views of shared vectors associated with adjacent nodes.
  • Problem Reformulation: Local convex sets P_i encode the constraints each node must satisfy through the condition P_i := {p_i|p_i verifies (6c)}.The global vector p stacks the local vectors, while z stacks the edge variables.
  • ADMM Structure: The optimization is separable, with z_i,j acting as the complicating variables linking local subproblems.This separability motivates using ADMM to coordinate neighboring computations.
  • ADMM Structure: The proposed distributed approach targets the edge-based convex relaxation rather than the original non-convex localization problem.The paper contrasts this formulation with prior methods that directly address the non-convex problem or rely on other decomposition techniques.

B. Proposed Algorithm

The algorithm applies ADMM to the reformulated edge-based problem through alternating local convex updates and neighbor exchanges. Its implementation uses only neighborhood information while preserving convergence to the centralized solution.

  • Algorithm Definition: ADMM is applied by defining a regularized Lagrangian for the reformulated problem with parameter ρ > 0.The recursion initializes y, p, z, and λ, then iterates the ADMM updates.
  • Distributed Iterations: Each node updates local variables, sends its local y_i,j vector to neighboring nodes, and computes shared edge quantities from exchanged values.The distributed recursion assigns local variables to nodes and communicates only across graph neighborhoods.
  • Distributed Iterations: The shared edge variable z_i,j is consistent across the two nodes incident to edge (i,j) when transmitted local vectors agree.The algorithm explicitly notes equality between the values computed by the two neighboring nodes.
  • Local Subproblems: The local ADMM subproblems are convex: one is an SDP and the other is an unconstrained quadratic program in z_i,j.The quadratic program has a direct solution, while the SDP can be solved with standard convex optimization toolboxes.
  • Local Subproblems: Slack variables γ_i,j impose the quadratic penalty in the SDP-form local subproblem.The derivation simplifies the multiplier computations because λ_i,j is no longer needed for computing z_i,j.

C. Properties of Algorithm 1 (Ideal)

Algorithm 1 converges to the centralized optimizer at an O(1/t) ergodic rate, with iteration and communication requirements characterized by local initialization and neighborhood size. Its ideal analysis assumes synchronous communication and exact local optimization, while establishing accuracy and communication bounds.

  • Complexity: The analysis characterizes both the iterations required for a target accuracy and the total communication cost.These quantities are analyzed for Algorithm 1’s solution to the centralized convex problem.
  • Accuracy: The iteration count needed for a given average local accuracy depends on the worst local initial error, not the network size.This is stated under the proposition’s initialization and connected-graph premises.
  • Communication: Each node’s communication cost to reach accuracy η is lower bounded by c_i ≥ 9|N_i|t_η.The per-iteration communication count is tied to the node’s neighborhood size.
  • Assumptions: The ideal O(1/t) guarantee assumes perfect synchronous communication and exact solution of the local optimization subproblems.The paper identifies asynchronous communication and limited computation as restrictive real-world conditions considered separately.

D. Properties of Algorithm 1 (Asynchronous)

The asynchronous version activates only subsets of edges at each iteration and, under stated stochastic connectivity assumptions, converges to the centralized optimizer. The analysis models communication through an edge-set perspective with recurring network connectivity.

  • Asynchronous model: The asynchronous algorithm updates and communicates only through the subset of edges active at each iteration.The active edge set E(t) defines the iteration-specific communication pattern.
  • Asynchronous model: The asynchronous analysis uses a symmetric adjacency matrix to represent the active edge set at each iteration.This edge-set perspective supports communication over changing subsets of links.
  • Assumptions: The stochastic assumptions require every existing edge to have positive activation probability and the active graphs to regain connectivity over bounded windows.These are the conditions used to state convergence under asynchronous communication.

E. Properties of Algorithm 1 (Computation errors)

When local subproblems are solved only approximately, Algorithm 1 retains an O(1/t) convergence pattern but approaches an error floor proportional to nε. The comparison framework includes analytical results for distributed algorithms applied to the E-ML formulation.

  • Approximate computation: The computation-error analysis assumes that every subproblem (18a) is solved up to a prescribed accuracy ε.The approximate solution condition is the premise for Theorem 3.
  • Comparison: Table I compares available distributed algorithms analytically, including SGO and ADMM applied to the E-ML formulation.The table is presented as an analytical comparison of distributed methods.
  • Approximate computation: With each local subproblem solved to accuracy ε, Algorithm 1 converges as O(1/t) to an error floor of magnitude nε.The result follows under the stated approximate-subproblem condition.

F. Comparison of Algorithm 1 with Alternatives

Compared with SGO and MVU, ADMM is presented as especially attractive for large-scale networks because it supports parallel local computation and faster convergence with limited additional communication. Its local workload and communication depend on neighborhood size rather than the full network.

  • ADMM complexity: The most complex E-ML ADMM local operation has computational complexity at least O((|N_i| + |N_{i,a}|)^3).The local convex program contains neighborhood-scaled variables, constraints, and small LMIs.
  • ADMM complexity: Each E-ML ADMM iteration sends 9|N_i| scalar values per sensor node.Each node sends an updated vector in R^9 to each neighbor.
  • SGO: SGO is sequential, lacks a formal convergence-rate proof, and has no established noise- or computation-error resilience in the cited comparison.The comparison considers SGO applied to the E-ML formulation.
  • MVU: MVU is parallel but requires each node eventually to locate all others and has per-node complexity at most O(|N_i|^2) with communication at most O(|N_i|).MVU uses a primal-dual scheme with a nested consensus step and cannot handle anchors.
  • Overall comparison: ADMM’s convergence rate is presented as advantageous for large-scale networks, with only a limited increase in communication cost.The communication increase can be tuned through neighborhood size.
  • SGO: Coloring-based partial parallelization of SGO can require between O(log(n)) and O(n exp(n)) iterations to compute decentralized bounds.This iteration range is cited as undermining coloring techniques for large-scale settings.

VII. NUMERICAL SIMULATIONS

The simulations compare E-ML and other convex relaxations under Gaussian and Laplacian noise, varying network size and measurement noise. They evaluate localization accuracy using PRMSE, maximum error, and CRLB benchmarks.

  • Simulation setup: The simulations use PRMSE, worst-case maximum error, and the CRLB to evaluate localization performance.The benchmark is applied to two-dimensional test10-500 networks over multiple noise realizations.
  • Gaussian noise: E-ML slightly outperforms ESDP under Gaussian noise when either sensor count or measurement noise is varied.With fixed σi,j = σi,k,a = 0.1, increasing n reduces average error and narrows the difference; with n = 8, the gap increases with noise.
  • Gaussian noise: The Gaussian comparisons vary sensor count with fixed σi,j = σi,k,a = 0.1 and vary noise standard deviation with fixed n = 8.Both comparisons use the E-ML relaxation and the ESDP relaxation of.
  • Laplacian noise: Under Laplacian noise, the Laplacian E-ML, Gaussian E-ML, and ESDP relaxations are compared across sensor counts and noise values.The modified CRLB of is used because Laplacian distributions are not differentiable.
  • Laplacian noise: Although it models the Laplacian noise distribution correctly, Laplacian E-ML performs worse than the other convex relaxations.The reported explanation is that it is not derived from a rank-D relaxation.

B. Distributed simulations

Distributed simulations evaluate ADMM-based Algorithm 1 under synchronous and asynchronous communication, computation inaccuracies, and varying network sizes. The results support its O(1/t) convergence, practical localization accuracy, and convergence to the centralized optimizer.

  • Synchronous case: Algorithm 1 converges more quickly than sequential SGO in large-scale settings while remaining resilient to computation inaccuracies in the reported simulations.SGO may be suitable for small networks, but further studies are needed to certify its reliability across broader scenarios.
  • Synchronous case: After 400 iterations, the running-averaged position estimates are practically coincident with the real sensor node positions.The trajectories start from X(0) = 0 and use Algorithm 1 in its exact form.
  • Asynchronous case: With asynchronous communication, Algorithm 1 converges to the optimal primal solution of the centralized E-ML problem.The experiment varies the number of sensor nodes and the communication probability sij.
  • Algorithm scope: The distributed algorithm is motivated by ADMM properties including convergence-rate analysis, asynchronism resilience, and computation-error resilience.The paper presents these properties as especially valuable for large networks.
Loading 1309.2502v2…