. 48
( 87 .)


Figure 8.6. Pulse position modulated reference signal aligned with observed signal, captured under
very low noise conditions.
8.4 AD HOC TECHNIQUES FOR LOCATION DISCOVERY A Self-Localization Method for Wireless Sensor Networks (SLM).
Another notable localization method has been developed in [23]. In this work, Moses et
al. have shown that sensor node positions and orientations can be estimated using signals
from acoustic sources with unknown locations. Each acoustic source generates a known
acoustic signal that is detected by the sensor nodes. The sensor nodes in turn measure the
ToA and DoA of the signal and propagate this information to a central information-pro-
cessing center (CIP). The CIP fuses the information using maximum likelihood estima-
tion to obtain the location and orientation of the sensor nodes.
In addition to this algorithm, the authors of [23] also treat the case in which only partial
measurements are available. This occurs when the source signal is detected only by a sub-
set of the nodes or when some sensors have only one successful measurement of either
ToA or DoA. Ad Hoc Positioning System (APS). The Ad Hoc Positioning System pro-
posed by Nicolescu and Nath in [21] estimates the locations in an ad hoc network by con-
sidering distances to a set of landmarks. This study explores three alternative propagation
methods: DV-hop, DV-distance, and Euclidean.
In the DV-hop method, landmarks propagate their location information inside the net-
work. Each node forwards the landmark information to its neighbors and maintains a table
with the landmark identification (ID), location, and hop distance. When a landmark re-
ceives one of the propagated packets with the position of a different landmark, it uses that
information to calculate the average hop distance between the two landmarks. The com-
puted average hop distance is broadcast back into the network as a correction to previous-
ly known hop distances. The nodes that receive this message use the average hop distances
to each of the landmarks to estimate their distances to the landmarks. This information is
then used to triangulate the node location. The corrections are propagated in the network
using controlled flooding. Each node will forward a correction from a certain landmark
only once in an effort to ensure that nodes will receive only one correction from the clos-
est landmark. This policy tries to account for anisotropies in the network.
The DV-distance approach is similar to DV-hop but uses radio received signal strength
measurements to measure distances. Although this approach gives finer-level granularity, it
is also the most sensitive to measurement error since the received signal strength is greatly
influenced by the surrounding environment and is, therefore, not always consistent.
The Euclidean propagation method uses the true distance measurement to a landmark.
In this case, nodes that have at least two distance measurements to nodes that have dis-
tance estimates to a landmark can use simple trigonometric relationships to estimate their
The reported simulation results indicate that the DV-hop propagation method is the
most accurate of the three and determines the positions of nodes within one-third of the
radio range in dense networks. Robust Positioning Algorithms for Distributed Ad Hoc Wireless
Sensor Networks (RPAD). The algorithm described in [26] explores the same prob-
lem setup as APS. It estimates the positions of nodes in an ad hoc network by utilizing in-
ternode distance measurements and a set of anchor nodes. Position estimation is carried
out in two phases: startup and refinement. The former provides a set of crude estimates for
the node locations, whereas the latter refines these estimates using a least squares algo-
rithm to obtain the final estimates.

The Hop-TERRAIN algorithm is similar to the DV-hop algorithm used in the APS sys-
tem. First, each node in the network finds out the number of hops to each anchor node.
When an anchor node receives the number of hops to another anchor, it then computes the
average hop distance and broadcasts it back into the network. Nodes with unknown loca-
tions multiply the number of hops with the average hop distance to get an estimate for the
distance to the anchor nodes. The nodes then perform a triangulation to obtain an initial
estimate with respect to the anchor nodes. One potential problem with Hop-TERRAIN is
that nodes with the same hop distances to the anchor nodes arrive at the same initial posi-
tion estimate. This problem can be avoided by excluding one of the anchor points so that
the nodes have at least one different reference point.
The refinement phase uses the estimated distances of the one-hop neighbors of each
node to obtain more accurate position estimates. Refinement is an iterative process that
uses a least squares solution. At each iteration, each node with unknown location com-
putes and broadcasts its position estimate to its neighbors. The neighbor nodes use this in-
formation to update their estimate and rebroadcast it back to their neighbors where the
new information is included in the computation of the next iteration. The algorithm termi-
nates when a maximum number of iterations is completed.
The study of this refinement algorithm revealed two main problems:

