PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributed Sensor Localization in Random Environments using Minimal Number of Anchor Nodes

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

arXiv:0802.3563v2cs.IT

TL;DR

The paper addresses distributed sensor localization with few anchors when centralized processing is impractical and network information or communication is unreliable. It develops DILOC and its stochastic-approximation extension DLRE, using local geometric updates and an absorbing-Markov-chain convergence analysis. The algorithms converge almost surely under deterministic and random conditions, while the random case yields characterized error relative to the true sensor locations.

  • Problem

    Large untethered sensor networks require localization with limited anchors and without relying on costly centralized communication and processing.

  • Method

    DILOC uses local iterative convex-combination updates based on barycentric coordinates, while DLRE extends it with stochastic approximation for noisy distances, corrupted communication, and random link failures.

  • Results

    DILOC converges to exact sensor locations when links do not fail, while DLRE converges almost surely in random environments and has a characterized error from the true locations.

  • Takeaways & Limitations

    The algorithms provide distributed localization using the minimal m+1 anchors and local communication, including under random communication and measurement conditions.

  • Takeaways & Limitations

    The random-environment analysis assumes inter-sensor communication links may fail randomly, so the network can lack connected iterations.

Abstract

from arXiv · show

The paper develops DILOC, a \emph{distributive}, \emph{iterative} algorithm that locates M sensors in $\mathbb{R}^m, m\geq 1$, with respect to a minimal number of m+1 anchors with known locations. The sensors exchange data with their neighbors only; no centralized data processing or communication occurs, nor is there centralized knowledge about the sensors' locations. DILOC uses the barycentric coordinates of a sensor with respect to its neighbors that are computed using the Cayley-Menger determinants. These are the determinants of matrices of inter-sensor distances. We show convergence of DILOC by associating with it an absorbing Markov chain whose absorbing states are the anchors. We introduce a stochastic approximation version extending DILOC to random environments when the knowledge about the intercommunications among sensors and the inter-sensor distances are noisy, and the communication links among neighbors fail at random times. We show a.s. convergence of the modified DILOC and characterize the error between the final estimates and the true values of the sensors' locations. Numerical studies illustrate DILOC under a variety of deterministic and random operating conditions.

I. INTRODUCTION

The paper introduces DILOC, a distributed iterative localization algorithm using only local communication and the minimal m+1 anchors, and extends it to noisy random environments. It establishes almost sure convergence for the deterministic and extended algorithms under broad conditions.

  • Motivation: DILOC addresses large sensor networks where centralized computation is costly, communication-intensive, latency-inducing, and vulnerable to bottlenecks or single points of failure.The algorithm is designed for sensors that communicate directly with only a few neighboring nodes and perform low-order local computations.
  • DILOC: DILOC localizes sensors with respect to a minimal set of m+1 anchors through distributed, iterative local state updates.Each sensor updates its state using a convex combination of m+1 neighbors, without a fusion center or global communication.
  • DILOC: DILOC permits arbitrary initial location estimates, including random guesses outside the anchors’ convex hull.Sensors iteratively exchange state information only with selected neighbors.
  • DILOC: The update coefficients are barycentric coordinates computed from mutual inter-sensor distances using Cayley-Menger determinants.Each sensor chooses a neighborhood whose m+1 members contain it in their convex hull; these neighbors may include anchors.
  • Convergence: DILOC converges almost surely in deterministic and random network environments by behaving as an absorbing Markov chain with anchors as absorbing states.The convergence rate depends on the spectral radius of the associated matrix.
  • Random environments: DLRE extends DILOC to random environments with noisy distances, corrupted communication, and randomly failing links using stochastic approximation with decreasing iteration weights.The paper characterizes the bias and mean-square error of the resulting location estimates under broad noise conditions.

II. DISTRIBUTED SENSOR LOCALIZATION: DILOC

