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