DocumentCode :
2678493
Title :
Analyzing connectivity-based multi-hop ad-hoc positioning
Author :
Bischoff, Regina ; Wattenhofer, Roger
Author_Institution :
Dept. of Comput. Sci., ETH Zurich, Switzerland
fYear :
2004
fDate :
14-17 March 2004
Firstpage :
165
Lastpage :
174
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.
Keywords :
Global Positioning System; ad hoc networks; distributed algorithms; graph theory; optimisation; wireless sensor networks; 1D unit disk graphs; GHoST; HS; angle information; connectivity-based ad-hoc positioning; distributed algorithms; fast algorithm; large-scale sensor networks; multihop ad-hoc positioning; optimal algorithm; physical distance; plain hop algorithms; positioning algorithms; theoretical limits; Communication systems; Computer science; Distributed algorithms; Global Positioning System; Joining processes; Large-scale systems; Pervasive computing; Spread spectrum communication; Transportation; Wireless sensor networks;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Pervasive Computing and Communications, 2004. PerCom 2004. Proceedings of the Second IEEE Annual Conference on
Print_ISBN :
0-7695-2090-1
Type :
conf
DOI :
10.1109/PERCOM.2004.1276855
Filename :
1276855
Link To Document :
بازگشت