Fast and Accurate Indoor Localization based on
Spatially Hierarchical Classification
Duc A. Tran (UMass Boston)
Cuong Pham (Microsoft Corp.)
10/28/14 @ IEEE MASS 2014
1 / 20
Indoor Localization: Demand
10/28/14 @ IEEE MASS 2014
2 / 20
Indoor Localization: Requirement
Fast/Efficient?
"Where am I?" – "Let me think!"
Think "critical"! (fire rescue, evacuation in a building)
Think "scalable"! (real-time service to thousands of shoppers in a
mall)
Accurate?
"Where am I" – "Apple Store, but I am only 50-50 sure"
(source: studentnewsdaily.com)
10/28/14 @ IEEE MASS 2014
3 / 20
Goal
Focus of today’s indoor localization is on accuracy but not
computational efficiency
Can we ...?
have faster positioning
... that is accurate
Contribution
A method based on spatially hierarchical learning
10/28/14 @ IEEE MASS 2014
4 / 20
Ranging
Ranging is a well-established method
SONAR (= SOund Navigation And Ranging),
RADAR (= RAdio Detection And Ranging) and
LIDAR (= LIght Detection And Ranging).
Distance between Tx and Rx can be estimated by probes of signal
strength, time of arrival, etc.
Location is determined by multi-lateration/angulation, given distances,
or a combination of distances and angles, from a set of references.
10/28/14 @ IEEE MASS 2014
5 / 20
Fingerprinting
Ranging-free (ranging is expensive!)
Fingerprint = a vector of features x = (x1 , x2 , ..., xm ) associated
with a location
should be location-discriminative, easy to obtain
e.g,. RSS from Wi-Fi APs, FM towers, sound, light, earth’s
magnetic, images of surrounding area, etc.
1
Survey: construct a fingerprint map {fingerprint xi , location yi }ni=1
2
Training: learn a prediction function: f (fingerprint x) = location y
Nearest Neighbors (kNN)
Bayesian inference
Support Vector Machines (SVM), Artificial Neural Networks (ANN)
3
Positioning: for each new fingerprint xnew , output f (xnew ).
10/28/14 @ IEEE MASS 2014
6 / 20
Fingerprinting vs. Ranging
Fingerprinting: data-driven
Preferable for its simplicity, wide applicability, and cost, more suitable
for indoor location-based services, especially targeting consumers
Ranging: model-based
Expensive, more suitable for specialized highly-critical applications
This paper is focused on the fingerprinting approach
10/28/14 @ IEEE MASS 2014
7 / 20
Bayesian Method
P(location | fingerprint) =
P(fingerprint | location) × P(location)
P(fingerprint)
Location estimate for fingerprint x is
f (x) = argmax P(y | x)
| {z }
y
Need to know (from training data)
Location distribution: P(location)
Fingerprint distribution: P(fingerprint)
Fingerprint distribution at each location:
P(fingerprint | location)
10/28/14 @ IEEE MASS 2014
8 / 20
Classification Method
1
Area = union of classes, each being a geographic region
Grid Approach: a class = cell of flat grid
2
Location ← fingerprint’s memberships in classes
Support Vector Machines (SVM): de facto for classification
Positioning phase: time complexity = O(#classes) = O(area)
10/28/14 @ IEEE MASS 2014
9 / 20
Hierarchical Classification Method
Hierarchical vs. Grid = Binary Search vs. Exhaustive Linear Search
For each dimension, define classi = i th percentile of the area
Consequently, class1 ⊂ class2 ⊂ ... ⊂ class100
Find smallest classi containing fingerprint ⇒ location = i +
1
2
√
No. classes = O( area)
Positioning phase: time O(log(#classes)) = O(log(area))
10/28/14 @ IEEE MASS 2014
10 / 20
Hierarchical Classes
10/28/14 @ IEEE MASS 2014
11 / 20
Hierarchical Classes
10/28/14 @ IEEE MASS 2014
12 / 20
Error Analysis
Assuming uniform distribution for the user location, the expected
location error along a single dimension (e.g., x-dimension or
y-dimension) is bounded by
E=
(1 + 2) 1 − (1 − )m−1 (1 − )
+ m −
.
2(1 + )
2
2m+1 (1 + )
Here, (2m − 1) classes are defined for this dimension and is the
maximal individual prediction error of these classes.
Location error can be made small by choosing a sufficiently large m
and given this choice of m, having a sufficiently small (which can be
achieved by training on sufficiently many fingerprint samples).
lim E =
→0
1
(1 + 2)
.
, lim E =
2(1 + )
2m+1 m→∞
10/28/14 @ IEEE MASS 2014
13 / 20
Numerical Results
University of Colorado Dataset (courtesy: Kevin Bauer)
Wi-Fi RSSI fingerprints at 179 sample locations, 5 Wi-Fi APs
Training set: 1,576 fingerprints (8.8 fingerprints per location)
Testing set: 77,516 fingerprints.
10/28/14 @ IEEE MASS 2014
14 / 20
Numerical Results: Hierarchical vs. Linear
Colorado Dataset
Colorado Dataset:
4.8
40
4.6
35
Time (sec)
Average Error (m)
4.4
4.2
Grid−SVM
Stripe−SVM
SH−SVM
4
30
Grid−SVM
Stripe−SVM
SH−SVM
25
3.8
20
3.6
3.4
10
20
30
40
50
60
Grid Size
70
80
90
100
15
10
20
30
40
50
60
Grid Size
70
80
90
100
Location error: slightly better
Computation time: 30+% faster
10/28/14 @ IEEE MASS 2014
15 / 20
Numerical Results: Hierarchical vs. kNN
Colorado Dataset: SH−SVM vs. kNN
Colorado Dataset: SH−SVM vs. kNN
4
2000
1800
3.5
1600
3
Time (sec)
Average Error (m)
1400
2.5
2
1200
1000
1.5
800
600
1
400
0.5
0
200
1NN(E)
5NN(E)
1NN(M)
5NN(M)
SH−SVM
Techniques
0
1NN(E)
5NN(E)
1NN(M)
5NN(M)
SH−SVM
Techniques
Location error: slightly better
Computation time: 16-76 times faster
10/28/14 @ IEEE MASS 2014
16 / 20
Numerical Results: Another Dataset
❘ ✁✂
❘
✁☞
❖✄☎✆ ✝✄✞✟☎
❊✆✌✠✞✆✟☎
❖✄☎✆ ✝✄✞✟☎ ✟ ✠✠✡☛ ✠
▼✎✏✌✡✁☎☛✡✞ ❘
✁
❲✍
University of Trento Dataset (courtesy: Mauro Brunato)
Wi-Fi RSSI fingerprints at 257 sample locations, 6 Wi-Fi APs
Training set: 128 fingerprints (1 fingerprints per location)
Testing set: 129 fingerprints.
Location error: slightly better than both kNN and Linear
Computation time: 3x faster than Linear, 1.4x faster than the fastest
kNN and 6x faster than the most accurate kNN
10/28/14 @ IEEE MASS 2014
17 / 20
Demo
http://www.youtube.com/embed/YNPCobmL9sQ
http://www.youtube.com/embed/BA6hUwSmWQ8
10/28/14 @ IEEE MASS 2014
18 / 20
Summary
Indoor localization needs be FAST, not just ACCURATE
Contribution
Location fingerprinting based on classification learning where classes
are regions hierarchically structured
Substantially faster (many times)
Comparable or better localization accuracy
Robust (seemingly) to different floor layouts with obstacles
Future research
What proposed remains a framework. In practice, we need to choose
best hierarchical partitioning for a given floor layout (a hierarchy of
rooms? spaces)
10/28/14 @ IEEE MASS 2014
19 / 20
Acknowledgements
Our work was supported in part by the NSF award CNS-1116430. Any
opinions, findings and conclusions or recommendations expressed in
this material are ours and do not necessarily reflect those of the NSF.
10/28/14 @ IEEE MASS 2014
20 / 20
© Copyright 2024 ExpyDoc
