IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL.XX,NO.XX,2019 6 4.2.1 Angle Computation Algorithm 1 Linear Fitting to Extract Position Indicators. As the antenna collects phases at different time points dur- Input: ing its mobile scanning,we can extract the phase differences The angle profile of a certain tag,{(cot i,li)}; for a tag at different positions.Using these phase differences, The threshold of angle difference,6m; we compute the angle-of-arrivals with Eq.(1).To get a The threshold of separation interval,lm; deterministic angle,as mentioned above,the distance of the The threshold of sample length,Lmi positions among two phases should be within A/4. Output: Position indicators,h and lo; 4.2.2 Angle Smoothing 1:Do the linear fitting with the angle profile {(cot ai,li) Although using the phase difference from two positions based on Eq.(3),and get the fitted angle profile with small separation can get a unique angle,the noise like {(cot i,li)).For each sample i,compute the absolute the multi-path effect would influence the phase measure- angle differences 6;cot ai-cot ill; ment,there would exist the large fluctuation among angles, 2:while the maximum value of f>m do so the angle smoothing is required.Usually,the phase 3 Calculate the temporary angle difference threshold: collected by the antenna is not uniform,so is the angle dis- 6:max(om,the biggest decile of foi); tribution,thus it is not suitable to use the common smooth Remove all outliers with i>6t in the angle profile; algorithms,e.g.,low-pass filter.Taking the noise u into 5: onr:cosa=a驶+2，whendis very smal山4 Check the continuity of the angle profile,if the sep- aration interval between two neighbor samples is larger has much influence on cosa.While when d increases,such than lm,split samples and keep the major continuous distortion effect decreases,but there exist redundant angles part; in the results,only one of them is the true value.Hence,we 6: Redo the linear fitting with the remaining samples, can derive two sets of angles from two phase separations:a and compute the new angle differences [} small one and a large one,then use the unique angles from 7:end while the small separation to filter the several angle candidates 8:if the length of remaining samples >Lm then from the large separation,hence,we get a relative accurate 9: Calculate position indicators h and lo according to angle profile with less fluctuation [18].Note that,too large the final linear fitting result based on Eq.(3); separation will bring too much environmental change and 10 return h and lo; break the restraint of the angle estimation method.Thus, 11:else we set the small separation around 5-8cm and the large 12: Abandon this angle profile; separation within 15cm empirically when the antenna is in 13: return front of the packages about 1m. 14:end if 4.2.3 Linear Fitting With smoothed angles at different positions from an angle profile for a certain tag,we can use the linear model as Eq.(3)to fit them iteratively,then derive the two important position indicators(h and lo)of that tag for the later 3D reconstruction,details are depicted in Algorithm 1. Due to the ambient noise in the environment,the angle ◆-Original data profile contains outliers which may mislead the linear fitting Original linear fitting result,thus we need to figure out these outliers and elimi- Processed data -Processed linear fitting nate them to extract accurate position indicators.Denote the angle profile of a certain tag as {(cot i,li)},the fitted angle 0.5 1 15 2.5 profile based on Eq.(3)as {(coti,i)}.If the absolute angle Distance(m) difference of sample i,i.e.,cot a;-cot ill,is larger than Fig.9.Linear fitting with original data and final processed data angle difference threshold 6m,we take sample i as an outlier candidate.Considering that outliers affect the linear fitting no outliers.After the linear fitting process,if there are not result,some normal samples may be identified as outliers enough remaining samples,which means angles fluctuate due to the inaccurate fitting line,thus we automatically seriously all the time,we abandon such an angle profile set the temporary angle difference threshold based on the of the tag to improve the whole accuracy.Otherwise,we distribution of angle differences.Empirically,we select the calculate the position indicators h and lo from the final linear larger value between 6m and the biggest decile of the angle fitting result,where h represents the perpendicular distance difference [as the temporary angle difference threshold from the tag to the antenna mobile trace and lo reflects 6t,and om is set to 0.12 in our experiments.Hence,we re- the projected tag position along the scanning direction.In move all outliers whose angle differences are larger than our experiments,we set the separation interval threshold as Due to the outliers elimination,the origin sample sequence 0.6m under the moving speed of 0.12m/s and the sample can be noncontinuous,i.e.,the separation interval between length threshold as 200.Taking Fig.9 for example,the two neighbor samples is larger than a separation interval blue original angles contain several outliers and using our threshold Im.In this situation,we only keep the central algorithm can effectively eliminate them at both ends,the major part of the continuous samples,and use these remain- remaining yellow angles are much more smoother.The ing samples to redo the linear fitting process until there are position indicators (h,lo)from the original data and theIEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. XX, NO. XX, 2019 6 4.2.1 Angle Computation As the antenna collects phases at different time points dur￾ing its mobile scanning, we can extract the phase differences for a tag at different positions. Using these phase differences, we compute the angle-of-arrivals with Eq. (1). To get a deterministic angle, as mentioned above, the distance of the positions among two phases should be within λ/4. 4.2.2 Angle Smoothing Although using the phase difference from two positions with small separation can get a unique angle, the noise like the multi-path effect would influence the phase measure￾ment, there would exist the large fluctuation among angles, so the angle smoothing is required. Usually, the phase collected by the antenna is not uniform, so is the angle dis￾tribution, thus it is not suitable to use the common smooth algorithms, e.g., low-pass filter. Taking the noise µ into consideration: cos α = λ 2d ∆θ+µ 2π + nλ 2d , when d is very small, µ has much influence on cos α. While when d increases, such distortion effect decreases, but there exist redundant angles in the results, only one of them is the true value. Hence, we can derive two sets of angles from two phase separations: a small one and a large one, then use the unique angles from the small separation to filter the several angle candidates from the large separation, hence, we get a relative accurate angle profile with less fluctuation [18]. Note that, too large separation will bring too much environmental change and break the restraint of the angle estimation method. Thus, we set the small separation around 5-8cm and the large separation within 15cm empirically when the antenna is in front of the packages about 1m. 4.2.3 Linear Fitting With smoothed angles at different positions from an angle profile for a certain tag, we can use the linear model as Eq. (3) to fit them iteratively, then derive the two important position indicators (h and l0) of that tag for the later 3D reconstruction, details are depicted in Algorithm 1. Due to the ambient noise in the environment, the angle profile contains outliers which may mislead the linear fitting result, thus we need to figure out these outliers and elimi￾nate them to extract accurate position indicators. Denote the angle profile of a certain tag as {(cot αi , li)}, the fitted angle profile based on Eq. (3) as {(cotdαi , li)}. If the absolute angle difference of sample i, i.e., k cot αi − cotdαik, is larger than angle difference threshold δm, we take sample i as an outlier candidate. Considering that outliers affect the linear fitting result, some normal samples may be identified as outliers due to the inaccurate fitting line, thus we automatically set the temporary angle difference threshold based on the distribution of angle differences. Empirically, we select the larger value between δm and the biggest decile of the angle difference {δi} as the temporary angle difference threshold δt, and δm is set to 0.12 in our experiments. Hence, we re￾move all outliers whose angle differences are larger than δt. Due to the outliers elimination, the origin sample sequence can be noncontinuous, i.e., the separation interval between two neighbor samples is larger than a separation interval threshold lm. In this situation, we only keep the central major part of the continuous samples, and use these remain￾ing samples to redo the linear fitting process until there are Algorithm 1 Linear Fitting to Extract Position Indicators. Input: The angle profile of a certain tag, {(cot αi , li)}; The threshold of angle difference, δm; The threshold of separation interval, lm; The threshold of sample length, Lm; Output: Position indicators, h and l0; 1: Do the linear fitting with the angle profile {(cot αi , li)} based on Eq. (3), and get the fitted angle profile {(cotdαi , li)}. For each sample i, compute the absolute angle differences δi = k cot αi − cotdαik; 2: while the maximum value of {δi} > δm do 3: Calculate the temporary angle difference threshold: δt = max(δm, the biggest decile of {δi}); 4: Remove all outliers with δi > δt in the angle profile; 5: Check the continuity of the angle profile, if the sep￾aration interval between two neighbor samples is larger than lm, split samples and keep the major continuous part; 6: Redo the linear fitting with the remaining samples, and compute the new angle differences {δi}; 7: end while 8: if the length of remaining samples > Lm then 9: Calculate position indicators h and l0 according to the final linear fitting result based on Eq. (3); 10: return h and l0; 11: else 12: Abandon this angle profile; 13: return ; 14: end if 0 0.5 1 1.5 2 2.5 Distance (m) -4 -2 0 2 cot Original data Original linear fitting Processed data Processed linear fitting Fig. 9. Linear fitting with original data and final processed data no outliers. After the linear fitting process, if there are not enough remaining samples, which means angles fluctuate seriously all the time, we abandon such an angle profile of the tag to improve the whole accuracy. Otherwise, we calculate the position indicators h and l0 from the final linear fitting result, where h represents the perpendicular distance from the tag to the antenna mobile trace and l0 reflects the projected tag position along the scanning direction. In our experiments, we set the separation interval threshold as 0.6m under the moving speed of 0.12m/s and the sample length threshold as 200. Taking Fig. 9 for example, the blue original angles contain several outliers and using our algorithm can effectively eliminate them at both ends, the remaining yellow angles are much more smoother. The position indicators (h, l0) from the original data and the