PaperlayerView exact revision on arXiv

Source-linked AI summary

DILAND: An Algorithm for Distributed Sensor Localization with Noisy Distance Measurements

Usman A. Khan, Soummya Kar, Jose M. F. Moura

arXiv:0910.2743v1cs.DCcs.IT

TL;DR

Distributed sensor localization must remain accurate despite noisy communication, random link failures, and noisy distance measurements. DILAND modifies DLRE by using accumulated measurements and consistent distance estimates, and the paper shows almost-sure convergence to exact sensor locations under these phenomena.

  • Problem

    The problem is distributed localization when communication, links, and distance measurements are noisy or unreliable, with sensors positioned relative to known anchors.

  • Method

    DILAND extends DLRE by using accumulated measurements to form distance estimates for its distributed localization updates.

  • Results

    DILAND converges almost surely to the exact sensor locations under communication noise, random link failures, and noisy distance measurements.

  • Takeaways & Limitations

    The algorithm provides distributed localization that remains exact under the broad random phenomena considered by the paper.

Abstract

from arXiv · show

In this correspondence, we present an algorithm for distributed sensor localization with noisy distance measurements (DILAND) that extends and makes the DLRE more robust. DLRE is a distributed sensor localization algorithm in $\mathbb{R}^m$ $(m\geq1)$ introduced in \cite{usman_loctsp:08}. DILAND operates when (i) the communication among the sensors is noisy; (ii) the communication links in the network may fail with a non-zero probability; and (iii) the measurements performed to compute distances among the sensors are corrupted with noise. The sensors (which do not know their locations) lie in the convex hull of at least $m+1$ anchors (nodes that know their own locations.) Under minimal assumptions on the connectivity and triangulation of each sensor in the network, this correspondence shows that, under the broad random phenomena described above, DILAND converges almost surely (a.s.) to the exact sensor locations.

I. INTRODUCTION

DILAND addresses distributed sensor localization when communication, links, and distance measurements are noisy or unreliable. It replaces DLRE’s current-measurement perturbation condition with consistent distance estimates, retaining almost-sure convergence to exact locations under broader conditions.

  • Prior method: DILOC updates each sensor’s estimate as a barycentric-coordinate convex combination of neighboring-node estimates.Its distributed linear iteration reduces localization to local inter-sensor communication.
  • Prior method: DLRE extends DILOC using decreasing stochastic-approximation weights and models noisy communication, random link failures, and perturbed barycentric coordinates.Under unbiased perturbations, DLRE reaches exact locations; biased perturbations produce steady-state error.
  • Problem setting: DILAND targets sensor localization with noisy communication, probabilistic link failures, and corrupted distance measurements.Sensors lack known locations and are placed within the convex hull of anchors.
  • DILAND modification: DILAND replaces DLRE’s current-distance condition with computationally efficient distance estimates that converge almost surely to the exact distances.The estimates use accumulated measurements, including practical RSS and TOA schemes, rather than only current measurements.
  • DILAND modification: DILAND does not require spatial or temporal noise-distribution assumptions beyond finite second moments.Its convergence result therefore covers broader distance-measurement noise conditions than the earlier biased-perturbation setting.

(B.3), DILAND

The paper frames DILAND as a robust extension of distributed localization that tolerates biased system-matrix perturbations and can converge faster than DLRE in a noise-free-link setting.

  • DILAND discussion: DILAND converges to exact sensor locations regardless of bias introduced in the system matrix at each iteration.This contrasts with DLRE’s steady-state error under biased barycentric-coordinate perturbations.
  • DILAND discussion: Using distance estimates formed from the entire measurement history creates strong statistical dependence in DILAND’s iterative scheme.This dependence requires analysis different from the standard stochastic-approximation arguments used for DLRE.
  • DILAND discussion: Without link failures and communication noise, DILAND does not require DLRE’s square-summability condition on the weight sequence.The paper links this relaxed condition to the possibility of faster convergence.
  • DILAND discussion: DILAND can be designed to converge faster than DLRE by choosing a weight sequence that sums faster to infinity.The comparison is stated for the setting without link failures and communication noise.
  • Distributed localization setting: The localization model assumes anchors and sensors satisfy structural connectivity, triangulation, convex-hull, and distance-availability conditions.Under these assumptions, DILOC’s states converge to the exact sensor locations.

B. Distributed Localization in Random Environments (DLRE)

