WiTrace:Centimeter-Level Passive Gesture Tracking Using OFDM signals Lei Wang,Ke Sun,Haipeng Dai,Member,IEEE,Wei Wang,Member,IEEE, Kang Huang,Alex X.Liu,Senior Member,IEEE,Xiaoyu Wang,and Qing Gu Member,IEEE Abstract-Gesture tracking is a basic Human-Computer Interaction mechanism to control devices such as loT and VR/AR devices However,prior OFDM signal based systems focus on gesture recognition and provide results with insufficient accuracy,and thus cannot be applied for high-precision gesture tracking.In this paper,we propose a CSI based device-free gesture tracking system, called WiTrace,which leverages the CSI values extracted from OFDM signals to enable accurate gesture tracking.For 1D tracking, WiTrace derives the phase of the signals reflected by the hand from the composite signals,and measures the phase changes to obtain the movement distance.For 2D tracking,WiTrace proposes the first CSI based scheme to accurately estimate the initial position,and adopts the Kalman Filter based on continuous Wiener process acceleration model to further filter out tracking noise.Our results show that WiTrace achieves an average accuracy of 6.23 cm for initial position estimation,and achieves cm-level accuracy,with average tracking errors of 1.46 cm and 2.09 cm for 1D tracking and 2D tracking,respectively. Index Terms-CSl,Gesture Tracking 1 INTRODUCTION ESTURE tracking is a basic Human-Computer Interaction human body as one single object with decimeter-level resolution. mechanism to control not only electronic Intemet of Things Our recent work,QGesture,uses phase information extracted (IoT)devices but also VR/AR devices.In smart homes,gestures from WiFi signals to track human hands.However,due to the are recognized to change the channel of TVs or adjust the phase noises,QGesture has a limited accuracy of 5.5 cm at a temperature of air conditioners.In VR/AR applications,users use distance of 2 m and needs to know the initial position before gestures to interact with devices,such as typewriting in the air performing 2D tracking.The dominant technologies above are 2].Gesture tracking can also be used for writing-in-the-air and shown in Table 1.Other Radio Frequency(RF)and acoustic signal gesture-based games.Recently,OFDM based WiFi signals are based tracking schemes use localization technologies to track widely used for passive sensing for gesture movement as [3]- gestures.WiTrack [14].[15]proposes to use specially designed [5]due to its particular advantages.In comparison with vision Frequency-Modulated Continuous-Wave (FMCW)radar with a based methods [6],[7].WiFi based approaches are not limited by high bandwidth of 1.79 GHz to track human movement behind lighting condition and room layout as WiFi signals are able to the wall with a resolution of 11 cm to 20 cm,which needs penetrate through walls.Meanwhile,users don't bother to wear special hardware.Similar to RF signal,although acoustic tracking devices [8].which is convenient and saves the extra cost of schemes [16]-[19]have high accuracy,these systems cannot serve wearable devices.Prior WiFi based gesture recognition systems as remote control interface for home applications due to limited extract features from reflected signals for different gestures [4]. working range. [9]and use machine learning methods to recognize gestures.Nev- In this paper,we propose WiTrace,a WiFi OFDM based ertheless,these methods provide results with insufficient accuracy device-free cm-level gesture tracking system.Our key idea is to and cannot be applied to high-precision gesture tracking.Existing use the Channel State Information (CSD)values of WiFi to track WiFi based tracking schemes include WiDraw [10].Widar [11], the hand with centimeter-level accuracy in 2D space.We utilize the Widar 2.0 [12],and QGesture [13].WiDraw uses Angle-Of- fact that the phase changes of CSI values reflected by the hand are Arrival (AOA)measurements to achieve a tracking accuracy of proportional to the propagation path length changes of the hand. 5 cm,which allows the user to draw in the air in densely deployed Since the wavelength of 2.4 GHz WiFi signals is around 12.5 cm, areas with more than 25 WiFi transmitters surrounding the user. hand movement with a few centimeters will significantly affect the Widar and Widar 2.0 are human tracking schemes which treat the CSI values.WiTrace uses Universal Software Radio Peripheral (USRP)to transmit and receive the Commercial-Off-the-Shelf .L.Wang.K.Sun,H.Dai.W.Wang,K.Kang.X.Wang.O.Gu are (COTS)802.11g signals with a carrier frequency of 2.4 GHz and with the State Key Laboratory for Novel Software Technology.Nanjing a bandwidth of 20 MHz.For ID tracking,WiTrace extracts the University,Nanjing 210023.China (e-mail:wangl@smail.nju.edu.cn: kesun@smail.nju.edu.cn:haipengdai@nju.edu.cn;ww@nju.edu.cn;hk- phase of the signals reflected by the hand from the composite wany520@gmail.com:mg 1633074@smail.nju.edu.cn:guq@nju.edu.cn) signals,and measures the phase changes to obtain the movement Alex X.Liu is with the State Key Laboratory for Novel Software Tech- distance.Furthermore,WiTrace uses one transmitter and two nology,Nanjing University,Nanjing 210023,China,and also with the receivers to enable the 2D tracking of hand.We propose the first Department of Computer Science and Engineering.Michigan State Uni- versity.East Lansing.MI 48824 USA (e-mail:alexliu @cse.msu.edu). CSI based scheme to accurately estimate the initial position,which A preliminary version of this work appeared in the proceeding of IEEE SECON has huge impact on the overall system performance.Furthermore, 2018 (11.Manuscript received April 19.2005:revised August 26.2015. we adopt the Kalman Filter(KF)based method to filter out noise Corresponding author:Wei Wang. of tracking
WiTrace: Centimeter-Level Passive Gesture Tracking Using OFDM signals Lei Wang, Ke Sun, Haipeng Dai, Member, IEEE, Wei Wang, Member, IEEE, Kang Huang, Alex X. Liu, Senior Member, IEEE, Xiaoyu Wang, and Qing Gu Member, IEEE Abstract—Gesture tracking is a basic Human-Computer Interaction mechanism to control devices such as IoT and VR/AR devices. However, prior OFDM signal based systems focus on gesture recognition and provide results with insufficient accuracy, and thus cannot be applied for high-precision gesture tracking. In this paper, we propose a CSI based device-free gesture tracking system, called WiTrace, which leverages the CSI values extracted from OFDM signals to enable accurate gesture tracking. For 1D tracking, WiTrace derives the phase of the signals reflected by the hand from the composite signals, and measures the phase changes to obtain the movement distance. For 2D tracking, WiTrace proposes the first CSI based scheme to accurately estimate the initial position, and adopts the Kalman Filter based on continuous Wiener process acceleration model to further filter out tracking noise. Our results show that WiTrace achieves an average accuracy of 6.23 cm for initial position estimation, and achieves cm-level accuracy, with average tracking errors of 1.46 cm and 2.09 cm for 1D tracking and 2D tracking, respectively. Index Terms—CSI, Gesture Tracking ✦ 1 INTRODUCTION G ESTURE tracking is a basic Human-Computer Interaction mechanism to control not only electronic Internet of Things (IoT) devices but also VR/AR devices. In smart homes, gestures are recognized to change the channel of TVs or adjust the temperature of air conditioners. In VR/AR applications, users use gestures to interact with devices, such as typewriting in the air [2]. Gesture tracking can also be used for writing-in-the-air and gesture-based games. Recently, OFDM based WiFi signals are widely used for passive sensing for gesture movement as [3]– [5] due to its particular advantages. In comparison with vision based methods [6], [7], WiFi based approaches are not limited by lighting condition and room layout as WiFi signals are able to penetrate through walls. Meanwhile, users don’t bother to wear devices [8], which is convenient and saves the extra cost of wearable devices. Prior WiFi based gesture recognition systems extract features from reflected signals for different gestures [4], [9] and use machine learning methods to recognize gestures. Nevertheless, these methods provide results with insufficient accuracy and cannot be applied to high-precision gesture tracking. Existing WiFi based tracking schemes include WiDraw [10], Widar [11], Widar 2.0 [12], and QGesture [13]. WiDraw uses Angle-OfArrival (AOA) measurements to achieve a tracking accuracy of 5 cm, which allows the user to draw in the air in densely deployed areas with more than 25 WiFi transmitters surrounding the user. Widar and Widar 2.0 are human tracking schemes which treat the • L. Wang, K. Sun, H. Dai, W. Wang, K. Kang, X. Wang, Q. Gu are with the State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China (e-mail: wangl@smail.nju.edu.cn; kesun@smail.nju.edu.cn; haipengdai@nju.edu.cn; ww@nju.edu.cn; hkwany520@gmail.com; mg1633074@smail.nju.edu.cn; guq@nju.edu.cn). • Alex X. Liu is with the State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China, and also with the Department of Computer Science and Engineering, Michigan State University, East Lansing, MI 48824 USA (e-mail: alexliu@cse.msu.edu). A preliminary version of this work appeared in the proceeding of IEEE SECON 2018 [1]. Manuscript received April 19, 2005; revised August 26, 2015. Corresponding author: Wei Wang. human body as one single object with decimeter-level resolution. Our recent work, QGesture, uses phase information extracted from WiFi signals to track human hands. However, due to the phase noises, QGesture has a limited accuracy of 5.5 cm at a distance of 2 m and needs to know the initial position before performing 2D tracking. The dominant technologies above are shown in Table 1. Other Radio Frequency (RF) and acoustic signal based tracking schemes use localization technologies to track gestures. WiTrack [14], [15] proposes to use specially designed Frequency-Modulated Continuous-Wave (FMCW) radar with a high bandwidth of 1.79 GHz to track human movement behind the wall with a resolution of 11 cm to 20 cm, which needs special hardware. Similar to RF signal, although acoustic tracking schemes [16]–[19] have high accuracy, these systems cannot serve as remote control interface for home applications due to limited working range. In this paper, we propose WiTrace, a WiFi OFDM based device-free cm-level gesture tracking system. Our key idea is to use the Channel State Information (CSI) values of WiFi to track the hand with centimeter-level accuracy in 2D space. We utilize the fact that the phase changes of CSI values reflected by the hand are proportional to the propagation path length changes of the hand. Since the wavelength of 2.4 GHz WiFi signals is around 12.5 cm, hand movement with a few centimeters will significantly affect the CSI values. WiTrace uses Universal Software Radio Peripheral (USRP) to transmit and receive the Commercial-Off-the-Shelf (COTS) 802.11g signals with a carrier frequency of 2.4 GHz and a bandwidth of 20 MHz. For 1D tracking, WiTrace extracts the phase of the signals reflected by the hand from the composite signals, and measures the phase changes to obtain the movement distance. Furthermore, WiTrace uses one transmitter and two receivers to enable the 2D tracking of hand. We propose the first CSI based scheme to accurately estimate the initial position, which has huge impact on the overall system performance. Furthermore, we adopt the Kalman Filter (KF) based method to filter out noise of tracking
TRANSACTIONS ON MOBILE COMPUTING,VOL.17,NO.10,OCTOBER 2018 2 Table 1 Push Comparison of different WiFi-based systems NLOS A System Object Granularity Range TX&RX LOSB WiDraw 101 Hand 5 cm 0.6m 27 Transmitter Receiver QGesture [13] Hand 5.5cm 2m 3 wdar[11】 Human body 0.83.2m 3 NLOS CY 25 cm Widar 2.0 [12] Human body 75 cm 8m Wall Wikey [3] Gesture Recognition 4m 25 WiFinger [4] Gesture Recognition 14m Wigesture [9] Gesture Recognition 22m 22 WiTrace Gesture 2.09cm 23.5m Figure 1.Illustration of multiple paths WiTrace addresses three critical challenges.The first challenge 2 CSI PHASE MODEL is to achieve cm-level hand tracking accuracy for large range In this section,we describe the theoretical model of Channel State based on WiFi signals.Prior WiFi based tracking scheme uses Information (CSI)regarding dynamic gesture movement.Specific- AOA to track hand with large number of transmitters in the range ally,CSI estimates the channel properties of a communication of 2 feet [10].In contrast,we leverage the fact that the phase link,which is described by channel frequency response (CFR) changes of dynamic component of CSI are proportional to the path for k-th subcarrier frequency fk [23].As a result,CSI of the length changes caused by the object movement.By measuring k-th subcarrier at time t is the superimposition response of all and analyzing the phase changes.WiTrace achieves an average transmission paths [24]: distance error of 1.46 cm when pushing hand for 30 cm in the range of 1.2 m using omnidirectional antennas. The second challenge is to separate the phase changes caused (2πfkd(t)/c+中e ej(f,,(1) by the moving hands from CSI values caused by other environ- ments.The Signal-to-Noise Ratio (SNR),which represents the ratio of the reflecting power of target objects and other static where K is the total number of paths,is the attenuation coefficient of the k-th subcarrier,di(t)is the length of path i,c is objects,attenuates at long distance.As a result,the phase changes caused by the moving hands can be easily contaminated by other the speed of the wireless signal,and o;is the initial phase caused by time delay of the imperfect hardware.Additionally,traditional ambient interference,which means it is challenging to extract the phase changes from mixture signals.To address this challenge, CSI measurements typically have a phase shift of(f,t),which we apply a heuristic algorithm,i.e.Extracting Static Component is caused by residual frequency offset due to non-synchronized- clocks between transceiver pair.In order to rule out the phase (ESC)which lies in its robustness to the ambient interference. errors,we use an external clock [25]to connect the transmitter For In-phase (i.e.I)or Quadrature (i.e.Q)components of CSI. we first find the nearby local maxima and minima using empirical and the receiver in our system. As shown in Figure 1,all of the paths can be divided into threshold.To wipe out those noisy extreme points,we set temporal static paths,e.g.,the wall and LoS path,and dynamic paths e.g., threshold that is determined by the maximal Doppler frequency. The third challenge is to estimate the initial position of hand the hand.For static path i,the length of path di can be considered as fixed during a short period.As a result,Eq.(1)can be rewritten in 2D space.Although we can precisely measure the distance as' changes of hand movements,it is difficult to locate the absolute position of the hand directly without the initial hand location. Existing indoor localization based on WiFi signals [20]-[22]can k(t)=afei(2rd()/+), (2) be used for initial location estimation.However,these systems iEPa only get the coarse location at decimeter level of the human body,which is insufficient for gesture tracking.To address this whereis the sum of CSI for the static paths that are constant challenge,we first estimate the coarse initial hand position based for a short duration,P is the set for the dynamic paths,and on the CSI phase difference of variant subcarriers caused by Ak=c/fr is the wavelength for frequency f. hand movement.This coarse initial position estimation can narrow Suppose we can derive the phase change of path i,i.e..A. down the candidate region for the following fine estimation step where the phase i is i=2mdi(t)/k+i.Thus,the length so that the computation complexity of the fine estimation can be change of dynamic path i is given by: significantly reduced.Then,we utilize the fact that the estimated trajectory would be different for different initial positions.We use the result of two preamble gestures as the fingerprints of different △d,= △p入 (3) 2π initial positions and combine two directions to refine the initial where Ai is the phase change of path i. position estimation.Our approach achieves an average accuracy Finally,our goal is to measure the phase changes of the of 6.23 cm for initial position estimation. dynamic path caused by hand movement,and thereby determine We implemented WiTrace using USRP transceivers.Our ex- the length change of dynamic path to track hand in the air. perimental results show that our approach achieves estimated accuracy of the initial hand position 6.23 cm on average,and tracks the hand movement with mean accuracy of 1.46 cm for ID 3 CSI PHASE BASED DISTANCE MEASUREMENT tracking and 2.09 cm for 2D tracking,respectively.The result also In this section.we propose a method to measure hand movement. shows that WiTrace reaches overall mean direction error of 7.32 Our measurement method contains four steps,as shown in Fig- degrees across five different directions in 2D space case. ure 2.First,we apply the Hampel filter to remove the noise of
TRANSACTIONS ON MOBILE COMPUTING, VOL. 17, NO. 10, OCTOBER 2018 2 Table 1 Comparison of different WiFi-based systems System Object Granularity Range TX&RX WiDraw [10] Hand 5 cm 0.6 m 27 QGesture [13] Hand 5.5 cm 2 m 3 Widar [11] Human body 25 cm 0.8 ∼ 3.2 m 3 Widar 2.0 [12] Human body 75 cm 8 m 2 Wikey [3] Gesture Recognition 4 m 5 WiFinger [4] Gesture Recognition 1 ∼ 4m 5 Wigesture [9] Gesture Recognition ≥ 2m ≥ 2 WiTrace Gesture 2.09 cm ≥ 3.5 m 3 WiTrace addresses three critical challenges. The first challenge is to achieve cm-level hand tracking accuracy for large range based on WiFi signals. Prior WiFi based tracking scheme uses AOA to track hand with large number of transmitters in the range of 2 feet [10]. In contrast, we leverage the fact that the phase changes of dynamic component of CSI are proportional to the path length changes caused by the object movement. By measuring and analyzing the phase changes, WiTrace achieves an average distance error of 1.46 cm when pushing hand for 30 cm in the range of 1.2 m using omnidirectional antennas. The second challenge is to separate the phase changes caused by the moving hands from CSI values caused by other environments. The Signal-to-Noise Ratio (SNR), which represents the ratio of the reflecting power of target objects and other static objects, attenuates at long distance. As a result, the phase changes caused by the moving hands can be easily contaminated by other ambient interference, which means it is challenging to extract the phase changes from mixture signals. To address this challenge, we apply a heuristic algorithm, i.e. Extracting Static Component (ESC) which lies in its robustness to the ambient interference. For In-phase (i.e. I ) or Quadrature (i.e. Q) components of CSI, we first find the nearby local maxima and minima using empirical threshold. To wipe out those noisy extreme points, we set temporal threshold that is determined by the maximal Doppler frequency. The third challenge is to estimate the initial position of hand in 2D space. Although we can precisely measure the distance changes of hand movements, it is difficult to locate the absolute position of the hand directly without the initial hand location. Existing indoor localization based on WiFi signals [20]–[22] can be used for initial location estimation. However, these systems only get the coarse location at decimeter level of the human body, which is insufficient for gesture tracking. To address this challenge, we first estimate the coarse initial hand position based on the CSI phase difference of variant subcarriers caused by hand movement. This coarse initial position estimation can narrow down the candidate region for the following fine estimation step so that the computation complexity of the fine estimation can be significantly reduced. Then, we utilize the fact that the estimated trajectory would be different for different initial positions. We use the result of two preamble gestures as the fingerprints of different initial positions and combine two directions to refine the initial position estimation. Our approach achieves an average accuracy of 6.23 cm for initial position estimation. We implemented WiTrace using USRP transceivers. Our experimental results show that our approach achieves estimated accuracy of the initial hand position 6.23 cm on average, and tracks the hand movement with mean accuracy of 1.46 cm for 1D tracking and 2.09 cm for 2D tracking, respectively. The result also shows that WiTrace reaches overall mean direction error of 7.32 degrees across five different directions in 2D space case. Transmitter Receiver Wall Push NLOS C LOS B NLOS A Figure 1. Illustration of multiple paths 2 CSI PHASE MODEL In this section, we describe the theoretical model of Channel State Information (CSI) regarding dynamic gesture movement. Specifically, CSI estimates the channel properties of a communication link, which is described by channel frequency response (CFR) for k-th subcarrier frequency fk [23]. As a result, CSI of the k-th subcarrier at time t is the superimposition response of all transmission paths [24]: −→H(t) k = X K i=1 α k i,te j(2πfkdi(t)/c+φi) ! e jψ(fk,t) , (1) where K is the total number of paths, α k i,t is the attenuation coefficient of the k-th subcarrier, di(t) is the length of path i, c is the speed of the wireless signal, and φi is the initial phase caused by time delay of the imperfect hardware. Additionally, traditional CSI measurements typically have a phase shift of ψ(fk, t), which is caused by residual frequency offset due to non-synchronizedclocks between transceiver pair. In order to rule out the phase errors, we use an external clock [25] to connect the transmitter and the receiver in our system. As shown in Figure 1, all of the paths can be divided into static paths, e.g., the wall and LoS path, and dynamic paths e.g., the hand. For static path i, the length of path di can be considered as fixed during a short period. As a result, Eq. (1) can be rewritten as: −→Hk (t) = −→Hk st + X i∈Pd α k i,te j(2πdi(t)/λk+φi) , (2) where −→H fk st is the sum of CSI for the static paths that are constant for a short duration, Pd is the set for the dynamic paths, and λk = c/fk is the wavelength for frequency fk. Suppose we can derive the phase change of path i, i.e., ∆ϕi , where the phase ϕi is ϕi = 2πdi(t)/λk + φi . Thus, the length change of dynamic path i is given by: ∆di = ∆ϕiλk 2π (3) where ∆ϕi is the phase change of path i. Finally, our goal is to measure the phase changes of the dynamic path caused by hand movement, and thereby determine the length change of dynamic path to track hand in the air. 3 CSI PHASE BASED DISTANCE MEASUREMENT In this section, we propose a method to measure hand movement. Our measurement method contains four steps, as shown in Figure 2. First, we apply the Hampel filter to remove the noise of
TRANSACTIONS ON MOBILE COMPUTING,VOL.17,NO.10,OCTOBER 2018 3 of CSI experiences large fluctuations because of phase change.We Receive CSI Denoise CSI asurements apply a sliding window to compute the variance of the amplitude continuously.We choose to use the amplitude instead of the phase mainly due to the less computational cost of the amplitude as the unwrapping process for phase calculation may incur additional Measure computation for rectifying the discontinuity in the phase.In Figure Remove Detect the moving distance 3(d).Std represents the standard deviation of each short period, and I component means the In-phase component of CSI values. Both Std and I component are normalized to [-1,1]for a clear illustration.As shown in Figure 3(d),the variance in static period Figure 2.Processing flow for 1D tracking is much smaller than the variance in dynamic period.So the movement period can be easily detected by using an empirical threshold.However,there may still exist some abnormal variances CSI signal.After removing the noise,we can verify the CSI phase due to multipath effect for one frequency.These multipaths are model by illustrating the CSI signal in two dimensions.Second, mainly caused by movement of other body parts.As a result,we we use the variance of CSI amplitude to detect the start of the combine the results of all the subcarriers by using mathematical movement.Third,we propose a heuristic algorithm to remove the expectation to mitigate the effect of multipath.Then,we use a static vector from the CSI signal.At last,we transform the phase predefined empirical threshold to detect the beginning and end of change of CSI signal to the movement distance. the movement. 3.1 CSI Signal Preprocessing 3.4 Static Vector Elimination As shown in Figure 3(a),raw CSI signals(red curves)have large In reality,it is challenging to remove static vector from the CSI jitters as they contain various types of noise [26].On one hand, measurement.On one hand,the static vector that is mainly caused there are many outliers in CSI signal,which are mostly caused by static reflectors,e.g.,Path B and Path C as shown in Figure 1,is by wireless interference.On the other hand,system hardware much stronger than the dynamic vector caused by hand,e.g.Path may generate high frequency noise [27].As a result,we need A.On the other hand,static vector may change slowly with the to preprocess the I/Q components of the CSI signal to remove moving of hand due to blocking of other reflectors and the slow these noises.First,we apply the Hampel filter [28]to filter out the movement of other body parts (e.g.the arm).Additionally,even outliers that have are significantly different to others.The green though dynamic vector of hand dominates the variation of CSI, curve in Figure 3(a)shows the results after applying the Hampel SNR will degrade with distance between hand and receiving end. filter.Second,we utilize the moving average low-pass filter to There are some existing algorithms that separate static vector further remove high frequency noise.The black curve in Figure from dynamic vector of hand.Dual-Differential Background Re- 3(a)shows the result of the signal after filtering.We then get the moval (DDBR)and Phase Counting and Reconstruction(PCR)are complex valued CSI measurements using the I/Q components as used in 60 GHz Radar systems,such as mTrack [29],to remove the real/imaginary parts. the static vector.However,both methods are not suitable for CSI signal due to the high noise-level of CSI and the lack of periodicity 3.2 CSI Phase Model Verification that is required by PCR.LLAP [16]based on ultrasound applies a heuristic algorithm called Local Extreme Value Detection (LEVD) In Figure 3(b).we use a real world CSI measurement to illustrate how CSI phase changes in our CSI phase model.During a short based on Empirical Mode Decomposition (EMD)algorithm [30] to estimate the static vector.It isolates the static vector by time period from 1.25 to 1.7 seconds,a user pushes his hand for 28 cm towards the receiving end.As the two-way path length detecting whether the gap between alternate local maximum and change is△d=28×2 cm and the wavelengthλis12.5cm,we minimum points is larger than an empirical threshold Thr.Here Thr is set as three times of the standard deviation of the baseband find that CSI rotates clockwise for△d/入=28×2/12.5≈4.5 signal in a static environment.However,for CSI signal,the static cycles.We further observe that the static vector which corresponds vector is always contaminated by surrounding noise,thus,it is to the static path is not constant during this period.This is mainly difficult to reliably detect the local maximum and minimum points due to other slow changes around ambient environment during the hand movement.Meanwhile,the CSI amplitude is not stable by threshold Thr.For example,most maximum and minimum points in Figure 3(e)are failed to be detected by LEVD.As during the period.This is owing to the increasing strength of reflected signal.As a result,we need to remove the static vector a result,we propose the Extracting Static Component (ESC) method as shown in Algorithm I to estimate static vector.On and extract the dynamic vector,which corresponds to the dynamic path,to get the phase change of dynamic vector as shown in Figure one hand,instead of using threshold that is three times of the standard deviation,we use empirical threshold called Thrm, 3(c).Note that the centers of the traces of the dynamic vectors are moved to the origin so that we can directly measure the phase of which is far below the previous threshold to avoid neglecting small local extreme points.However,this operation may include them. some noisy points leading to incorrect static components.To remove noisy extreme points in the environment,we set a temporal 3.3 Movement Detection threshold related to the frequency shift of signals caused by gesture Before measuring the movement,our system needs to detect the movement,Ta,to 1/(2fdm)-u,where fd is the largest start of the movement.When user keeps static,the amplitude of Doppler frequency shift for each short period and u is a small CSI is stable except for small fluctuation caused by ambient noise. positive constant.We apply Short Time Fourier Transform(STFT) Meanwhile,once the user begins to move his hand,the amplitude method on CSI measurements to derive the instantaneous Doppler
TRANSACTIONS ON MOBILE COMPUTING, VOL. 17, NO. 10, OCTOBER 2018 3 Detect the movement No Yes Remove static vector Measure moving distance Receive CSI measurements Denoise CSI measurements Figure 2. Processing flow for 1D tracking CSI signal. After removing the noise, we can verify the CSI phase model by illustrating the CSI signal in two dimensions. Second, we use the variance of CSI amplitude to detect the start of the movement. Third, we propose a heuristic algorithm to remove the static vector from the CSI signal. At last, we transform the phase change of CSI signal to the movement distance. 3.1 CSI Signal Preprocessing As shown in Figure 3(a), raw CSI signals (red curves) have large jitters as they contain various types of noise [26]. On one hand, there are many outliers in CSI signal, which are mostly caused by wireless interference. On the other hand, system hardware may generate high frequency noise [27]. As a result, we need to preprocess the I/Q components of the CSI signal to remove these noises. First, we apply the Hampel filter [28] to filter out the outliers that have are significantly different to others. The green curve in Figure 3(a) shows the results after applying the Hampel filter. Second, we utilize the moving average low-pass filter to further remove high frequency noise. The black curve in Figure 3(a) shows the result of the signal after filtering. We then get the complex valued CSI measurements using the I/Q components as the real/imaginary parts. 3.2 CSI Phase Model Verification In Figure 3(b), we use a real world CSI measurement to illustrate how CSI phase changes in our CSI phase model. During a short time period from 1.25 to 1.7 seconds, a user pushes his hand for 28 cm towards the receiving end. As the two-way path length change is ∆d = 28 × 2 cm and the wavelength λ is 12.5 cm, we find that CSI rotates clockwise for ∆d/λ = 28 × 2/12.5 ≈ 4.5 cycles. We further observe that the static vector which corresponds to the static path is not constant during this period. This is mainly due to other slow changes around ambient environment during the hand movement. Meanwhile, the CSI amplitude is not stable during the period. This is owing to the increasing strength of reflected signal. As a result, we need to remove the static vector and extract the dynamic vector, which corresponds to the dynamic path, to get the phase change of dynamic vector as shown in Figure 3(c). Note that the centers of the traces of the dynamic vectors are moved to the origin so that we can directly measure the phase of them. 3.3 Movement Detection Before measuring the movement, our system needs to detect the start of the movement. When user keeps static, the amplitude of CSI is stable except for small fluctuation caused by ambient noise. Meanwhile, once the user begins to move his hand, the amplitude of CSI experiences large fluctuations because of phase change. We apply a sliding window to compute the variance of the amplitude continuously. We choose to use the amplitude instead of the phase mainly due to the less computational cost of the amplitude as the unwrapping process for phase calculation may incur additional computation for rectifying the discontinuity in the phase. In Figure 3(d), Std represents the standard deviation of each short period, and I component means the In-phase component of CSI values. Both Std and I component are normalized to [−1, 1] for a clear illustration. As shown in Figure 3(d), the variance in static period is much smaller than the variance in dynamic period. So the movement period can be easily detected by using an empirical threshold. However, there may still exist some abnormal variances due to multipath effect for one frequency. These multipaths are mainly caused by movement of other body parts. As a result, we combine the results of all the subcarriers by using mathematical expectation to mitigate the effect of multipath. Then, we use a predefined empirical threshold to detect the beginning and end of the movement. 3.4 Static Vector Elimination In reality, it is challenging to remove static vector from the CSI measurement. On one hand, the static vector that is mainly caused by static reflectors, e.g., Path B and Path C as shown in Figure 1, is much stronger than the dynamic vector caused by hand, e.g. Path A. On the other hand, static vector may change slowly with the moving of hand due to blocking of other reflectors and the slow movement of other body parts (e.g. the arm). Additionally, even though dynamic vector of hand dominates the variation of CSI, SNR will degrade with distance between hand and receiving end. There are some existing algorithms that separate static vector from dynamic vector of hand. Dual-Differential Background Removal (DDBR) and Phase Counting and Reconstruction (PCR) are used in 60 GHz Radar systems, such as mTrack [29], to remove the static vector. However, both methods are not suitable for CSI signal due to the high noise-level of CSI and the lack of periodicity that is required by PCR. LLAP [16] based on ultrasound applies a heuristic algorithm called Local Extreme Value Detection (LEVD) based on Empirical Mode Decomposition (EMD) algorithm [30] to estimate the static vector. It isolates the static vector by detecting whether the gap between alternate local maximum and minimum points is larger than an empirical threshold T hr. Here T hr is set as three times of the standard deviation of the baseband signal in a static environment. However, for CSI signal, the static vector is always contaminated by surrounding noise, thus, it is difficult to reliably detect the local maximum and minimum points by threshold T hr. For example, most maximum and minimum points in Figure 3(e) are failed to be detected by LEVD. As a result, we propose the Extracting Static Component (ESC) method as shown in Algorithm 1 to estimate static vector. On one hand, instead of using threshold that is three times of the standard deviation, we use empirical threshold called T hrm, which is far below the previous threshold to avoid neglecting small local extreme points. However, this operation may include some noisy points leading to incorrect static components. To remove noisy extreme points in the environment, we set a temporal threshold related to the frequency shift of signals caused by gesture movement, Td, to 1/(2fdmax ) − µ, where fdmax is the largest Doppler frequency shift for each short period and µ is a small positive constant. We apply Short Time Fourier Transform (STFT) method on CSI measurements to derive the instantaneous Doppler
TRANSACTIONS ON MOBILE COMPUTING,VOL.17,NO.10,OCTOBER 2018 0.04 -Raw I component -Raw CSI Step1(Hampel filter) 兰0.9 Step2(Average moving filte 0.06 -0.08 0.7 0.12 06 -0.141 1.2 14 1.6 18 0.740.760.780.80.820.84 Time(Second) I component (a)CSI preprocessing (b)I/Q trace of filtered CSI 0.05 15 -125 -Dynamic vetor -Std I componen -1.3 0 8 LEVD ESC extreme point LEVD extreme point .1.4g 0 0.05 05 1.5 0 0.102 0.30.40.50.60.7 0.8 I component Time (second) Time(second） (c)I/Q trace of dynamic vector (d)Variance of I/Q component (e)Static vector estimation of LEVD and ESC Figure 3.1D tracking measurement Algorithm 1:Extracting Static Component Algorithm according to Eq.(3).As Figure I shows,since transmitter/receiver Input:CSI signal of real or imaginary part X(t)=X(t)or and hand are set on the same line,the real movement distance X(t).CSI deviation of real or imaginary part d,=d of hand is half of the path length,e.g.,Ad= when ord for previous static period. a user pushes his hand from moment ti to ti.Although we Output:Estimated static vector S(t) have mitigated the effect of static multipath by removing the 1 Initialize extrema of real and imaginary part:E(ti)=E(ti) static vector,there still remains some dynamic multipath effect or ER(t),where t;is the timestamps of extrema; when hands move.We utilize the fact that different subcarriers 2 for each time t do have different frequencies.Meanwhile,when there is no multipath if detect the movement then /*Find extreme point of X(t)*/ effect,the measured distance changes should be the same for all ifX(t)is a local extrema and X(t)-E(ti)2 ds subcarriers,while the phase changes of different subcarriers are then different.As a result,we combine results of different subcarriers Take STFT of X(t)to get the maximum doppler by using linear regression [161,which finds the best value of Ad frequency fmar: that fits all phase changes obtained from different frequencies,to ift-t≥l/(2fmar)-μthen further mitigate the multipath effect. i←i+1: 9 t1←t; 10 E(t)←X(e: 4 2D TRACKING 么 Xs(t)←(E(t)+E(t-1)/2: In this section,we present our 2D tracking algorithm based on 12 /*Update the static vector*/ the distance measurements in Section 2.We first discuss the 3(e)←X()+jX8(e): CSI measurement noise sources that make our initial position estimation results significantly deviate from ground truth and take 14 return了(e); methods to reduce the noises.Then,we apply phase difference over different subcarriers to coarsely estimate the initial hand frequency shift fdm The duration between any two adjacent position and propose a novel algorithm to refine the resolution extreme points should be more than Td.which is slightly larger subsequently.At last,we present a KF based algorithm to further than half of the shortest period.As shown in Figure 3(e),ESC refine the trajectory. improves the accuracy to detect the movement of hand and avoids the small noise induced by ambient environment within the first 0.15 seconds. 4.1 CSI Measurement Evaluation and Denoising There are mainly three kinds of noises in CSI measurements that may give rise to large phase errors. 3.5 Distance Measurement Carrier Frequency Offset(CFO):CFO occurs when there After movement detection and static vector elimination,the phase exists carrier frequency mismatch between the transmitter and of dynamic vector changes linearly with path length change receiver oscillators.Although the CFO is compensated by the
TRANSACTIONS ON MOBILE COMPUTING, VOL. 17, NO. 10, OCTOBER 2018 4 1 1.2 1.4 1.6 1.8 Time(Second) 0.6 0.7 0.8 0.9 1 I component Raw I component Step1(Hampel filter) Step2(Average moving filter) (a) CSI preprocessing 0.74 0.76 0.78 0.8 0.82 0.84 I component -0.14 -0.12 -0.1 -0.08 -0.06 -0.04 Q component Raw CSI (b) I/Q trace of filtered CSI -0.05 0 0.05 I component -0.05 0 0.05 Q component Dynamic vetor (c) I/Q trace of dynamic vector 0 0.5 1 1.5 2 Time (second) -1.5 -1 -0.5 0 0.5 1 1.5 Normalized Std I component Threshold Movement Period (d) Variance of I/Q component 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 Time (second) -1.45 -1.4 -1.35 -1.3 -1.25 I/Q components Raw signal ESC LEVD ESC extreme point LEVD extreme point (e) Static vector estimation of LEVD and ESC Figure 3. 1D tracking measurement Algorithm 1: Extracting Static Component Algorithm Input: CSI signal of real or imaginary part X(t) = X I (t) or X Q(t). CSI deviation of real or imaginary part ds = d I s or d Q s for previous static period. Output: Estimated static vector −→S (t) 1 Initialize extrema of real and imaginary part: E(ti) = E I (ti) or E Q(ti), where ti is the timestamps of extrema; 2 for each time t do 3 if detect the movement then 4 /*Find extreme point of X(t) */ 5 if X(t) is a local extrema and |X(t) − E(ti)| ≥ ds then 6 Take STFT of X(t) to get the maximum doppler frequency fmax; 7 if t − ti ≥ 1/(2fmax) − µ then 8 i ← i + 1; 9 ti ← t; 10 E(ti) ← X(t); 11 Xs(t) ← (E(ti) + E(ti−1))/2; 12 /*Update the static vector*/ 13 −→S (t) ← X I s (t) + jXQ s (t); 14 return −→S (t) ; frequency shift fdmax . The duration between any two adjacent extreme points should be more than Td, which is slightly larger than half of the shortest period. As shown in Figure 3(e), ESC improves the accuracy to detect the movement of hand and avoids the small noise induced by ambient environment within the first 0.15 seconds. 3.5 Distance Measurement After movement detection and static vector elimination, the phase of dynamic vector changes linearly with path length change according to Eq. (3). As Figure 1 shows, since transmitter/receiver and hand are set on the same line, the real movement distance of hand is half of the path length, e.g., ∆d = dti−dtj 2 when a user pushes his hand from moment ti to tj . Although we have mitigated the effect of static multipath by removing the static vector, there still remains some dynamic multipath effect when hands move. We utilize the fact that different subcarriers have different frequencies. Meanwhile, when there is no multipath effect, the measured distance changes should be the same for all subcarriers, while the phase changes of different subcarriers are different. As a result, we combine results of different subcarriers by using linear regression [16], which finds the best value of ∆d that fits all phase changes obtained from different frequencies, to further mitigate the multipath effect. 4 2D TRACKING In this section, we present our 2D tracking algorithm based on the distance measurements in Section 2. We first discuss the CSI measurement noise sources that make our initial position estimation results significantly deviate from ground truth and take methods to reduce the noises. Then, we apply phase difference over different subcarriers to coarsely estimate the initial hand position and propose a novel algorithm to refine the resolution subsequently. At last, we present a KF based algorithm to further refine the trajectory. 4.1 CSI Measurement Evaluation and Denoising There are mainly three kinds of noises in CSI measurements that may give rise to large phase errors. Carrier Frequency Offset (CFO): CFO occurs when there exists carrier frequency mismatch between the transmitter and receiver oscillators. Although the CFO is compensated by the
TRANSACTIONS ON MOBILE COMPUTING,VOL.17,NO.10,OCTOBER 2018 451 -SFO retained 09 09 15 2 25 20 30 40 50 30 50 05 Time (Second) Subcarrier Subcarriers Standard Deviation(Radian) Figure 4.CSI phase changes of Figure 5.Raw CSI phase Figure 6.Denoised CSI phase of Figure 7.CDF of phase variance all subcarriers changes of various moment various moment for all subcarriers W/O SFO external clock in our system,the compensation is not perfect due strate the effect of the filter,we collect 150 CSI samples with a to the hardware imperfection.The residual CFO will lead to the duration of 96 ms.Then,we compute the standard deviation of time-varying CSI values offset as He(f,t)=(f,t). CSI phase over the 96 ms segment for each subcarrier.Figure where Af is the corresponding CFO.Fortunately,as shown in 10 shows that the average phase deviation significantly reduced Figure 4,the frequency shift over a silent duration of 1.5 seconds from 0.032 radians before filtering to 0.025 radians after filtering. is only 0.044 radians for all subcarriers,which is small,relative to The denoising process is necessary for the coarse estimation in the Doppler frequency caused by hand movements.Note that there Section 4.2,since the performance of coarse estimation would are no any dynamic paths over this silent duration.For example, degrade severely without denoising the Doppler frequency is at least 16 Hz when the velocity of a pushing hand is 1 m/s.This indicates that the impact of CFO can be ignored since it is small comparing to the impact of hand 4.2 Coarse Initial Position Estimation movements. After removing CSI noises,we use the phase difference between Sampling Frequency Offset(SFO)and Packet Detection subcarriers to coarsely estimate the initial position of hand.The Delay (PDD):In addition to CFO,two other noise sources (i.e. coarse initial position estimation can narrow down the candid- SFO and PDD)[13].[27]have the similar effect on the CSI ate region,which greatly reduces the complexity of the later measurements.As shown in Figure 5,the slopes of linear phase refinement algorithm.As shown in Eg.(2),CSI of one pair of shift are almost the same on the different frames during the transceiver is the superimposition of all paths.Suppose that there same measurement.However,the slope changes randomly across is only one dynamic path (i.e.,hand movement)in our system. different measurements when the equipments restarts due to the Thus,the CSI vector of all paths on k-th subcarrier at time t can randomness in the PLL locking process of the clock.Thus,we be described as: compensate the SFO/PDD offset whenever the system restarts.We use linear regression to remove the SFO/PDD offset [13].Figure 6 (t)=+aa(t)ej(2xdna()/A+ha) (4) shows the CSI phase before and after correction.We observe that where Hk,af(t).dnd(t).and ohd are the constant static the CSI phase is more consistent over different subcarriers after vector,the attenuation coefficient,path length and initial phase SFO/PDD correction.The largest phase difference for any two subcarriers is smaller than 0.03 radians,and there is only a small for hand reflection,respectively.We can use(t) residual difference of less than 0.01 radians after phase correction. (t)/)to represent the dynamic vector.As shown in Figure 11,the dynamic vector rotates due to the phase In case that the system restarts,CSI phase may have inconsistent initial phases.To demonstrate this,we collect 150 CSI samples shift caused by hand movements.Furthermore,the phase differ- ence of two subcarriers due to hand movement at time t can be across different measurements to compute the standard deviation described as: of CSI phase over all subcarriers.Figure 7 shows the standard deviation of phase averaged over different subcarriers reduced Apki,ka (t)=arg((t))-arg(()) (5) from 0.61 radians before removing the CFO to 0.01 radians after removing SFO. 2dhd(t)/XK2 -2ndhd(t)/Xk CSI variance:Although we have applied low-pass filter to where we use k,2 to represent two different subcarriers and remove high frequency noises at the denoising step,there is still arg((t))represents the the phase of dynamic vector cor- CSI variance even in silent period.For example,the standard responding to hand movement on subcarrier k.Once we know deviation of CSI phase for time period 01.5 s as shown in Ap(t),the path length can be calculated as: Figure 4 is 0.013 radians.This variance will degrade the initial hand position estimation performance significantly.To remove △Pk1k2(t)入k1入k2 (6) CSI noises efficiently,we use three cascading low-pass filters to dhd(t)= 2r(Ak1-入k2) constitute a new cascading filter as h'(t)=h(t)*h(t)*h(t), where h(t)is the impulse response for one low-pass filter and We use the tangent vector corresponding to dynamic vector represents convolution.Figure 8 shows the frequency response of (t).denoted as(t).to estimate pk The phase the cascading filter comparing with the previous average moving change of the dynamic vector is equivalent to phase change in filter.In Figure 9,we observe that high frequency noises are its tangent vector: attenuated significantly by the filter so that the SNR is improved, where SNR here is denoted by the ratio of normal hand movements △pk,k2()=【arg(ig(t)-元/2-[arg(i()-π/2A to the high frequency noises power on I/Q component.To demon- -arg(i好()-arg(() (7)
TRANSACTIONS ON MOBILE COMPUTING, VOL. 17, NO. 10, OCTOBER 2018 5 0 0.5 1 1.5 2 2.5 3 3.5 Time (Second) -4 -3 -2 -1 0 1 2 3 4 Phase (Radian) Subcarrier1 Subcarrier15 Subcarrier25 Subcarrier35 Subcarrier45 Subcarrier55 Figure 4. CSI phase changes of all subcarriers 0 10 20 30 40 50 60 Subcarriers 1 1.5 2 2.5 3 3.5 4 4.5 Phase (Radian) 0.1 s 0.3 s 0.5 s 0.7 s 0.9 s Figure 5. Raw CSI phase changes of various moment 0 10 20 30 40 50 60 Subcarriers 0.015 0.02 0.025 0.03 0.035 0.04 0.045 0.05 0.055 Phase (Radian) t=0.1 s t=0.3 s t=0.5 s t=0.7 s t=0.9 s Figure 6. Denoised CSI phase of various moment 0 0.5 1 1.5 Standard Deviation(Radian) 0 0.2 0.4 0.6 0.8 1 CDF SFO retained SFO removed Figure 7. CDF of phase variance for all subcarriers W/O SFO external clock in our system, the compensation is not perfect due to the hardware imperfection. The residual CFO will lead to the time-varying CSI values offset as −→Hc(f, t) = e j2π∆f t−→H(f, t), where ∆f is the corresponding CFO. Fortunately, as shown in Figure 4, the frequency shift over a silent duration of 1.5 seconds is only 0.044 radians for all subcarriers, which is small, relative to the Doppler frequency caused by hand movements. Note that there are no any dynamic paths over this silent duration. For example, the Doppler frequency is at least 16 Hz when the velocity of a pushing hand is 1 m/s. This indicates that the impact of CFO can be ignored since it is small comparing to the impact of hand movements. Sampling Frequency Offset (SFO) and Packet Detection Delay (PDD): In addition to CFO, two other noise sources (i.e. SFO and PDD) [13], [27] have the similar effect on the CSI measurements. As shown in Figure 5, the slopes of linear phase shift φ are almost the same on the different frames during the same measurement. However, the slope changes randomly across different measurements when the equipments restarts due to the randomness in the PLL locking process of the clock. Thus, we compensate the SFO/PDD offset whenever the system restarts. We use linear regression to remove the SFO/PDD offset [13]. Figure 6 shows the CSI phase before and after correction. We observe that the CSI phase is more consistent over different subcarriers after SFO/PDD correction. The largest phase difference for any two subcarriers is smaller than 0.03 radians, and there is only a small residual difference of less than 0.01 radians after phase correction. In case that the system restarts, CSI phase may have inconsistent initial phases. To demonstrate this, we collect 150 CSI samples across different measurements to compute the standard deviation of CSI phase over all subcarriers. Figure 7 shows the standard deviation of phase averaged over different subcarriers reduced from 0.61 radians before removing the CFO to 0.01 radians after removing SFO. CSI variance: Although we have applied low-pass filter to remove high frequency noises at the denoising step, there is still CSI variance even in silent period. For example, the standard deviation of CSI phase for time period 0 ∼ 1.5 s as shown in Figure 4 is 0.013 radians. This variance will degrade the initial hand position estimation performance significantly. To remove CSI noises efficiently, we use three cascading low-pass filters to constitute a new cascading filter as h 0 (t) = h(t) ∗ h(t) ∗ h(t), where h(t) is the impulse response for one low-pass filter and ∗ represents convolution. Figure 8 shows the frequency response of the cascading filter comparing with the previous average moving filter. In Figure 9, we observe that high frequency noises are attenuated significantly by the filter so that the SNR is improved, where SNR here is denoted by the ratio of normal hand movements to the high frequency noises power on I/Q component. To demonstrate the effect of the filter, we collect 150 CSI samples with a duration of 96 ms. Then, we compute the standard deviation of CSI phase over the 96 ms segment for each subcarrier. Figure 10 shows that the average phase deviation significantly reduced from 0.032 radians before filtering to 0.025 radians after filtering. The denoising process is necessary for the coarse estimation in Section 4.2, since the performance of coarse estimation would degrade severely without denoising. 4.2 Coarse Initial Position Estimation After removing CSI noises, we use the phase difference between subcarriers to coarsely estimate the initial position of hand. The coarse initial position estimation can narrow down the candidate region, which greatly reduces the complexity of the later refinement algorithm. As shown in Eq. (2) , CSI of one pair of transceiver is the superimposition of all paths. Suppose that there is only one dynamic path (i.e., hand movement) in our system. Thus, the CSI vector of all paths on k-th subcarrier at time t can be described as: −→Hk (t) = −→Hk st + α k hd(t)e j(2πdhd(t)/λk+φhd) (4) where Hk st, α k hd(t), dhd(t), and φhd are the constant static vector, the attenuation coefficient, path length and initial phase for hand reflection, respectively. We can use −→Hk hd(t) = α k hd(t)e j(2πdhd(t)/λk+φhd) to represent the dynamic vector. As shown in Figure 11, the dynamic vector rotates due to the phase shift caused by hand movements. Furthermore, the phase difference of two subcarriers due to hand movement at time t can be described as: ∆pk1,k2 (t) = arg( −→H k2 hd(t)) − arg( −→H k1 hd(t)) (5) = 2πdhd(t)/λk2 − 2πdhd(t)/λk1 where we use k1, k2 to represent two different subcarriers and arg( −→Hk hd(t)) represents the the phase of dynamic vector corresponding to hand movement on subcarrier k. Once we know ∆pk1,k2 (t), the path length can be calculated as: dhd(t) = ∆pk1,k2 (t)λk1 λk2 2π(λk1 − λk2 ) . (6) We use the tangent vector corresponding to dynamic vector −→Hk hd(t), denoted as −→Hk tg(t), to estimate ∆pk1,k2 . The phase change of the dynamic vector is equivalent to phase change in its tangent vector: ∆pk1,k2 (t) = [arg( −→H k2 tg (t)) − π/2] − [arg( −→H k1 tg (t)) − π/2] = arg( −→H k2 tg (t)) − arg( −→H k1 tg (t)). (7)
TRANSACTIONS ON MOBILE COMPUTING,VOL.17,NO.10,OCTOBER 2018 -Low pass averaging filter 一Before filtering 0.04 0.8 -Cascading filter e -After filtering 0.8 .035 0.03 0.4 02 0.025 一After filtering 50 100 150 200 0.005 0.010.0150.02 0.025 00150.020.0250.030.0350.040.045 Frequency (Hz) I component Standard Deviation(Radian) Figure 8.Frequency response of filter Figure 9.l/Q trace of CSI after filtering Figure 10.CDF of phase variance t+)g H2(t). TX(0.0) arg(日.() RX1(L1.0) 月2(1+1). "Aarg(H(t Fake initial position H2(t)- Subcarrier 2 (x0%) i'(t+). H(小 +) RX2(0,L2) HO -9-- Subcarrier 1 Initial position (xo.yo) V Figure 11.CSI vector changes Figure 12.2D geometric scenery According to the definition of tangent vector,the tangent vector of The coarse initial position estimation still has two problems to dynamic vector (t)can be approximated as: be considered.Firstly,which two subcarriers should be chosen to compute phase difference in Eq.(5).On one hand,the frequency arg((t))arg(Ha(t+1)-a(t)) (8) difference of these two subcarriers should not be too large.For where time t+1 is the next moment following time t.Since example,if the frequency difference is 20 MHz,the maximal path the static vector is constant for the short duration,Eq.(8)can be length should be limited to 8.35 m to make sure that the phase difference does not exceed 2.On the other hand,if the frequency rewritten as: difference is only 1 MHz,the estimated phase difference corres- arg(H(t))arg([Ha(t+1)+-[d(t)+) ponding to the path length of 2 m will be only 0.02 radians, ≈arg((t+1)-i() which can be easily contaminated by noise.In our system,we (9) choose two subcarriers which have frequency difference around 10 Based on above equations,we derive the phase difference of two MHz.Secondly,we need to choose appropriate time instance t to subcarriers due to hand movement at time t as: estimate the phase difference.We can only measure the dynamical △p1(=arg(i(t+1)-7()】 vector when the hand is moving.However,to serve as an initial position,we need to measure the phase difference as soon as the -arg(i1(t+1)-i() (10) hand moves.Thus,we perform phase difference estimation as soon as our system detects the movement as expressed in Section 3.3. Combining Eq.(6)and Eq.(10),we directly derive the path length of hand dhd(t)corresponding to one pair of transceiver at We use three experiments to evaluate coarse initial position time t. estimation algorithm.Firstly,we ask the volunteer to move his/her To estimate initial hand position in 2D,we use one transmitter hand at different distances to the transmitter.Figure 13 shows that and two receivers in two-dimensional space.As shown in Figure the average estimation error is less than 0.31 m when the volunteer 12,the transmitter is set at point(0,0),while two receivers are is at a distance of less than 2.5 m.The estimation error increases set at(L1,0)and(0,L2),respectively.Suppose that the lengths with the distance due to the weaker reflection signal at a longer of the two paths from transmitter to two receivers in Figure 12 distance.Secondly,we collect 150 CSI samples at a distance of are di and d2,respectively.Therefore,the position of the hand is 1.2 m to evaluate the estimation performance with/without the the intersection of the two ellipses defined by the following two denoising algorithm.Figure 14 shows that the average estimation equations: error with our denoising algorithm (ie.,"Normal")is 0.28 m and the average error without filtering is 0.38 m.If we don't remove -心+=1 the SFO,the estimation error could be as large as 4.91 m.Such d large random noise is due to the SFO introduced by the receiver (11) clock.Thirdly,to evaluate the impact of different scenarios and (+w-名2-1 4x2 users,we recruit five users to move their hands at a distance of 1.2 d m while other volunteers were performing office tasks(i.e.,typing) where (y)is the coordinate of the initial hand position. or walking at 2.5 m away from the transmitter.Figure 15 shows
TRANSACTIONS ON MOBILE COMPUTING, VOL. 17, NO. 10, OCTOBER 2018 6 0 50 100 150 200 Frequency (Hz) 0 0.2 0.4 0.6 0.8 1 Amplitude Low pass averaging filter Cascading filter Figure 8. Frequency response of filter 0.005 0.01 0.015 0.02 0.025 I component 0.025 0.03 0.035 0.04 Q component) After filtering Figure 9. I/Q trace of CSI after filtering 0.015 0.02 0.025 0.03 0.035 0.04 0.045 Standard Deviation(Radian) 0 0.2 0.4 0.6 0.8 1 CDF Before filtering After filtering Figure 10. CDF of phase variance Subcarrier 1 Subcarrier 2 Q I ( 1) 1 H t ( ) 1 H t 1 Htg ( ) 2 H t tg ( 1) 2 H t ( ) 2 H t ( ) 1 H t hd ( ) 2 H t hd 2 1 arg H (t) tg 2 1 arg H (t) hd 1 Hst 2 Hst ( 1) 2 Hhd t ( 1) 1 Hhd t Figure 11. CSI vector changes y TX (0,0) RX2(0,�") RX1(�#,0) Initial position (�%,�%) x Fake initial position (�% ' ,�% ' ) �% �% ' � �# �" Figure 12. 2D geometric scenery According to the definition of tangent vector, the tangent vector of dynamic vector −→Hk hd(t) can be approximated as: arg( −→Hk tg(t)) ≈ arg( −→Hk hd(t + 1) − −→Hk hd(t)) (8) where time t + 1 is the next moment following time t. Since the static vector is constant for the short duration, Eq. (8) can be rewritten as: arg( −→Hk tg(t)) ≈ arg([−→Hk hd(t + 1) + −→Hk st] − [ −→Hk hd(t) + −→Hk st]) ≈ arg( −→Hk (t + 1) − −→Hk (t)). (9) Based on above equations, we derive the phase difference of two subcarriers due to hand movement at time t as: ∆pk1,k2 (t) = arg( −→Hk2 (t + 1) − −→Hk2 (t)) −arg( −→Hk1 (t + 1) − −→Hk1 (t)). (10) Combining Eq. (6) and Eq. (10), we directly derive the path length of hand dhd(t) corresponding to one pair of transceiver at time t. To estimate initial hand position in 2D, we use one transmitter and two receivers in two-dimensional space. As shown in Figure 12, the transmitter is set at point (0, 0), while two receivers are set at (L1, 0) and (0, L2), respectively. Suppose that the lengths of the two paths from transmitter to two receivers in Figure 12 are d1 and d2, respectively. Therefore, the position of the hand is the intersection of the two ellipses defined by the following two equations: 4(x−L1/2)2 d 2 1 + 4y 2 d 2 1−L2 1 = 1 4x 2 d 2 2−L2 2 + 4(y−L2/2)2 d 2 2 = 1 (11) where (x, y) is the coordinate of the initial hand position. The coarse initial position estimation still has two problems to be considered. Firstly, which two subcarriers should be chosen to compute phase difference in Eq.(5). On one hand, the frequency difference of these two subcarriers should not be too large. For example, if the frequency difference is 20 MHz, the maximal path length should be limited to 8.35 m to make sure that the phase difference does not exceed 2π. On the other hand, if the frequency difference is only 1 MHz, the estimated phase difference corresponding to the path length of 2 m will be only 0.02 radians, which can be easily contaminated by noise. In our system, we choose two subcarriers which have frequency difference around 10 MHz. Secondly, we need to choose appropriate time instance t to estimate the phase difference. We can only measure the dynamical vector when the hand is moving. However, to serve as an initial position, we need to measure the phase difference as soon as the hand moves. Thus, we perform phase difference estimation as soon as our system detects the movement as expressed in Section 3.3. We use three experiments to evaluate coarse initial position estimation algorithm. Firstly, we ask the volunteer to move his/her hand at different distances to the transmitter. Figure 13 shows that the average estimation error is less than 0.31 m when the volunteer is at a distance of less than 2.5 m. The estimation error increases with the distance due to the weaker reflection signal at a longer distance. Secondly, we collect 150 CSI samples at a distance of 1.2 m to evaluate the estimation performance with/without the denoising algorithm. Figure 14 shows that the average estimation error with our denoising algorithm (i.e., “Normal” ) is 0.28 m and the average error without filtering is 0.38 m. If we don’t remove the SFO, the estimation error could be as large as 4.91 m. Such large random noise is due to the SFO introduced by the receiver clock. Thirdly, to evaluate the impact of different scenarios and users, we recruit five users to move their hands at a distance of 1.2 m while other volunteers were performing office tasks (i.e., typing) or walking at 2.5 m away from the transmitter. Figure 15 shows
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 inaccurate. 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 position 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 receiving 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
TRANSACTIONS ON MOBILE COMPUTING,VOL.17,NO.10,OCTOBER 2018 05 05 -0.45 -0.55 0.55 0.6 0.55 -06 -0.6 -0.65 ( 0.65 0. Real Initial 0.7 Real Initial Real Initial Position 2 Position -0.7 Position -0.75 -0.75 -0.75 08 0 .50.550.60.650.70.750.8 085050.6065、0707508 .450.50.550.60.650.70.750.8 X(m) X(m) X(m) (a)Horizontal (b)Vertical (c)Real experiment Figure 16.Initial position simulation and experimental results To better understand this method,we illustrate the process threshold th and thy,respectively.We set both th and thy as of initial position refinement via simulation.Suppose that a user 0.05 m in the following experiments.Next,we find two closest moves his hand along X-axis for 30 cm.We use a maximum candidate positions in the two directions and derive the new likelihood scheme to determine the initial position based on the estimation by linearly combining these two positions.The iteration measured distance change.Generally,the gesture trajectory (y) stops if the distance between these two candidate positions is related to candidate initial position (x',y)can be determined by smaller than an empirical threshold thz,which is set as 0.1 m. solving the following two equations: V2+y2+Vx-L1)2+y 4.4 Successive 2D Tracking =V2+y2+V(x-L1)2+2+△d山 As the lengths of the two initial paths from the transmitter to two receivers in Figure 12(di and d2)are estimated in Section 4.3. (12) the instantaneous length of the paths d and d can be calculated Vx2+y2+V2+(-L2) by updated distance change measurements (i.e..Ad and Ad2). =Vx2+y2+V2+(y-L2+△d2 Then,by solving Eq.(11)with the conditions of 0 and y<0, where Ad and Ad2 are the path length changes corresponding to the realtime position of hand can be located,and the successive two receivers at (L1,0)and (0,L2),while the source is at (0,0). position will be derived from this iterative method. Each path contains two segments,e.g.,V2+y2(from source to candidate initial position)and v(z'-L1)2+y2(from the 4.5 Trajectory Correction candidate initial position to RXI at (0,L1)).Eq.3 shows how The estimated trajectory of the hand still has large error due to the path length changes when the hand moves from candidate persistent systematic noise.To filter out such noise and further initial position (x',y)to (x,y).Therefore,the point (,y)on improve the accuracy of the trajectory,we propose to use the KF the gesture trajectory is on the intersections of two elliptic curves based on a 2D Continous Wiener Process Acceleration(CWPA) determined by the position of receivers and the measured path model [31],which basically handles the case where the object's length change.Figure 16(a)shows the simulating result for hori- acceleration is perturbed by Gaussian noise,to correct the traject- zontal movement.The color represents deviation of the trajectory ory.The state vector of 2D CWPA model is along Y-axis for various initial positions (ie.,arg max) Sk=[rk张王k弧k] (13) Similar to the horizontal movement,Figure 16(b)shows deviation of the trajectory along X-axis for the vertical movement (i.e., where (xk,y),(ik,and (k,are the movement dis- arg max).From Figure 16(a)and Figure 16(b).we find tances,velocity and acceleration of the hand at time k,respect- that the red point is the real initial position in our simulation. ively.The KF model assumes the true state at time k is evolved However,in reality,the real initial position may not be the red from the state at (k-1)according to point,since the distance measurement may have some errors.As Sk=Ask-1+qk (14) shown in Figure 16(c).the real initial position is the second darkest red point of all the candidate positions.Thus,we combine X-axis where only the movement acceleration has the process noise,q and Y-axis directions to locate the initial point more accurately. N(0,Q).Q is the covariance matrix of the process noise.Based Algorithm 2 shows the description of locating the initial point. on the physical laws of motion,the transition matrix is We first select the candidate area around coarse position estimation [10t0号t201 (e,ye)that is a square with side-length of L.Since the majority 010t0号2 of the estimation error is less than 0.5 m as shown in Figure 0010t 0 A 13,we set L as 0.5 m.We use an iterative candidate region (15) 00010 t selection algorithm that converges until the final initial position 00001 0 is determined.We calculate the tracking trajectory corresponding 00000 1 to all positions in the candidate region to find a limited number of candidates for the two directions separately.These candidates The measurement vector at time k in our system is should have movement deviations smaller than two empirical k=k VA]T (16)
TRANSACTIONS ON MOBILE COMPUTING, VOL. 17, NO. 10, OCTOBER 2018 8 0.5 0.55 0.6 0.65 0.7 0.75 0.8 X(m) -0.8 -0.75 -0.7 -0.65 -0.6 -0.55 -0.5 Y(m) 1 2 3 4 5 6 7 104 Real Initial Position (a) Horizontal 0.5 0.55 0.6 0.65 0.7 0.75 0.8 X(m) -0.8 -0.75 -0.7 -0.65 -0.6 -0.55 -0.5 Y(m) 1 2 3 4 5 6 7 104 Real Initial Position (b) Vertical 0.45 0.5 0.55 0.6 0.65 0.7 0.75 0.8 X(m) -0.8 -0.75 -0.7 -0.65 -0.6 -0.55 -0.5 -0.45 Y(m) 1 2 3 4 5 6 7 104 Real Initial Position (c) Real experiment Figure 16. Initial position simulation and experimental results To better understand this method, we illustrate the process of initial position refinement via simulation. Suppose that a user moves his hand along X-axis for 30 cm. We use a maximum likelihood scheme to determine the initial position based on the measured distance change. Generally, the gesture trajectory (x, y) related to candidate initial position (x 0 , y0 ) can be determined by solving the following two equations: p x 02 + y 02 + p (x 0 − L1) 2 + y 02 = p x 2 + y 2 + p (x − L1) 2 + y 2 + ∆d1 p x 02 + y 02 + p x 02 + (y 0 − L2) 2 = p x 2 + y 2 + p x 2 + (y − L2) 2 + ∆d2 (12) where ∆d1 and ∆d2 are the path length changes corresponding to two receivers at (L1, 0) and (0, L2), while the source is at (0, 0). Each path contains two segments, e.g., p x 02 + y 02 (from source to candidate initial position) and p (x 0 − L1) 2 + y 02 (from the candidate initial position to RX1 at (0, L1)). Eq.3 shows how the path length changes when the hand moves from candidate initial position (x 0 , y0 ) to (x, y). Therefore, the point (x, y) on the gesture trajectory is on the intersections of two elliptic curves determined by the position of receivers and the measured path length change. Figure 16(a) shows the simulating result for horizontal movement. The color represents deviation of the trajectory along Y-axis for various initial positions (i.e., arg maxy0 1 |y0−y| ). Similar to the horizontal movement, Figure 16(b) shows deviation of the trajectory along X-axis for the vertical movement (i.e., arg maxx0 1 |x0−x| ). From Figure 16(a) and Figure 16(b), we find that the red point is the real initial position in our simulation. However, in reality, the real initial position may not be the red point, since the distance measurement may have some errors. As shown in Figure 16(c), the real initial position is the second darkest red point of all the candidate positions. Thus, we combine X-axis and Y-axis directions to locate the initial point more accurately. Algorithm 2 shows the description of locating the initial point. We first select the candidate area around coarse position estimation (xe, ye) that is a square with side-length of L. Since the majority of the estimation error is less than 0.5 m as shown in Figure 13, we set L as 0.5 m. We use an iterative candidate region selection algorithm that converges until the final initial position is determined. We calculate the tracking trajectory corresponding to all positions in the candidate region to find a limited number of candidates for the two directions separately. These candidates should have movement deviations smaller than two empirical threshold thx and thy, respectively. We set both thx and thy as 0.05 m in the following experiments. Next, we find two closest candidate positions in the two directions and derive the new estimation by linearly combining these two positions. The iteration stops if the distance between these two candidate positions is smaller than an empirical threshold thz, which is set as 0.1 m. 4.4 Successive 2D Tracking As the lengths of the two initial paths from the transmitter to two receivers in Figure 12 (d1 and d2) are estimated in Section 4.3, the instantaneous length of the paths d 0 1 and d 0 2 can be calculated by updated distance change measurements (i.e., ∆d1 and ∆d2). Then, by solving Eq.(11) with the conditions of x > 0 and y < 0, the realtime position of hand can be located, and the successive position will be derived from this iterative method. 4.5 Trajectory Correction The estimated trajectory of the hand still has large error due to persistent systematic noise. To filter out such noise and further improve the accuracy of the trajectory, we propose to use the KF based on a 2D Continous Wiener Process Acceleration (CWPA) model [31], which basically handles the case where the object’s acceleration is perturbed by Gaussian noise, to correct the trajectory. The state vector of 2D CWPA model is sk = [xk yk x˙k y˙k x¨k y¨k] T (13) where (xk, yk), ( ˙xk, y˙k) and (¨xk, y¨k) are the movement distances, velocity and acceleration of the hand at time k, respectively. The KF model assumes the true state at time k is evolved from the state at (k − 1) according to sk = Ask−1 + qk (14) where only the movement acceleration has the process noise, qk ∼ N (0, Q), Q is the covariance matrix of the process noise. Based on the physical laws of motion, the transition matrix is A = 1 0 t 0 1 2 t 2 0 0 1 0 t 0 1 2 t 2 0 0 1 0 t 0 0 0 0 1 0 t 0 0 0 0 1 0 0 0 0 0 0 1 . (15) The measurement vector at time k in our system is zk = [xk yk] T (16)
TRANSACTIONS ON MOBILE COMPUTING,VOL.17,NO.10,OCTOBER 2018 9 Transmitter Receiver1 Transmitter Door Receiver Receiver2 Push direction +× Push direction Walk Walk 20访 Template +TX +TX XRX XRX ☆User ☆User Table ☆People Table ☆People 1 23 4 5 6 0 1 2 3 4 5 6 X(m) X(m) (a)ID scenario (b)2D scenario (c)ID setup (d)2D setup Figure 17.Evaluation environment in laboratory where (k,y)is the movement distance.As a result,the meas- (horizontal beam width =35 and vertical beam width =30) urement zk of the true state sk is made according to are used in our experiment.TX and RX antennas,are at the height of 0.8 m,and the user's hand is at the same height.Our wireless Zk=Hsk+Uk (17) transceiver system is synchronized by an external clock to avoid where vk is the measurement noise,vk N(0,R).R is the Carrier Frequency Offset and Sampling Frequency Offset,which covariance of the measurement noise.The observation matrix is changes the phase of CSI significantly.To synchronize two receiv- H= 100000 ers,we send 1000 abnormal frames which has 10752 bytes per 010000 (18) frame before tracking.The CSI evaluation results are processed offline using MATLAB.We choose offline evaluation because it is We use the model above to follow the traditional steps of KF to more repeatable in comparing the tracking performance between correct trajectory immediately. various schemes than real-time experiments. Note that other trajectory correction methods (e.g.,Roughness Penalty Smoothing and particle filter)have the similar perform- ance (as shown in Figure 20)to ours,they are not suitable for our 5.2 Evaluation Metrics system for their high computation cost and large processing delay. Our experiments are conducted in a laboratory with an area of 5 m x 6 m.For ID scenario,the transmitter and the receiver are IMPLEMENTATION AND EVALUATION set in a line,as shown in Figure 17(c).The distance between the transmitter and the receiver is 0.5 m. 5.1 Implementation We evaluate ID tracking with omnidirectional antennas in We implemented WiTrace on the software radio platform-USRP- terms of four metrics:(1)Tracking accuracy:the error between N210 hardware.The transmitting USRP with SBX board sends measured movement distance and ground truth movement distance IEEE 802.11g OFDM frames [32]with bandwidth 20 MHz at measured by ruler along the movement path when the distance 2.4 GHz [33].While it is possible to use higher bandwidth to between receiver and user is set to 1.2 m.(2)Tracking accuracy get better Time-of-Flight (ToF)measurements,we decide to use with different antennas:the error between measured distance and 20 MHz bandwidth because we mainly use the phase information the ground truth distance by using the omnidirectional antenna for localization,which is more accurate than ToF and does not and directional antenna along the same movement path at dif- benefit much from a higher bandwidth.There are 64 subcarriers ferent distances.(3)Tracking accuracy with different algorithms: in each transmitted frame,among which 48 subcarreiers are the measurement error by using different algorithms to extract for data,4 subcarriers are for pilot.Each receiver collects CSI the phase changes along the same movement path at different measurements at a rate of 20 M samples per second using a distances.(4)The robustness for different scenarios and users: laptop.Since each frame consists of 64 subcarriers,each receiver the measurement error for three different scenarios and five users. collects 64 CSI measurements per OFDM symbol.All subcarriers (5)The effect of hand height and other people walking around are modulated in Binary Phase Shift Keying.To reduce processing on tracking accuracy.For 2D scenario,the transmitter and the complexity,we downsample CSI streams for each subcarrier with receivers are set as shown in Figure 17(d).We evaluated 2D track- a downsample rate of 100.Therefore,the sampling rate is reduced ing with omnidirectional antennas from four metrics:(1)Initial to 20 M/(64 100)=3.125 KHz for each subcarrier.The position error:the distribution of all estimated initial positions transmission power is set to 20 dBm which is the same as the via preamble gesture.(2)Tracking error:the error between the COTS WiFi NIC.Note that the major difference between the CSI measured trace and the standard template.(3)The robustness for from commercial WiFi devices and USRP is that the USRP uses different scenarios and users for 2D.(4)The impact of different an external clock to synchronize the transceiver system,which pushing directions on 2D tracking. can effectively reduce the CFO,while CFO can only be reduced by heuristic clock compensation algorithms in WiFi CSI [13]. Thus,the signal phase measured by USRP is more stable than 5.3 Experimental Results by commercial WiFi devices.For ID tracking,our system uses Tracking accuracy in 1D space:WiTrace achieves average error one receiving USRP,as shown in Figure 17(a).For 2D tracking,of 1.46 cm when the hand moves for 30 cm at a distance of 1.2 two receiving USRPs are placed on the table as shown in Figure m.As shown in Figure 17(c),the initial position of volunteer 17(b).Both omnidirectional antennas and directional antennas is 1.2 m away from the receiver and the volunteer pushes hand
TRANSACTIONS ON MOBILE COMPUTING, VOL. 17, NO. 10, OCTOBER 2018 9 Transmitter Receiver Ruler (a) 1D scenario Receiver1 Transmitter Receiver2 Template (b) 2D scenario 0123456 X(m) 0 1 2 3 4 5 Y(m) Table Table Sofa Push direction Walk Door TX RX User People (c) 1D setup 0123456 X(m) 0 1 2 3 4 5 Y(m) Table Table Sofa Push direction Walk Door TX RX User People (d) 2D setup Figure 17. Evaluation environment in laboratory where (xk, yk) is the movement distance. As a result, the measurement zk of the true state sk is made according to zk = Hsk + vk (17) where vk is the measurement noise, vk ∼ N (0, R), R is the covariance of the measurement noise. The observation matrix is H = 1 0 0 0 0 0 0 1 0 0 0 0 . (18) We use the model above to follow the traditional steps of KF to correct trajectory immediately. Note that other trajectory correction methods (e.g., Roughness Penalty Smoothing and particle filter) have the similar performance (as shown in Figure 20) to ours, they are not suitable for our system for their high computation cost and large processing delay. 5 IMPLEMENTATION AND EVALUATION 5.1 Implementation We implemented WiTrace on the software radio platform-USRPN210 hardware. The transmitting USRP with SBX board sends IEEE 802.11g OFDM frames [32] with bandwidth 20 MHz at 2.4 GHz [33]. While it is possible to use higher bandwidth to get better Time-of-Flight (ToF) measurements, we decide to use 20 MHz bandwidth because we mainly use the phase information for localization, which is more accurate than ToF and does not benefit much from a higher bandwidth. There are 64 subcarriers in each transmitted frame, among which 48 subcarreiers are for data, 4 subcarriers are for pilot. Each receiver collects CSI measurements at a rate of 20 M samples per second using a laptop. Since each frame consists of 64 subcarriers, each receiver collects 64 CSI measurements per OFDM symbol. All subcarriers are modulated in Binary Phase Shift Keying. To reduce processing complexity, we downsample CSI streams for each subcarrier with a downsample rate of 100. Therefore, the sampling rate is reduced to 20 M/(64 ∗ 100) = 3.125 KHz for each subcarrier. The transmission power is set to 20 dBm which is the same as the COTS WiFi NIC. Note that the major difference between the CSI from commercial WiFi devices and USRP is that the USRP uses an external clock to synchronize the transceiver system, which can effectively reduce the CFO, while CFO can only be reduced by heuristic clock compensation algorithms in WiFi CSI [13]. Thus, the signal phase measured by USRP is more stable than by commercial WiFi devices. For 1D tracking, our system uses one receiving USRP, as shown in Figure 17(a). For 2D tracking, two receiving USRPs are placed on the table as shown in Figure 17(b). Both omnidirectional antennas and directional antennas (horizontal beam width = 35◦ and vertical beam width = 30◦ ) are used in our experiment. TX and RX antennas, are at the height of 0.8 m, and the user’s hand is at the same height. Our wireless transceiver system is synchronized by an external clock to avoid Carrier Frequency Offset and Sampling Frequency Offset, which changes the phase of CSI significantly. To synchronize two receivers, we send 1000 abnormal frames which has 10752 bytes per frame before tracking. The CSI evaluation results are processed offline using MATLAB. We choose offline evaluation because it is more repeatable in comparing the tracking performance between various schemes than real-time experiments. 5.2 Evaluation Metrics Our experiments are conducted in a laboratory with an area of 5 m × 6 m. For 1D scenario, the transmitter and the receiver are set in a line, as shown in Figure 17(c). The distance between the transmitter and the receiver is 0.5 m. We evaluate 1D tracking with omnidirectional antennas in terms of four metrics: (1) Tracking accuracy: the error between measured movement distance and ground truth movement distance measured by ruler along the movement path when the distance between receiver and user is set to 1.2 m. (2) Tracking accuracy with different antennas: the error between measured distance and the ground truth distance by using the omnidirectional antenna and directional antenna along the same movement path at different distances. (3) Tracking accuracy with different algorithms: the measurement error by using different algorithms to extract the phase changes along the same movement path at different distances. (4) The robustness for different scenarios and users: the measurement error for three different scenarios and five users. (5) The effect of hand height and other people walking around on tracking accuracy. For 2D scenario, the transmitter and the receivers are set as shown in Figure 17(d). We evaluated 2D tracking with omnidirectional antennas from four metrics: (1) Initial position error: the distribution of all estimated initial positions via preamble gesture. (2) Tracking error: the error between the measured trace and the standard template. (3) The robustness for different scenarios and users for 2D. (4) The impact of different pushing directions on 2D tracking. 5.3 Experimental Results Tracking accuracy in 1D space: WiTrace achieves average error of 1.46 cm when the hand moves for 30 cm at a distance of 1.2 m. As shown in Figure 17(c), the initial position of volunteer is 1.2 m away from the receiver and the volunteer pushes hand
TRANSACTIONS ON MOBILE COMPUTING,VOL.17,NO.10,OCTOBER 2018 10 WrO Plank -With Plank DDBR Omni antenna ◆LEVD Directional antenna ESC 15 2 25 35 15 2 25 3 3.5 Distance(cm) Distance(m) Distance(m) (a)CDF for measurements error (b)Different antennas (c)Different algorithms 雪Valking position TX-RX distance 3 0.50.8 12 18 Users X(m) X(m) Distance(m) (d)Different scenarios (e)Different hand heights (f)Different walking positions (g)Different TX-RX distances Figure 18.1D tracking error for a distance of 30 cm towards the receiver.Figure 18(a)shows WiTrace.we invited five users to push their hands towards receiver the Cumulative Distribution Function (CDF)of the distance error at a distance of 1.2 m while other volunteers were working or for 100 movements.The 80th percentile measurement error is walking 2 m away from the receiver.The users indices 2 and 2.59 cm and the average error is 1.46 cm.Note that if we place 3 correspond to females while others are males with age from a 5 cm thick plank (50 cm x 50 cm)between the transmitter and 20 to 62.As shown in Figure 18(d),the standard deviation receiver,the average tracking error will slightly increase to 4.99 of different users is 0.86 cm,which shows WiTrace is robust cm due to power loss during WiFi penetrating plank. for different users.Figure 18(d)shows the measurement errors Tracking accuracy with different antennas in 1D space: for three different scenarios:"Normal"is a typical silent indoor WiTrace achieves average error of 4.48 cm and 3.09 cm when scenario,"Office"represents the scenario that a person striking using omnidirectional antennas and directional antennas in the the keyboard near the user,and "Walk"represents the scenario range of 2 m,respectively.Figure 18(b)shows the average error that a person walking around 2 m away from the receiver.The by using omnidirectional antennas and directional antennas when average errors of“Normal",“Office”,and“Walk'arel.78cm, a volunteer is at different distances from the receiver.The results 1.85 cm and 2.72 cm,respectively.WiTrace has slightly larger show that WiTrace achieves an average distance error of 4.48 cm tracking errors for“Office”and“Walk”scenario than“Normal" and 3.09 cm when the hand moves for 30 cm over a distance of scenario.This is mainly because micro striking action and walking less than 2 m for omnidirectional antenna and directional antenna, around slightly affect the SNR of pushing.Our system's robust- respectively.The average tracking errors for both omnidirectional ness against walking interferences is due to two reasons.Firstly, antenna and directional antenna will increase to 7.20 cm and most high frequency noises caused by the walking movement 4.34 cm within the range of 3.5 m,due to the reduced SNR. can be efficiently removed through the low-pass filter in Section Note that the tracking error increases while user is quite close 3.1.Secondly,since the signal strength decays with the distance to the receiving end.This is because the reflection of limb and according to the power law,the reflection of walking volunteer at other dynamic body parts movement contaminate the dynamic 2 m has a limited effect on the user's pushing movement within vector by hand.The average accuracy of directional antenna 1.2 m.However,if the walking people is very close to the pushing outperforms omnidirectional antenna obviously.This is due to the user,the tracking performance would degrade severely. highly directional property of directional antenna,which leads to Impact of hand height and people walking in 1D space: larger SNR than omnidirectional antennas at the same distance. WiTrace achieves average tracking error of 6.46 cm and 3.80 cm Tracking accuracy with different algorithms in 1D space: while pushing hand at the height from 0.6 m to 1 m and another By using ESC,WiTrace achieves highly improvement than other people walking at the distance from 1.6 m to 2.2 m relative to algorithms.As shown in Figure 18(c),the average errors are the receiver,respectively.As shown in Figure 18(e),the tracking 7.20 cm,16.97 cm and 23.82 cm by using ESC,LEVD,and error becomes larger while the hand height is further away from DDBR in the range of 3.5 m,respectively.Results show that the the height of the plane of transceiver(i.e.,0.8 m).This is because ESC algorithm outperforms the DDBR algorithm and the LEVD that the practical path length caused by hand is larger than the algorithm since the ESC algorithm is less susceptible to noise and pushing distance and the SNR is lower for longer paths.Similarly, robust for different distances. closer distance between another walking volunteer and the receiver Robustness for different scenarios and users in 1D space: will decrease the SNR of our system shown in Figure 18(f).The WiTrace is robust to background activities which are 2 m away lower SNR will make it more difficult to detect movement of from the receiver for different users.To evaluate the robustness of hand accurately,leading to larger tracking errors.The result above
TRANSACTIONS ON MOBILE COMPUTING, VOL. 17, NO. 10, OCTOBER 2018 10 0 2 4 6 8 1012 Distance(cm) 0 0.2 0.4 0.6 0.8 1 CDF W/O Plank With Plank (a) CDF for measurements error 0.5 1 1.5 2 2.5 3 3.5 Distance(m) 0 2 4 6 8 10 12 Error(cm) Omni antenna Directional antenna (b) Different antennas 0.5 1 1.5 2 2.5 3 3.5 Distance(m) 0 5 10 15 20 25 30 Error(cm) DDBR LEVD ESC (c) Different algorithms 12345 Users 0 0.5 1 1.5 2 2.5 3 3.5 4 Error(cm) Normal Office Walk (d) Different scenarios 0.6 0.8 1 1.2 1.4 X(m) 0 2 4 6 8 10 12 14 16 Error(cm) Height (e) Different hand heights 2.2 X(m) 0 2 4 6 8 10 Error(cm) Walking position 1.4 1.6 1.8 2 (f) Different walking positions 2 3 4 Distance(m) 0 1 2 3 4 5 6 Error(cm) TX-RX distance 1 5 (g) Different TX-RX distances Figure 18. 1D tracking error for a distance of 30 cm towards the receiver. Figure 18(a) shows the Cumulative Distribution Function (CDF) of the distance error for 100 movements. The 80th percentile measurement error is 2.59 cm and the average error is 1.46 cm. Note that if we place a 5 cm thick plank (50 cm × 50 cm) between the transmitter and receiver, the average tracking error will slightly increase to 4.99 cm due to power loss during WiFi penetrating plank. Tracking accuracy with different antennas in 1D space: WiTrace achieves average error of 4.48 cm and 3.09 cm when using omnidirectional antennas and directional antennas in the range of 2 m, respectively. Figure 18(b) shows the average error by using omnidirectional antennas and directional antennas when a volunteer is at different distances from the receiver. The results show that WiTrace achieves an average distance error of 4.48 cm and 3.09 cm when the hand moves for 30 cm over a distance of less than 2 m for omnidirectional antenna and directional antenna, respectively. The average tracking errors for both omnidirectional antenna and directional antenna will increase to 7.20 cm and 4.34 cm within the range of 3.5 m, due to the reduced SNR. Note that the tracking error increases while user is quite close to the receiving end. This is because the reflection of limb and other dynamic body parts movement contaminate the dynamic vector by hand. The average accuracy of directional antenna outperforms omnidirectional antenna obviously. This is due to the highly directional property of directional antenna, which leads to larger SNR than omnidirectional antennas at the same distance. Tracking accuracy with different algorithms in 1D space: By using ESC, WiTrace achieves highly improvement than other algorithms. As shown in Figure 18(c), the average errors are 7.20 cm, 16.97 cm and 23.82 cm by using ESC, LEVD, and DDBR in the range of 3.5 m, respectively. Results show that the ESC algorithm outperforms the DDBR algorithm and the LEVD algorithm since the ESC algorithm is less susceptible to noise and robust for different distances. Robustness for different scenarios and users in 1D space: WiTrace is robust to background activities which are 2 m away from the receiver for different users. To evaluate the robustness of WiTrace, we invited five users to push their hands towards receiver at a distance of 1.2 m while other volunteers were working or walking 2 m away from the receiver. The users indices 2 and 3 correspond to females while others are males with age from 20 to 62. As shown in Figure 18(d), the standard deviation of different users is 0.86 cm, which shows WiTrace is robust for different users. Figure 18(d) shows the measurement errors for three different scenarios: “Normal” is a typical silent indoor scenario, “Office” represents the scenario that a person striking the keyboard near the user, and “Walk” represents the scenario that a person walking around 2 m away from the receiver. The average errors of “Normal”, “Office”, and “Walk” are 1.78 cm, 1.85 cm and 2.72 cm, respectively. WiTrace has slightly larger tracking errors for “Office” and “Walk” scenario than “Normal” scenario. This is mainly because micro striking action and walking around slightly affect the SNR of pushing. Our system’s robustness against walking interferences is due to two reasons. Firstly, most high frequency noises caused by the walking movement can be efficiently removed through the low-pass filter in Section 3.1. Secondly, since the signal strength decays with the distance according to the power law, the reflection of walking volunteer at 2 m has a limited effect on the user’s pushing movement within 1.2 m. However, if the walking people is very close to the pushing user, the tracking performance would degrade severely. Impact of hand height and people walking in 1D space: WiTrace achieves average tracking error of 6.46 cm and 3.80 cm while pushing hand at the height from 0.6 m to 1 m and another people walking at the distance from 1.6 m to 2.2 m relative to the receiver, respectively. As shown in Figure 18(e), the tracking error becomes larger while the hand height is further away from the height of the plane of transceiver (i.e., 0.8 m). This is because that the practical path length caused by hand is larger than the pushing distance and the SNR is lower for longer paths. Similarly, closer distance between another walking volunteer and the receiver will decrease the SNR of our system shown in Figure 18(f). The lower SNR will make it more difficult to detect movement of hand accurately, leading to larger tracking errors. The result above
