ten required to be computationally lightweight so that it can be performed on resource-
constrained embedded microprocessors. At the same time, the solution should operate in a
fully distributed manner that is tolerant of node failures. Furthermore, in situations where
known landmarks are not within range of the nodes, individual nodes have to collaborate
over multiple hops and utilize indirect line of sight measurement information to estimate
their positions. This intensifies the problem, especially when network density and the den-
sity of landmarks becomes very sparse. Second, the ad hoc deployment of nodes in un-
known environments affects the measurements at the physical layer. Transmissions from
multiple sources can cause interference and changes in the surrounding terrain can intro-
duce unexpected multipath and shadowing components, whereas changes in wheather
conditions can affect signal propagation properties. Furthermore, the non-line-of-sight
components increase in environments with more obstacles, introducing additional mea-
surement errors. Third, despite the fact that many sensors and measurement technologies
are readily available, a significant system integration effort is still required. To achieve the
localization task, nodes need to coordinate and several components at multiple levels need
to operate in harmony to produce an operational system.
8.4.2 Existing Ad Hoc Localization Approaches
Because of the aforementioned challenges and the great diversity of application require-
ments, there is currently no universal ad hoc localization system that will satisfy all appli-
cations. Instead, different types of systems have been proposed, each focusing on the re-
quirements of the application at hand. Some setups require that positions be calculated at
a central processing center in the network, and other setups call for fully distributed oper-
ation. The context in which locations are presented is also important. For some applica-
tions, relative positioning of nodes with respect to each other is sufficient, but for other
applications a global frame of reference is more suitable. A local frame of reference typi-
cally does not require any prior knowledge of position information. When a global frame
of reference is needed, the positions of some of the nodes, frequently referred as anchors
or beacons, should be known. The existence of beacon nodes is typically assumed in most
of the multihop localization approaches aiming to localize a number of nodes by using a
very small fraction of beacons. Another difference in the existing approaches deals with
the type of measurements. Some approaches such as the ones in  and  are based on
connectivity only, whereas others are based on crude signal-strength measurements or
very accurate ToF measurements.
The following subsections survey seven approaches that represent the recently pro-
posed work in ad hoc localization algorithms and systems. The first two approaches are
based on mere radio connectivity to provide node proximity. The next two approaches
deal with systems that construct a local coordinate system without the use of beacons. The
remaining three approaches deal with systems in which a small percentage of nodes are
aware of their locations and act as beacons for the remaining nodes and positions of the
22.214.171.124 GPS-less Low-Cost Outdoor Localization System for Very Small
Devices (GPSLC). This system determines the proximity of a node based on a set of
predeployed location-aware reference nodes that transmit spatially overlapping beacon
signals. Nodes localize themselves at the centroids of the reference nodes, from which
they can receive beacon signals. The accuracy of localization depends on the density of
8.4 AD HOC TECHNIQUES FOR LOCATION DISCOVERY
the reference nodes and their transmission range. The best results are obtained when bea-
con nodes are arranged in a mesh pattern.
126.96.36.199 Convex Position Estimation in Wireless Sensor Networks (CPE).
The convex position estimation algorithm described in  computes the locations of
nodes in an ad hoc network by performing computation at a central point in the network.
Location estimation is formulated as a linear program (LP) or a semidefinite program
(SDP), and the solutions are computed using a special optimization software package. Us-
ing this formulation, node locations are estimated using mere radio connectivity. More ac-
curate position estimates can also be obtained if internode distance measurements are also
The convex optimization protocols consider two main constraint models, a radial con-
straint model and an angular constraint model. The radial constraint model represents RF
node connectivity. A node is defined to be within transmission range if it is found within a
circle of radius R from the transmitting node. Combining the individual constraints results
(see Figure 8.3) in a reduced feasible region where an unknown node can be found. The
angular constraint model applies to sensor nodes that use optical communication. In this
case, the beam angle of a laser transmitter is modeled as a cone (or a triangle in two di-
mensions), with a certain beam angle and a finite length representing the maximum
According to the simulation results, when nodes with known locations are carefully
placed on the perimeter of the network, position accuracies between 0.72 and 0.64 R are
possible. This result is obtained when each node in the network has an average of 5.6 neigh-
bors with 10% of the nodes acting as beacons. The authors have also shown that accuracies
of less than 0.1 R are also possible at higher node densities and higher percentages of bea-
con nodes. One potential drawback of this approach is that the LP and SDP solutions re-
quire rigorous computation and can only be performed at a central point in the network.
188.8.131.52 GPS-Free Positioning in Mobile Ad Hoc Networks (GPSFP). The sys-
tem described in  and developed as part of the Terminode project  uses radio ToF
measurements to provide locations in mobile ad hoc networks. Despite the existence of
measurement errors, this system is reported to support mobile nodes with speeds up to 20
m/s and can provide adequate location accuracies for supporting basic network services
such as location-aided routing.
Figure 8.3. Combining radial constraints.
242 LOCATION DISCOVERY
The Self-Positioning Algorithm (SPA) described in this paper forms local coordinate
systems for each node and then merges them to construct a global coordinate system. In
this setup, nodes initially discover their neighbors using a set of beacon signals. Each
node then measures the distances to its one-hop neighbors using ToA and broadcasts these
to all its neighbors. The nodes use this information to derive their local coordinate system.
This is illustrated in Figure 8.4. First, node i constructs its own local coordinate system
with nodes p and q. The corresponding coordinates are
ix = 0; iy = 0
px = dip; py = 0
qx = diq cos ; qy = diq sin
where is the angle (p, i, q) and is obtained from the cosines rule:
d iq + d ip вЂ“ d 2
The positions of other nodes with known distances to nodes i, p, and q can also be found
using a similar set of rules. The position for node j in the example figure is given by
jx = dij cos (8.6)
if =| вЂ“ | => dij sin (8.7)
j j j
else => jy = вЂ“dij sin (8.8)
After the local coordinate systems are formed, applying a rotation or a rotation followed by
a mirror transformation aligns the directions of all the local coordinate systems so that the
i jx p
Figure 8.4. Local coordinate system formation example.
8.4 AD HOC TECHNIQUES FOR LOCATION DISCOVERY
x and y coordinates point in the same direction for all the nodes. These transformations are
performed among nodes that are one-hop neighbors, referred to as the local view set (LVS).
Once all the coordinate systems have the same direction, the nodes adjust their coordi-
nates of a single node i that becomes the center of the coordinate system. This adjustment
is initially done between nodes that are within the two-hop neighborhood from the node
that becomes the origin of the coordinate system. This is illustrated in Figure 8.5. Node i
knows the position of node k in terms of its own coordinate system, and node k knows the
position of node 1 in its own coordinate system. The coordinates of node 1 can therefore
be given in term of the coordinate system of node i by summing the corresponding vec-
tors. When the coordinate systems of the two-hop neighborhood nodes are transformed,
the same operation is applied to nodes that are further away, until all the nodes are in the
same coordinate system.
The authors also note that this global coordinate system is not very suitable for net-
works with high levels of mobility. To address this problem, an alternative approach that
computes the center of the coordinate system as a function of the node positions in the
network is proposed. Instead of using a single node as the center of the coordinate system,
a location reference group consisting of the nodes with the highest density in the network
is selected, and the remaining nodes adjust their coordinate systems with respect to this
group of nodes.
184.108.40.206 Locating Tiny Sensors In Time and Space: A Case Study (LTSTS).
This subsection presents the implementation of an operational localization system that
works in close coordination with a time synchronization service. This design is validated
in a testbed setup consisting of two types of nodes forming a tiered network. The first type
of node is small, cheap, and computationally limited, and the second type of node consists
of larger, faster, and more expensive nodes that act as вЂњbasesвЂќ for the smaller nodes.
The localization subsystem consists of three main components: a wideband acoustic
ranging system, a local coordinate system algorithm, and a location service.
The ranging system (described in detail in ) uses a fine-grained time synchroniza-
tion service and a wideband pseudonoise sequence to measure ToF of an acoustic signal
il = ik + kl
Figure 8.5. Local coordinate system formation example.
244 LOCATION DISCOVERY
between a pair of nodes. The wavelengths of the emitted acoustic signals span from one
centimeter to one meter, offering high resilience to signal scattering. Furthermore, the se-
lection of orthogonal codes among different emitters allows the signals to be detected at
the receiver even when collisions take place. This design choice simplifies the associated
implementation complexity because it eliminates the need for tight coordination and syn-
chronization between senders and receivers. The transmitter initiates the distance mea-
surement by advertising to other devices its intention to transmit an acoustic signal with a
particular code at a given time. The receiver starts sampling the acoustic channel at the
specified time and the sampled time series is compared to a locally generated signal using
a sliding correlator. A portion of the observed signal aligned with the reference signal at
the вЂњbestвЂќ offset is shown in Figure 8.6.
Once the distance measurements are completed, a local coordinate system is estab-
lished. Distance measurements are collected at a single aggregation point that uses a mass
spring model to establish an initial coordinate system. Four fully connected, noncoplanar
points close to the aggregation point are initially considered. The mass spring system pro-
vides an initial configuration for these nodes, which is then improved using nonlinear re-
gression to minimize Gaussian measurement error. The RMS error for this set of nodes
based on the testbed measurements is 11.5 cm. After the local coordinate system is
formed, less powerful nodes can discover their location using the location service provid-
ed by the more powerful nodes. According to the testbed results, the RMS position error
for these nodes is 9.2 cm.
Audio input time series matched against reference signal
PPM Reference Signal
0 200 400 600 800 1000 1200 1400 1600 1800 2000