1. Error propagation through the network.
2. Hard network topologies. These are cases there the whole or parts of the network
can be rotated while keeping the intranode ranges. This problem was originally
identified in [27] and will also be described in the next subsection.

To address the first issue, the authors perform the least squares computation using
weights (see Section 8.3.2) that correspond to the confidence level for each location. The
confidence levels vary between 0 and 1. Initially, anchor nodes have confidence level 1
and nodes with unknown locations have a confidence level 0.01. At each iteration of the
algorithm, the confidence level of the node that computes a new estimate is set to the av-
erage of the confidence levels of its neighbors. In most cases, this gradually raises the
confidence level of the nodes. If the triangulation fails due to insufficient constraints or
because the computed result does not meet some other consistency checks, then the confi-
dence level of the node is set to 0 so that other nodes in the next iteration do not use it. The
node failing to improve its confidence level may try to recompute its location in subse-
quent iterations. If the computed result is rejected multiple times, then the node is exclud-
ed from the refinement process. The simulation results note that although the use of con-
fidence level yields an improvement of the average error in computed locations, it cannot
be used as an indicator of the estimated accuracy.
For the second problem of hard topologies, the authors propose a heuristic that detects
most of the ill-connected configurations. In such configurations, although each unknown
node has at least three neighbors, the whole network or parts of the network can be rotated
while still maintaining a consistent pattern. This is illustrated in the example network
topology of Figure 8.7, which originally appeared in [27]. Node 4 in the example has two
possible positions that are consistent with the distance measurements. To determine if a
certain topology is sound, the Hop-TERRAIN records the ID of each node™s immediate
neighbor on the shortest path to each anchor point. If multiple shortest paths are available,
then the ID for the node on the first shortest path found is recorded. When the number of


Unknown Location
2 Beacon

Figure 8.7. An example of an ill-constrained topology.

unique IDs in this set reaches three (four for three dimensional scenarios), the node de-
clares itself sound and enters the refinement phase. The neighbors of the sound nodes add
this node to their sound set and the process continues around the network. This process is
repeated throughout the network and identifies the majority of ill-connected configura-
According to the simulation results, the robust positioning algorithm achieves, on aver-
age, position errors of less than 33% of a node™s radio range in the presence of a 5% range
measurement error when at least 5% of the nodes are anchor nodes. Ad Hoc Localization System (AHLoS). The Ad Hoc Localization System
developed at the University of California, Los Angeles [27, 28] focuses on the fine-
grained localization of sensor nodes in an ad hoc network. The core component of the sys-
tem is collaborative multilateration, a method that allows nodes with unknown locations
to collaborate with each other and jointly estimate their location based on some initial
beacon information and a set of distance measurements between the nodes. With this
method, the direct line of sight to beacons requirement is relaxed to an indirect line of
sight to beacons requirement that enables nodes to estimate their locations even when bea-
con nodes are found multiple hops away. Collaborative multilateration is provided in two
computation models, centralized and distributed. The centralized model operates based on
a global view of the network. It uses all beacon node location information and all the in-
ternode distance measurements as constraints to set up a global nonlinear optimization
problem that is then solved using iterative least squares. By considering all the constraints
in the network at the same time, this solution minimizes error propagation incurred by the
use of measurements over multiple hops.
The distributed computation model is an approximation of the centralized model that is
also based on iterative least squares but distributes computation evenly to all nodes with
unknown locations. This results in significantly less computation and provides a more ro-
bust setup for ad hoc networks. Furthermore, it enables small resource-constrained nodes
to collaborate among each other to set up and solve a nonlinear optimization problem with
local computation but with respect to the global constraints, a task that none of the nodes
can perform individually.
Collaborative multilateration is based on a three-phase process. First, before position
estimation can start, nodes need to organize themselves into groups. These groups, re-
ferred to as collaborative subtrees, ensure that all the unknown nodes included in each
group are well constrained or overconstrained so that the estimation problem has a unique
solution. The second phase uses simple geometric relations to estimate a set of initial po-

