Analyzing Connectivity-Based Multi-Hop Ad-Hoc Positioning

Abstract

We investigate the theoretical limits of positioning algo rithms. In particular, we study scenarios where the nodes do not receive anchors directly (multi-hop) and where no phys ical distance or angle information whatsoever is available (connectivity-based). Since we envision large-scale sensor networks as an application, we are interested in fast, dis tributed algorithms. As such, we show that plain hop al gorithms are not competitive. Instead, for one-dimensional unit disk graphs we present an optimal algorithm HS. For two or more dimensions, we propose an algorithm GHoST which improves upon the basic hop algorithm in theory and in simulations.