Localization on the pushpin computing sensor network using spectral graph drawing and mesh relaxation
Authors:
Open Access
- 1 January 2006
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMOBILE Mobile Computing and Communications Review
- Vol. 10 (1) , 1-12
Abstract
This work approaches the problem of localizing the nodes of a distributed sensor network by leveraging distance constraints such as inter-node separations or ranges between nodes and a globally observed event. Previous work has shown this problem to suffer from false minima, mesh folding, slow convergence, and sensitivity to initial position estimates. Here, we present a localization system that combines a technique known as spectral graph drawing (SGD) for initializing node position estimates and a standard mesh relaxation (MR) algorithm for converging to finer accuracy. We describe our combined localization system in detail and build on previous work by testing these techniques with real 40-kHz ultrasound time-of-flight range data collected from 58 nodes in the Pushpin Computing network, a dense hardware testbed spread over an area of one square meter. In this paper, we discuss convergence characteristics, accuracy, distributability, and the robustness of this localization system.Keywords
This publication has 16 references indexed in Scilit:
- Localizing a sensor network via collaborative processing of global stimuli2005
- Distributed Graph Layout for Sensor NetworksLecture Notes in Computer Science, 2005
- Robust distributed network localization with noisy range measurements2004
- Manifold learning algorithms for localization in wireless sensor networks2004
- Distributed localization in wireless sensor networks: a quantitative comparisonComputer Networks, 2003
- Using proximity and quantized RSS for sensor localization in wireless networks2003
- Relative location estimation in wireless sensor networksIEEE Transactions on Signal Processing, 2003
- Localization from mere connectivity2003
- Applied Numerical Linear Algebra1997
- An r-Dimensional Quadratic Placement AlgorithmManagement Science, 1970