DLRE applies stochastic approximation to DILOC under random communication and measurement effects, but biased system-matrix perturbations prevent exact localization.

  • Noise model: DLRE computes iterations with system matrices derived from noisy inter-node distance estimates rather than exact distances.The estimates may come from RSS or TOA measurements.
  • Noise model: Even unbiased distance estimates can yield nonzero biases in the computed system matrices P and B.These biases are denoted S_P and S_B in the DLRE formulation.
  • Convergence: Under the stated random noise model and persistence condition, DLRE converges to a limit determined by the perturbed system matrices.The limit is expressed using P + S_P and B + S_B.
  • Convergence: DLRE reaches exact sensor locations when the random system matrices are unbiased, meaning S_P = S_B = 0.When the computed matrices are biased, DLRE has a nonzero steady-state localization error.

III. DISTRIBUTED SENSOR LOCALIZATION WITH NOISY DISTANCE MEASUREMENTS

DILAND uses past RSS or TOA measurements to form consistent distance estimates and compute barycentric coordinates, addressing the bias caused by DLRE’s use of only current measurements.

  • Motivation: DLRE’s use of only current RSS or TOA measurements can produce biased system matrices even when distance estimates are unbiased.DILAND instead uses the entire history of distance measurements.
  • Approach: DILAND efficiently incorporates past measurements and is shown to converge almost surely to exact locations under practical distance-measurement schemes.The paper studies RSS and TOA as standard wireless distance-measurement models.
  • RSS and TOA models: RSS distance estimation depends on received signal power and an environment-dependent path-loss exponent.The paper also considers calibration of a multiplicative bias factor for RSS-based estimates.
  • Distance-estimate construction: DILAND uses all measurements available through time t to construct distance estimates for barycentric-coordinate computation.Under the stated independence conditions, the paper invokes the strong law of large numbers for convergence of these estimates.
  • RSS and TOA models: TOA estimates distance from propagation time multiplied by the propagation speed.The paper presents TOA alongside RSS as a wireless distance-measurement method.

2) Time-of-arrival (TOA):

The TOA procedure models measured delays statistically, corrects bias, and converts calibrated time measurements into inter-node distance estimates. These measurements can be processed over time to obtain increasingly precise distance estimates for DILAND.

  • 2) Time-of-arrival (TOA):: TOA measures propagation delay and converts it into distance by multiplying the bias-corrected delay by propagation velocity.The distance estimate is given by bd_ab = (T_ab − μ_T)ν_p.
  • 2) Time-of-arrival (TOA):: Over short ranges, measured time delay T_ab can be modeled as Gaussian, with bias μ_T estimated through calibration experiments and environmental knowledge.The paper reports μ_T = 10.9 ns in DS-SS measurements.
  • 2) Time-of-arrival (TOA):: Because DILAND is iterative, it can collect measurements and estimate the delay bias μ_T at each iteration.The resulting bias estimates are used to obtain a sequence of distance estimates.
  • 2) Time-of-arrival (TOA):: A sequence of inter-node measurements Z(t), including TOA measurements, is used to construct distance estimates that become arbitrarily precise as t approaches infinity.This forms the natural noisy-distance-measurement assumption used by DILAND.

B. Algorithm

DILAND updates sensor-coordinate estimates using barycentric coordinates computed from evolving distance estimates. Under the stated assumptions, its coordinate sequences converge almost surely to the exact sensor locations.

  • B. Algorithm: The analysis in this section focuses on noisy distance measurements while assuming perfect inter-sensor communication.The effects of link failures and communication noise are discussed separately.
  • B. Algorithm: DILAND computes barycentric-coordinate matrices from distance estimates and uses them to update each coordinate component of every sensor state.The coordinate update is followed by a distance update.
  • B. Algorithm: Theorem 3 states that, under assumptions (A.1)–(A.5) and (B.3), each coordinate sequence x_j(t) generated by DILAND converges almost surely to the exact coordinate location.The limiting value is (I − P(d*) )^-1 B(d*)u_j, identified as the exact sensor locations by Theorem 1.

C. DILAND:Discussions

DILAND improves robustness and can converge faster than DLRE by continuously updating distance estimates, while retaining a sub-exponential rate and incurring greater per-iteration computation. Its noisy-communication extension preserves convergence under an additional square-summability condition.

  • C. DILAND:Discussions: DILAND’s analysis handles dependent system matrices arising from distance estimates based on past measurements, rather than relying on the independence assumed by DLRE.The proof uses a framework for stochastic iterative schemes with non-Markovian perturbations.
  • C. DILAND:Discussions: The modified algorithm converges almost surely because its residual error evolves as a stable system driven by temporally independent martingale-difference noise.The convergence of the residual to zero follows from standard stochastic-approximation arguments.
  • C. DILAND:Discussions: DILAND can converge faster than DLRE by choosing weights whose sum grows faster, because its weights do not require square summability in the noiseless-communication case.DLRE’s square-summability requirement limits its convergence rate to order 1/t, whereas DILAND can obtain better rates.
  • C. DILAND:Discussions: DILAND’s requirement α(t) → 0 makes its convergence rate always sub-exponential, since exponential rates require weights bounded away from zero asymptotically.This is an explicit limitation on the achievable rate.
  • C. DILAND:Discussions: Continuous distance re-estimation helps DILAND correct triangulation errors caused by high measurement variance and eventually obtain a correct triangulation.The triangulation set may differ across iterations as distance estimates improve.
  • C. DILAND:Discussions: Compared with initial averaging followed by DLRE, DILAND avoids setup delay and residual distance bias, but requires continuous distance updates and barycentric-coordinate recomputation.The alternative scheme is also sensitive to sensor-location variations, whereas DILAND is adaptive to such variations to a certain degree.

IV. SIMULATIONS

Simulations compare DLRE and DILAND under distance noise alone and under distance noise combined with communication noise and link failures. Across both studies, DILAND converges almost surely to the exact sensor locations and faster than DLRE.

  • Distance noise only: With distance noise only, the study compares DLRE and DILAND weight sequences and normalized mean squared error.The distance measurements are corrupted by additive Gaussian noise, with variance set to 10% of the actual distance, and the estimator averages past observations.
  • Simulation setup: The simulations use an N = 50 network in 2-D space with 3 anchors and 47 sensors.The setup includes appropriate sensor triangulations.
  • All random phenomena: With communication noise and 90%-active links, the study uses the same weight sequence for DLRE and DILAND.Communication noise is modeled as a unit-variance zero-mean Gaussian random variable.
  • Results: DILAND converges almost surely to the exact sensor locations, whereas DLRE converges with a steady-state error.This pattern appears in both simulation studies.
  • Results: DILAND converges faster because its weight sequence is not subject to DLRE’s square-summability condition.The simulations attribute faster convergence under all random phenomena to refined distance measurements.

V. CONCLUSIONS

The conclusions present DILAND as a distributed localization algorithm that handles noisy communication, random link failures, and noisy distance measurements. Under almost-surely convergent distance estimates, it eliminates the steady-state location error and can converge faster than DLRE in favorable communication conditions.

  • Main conclusions: DILAND converges almost surely to the exact sensor locations with communication noise, random link failures, and noisy distance measurements.The result is stated for the three random phenomena together.
  • Relation to prior work: The work builds on DLRE, which extends earlier distributed localization research.The paper identifies DILAND as a modification of DLRE for noisy distance measurements.
  • Main conclusions: DLRE has a non-zero steady-state location error because noisy distance measurements generally create biased system-matrix perturbations.DILAND’s steady-state error is zero when its distance estimates converge almost surely to the exact distances.
  • Convergence rate: Without communication noise and link failures, DILAND can converge faster than DLRE.The correspondence provides simulations supporting the analytical results.

CONVERGENCE OF DILAND

The convergence analysis proves that DILAND’s iterations remain bounded almost surely and that the estimation error converges to zero. The proof uses a comparison argument, norm contraction, and almost-sure convergence of the distance estimates.

  • Boundedness: The DILAND iteration sequence remains bounded almost surely for every coordinate and all times.This is established as the role of Lemma 2 in the convergence proof.
  • Contraction: A norm equivalent to the Euclidean norm makes the linear operator contractive through the bound 1 − λ*α(t).The proof uses α(t) → 0 and the spectral-radius condition ρ(P(d*) ) < 1.
  • Error control: Almost-sure convergence of the distance estimates and continuity of the update functions control the perturbation terms in the recursion.The proof applies pathwise bounds and a summability comparison to show decay of the error.
  • Proof strategy: The proof rewrites DILAND as an idealized update plus an error sequence and applies a comparison argument.The error is defined as the difference between the actual and idealized coordinate sequences.
  • Conclusion: The estimation error converges to zero almost surely, completing the convergence proof for DILAND.The conclusion follows after translating convergence between the constructed norm and the Euclidean norm.
Loading 0910.2743v1…