Article

Moving-Baseline Localization

Authors:

Erik D. Demaine,

Seth TellerAuthors Info & Claims

IPSN '08: Proceedings of the 7th international conference on Information processing in sensor networks

Pages 15 - 26

https://doi.org/10.1109/IPSN.2008.65

Published: 22 April 2008 Publication History

Abstract

The moving-baseline localization (MBL) problem arises when a group of nodes moves through an environment in which no external coordinate reference is available. When group members cannot see or hear one another directly, each node must employ local sensing and inter-device communication to infer the spatial relationship and motion of all other nodes with respect to itself. We consider a setting in which nodes move with piecewise-linear velocities in the plane, and any node can exchange noisy range estimates with certain sufficiently nearby nodes. We develop a distributed solution to the MBL problem in the plane, in which each node performs robust hyperbola fitting, trilateration with velocity constraints, and subgraph alignment to arrive at a globally consistent view of the network expressed in its own "rest frame." Changes in any node's motion cause deviations between observed and predicted ranges at nearby nodes, triggering revision of the trajectory estimates computed by all nodes.We implement and analyze our algorithm in a simulation informed by the characteristics of a commercially available UWB (ultra-wideband) radio, and show that recovering node trajectories (rather than just locations) requires substantially less computation at each node. Finally, we quantify the minimum ranging rate and local network density required for the method's successful operation.

References

[1]

B. Alavi and K. Pahlavan. Modeling of the ToA-based distance measurement error using UWB indoor radio measurements. IEEE Communications Letters, 10(4):275-277, 2006.

[2]

S. Chatterjee and I. Olkin. Nonparametric estimation for quadratic regression. Statistics and Probability Letters, 76(11):1156-1163, 2006.

[3]

S. Datta, C. Klinowski, M. Rudafshani, and S. Khaleque. Distributed localization in static and mobile sensor networks. In IEEE Int'l Conf. on Wireless and Mobile Computing , pages 69-76, 2006.

Digital Library

[4]

B. Dil, S. Dulman, and P. Havinga. Range-based localization in mobile sensor networks. In Third European Workshop on Wireless Sensor Networks, volume 3868, pages 164-179. Springer, 2006.

Digital Library

[5]

T. Eren, D. Goldenberg, W. Whiteley, Y. R. Yang, A. S. Morse, B. D. O. Anderson, and P. N. Belhumeur. Rigidity, computation, and randomization in network localization. In Proc. IEEE INFOCOM, pages 2673-2684, March 2004.

[6]

L. Freitag, M. Johnson, M. Grund, S. Singh, and J. Preisig. Integrated acoustic communication and navigation for multiple UUVs. In Proc. MTS/IEEE Oceans, pages 290-294, Honolulu, HI, USA, Sept. 2001.

[7]

D. K. Goldenberg, A. Krishnamurthy, W. C. Maness, Y. R. Yang, A. Young, A. S. Morse, A. Savvides, and B. D. Anderson. Network localization in partially localizable networks. In Proc. IEEE INFOCOM, pages 313-326, Miami, FL, March 2005.

[8]

B. Hoffmann-Wellenhof, H. Lichtenegger, and J. Collins. Global Positioning System: Theory and Practice, Fourth Edition. Springer-Verlag, 1997.

[9]

B. K. P. Horn, H. M. Hilden, and S. Negahdaripour. Closed-form solution of absolute orientation using orthonormal matrices. Journal of the Optical Society of America A, 5(7):1127-1135, 1988.

[10]

L. Hu and D. Evans. Localization for mobile sensor networks. In Proc. MobiCom, pages 45-57. ACM Press New York, NY, USA, 2004.

Digital Library

[11]

R. Kurazume, S. Nagata, and S. Hirose. Cooperative positioning with multiple robots. In Proc. IEEE Int'l Conf. in Robotics and Automation, pages 1250-1257, Los Alamitos, CA, USA, May 1994.

[12]

J.-Y. Lee and R. Scholtz. Ranging in a dense multipath environment using an uwb radio link. IEEE J. Selected Areas in Communications, 20(9):1677-1683, Dec. 2002.

Digital Library

[13]

M. Maroti, B. Kusy, G. Simon, and A. Ledeczi. The flooding time synchronization protocol. In Proc. SenSys, pages 39- 49, New York, NY, USA, 2004. ACM Press.

Digital Library

[14]

D. Moore, J. Leonard, D. Rus, and S. Teller. Robust distributed network localization with noisy range measurements. In Proc. SenSys, pages 50-61, New York, NY, USA, 2004. ACM Press.

Digital Library

[15]

N. Priyantha, H. Balakrishnan, E. Demaine, and S. Teller. Mobile-Assisted Localization in Wireless Sensor Networks. In Proc. InfoCom, pages 172-183, March 2005.

[16]

N. Priyantha, A. Chakraborty, and H. Balakrishnan. The Cricket Location-Support System. In Proc. MobiCom, Boston, MA, Aug. 2000.

Digital Library

[17]

N. B. Priyantha, H. Balakrishnan, E. Demaine, and S. Teller. Anchor-free distributed localization in sensor networks (poster abstract). In Proc. SenSys, pages 340-341, Los Angeles, California, USA, November 5-7 2003.

Digital Library

[18]