DILOC formulates distributed localization in R^m using triangulation sets, barycentric coordinates, and local inter-sensor distances. Its iterative states describe sensors relative to known anchors without centralized processing.

  • Problem setting: DILOC addresses localization in R^m, including the practical cases m=1, m=2, and m=3, while also covering higher-dimensional feature vectors.The framework is presented generically for m≥1 and can represent distributed global coordinates relative to a reference frame.
  • Triangulation: Each sensor uses a triangulation set of exactly m+1 neighboring nodes whose convex hull contains the sensor without degeneracy.The triangulation set is selected from neighbors within a radius and must have nonzero generalized volume.
  • Barycentric coordinates: DILOC represents each sensor location as a barycentric combination of its triangulation neighbors.The barycentric coordinates are unique and are computed from inter-sensor distances using Cayley-Menger determinants.
  • Local information: The algorithm requires only local geometric information: sensor l needs distances among the m+2 nodes in {l} ∪ Θ_l.This local distance set is sufficient to compute the barycentric coordinates used by the updates.

B. Distributed iterative localization algorithm.

DILOC combines fixed anchor states with local iterative updates based on triangulation sets. Its setup finds valid neighbor sets, after which each sensor repeatedly updates from m+1 neighboring states.

  • Assumptions: DILOC assumes known anchor locations, all sensors inside the anchors’ convex hull, and valid local inter-sensor links and distances.For each sensor, the triangulation set must satisfy the convex-hull and nondegeneracy conditions and be directly communicable.
  • DILOC setup: The setup phase triangulates every sensor by testing collections of m+1 nearby nodes and increasing its communication radius when necessary.Success means finding a set Θ_l satisfying the convex-hull, cardinality, volume, and communication requirements.
  • DILOC iterations: After setup, each non-anchor sensor updates its state as a convex combination of the states of nodes in its triangulation set, while anchors remain fixed.The update is performed independently at each sensor using only its m+1 neighboring states.
  • Matrix format: The matrix representation preserves distributed operation: anchor rows are fixed, sensor rows are sparse, and each sensor row uses only triangulation-set neighbors.The matrix form is provided for compact notation and convergence analysis, not centralized execution.
  • Matrix format: DILOC’s iteration matrix contains exactly (m + 1) + M(m + 1) nonzero entries out of (m + 1 + M)^2 possible entries.The sparsity reflects the fixed anchor updates and the m+1-neighbor update for each of M sensors.

C. Example

In a two-dimensional example with three anchors and four sensors, no sensor can localize in one step because none communicates directly with three anchors. DILOC instead uses local iterative updates with constant per-sensor costs.

  • Example setup: The example contains m=2, three anchors, and four sensors, with triangulation sets identified by convex-hull inclusion tests.The sets are Θ4={1,5,7}, Θ5={4,6,7}, Θ6={2,5,7}, and Θ7={3,4,6}.
  • Example behavior: Sensor 5 has no anchor in its triangulation set, while every other sensor has exactly one anchor in its set.Consequently, no sensor communicates directly with all three anchors.
  • Example behavior: Because no sensor can communicate with three anchors directly, no sensor localizes itself in a single step.The example therefore illustrates the need for iterative propagation of anchor information through sensor neighbors.
  • State update: Sensor 5 updates according to c5(t + 1) = a54c4(t) + a56c6(t) + a57c7(t).Its update uses the three states in Θ5 and the corresponding barycentric coordinates.
  • Complexity: DILOC requires 2m + 1 operations per sensor per iteration, giving O(1) computation and communication per sensor per iteration.For M sensors, both total computation and communication complexity are O(M).

E. Random Poisson Deployment

Under Poisson deployment, DILOC’s triangulation condition can be analyzed through independent sector occupancies. Increasing the local radius or deployment density raises the probability that a valid triangulation set exists.

  • Deployment model: The Poisson deployment model treats sensor locations as a random spatial deployment with density γ and independent counts in disjoint sectors.The model is used to derive probabilistic bounds for finding triangulation sets.
  • Triangulation condition: In two dimensions, a sufficient triangulation condition is at least one sensor in each of four equal-area sectors within radius r_l.The sensor then selects three neighbors forming a triangulating set.
  • Probability analysis: The probability of finding one sensor in every sector is obtained by multiplying the independent probabilities for the four disjoint sectors.This converts the geometric triangulation requirement into a Poisson occupancy calculation.
  • Probability analysis: For a fixed deployment density, choosing r_l appropriately can make the probability of triangulation arbitrarily high.The same analysis gives a required radius or density when a target probability is specified.
  • Numerical implication: At density γ=1 sensor/m^2, 99% of sensors can triangulate when the communication radius is at least R_l=5.52m.The remaining 1% may require communication over a larger radius.

