3-Dimensional Localization via RFID Tag Array Yuan Zhangt,Lei Xief,Yanling But,Yanan Wangt,Jie Wut,and Sanglu Lut iState Key Laboratory for Novel Software Technology,Nanjing University,China Center for Networked Computing,Temple University,USA Email:zhangyuan@smail.nju.edu.cn,Ixie@nju.edu.cn,{yanling.yananwang}@smail.nju.edu.cn, jiewu@temple.edu,sanglu @nju.edu.cn Abstract-In this paper,we propose 3DLoc,which performs 3- dimensional localization on the tagged objects by using the RFID tag arrays.3DLoc deploys three arrays of RFID tags on three mutually orthogonal surfaces of each object.When performing Object location 3D localization,3DLoc continuously moves the RFID antenna and (Xo.yo,Zo) scans the tagged objects in a 2-dimensional space right in front of the tagged objects.It then estimates the object's 3D position Object according to the phases from the tag arrays.By referring to orientation Target tag array the fixed layout of the tag array,we use Angle of Arrival-based schemes to accurately estimate the tagged objects'orientation Antenna and 3D coordinates in the 3D space.To suppress the localization Fig.1.Illustration of 3DLoc errors caused by the multipath effect,we use the linear relation- ship of the AoA parameters to remove the unexpected outliers When performing the 3D localization,the RFID antenna from the estimated results.We have implemented a prototype continuously moves and scans the tagged objects in a 2D system and evaluated the actual performance in the real complex space right in front of the tagged objects.Specifically,the environment.The experimental results show that 3DLoc achieves RFID antenna first moves along the 2 axis and scans all tags the mean accuracy of 10cm in free space and 15.3cm in the multipath environment for the tagged object. to estimate the Z-coordinate of each tag from the tag array, 3DLoc then estimates the rough orientation of the object and I.INTRODUCTION selects a target tag array for further localization in the x- A.Motivation Y plane.After that,the RFID antenna moves along the X Nowadays,RFID has been widely used in several ap- axis and scans the tags in the target tag array.As it obtains plications such as warehouse and logistic management.In the phase values from the tag arrays,it estimates the object's these applications,each of the items is attached with one orientation and figures out the object's 3D coordinates in the or more RFID tags,which illustrate the detailed information 3D space,by leveraging the Angle of Arrival(AoA)-based of the specified items,e.g.,the production/expiration dates, localization schemes.For the layout of the tag array,each manufacturers,etc.With the assistance of RFID,many nov-tag's ID and relative position are known in advance to support el functions such as indoor localization can be effectively the 3D localization. realized.For example,with the exact locations of all items C.Challenges and Solutions on the shelves.the robotic arm can be used to fetch the There are two technical challenges in realizing 3D lo- specified items in a fully automated manner.However,most calization for the tagged objects.First,the 3D localization state-of-art RFID-based localization schemes,such as PinIt results can be severely impacted by interferences such as [10]and Tagoram [12],mainly focus on the localization in the multipath effect from the indoor environment.Due to the 2-dimensional(2D)space,e.g.,they usually provide the 2D the continuously changing factors in the multipath effect, coordinates of the objects in the indoor maps.These solutions it distorts the phase values of tags in a very unpredictable usually fail to locate the items which are arbitrarily stacked in approach,thus it could further lead to errors in the AoA- the 3-dimensional(3D)space,as shown in Fig.1.Therefore,it based localization.To address this challenge,we perform is essential to propose an RFID-based mechanism to accurately mobile scanning to continuously sample the phases of the perform 3D localization,so that the 3D coordinates of the specified tags at different positions,compute the spatial angles objects can be figured out in the 3D space. of arrival of the tags in different locations,and suppress the B.Proposed Approach outliers caused by the multipath effect.By using the mobile In this paper,we propose 3DLoc,which performs 3D scanning-based scheme,3DLoc investigates and uses the linear localization on the tagged objects by using the RFID tag relationship of the AoA parameters to remove the unexpected arrays.The basic idea is as follows:Without loss of generality,outliers from the estimated results via continuous sampling,so we assume that the tagged object is a cuboid with six surfaces, it is robust to the interferences including ambient noises and e.g.,an express package or a cardboard box.For each of the the multipath effect. specified objects,three arrays of RFID tags are attached onto Second,the orientation of the tagged objects is essential to three mutually orthogonal surfaces of the object in advance. be firstly determined before performing accurate 3D localiza-
3-Dimensional Localization via RFID Tag Array Yuan Zhang† , Lei Xie† , Yanling Bu† , Yanan Wang† , Jie Wu‡ , and Sanglu Lu† †State Key Laboratory for Novel Software Technology, Nanjing University, China ‡Center for Networked Computing, Temple University, USA Email: zhangyuan@smail.nju.edu.cn, lxie@nju.edu.cn, {yanling,yananwang}@smail.nju.edu.cn, jiewu@temple.edu, sanglu@nju.edu.cn Abstract—In this paper, we propose 3DLoc, which performs 3- dimensional localization on the tagged objects by using the RFID tag arrays. 3DLoc deploys three arrays of RFID tags on three mutually orthogonal surfaces of each object. When performing 3D localization, 3DLoc continuously moves the RFID antenna and scans the tagged objects in a 2-dimensional space right in front of the tagged objects. It then estimates the object’s 3D position according to the phases from the tag arrays. By referring to the fixed layout of the tag array, we use Angle of Arrival-based schemes to accurately estimate the tagged objects’ orientation and 3D coordinates in the 3D space. To suppress the localization errors caused by the multipath effect, we use the linear relationship of the AoA parameters to remove the unexpected outliers from the estimated results. We have implemented a prototype system and evaluated the actual performance in the real complex environment. The experimental results show that 3DLoc achieves the mean accuracy of 10cm in free space and 15.3cm in the multipath environment for the tagged object. I. INTRODUCTION A. Motivation Nowadays, RFID has been widely used in several applications such as warehouse and logistic management. In these applications, each of the items is attached with one or more RFID tags, which illustrate the detailed information of the specified items, e.g., the production/expiration dates, manufacturers, etc. With the assistance of RFID, many novel functions such as indoor localization can be effectively realized. For example, with the exact locations of all items on the shelves, the robotic arm can be used to fetch the specified items in a fully automated manner. However, most state-of-art RFID-based localization schemes, such as PinIt [10] and Tagoram [12], mainly focus on the localization in the 2-dimensional(2D) space, e.g., they usually provide the 2D coordinates of the objects in the indoor maps. These solutions usually fail to locate the items which are arbitrarily stacked in the 3-dimensional(3D) space, as shown in Fig. 1. Therefore, it is essential to propose an RFID-based mechanism to accurately perform 3D localization, so that the 3D coordinates of the objects can be figured out in the 3D space. B. Proposed Approach In this paper, we propose 3DLoc, which performs 3D localization on the tagged objects by using the RFID tag arrays. The basic idea is as follows: Without loss of generality, we assume that the tagged object is a cuboid with six surfaces, e.g., an express package or a cardboard box. For each of the specified objects, three arrays of RFID tags are attached onto three mutually orthogonal surfaces of the object in advance. X Y Object location Z ሺݔǡ ݕǡ ݖሻ Target tag array Object orientation Tag O Fig. 1. Illustration of 3DLoc When performing the 3D localization, the RFID antenna continuously moves and scans the tagged objects in a 2D space right in front of the tagged objects. Specifically, the RFID antenna first moves along the Z axis and scans all tags to estimate the Z-coordinate of each tag from the tag array, 3DLoc then estimates the rough orientation of the object and selects a target tag array for further localization in the XY plane. After that, the RFID antenna moves along the X axis and scans the tags in the target tag array. As it obtains the phase values from the tag arrays, it estimates the object’s orientation and figures out the object’s 3D coordinates in the 3D space, by leveraging the Angle of Arrival(AoA)-based localization schemes. For the layout of the tag array, each tag’s ID and relative position are known in advance to support the 3D localization. C. Challenges and Solutions There are two technical challenges in realizing 3D localization for the tagged objects. First, the 3D localization results can be severely impacted by interferences such as the multipath effect from the indoor environment. Due to the continuously changing factors in the multipath effect, it distorts the phase values of tags in a very unpredictable approach, thus it could further lead to errors in the AoAbased localization. To address this challenge, we perform mobile scanning to continuously sample the phases of the specified tags at different positions, compute the spatial angles of arrival of the tags in different locations, and suppress the outliers caused by the multipath effect. By using the mobile scanning-based scheme, 3DLoc investigates and uses the linear relationship of the AoA parameters to remove the unexpected outliers from the estimated results via continuous sampling, so it is robust to the interferences including ambient noises and the multipath effect. Second, the orientation of the tagged objects is essential to be firstly determined before performing accurate 3D localiza-
tion for the tagged objects.However,according to the phase Meanwhile,in the indoor environment,the wireless signals values from one tag array,it is usually difficult to completely suffer from multipath propagations which will distort the determine the exact orientation of the tagged objects,as there phase values and lead to errors in the localization results. exist multiple possibilities of the orientation state in the 3D Many researches have focused on suppressing the negative space.To address this challenge,we attach three tag arrays to impacts caused by the multipath [10,13].PinIt [10]deploys three mutually orthogonal surfaces of the object,respectively. many reference tags in advance and exploits the similar By comparing the AoA parameters from multiple tag arrays,multipath profiles of the nearby RFIDs which experience a 3DLoc is able to accurately estimate the orientation of the similar multipath environment to pinpoint a tag's location. tagged object.We then select a target tag array vertically MobiTagbot [13]leverages the changing carrier frequency of deployed on the vertical plane,and further figure out the 3D the RFID query to detect whether the phase value is obtained position of the specified object. in severe multipath location,and only uses the phases obtained D.Contributions in low multipath locations for further localization.Similar to To the best of our knowledge,this is the first work to MobiTagbot,3DLoc uses the linear relationship of the AoA consider 3D-localization of tagged objects by using the RFID parameters to find and remove the unexpected outliers which tag arrays.We make three contributions in this paper.1)To result from multipath effect.What's more,instead of localizing perform accurate 3D localization for the tagged objects,we each tag respectively as prior solutions,3DLoc views the tags deploy tag arrays on three mutually orthogonal surfaces of the in the tag array as a whole,and designs a novel algorithm to object.By referring to the fixed layout of the tag array,we calibrate each tag's position referring to the fixed layout of the use the AoA-based schemes to accurately estimate the tagged tag array and finally estimate the location and orientation of object's orientation and 3D coordinates in the 3D space.2)To the tagged object. suppress the localization errors caused by the multipath effect, we propose a mobile scanning-based scheme and use the linear III.MODELING THE 3D LOCALIZATION relationship of the AoA parameters to remove the unexpected A.AoA-based Localization outliers from the estimated results via continuous sampling. The phase value is a common metric in the RFID local- 3)We have implemented a prototype system with the COTS ization system.It reflects the phase rotation between the tag's RFID system,and evaluated the actual performance in the backscattered signal and the signal sent by the antenna.Let d real complex environment.The experimental results show that be the distance between the tag and the reader antenna,then 3DLoc achieves the mean accuracy of 10cm in the free space the backscattered signal traverse a round trip of 2d.Besides and 15.3cm in the multipath environment for the tagged object. the phase rotation over distance,the antenna's transceiver and II.RELATED WORK the tag's reflection characteristic will also introduce additional phase rotations,denoted as A and or,respectively.Hence, Many approaches have been proposed in RFID localization the total phase rotation can be expressed as: system.RSSI information is widely used for localization [1-5],but it is limited for accurate absolute localization 2d 2不 +A+OT mod 2m since RSSI-based approaches are not sensitive enough to (1) distance change.Different from RSSI,the tag's phase value is distance sensitive:the phase difference obtained at two In an RF localizing system,phases obtained at different antenna positions reflects different distances from the tag to the positions are related to the tag's angles of arrival for the corresponding antenna position.Current RF-based localization antenna at different positions.As illustrated in Fig.2,the solutions have great interest in using the phase values to locate antenna interrogates a tag at two different positions x and the tagged objects,and they mainly fall into distance-based x2,with phase readings o and 2.The distances from the methods [6-8].AoA-based methods [9-11],and holography- tag to i and x2 are di and d2,and Ax is the distance of based methods [12,13].For example,BackPos [7]infers 12.According to Eq.1,for the same tag and the same the distance difference from the phases detected by antennas. antenna,and 2 share the same A and or,thus the phase and uses a hyperbolic-based method for localization.RF. difference Ad1.2=1-2 is related to the distance difference IDraw [11]leverages the phase differences as well,but it △d1,2=d1-d2,as: uses an AoA-based method to reconstruct the gestures of a user.Tagoram [12]uses the holography-based method to △p1,2=2m· 2△d2+2kT (2) calculate the possibility of each point being the RF source in the 2D surveillance plane and selects the most likely position where k is an integer which ensures that Ad12 is within the as the tag's location.These above solutions only address the range [0,2].As can be seen from Fig.2,when the tag is 2D localization problem,but fail to provide 3D coordinates relatively far from the antenna,△di,2≈△x·cos9,where 6 of the objects.3DLoc creatively proposes a 3D localization is the angle of arrival of the tag at z(the midpoint of 2). approach:it estimates the rough orientation of the object first, Combined with Eq.2,cos can be expressed as: then calculates the location of the object from the phases of 入（△p1.2-2kπ） the tags in the target tag array. 4π△x
tion for the tagged objects. However, according to the phase values from one tag array, it is usually difficult to completely determine the exact orientation of the tagged objects, as there exist multiple possibilities of the orientation state in the 3D space. To address this challenge, we attach three tag arrays to three mutually orthogonal surfaces of the object, respectively. By comparing the AoA parameters from multiple tag arrays, 3DLoc is able to accurately estimate the orientation of the tagged object. We then select a target tag array vertically deployed on the vertical plane, and further figure out the 3D position of the specified object. D. Contributions To the best of our knowledge, this is the first work to consider 3D-localization of tagged objects by using the RFID tag arrays. We make three contributions in this paper. 1) To perform accurate 3D localization for the tagged objects, we deploy tag arrays on three mutually orthogonal surfaces of the object. By referring to the fixed layout of the tag array, we use the AoA-based schemes to accurately estimate the tagged object’s orientation and 3D coordinates in the 3D space. 2) To suppress the localization errors caused by the multipath effect, we propose a mobile scanning-based scheme and use the linear relationship of the AoA parameters to remove the unexpected outliers from the estimated results via continuous sampling. 3) We have implemented a prototype system with the COTS RFID system, and evaluated the actual performance in the real complex environment. The experimental results show that 3DLoc achieves the mean accuracy of 10cm in the free space and 15.3cm in the multipath environment for the tagged object. II. RELATED WORK Many approaches have been proposed in RFID localization system. RSSI information is widely used for localization [1–5], but it is limited for accurate absolute localization since RSSI-based approaches are not sensitive enough to distance change. Different from RSSI, the tag’s phase value is distance sensitive: the phase difference obtained at two antenna positions reflects different distances from the tag to the corresponding antenna position. Current RF-based localization solutions have great interest in using the phase values to locate the tagged objects, and they mainly fall into distance-based methods [6–8], AoA-based methods [9–11], and holographybased methods [12, 13]. For example, BackPos [7] infers the distance difference from the phases detected by antennas, and uses a hyperbolic-based method for localization. RFIDraw [11] leverages the phase differences as well, but it uses an AoA-based method to reconstruct the gestures of a user. Tagoram [12] uses the holography-based method to calculate the possibility of each point being the RF source in the 2D surveillance plane and selects the most likely position as the tag’s location. These above solutions only address the 2D localization problem, but fail to provide 3D coordinates of the objects. 3DLoc creatively proposes a 3D localization approach: it estimates the rough orientation of the object first, then calculates the location of the object from the phases of the tags in the target tag array. Meanwhile, in the indoor environment, the wireless signals suffer from multipath propagations which will distort the phase values and lead to errors in the localization results. Many researches have focused on suppressing the negative impacts caused by the multipath [10, 13]. PinIt [10] deploys many reference tags in advance and exploits the similar multipath profiles of the nearby RFIDs which experience a similar multipath environment to pinpoint a tag’s location. MobiTagbot [13] leverages the changing carrier frequency of the RFID query to detect whether the phase value is obtained in severe multipath location, and only uses the phases obtained in low multipath locations for further localization. Similar to MobiTagbot, 3DLoc uses the linear relationship of the AoA parameters to find and remove the unexpected outliers which result from multipath effect. What’s more, instead of localizing each tag respectively as prior solutions, 3DLoc views the tags in the tag array as a whole, and designs a novel algorithm to calibrate each tag’s position referring to the fixed layout of the tag array and finally estimate the location and orientation of the tagged object. III. MODELING THE 3D LOCALIZATION A. AoA-based Localization The phase value is a common metric in the RFID localization system. It reflects the phase rotation between the tag’s backscattered signal and the signal sent by the antenna. Let d be the distance between the tag and the reader antenna, then the backscattered signal traverse a round trip of 2d. Besides the phase rotation over distance, the antenna’s transceiver and the tag’s reflection characteristic will also introduce additional phase rotations, denoted as ϕA and ϕT , respectively. Hence, the total phase rotation ϕ can be expressed as: ϕ = ( 2π · 2d λ + ϕA + ϕT ) mod 2π (1) In an RF localizing system, phases obtained at different positions are related to the tag’s angles of arrival for the antenna at different positions. As illustrated in Fig.2, the antenna interrogates a tag at two different positions x1 and x2, with phase readings ϕ1 and ϕ2. The distances from the tag to x1 and x2 are d1 and d2, and ∆x is the distance of |x1x2|. According to Eq.1, for the same tag and the same antenna, ϕ1 and ϕ2 share the same ϕA and ϕT , thus the phase difference ∆ϕ1,2 = ϕ1−ϕ2 is related to the distance difference ∆d1,2 = d1 − d2, as: ∆ϕ1,2 = 2π · 2∆d1,2 λ + 2kπ (2) where k is an integer which ensures that ∆ϕ1,2 is within the range [0, 2π]. As can be seen from Fig.2, when the tag is relatively far from the antenna, ∆d1,2 ≈ ∆x · cos θ, where θ is the angle of arrival of the tag at x (the midpoint of x1x2). Combined with Eq.2, cos θ can be expressed as: cos θ = λ (∆ϕ1,2 − 2kπ) 4π∆x
Z Tag (xo,yo,Zo) d △d1,2≈△xcos d, do 810 100 X -Theory line X1X X2 -Theory line Xo ·Measured value ·Measured value Y △x -12 -0.6 0 0.6 12 -12 -0.6 0 0.6 X(m) X(m) Fig.2.The angle of arrival of the tag (a)Free space (b)Severe multipath If we set Az to be no greater than A/4,then k must equal Fig.3. Comparisons of cot in two cases 0 to ensure -1 cos 1,hence 0 is unique.Therefore, we can get the angle of arrival of the tag at position x as be estimated relying on the linear relationship of the AoA follows: parameters in R as described in Theorem 1. 入·△1,2 Theorem 1:Let the antenna's linear moving trajectory be 0=arccos 4π△x the X axis and 0 be the angle of arrival of the tag at position (3) x1+E2 z,then cot and x and have the following linear relationship: T= 2 1 cot=- (x-x0) (4) In conclusion,based on two phase readings obtained by the do antenna at different positions,we can calculate the angle of where do is the vertical distance from the tag to the X axis arrival of the tag at the corresponding position. and zo is the X-coordinate of the tag. B.AoA Localization via Mobile Scanning Proof:As illustrated in Fig.2,according to the triangle Due to ambient noises and the multipath effect from the en- relationship,we have: vironment,the phase values of the tag will be distorted,which will lead to errors in the AoA-based localization.Therefore, x0-x=d0·cot0 we perform mobile scanning to continuously obtain the phases from which we can easily infer Eq.4.Then the slope of the of the tag at different positions,from which we can calculate the spatial angle of arrival of the tag when the antenna is at line equals-1/do,and zo equals the X-intercept of the line, because at position ro,8 equalsπ/2，then cot9=0.■ different positions and use the linear relationship of the AoA parameters to estimate the location of the tag.In the 3D space, Therefore,with the angle of arrival result set R,we replace 0 with cot,then the transformed result set is we assume that the antenna moves at a constant speed v along a certain line.Without loss of generality,suppose the X axis P={(io,coto）,…,(立m,cot Om),and the points in is along the antenna's moving trajectory.Then,the position of P should form a line as described in Eg.4.To validate the the antenna z(t)at time t can be inferred by: above theorem,we conduct empirical studies using a COTS RFID platform in both free space and the severe multipath x(t)=x(to)+v.(t-to) environment.The antenna is programmed to move at a con- where to is the start time and x(to)is the initial position stant speed of 15cm/s along a linear trajectory,and the tag's of the antenna.Let x {z(to),z(t1),...,x(tn)}be vertical distance to the trajectory is 1.2m.We plot the x-cot diagram along with the theory line calculated by Eg.4 in Fig.3. the antenna's positions at different interrogated time,where x(ti)is the ith antenna's position at interrogated time 1)Free space:As shown in Fig.3(a),all points fit well with ti.We define (ti)as the phase value from the antenna the theory line.Specifically,we can use the linear least squares to find a fitting line for the calculated points to estimate do at x(ti),so the phase measurements can be denoted as =o(to),(t),...,(n)}.Recall that based on two and zo based on Eq.4. phase readings at different positions,the spatial angle of arrival 2)Multipath environment:In the severe multipath scenario, as shown in Fig.3(b).we make the following observation: of the tag can be calculated.So,we can choose phase tuples from for the estimation of angles of arrival,denoted as T= Observation 1 There are many outliers away from the theory line and the occurrence of them is continuous. {(p(to),p(tk)》,(p(t1),p(tk)》,…,(p(tm),p(tkm)》}. Intuitively,for the outliers,we can infer that errors exist For each tuple(p(t),p(tk)》,0≤i<k≤n,and the distance Ar;between two antenna locations x(ti)and x(tk) in their angles of arrival results.Since the angle of arrival should meet the following condition: of the tag is calculated from the phase values of the tag, in a multipath environment,the backscattered signal from △x=x(tk)-x(t)≤λ/4 the tag will bounce off objects like walls and the ground, thus the phase readings are not only related to the signal Based on each tuple in T.we can calculate the angle of that propagates along the direct path,but also related to the arrival of the tag when the antenna is at different position-unpredictable signals that reflect from other objects.Recall that s according to Eq.3,the results can be denoted as R based on the phase tuple ((ti),()),we can compute the .Then the location of the tag can tag's spatial angle of arrivaland corresponding coordinates
ߠ ଶݔ ݔଵݔ Tag ሺݔǡ ݕǡ ݖሻ ݀ଶ ݀ଵ ߠ ڄ ݔȟ ൎ ଵǡଶ݀ȟ ݔȟ X Y Z ݔ ݀ O Fig. 2. The angle of arrival of the tag If we set ∆x to be no greater than λ/4, then k must equal 0 to ensure −1 ≤ cos θ ≤ 1, hence θ is unique. Therefore, we can get the angle of arrival θ of the tag at position x as follows: θ = arccos ( λ · ∆ϕ1,2 4π∆x ) x = x1 + x2 2 (3) In conclusion, based on two phase readings obtained by the antenna at different positions, we can calculate the angle of arrival of the tag at the corresponding position. B. AoA Localization via Mobile Scanning Due to ambient noises and the multipath effect from the environment, the phase values of the tag will be distorted, which will lead to errors in the AoA-based localization. Therefore, we perform mobile scanning to continuously obtain the phases of the tag at different positions, from which we can calculate the spatial angle of arrival of the tag when the antenna is at different positions and use the linear relationship of the AoA parameters to estimate the location of the tag. In the 3D space, we assume that the antenna moves at a constant speed v along a certain line. Without loss of generality, suppose the X axis is along the antenna’s moving trajectory. Then, the position of the antenna x (t) at time t can be inferred by: x (t) = x (t0) + v · (t − t0) where t0 is the start time and x (t0) is the initial position of the antenna. Let X = {x (t0), x (t1), · · · , x (tn)} be the antenna’s positions at different interrogated time, where x (ti) is the i th antenna’s position at interrogated time ti . We define ϕ (ti) as the phase value from the antenna at x (ti), so the phase measurements can be denoted as Φ = {ϕ (t0), ϕ (t1), · · · , ϕ (tn)}. Recall that based on two phase readings at different positions, the spatial angle of arrival of the tag can be calculated. So, we can choose phase tuples from Φ for the estimation of angles of arrival, denoted as T = {⟨ϕ (t0), ϕ (tk0 )⟩,⟨ϕ (t1), ϕ (tk1 )⟩, · · · ,⟨ϕ (tm), ϕ (tkm)⟩}. For each tuple ⟨ϕ (ti), ϕ (tki )⟩, 0 ≤ i < ki ≤ n, and the distance ∆xi between two antenna locations x (ti) and x (tki ) should meet the following condition: ∆xi = x (tki ) − x (ti) ≤ λ/4 Based on each tuple in T, we can calculate the angle of arrival of the tag when the antenna is at different positions according to Eq.3, the results can be denoted as {( R = x˜0, ˜θ0 ) , · · · , ( x˜m, ˜θm )}. Then the location of the tag can −1.2 −0.6 0 0.6 1.2 −4 −2 0 2 X(m) cot θ Theory line Measured value (a) Free space −1.2 −0.6 0 0.6 1.2 −4 −2 0 2 X(m) cot θ Theory line Measured value (b) Severe multipath Fig. 3. Comparisons of ( x˜i, cot θ˜ i ) in two cases be estimated relying on the linear relationship of the AoA parameters in R as described in Theorem 1. Theorem 1: Let the antenna’s linear moving trajectory be the X axis and θ be the angle of arrival of the tag at position x, then cot θ and x and have the following linear relationship: cot θ = − 1 d0 (x − x0) (4) where d0 is the vertical distance from the tag to the X axis and x0 is the X-coordinate of the tag. Proof: As illustrated in Fig.2, according to the triangle relationship, we have: x0 − x = d0 · cot θ from which we can easily infer Eq.4. Then the slope of the line equals −1/d0, and x0 equals the X-intercept of the line, because at position x0, θ equals π/2, then cot θ = 0. Therefore, with the angle of arrival result set R, we replace θ with cot θ, then the transformed result set is P = {(x˜0, cot ˜θ0 ) , · · · , ( x˜m, cot ˜θm )}, and the points in P should form a line as described in Eq.4. To validate the above theorem, we conduct empirical studies using a COTS RFID platform in both free space and the severe multipath environment. The antenna is programmed to move at a constant speed of 15cm/s along a linear trajectory, and the tag’s vertical distance to the trajectory is 1.2m. We plot the x−cot θ diagram along with the theory line calculated by Eq.4 in Fig.3. 1) Free space: As shown in Fig.3(a), all points fit well with the theory line. Specifically, we can use the linear least squares to find a fitting line for the calculated points to estimate d0 and x0 based on Eq.4. 2) Multipath environment: In the severe multipath scenario, as shown in Fig.3(b), we make the following observation: Observation 1 There are many outliers away from the theory line and the occurrence of them is continuous. Intuitively, for the outliers, we can infer that errors exist in their angles of arrival results. Since the angle of arrival of the tag is calculated from the phase values of the tag, in a multipath environment, the backscattered signal from the tag will bounce off objects like walls and the ground, thus the phase readings are not only related to the signal that propagates along the direct path, but also related to the unpredictable signals that reflect from other objects. Recall that based on the phase tuple ⟨ϕ (ti), ϕ (tki )⟩, we can compute the tag’s spatial angle of arrival ˜θi and corresponding coordinates
Maximum Minimum Z-coordinate Z-coordinate Array 3 Array 2 Array 2 Tag array center (xc,ye) Array I 2 Rotation angle..◆ Array I -X Array 3 0 -X (a)Flip state 1 (b)Flip state 2 Fig.5.Rotation angle of the tagged object:It is defined as the angle between Fig.4.Flip of the object Xaxis and the vector which points from the 1st tag to then tag in the target tag array in the antenna's trajectory,denoted as ()If both Y (ti)and (t)are obtained in the free space,the point B=a cotshould be on the theory line according to Theorem T4 1.However,if either one of the phase readings suffers from (xc,yc) Ti a severe multipath,the accuracy of will be impacted,so the d point (cot will be far away from the line and can be (xe,ye) B=π- considered as an outlier.Also,the occurrence of the outliers 0 is continuous.This is because if we find that one certain a)0≤a< (b)5≤a<T antenna's position suffers from the severe multipath,then the nearby positions can be inferred to be affected by multipath T B=2π-a effect at different extents. C.Tag Array-based Localization d To localize the tags on the object,the orientation of the (Xc,yc) (xc,yc) tagged objects needs to be firstly determined so as to perform the accurate 3D localization for the tagged objects.However, B=-π X O it is not enough to use a single tag to perform accurate localization as there exist multiple possible orientation states ⊙r≤a<罗 (d要≤a<2m for the object in the 3D space.Thus we deploy RFID tag arrays Fig.6.Four cases for the rotation angle on the three mutually orthogonal surfaces of the object and practice,we move the antenna along the Z axis to estimate the three tag arrays are along mutually orthogonal directions. the Z-coordinates of all the tags in the three tag arrays.By First,we specify a 3D coordinate system for the antenna:the comparing the Z-coordinate of each tag array,we can infer X axis is along the antenna's moving direction and the X-Y how the object flips and distinguish the three tag arrays on the plane is parallel to the ground.Specifically,we use two kinds different surfaces. of motions to describe the orientation of the tagged object in 2)Rotation angle:To estimate the rotation angle of the the 3D space.First,the object turns over in the 3D space, object,we can project the rotation of the object onto the X-Y resulting in different surfaces touching the ground.We define plane.Taking Fig.4(a)for example,the tags in Array 2 have this kind of motion as a flip.Second,the object rotates along the same X-coordinate and Y-coordinate and their projections the Z axis. become a same point in the X-Y plane,thus it is infeasible 1)Flip State:Fig.4 shows two flip states of a tagged object.to use Array 2 to estimate the rotation angle.Both Array 1 The surface deployed Array 1 faces towards us in Fig.4(a),and Array 2 can be used for rotation angle estimation and in when the object flips,it is on the ground(Fig.4(b)).Different this paper,we choose the tag array in which each tag is along flip states result in different layouts for the three tag arrays.the Z axis(Array 1 in Fig 4(a))as the target tag array for No matter how the object flips,there always exists a certain the rotation angle estimation and further localization in the tag array which is on the top/bottom surface of the object.X-Y plane.Suppose the target tag array is composed of n Therefore,the flip state of the object can be inferred with the tags,and for brevity,we consider the distance between two tag array which is on the top/bottom surface. adjacent tags to be the same,termed as d. Notice that the Z-coordinates of the tags in the three As illustrated in Fig.5,the rotation of the object and the tag arrays have different characteristics.The tags in the tag target tag array are projected onto the X-Y plane.We define array which is on the top/bottom surface (i.e.Array 3 in the rotation angle of the object as the angle between theX Fig.4(a))have the same Z-coordinate value and the value is axis and the vector which points from the 1st tag to the nth the maximum/minimum.For the other two tag arrays which tag.Let (c,yc)be the coordinates of the tag array's center are on the two vertical surfaces,the directions of the tags inin the X-Y plane and a be the rotation angle of the object, the two tag arrays are different.For the tag array in which where a is in the range [0,2].Obviously,(,yc)and o can each tag is along the Z axis(i.e.Array 1 in Fig.4(a)),the tags uniquely determine the target tag array's position in the X-Y also have the same Z-coordinate.For the last tag array (i.e.plane. Array 2 in Fig.4(a)),the tags have different 2-coordinates.In The relative position of the tags in the target tag array
Array 1 Array 3 X Y Z α Maximum Z-coordinate Array 2 O (a) Flip state 1 Array 1 Array 2 α Minimum Z-coordinate X Array 3 Y Z O (b) Flip state 2 Fig. 4. Flip of the object x˜i in the antenna’s trajectory, denoted as ( x˜i , ˜θi ) . If both ϕ (ti) and ϕ (tki ( ) are obtained in the free space, the point x˜i , cot ˜θi ) should be on the theory line according to Theorem 1. However, if either one of the phase readings suffers from severe multipath, the accuracy of ˜θi will be impacted, so the point ( x˜i , cot ˜θi ) will be far away from the line and can be considered as an outlier. Also, the occurrence of the outliers is continuous. This is because if we find that one certain antenna’s position suffers from the severe multipath, then the nearby positions can be inferred to be affected by multipath effect at different extents. C. Tag Array-based Localization To localize the tags on the object, the orientation of the tagged objects needs to be firstly determined so as to perform the accurate 3D localization for the tagged objects. However, it is not enough to use a single tag to perform accurate localization as there exist multiple possible orientation states for the object in the 3D space. Thus we deploy RFID tag arrays on the three mutually orthogonal surfaces of the object and the three tag arrays are along mutually orthogonal directions. First, we specify a 3D coordinate system for the antenna: the X axis is along the antenna’s moving direction and the X-Y plane is parallel to the ground. Specifically, we use two kinds of motions to describe the orientation of the tagged object in the 3D space. First, the object turns over in the 3D space, resulting in different surfaces touching the ground. We define this kind of motion as a flip. Second, the object rotates along the Z axis. 1) Flip State: Fig.4 shows two flip states of a tagged object. The surface deployed Array 1 faces towards us in Fig.4(a), when the object flips, it is on the ground (Fig.4(b)). Different flip states result in different layouts for the three tag arrays. No matter how the object flips, there always exists a certain tag array which is on the top/bottom surface of the object. Therefore, the flip state of the object can be inferred with the tag array which is on the top/bottom surface. Notice that the Z-coordinates of the tags in the three tag arrays have different characteristics. The tags in the tag array which is on the top/bottom surface (i.e. Array 3 in Fig.4(a)) have the same Z-coordinate value and the value is the maximum/minimum. For the other two tag arrays which are on the two vertical surfaces, the directions of the tags in the two tag arrays are different. For the tag array in which each tag is along the Z axis (i.e. Array 1 in Fig.4(a)), the tags also have the same Z-coordinate. For the last tag array (i.e. Array 2 in Fig.4(a)), the tags have different Z-coordinates. In Rotation angle ߙ Tag array center ሺݔ ሻݕ , ܶଵ X Y O ܶ ߚ ݀ Fig. 5. Rotation angle of the tagged object: It is defined as the angle between X axis and the vector which points from the 1 st tag to the n th tag in the target tag array ߙ ߚ ݀ ݔሺ ሻݕ , ߙ ൌ ߚ O X ܶଵ ܶସ Y (a) 0 ≤ α < π 2 ߙ ߚ ݀ ݔሺ ሻݕ , ߙ െ ߨ ൌ ߚ X ܶଵ ܶସ Y O (b) π 2 ≤ α < π ߙ ߚ ݀ ݔሺ ሻݕ , X Y ܶସ ܶଵ ߨ െ ߙ ൌ ߚ O (c) π ≤ α < 3π 2 ߙ ߚ ݀ ݔሺ ሻݕ , X ܶସ ܶଵ Y ߙ െ ߨʹ ൌ ߚ O (d) 3π 2 ≤ α < 2π Fig. 6. Four cases for the rotation angle practice, we move the antenna along the Z axis to estimate the Z-coordinates of all the tags in the three tag arrays. By comparing the Z-coordinate of each tag array, we can infer how the object flips and distinguish the three tag arrays on the different surfaces. 2) Rotation angle: To estimate the rotation angle of the object, we can project the rotation of the object onto the X-Y plane. Taking Fig.4(a) for example, the tags in Array 2 have the same X-coordinate and Y -coordinate and their projections become a same point in the X-Y plane, thus it is infeasible to use Array 2 to estimate the rotation angle. Both Array 1 and Array 2 can be used for rotation angle estimation and in this paper, we choose the tag array in which each tag is along the Z axis(Array 1 in Fig 4(a)) as the target tag array for the rotation angle estimation and further localization in the X-Y plane. Suppose the target tag array is composed of n tags, and for brevity, we consider the distance between two adjacent tags to be the same, termed as d. As illustrated in Fig.5, the rotation of the object and the target tag array are projected onto the X-Y plane. We define the rotation angle of the object as the angle between the X axis and the vector which points from the 1 st tag to the n th tag. Let (xc, yc) be the coordinates of the tag array’s center in the X-Y plane and α be the rotation angle of the object, where α is in the range [0, 2π]. Obviously, (xc, yc) and α can uniquely determine the target tag array’s position in the X-Y plane. The relative position of the tags in the target tag array
Localization Calibration B.Localization for each tag for each tag by tag arrays 1)AoA Localization via Mobile Scanning:To perform 3D AOA Localization Orientation localization for the object,we move the antenna in a 2D space RF phas Estimation Mobile Scanning along two different axes.Without loss of generality,we will Target Tag Array 3D location Localization discuss our approach assuming that the antenna moves along Multipath Object the X axis.As aforementioned,when the antenna interrogates Suppression Localization the tag at different positions along the X axis,we can calculate the tag's angles of arrival in different locations and denote Fig.7. System architecture the results as R)According to changes as the object rotates.Taking the four-tag linear array Theorem 1,x and cot are of a linear relationship,and the for example,as illustrated in Fig.6,we divide a in four cases. line can be described as a function of zo and do according to For each case,the four tags in the tag array have different Eq.4 as: relative positions in the X and Y axes.Once we identify which cot0=-1(x-zo) case a belongs to,the relative layout of the four tags in the do X and Y axis is uniquely determined.Then,the coordinates of the four tags can be expressed as a function of e,ye and where do is the vertical distance from the tag to the X axis a,i.e.in Fig..6(b),π/2≤a<π，and for T,we have: and zo is the X coordinate of the tag.Hence with the point setP=了 o coto)m co),we adopt the T1=Te+ -d cos B linear least squares in order to find a fitting line that best fits all these points to estimate do and zo,The objective function 3 h=-2 -dsin B is formalized as follows: B=π-a arg mir (6 do,ro More generally,for the ith tag in the n-tag tag array,its coordinates (i,can be expressed as: Subject to: xi=xc+pPi·dcosB P={(o,coto)…,(在m,cot)} yi=yc+qi·dsin B (5) B=f(a) 2)Multipath Suppression:In the multipath environ- ment, according to Observation 1,there exist contin- where lpi and gil are related to the number of tags in the uous occurrences of outliers in the point set P target tag array,and f(a)is determined by the case that a o;coto(m cotm.Obviously,the outliers belongs to as shown in Fig.6.Thus,(e,yc)and a can be will definitely influence the result of the fitting line for the estimated by each tag's coordinate (ri,yi).In practice,we point set P,thus the accuracies of do and o will be degraded. move the antenna along the X axis to calculate the coordinates So,the basic idea of our multipath suppression algorithm of all the tags in the target tag array,then calibrate the is to find and remove the outliers from the point set P. calculated results of each tag to localize the target tag array As shown in Fig.8,since the occurrence of the outliers is and compute the rotation angle of the object. continuous,we use a slide window to split the point set P into k subsets:Sp=[Sp,..,Sp},where Sp is ith subset IV.SYSTEM DESIGN from P,and the window size is a predefined value w.We A.System Overview denote the ground truth line for P as 1.Intuitively,if Sp 3DLoc is a 3D localization system for the tagged object does not contain continuous occurrence of the outliers,cot using tag arrays,as illustrated in Fig.7,it involves two main will change linearly with and the average changing rate of components. the points in Sp can be regarded as the scope of l.On the 1)Localization for each tag:We move the RFID antenna in contrary,if the outliers continuously occur in Sp,cot will a 2-dimensional space continuously to interrogate all the tags change irregularly with x and its average changing rate cannot on the tagged object and localize each tag using an Angle of be considered as the scope of l. Arrival(AoA)-based scheme.To weaken the negative impact How can we evaluate the changing rate for each subset? of multipath,we adopt a multipath suppression algorithm to In practice,for each subset Sp in Sp,we use the linear optimize the localization results. least squares to find a fitting line li for all the points in 2)Calibration by tag array:We consider all the tags in Sp.Let ai be the scope of li,then ai can be considered the tag array as whole and by referring to the fixed layout of as the average changing rate for the points in Sp.Finally the tag array,the location of each tag can be calibrated and we will get a changing rate set A =fa1,...,ak}for k we can calculate the object's 3D location.Specifically,we first subsets in Sp.In theory,except for those subsets which contain estimate the object's rough orientation and then select a target continuous occurrences of outliers,the other changing rate tag array for further localization of the object. values in A should be close to the scope of l.Based on the
AOA Localization via Mobile Scanning Multipath Suppression Localization for each tag Calibration by tag arrays 3D location RF phase Orientation Estimation Target Tag Array Localization Object Localization Fig. 7. System architecture changes as the object rotates. Taking the four-tag linear array for example, as illustrated in Fig.6, we divide α in four cases. For each case, the four tags in the tag array have different relative positions in the X and Y axes. Once we identify which case α belongs to, the relative layout of the four tags in the X and Y axis is uniquely determined. Then, the coordinates of the four tags can be expressed as a function of xc, yc and α, i.e. in Fig.6(b), π/2 ≤ α < π, and for T1, we have: x1 = xc + 3 2 d cos β y1 = yc − 3 2 d sin β β = π − α More generally, for the i th tag in the n-tag tag array, its coordinates (xi , yi) can be expressed as: xi = xc + pi · d cos β yi = yc + qi · d sin β β = f (α) (5) where |pi | and |qi | are related to the number of tags in the target tag array, and f (α) is determined by the case that α belongs to as shown in Fig.6. Thus, (xc, yc) and α can be estimated by each tag’s coordinate (xi , yi). In practice, we move the antenna along the X axis to calculate the coordinates of all the tags in the target tag array, then calibrate the calculated results of each tag to localize the target tag array and compute the rotation angle of the object. IV. SYSTEM DESIGN A. System Overview 3DLoc is a 3D localization system for the tagged object using tag arrays, as illustrated in Fig.7, it involves two main components. 1) Localization for each tag: We move the RFID antenna in a 2-dimensional space continuously to interrogate all the tags on the tagged object and localize each tag using an Angle of Arrival(AoA)-based scheme. To weaken the negative impact of multipath, we adopt a multipath suppression algorithm to optimize the localization results. 2) Calibration by tag array: We consider all the tags in the tag array as whole and by referring to the fixed layout of the tag array, the location of each tag can be calibrated and we can calculate the object’s 3D location. Specifically, we first estimate the object’s rough orientation and then select a target tag array for further localization of the object. B. Localization for each tag 1) AoA Localization via Mobile Scanning: To perform 3D localization for the object, we move the antenna in a 2D space along two different axes. Without loss of generality, we will discuss our approach assuming that the antenna moves along the X axis. As aforementioned, when the antenna interrogates the tag at different positions along the X axis, we can calculate the tag’s angles of arrival in different locations and denote the results as R = {(x˜0, ˜θ0 ) , · · · , ( x˜m, ˜θm )}. According to Theorem 1, x and cot θ are of a linear relationship, and the line can be described as a function of x0 and d0 according to Eq.4 as: cot θ = − 1 d0 (x − x0) where d0 is the vertical distance from the tag to the X axis and x0 is the X coordinate of the tag. Hence with the point set P = {(x˜0, cot ˜θ0 ) , · · · , ( x˜m, cot ˜θm )} , we adopt the linear least squares in order to find a fitting line that best fits all these points to estimate d0 and x0, The objective function is formalized as follows: arg min d0,x0 ∑m i=0 ( − 1 d0 · ( ˜xi − x0) ) − cot ˜θi 2 (6) Subject to: P = {(x˜0, cot ˜θ0 ) , · · · , ( x˜m, cot ˜θm )} 2) Multipath Suppression: In the multipath environment, according to Observation 1, there exist continuous occurrences of outliers in the point set {( P = x˜0, cot ˜θ0 ) , · · · , ( x˜m, cot ˜θm )}. Obviously, the outliers will definitely influence the result of the fitting line for the point set P, thus the accuracies of d0 and x0 will be degraded. So, the basic idea of our multipath suppression algorithm is to find and remove the outliers from the point set P. As shown in Fig.8, since the occurrence of the outliers is continuous, we use a slide window to split the point set P into k subsets: SP = {SP1 , · · · , SPk }, where SPi is i th subset from P, and the window size is a predefined value w. We denote the ground truth line for P as l. Intuitively, if SPi does not contain continuous occurrence of the outliers, cot θ will change linearly with x and the average changing rate of the points in SPi can be regarded as the scope of l. On the contrary, if the outliers continuously occur in SPi , cot θ will change irregularly with x and its average changing rate cannot be considered as the scope of l. How can we evaluate the changing rate for each subset? In practice, for each subset SPi in SP , we use the linear least squares to find a fitting line li for all the points in SPi . Let ai be the scope of li , then ai can be considered as the average changing rate for the points in SPi . Finally we will get a changing rate set A = {a1, · · · , ak} for k subsets in SP . In theory, except for those subsets which contain continuous occurrences of outliers, the other changing rate values in A should be close to the scope of l. Based on the
cot Algorithm 2:Calibration by tag arrays 1 Orientation Estimation: 2 The antenna moves along the Z axis to estimate the Z-coordinates of the all the tags; 3 Distinguish the three tag arrays on different surfaces; 4 Judge the flip state of the object by finding the tag array which is on the bottom/top surface; Fig.8.Segmentation for the points in P 5 Select the target tag array and calibrate the Z-coordinate of the target tag array according to Eq.7; Algorithm 1:Multipath Suppression 6 Target Tag Array Localization: 7 The antenna moves along the X axis to localize the tags Input:Point set P={(io,cot）,…,(im,cotm in the target tag array in the X-Y plane; Output:New point set P removed the outliers s Calculate the location of the target tag array and estimate 1 Split P into k subset using a slide window: the rotation angle of the object according to Eq.8; Sp={SP1·,SPw}: 9 Object Localization: 2 Changing rate set for the subsets:A =0; 10 Calculate the 3D coordinates of the object based on the 3 Calculation for average changing rate step: location of the target tag array and the rotation angle of 4 for each Sp in Sp do the object according to Eq.9; 5 Calculate a fitting line li for the points in Sp; 11 return 3D coordinates of the object 6 Add the scope ai of li to A: 7A={a1,…,ak: s Outliers finding and removing step: whole algorithm is described in Algorithm 2. 9 Find outliers in A and remove the points in 1)Orientation Estimation:The orientation of the tagged corresponding subsets in Sp; objects must be firstly determined before performing an ac- 10 for each subset which has been removed do curate 3D localization for the tagged objects.First,we need if Sp,and Sp+2 are removed then to distinguish the tag arrays on three mutually orthogonal L Remove SP if it has not been removed; surfaces.Recall that the 2-coordinates of the tags in the three tag arrays have different characteristics.In practice,we 13 return a new point set P first move the antenna along the Z axis to estimate the Z- coordinates of all the tags,then the three tag arrays can be distinguished by comparing the Z-coordinate of each tag in the tag arrays.As illustrated in Fig.9(a),the antenna moves above idea,we only need to find the outliers in A and remove the corresponding subsets in Sp.and the above finding process along the Z axis to calculate the Z-coordinate of the all the can be considered as a one class SVM problem.After the tags.Fig.9(b)shows the localization results.Notice that the Z-coordinates of the tags in Array 1 and Array 2 are equal above step,the subsets which contain continuous occurrences and in Array 3 are different,so we can easily correspond the of outliers are partly removed.We can further remove the other red points in Figure.9(b)to Array 3.Since the tag array on unexpected subsets in Sp using the continuity of the outliers again.That is to say,if the subsets Sp,and Sp+2 are removed, the top/bottom surface has the maximum or the minimum Z- then the subset pshould be removed too.As a result,we coordinate value,so,the green points with the minimum Z- removed the outliers in P for the estimation of do and o.The coordinates in Fig.9(b)correspond to Array 1 and we can also multipath suppression algorithm is shown in Algorithm 1. infer that Array 1 is at the bottom.Finally,the blue points corresponds to Array 2.After the above process,the flip state C.Calibration by tag arrays of the object is figured out.In addition,as mentioned before, After the AoA localization for each tag in the tag array,we the rotation angle of the object can be estimated from the can leverage the fixed layout of the tag array to calibrate the target tag array in which every tag is attached along the Z result of each tag in order to estimate the 3D coordinates and axis and on the vertical surface of the object,so here Array 2 orientation of the object.In general,this part includes three can be chosen as the target tag array. main components:first,we use the calculated Z-coordinates We next optimize the Z-coordinate of the target tag array. of all the tags to infer the rough orientation of the object,from Let ze be the Z-coordinate of the target tag array's center and which we distinguish the three tag arrays on different surfaces be the Z-coordinate for the ith tag calculated through AoA and select a target tag array for further localization in the X- localization.As the Z-coordinate of each tag in the target tag Y plane.Then,we localize the target tag array in the X-Y array is the same,then,ze can be considered as the average plane and estimate the rotation angle of the object.Finally,we Z-coordinate of all the tags in the target tag array: get the 3D coordinates of the object referring to the location n of the target tag array and the rotation angle of the object.The 2e =1名 (7)
ܵభ ܵೖషభ ܵ ܵೖ ܵమ X ߠ Fig. 8. Segmentation for the points in P Algorithm 1: Multipath Suppression Input: Point set P = {(x˜0, cot ˜θ0 ) , · · · , ( x˜m, cot ˜θm )} Output: New point set P ′ removed the outliers 1 Split P into k subset using a slide window: SP = {SP1 , · · · , SPk }; 2 Changing rate set for the subsets: A = ∅; 3 Calculation for average changing rate step: 4 for each SPi in SP do 5 Calculate a fitting line li for the points in SPi ; 6 Add the scope ai of li to A; 7 A = {a1, · · · , ak}; 8 Outliers finding and removing step: 9 Find outliers in A and remove the points in corresponding subsets in SP ; 10 for each subset which has been removed do 11 if SPj and SPj+2 are removed then 12 Remove SPj+1 if it has not been removed; 13 return a new point set P ′ above idea, we only need to find the outliers in A and remove the corresponding subsets in SP , and the above finding process can be considered as a one class SVM problem. After the above step, the subsets which contain continuous occurrences of outliers are partly removed. We can further remove the other unexpected subsets in SP using the continuity of the outliers again. That is to say, if the subsets SPj and SPj+2 are removed, then the subset SPj+1 should be removed too. As a result, we removed the outliers in P for the estimation of d0 and x0. The multipath suppression algorithm is shown in Algorithm 1. C. Calibration by tag arrays After the AoA localization for each tag in the tag array, we can leverage the fixed layout of the tag array to calibrate the result of each tag in order to estimate the 3D coordinates and orientation of the object. In general, this part includes three main components: first, we use the calculated Z-coordinates of all the tags to infer the rough orientation of the object, from which we distinguish the three tag arrays on different surfaces and select a target tag array for further localization in the XY plane. Then, we localize the target tag array in the X-Y plane and estimate the rotation angle of the object. Finally, we get the 3D coordinates of the object referring to the location of the target tag array and the rotation angle of the object. The Algorithm 2: Calibration by tag arrays 1 Orientation Estimation: 2 The antenna moves along the Z axis to estimate the Z-coordinates of the all the tags; 3 Distinguish the three tag arrays on different surfaces; 4 Judge the flip state of the object by finding the tag array which is on the bottom/top surface; 5 Select the target tag array and calibrate the Z-coordinate of the target tag array according to Eq.7; 6 Target Tag Array Localization: 7 The antenna moves along the X axis to localize the tags in the target tag array in the X-Y plane; 8 Calculate the location of the target tag array and estimate the rotation angle of the object according to Eq.8; 9 Object Localization: 10 Calculate the 3D coordinates of the object based on the location of the target tag array and the rotation angle of the object according to Eq.9; 11 return 3D coordinates of the object whole algorithm is described in Algorithm 2. 1) Orientation Estimation: The orientation of the tagged objects must be firstly determined before performing an accurate 3D localization for the tagged objects. First, we need to distinguish the tag arrays on three mutually orthogonal surfaces. Recall that the Z-coordinates of the tags in the three tag arrays have different characteristics. In practice, we first move the antenna along the Z axis to estimate the Zcoordinates of all the tags, then the three tag arrays can be distinguished by comparing the Z-coordinate of each tag in the tag arrays. As illustrated in Fig.9(a), the antenna moves along the Z axis to calculate the Z-coordinate of the all the tags. Fig.9(b) shows the localization results. Notice that the Z-coordinates of the tags in Array 1 and Array 2 are equal and in Array 3 are different, so we can easily correspond the red points in Figure.9(b) to Array 3. Since the tag array on the top/bottom surface has the maximum or the minimum Zcoordinate value, so, the green points with the minimum Zcoordinates in Fig.9(b) correspond to Array 1 and we can also infer that Array 1 is at the bottom. Finally, the blue points corresponds to Array 2. After the above process, the flip state of the object is figured out. In addition, as mentioned before, the rotation angle of the object can be estimated from the target tag array in which every tag is attached along the Z axis and on the vertical surface of the object, so here Array 2 can be chosen as the target tag array. We next optimize the Z-coordinate of the target tag array. Let zc be the Z-coordinate of the target tag array’s center and zbi be the Z-coordinate for the i th tag calculated through AoA localization. As the Z-coordinate of each tag in the target tag array is the same, then, zc can be considered as the average Z-coordinate of all the tags in the target tag array: zc = ∑n i=1 zbi n (7)
0.3 0.2 Object centroid Array 3 0 (x0.y0.2o) Array 2 0 (Target) Tag array center 0.1 nu间 (xe.ye,Ze) 0.2 (xc,ye) Array 1 0.3 0.8 1 1.2 1.4 X 0 一X (a)Layout for the three tag arrays (b)Localization results (a)The relative locations of the target (b)Projections of the object onto tag array and the object the X-Y plane Fig.9.Distinguishing the three tag arrays Fig.10.Localization for the centroid of the object where n is the number of tags in the target tag array. where represents the ith tag's angle of arrival atj.The 2)Target tag array localization:After we choose the target linear relationship of x and cot can be used to find a fitting tag array and obtain its Z-coordinate zc,we focus on its line for P.Let the location of the ith tag be (i,)then, localization in the X-Y plane and estimate the rotation angle the line can be calculated according to Eg.4 as: of the object.The antenna is adjusted to be at the same cot8,=-1e-) height with the target tag array according to zc,and then we move the antenna along the X axis to compute the X and Y Since the coordinate of all the tags can be expressed with coordinates of each tag in the target tag array using AoA-based the tag array's center (re,yc)and rotation angle a,we aims localization.The result is denoted as {(1,),...,(n,Un)}, to find n fitting lines which can all be expressed with c, where (,is the coordinates of the ith tag.To calibrate and a to best fit n tags'point set P,P2,...,Pn.So, the location of each tag,we should consider all the tags in the coordinates of the target tag array's center (re,ye)and the tag array as a whole,then the coordinates of each tag can the object's rotation angle a can be calculated by solving the be expressed based on the location of the tag array's center following optimization problem: (e,ye)and rotation angle a of the object according to Eq.5. That is to say,the locations of all the tags are related to (e,ve) and a.Thus,the basic idea of our approach is to compute arg min (8) a.Te.ue 1 the optimal solution of(e,ye)and o while referring to the fixed layout of the tag array with the AoA localization result Subject to: {(t1,1),…,(在n,n)}. Before the optimization process,since a is in the range B={(色a,ot(a)）,…,(,cot(a)} [0,2m,we can classify a into a limited range based on the ri=xc+Pi·d cos B position of each tag in the tag array.As mentioned before,a yhi=yc+qi·dsin B can be divided into four cases and each case corresponds to a B=f(a) unique relative position relationship of the tags in the X and Y axes.Thus,we can judge the case where a belongs to by In practice,the search space of xe and ye can be reduced when comparing the X and Y coordinates of the 1st tag and the nth referring to{(t1,),…,(在n,n)}. tag in the tag array.For example,as shown in Fig.5,if1<n 3)Object Localization:Notice that we finally aim to locate and<yn,we can then infer that0≤a<π/2，belonging the object,then the centroid of the object can be regarded to case 1.Once the case that a belongs to is determined,the as our localization target.As shown in Fig.10(a),the sizes search range for the optimization process is reduced and the l1,12,and l3 of the object can be easily approximated, coordinate of the ith tag (i,y)can be expressed as a function therefore,it is not difficult to infer the position of the object's of c,ye and o according to Eq.5 as: centroid (o,y,2)from the coordinate of the target tag array's center (e,ye,zc)and the object's rotation angle a. xi=xe+pi·dcos B The Z-coordinates of the object's centroid and the target tag h=c+qi·dsin B array are equal,so,for localization in the X-Y plane,we can B=f(a) refer to(e,ye)and a.For example,as illustrated in Fig.10(b), the 3D coordinates of the object's centroid (o,,2)can be where lpil and gil can be previously determined by the tag expressed as: number n of the tag array,and d is the distance between two To =Ic +12/2.sina adjacent tags. yo ye +12/2.cos a (9) Next,we will discuss how to find the optimal solution of Zo Ze e.ye and a based on the AoA localization results of each tag (1,),...,(n,Un)}.Recall that the coordinate (of V.PERFORMANCE EVALUATION the ith tag is computed from the point set A.Implementation Hardware:3DLoc consists of a Impinj Speedway R420 B={(在1，cot(a)…,(色kcot(ak)} reader,a Laird S9028 RFID antenna,a motion controller,paper
Array 1 Array 2 (Target) Array 3 α X Z Y O (a) Layout for the three tag arrays 0.8 1 1.2 1.4 1.6 −0.3 −0.2 −0.1 0 0.1 0.2 0.3 d z Z (b) Localization results Fig. 9. Distinguishing the three tag arrays where n is the number of tags in the target tag array. 2) Target tag array localization: After we choose the target tag array and obtain its Z-coordinate zc, we focus on its localization in the X-Y plane and estimate the rotation angle of the object. The antenna is adjusted to be at the same height with the target tag array according to zc, and then we move the antenna along the X axis to compute the X and Y coordinates of each tag in the target tag array using AoA-based localization. The result is denoted as {(xb1, yb1), · · · ,(xbn, ybn)}, where (xbi , ybi) is the coordinates of the i th tag. To calibrate the location of each tag, we should consider all the tags in the tag array as a whole, then the coordinates of each tag can be expressed based on the location of the tag array’s center (xc, yc) and rotation angle α of the object according to Eq.5. That is to say, the locations of all the tags are related to (xc, yc) and α . Thus, the basic idea of our approach is to compute the optimal solution of (xc, yc) and α while referring to the fixed layout of the tag array with the AoA localization result {(xb1, yb1), · · · ,(xbn, ybn)}. Before the optimization process, since α is in the range [0, 2π], we can classify α into a limited range based on the position of each tag in the tag array. As mentioned before, α can be divided into four cases and each case corresponds to a unique relative position relationship of the tags in the X and Y axes. Thus, we can judge the case where α belongs to by comparing the X and Y coordinates of the 1 st tag and the n th tag in the tag array. For example, as shown in Fig.5, if xb1 < xbn and yb1 < ybn, we can then infer that 0 ≤ α < π/2, belonging to case 1. Once the case that α belongs to is determined, the search range for the optimization process is reduced and the coordinate of the i th tag (xi , yi) can be expressed as a function of xc, yc and α according to Eq.5 as: xi = xc + pi · d cos β yi = yc + qi · d sin β β = f (α) where |pi | and |qi | can be previously determined by the tag number n of the tag array, and d is the distance between two adjacent tags. Next, we will discuss how to find the optimal solution of xc, yc and α based on the AoA localization results of each tag {(xb1, yb1), · · · ,(xbn, ybn)}. Recall that the coordinate (xbi , ybi) of the i th tag is computed from the point set Pi = {(x˜i,1, cot ( ˜θi,1 )) , · · · , ( x˜i,ki , cot ( ˜θi,ki ))} ߙ ݈ଵ ݈ଶ ݈ଷ Object centroid ሺݔǡ ݕǡ ݖሻ Tag array center ݔሺ ݕ ǡ ǡ ݖሻ X Y Z O (a) The relative locations of the target tag array and the object X Y ሺݔǡ ݕሻ ݔሺ ǡ ݕሻ ݈ଵ ݈ଶ ߙ ݈ଶ ʹ O (b) Projections of the object onto the X-Y plane Fig. 10. Localization for the centroid of the object where ˜θi,j represents the i th tag’s angle of arrival at x˜i,j . The linear relationship of x and cot θ can be used to find a fitting line for Pi . Let the location of the i th tag be (xi , yi), then, the line can be calculated according to Eq.4 as: cot θi = − 1 yi (x − xi) Since the coordinate of all the tags can be expressed with the tag array’s center (xc, yc) and rotation angle α, we aims to find n fitting lines which can all be expressed with xc, yc and α to best fit n tags’ point set P1, P2, · · · , Pn. So, the coordinates of the target tag array’s center (xc, yc) and the object’s rotation angle α can be calculated by solving the following optimization problem: arg min α,xc,yc ∑n i=1 ∑ ki j=1 − 1 yi (˜xi,j − xi) − cot ( ˜θi,j) 2 (8) Subject to: Pi = {(x˜i,1, cot ( ˜θi,1 )) , · · · , ( x˜i,ki , cot ( ˜θi,ki ))} xi = xc + pi · d cos β yi = yc + qi · d sin β β = f (α) In practice, the search space of xc and yc can be reduced when referring to {(xb1, yb1), · · · ,(xbn, ybn)}. 3) Object Localization: Notice that we finally aim to locate the object, then the centroid of the object can be regarded as our localization target. As shown in Fig.10(a), the sizes l1, l2, and l3 of the object can be easily approximated, therefore, it is not difficult to infer the position of the object’s centroid (xo, yo, zo) from the coordinate of the target tag array’s center (xc, yc, zc) and the object’s rotation angle α. The Z-coordinates of the object’s centroid and the target tag array are equal, so, for localization in the X-Y plane, we can refer to (xc, yc) and α. For example, as illustrated in Fig.10(b), the 3D coordinates of the object’s centroid (xo, yo, zo) can be expressed as: xo = xc + l2/2 · sin α yo = yc + l2/2 · cos α zo = zc (9) V. PERFORMANCE EVALUATION A. Implementation Hardware: 3DLoc consists of a Impinj Speedway R420 reader, a Laird S9028 RFID antenna, a motion controller, paper
boxes,and a set of Impinj E41-B tags.The reader works at the frequency band 920.625~924.375MHz.The antenna is fixed on the motion controller which enables the linear movement along the horizontal direction and the vertical direction. Software:We have implemented 3DLoc in Java and we run the software in a terminal PC which is connected to the Reader with the Low-level Reader Protocol.The motion controller is programmed to move at the speed of 15cm/s for the 3D ader localization of the tagged objects. Fig.11.Experiment scene B.Deployment We conduct our experiments in the indoor environment. obviously as we increase the distance between the tags:the Fig.11 shows the experiment scene and specifies the coordinate error drops from 15.2cm to 7.3cm as the tag distance changes system.The antenna is fixed on the motion controller,which from 3cm to 15cm.In free space,the localization error changes supports the antenna's movement along the X axis and the slightly when the distance changes from 3cm to 9cm and the Z axis.For the tagged object,we deploy three sets of tag localization errors are all around 7cm.If we further increase arrays along mutually orthogonal directions on three mutually the distance to 12cm,the error becomes 4.3cm.In conclusion. orthogonal surfaces.For each tag array,since the tag coupling it is more useful to increase the distance between the two effect will distort the phase value [14,15],we ensure that two adjacent tags for the tag array in the multipath environment adjacent tags are deployed with opposite orientations as shown since the localization error in free space is small. in Fig.11. Tag number of the tag array vs.Localization error: Generally,more tags in the tag array contributes to a lower C.Micro-Benchmark localization error.We set the distance between the two adjacent Experimental setup:The experiments are performed in tags to be 9cm and change the the number of tags in the tag two cases:free space and multipath environment.We have array.As shown in Fig.15,in the multipath environment,the designed four experiments to evaluate the performance of localization errors decrease when we increase the total number the multipath suppression algorithm and analyze how the tag of the tags from 2 to 5:the localization error changes from numbers and tag distances influence the localization accuracy. 17cm to 9cm.For the free space scenario,the error for the 2- Since the 3D localization is expanded from the 2D plane,we tag array is 7.1cm,thus obvious improvement cannot been seen first focus on the 2D localization of the tags.The antenna and for the localization accuracy when we increase the number of the tags are all put at a height of 80cm from the ground. the tags in the tag array. Metrics:We use error(cm)to indicate the localization accuracy for a single tag and the tag array.Specifically for D.Macro-Benchmark the tag array,the center of the tag array are considered as our Experimental setup:We put the antenna on the motion localization target. controller to move along the X and Z axes to localize three Determine a proper window size for multipath suppres- tagged objects.The size of the object is 45 x 40 x 30cm and it sion:The slide window separates the point set for removing is attached with three four-tag arrays in which the distance of the outliers in the AoA-based localization.As illustrated in the two adjacent tags is 9cm.In the experiment,we place three Fig.12,the localization error is 15cm when we set the window tagged objects in different locations with different orientations. size to 5.The error decreases as we increase the window size Metrics:In the evaluation of 3DLoc,the localization errors from 5 to 15.However,the error increases again if we go on are calculated both for the target tag array and the object.We increasing the window size w.Therefore,we set w to 15cm consider the center of the tag array and the centroid of the as a trade-off. object as the localization target for the target tag array and With or without multipath suppression:To evaluate the object,respectively. the performance of the multipath suppression algorithm,we In the first experiment,we evaluate 3DLoc in comparison localize four tags in different locations.The coordinates of with the Hologram-based method.Since the orientation of the the four tags are Ti(0,120),T2(-20,140),T3(20,140),and object cannot be estimated by the Hologram-based method T4(-20,160).As shown in Fig.13,the localization error compared with 3DLoc,we cannot estimate location of the decreases sharply when we adopt the proposed multipath centroid of object.Thus We only compare the localization suppression algorithm,i.e.,the error for T2 decreases from results of the given target tag array.As shown in Fig.16, 45cm to 15cm. two methods both perform well in the free space.However, Tag distance of the tag array vs.Localization error:in the multipath environment,the errors for 3DLoc and the Intuitively,a larger distance between the tags results in a Hologram-based method are 8cm and 16.7cm respectively.So higher localization accuracy.We localize a four-tag array in 3DLoc outperforms the Hologram-based method significantly both free space and the multipath environment while changing in the multipath environment. the distance between two adjacent tags.As shown in Fig.14, In the second experiment,we place three objects in different in the multipath scenario,the localization error decreases locations and orientations,and localize them by 3DLoc in the
boxes, and a set of Impinj E41-B tags. The reader works at the frequency band 920.625∼924.375MHz. The antenna is fixed on the motion controller which enables the linear movement along the horizontal direction and the vertical direction. Software: We have implemented 3DLoc in Java and we run the software in a terminal PC which is connected to the Reader with the Low-level Reader Protocol. The motion controller is programmed to move at the speed of 15cm/s for the 3D localization of the tagged objects. B. Deployment We conduct our experiments in the indoor environment. Fig.11 shows the experiment scene and specifies the coordinate system. The antenna is fixed on the motion controller, which supports the antenna’s movement along the X axis and the Z axis. For the tagged object, we deploy three sets of tag arrays along mutually orthogonal directions on three mutually orthogonal surfaces. For each tag array, since the tag coupling effect will distort the phase value [14, 15], we ensure that two adjacent tags are deployed with opposite orientations as shown in Fig.11. C. Micro-Benchmark Experimental setup: The experiments are performed in two cases: free space and multipath environment. We have designed four experiments to evaluate the performance of the multipath suppression algorithm and analyze how the tag numbers and tag distances influence the localization accuracy. Since the 3D localization is expanded from the 2D plane, we first focus on the 2D localization of the tags. The antenna and the tags are all put at a height of 80cm from the ground. Metrics: We use error(cm) to indicate the localization accuracy for a single tag and the tag array. Specifically for the tag array, the center of the tag array are considered as our localization target. Determine a proper window size for multipath suppression: The slide window separates the point set for removing the outliers in the AoA-based localization. As illustrated in Fig.12, the localization error is 15cm when we set the window size to 5. The error decreases as we increase the window size from 5 to 15. However, the error increases again if we go on increasing the window size w. Therefore, we set w to 15cm as a trade-off. With or without multipath suppression: To evaluate the performance of the multipath suppression algorithm, we localize four tags in different locations. The coordinates of the four tags are T1 (0, 120), T2 (−20, 140), T3 (20, 140), and T4 (−20, 160). As shown in Fig.13, the localization error decreases sharply when we adopt the proposed multipath suppression algorithm, i.e., the error for T2 decreases from 45cm to 15cm. Tag distance of the tag array vs. Localization error: Intuitively, a larger distance between the tags results in a higher localization accuracy. We localize a four-tag array in both free space and the multipath environment while changing the distance between two adjacent tags. As shown in Fig.14, in the multipath scenario, the localization error decreases Z Y X Motion controller Reader Antenna Tag array Different orientation O Fig. 11. Experiment scene obviously as we increase the distance between the tags: the error drops from 15.2cm to 7.3cm as the tag distance changes from 3cm to 15cm. In free space, the localization error changes slightly when the distance changes from 3cm to 9cm and the localization errors are all around 7cm. If we further increase the distance to 12cm, the error becomes 4.3cm. In conclusion, it is more useful to increase the distance between the two adjacent tags for the tag array in the multipath environment since the localization error in free space is small. Tag number of the tag array vs. Localization error: Generally, more tags in the tag array contributes to a lower localization error. We set the distance between the two adjacent tags to be 9cm and change the the number of tags in the tag array. As shown in Fig.15, in the multipath environment, the localization errors decrease when we increase the total number of the tags from 2 to 5: the localization error changes from 17cm to 9cm. For the free space scenario, the error for the 2- tag array is 7.1cm, thus obvious improvement cannot been seen for the localization accuracy when we increase the number of the tags in the tag array. D. Macro-Benchmark Experimental setup: We put the antenna on the motion controller to move along the X and Z axes to localize three tagged objects. The size of the object is 45 × 40 × 30cm and it is attached with three four-tag arrays in which the distance of the two adjacent tags is 9cm. In the experiment, we place three tagged objects in different locations with different orientations. Metrics: In the evaluation of 3DLoc, the localization errors are calculated both for the target tag array and the object. We consider the center of the tag array and the centroid of the object as the localization target for the target tag array and the object, respectively. In the first experiment, we evaluate 3DLoc in comparison with the Hologram-based method. Since the orientation of the object cannot be estimated by the Hologram-based method compared with 3DLoc, we cannot estimate location of the centroid of object. Thus We only compare the localization results of the given target tag array. As shown in Fig.16, two methods both perform well in the free space. However, in the multipath environment, the errors for 3DLoc and the Hologram-based method are 8cm and 16.7cm respectively. So 3DLoc outperforms the Hologram-based method significantly in the multipath environment. In the second experiment, we place three objects in different locations and orientations, and localize them by 3DLoc in the
20 ■Without suppression 20 ■Free space 60 ☐Multipath 15 ☐With suppression (w)o 15 15 10 3 l 1015.2025 T4 91215 Window Size Different Tags Tag Distance(cm) Fig.12. Window size for multipath suppression Fig.13. The performance of multipath suppression Fig.14.Tag distance vs.error 30 Free space 3DLoc Multipath ☐Holography-based 0.8 20 0.2 -Free space -Multi-path Free space Multipath 10 20 30 40 Tag Number Different Schemes Error(cm) Fig.15.Tag number vs.error Fig.16.Scheme vs.error Fig.17.Error CDF free space and the multipath environment.In the localization REFERENCES process,we first calculate the target tag array's 3D coordinates [1]L.Shangguan,Z.Li,Z.Yang,M.Li,and Y.Liu,Otrack:Order Tracking and object's rotation angle,and then the centroid of the object for Luggage in Mobile RFID Systems,in Proc.of IEEE INFOCOM. 2013 can be obtained according to Eq.9.We plot the CDF of the [2]J.Nickels,P.Knierim,B.Koenings,F.Schaub,B.Wiedersheim,S.Mu- position error for the centroid of the object in Fig.17.The siol,and M.Weber,Find My Stuff:Supporting Physical Objects Search mean error of the object is 10cm and 15.3cm in the free space with Relative Positioning,in Proc.of ACM MOBIOUITOUS,2013. and the multipath environment,which is sufficient compared [3]M.R.Basheer and S.Jagannathan,Localization of RFID Tags Using Stochastic Tunneling.in IEEE TRANSACTIONS ON MOBILE COMPUT. with the object's size(45×40×30cm). NG,ol.12,no.6,Pp.1225-1235,2013. [4]L.Yang.Y.Qi.J.Fang.X.Ding.T.Liu and M.Li,Frogeye:Perception VI.CONCLUSION of the slightest tag motion,in Proc.of IEEE INFOCOM,2014. 5]W.Ruan,L.Yao,Q.Sheng.N.Falkner and X.Li,TagTrack:Device-free In this paper,we propose 3DLoc to perform 3D localization Localization and Tracking Using Passive RFID Tags,in Proc.of ACM on the tagged objects using RFID tag arrays.3DLoc uses the MOBIOUITOUS,2014. AoA-based scheme to accurately estimate the tagged objects' [6]J.Wang.F.Adib,R.Knepper,D.Katabi and D.Rus,RF-Compass:Robot Object Manipulation Using RFIDs,in Proc.of ACM MOB/COM,2013. orientations and 3D coordinates in the 3D space referring [7]T.Liu,L.Yang,Q.Lin,Y.Guo and Y.Liu,Anchor-free Backscatter to the fixed layout of the tag array.We propose a novel Positioning for RFID Tags with High Accuracy.in Proc.of IEEE algorithm to suppress the localization errors caused by the INFOCOM.2014. [8]L.Xie,J.Sun,Q.Cai,C.Wang,J.Wu and S.Lu,Tell Me What I See: multipath effect.3DLoc has been implemented on a COTS Recognize RFID Tagged Objects in Augmented Reality Systems.in Proc. RFID platform,and we have evaluated the actual performance of ACM UBICOMP,2016. of 3DLoc in the real complex environment,the experiment [9]S.Azzouzi,M.Cremer,U.Dettmar.R.Kronberger and T.Knie.New Measurement Results for the Localization of UHF RFID Transponders results show that 3DLoc can achieve a high accuracy.3DLoc Using an Angle of Arrival (AoA)approach.in Proc.of IEEE RFID. is the first work to consider the 3D localization of tagged 2011. objects using the RFID tag arrays,and it can be applied to [10]J.Wang and D.Katabi,Dude.where's my card?:RFID Positioning That Works with Multipath and Non-Line of Sight,in Proc.of ACM indoor localization systems with the severe multipath. SIGCOMM.2013. [11]J.Wang,D.Vasisht and D.Katabi,RF-IDraw:Virtual Touch Screen in ACKNOWLEDGMENTS the Air Using RF Signals,in Proc.of ACM S/GCOMM,2014 [12]L.Yang.Y.Chen,X.Li,C.Xiao,M.Li,and Y.Liu,Tagoram:Real-time This work is supported in part by National Natural Science Tracking of Mobile RFID Tags to High Precision Using COTS Devices. Foundation of China under Grant Nos.61472185.61373129. in Proc.of ACM MOBICOM,2014. 61321491,61502224;JiangSu Natural Science Foundation [13]L.Shangguan,and K.Jamieson,The Design and Implementation of a Mobile RFID Tag Sorting Robot,in Proc.of ACM MOBISYS,2016. under Grant No.BK20151390:Fundamental Research Funds [14]J.Han,Q.Chen,X.Wang,D.Ma,J.Zhao,W.Xi,Z.Jiang and Z.Wang for the Central Universities under Grant No.020214380035: Twins:Device-free Object Tracking using Passive Tags,in Proc.of IEEE NSF grants CNS 1629746,CNS 1564128,CNS 1449860,CNS INFOCOM,2014. [15]L.Yang.J.Han,Y.Qi,C.Wang.T.Gu and Y.Liu,Season:Shelving 1461932.CNS1460971.CNS1439672.CNS1301774.ECCS interference and joint identification in large-scale rfid systems,in Proc. 1231461.This work is partially supported by Collaborative of IEEE INFOCOM,2011. Innovation Center of Novel Software Technology and Indus- trialization.Lei Xie is the corresponding author
5 10 15 20 25 0 5 10 15 20 Window Size Error (cm) Fig. 12. Window size for multipath suppression T1 T2 T3 T4 0 15 30 45 60 Error (cm) Different Tags Without suppression With suppression Fig. 13. The performance of multipath suppression 3 6 9 12 15 0 5 10 15 20 Error (cm) Tag Distance (cm) Free space Multipath Fig. 14. Tag distance vs. error 2 3 4 5 0 5 10 15 20 Error (cm) Tag Number Free space Multipath Fig. 15. Tag number vs. error Different Schemes Free space Multipath Error (cm) 0 10 20 30 3DLoc Holography-based Fig. 16. Scheme vs. error 0 10 20 30 40 0 0.2 0.4 0.6 0.8 1 Error (cm) CDF Free space Multi−path Fig. 17. Error CDF free space and the multipath environment. In the localization process, we first calculate the target tag array’s 3D coordinates and object’s rotation angle, and then the centroid of the object can be obtained according to Eq.9. We plot the CDF of the position error for the centroid of the object in Fig.17. The mean error of the object is 10cm and 15.3cm in the free space and the multipath environment, which is sufficient compared with the object’s size (45 × 40 × 30cm). VI. CONCLUSION In this paper, we propose 3DLoc to perform 3D localization on the tagged objects using RFID tag arrays. 3DLoc uses the AoA-based scheme to accurately estimate the tagged objects’ orientations and 3D coordinates in the 3D space referring to the fixed layout of the tag array. We propose a novel algorithm to suppress the localization errors caused by the multipath effect. 3DLoc has been implemented on a COTS RFID platform, and we have evaluated the actual performance of 3DLoc in the real complex environment, the experiment results show that 3DLoc can achieve a high accuracy. 3DLoc is the first work to consider the 3D localization of tagged objects using the RFID tag arrays, and it can be applied to indoor localization systems with the severe multipath. ACKNOWLEDGMENTS This work is supported in part by National Natural Science Foundation of China under Grant Nos. 61472185, 61373129, 61321491, 61502224; JiangSu Natural Science Foundation under Grant No. BK20151390; Fundamental Research Funds for the Central Universities under Grant No. 020214380035; NSF grants CNS 1629746, CNS 1564128, CNS 1449860, CNS 1461932, CNS 1460971, CNS 1439672, CNS 1301774, ECCS 1231461. This work is partially supported by Collaborative Innovation Center of Novel Software Technology and Industrialization. Lei Xie is the corresponding author. REFERENCES [1] L. Shangguan, Z. Li, Z. Yang, M. Li, and Y. Liu, Otrack: Order Tracking for Luggage in Mobile RFID Systems, in Proc. of IEEE INFOCOM, 2013. [2] J. Nickels, P. Knierim, B. Koenings, F. Schaub, B. Wiedersheim, S. Musiol, and M. Weber, Find My Stuff: Supporting Physical Objects Search with Relative Positioning, in Proc. of ACM MOBIQUITOUS, 2013. [3] M. R. Basheer and S. Jagannathan, Localization of RFID Tags Using Stochastic Tunneling, in IEEE TRANSACTIONS ON MOBILE COMPUTING, vol. 12, no. 6, pp. 1225-1235, 2013. [4] L. Yang, Y. Qi, J. Fang, X. Ding, T. Liu and M. Li, Frogeye: Perception of the slightest tag motion, in Proc. of IEEE INFOCOM, 2014. [5] W. Ruan, L. Yao, Q. Sheng, N. Falkner and X. Li, TagTrack: Device-free Localization and Tracking Using Passive RFID Tags, in Proc. of ACM MOBIQUITOUS, 2014. [6] J. Wang, F. Adib, R. Knepper, D. Katabi and D. Rus, RF-Compass: Robot Object Manipulation Using RFIDs, in Proc. of ACM MOBICOM, 2013. [7] T. Liu, L. Yang, Q. Lin, Y. Guo and Y. Liu, Anchor-free Backscatter Positioning for RFID Tags with High Accuracy, in Proc. of IEEE INFOCOM, 2014. [8] L. Xie, J. Sun, Q. Cai, C. Wang, J. Wu and S. Lu, Tell Me What I See: Recognize RFID Tagged Objects in Augmented Reality Systems, in Proc. of ACM UBICOMP, 2016. [9] S. Azzouzi, M. Cremer, U. Dettmar, R. Kronberger and T. Knie, New Measurement Results for the Localization of UHF RFID Transponders Using an Angle of Arrival (AoA) approach, in Proc. of IEEE RFID, 2011. [10] J. Wang and D.Katabi, Dude, where’s my card?: RFID Positioning That Works with Multipath and Non-Line of Sight, in Proc. of ACM SIGCOMM, 2013. [11] J. Wang, D. Vasisht and D. Katabi, RF-IDraw: Virtual Touch Screen in the Air Using RF Signals, in Proc. of ACM SIGCOMM, 2014. [12] L. Yang, Y. Chen, X. Li, C. Xiao, M. Li, and Y. Liu, Tagoram: Real-time Tracking of Mobile RFID Tags to High Precision Using COTS Devices, in Proc. of ACM MOBICOM, 2014. [13] L. Shangguan, and K. Jamieson, The Design and Implementation of a Mobile RFID Tag Sorting Robot, in Proc. of ACM MOBISYS, 2016. [14] J. Han, Q. Chen, X. Wang, D. Ma, J. Zhao, W. Xi, Z. Jiang and Z. Wang, Twins: Device-free Object Tracking using Passive Tags, in Proc. of IEEE INFOCOM, 2014. [15] L. Yang, J. Han, Y. Qi, C. Wang, T. Gu and Y. Liu, Season: Shelving interference and joint identification in large-scale rfid systems, in Proc. of IEEE INFOCOM, 2011