S. Roumeliotis and G. Bekey. Synergetic localization for groups of mobile robots. In Proc. IEEE Decision and Control , pages 3477-3482, Sydney, Australia, Dec. 2000.

[19]

A. Savvides, W. Garber, S. Adlakha, R. Moses, and M. B. Srivastava. On the error characteristics of multihop node localization in ad-hoc sensor networks. In Proc. IPSN, pages 317-332, Palo Alto, CA, April 2003.

Digital Library

[20]

E. Stump, B. Grocholsky, and V. Kumar. Extensive representations and algorithms for nonlinear filtering and estimation. In Proc. WAFR, New York, NY, July 2006.

[21]

J. Vaganay, J. Leonard, J. Curcio, and S. Willcox. Experimental validation of the moving long base-line navigation concept. In AUV 2004, pages 555-556, Nagoya, Japan, June 2004.

[22]

G. Welch, G. Bishop, L. Vicci, S. Brumback, K. Keller, and D. Colucci. The HiBall tracker: High-performance wide-area tracking for virtual and augmented environments. In Proc. ACM Symp. on Virtual Reality Software and Technology , December 1999.

Digital Library

[23]

L. Whitcomb, D. Yoerger, H. Singh, and J. Howland. Advances in Underwater Robot Vehicles for Deep Ocean Exploration: Navigation, Control and Survey Operations. In The Ninth Int'l Symposium on Robotics Research, Springer-Verlag, London, 2000.

[24]

K. Whitehouse and D. Culler. A robustness analysis of multi-hop ranging-based localization approximations. In Proc. IPSN, pages 317-325, Nashville, TN, April 2006.

Digital Library

[25]

M. Z. Win and R. A. Scholtz. On the robustness of ultra-wide bandwidth signals in dense multipath environments. IEEE Communications Letters, 2(2):51-53, 1998.

[26]

Y. Xu, Y. Ouyang, Z. Le, J. Ford, and F. Makedon. Mobile anchor-free localization for wireless sensor networks. In Distributed Computing in Sensor Systems, 2007.

Digital Library

Cited By

Akcan HEvrendilek CNascimento MSharaf MLi FMouratidis K(2013)Reducing the number of flips in trilateration with noisy range measurementsProceedings of the 12th International ACM Workshop on Data Engineering for Wireless and Mobile Acess10.1145/2486084.2486088(20-27)Online publication date: 23-Jun-2013
https://dl.acm.org/doi/10.1145/2486084.2486088
Zhu YGortler SThurston D(2011)Sensor network localization using sensor perturbationACM Transactions on Sensor Networks10.1145/1921621.19216307:4(1-23)Online publication date: 4-Feb-2011
https://dl.acm.org/doi/10.1145/1921621.1921630
Schiff JSudderth EGoldberg K(2009)Nonparametric belief propagation for distributed tracking of robot networks with noisy inter-distance measurementsProceedings of the 2009 IEEE/RSJ international conference on Intelligent robots and systems10.5555/1733343.1733593(1369-1376)Online publication date: 10-Oct-2009
https://dl.acm.org/doi/10.5555/1733343.1733593

Index Terms

Moving-Baseline Localization

Recommendations

Computational intelligence based localization of moving target nodes using single anchor node in wireless sensor networks

Wireless Sensor Networks (WSNs) have tremendous ability to interact and collect data from the physical world. The main challenges for WSNs regarding performance are data computation, prolong lifetime, routing, task scheduling, security, deployment and ...
A Factorization-Based Approach for Articulated Nonrigid Shape, Motion and Kinematic Chain Recovery From Video

Recovering articulated shape and motion, especially human body motion, from video is a challenging problem with a wide range of applications in medical study, sport analysis and animation, etc. Previous work on articulated motion recovery generally ...
Low-cost two-hop anchor node-based distributed range-free localization in wireless sensor networks
ICCSA'10: Proceedings of the 2010 international conference on Computational Science and Its Applications - Volume Part III

Due to the fact that most of the sensor network applications are based on the location information of sensor nodes, localization is an essential research area. Some localization schemes in the literature require sensor nodes to have additional devices ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

IPSN '08: Proceedings of the 7th international conference on Information processing in sensor networks

April 2008

552 pages

ISBN:9780769531571

Sponsors

SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

IEEE Computer Society

United States

Publication History

Published: 22 April 2008

Check for updates

Author Tags

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 143 of 593 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
277
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Akcan HEvrendilek CNascimento MSharaf MLi FMouratidis K(2013)Reducing the number of flips in trilateration with noisy range measurementsProceedings of the 12th International ACM Workshop on Data Engineering for Wireless and Mobile Acess10.1145/2486084.2486088(20-27)Online publication date: 23-Jun-2013
https://dl.acm.org/doi/10.1145/2486084.2486088
Zhu YGortler SThurston D(2011)Sensor network localization using sensor perturbationACM Transactions on Sensor Networks10.1145/1921621.19216307:4(1-23)Online publication date: 4-Feb-2011
https://dl.acm.org/doi/10.1145/1921621.1921630
Schiff JSudderth EGoldberg K(2009)Nonparametric belief propagation for distributed tracking of robot networks with noisy inter-distance measurementsProceedings of the 2009 IEEE/RSJ international conference on Intelligent robots and systems10.5555/1733343.1733593(1369-1376)Online publication date: 10-Oct-2009
https://dl.acm.org/doi/10.5555/1733343.1733593

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents