An as-rigid-as-possible approach to sensor network localization
Authors:
Open Access
- 13 July 2010
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Sensor Networks
- Vol. 6 (4) , 1-21
Abstract
We present a novel approach to localization of sensors in a network given a subset of noisy inter-sensor distances. The algorithm is based on “stitching” together local structures by solving an optimization problem requiring the structures to fit together in an “As-Rigid-As-Possible” manner, hence the name ARAP. The local structures consist of reference “patches” and reference triangles, both obtained from inter-sensor distances. We elaborate on the relationship between the ARAP algorithm and other state-of-the-art algorithms, and provide experimental results demonstrating that ARAP is significantly less sensitive to sparse connectivity and measurement noise. We also show how ARAP may be distributed.Keywords
Funding Information
- Microsoft Research (60776799973)
- Ministry of Science and Technology of the People's Republic of China (2009CB320801)
- United States-Israel Binational Science Foundation (2006089)
This publication has 17 references indexed in Scilit:
- A remark on global positioning from local distancesProceedings of the National Academy of Sciences, 2008
- Semidefinite programming based algorithms for sensor network localizationACM Transactions on Sensor Networks, 2006
- Connected rigidity matroids and unique realizations of graphsJournal of Combinatorial Theory, Series B, 2005
- Graph Drawing by Stress Majorization2005
- Distributed Graph Layout for Sensor NetworksJournal of Graph Algorithms and Applications, 2005
- Robust distributed network localization with noisy range measurements2004
- Generic Global RigidityDiscrete & Computational Geometry, 2004
- Sensor networks: an overviewIEEE Potentials, 2003
- Nonlinear Dimensionality Reduction by Locally Linear EmbeddingScience, 2000
- Modern Multidimensional Scaling1997