III. CONVERGENCE OF DILOC

DILOC models sensor updates as an absorbing Markov chain whose anchors absorb and whose sensors are transient. Under the network assumptions, the iterations converge to the exact sensor coordinates.

  • Markov-chain formulation: DILOC represents sensors and anchors as states of an absorbing Markov chain, with anchors absorbing and sensors transient.The iteration matrix supplies transition probabilities between these states.
  • Markov-chain formulation: The chain is absorbing because the triangulation assumptions prevent boundary sensor clusters from remaining disconnected from anchors.Boundary sensors must reach sensors or anchors that enable their triangulation.
  • Limit and exactness: The limiting sensor states are weighted combinations of the m + 1 known anchor coordinates through (I_M − P)^−1B.The transient-state block P has spectral radius below one, making I_M − P invertible.
  • Limit and exactness: Theorem 1 states that DILOC converges to the exact coordinates of the M sensors.The proof combines the absorbing-chain result with the barycentric representation of each sensor location.
  • Convergence rate: Convergence slows when ρ(P) is close to 1, notably when sensors cluster in a small region inside widely separated anchors.This geometry makes the sensor-to-anchor block B close to zero.

IV. DILOC WITH RELAXATION

DILOC-REL introduces a relaxation parameter that blends each current estimate with the original DILOC update. Its tunable iteration matrix preserves exact convergence while allowing rate optimization.

  • Relaxed update: DILOC-REL uses α ∈ (0, 1] to form a convex combination of the current state and the DILOC update.DILOC is recovered when α = 1.
  • Relaxed update: The relaxed iteration matrix is H = (1 − α)I_N + αΥ, and its sensor block is J = (1 − α)I_M + αP.The corresponding chain retains anchors as absorbing states and sensors as transient states.
  • Convergence and purpose: DILOC-REL converges to the exact coordinates of the M sensors.The convergence follows because the relaxed transient matrix has spectral radius below one.
  • Convergence and purpose: Because ρ(J) depends on α, DILOC-REL permits optimizing the convergence rate and provides the basis for DLRE.The paper explicitly connects the relaxed form to localization in random environments.

V. DISTRIBUTED LOCALIZATION IN RANDOM ENVIRONMENTS: ASSUMPTIONS AND ALGORITHM

The random-environment extension addresses inaccurate distance computations, random link failures, and noisy neighbor states. It replaces exact updates with a time-varying stochastic-approximation recursion.

  • Motivation and algorithm: Random environments make exact DILOC updates impractical because distance computations, communication links, and received neighbor states are imperfect.The proposed modification accounts for partial and noisy information at each iteration.
  • Stochastic system matrices: Sensors estimate the required rows of B and P at every iteration from noisy inter-sensor distance measurements.The distance-estimation process implicitly averages unbiased noisy effects over iterations.
  • Random communication: The model allows random link failures, with each potential link active at iteration t with probability q_ln.The binary link variable equals one when active and zero when failed.
  • Random communication: Additive channel noise means an active link delivers a corrupt version of a neighbor’s current state.The channel-noise variables are assumed to have zero mean under weak moment conditions.
  • DLRE construction: DLRE uses a time-varying gain α(t) and random system matrices to update sensor-coordinate estimates under these disturbances.The recursion is designed for the random environment rather than the exact DILOC iteration.
  • Design assumptions: The design additionally assumes persistence of the weights and sufficiently small non-zero bias in the P-system computation.The low-bias condition is justified when the bias S_P is small.

VI. DLRE: A.S. CONVERGENCE

