Power Point Presentation - Radar 03
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Power Point Presentation - Radar 03 as PDF for free.
More details
- Words: 1,504
- Pages: 35
Location-Aware Services in an In-Building Environment Collaborators: Victor Bahl, Venkat Padmanabham, Anand Balachandran (UCSD), Yi-Min Wang, and Wilf Russell
The RADAR System Research Goal Leverage the existing infrastructure of an indoor RF wireless LAN to build applications that take advantage of location information.
Victor Bahl
Related Work in Positioning System Outdoor (Cellular) Systems GPS, DGPS, etc. (QualComm/SnapTrack, …) Time Difference of Arrival (TruePosition System…) Angle of Arrival (KSI, … )
Solutions designed for the outdoors are either ineffective or too costly indoors Victor Bahl
Related Work in Indoor Positioning Systems Infrared-based systems AT&T Research’s Active Badge System Accurate due to short range and line-of-sight property Scales poorly, limited by LoS, requires specialized infrastructure
Radio Frequency-based systems Cell-level granularity [HKSR97] Duress Alarm Location System, PinPoint
Alternative technologies: magnetic, optical, acoustic MIT’s Cricket System (MobiCom ‘99, ‘00), AT&T’s Bat Very accurate (cm resolution) Requires dedicated infrastructure Targeted at specialized applications, e.g. head tracking, Orientation etc. Victor Bahl Traditional approach has been based on dedicated technology and infrastructure
The RADAR System Our Approach Leverage existing infrastructure Use off-the-shelf RF wireless LAN Several advantages WLAN deployed primarily to provide data connectivity software adds value to wireless hardware better scalability and lower cost than all available solutions Not too hard to install and easy to manage one-time cost for building signal-strength database one-time cost for building the location hierarchy
Three Components User Location and Tracking Location Information Management Programmability Victor Bahl
Location Determination Algorithmic Components RF fingerprinting and matching RF environment profiling and matching Trajectory prediction Scanning and channel switching Location databases and location services
A P
Access Point 2 A P
Access Point 1
Access Point 4 Mobile User
A P
Access Point 3
Victor Bahl
Signal Strength (dBm)
How good an indicator of location is signal strength? BS 1
BS 2
40
60
BS 3
40 35 30 25 20 15 10 5 0 0
20
80
100
Distance along w alk (meters)
Signal strength correlates well with distance Victor Bahl
Signal Processing in RADAR Key idea: Map signal strengths to physical locations (Radio Fingerprinting)
Inputs: signal strength of access point beacons building geometry
Offline phase: Construct a Radio Map tabulate information
Real-time phase: extract SS from base station beacons find Radio Map entry that best matches the measured SS Victor Bahl
Radio Map Construction Empirical method Access Points emit beacons periodically measure SS at various locations record SS along with corresponding coordinates • •
user orientation needs to be included too! tuples of the form (x,y,z,d,s1,…,sn)
accurate but laborious
Mathematical method compute SS using a simple propagation model • •
factor in free space loss and wall attenuation Cohen-Sutherland line clipping algorithm
more convenient but less accurate Victor Bahl
Demo
RADAR Demo
Victor Bahl
Baseline Performance Empirical
Strongest BS
Random
1.2
Probability
1 0.8 0.6 0.4 0.2 0 0
10
20
30
40
50
Error distance (meters)
Median error distance is 2.94 meters Victor Bahl
Neighbor Averaging Find nearest neighbor in signal space (NNSS) default metric is Euclidean distance
Phys. coordinates of NNSS ⇒ user location Refinement: k-NNSS average the coordinates of k nearest neighbors
N1
N1, N2, N3: neighbors T: true location of user G: guess based on averaging
T G N2
N3 Victor Bahl
Performance with Averaging Error distance (meters)
25th
50th
3.5 3 2.5 2 1.5 1 0.5 0 0
2
4
6
8
10
Number of neighbors averaged (k)
Median error distance is 2.13 meters when averaging is done over 3 neighbors Victor Bahl
How extensive does the Radio Map have to be? Error distance (meters)
25th
50th
14 12 10 8 6 4 2 0 1
10
100
Size of empirical data set (# physical points, n )
Diminishing returns as the number of physical points mapped increases Victor Bahl
Radio Map Construction with RF Modeling 40
40
35
35 Signal Strength (dBm)
Signal Strength (dBm)
Signal Propagation Measurements
30 25 20 15 10 5
30 25 20 15 10 5
0
0
0
5
10
15
20 Distance (m)
25
30
35
40
0
5
10
15
20
25
30
35
40
Distance (m)
d nW *WAF P (d )[ dBm ] = P ( d o )[ dBm ] − 10 n log − d o C *WAF
nW < C nW ≥ C
Model parameters: P(d0) = 28 dBm, n = 1.53, WAF = 3.1 dBm, C = 4 walls Victor Bahl
How well does WAF work? 50
Signal Strength (dBm)
45 40 35 30 25 20 15 10 5 0 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 Sample
Median error distance is 4.94 m compared to 2.94 m with empirically constructed radio map and 8.16 m with nearest base station method Victor Bahl
Are User Trajectory and Speed Predictable?
Signal processing, and pattern recognition allow mobility management Victor Bahl
Mobility Modeling and Prediction User’s previous locations can provide a good hint of her next location guess
Mean
i
90th %tile
8
k
.
2 number of signal strength samples
h
Error distance (meters)
dij j
1
Median
7 6 5 4 3 2 1 0 NNSS
NNSS-AVG
Viterbi
Victor Bahl
Environmental Profiling RF propagation characteristics change all the time
A P
Win = 4
50
100
Win = 14
Access Point 2 Access Point 1
Access Point 4
Environmental state
2.5
A P
Mobile User
Actual
2 1.5 1 0.5 0
A P
Access Point 3
0
150
200
Signal strength sample sequence number
Calculate location of known AP using different Radio Maps. Select the one that produces best result. Victor Bahl
Channel Switching For the mobile to “hear” neighboring APs – all APs must be on the same channel
Aquiring beacons
Effects overall system cost
AP1 on Ch. 1 Mobile on Ch.1
Switching channels to listen to AP beacons is possible Degrades performance considerably
AP2 on Ch. 6 AP3 on Ch. 11 Channel Switching Time = 10 msec Beacons Interval = 100 msec
Victor Bahl
Programming Requirements for RADAR Ability of the wireless NIC to scan specified channels.
For every incoming packet from a specified MAC address, ability to retrieve the packet’s - received signal strength, - noise floor at the transmitter, and - noise floor at the receiver.
Victor Bahl
AP Monitor in WinXP Windows XP contains the necessary support to enable RADAR
Victor Bahl
Experimental Testbeds Testbed 1 (Bldg. 31/2)
Testbed 2 (Bldg. 112/2)
Hardware
RoamAbout
Aironet/Cisco
MAC
CSMA/CA
IEEE 802.11b
Modulation
SS DQPSK
SS CCK
Power
50 mW
30 mW
Raw Date Rate
1, 2 Mbps
1,2, 5.5, 11 Mbps
# of APs
3
5
Floor
43.2 m x 22.5 m
42.9 m x 21. 8 m
OS
FreeBSD 3.0
Windows 2000 Victor Bahl
Exploiting Location Country
Subscription based: Location Information Service Location Alert Service Location based Buddy List Service OnSale Mall Buddy Service
Network Improvements
State
Territory
County
County
City
City
Absolute Location Campus (longitude, latitude, altitude) Building
AP Load balancing Node-level QoS
Campus Building
Area
... Floor
Access Point
Printer
Copier
Scanner
Relative Location (meters, meters, floor)
Victor Bahl
Location Information Service WISH (Where IS Harry?) “I wish I knew where Harry is.”
User location system that works with Wireless LANs Usage scenarios - Locate people and devices - Discover nearby resources (printers, offices, restrooms, etc.)
Victor Bahl
Location Information Service Architecture
http://wish
WISH Client WiLIB
Every 2 minutes
Every 30 seconds
Eventing Infrastructure
Every 30 seconds
WISH Server
Device Driver Every 30 seconds Access Point
Victor Bahl
Where IS Harry Service
Victor Bahl
Location Alert Service When I can’t find Harry… “Alert me when you find Harry.”
Soft-state eventing infrastructure to trigger alerts when event matches are found. Personalized alert delivery through Instant Messaging, emails, cell phone SMS
Victor Bahl
Location Alert Service Architecture WISH
WISH
Client
Server
WISH Alert Service
Alert Subscription Page Eventing Infrastructure
SIMBA Library
IM Email SMS
MyAlertBuddy Email
IM Victor Bahl
Location-Based Buddy List Service When Harry is my buddy.. “Alert me if Harry happens to be close by.”
Subject-based publish/subscribe eventing based on user profiles Integrated tightly with MSN buddy list
Victor Bahl
Location-Based Buddy List Service Architecture Mall Buddy Client
Wilf
Buddy List
“Victor is in the mall.”
Victor
http://www.mschoice.com http://choice
Mall Buddy Server
Mall Buddy Client
Buddy List
Eventing Infrastructure
“Wilf is in the mall.” Victor Bahl
OnSale Mall Buddy Service Personalized sales announcements “Alert me when electronics are on sale.”
Subject-based publish/subscribe eventing based on product categories and user profiles
Victor Bahl
OnSale Mall Buddy Service Architecture Shopping Profiles
Profile s Mall Buddy Client
Wilf
Victor
Mall Buddy Client
Mall Buddy Server “Electronics are on sale.”
OnSale Server Eventing Infrastructure Victor Bahl
Summary Takes advantage of existing Wireless LAN infrastructure Easy to install and manage one-time cost for building signal-strength database one-time cost for building the location hierarchy
System does not require line-of-site communication Provides security, replication, partitioning for scalability, and back-up and restore RADAR: a software solution to indoor location determination Victor Bahl
Thanks! http://research.microsoft.com/~bahl
The RADAR System Research Goal Leverage the existing infrastructure of an indoor RF wireless LAN to build applications that take advantage of location information.
Victor Bahl
Related Work in Positioning System Outdoor (Cellular) Systems GPS, DGPS, etc. (QualComm/SnapTrack, …) Time Difference of Arrival (TruePosition System…) Angle of Arrival (KSI, … )
Solutions designed for the outdoors are either ineffective or too costly indoors Victor Bahl
Related Work in Indoor Positioning Systems Infrared-based systems AT&T Research’s Active Badge System Accurate due to short range and line-of-sight property Scales poorly, limited by LoS, requires specialized infrastructure
Radio Frequency-based systems Cell-level granularity [HKSR97] Duress Alarm Location System, PinPoint
Alternative technologies: magnetic, optical, acoustic MIT’s Cricket System (MobiCom ‘99, ‘00), AT&T’s Bat Very accurate (cm resolution) Requires dedicated infrastructure Targeted at specialized applications, e.g. head tracking, Orientation etc. Victor Bahl Traditional approach has been based on dedicated technology and infrastructure
The RADAR System Our Approach Leverage existing infrastructure Use off-the-shelf RF wireless LAN Several advantages WLAN deployed primarily to provide data connectivity software adds value to wireless hardware better scalability and lower cost than all available solutions Not too hard to install and easy to manage one-time cost for building signal-strength database one-time cost for building the location hierarchy
Three Components User Location and Tracking Location Information Management Programmability Victor Bahl
Location Determination Algorithmic Components RF fingerprinting and matching RF environment profiling and matching Trajectory prediction Scanning and channel switching Location databases and location services
A P
Access Point 2 A P
Access Point 1
Access Point 4 Mobile User
A P
Access Point 3
Victor Bahl
Signal Strength (dBm)
How good an indicator of location is signal strength? BS 1
BS 2
40
60
BS 3
40 35 30 25 20 15 10 5 0 0
20
80
100
Distance along w alk (meters)
Signal strength correlates well with distance Victor Bahl
Signal Processing in RADAR Key idea: Map signal strengths to physical locations (Radio Fingerprinting)
Inputs: signal strength of access point beacons building geometry
Offline phase: Construct a Radio Map tabulate
Real-time phase: extract SS from base station beacons find Radio Map entry that best matches the measured SS Victor Bahl
Radio Map Construction Empirical method Access Points emit beacons periodically measure SS at various locations record SS along with corresponding coordinates • •
user orientation needs to be included too! tuples of the form (x,y,z,d,s1,…,sn)
accurate but laborious
Mathematical method compute SS using a simple propagation model • •
factor in free space loss and wall attenuation Cohen-Sutherland line clipping algorithm
more convenient but less accurate Victor Bahl
Demo
RADAR Demo
Victor Bahl
Baseline Performance Empirical
Strongest BS
Random
1.2
Probability
1 0.8 0.6 0.4 0.2 0 0
10
20
30
40
50
Error distance (meters)
Median error distance is 2.94 meters Victor Bahl
Neighbor Averaging Find nearest neighbor in signal space (NNSS) default metric is Euclidean distance
Phys. coordinates of NNSS ⇒ user location Refinement: k-NNSS average the coordinates of k nearest neighbors
N1
N1, N2, N3: neighbors T: true location of user G: guess based on averaging
T G N2
N3 Victor Bahl
Performance with Averaging Error distance (meters)
25th
50th
3.5 3 2.5 2 1.5 1 0.5 0 0
2
4
6
8
10
Number of neighbors averaged (k)
Median error distance is 2.13 meters when averaging is done over 3 neighbors Victor Bahl
How extensive does the Radio Map have to be? Error distance (meters)
25th
50th
14 12 10 8 6 4 2 0 1
10
100
Size of empirical data set (# physical points, n )
Diminishing returns as the number of physical points mapped increases Victor Bahl
Radio Map Construction with RF Modeling 40
40
35
35 Signal Strength (dBm)
Signal Strength (dBm)
Signal Propagation Measurements
30 25 20 15 10 5
30 25 20 15 10 5
0
0
0
5
10
15
20 Distance (m)
25
30
35
40
0
5
10
15
20
25
30
35
40
Distance (m)
d nW *WAF P (d )[ dBm ] = P ( d o )[ dBm ] − 10 n log − d o C *WAF
nW < C nW ≥ C
Model parameters: P(d0) = 28 dBm, n = 1.53, WAF = 3.1 dBm, C = 4 walls Victor Bahl
How well does WAF work? 50
Signal Strength (dBm)
45 40 35 30 25 20 15 10 5 0 1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 Sample
Median error distance is 4.94 m compared to 2.94 m with empirically constructed radio map and 8.16 m with nearest base station method Victor Bahl
Are User Trajectory and Speed Predictable?
Signal processing, and pattern recognition allow mobility management Victor Bahl
Mobility Modeling and Prediction User’s previous locations can provide a good hint of her next location guess
Mean
i
90th %tile
8
k
.
2 number of signal strength samples
h
Error distance (meters)
dij j
1
Median
7 6 5 4 3 2 1 0 NNSS
NNSS-AVG
Viterbi
Victor Bahl
Environmental Profiling RF propagation characteristics change all the time
A P
Win = 4
50
100
Win = 14
Access Point 2 Access Point 1
Access Point 4
Environmental state
2.5
A P
Mobile User
Actual
2 1.5 1 0.5 0
A P
Access Point 3
0
150
200
Signal strength sample sequence number
Calculate location of known AP using different Radio Maps. Select the one that produces best result. Victor Bahl
Channel Switching For the mobile to “hear” neighboring APs – all APs must be on the same channel
Aquiring beacons
Effects overall system cost
AP1 on Ch. 1 Mobile on Ch.1
Switching channels to listen to AP beacons is possible Degrades performance considerably
AP2 on Ch. 6 AP3 on Ch. 11 Channel Switching Time = 10 msec Beacons Interval = 100 msec
Victor Bahl
Programming Requirements for RADAR Ability of the wireless NIC to scan specified channels.
For every incoming packet from a specified MAC address, ability to retrieve the packet’s - received signal strength, - noise floor at the transmitter, and - noise floor at the receiver.
Victor Bahl
AP Monitor in WinXP Windows XP contains the necessary support to enable RADAR
Victor Bahl
Experimental Testbeds Testbed 1 (Bldg. 31/2)
Testbed 2 (Bldg. 112/2)
Hardware
RoamAbout
Aironet/Cisco
MAC
CSMA/CA
IEEE 802.11b
Modulation
SS DQPSK
SS CCK
Power
50 mW
30 mW
Raw Date Rate
1, 2 Mbps
1,2, 5.5, 11 Mbps
# of APs
3
5
Floor
43.2 m x 22.5 m
42.9 m x 21. 8 m
OS
FreeBSD 3.0
Windows 2000 Victor Bahl
Exploiting Location Country
Subscription based: Location Information Service Location Alert Service Location based Buddy List Service OnSale Mall Buddy Service
Network Improvements
State
Territory
County
County
City
City
Absolute Location Campus (longitude, latitude, altitude) Building
AP Load balancing Node-level QoS
Campus Building
Area
... Floor
Access Point
Printer
Copier
Scanner
Relative Location (meters, meters, floor)
Victor Bahl
Location Information Service WISH (Where IS Harry?) “I wish I knew where Harry is.”
User location system that works with Wireless LANs Usage scenarios - Locate people and devices - Discover nearby resources (printers, offices, restrooms, etc.)
Victor Bahl
Location Information Service Architecture
http://wish
WISH Client WiLIB
Every 2 minutes
Every 30 seconds
Eventing Infrastructure
Every 30 seconds
WISH Server
Device Driver Every 30 seconds Access Point
Victor Bahl
Where IS Harry Service
Victor Bahl
Location Alert Service When I can’t find Harry… “Alert me when you find Harry.”
Soft-state eventing infrastructure to trigger alerts when event matches are found. Personalized alert delivery through Instant Messaging, emails, cell phone SMS
Victor Bahl
Location Alert Service Architecture WISH
WISH
Client
Server
WISH Alert Service
Alert Subscription Page Eventing Infrastructure
SIMBA Library
IM Email SMS
MyAlertBuddy Email
IM Victor Bahl
Location-Based Buddy List Service When Harry is my buddy.. “Alert me if Harry happens to be close by.”
Subject-based publish/subscribe eventing based on user profiles Integrated tightly with MSN buddy list
Victor Bahl
Location-Based Buddy List Service Architecture Mall Buddy Client
Wilf
Buddy List
“Victor is in the mall.”
Victor
http://www.mschoice.com http://choice
Mall Buddy Server
Mall Buddy Client
Buddy List
Eventing Infrastructure
“Wilf is in the mall.” Victor Bahl
OnSale Mall Buddy Service Personalized sales announcements “Alert me when electronics are on sale.”
Subject-based publish/subscribe eventing based on product categories and user profiles
Victor Bahl
OnSale Mall Buddy Service Architecture Shopping Profiles
Profile s Mall Buddy Client
Wilf
Victor
Mall Buddy Client
Mall Buddy Server “Electronics are on sale.”
OnSale Server Eventing Infrastructure Victor Bahl
Summary Takes advantage of existing Wireless LAN infrastructure Easy to install and manage one-time cost for building signal-strength database one-time cost for building the location hierarchy
System does not require line-of-site communication Provides security, replication, partitioning for scalability, and back-up and restore RADAR: a software solution to indoor location determination Victor Bahl
Thanks! http://research.microsoft.com/~bahl
Related Documents
Power Point Presentation - Radar 03
May 2020 6
Power Point Presentation - Radar
May 2020 7
Radar Fundamentals Power Point Presentation
May 2020 12
Power Point Presentation - Radar 04
May 2020 12
19143532-power-point-presentation-radar[1]
May 2020 3
Radar Presentation 03
April 2020 1More Documents from "cozdim"
Fina Training Report
July 2020 16
Tv Vocational Training Project
July 2020 20
Power Point Presentation - Radar02
May 2020 24
Tv Studio Of Presentation
July 2020 14
Computer Network File(mpct)
June 2020 18