Localization on the pushpin computing sensor network using spectral graph drawing and mesh relaxation

Authors:

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.

This publication has 16 references indexed in Scilit: