Distributed localization using noisy distance and angle information
Authors:
Open Access
- 22 May 2006
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 262-273
Abstract
Localization is an important and extensively studied problem in ad-hoc wireless sensor networks. Given the connectivity graph of the sensor nodes,along with additional local information (e.g. distances, angles, orientations etc.), the goal is to reconstruct the global geometry of the network. In this paper, we study the problem of localization with noisy distance and angle information. With no noise at all, the localization problem with both angle (with orientation) and distance information is trivial. However, in the presence of even a small amount of noise, we prove that the localization problem is NP hard.Localization with accurate distance information and relative angle information is also hard. These hardness results motivate our study of approximation schemes. We relax the non-convex constraints to approximating convex constraints and propose linear programs (LP) for two formulations of the resulting localization problem, which we call the weak deployment and strong deployment problems.These two formulations give upper and lower bounds on the location uncertainty respectively: No sensor is located outside its weak deployment region, and each sensor can be anywhere in its strong deployment region without violating the approximate distance and angle constraints. Though LP-based algorithms are usually solved by centralized methods, we propose distributed, iterative methods, which are provably convergent to the centralized algorithm solutions. We give simulation results for the distributed algorithms, evaluating the convergence rate, dependence on measurement noises,and robustness to link dynamics.Keywords
This publication has 21 references indexed in Scilit:
- Theoretical aspects of connectivity-based multi-hop positioningTheoretical Computer Science, 2005
- Localization and routing in sensor networks by local angle information2005
- Distributed Graph Layout for Sensor NetworksLecture Notes in Computer Science, 2005
- Unit disk graph approximation2004
- Virtual coordinates for ad hoc and sensor networks2004
- Error characteristics of ad hoc positioning systems (aps)2004
- On the Computational Complexity of Sensor Network Localization2004
- Geographic routing without location information2003
- Localization from mere connectivity2003
- Unit disk graph recognition is NP-hardComputational Geometry, 1998