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