Comparison: Localization of 200 sensors in square-shaped region by different algorithms. Columns: Various algorithms. Rows: Various average number of neighbors. Inlaid numbers are localization error (in boldface) and runtime (in millisec).
Abstract
We present a novel
approach to localization of sensors in a network given a subset of noisy
intersensor 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.
PDF (1.6M)
An earlier version: Technical report (0.6M), Harvard University,TR-01-09, Jan. 2009
Executable C++ software (5.0M)
Source code (C++, Matlab)
We thank the anonymous
reviewers for their helpful comments and Y. Shang for providing an
implementation of MDS-MAP(P,R). This work is supported by the joint
grant of the National Natural Science Foundation of China and Microsoft
Research Asia (grant 60776799) and the 973 National Key Basic Research
Foundation of China (grant 2009CB320801). Craig Gotsman and Steven
Gortler were partially supported by United States - Israel Binational
Science Foundation (grant 2006089).
title = {An As-Rigid-As-Possible Approach to Sensor Network Localization},
author = {Lei Zhang and Ligang Liu and Craig Gotsman and Steven J. Gortler}
journal = {ACM Transactions on Sensor Networks},
volume = {6},
number = {4},
pages = {Article 35: 1-21},
year = {2010}
}