Report

Localization of Mobile Users Using Trajectory Matching ACM MELT’08 HyungJune Lee, Martin Wicke, Branislav Kusy, and Leonidas Guibas Stanford University Motivation • Location is an important and useful resource – Push local information to nearby mobile users • Restaurant, Café, Shopping center on sale, … – Building automation, etc. • GPS not available – Indoor, mobile environment • ~1m-accuracy – Usable for location-based service 2 Motivation • RSSI-based localization • Indoor setting RSSI graph – Due to reflection, refraction, and multi-path fading, specific model does not work – More severe link variation caused by mobility • Range-free methods – Connectivity & Triangulation: DVhop[Niculescu03] , APIT[He05] – RSSI pattern matching: RADAR[Bhal00], MoteTrack[Lorincz07] – Bayesian inference & Hidden Markov Model: [Haeberlen04], [Ladd04], LOCADIO[Krumm04] • Idea: Use historical RSSI measurements 3 Outline • Trace Space • Localization algorithm – Training Phase with RBF construction – Localization Phase • Evaluation • Conclusion and Future work 4 Trace Space • Traces of RSSI readings form a trace space k, N . • Each trace T corresponds to a location T= : k, N → L= x y 3 (x1, y1) 2 1 R2 (x2, y2) 4 • Learn to match a trace to a position i.e., L(∙): k, N → R2 5 5 Training Phase with RBF Fitting • Training input r r RSSI vectors T in trace space k, N • Training output p L(r) p [ px py ]T in R2 space • Solve linear systems of training data by least-squares • Obtain L(∙) function NC Lx (r ) w j ( r c j ) ar b j 1 where c j is a RBF cent er w j , a, b ( j 1,, NC ) are solvedby least - squares 6 Localization Phase • Localization phase – Calculate the L (∙) given current trace T in test sets • Sparse interpolation in trace space – Handles noisy input data gracefully – Extrapolates to uncharted regions Location X LX (T) LY (T) Location Y Illustration from “Scattered Data Interpolation with Multilevel B-Splines” [Lee97] 7 Evaluation • MicaZ motes 8 – CC2420 radio chip • 10 stationary nodes 1 • 1 mobile node • 14 waypoints location 9 7 6 10 5 4 2 1 3 • Ground-truth: (r(t), p(t)) – Training RSSI vector r(t) – Training position p(t) • linear interpolation between waypoints RSSI graph 8 Evaluation • Training phase : (a), (b), (c), (d), (e) • Testing phase : (f), (g), (h), (i) • 5 runs for each path • Error measures – Position error – Path error 9 Influence of Historical data 2.4 m 1.28 m History size k 10 Other Link Quality Measures 2.02 m 1.74 m 1.28 m 11 Conclusion • Historical RSSI values significantly increase the fidelity of localization (mean position error < 1.3 m) • Our algorithm also works well with any link quality measurements, e.g., LQI or PRR, which allows flexibility of the algorithm 12 Future work • Prediction of future location • Scalability • Dynamic time warping for different speed 13 Questions? HyungJune Lee [email protected] 14 Radial Basis Function Fitting (Backup) • Multi-quadratic function (d ) 1 d2 2 NC with 1 L(r ) w j ( r c j ) ar b j 1 where c j is a RBF center • By least-squares 1,1 N ,1 S 1 c 1 1, N N C S , NC 1 cNC r (t1 )T r (t N S )T 0 0 1 w 1 a 0 b 0 p(t1 ) p(t N S ) 0 where i , j ( ri c j ) , w w1 , , wN C T , N S NC 15 Influence of # of RBF centers Nc (Backup) # of RBF centers Nc 16 Influence of Average Window Size b (Backup) Burst window size b 17