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 the
IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. XX, NO. XX, 2019 6 4.2.1 Angle Computation As the antenna collects phases at different time points during 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 measurement, 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 distribution, 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 eliminate 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 remove 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 remaining 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 separation 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
IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL.XX,NO.XX,2019 (a)Rulel (b)Rule2 (c)Possible solution Linear Scanning Fig.10.Rules of deploying tags Fig.11.Experiment setup of linear fitting accuracy with different tag orientations final processed data are (1.4m,1.42m)and (1.23m,1.47m), respectively.Compared to ground-truth (1.3m,1.46m),the 15 accuracy improves a lot with the outliers elimination. 4.3 Determine Package Orientation for Each Single Package To reconstruct a single package,it makes the same sense to determine the package orientation,so we just need to iden- T1-T2T3-T4T5-T6T1-T3T3-T5 TI T2 T3 T4 T5 T6 tify the bottom face of this package,and estimate the relative rotation angle of the vertical sides against the antenna Fig.12.Accuracy along scanning Fig.13.Accuracy along orthogo- direction nal direction of scanning plane in a specified coordinate system.Here,the "antenna plane"refers to the extended plane of the antenna's front Fig.10(c),the results are plotted in Fig.12 and Fig.13. surface,which should be perpendicular to the ground in our We observe that the accuracy of projected position lo along settings.When the antenna performs the mobile scanning the scanning direction keeps stable with different orientations, linearly,it is just in the antenna plane. while the perpendicular distance h does not have the same high accuracy as lo.Fig.12 plots the accuracy of lo along the 4.3.1 Tag Layout antenna scanning direction,i.e.,the absolute separation Aiming at determining the package orientation only by once error between two tags along the scanning direction.Most 1D mobile scanning,we need to deploy tags in an efficient of the absolute separation errors of different tag pairs are and robust way.The design principle of tag deployment is to below 1.8cm,even in the worst case,the separation achieves use as fewer tags as possible to depict the package uniquely, around 92.3%accuracy.Fig.13 plots the accuracy of the accurately and conveniently.Specifically,as the package perpendicular distance h along the orthogonal direction to can be with any orientation in the 3D space,we should the scanning.The error is much larger than the separation pay attention to ensuring there are always enough effective error along the scanning direction.For tags with the same tags reflecting the signals to the antenna.Meanwhile,as for orientation,the near-far relationships between tags and the identifying the bottom face of the package,it is the same to antenna are reliable,but for tags with different orientations, find which tags are along the vertical axis and what order the error may incur the wrong near-far relationship,i.e.,T3 these tags are with.Therefore,we make two rules as follows. has the smaller h than T2,but T3 has the larger estimated h. 1) The orientations of tags should be along different orthog- Therefore,when using position indicators,we can leverage onal axes(in Fig.10(a)).With this rule,tags along one the projected positions of tags with different orientations, direction at most are in the blind direction,so other and prefer the perpendicular distances of tags with the same tags can response to the antenna successfully. orientation for comparison or calculation. 2) Tags should be deployed along different orthogonal axes (in Fig.10(b)).With this rule,whatever the orienta- 4.3.3 Determine Package Orientation tion of the package is,there is always one tag pair To determine the package orientation,it demands to identify along the vertical axis. the bottom face of the package and the relative angle of the Combining the above two rules,Fig.10(c)illustrates vertical sides in a specified coordinate system.Considering a possible tag deployment satisfying these two rules.No our assumption that one side of the cube package must be matter what orientation the package is,there are four tags parallel to the ground,when we deploy tags like the solution at least to avoid the signal blind direction.Also,there is described in Fig.10(c),we can identify which tag pair is always one tag pair along the Z axis.By determining the along the Z axis and what order the tag pair is in fact.In tags'order of this tag pair,we can derive which side of the this case,let the antenna do the mobile scanning along the package is on the ground then. X or Y axis only once,we can determine the orientation for a single package.Note that,the antenna should be above 4.3.2 Linear Fitting of Tags with Different Orientations or below all the tags,and the package is at the same side Considering that tags in the layout as Fig.10(c)have against the antenna plane during the scanning process different orientations,we carry out experiments to check For simplicity,suppose the antenna is above all the tags whether different orientations among tags have effects on and ahead of all the tags along the X axis positive direction, the accuracy of the linear fitting.As shown in Fig.11,it moves along the y axis,then the tag pair along the Z we arrange six tags with three orientations as required in axis is perpendicular to the antenna scanning direction,so
IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. XX, NO. XX, 2019 7 X Z Y X (a) Rule1 Y X Z Y X (b) Rule2 Y X Z Y ! " # $ % & (c) Possible solution Fig. 10. Rules of deploying tags final processed data are (1.4m, 1.42m) and (1.23m, 1.47m), respectively. Compared to ground-truth (1.3m, 1.46m), the accuracy improves a lot with the outliers elimination. 4.3 Determine Package Orientation for Each Single Package To reconstruct a single package, it makes the same sense to determine the package orientation, so we just need to identify the bottom face of this package, and estimate the relative rotation angle of the vertical sides against the antenna plane in a specified coordinate system. Here, the “antenna plane” refers to the extended plane of the antenna’s front surface, which should be perpendicular to the ground in our settings. When the antenna performs the mobile scanning linearly, it is just in the antenna plane. 4.3.1 Tag Layout Aiming at determining the package orientation only by once 1D mobile scanning, we need to deploy tags in an efficient and robust way. The design principle of tag deployment is to use as fewer tags as possible to depict the package uniquely, accurately and conveniently. Specifically, as the package can be with any orientation in the 3D space, we should pay attention to ensuring there are always enough effective tags reflecting the signals to the antenna. Meanwhile, as for identifying the bottom face of the package, it is the same to find which tags are along the vertical axis and what order these tags are with. Therefore, we make two rules as follows. 1) The orientations of tags should be along different orthogonal axes (in Fig. 10(a)). With this rule, tags along one direction at most are in the blind direction, so other tags can response to the antenna successfully. 2) Tags should be deployed along different orthogonal axes (in Fig. 10(b)). With this rule, whatever the orientation of the package is, there is always one tag pair along the vertical axis. Combining the above two rules, Fig. 10(c) illustrates a possible tag deployment satisfying these two rules. No matter what orientation the package is, there are four tags at least to avoid the signal blind direction. Also, there is always one tag pair along the Z axis. By determining the tags’ order of this tag pair, we can derive which side of the package is on the ground then. 4.3.2 Linear Fitting of Tags with Different Orientations Considering that tags in the layout as Fig. 10(c) have different orientations, we carry out experiments to check whether different orientations among tags have effects on the accuracy of the linear fitting. As shown in Fig. 11, we arrange six tags with three orientations as required in 0.5 m 0.3 m 0.5 m 0.3 m 1 m Linear Scanning !" !# !$ !% !& !' Fig. 11. Experiment setup of linear fitting accuracy with different tag orientations T1-T2 T3-T4 T5-T6 T1-T3 T3-T5 0 1 2 3 4 Error (cm) Fig. 12. Accuracy along scanning direction T1 T2 T3 T4 T5 T6 0 5 10 15 Error (cm) Fig. 13. Accuracy along orthogonal direction of scanning Fig. 10(c), the results are plotted in Fig. 12 and Fig. 13. We observe that the accuracy of projected position l0 along the scanning direction keeps stable with different orientations, while the perpendicular distance h does not have the same high accuracy as l0. Fig. 12 plots the accuracy of l0 along the antenna scanning direction, i.e., the absolute separation error between two tags along the scanning direction. Most of the absolute separation errors of different tag pairs are below 1.8cm, even in the worst case, the separation achieves around 92.3% accuracy. Fig. 13 plots the accuracy of the perpendicular distance h along the orthogonal direction to the scanning. The error is much larger than the separation error along the scanning direction. For tags with the same orientation, the near-far relationships between tags and the antenna are reliable, but for tags with different orientations, the error may incur the wrong near-far relationship, i.e., T3 has the smaller h than T2, but T3 has the larger estimated h. Therefore, when using position indicators, we can leverage the projected positions of tags with different orientations, and prefer the perpendicular distances of tags with the same orientation for comparison or calculation. 4.3.3 Determine Package Orientation To determine the package orientation, it demands to identify the bottom face of the package and the relative angle of the vertical sides in a specified coordinate system. Considering our assumption that one side of the cube package must be parallel to the ground, when we deploy tags like the solution described in Fig. 10(c), we can identify which tag pair is along the Z axis and what order the tag pair is in fact. In this case, let the antenna do the mobile scanning along the X or Y axis only once, we can determine the orientation for a single package. Note that, the antenna should be above or below all the tags, and the package is at the same side against the antenna plane during the scanning process. For simplicity, suppose the antenna is above all the tags and ahead of all the tags along the X axis positive direction, it moves along the Y axis, then the tag pair along the Z axis is perpendicular to the antenna scanning direction, so