Report

LOCATING IN FINGERPRINT SPACE: WIRELESS INDOOR LOCALIZATION WITH LITTLE HUMAN INTERVENTION Zheng Yang, Chenshu Wu, and Yunhao Liu MobiCom 2012 - Sowhat 2012.08.20 OUTLINE Introduction System Design Evaluation Discussion Conclusion OUTLINE Introduction System Design Evaluation Discussion Conclusion MOTIVATION RSSI fingerprinting-based localization Site survey Time-consuming Labor-intensive Vulnerable to environmental dynamics Inevitable OBJECTIVE Wireless Indoor Localization Approach RSSI Floor Plan User Movement OUTLINE Introduction System Design Evaluation Discussion Conclusion LIFS, SYSTEM ARCHITECTURE Geographical dist. ≠ Walking dist. RSSI + Distance MULTIDIMENSIONAL SCALING (MDS) Information visualization for exploring similarities/dissimilarities in data STRESS-FREE FLOOR PLAN Geographical distance ≠ Walking distance, Ground-truth floor plan – conflict with measured distance Sample grids in a floor plan (grid length l = 2m) Distance matrix D = [dij], dij = walking distance between point i and j MDS Stress-free floor plan – 2D & 3D FINGERPRINT SPACE – FINGERPRINT & DISTANCE MEASUREMENT Fingerprints and distance collection Record while walking Footsteps every consecutive steps by accelerometer Set of fingerprints, F = {fi, i = 1~n} Distance(footsteps) matrix, D’=[d’ij] Pre-processing Merge similar fingerprints (δij<ε) Accelerometer reading Twice integration Distance: Noice Local variance threshold method Step count Stride lengths vary? MDS tolerate measurement errors FINGERPRINT SPACE – FINGERPRINT SPACE CONSTRUCTION Adequate fingerprints & distance 1. 2. 10x sample locations in stress-free floor plan First several days for training d’ij unavailable d’ij = d’ik + d’kj Shortest path update D’ all-pairs of fingerprints Floyd-Warshall algorithm MDS Fingerprint space 2D & 3D MAPPING – CORRIDOR & ROOM RECOGNITION Corridor recognition (Fc) Higher prob. on a randomly chosen shortest path Minimum spanning tree Betweenness Classify fingerprints into Watershed 1. 2. the corridor or rooms Size(corridor) / Size(all) Large gap of betweenness values Room recognition (FRi) k-means algorithm (k = number of rooms) MAPPING – REFERENCE POINT Fingerprints collected near “doors” PD = {p1, p2, …, pk}, stress-free floor plan FD 1. Map near-door fingerprints , fingerprint space to real locations (FD → PD) 2. Map roomsNear-door to rooms fingerprints, FD, labeled with real locations distance matrix D and D’ cosine similarity l = (lp1, lp2, …, lp k-1) l’ = (lf1, l’f2, …, l’f k-1) MAPPING – SPACE TRANSFORMATION Floor-level transformation Stress-free floor plan ≠ Fingerprint space ∵ translation, rotation, reflection Transform matrix, xi = coordinate of fi ∈ FD yi = coordinate of pi ∈ PD For fingerprint with coordinate x real location = sample location closest to Ax + B Room-level transformation Room by room Doors and room corners as reference point Transformation matrix OUTLINE Introduction System Design Evaluation Discussion Conclusion HARDWARE AND ENVIRONMENT 2 Google Nexus S phones Typical office building covering 1600m2 16 rooms, 5 large – 142m2, 7 small, 4 inaccessible 26 Aps, 15 are with known location 2m x 2m grids, 292 sample locations EXPERIMENT DESIGN 5 hours with 4 volunteers Fingerprints recording – every 4~5 steps (2~3m) Accelerometer – work in different frequency based on detecting movement 600 user traces, with 16498 fingerprints Corridor, >500 paths Small rooms, >5 paths Large rooms, >10 paths Half of data used for training, half …………………... in operating phase THRESHOLD VALUE OF FINGERPRINT DISSIMILARITY STEP COUNT 5 ~ 200 footsteps Error rate = 2% in number of detected steps Accumulative error of long path Unobvious performance drop ∵ only use inter-fingerprint step counts FINGERPRINT SPACE 795 fingerprints when ε = 30 CORRIDOR RECOGNITION Refining Perform MST iteratively Sift low betweenness Until MST forms a single line ROOM RECOGNITION REFERENCE POINT MAPPING POINT MAPPING • 96 percentile < 4m • Average mapping error = 1.33m LOCALIZATION ERROR Emulate 8249 queries using real data on LiFS Location error Average, LiFS = 5.88m RADAR = 3.42m Percentile of LiFS 80 < 9m / 60 < 6m Caused by symmetric structure Fairly reasonable! Room error = 10.91% OUTLINE Introduction System Design Evaluation Discussion Conclusion DISCUSSION Global reference point Last reported GPS location Locations of APs Similar surrounding sound signature … Could be added in LiFS for more robust mapping Key for symmetric floor plans / multi-floor fuildings Large open environment OUTLINE Introduction System Design Evaluation Discussion Conclusion CONCLUSION LiFS Spatial relation of RSSI fingerprints + Floor plan Low human cost Comments Clear architecture Not specific descriptions in evaluation THANKS FOR LISTENING ~