Transcript Localization Algorithm: MMC-KNN

Indoor Localization with a Crowdsourcing
based Fingerprints Collecting
Copyright ©2013 by SJTU, IWCT.
Dongchuan Road #800, Minhang,
Shanghai,200240
All rights reserved.
System Architecture
Crowdsourced Fingerprint Collection
Crowdsourced Process
User A
Device A
User B
Device B
Cloud Computing Platform - CloudFoundry
Kernel Density Estimate
Extract Fingerprint
Clustering
Sufficient Statistics
Optimum Reception Theory
Affinity Propagation
FingerPrint Database
for Diverse Devices
User C
Device C
Location Process Using Fingerprint Database
Cloud Computing Platform - CloudFoundry
User Upload Rss Value
Use Any Device
User A
Device A
AP Detection
Remove Aps below
threshold
Cluster Matching
Location Algorithm
Affinity Propagation
K Nearest Neighbor (KNN)
MMC-KNN
Get Estimate Location
Information
Grid Window Filter
Restrict Estimate Results into
Sub Regions
Copyright ©2013 by SJTU, IWCT.
Dongchuan Road #800, Minhang,
Shanghai,200240
All rights reserved.
Key Technology
• Crowdsourcing based fingerprint extraction methods
• Localization Algorithms based on clustering theory
Copyright ©2013 by SJTU, IWCT.
Dongchuan Road #800, Minhang,
Shanghai,200240
All rights reserved.
Fingerprints Extraction
• In crowdsourcing model, multiple users will upload
fingerprints via diverse devices
• Our method extract fingerprint value based on RSS
probability estimation, choose the optimum value
from upload samples
• Kernel density estimation eliminates device diversity
than Gaussian probability estimation
Copyright ©2013 by SJTU, IWCT.
Dongchuan Road #800, Minhang,
Shanghai,200240
All rights reserved.
Fingerprints Extraction
• Comparison of Gaussian and Kernel density
estimation:
Copyright ©2013 by SJTU, IWCT.
Dongchuan Road #800, Minhang,
Shanghai,200240
All rights reserved.
Fingerprints Extraction
• Based on kernel density estimation, choose optimum
value from multiple upload RSS samples by multiple
users by diverse devices.
Copyright ©2013 by SJTU, IWCT.
Dongchuan Road #800, Minhang,
Shanghai,200240
All rights reserved.
Localization Algorithm: MMC-KNN
• MMC-KNN algorithm: find M most matched
clusters, then apply KNN principle to choose out
matched fingerprint
• Use affinity propagation to process clustering:
Copyright ©2013 by SJTU, IWCT.
Dongchuan Road #800, Minhang,
Shanghai,200240
All rights reserved.
Localization Algorithm: MMC-KNN
• How to find out the M most matched cluster?
– Consider uploaded observation’s connections and
similarities with all exemplars
– Apply affinity propagation again and get
responsibility vector:
– choose the M most matched cluster by sort this
responsibility vector
Copyright ©2013 by SJTU, IWCT.
Dongchuan Road #800, Minhang,
Shanghai,200240
All rights reserved.
Localization Algorithm: MMC-KNN
• Assign a weight factor to each cluster’s fingerprints
ec
w( f ) 
D ( f , o)
• Apply a grid window filter to filter a region which
has the maximum weight, with the purpose to restrict
KNN applied to a bursting region
Copyright ©2013 by SJTU, IWCT.
Dongchuan Road #800, Minhang,
Shanghai,200240
All rights reserved.
Real-time experimental testbed
• Average error distance with different matched cluster
number and grid window size for Nexus-S
Copyright ©2013 by SJTU, IWCT.
Dongchuan Road #800, Minhang,
Shanghai,200240
All rights reserved.
Real-time experimental testbed
• 220 observation’s error distance statistic with best
performance parameters for Nexus-S
Copyright ©2013 by SJTU, IWCT.
Dongchuan Road #800, Minhang,
Shanghai,200240
All rights reserved.
Real-time experimental testbed
• CDF of location error distance for different
algorithms
Copyright ©2013 by SJTU, IWCT.
Dongchuan Road #800, Minhang,
Shanghai,200240
All rights reserved.
Real-time experimental testbed
• Comparison of different types devices’ location
performance under diverse fingerprint databases
Copyright ©2013 by SJTU, IWCT.
Dongchuan Road #800, Minhang,
Shanghai,200240
All rights reserved.