Transcript ppt
Localization Techniques in
Wireless Networks
ECE 591
Instructions
Print my last name WANG in the STUDENT NAME box.
There is NO need to fill in the corresponding ovals.
Print course and section number 59102 (for ECE591) in
the first 5 positions of the STUDENT ID NUMBER box.
There is NO need to fill in the corresponding ovals.
Queries on the Questionnaire are matched to the
numbers on the Answer Sheet.
E: Strongly Agree; D: Agree; C: Neutral; B: Disagree; A: Strongly Disagree
2
Motivation
Technology trends creating cheap wireless communication in every computing
device
Radio offers localization opportunity in 2D and 3D
New capability compared to traditional communication networks
Research Challenge
General purpose localization analogous to general purpose
communication.
Work on any wireless device with little/no modification
Supports vast range of performance
Device always “knows where it is”
“Lost” --- no longer a concern
Use only the existing communication infrastructure?
Background: Localization Strategies
Scene matching
The best match on a previously constructed radio map
A classifier problem: “best” spot that matches the data
Lateration and Angulation
Use distances, angles to landmarks to compute positions
Scene Matching
Build a radio map
[X,Y,RSS1,RSS2,RSS3]
Training data
Classifiers:
Bayes’ rule
Max. Likelihood
Machine learning (SVM)
Slow, error prone
Have to change when
environment changes
Lateration and Angulation
D1
D2
D3
D4
Observing Distances and Angles
Received Signal Strength
(RSS) to Distance
RSS to Angle of Arrival (AoA)
Path loss models
In absence of noise
Directional antenna models
Time-of-Flight to
distance(ToF)
Speed of light
signal that has strength A at a unit distance from
the source. Suppose the signal strength at a
distance from the source is s. β is the path loss
coefficient
RSS to Angle
-40
RSS (dBm)
Actual
Smoothed
Modeled
-80
0
Angle (degrees)
Results Overview
Last 6 years --- many, many varied efforts
Most are simulation, or trace-driven simulation
Scene matching
802.11, 802.15.4: Room/2-3m
Need
accuracy [Elnahrawy 04]
lots of training data
Lateration and Angulation
802.11, 802.15.4: Room/3-4m
accuracy
Real deployments worse than theoretical models predict (1m)
Network Localization Algorithm
Motivations
Location-aware computing
Sensor network applications
Resource Selection (server, printer, etc.)
Location aware information services (web-search, advertisement,
etc.)
Inventory management, intruder detection, traffic monitoring,
emergency crew coordination, air/water quality monitoring,
military/intelligence apps
Geographic routing in ad hoc networks
Scalable, lightweight, fault-tolerant protocols
Current location more important than identity
Geographical Routing
Each node only needs to keep state (positions) of its
neighbors
each node broadcasts its MAC and position
S
D
GeoRouting: Greedy Distance
Closest
to D
S
A
-Find neighbors who are the closest to destination
D
Localization Problem
Given:
Set of n points in the plane,
Distances between m pairs of points.
Find:
Positions of all n points…
Illustration:
node with unknown position
distance measurement
Localization problem “rephrasing”
2
3
1
0
6
Given:
0 d01 d02 d03 d04 d05 d06
d10 0 d12 ? ? ? d16
d20 d21 0 d23 ? ? ?
d30 ? d32 0 d34 ? ?
d40 ? ? d43 0 d45 ?
d50 ? ? ? d54 0 d56
d60 d61 ? ? ? d65 0
4
5
Find:
0 d01 d02 d03 d04 d05 d06
d10 0 d12 d13 d14 d15 d16
d20 d21 0 d23 d24 d25 d26
d30 d31 d32 0 d34 d35 d36
d40 d41 d42 d43 0 d45 d46
d50 d51 d52 d53 d54 0 d56
d60 d61 d62 d63 d64 d65 0
2
2
3
1
1
0
6
3
4
5
0
6
4
5
Remove one edge… and the problem becomes unsolvable
Given:
0 d01 d02 d03 d04 d05 d06
d10 0 d12 ? ? ? ?
d20 d21 0 d23 ? ? ?
d30 ? d32 0 d34 ? ?
d40 ? ? d43 0 d45 ?
d50 ? ? ? d54 0 d56
d60 ? ? ? ? d65 0
Cannot Find!
0 d01 d02 d03 d04 d05 d06
d10 0 d12 d13 d14 d15 d16
d20 d21 0 d23 d24 d25 d26
d30 d31 d32 0 d34 d35 d36
d40 d41 d42 d43 0 d45 d46
d50 d51 d52 d53 d54 0 d56
d60 d61 d62 d63 d64 d65 0
Two Cases
2
{x1, x2, x3}
2
{d14, d24, d34}
4
1
1
4
3
3
In general, this graph is
uniquely realizable.
Case 1:
4
1
2
first case: {x4}
second case: ???
3
2
?
Case 2:
?
1
3
In degenerate case, it is not
Network Localization Problem
Illustration:
Given:
Set of n points in the plane,
Positions of k of them,
Distances between m pairs of points.
Find:
Positions of all n points.
node with known position (beacon)
node with unknown position
distance measurement