Preprint 0 (2001) ?{? 1
GPS-free p ositioning in mobile ad ho c networks
Srdjan
Capkun, Maher Hamdi, Jean-Pierre Hubaux
Institute for computer Communication and Applications (ICA)
Communication Systems Department (DSC)
Swiss Federal Institute of Technology Lausanne (EPFL)
CH-1015 Lausanne, Switzerland
(srdan.capkun, maher.hamdi, jean-pierre.hubaux)@ep.ch
We consider the problem of node positioning in ad hoc networks. We prop ose a distributed, infrastructure-
free positioning algorithm that does not rely on GPS (Global Positioning System). Instead, the algorithm uses
the distances between the nodes to build a relative coordinate system in which the no de positions are computed
in two dimensions. Despite the distance measurement errors and the motion of the no des, the algorithm provides
sucient location information and accuracy to support basic network functions. Examples of applications where
this algorithm can be used include Location Aided Routing 8] and Geodesic Packet Forwarding 7]. Another
example are sensor networks, where mobility is less of a problem. The main contribution of this work is to
dene and compute relative positions of the nodes in an ad ho c network without using GPS. We further explain
how the prop osed approach can be applied to wide area ad ho c networks.
Keywords:
ad ho c, mobile, distributed, wireless networks, p ersonal communication system, self-locating,
radio-location, GPS-free, self-organization.
1. Intro duction
The presented work is a part of the Termin-
ode pro ject, a 10 year ongoing pro ject that in-
vestigates large area, wireless, mobile ad ho c net-
works 1,19,20]. The main design points of the
pro ject are to eliminate any infrastructure and
to build a decentralized, self-organized and scal-
able network where no des perform all networking
functions (traditionally implemented in backbone
switches/routers and servers).
In this pap er, we describ e an algorithm for the
p ositioning of no des in an ad ho c network that do es
not use GPS. The algorithm provides a p osition
information to the nodes in the scenarios where an
infrastructure do es not exist and GPS cannot be
used. GPS-free p ositioning is also desirable, when
the GPS signal is to o weak (e.g., indoor), when it is
jammed, or when a GPS receiver has to b e avoided
for cost or integration reasons.
We intro duce a distributed algorithm that en-
ables the no des to nd their p ositions within the
network area using only their lo cal information.
The algorithm is referred to as the Self-Positioning
Algorithm (SPA). It uses range measurements b e-
tween the no des to build a Network Co ordinate
System (Fig 1.). The Time of Arrival (TOA)
metho d is used to obtain the range between two
mobile devices.
Despite the distance measurement errors and
the motion of the no des, the algorithm provides
sucient lo cation information and accuracy to sup-
p ort basic network functions. Examples of applica-
tions where this algorithm can b e used include Lo-
cation Aided Routing 8] and Geo desic Packet For-
warding 7], both in ad hoc and sensor networks.
In the Geo desic Packet Forwarding algorithm, the
source sends packets in the physical direction of the
destination no de. Given that the no de knows its
p osition and the p ositions of the destination no de
in the relative co ordinate system, it is able to com-
剩余14页未读，继续阅读
资源评论
活宝贝熊猫2012-09-20很久以前下的，东西都做完了，很有用
