TRANSACTIONS ON MOBILE COMPUTING,VOL.17,NO.10,OCTOBER 2018 11 -08 ·Estimated position *Ground truth -09 -With Coarse Estimation -12 W/O Coarse Estimation W/O Template 1 0.8 0.9 1.1 12 13 5 10 15 20 X(m) Distance(cm) (a)Initial position error in the 2D space (b)CDF for estimated initial position error ■Normal 3.5 ■Office 0.8 0.8 Wak -With Coarse Estimation 0.6 -W/O Coarse Estimation 0.6 Perpendicular plane 2.5 8 总 -Horizontal plane -W/O Initilal position 0.4 04 1.5 0.2 02 0.5 5 10 15 20 25 30 10 15 20 Time(Second) Distance(cm) Users (c)CDF of processing time (d)CDF of tracking error for 2D (e)Different scenarios Figure 19.2D measurement shows that WiTrace has high precision even if the user's hand is complexity of our algorithm by running the algorithm on the same not at the same height with transceiver or another people walking dataset with 150 instances on a desktop with an i7-7700 CPU. around the user. The average running time of the two-step initial position estim- Impact of TX-RX distance in ID space:WiTrace achieves ation is 1.65 seconds,while our preliminary algorithm without an average tracking error that is lower than 3.71 cm over different coarse estimation takes 20.58 seconds on the same machine.The TX-RX distances.We change the TX-RX distances from I m to superior performance is mainly due to the smaller candidate region 5 m and ask the user to push for 30 cm at a distance of 1.2 m provided by the coarse estimation. to the receiver.Figure 18(g)shows that WiTrace achieves the best tracking performance(i.e.,2.37 cm error on average)with a TX- Tracking error in 2D space:For 2D tracking,WiTrace RX distance of I m.With the TX-RX distance of larger than 3 m, achieves an average tracking error of 2.09 cm.Figure 20 shows WiTrace undergoes a slight degradation trend. samples of three shapes'trajectories (i.e.,rectangle,triangle,and Estimated initial position error in 2D space:WiTrace circle)drawn by WiTrace.We calculate each trajectory with time achieves average 6.23 cm estimated error with the template,and interval of 0.04 seconds for adjacent points.The average time for average 10.18 cm error without template in 2D space.Figure users to finish drawing the rectangle,triangle,and circle are 2.9 19(a)shows the estimated initial positions when users perform seconds,2.3 seconds,and 2.1 seconds,respectively.The initial 100 pairs of vertical movements and horizontal movements along position of user's hand is at the distance of 1.2 m with respect the template with the real initial position(1,-1).Both vertical to the transmitter,and the drawing areas are around 30 x 30 and horizontal movement distances range from 15 cm to 30 cm. cm.Figure 19(d)shows the CDF of the 2D tracking errors of Figure 19(b)shows that 80th percentile estimated distance error is 100 drawing movements in "Normal"scenario,which is defined within 9.48 cm with template.This is mainly because the dynamic as the distance of all points on the trace to the nearest points path measurements have slight error,which leads to the error of on the template.The 90th percentile measurement error is 3.95 estimated position according to our model.Additionally,we ask cm and the average error is 2.09 cm comparing with the ground users to perform the same movement without the template.The truth when the two receivers are in default perpendicular plane result shows that the 80th estimating error is 14.05 cm,larger than as shown in Figure 17(d).Note that if two receivers are in the the previous result.This is because the movement of user's hand is horizontal plane,the average measurement error is 2.15 cm, more random than pushing along the template.Figure 19(b)also similar to the perpendicular setup.It indicates that different setups shows that the initial estimation errors with and without the coarse have little impact on the 2D tracking accuracy.Moreover,without estimation are almost the same. the initial position,the tracking performance will degrade severely. Computational complexity of initial position estimation: As shown in Figure 19(d),we assume that the initial position is WiTrace's initial position estimation process reduces the com- 30 cm away from the practical location,the tracking error will putational complexity by more than 12 times when compared to increase to 6.23 cm on average.Additionally,Figure 20 also shows our preliminary algorithm [1].We evaluate the computational that Kalman Filter improves the tracking accuracy effectively.TRANSACTIONS ON MOBILE COMPUTING, VOL. 17, NO. 10, OCTOBER 2018 11 0.8 0.9 1 1.1 1.2 1.3 X(m) -1.3 -1.2 -1.1 -1 -0.9 -0.8 Y(m) Estimated position Ground truth (a) Initial position error in the 2D space 0 5 10 15 20 Distance(cm) 0 0.2 0.4 0.6 0.8 1 CDF With Coarse Estimation W/O Coarse Estimation W/O Template (b) CDF for estimated initial position error 0 5 10 15 20 25 30 Time(Second) 0 0.2 0.4 0.6 0.8 1 CDF With Coarse Estimation W/O Coarse Estimation (c) CDF of processing time 0 5 10 15 20 25 30 Distance(cm) 0 0.2 0.4 0.6 0.8 1 CDF Perpendicular plane Horizontal plane W/O Initilal position (d) CDF of tracking error for 2D 12345 Users 0 0.5 1 1.5 2 2.5 3 3.5 4 Error(cm) Normal Office Walk (e) Different scenarios Figure 19. 2D measurement shows that WiTrace has high precision even if the user’s hand is not at the same height with transceiver or another people walking around the user. Impact of TX-RX distance in 1D space: WiTrace achieves an average tracking error that is lower than 3.71 cm over different TX-RX distances. We change the TX-RX distances from 1 m to 5 m and ask the user to push for 30 cm at a distance of 1.2 m to the receiver. Figure 18(g) shows that WiTrace achieves the best tracking performance (i.e., 2.37 cm error on average) with a TX￾RX distance of 1 m. With the TX-RX distance of larger than 3 m, WiTrace undergoes a slight degradation trend. Estimated initial position error in 2D space: WiTrace achieves average 6.23 cm estimated error with the template, and average 10.18 cm error without template in 2D space. Figure 19(a) shows the estimated initial positions when users perform 100 pairs of vertical movements and horizontal movements along the template with the real initial position (1, −1). Both vertical and horizontal movement distances range from 15 cm to 30 cm. Figure 19(b) shows that 80th percentile estimated distance error is within 9.48 cm with template. This is mainly because the dynamic path measurements have slight error, which leads to the error of estimated position according to our model. Additionally, we ask users to perform the same movement without the template. The result shows that the 80th estimating error is 14.05 cm, larger than the previous result. This is because the movement of user’s hand is more random than pushing along the template. Figure 19(b) also shows that the initial estimation errors with and without the coarse estimation are almost the same. Computational complexity of initial position estimation: WiTrace’s initial position estimation process reduces the com￾putational complexity by more than 12 times when compared to our preliminary algorithm [1]. We evaluate the computational complexity of our algorithm by running the algorithm on the same dataset with 150 instances on a desktop with an i7-7700 CPU. The average running time of the two-step initial position estim￾ation is 1.65 seconds, while our preliminary algorithm without coarse estimation takes 20.58 seconds on the same machine. The superior performance is mainly due to the smaller candidate region provided by the coarse estimation. Tracking error in 2D space: For 2D tracking, WiTrace achieves an average tracking error of 2.09 cm. Figure 20 shows samples of three shapes’ trajectories (i.e., rectangle, triangle, and circle) drawn by WiTrace. We calculate each trajectory with time interval of 0.04 seconds for adjacent points. The average time for users to finish drawing the rectangle, triangle, and circle are 2.9 seconds, 2.3 seconds, and 2.1 seconds, respectively. The initial position of user’s hand is at the distance of 1.2 m with respect to the transmitter, and the drawing areas are around 30 × 30 cm. Figure 19(d) shows the CDF of the 2D tracking errors of 100 drawing movements in “Normal” scenario, which is defined as the distance of all points on the trace to the nearest points on the template. The 90th percentile measurement error is 3.95 cm and the average error is 2.09 cm comparing with the ground truth when the two receivers are in default perpendicular plane as shown in Figure 17(d). Note that if two receivers are in the horizontal plane, the average measurement error is 2.15 cm, similar to the perpendicular setup. It indicates that different setups have little impact on the 2D tracking accuracy. Moreover, without the initial position, the tracking performance will degrade severely. As shown in Figure 19(d), we assume that the initial position is 30 cm away from the practical location, the tracking error will increase to 6.23 cm on average. Additionally, Figure 20 also shows that Kalman Filter improves the tracking accuracy effectively