стр. 47 |

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 [3] and [6] 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

nodes.

8.4.2.1 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

241

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.

8.4.2.2 Convex Position Estimation in Wireless Sensor Networks (CPE).

The convex position estimation algorithm described in [6] 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

known.

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

communication range.

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.

8.4.2.3 GPS-Free Positioning in Mobile Ad Hoc Networks (GPSFP). The sys-

tem described in [4] and developed as part of the Terminode project [11] 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

2 2

pq

= arcos

2diqdip

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)

j

if =| вЂ“ | => dij sin (8.7)

j j j

else => jy = вЂ“dij sin (8.8)

j

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

q

diq

dpq

djq

ОіОІ

i jx p

dip

О±

dij dpj

jy

j

Figure 8.4. Local coordinate system formation example.

243

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.

8.4.2.4 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 [7]) uses a fine-grained time synchroniza-

tion service and a wideband pseudonoise sequence to measure ToF of an acoustic signal

y

l

kl

k

x

ik

il = ik + kl

y

i x

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

20000

Observed Signal

PPM Reference Signal

15000

10000

Sensor value

5000

0

-5000

-10000

-15000

0 200 400 600 800 1000 1200 1400 1600 1800 2000

Samples

стр. 47 |