Scalable Location Performance in IEEE 802.11-17/1371r0 Document

1 / 34

Embed Share

Explore the detailed study on scalable location performance in the IEEE 802.11-17/1371r0 document authored by Erik Lindskog and team from Qualcomm, focusing on simulation procedures, RTT measurements, location estimation, and Newton's method applications.

nikoletah Follow

Uploaded on Apr 03, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

Sept 2017 doc.: IEEE 802.11-17/1371r0 Scalable Location Performance Date: 2017-09-13 Authors: Name Erik Lindskog Affiliations Address Qualcomm Phone email elindsko@qca.qualcomm.com nkakani@qca.qualcomm.com Naveen Kakani Qualcomm alirezar@qca.qualcomm.com Ali Raissinia Qualcomm Submission Slide 1 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 General Simulation Procedure Setup: 6 APs in circle with 50 m radius 1 client AP2 (x2,y2) 2 AP3 AP1 Unknowns: AP clock offsets , , (w.r.t. client clock, i.e. =0) Client coordinates x0,y0 3 1 Client (x0,y0) AP4 AP6 0= 0 Modeling of imperfections: For simplicity Clock offsets i=0 but unknown No clock drifts modeled 3 ns stdev Gaussian clock gitter 1 m stdev Gaussian multipath error All errors independent 6 4 AP5 5 Submission Slide 2 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 RTT Round Trip Time Location Submission Slide 3 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 Propagation paths and time stamps Illustrating timing diagram showing double sided feedback of time-stamps: Client AP t1 UL MU NDP t2 DL NDP t3 t4 AP to STA feedback t2, t3 ToF=(t2-t1+t4-t3)/2 Submission Slide 4 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 RTT Simulation Procedure Measurements: One RTT measurement between each AP and the client AP2 (x2,y2) AP3 AP1 t1 t4 t2 Location estimation: E.g. iteration with Newton s method to solve for least squares solution to non-linear system of equations for measured ToF as a function of client position. Client (x0,y0) t3 AP4 AP6 AP5 Submission Slide 5 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 RTT Location Estimation Calculations Rij In two dimensions with 3 APs: AP1 AP2 Unknowns: Client coordinates x0,y0 2 unknowns t1 ToF1=(t2-t1+t4-t3)/2 t4 Client (x0,y0) t2 R1(x0,y0) Equations: ToF equations 3 equations t3 ToF1 = R1/c ToF2 = R2/c ToF3 = R3/c Solve for location, e.g. with Newton iterations described in following slides. (x3,y3) AP3 Submission Slide 6 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 Newton s method for solving non-linear equation (x ) f Solve equation: F = *x ( ) f F (x ) f x x1 x3x2 etc. = x x* Submission Slide 7 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 Solving of non-linear system of equations F = *x ( ) f - solve for x* Non linear system of equations: Use Newton s method for multiple variables: f = + = * ( ) i f x ( ) ( ) ( ) F f x f x f x x where Linearization: k k x j Over-determined non-linear system of equation to solve for x: + ( ) ( ) F f x f x x k k Least squares solution for iterative step: ( ) ) k 1 = = T T ( ) ( ) ( ) ( x x x f x f x f x F f x + 1 k k k k k Iterate according to: ( ) ) k 1 = + T T ( ) ( ) ( ) ( x x f x f x f x F f x + 1 k k k k k Submission 8 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 Our derivatives To simplify the equations, measure time in light seconds - the distance light travels in one second. = = ( , ) ToF f x y R 0 0 i i i ( ) ( )2 2 = + R x x y y 0 0 i i i ( , ) ( , ) R x y R x y = 0 0 0 0 ( , ) i i f x y , 0 0 x y i x y 0 0 x x y y = 0 0 ( , ) i i f x y , 0 0 x y i ( , ) ( , ) R x y R x y 0 0 0 0 i i Submission Slide 9 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 Iterative solution for client position (x0,y0) Step calculation. LS solution to: x x y y 0 1 0 1 ( , ) ( , ) R x y R x y TOF R 1 x 0 0 1 y 0 0 1 1 x x x x y 0 = 0 ( 2 0 ( 2 TOF R 2 2 y , ) , ) R y R y 0 2 x 0 0 2 y 0 0 TOF R x x y 3 3 0 ( 3 0 ( 3 y , ) , ) R x y R 3 0 0 02 0 0 Note: Time in units of light seconds Iterations: + ( ) 1 ( ) x k x k x 0 0 0 = + + ( ) 1 ( ) y k y k y 0 0 0 Submission 10 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 DToA Differential Time-of-Arrival Location See [1,2 and 3] Submission Slide 11 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 Propagation paths and time stamps Illustrating timing diagram showing double sided feedback of time-stamps: Client AP2 AP1 t1 UL MU NDP t5 t2 DL NDP t3 t4 t2, t3 AP to STA feedback t6 t1, t4 STA to AP feedback Submission Slide 12 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 Double-Sided Differential Distance Calculation The client STA listens to the exchanges between the AP1 and AP2 and records the time t5 when it receives the UL MU NDP from AP2 and the time t6 when it receives the DL NDP from AP1. The client also listens to the relayed t2 and t3 from AP1 and the relayed t1 and t4 in the feedback from AP2. The differential distance between the client STA and AP1 vs. AP2 can now be calculated as follows: D_01 = [t6 t5 (t3 t2 + T_12)] * c Using T_01 = [(t4 t1) (t3 t2)]/2 We get D_01 = [t6 t5 (t3 t2 + 0.5*t4 0.5*t1 0.5*t3 + 0.5*t2)]*c Or finally: D_12 = [t6 t5 0.5*t3 + 0.5*t2 0.5*t4 + 0.5*t1]*c Note that the above expression for the differential distance D_12 does not depend on the ToF, T_12, between AP1 and AP2. Thus this method of calculating D_12 is insensitive to LOS obstructions between AP1 and AP2. Submission Slide 13 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 DToA Simulation Procedure Measurements: One RTT measurement between each pair of APs, repeated 6 times1 (I.e., each AP takes on the role of AP1 in the picture once) AP2 (x2,y2) AP1 AP3 Client (x0,y0) Location estimation: E.g. iteration with Newton s method to solve for least squares solution to non-linear system of equations for measured DToA as a function of client position. AP4 AP6 AP5 1)Note: The DToA, and the later described Joint Clock Offsets and Client Location Estimation method, both have 5 times more measurements than the RTT method and as such cannot be compared directly. It can however be justified to have more measurements for the DToA and Joint Clock Offsets and Client Location Estimation methods as the number of transmissions do not increase when we are considering location for multiple clients. Submission Slide 14 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 DToA Location Estimation Calculations Rij In two dimensions with 3 APs: AP1 AP2 Unknowns: Client coordinates x0,y0 2 unknowns t1 DTOF12 = t6 t5 0.5*t3 + 0.5*t2 0.5*t4 + 0.5*t1 t2 t4 t3 Client (x0,y0) t5 t6 R02(x0,y0) Equations: Differential ToF equations DToA12 = (R01-R02)/c DToA13 = (R01-R03)/c DToA23 = (R02-R03)/c 3 equations Solve for location, e.g. with Newton iterations described in following slides. (x3,y3) AP3 Submission Slide 15 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 Solving of non-linear system of equations F = *x ( ) f - solve for x* Non linear system of equations: Use Newton s method for multiple variables: f = + = * ( ) i f x ( ) ( ) ( ) F f x f x f x x where Linearization: k k x j Over-determined non-linear system of equation to solve for x: + ( ) ( ) F f x f x x k k Least squares solution for iterative step: ( ) ) k 1 = = T T ( ) ( ) ( ) ( x x x f x f x f x F f x + 1 k k k k k Iterate according to: ( ) ) k 1 = + T T ( ) ( ) ( ) ( x x f x f x f x F f x + 1 k k k k k Submission 16 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 Our derivatives To simplify the equations, measure time in light seconds - the distance light travels in one second. = = ( , ) DToA f x y R R 0 0 ij ij i j ( ) ( )2 ( ) ( )2 2 2 = + = + R x x y y R x x y y 0 0 j j j 0 0 i i i ( ) ( ) x y ( , ) ( , ) ( , ) ( , ) R x y R x y R x y R x y 0 0 0 0 0 0 0 0 i j i j = ( , ) f x y , 0 0 x y ij 0 0 x x x x y y x x y y 0 0 j j = 0 0 ( , ) i i f x y , 0 0 x y ij ( , ) ( , ) ( , ) ( , ) R x y R y R x y R y 0 0 0 0 0 0 0 0 i j i j Submission Slide 17 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 Iterative solution for client position (x0,y0) Step calculation. LS solution to: x x x x x x x x y y y y 0 ( 1 y 0 ( 2 y 0 ( 1 y 0 ( 2 y ( ( ( ) ) ) , ) , x ) , ) , y ) R R R R DTOA R R 01 x 0 0 02 x 0 0 01 y 0 0 02 y 0 0 12 01 02 x x x x x x y 0 = 0 ( 1 y 0 ( 3 y 0 ( 1 y 0 ( 3 y DTOA R R 13 01 03 y , x ) , x ) , y ) , x ) R R R R 0 01 x 0 0 03 x 0 0 01 y 0 0 03 y 0 0 DTOA R R x x x x 23 02 03 0 ( 2 y 0 ( 3 y 0 ( 2 y 0 ( 3 y , ) , ) , ) , ) R R R R 02 0 0 03 0 0 02 0 0 03 0 0 Note: Time in units of light seconds Iterations: + ( ) 1 ( ) x k x k x 0 0 0 = + + ( ) 1 ( ) y k y k y 0 0 0 Submission 18 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 Joint Clock Offsets and Client Location Estimation See [4 and 5] Submission Slide 19 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 Joint Clock Offsets and Client Location and Estimation Calculations We are here using the CToA method [4,5] only to do joint AP clock offset and client position estimation. We are not modeling nor tracking any drift in the clocks. We are not using the Kalman filter approach for the calculations described in [4 and 5] here. Submission Slide 20 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 Joint Clock Offsets and Client Location Estimation Simulation Procedure Measurements: One RTT measurement 1 between each pair of APs, repeated 6 times (I.e., each AP takes on the role of AP1 in the picture once) AP2 (x2,y2) AP1 AP3 Location estimation: E.g. iteration with Newton s method to solve for least squares solution to non- linear system of equations for measured Joint Clock Offsets and Client Location calculations as a function of client position. Client (x0,y0) AP4 AP6 AP5 1)Note: The DToA, and the Joint Clock Offsets and Client Location Estimation method, both have 5 times more measurements than the RTT method and as such cannot be compared directly. It can however be justified to have more measurements for the DToA and Joint Clock Offset and Client Location Estimation methods as the number of transmissions do not increase when we are considering location for multiple clients. Submission Slide 21 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 Joint Clock Offsets and Client Location Estimation In two dimensions with 3 APs: Rij Unknowns: AP clock offsets and (w.r.t. client clock, i.e. =0) Client coordinates x,y 5 unknowns AP1 TOD1 AP2 TOA2 1 2 Client (x0,y0) R02(x0,y0) Equations: AP to AP propagations: TOAi i = TODj - j + Rij/c AP to client propagations: TOA0 = TODj - j + R0j(x,y)/c 9 equations TOA0 0= 0 Solve for location, e.g. with Newton iterations described in following slides. 3 (x3,y3) AP3 Submission Slide 22 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 Solving of non-linear system of equations F = *x ( ) f - solve for x* Non linear system of equations: Use Newton s method for multiple variables: f = + = * ( ) i f x ( ) ( ) ( ) F f x f x f x x where Linearization: k k x j Over-determined non-linear system of equation to solve for x: + ( ) ( ) F f x f x x k k Least squares solution for iterative step: ( ) ) k 1 = = T T ( ) ( ) ( ) ( x x x f x f x f x F f x + 1 k k k k k Iterate according to: ( ) ) k 1 = + T T ( ) ( ) ( ) ( x x f x f x f x F f x + 1 k k k k k Submission 23 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 Our derivatives To simplify the equations, measure time in light seconds - the distance light travels in one second. = , , , = + ( , ) TOA TOD f x y R 0 0 1 2 3 i j ij ij i j ( ) ( )2 2 = + R x x y y ij j i j i ( , ) ( , ) R x y R x y x x y y 1 0 0 1 0 0 0 1 0 1 ( , ) ( , ) x y R x y R x y ( , , , , ) 10 f x y v v v 0 0 1 x 0 0 1 y 0 0 0 0 1 2 3 x x ( , ) ( , ) R x y R x y x y = = 2 0 0 2 0 0 0 2 0 2 ( , , , , ) f x y v v v , 20 0 0 1 2 3 x y ( , ) ( , ) x y R y R y 0 0 0 0 2 x 0 0 2 y 0 0 ( , , , , ) f x y v v v ( , ) ( , ) R x y R x y x y 20 0 0 1 2 3 3 0 0 3 0 0 0 3 0 3 ( , ) ( , ) x y R x y R x y 0 0 3 0 0 3 0 0 = depending 1 ( , , , , ) on entry f x y v v v , , 0 0 1 2 3 v v v 1 2 3 Submission Slide 24 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 Iterative solution for client position (x0,y0) Step calculation. LS solution to: x x x x y y 0 ( 1 y 0 ( 1 y 1 0 0 ( ( ( ) ) ) , x ) , y ) R R TOA TOD R 01 x 0 0 01 y 0 0 0 1 01 1 x x TOA TOD R 0 ( 2 y 0 ( 2 y 0 1 0 0 2 02 2 , x ) , y ) R R R 02 x 0 0 02 y 0 0 TOA TOD R x x x 0 3 03 3 0 ( ( ( ( ( ( ) ) ) ) ) ) 0 ( 3 y 0 ( 3 y 0 0 1 + TOA TOD y , ) , ) R R 1 2 12 1 2 0 03 0 0 03 0 0 = + TOA TOD R 0 0 0 1 1 0 1 3 13 1 3 1 + TOA TOD R 0 0 0 1 1 2 1 21 2 1 2 + TOA TOD R 0 0 0 1 1 2 3 23 2 3 3 + TOA TOD R 1 0 0 1 1 3 1 31 3 1 + TOA TOD R 0 0 0 1 0 3 2 23 3 2 0 0 1 1 Note: Time in units of light seconds Iterations: + ( ) 1 ( ) v k v k v 1 1 1 + ( ) 1 ( ) x k x k x + = + 0 0 0 = + ( ) 1 ( ) v k v k v 2 2 2 + ( ) 1 ( ) y k y k y + 0 0 0 ( ) 1 ( ) v k v k v 3 3 3 Submission 25 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 Some RTT, DToA and Joint Clock Offsets and Client Location Estimation Comparisons Submission Slide 26 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 RTT, DToA and Joint Clock Offsets and Client Location Estimation Client in center of circle DToA and Joint Clock Offsets and Client Location estimated positions offset for display purposes Submission Slide 27 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 RTT, DToA and Joint Clock Offsets and Client Location Estimation Client in center of circle Submission Slide 28 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 RTT, DToA and Joint Clock Offsets and Client Location Estimation Client on circle DToA and Joint Clock Offsets and Client Location estimated positions offset for display purposes Submission Slide 29 Erik Lindskog, Qualcomm, et al.

Sept 2017 RTT, DToA and Joint Clock Offsets and Client Location Estimation doc.: IEEE 802.11-17/1371r0 Client on circle Submission Slide 30 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 RTT, DToA and Joint Clock Offsets and Client Location Estimation Client outside circle DToA and Joint Clock Offsets and Client Location estimated positions offset for display purposes Submission Slide 31 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 RTT, DToA and Joint Clock Offsets and Client Location Estimation Client outside circle Submission Slide 32 Erik Lindskog, Qualcomm, et al.

Sept 2017 doc.: IEEE 802.11-17/1371r0 References [1] Client Positioning using Timing Measurements between Access Points , Erik Lindskog, Naveen Kakani, Raja Banerjea, Jim Lansford and Jon Rosdahl, IEEE 802.11-13/0072r1. [2] A Low Overhead Receive Only Wi-Fi Based Location Mechanism , Erik Lindskog, Hong Wan, Raja Banerjea, Naveen Kakani and Dave Huntingford, Proceedings of the 27th International Technical Meeting of The Satellite Division of the Institute of Navigation (ION GNSS+ 2014), Tampa, Florida, September 2014, pp. 1661-1668. [3] Passive Location , Erik Lindskog, Naveen Kakani and Ali Raissinia, IEEE 802.11- 17/0417r0. [4] High-Accuracy Indoor Geolocation using Collaborative Time of Arrival (CToA) - Whitepaper , Leor Banin, Ofer Bar Shalom, Nir Dvorecki, Yuval Amizur, IEEE 802.11- 17/1387r0. [5] Collaborative Time of Arrival (CToA) , Ofer Bar Shalom, Yuval Amizur, Leor Bani, IEEE 802.11-17/1308r0. Submission Slide 33 Erik Lindskog, Qualcomm, et al.