Under the stated stochastic and design assumptions, DLRE converges almost surely from arbitrary initial estimates. Its steady-state error is determined by persistent biases rather than zero-mean random disturbances.

  • Almost-sure convergence: Theorem 3 states that DLRE’s state sequence converges almost surely under assumptions (C1)–(C4) and (D1)–(D2).The convergence proof uses a stochastic approximation result for controlled Markov processes.
  • Almost-sure convergence: Starting from any initial guess X(0), the estimated sensor-location matrix X(t) converges almost surely to a limiting state.The theorem applies to the full coordinate estimate matrix.
  • Steady-state error: The limiting DLRE estimate is not exact when random system-matrix errors include non-zero biases.The paper introduces localization error to characterize the gap from the exact sensor locations.
  • Steady-state error: The localization error depends only on the non-zero biases S_P and S_B caused by noisy inter-sensor distance measurements.Random errors themselves do not determine the final error under the stated model.
  • Robustness: DLRE is robust to random link failures, additive channel noise, and zero-mean random errors in system-matrix computations.The remaining steady-state discrepancy is attributed to fixed non-zero biases.
  • Robustness: When S_P = S_B = 0, the localization error is zero; sufficiently accurate distance computation therefore yields negligible steady-state error.The paper notes that numerical studies illustrate this behavior in random sensing environments.

VII. NUMERICAL STUDIES

The numerical studies evaluate DILOC and DLRE in deterministic settings and under communication, link-failure, distance-measurement, and combined random conditions. Simulations use networks of 50 or 500 nodes and decreasing weight sequences in the noisy cases.

  • Study design: The study covers deterministic operation, communication noise and link failures, noisy distance measurements, and combinations of all random scenarios.The authors organize the numerical study into these operating conditions.
  • Deterministic environments: N = 7 nodes in m = 2 dimensions are used for the deterministic example, with 3 anchors and 4 sensors.DILOC is implemented on this example, with estimated coordinates and trajectories shown in Fig. 3(a)–(b).
  • Deterministic environments: N = 500 nodes are used for a larger deterministic network, with triangulation sets and iterations shown for two selected sensors.These results correspond to Fig. 3(c)–(d).
  • Communication noise and link failures: With communication noise and link failures, all links are active 90% of the time and communication noise is Gaussian with variance 1/M.DILOC uses the decreasing weight sequence α(t) = 4/(t+1) in this experiment.
  • Noisy and random environments: Noisy-distance experiments assume a small perturbation of the required distances and use DLRE with α = 1/t^0.55 on N = 50-node networks.The combined random-environment experiment applies the same weight sequence with noisy distances, communication noise, and link failures.

VIII. CONCLUSIONS

The paper presents distributed iterative localization in R^m using the minimal m + 1 anchors for sensors inside their convex hull. DILOC converges to exact locations deterministically, while DLRE converges almost surely in random environments and has a characterized final estimation error.

  • Conclusions: The algorithm finds sensor coordinates in R^m using only local communication and the minimal number, m + 1, of known-location anchors.It localizes an arbitrary number M of sensors lying in the convex hull of those anchors.
  • Deterministic environments: In deterministic conditions, DILOC and DILOC-REL converge to the exact sensor locations.This assumes accurate inter-sensor distances, no communication noise, and no link failures.
  • Random environments: In random environments, DLRE yields almost sure convergence when links fail randomly, transmitted data is noisy, and distances are imprecise.The random-environment setting includes all three sources of uncertainty.
  • Random environments: The paper explicitly characterizes the error between exact sensor locations and converged estimates in the random case.Numerical simulations illustrate algorithm behavior under different field conditions.

APPENDIX I

Appendix I develops a distance-only convex-hull inclusion test and connects DILOC convergence to absorbing Markov-chain properties. Cayley-Menger determinants provide the required generalized volumes from inter-sensor distances.

  • Convex hull inclusion test: A sensor l is tested for membership in the convex hull of m + 1 nodes using only mutual distances among those m + 2 nodes.The test compares generalized volumes before and after adding l.
  • Cayley-Menger determinants: The generalized volumes used by the inclusion test are calculated from inter-sensor distances through Cayley-Menger determinants.The determinant is formed from an (m + 2) × (m + 2) symmetric distance matrix.
Loading 0802.3563v2…