TRANSACTIONS ON MOBILE COMPUTING,VOL.17,NO.10,OCTOBER 2018 100 -Normal Normal W/O filter ■Office -WO SFO removal Walk 亚收 2.5 Distance(m) Error(m) Users Figure 13.Coarse estimation error for different Figure 14.Coarse estimation error with and Figure 15.Coarse estimation error for different distances without denoising algorithm scenarios that the coarse estimation algorithm is robust under different Algorithm 2:Estimating Initial Position scenarios.The average errors of"Normal","Office",and"Walk" Input:Vertical movement path length changes of two are 0.27 m.0.32 m,and 0.34 m,respectively.For most users the receivers:Adi,Ad?,horizontal movement path length estimation accuracies are just slightly lower in the "Office"and changes of two receivers:Ad,Ad2.coarse initial "Walk"scenario.However,if the walking volunteer is very close position(re,ye） to the user,the estimation performance would degrade severely. Output:Estimated position (ro,yo)in two-dimensional space 1 for k 1 to K do The coarse estimation error is mainly due to two reasons: 2 Determine the candidate square region:C= Firstly,the trajectories of CSI I/Q components caused by the hand {(x,)(k-1)*L<z:-xe≤k*L), movement are not perfect circles.When the trajectory deviates (k-1)*L<l-e|≤k*L from circles,the phase differences of the dynamic vectors no /*Vertical movement calculation*/ longer egual to that of the tangent vectors as in Eq.7 (i.e. Calculate the tracking trajectory (,y)for two receivers △arg(Htg(t)月≠△arg(Hhd(t)).Secondly,there are still based on the candidate initial position (x,y)E C and some remaining noises that make the phase measurements inac- path change△d,△d: /*Horizontal movement calculation*/ curate.As shown in Figure 12,the large initial position estimation error may lead to deviated trace.Therefore,we need to further Calculate the tracking trajectory (for two receivers refine the initial position estimation. based on the initial position (rf,y)EC and path change △d,△d: Find N candidate positions (x,y)which have the top N 4.3 Fine Initial Position Estimation smallest deviations (of X-axis; After estimating the initial position of hand at a coarse resolution, Find M candidate positions (which have the top we select a small candidate region,e.g.,less than 0.5 m around the M smallest deviations (of Y-axis; coarse position estimation as the candidate set for refinement.In Calculate M x N distance matrix zxN,where this section,we focus on refining the resolution using a heuristic z4,=√/(2-)2+（坡-）2 algorithm. Find the smallest element in matrixMxN; As we will see,the trajectory of hand in 2D space is not only determined by the path length change of the movement but also <thz and<thy and ziminjmin th:then by its initial position.The incorrect initial position of hand will (eo,0）←（住mntn2,些nau2 severely affect the tracking result.As shown in Figure 12,a user 2 2 break; pushes his hand from(o,y0)along the X-axis and the movement distance is Lo.For the same path length change,if the initial 14 return(ro,yo)÷ position is(o,).the movement distance would be changed to Lo.and the trajectory direction would have deviation of 0. the initial phase in Eq.(1).Additionally,the bandwidth B We have evaluated several methods to refine the initial pos- of signals needs to be large enough such that the resolution of ition in 2D space.For example,mTrack [29]based on 60 GHz absolute path length (i.e.,c/B)is accurate.Since the bandwidth technology uses a discrete beam scanning mechanism to pinpoint of 802.11g WiFi Orthogonal Frequency Division Multiplexing the object's initial localization.They use two RX antennas of (OFDM)signal is only 20 MHz,the resolution of using IDFT beamwidth 4.5 to steer the beam.The intersection of two receiv- is 20x-15 m.It is obviously not suitable for our case. 3×108 ing beams is used to estimate the initial position.However,this method is dependent on the beamwidth of the directional antenna. We refine the initial position of hand by performing preamble With the directional antenna,the phase of a signal might not be gestures before the tracking.Our algorithm is inspired by the fact significantly affected by the movement outside the transmitter's that the trajectory would be different for various candidate initial beam,which incurs degradations of tracking accuracy.Another positions with the same path length change.First,the user is asked ultrasonic work,LLAP,uses Inverse Discrete Fourier Transform to to push the hand along the X-axis and Y-axis,respectively.Then, process CFR signals for all subcarriers to get the objects's absolute we use the result of these two preamble gestures as the fingerprint position.However,the calibration of the algorithm requires the of different initial positions.At last,we find the least deviation exact distance between the reflector and receiver to compensate position to estimate the optimal initial position.TRANSACTIONS ON MOBILE COMPUTING, VOL. 17, NO. 10, OCTOBER 2018 7 1 1.5 2 2.5 3 3.5 Distance(m) 0 0.2 0.4 0.6 0.8 1 1.2 Error(m) Figure 13. Coarse estimation error for different distances 0 2 4 6 8 10 12 Error(m) 0 0.2 0.4 0.6 0.8 1 CDF Normal W/O filter W/O SFO removal Figure 14. Coarse estimation error with and without denoising algorithm 12345 Users 0 20 40 60 80 100 Error(cm) Normal Office Walk Figure 15. Coarse estimation error for different scenarios that the coarse estimation algorithm is robust under different scenarios. The average errors of “Normal”, “Office”, and “Walk” are 0.27 m, 0.32 m, and 0.34 m, respectively. For most users the estimation accuracies are just slightly lower in the “Office” and “Walk” scenario. However, if the walking volunteer is very close to the user, the estimation performance would degrade severely. The coarse estimation error is mainly due to two reasons: Firstly, the trajectories of CSI I/Q components caused by the hand movement are not perfect circles. When the trajectory deviates from circles, the phase differences of the dynamic vectors no longer equal to that of the tangent vectors as in Eq. 7 (i.e. ∆arg( −→Htg(t))2 1 6= ∆arg( −→Hhd(t))2 1 ). Secondly, there are still some remaining noises that make the phase measurements inac￾curate. As shown in Figure 12, the large initial position estimation error may lead to deviated trace. Therefore, we need to further refine the initial position estimation. 4.3 Fine Initial Position Estimation After estimating the initial position of hand at a coarse resolution, we select a small candidate region, e.g., less than 0.5 m around the coarse position estimation as the candidate set for refinement. In this section, we focus on refining the resolution using a heuristic algorithm. As we will see, the trajectory of hand in 2D space is not only determined by the path length change of the movement but also by its initial position. The incorrect initial position of hand will severely affect the tracking result. As shown in Figure 12, a user pushes his hand from (x0, y0) along the X-axis and the movement distance is L0. For the same path length change, if the initial position is (x 0 0 , y0 0 ), the movement distance would be changed to L 0 0 , and the trajectory direction would have deviation of θ. We have evaluated several methods to refine the initial pos￾ition in 2D space. For example, mTrack [29] based on 60 GHz technology uses a discrete beam scanning mechanism to pinpoint the object’s initial localization. They use two RX antennas of beamwidth 4.5 ◦ to steer the beam. The intersection of two receiv￾ing beams is used to estimate the initial position. However, this method is dependent on the beamwidth of the directional antenna. With the directional antenna, the phase of a signal might not be significantly affected by the movement outside the transmitter’s beam, which incurs degradations of tracking accuracy. Another ultrasonic work, LLAP, uses Inverse Discrete Fourier Transform to process CFR signals for all subcarriers to get the objects’s absolute position. However, the calibration of the algorithm requires the exact distance between the reflector and receiver to compensate Algorithm 2: Estimating Initial Position Input: Vertical movement path length changes of two receivers: ∆d v 1, ∆d v 2, horizontal movement path length changes of two receivers: ∆d h 1 , ∆d h 2 , coarse initial position (xe, ye) Output: Estimated position (x0, y0) in two-dimensional space 1 for k = 1 to K do 2 Determine the candidate square region: C = {(xi, yi)|((k − 1) ∗ L < |xi − xe| ≤ k ∗ L), (k − 1) ∗ L < |yi − ye| ≤ k ∗ L } 3 /*Vertical movement calculation*/ 4 Calculate the tracking trajectory (xcv i , ycv i ) for two receivers based on the candidate initial position (x v i , yv i ) ∈ C and path change ∆d v 1, ∆d v 2; 5 /*Horizontal movement calculation*/ 6 Calculate the tracking trajectory (xch i , ych i ) for two receivers based on the initial position (x h i , yh i ) ∈ C and path change ∆d h 1 , ∆d h 2 ; 7 Find N candidate positions (x v i , yv i ) which have the top N smallest deviations (|xcv i − x v i |) of X-axis; 8 Find M candidate positions (x h i , yh i ) which have the top M smallest deviations (|ych i − y h i |) of Y-axis; 9 Calculate M × N distance matrix zM×N , where zi,j = q (x h i − x v j ) 2 + (y h i − y v j ) 2; 10 Find the smallest element zimin,jmin in matrix zM×N ; 11 if |x\v jmin − x v jmin | < thx and |y\h imin − y h imin | < thy and zimin,jmin < thz then 12 (x0, y0) ← ( (x h imin +x v jmin ) 2 , (y h imin +y v jmin ) 2 ); 13 break; 14 return (x0, y0) ; the initial phase φi in Eq. (1). Additionally, the bandwidth B of signals needs to be large enough such that the resolution of absolute path length (i.e., c/B) is accurate. Since the bandwidth of 802.11g WiFi Orthogonal Frequency Division Multiplexing (OFDM) signal is only 20 MHz, the resolution of using IDFT is c B = 3×108 20×106 = 15 m. It is obviously not suitable for our case. We refine the initial position of hand by performing preamble gestures before the tracking. Our algorithm is inspired by the fact that the trajectory would be different for various candidate initial positions with the same path length change. First, the user is asked to push the hand along the X-axis and Y-axis, respectively. Then, we use the result of these two preamble gestures as the fingerprint of different initial positions. At last, we find the least deviation position to estimate the optimal initial position