Transcript ppt - Department of Computer Engineering

Architectures and Applications
for Wireless Sensor Networks
(01204525)
Localization
Chaiporn Jaikaeo
[email protected]
Department of Computer Engineering
Kasetsart University
Materials taken from lecture slides by Karl and Willig
Overview



Basic approaches
Trilateration
Multihop schemes
2
Localization & positioning

Determine physical position or logical
location



Coordinate system or symbolic reference
Absolute or relative coordinates
Metrics



Accuracy
http://www.mathsisfun.com/accuracy-precision.html
Precision
Costs, energy consumption, …
3
Main Approaches

Based on information
source



Proximity
(Tri-/Multi-)lateration
and angulation
Scene analysis

Radio environment has
characteristic
“signatures”
(x = 5, y = 4)
r2
r3
(x = 8, y = 2)
r1
(x = 2, y = 1)
Angle 1
Le
ng
th
kn
ow
n
Angle 2
4
Estimating Distances – RSSI
Compute distance from Received Signal
Strength Indicator

Problem: Highly error-prone process
PDF
PDF

Distance
Distance
Signal strength
5
Estimating Distances – Others

Time of arrival (ToA)


Use time of transmission, propagation speed,
time of arrival to compute distance
Time Difference of Arrival (TDoA)


Use two different signals with different
propagation speeds
Example: ultrasound and radio signal
6
Determining Angles

Directional antennas







Multiple antennas

Measure time difference between receptions
7
Range-Free Techniques

Overlapping connectivity

Approximate point in triangle
G
B
F
A
?
E
C
?
D
8
Overview



Basic approaches
Trilateration
Multihop schemes
9
Trilateration


Assuming distances to three
points with known location are
exactly given
Solve system of equations(x ,y )
1
1
(x2,y2)
r1
r2
(xu,yu)
r3
(x3,y3)
10
Trilateration as Matrix Equation

Rewriting as a matrix equation:

Example: (x1, y1) = (2,1), (x2, y2) = (5,4),
(x3, y3) = (8,2), r1 = 100.5 , r2 = 2, r3 = 3
11
Trilateration with Distance Errors


What if only distance estimation ri' = ri + i
available?
Use multiple anchors


Overdetermined system of equations
Use (xu, yu) that minimize mean square error, i.e,
12
Minimize Mean Square Error

Look at derivative with respect to x, set it
equal to 0:
 Normal equation
 Has unique solution (if A has full rank), which
gives desired minimal mean square error
13
Example: Distance Error

Anchors' positions and measured distances:
(x,y)
(2,1)
(5,4)
(8,2)
(3,1)
(7,5)
(2,8)
(4,6)
r
5
1
4
2
3
7
4
0.5
Solve A T Axˆ  A Tb
 5. 5 
x̂   
 2. 7 
14
Overview



Basic approaches
Trilateration
Multihop schemes
15
Multihop Range Estimation

No direct radio communication exists
B
X
A
C


Idea 1: Count number of hops, assume
length of one hop is known (DV-Hop)
Idea 2: If range estimates between
neighbors exist, use them

Improve total length of route estimation in
previous method (DV-Distance)
16
Iterative Multilateration
17
Probabilistic Position Description

Position of nodes is only probabilistically known


Represent this probability explicitly
Use it to compute probabilities for further nodes
18
Conclusions

Determining location or position is a vitally
important function in WSN, but fraught with
many errors and shortcomings




Range estimates often not sufficiently
accurate
Many anchors are needed for acceptable
results
Anchors might need external position sources
(GPS)
Multilateration problematic (convergence,
accuracy)
19