sition estimates for each unknown node. These estimates are used to initialize the third
phase, a refinement phase that uses an iterative least squares algorithm. A good set of ini-
tial estimates is required to ensure that the iterative process does not get stuck at local

Computing Initial Estimates. A set of initial estimates is obtained by applying the dis-
tance measurements as constraints on the x and y coordinates of the nodes. Figure 8.8a
shows how the distance measurements from two beacons A and B can be used to obtain
the x coordinate bounds for the unknown node C. If the distance between an unknown
and the beacon A is , the x coordinates of node C are bounded to the left and to the
right of the x coordinate of the coordinate of beacon A, xA “ and xA + . Beacon B
imposes its constraints in the same way. Similarly, if beacon B is two hops away from C
(as in Figure 8.8b), the coordinates bounds of node C are defined by the length of the
minimum weight path to C, b + c, so the bounds for C x-coordinates with respect to B
are xB “ (b + c) and xB + (b + c). By knowing this information, C can determine that its
x coordinate bounds with respect to beacons A and B are xB + (b + c) and xA “ . This
operation selects the tightest left-hand-side bound and the tightest right-hand-side bound
from each beacon. The same operation is applied on the coordinates. The node then
combines its bounds on the x and y coordinates to construct a bounding box of the re-

x coordinate bounds for node C: x coordinate bounds for node C:
[x A ’ a ] to [xB + b] [x A ’ a ] [x B + (b + c )]
from to

a Aa
a Aa a
b+c b+c
b b

7 3 5

Initial Estimate


Figure 8.8. Obtaining initial position estimates.

gion where the node lies. To obtain this bounding box, the locations of all the beacons
are forwarded to all unknowns along a minimum weight path. This forwarding is simi-
lar to distance vector routing (e.g., DSDV) but uses the measured distances instead of
hops as weights.
The initial position estimate of a node is taken to be as the center of the bounding box.
When these constraints are combined with the conditions for position uniqueness, they
provide a good set of initial estimates for the iterative least squares algorithm used in the
next phase. The resulting initial estimates for a 10-node network with three beacons is
shown in Figure 8.8c. The initial estimates for each node (shown as crosses in the figure)
are close to the actual node positions and provide a good starting point for the refinement
process. One challenge in this method is that the quality of the initial estimates suffers
when the unknown nodes lie far outside the convex hull formed by the beacons on the
perimeter of the collaborative subtree, and then the initial estimates degrade. In our exper-
iments with large networks, we deploy some of the beacons on the edges of the sensor

Centralized Computation Model. The centralized computation solved a nonlinear op-
timization problem by considering the global topology. This is illustrated by the example
network in Figure 8.9. In this example node 1, 2, 5, and 6 are beacons and nodes 3 and 4
have unknown locations.
The nodes can perform a total of five distance measurements that provide the follow-
ing five constraints:

(x2 “ ex3)2 + (y2 “ ry3)2
f2,3 = r2,3 “

(ex3 “ x5)2 + (ey3 “ y5)2
f3,5 = r3,5 “

(ex4 “ ex3)2 + (ey4 “ ey3)2
f4,3 = r4,3 “

(ex4 “ x5)2 + (ey4 “ y5)2
f4,5 = r4,5 “

(ex4 “ x1)2 + (ey4 “ y1)2
f4,1 = r4,1 “

Solving a similar objective function as in the case of the single-hop setup described in
Section 7.3.1 we have

F(x3, y3, x4, y4) = min i,


. 48
( 87 .)