Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10334310 | Theoretical Computer Science | 2005 | 22 Pages |
Abstract
We investigate the theoretical limits of positioning algorithms. In particular, we study scenarios where the nodes do not receive anchors directly (multi-hop) and where no physical distance or angle information whatsoever is available (connectivity-based). Since we envision large-scale sensor networks as an application, we are interested in fast, distributed algorithms. As such, we show that plain hop algorithms 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
R. O'Dell, R. Wattenhofer,