ñòð. 48 |

very low noise conditions.

245

8.4 AD HOC TECHNIQUES FOR LOCATION DISCOVERY

8.4.2.5 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.

8.4.2.6 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

locations.

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.

8.4.2.7 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.

246 LOCATION DISCOVERY

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

247

8.4 AD HOC TECHNIQUES FOR LOCATION DISCOVERY

4'

1

5

Unknown Location

3

4

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-

tions.

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.

8.4.2.8 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-

248 LOCATION DISCOVERY

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

minima.

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

from

a Aa

a Aa a

c

C C

a

b

b

b+c b+c

b b

B B

(b)

1

(a)

4

2

6

7 3 5

8

Beacon

9

Unknown

Initial Estimate

0

(c)

Figure 8.8. Obtaining initial position estimates.

249

8.4 AD HOC TECHNIQUES FOR LOCATION DISCOVERY

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

field.

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

f2j

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

ñòð. 48 |