This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE ICC 2010 proceedings
`
`3D Passive Tag Localization Schemes for
`Indoor RFID Applications
`
`Abdallah Almaaitah
`ECE Department, Queen’s University
`Kingston, Ontario, Canada, K7L 3N6
`abdallah.almaaitah@queensu.ca
`
`Kashif Ali, Hossam S. Hassanein
`School of Computing, Queen’s University
`Kingston, Ontario, Canada, K7L 3N6
`{kashif, hossam}@cs.queensu.ca
`
`Mohamed Ibnkahla
`ECE Department, Queen’s University
`Kingston, Ontario, Canada, K7L 3N6
`mohamed.ibnkahla@queensu.ca
`
`Abstract—Accurate and efficient localization of tags are of
`utmost importance for numerous existing and forthcoming RFID
`applications. In this paper, we introduce two novel methods
`for three dimensional
`localization of the passive RFID tags.
`In the first approach, namely Adaptive Power Multilateration
`(APM), using four RFID readers, distance estimations param-
`eters are processed based on the minimal interrogation power
`and multilateration. Whereas in the second approach, namely
`Adaptive Power with Antenna Array (APAA), a single RFID
`reader equipped with horizontal and vertical smart antennas
`alongside with the reader’s adaptive power levels are used for
`the tags distance estimations. The APM scheme localizes the
`tags with comparatively finer granularity whereas the APAA
`scheme supports reader’s mobility and facilitates highly dense
`tag environments. Simulation results show that our proposed
`schemes provide more accurate localization than other indoor
`localization schemes.
`Keywords—localization, RFID, Angle-of-Arrival (AoA), smart
`antennas, power control, multilateration
`
`I. INTRODUCTION
`Object localization, in both two and three dimensions, is
`a well studied problem. Numerous solutions with varying
`techniques have been proposed in this context. For outdoor
`environments, Global Positioning System (GPS) technology
`is an efficient solution when it comes to localization of
`people, equipments, vehicles, etc. However, despite the huge
`advancements in the indoor signal sensing, the GPS tech-
`nology because of its line of sight requirements with the
`orbiting satellites will not be feasible for many of the indoor
`applications [1]. As remedy, other wireless technologies such
`as WLAN and ZigBee, have been investigated as possible
`solutions. However, these technologies are not reliable due
`to high error margins and do not scale to facilitate item-level
`tagging. Furthermore, the monetary cost of localization, using
`the aforementioned solutions, exceeds the actual cost of the
`object being tracked hence, are economically unfeasible.
`Radio Frequency IDentification (RFID) is an emerging
`technology and is widely seen as a promising solution with
`ability to turn objects into a network of mobile nodes, which
`can then be used to track objects and trigger events, hence,
`instigates new applications [11]. Tag localization is the key
`requirement for many existing and forthcoming applications.
`For instance, item-level tracking on conveyor belts , localizing
`lost inventory in apparel industry and so forth. Numerous
`RFID based localization schemes, for indoor applications,
`
`have been proposed [2]–[4]. The existing schemes measure
`the signal strength from multiple readers [5] to calculate the
`tag’s position. However, these schemes demand active and/or
`customized tags and require extensive pre-installation planning
`of the interrogating readers.
`In this paper, we propose and evaluate two deterministic
`location estimation schemes for passive and active RFID tags.
`In the first scheme, Adaptive Power Multilateration (APM),
`the RFID readers dynamically adjusts their transmission power
`to estimate tags’ location using the multilateration approach.
`The APM scheme localizes tags with high accuracy however,
`requires minimal of three and four standard RFID readers
`for 2D and 3D environments, respectively. In the second
`scheme, Adaptive Power with Antenna Array (APAA), the
`reader is equipped with a smart antennas systems [6]. The
`smart antennas system, using its horizontal and vertical an-
`tennas, estimates the Angle-of-Arrival (AoA) of the received
`RF signal, while also varying the transmission power levels.
`Unlike the APM scheme, the APAA scheme can localize the
`RFID tags, in both 2D and 3D settings, using a single reader,
`however with lesser accuracy. Furthermore, the APAA scheme
`facilitates mobility and dense item-level
`localization. The
`RFID localization system is implemented using MATLAB.
`Simulation results validate the effectiveness of both schemes
`in localizing passive and active tags under mobile and dense
`tags environment.
`The remainder of the paper is organized as follows. Sec-
`tion II surveys the existing literature in the context of RFID lo-
`calization. Section III describes the two proposed localization
`schemes and explains the adopted error model and multiple
`reader’s placement scenarios. Section IV presents simulated
`experiments conducted using MATLAB and analyzes the
`obtained results under multiple scenarios. Finally, section V
`concludes our work and highlights future direction.
`
`II. LITERATURE SURVEY
`Numerous location estimation algorithms have been pro-
`posed to localize RFID tags; active and passive. Active tag
`localization includes many techniques such as SpotOn [2] and
`LANDMARC [3]. The SpotON [2] uses the aggregation algo-
`rithm for 3D location sensing using Received Signal Strength
`Indication (RSSI). The tags in this system are customized to
`use radio signal attenuation in order to estimate the inter-tag
`
`978-1-4244-6404-3/10/$26.00 ©2010 IEEE
`
`RFC - Exhibit 1015
`
`1
`
`

`
`This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE ICC 2010 proceedings
`
`distance. The system requires unacceptable computational and
`processing time, in tens of seconds, hence, yields low localiza-
`tion and tracking accuracy. The LocAlizatioN iDentification
`based on dynaMic Active Rfid Calibration (LANDMARC)
`technique [3], is an active tag based localization system. The
`readers in the LANDMARC scheme estimate the tag location
`based on the sub-region that it may be in. When the tags
`enter each sub-region, the distance between the tag and the
`reader will be computed and calibrated. Furthermore,
`the
`reference tags are also placed at well-known locations in order
`to determine the ‘power fingerprints’ for such locations. The
`reference tags serve as landmarks to the system. Despite the
`effectiveness in LANDMARC localization system, it requires
`pre-deployment planning, pre-installation of anchor tags and
`customized active RFID tags.
`Passive tag localization schemes include probabilistic,
`multi-frequency, and repository-based solutions. In the proba-
`bilistic scheme [4], a pre-deployment probabilistic estimation
`of the passive tags localization is performed. The passive tags,
`once interrogated, inform only about its presence within an
`angular sector. The angular sectors are created by the reader
`with rotating angular antenna. The rotating antenna snaps the
`environment in different angular sections with different trans-
`mitting powers to fine grain the angular space. However, in
`such a system, the localization accuracy significantly depends
`on pre-deployment estimation and the readers enumeration and
`their deployment patterns. In the multi-frequency scheme [5],
`the field generators expand the reader signal range (act as
`a repeater for the reader) and use frequency range of 433
`MHz for signalling the tags whereas the tags communicate
`with the reader using UHF frequency of 916 MHz. However,
`the use of field generators normally increases the location
`error. Therefore, are not feasible for localization of passive
`tags in 3D environments. In the repository-based scheme [7],
`an RFID-based Library Information Management (R-LIM)
`system is maintained to localize and track the tagged library
`books. The R-LIM maintains a repository of the IDs of the
`RFID tags affix on each book along with the book residing
`shelf ID. The reader scans multiple shelves by moving along
`each shelve. The R-LIM scheme effectively localize the book
`however, only within its shelved area.
`All
`the aforementioned schemes, however, require pre-
`deployment scanning and book-keeping, optimal readers de-
`ployment, custom tags, economical inefficient and/or are tai-
`lored for a given application.
`
`III. PROPOSED LOCALIZATION SCHEMES
`In this paper, we propose two 3D indoor localization
`schemes for passive RFID tags using the range-based and
`bearing-based approaches. In the range-based scheme, namely
`Adaptive Power Multilateration (APM), a modified multilater-
`ation technique is used to calculate the expected tags location.
`Multilateration [8] is a deterministic estimation method; the
`statistical parameters such as mean or median are used for ro-
`bust estimation. This is shown in Fig. 1, wherein the expected
`location of the tag will be the average of the intersection points
`
`Fig. 1. Multilateration technique
`
`S1, S2, and S3. In APM, the reader’s antenna power level is
`dynamically adjusted for fine-grained distance resolutions. In
`this context, a modified multilateration method is proposed,
`since the existing variants of multilateration do not employ
`the adaptive power levels approach nor exploit
`the RFID
`specific characteristics. In the context of RFID localization,
`the use of adaptive power level is a novel approach which has
`been adopted from our earlier work to resolve tag collisions
`[10]. The unique feature, implicit to RFID tags (i.e. reader’s
`triggering of tag to send its serial number is embedded with
`the RSSI) is used to simplify the range calculations. The APM
`scheme achieves high localization accuracy using off-the-shelf
`RFID readers. In the bearing-based scheme, namely Adaptive
`Power Antenna Array (APAA),
`the adaptive power levels
`is adopted beside two smart antennas. The smart antennas
`estimate the horizontal and vertical angle of tag relative to
`the reader. The estimated angles and power levels are then
`used in the estimation of the tag location.
`
`A. Adaptive Power with Multilateration (APM)
`In this method, the adaptive power level technique [10]
`is applied to any pre-installed readers and the tag position
`is then estimated using multilateration calculations. For each
`reader, two power levels are evaluated and logged for each
`tag laying within its interrogation zone. The first level is the
`maximum power, Pi−1, at which tag did not respond to the
`reader queries. The second is the minimum power level, Pi,
`at which the tag responded. The two power levels, along with
`the singulated tags serial-numbers are used along with the
`multilateration based tag’s location calculation.
`For the multilateration based calculation, the center point
`between the two power levels is assumed to be the radius (P )
`of the spheres that centred at the reader. The radius of the
`sphere is used to determine the intersection points with the
`other readers’ spheres ( i.e., radios P from other readers) for a
`particular tag. Therefore, the center point of two power levels
`is
`P = Pi + Pi+1
`= Pi−1 + l
`2
`2
`where l is the power level step, i.e., the incremental value
`between two sequential power levels. The APM scheme,
`beside being a variant of multilateration approach, requires
`predetermined readers placement due to the adaptive power
`
`(1)
`
`2
`
`

`
`This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE ICC 2010 proceedings
`
`(a) 3D tetrahedron
`
`(b) AoA and power-level
`
`Fig. 3. Reader’s placement along with its AoA and power-level measurements
`
`based on the adaptive power levels. The reader reconfigures
`the transmission power to deterministically estimate the tag’s
`location. Second technique is based on AoA measurements.
`The AoA measurements are calculated using the phase dif-
`ferences at the smart antenna. The reader is affixed with two
`smart antennas, vertical and horizontal, with an angle step of
`θs. The AoA information is also associated with the tag serial-
`number and is stored in reader’s repository. Both information,
`the AoA measurement and the power-level are then used to
`estimate the location of the tag, as illustrated in Fig. 3-b.
`The tag expected location in the APAA scheme is defined
`by the power-levels (Pi−1, Pi) and the AoA measurement, θv
`from the vertical antenna array and θh from the horizontal
`antenna array and range of the two angles, is
`
`xm(P, θv,θh) =
`(cid:10)
`
`(cid:7)(cid:8)(cid:8)(cid:8)(cid:9)
`
`1 +
`
`sin(θh)
`| sin(θh)| ∗
`
`P 2
`cos2(θv)
`+
`1 − cos2(θv)
`
`cos2(θh)
`1 − cos2(θh)
`
`(cid:11)
`
`(4)
`
`(cid:12)
`zm(P, θv, θh) =
`
`(5)
`
`(6)
`
`cos(θh)
`| cos(θh)| ∗
`(cid:12)
`ym(P, θv, θh) =
`cos2(θv)
`xm(P, θv, θh)2 ∗
`1 − cos2(θv)
`cos(θv)
`| cos(θv)| ∗
`cos2(θh)
`xm(P, θv, θh)2 ∗
`1 − cos2(θh)
`For accurate estimation, the smaller the angle step (θs),
`which is based on the beamforming resolution of the smart
`antenna, the better the estimation of the vertical angle (θv)
`and horizontal angle (θh) would be. The effect of the power
`step l is embedded within P in the above equations. The
`effects of θs and l on the accuracy of the proposed scheme are
`studied in the following section. Unlike APM, where cases of
`no intersection points amongst all readers are possible, every
`
`level approach. The reason is that the power levels may intro-
`duce some cases where it is impossible to have intersection
`amongst the required number of readers. An example of such
`a case is when one reader’s range fits inside another reader’s
`range (no intersection points). Such cases are further discussed
`in Section IV. To this end, we introduce the tetrahedron-based
`readers placement (Fig. 3-a), where maximum non-collinearity
`between the readers is achieved when they are placed at the
`vertices of the tetrahedron. Outside the tetrahedron region, the
`localization accuracy of the tag drops as the probability of
`having no intersections between the power spheres increases.
`
`Fig. 2. Clustering of the centre point for 3 readers
`
`To estimate the location of a particular tag m in the x,y,
`and z coordinates requires determination of unique intersecting
`point of the four readers radius, as shown in Fig. 2. Two
`points P1(1,2,3) and P2(1,2,3) are calculated from the centre
`point of power level P , an intersection of power levels, from
`eq. (1), of the three readers R1,R2, and R3 [9]. Furthermore,
`the distances between the fourth reader and the two points P1
`P2 are calculated. The point which has the closest distance to
`P4 is selected as the expected point from R4 and is denoted
`E4.
`
`⎧⎪⎨
`⎪⎩P1(1,2,3),
`
`E4 =
`
`(2)
`
`if (((cid:2)P1(1,2,3) − C4(cid:2) −P 4)
`< ((cid:2)P2(1,2,3) − C4(cid:2) − P4))
`P2(1,2,3), otherwise
`The expected point from other readers, E1, E2, and E3,
`are also calculated in similar manner. An average of all
`the intersection points (Eaverage) is used to determine the
`estimated location of the tag m,
`
`(cid:6)
`
`(3)
`
`K k
`
`=1 Ek
`K
`where K is the number of readers covering the space (in
`Fig. 2, K = 4). APM scheme requires pre-deployment planning
`and is suitable for a fixed-reader mobile-tag applications.
`Potential applications of the APM scheme may include patient
`monitoring, museum artifacts monitoring and context-aware
`applications, where readers mobility is not crucial.
`
`Eaverage =
`
`B. Adaptive Power with Antenna Array(APAA)
`Tag localization in the APAA scheme is based on two
`techniques. First technique, similar to the APM scheme, is
`
`3
`
`

`
`This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE ICC 2010 proceedings
`
`Fig. 4. Testing methodology
`
`Fig. 6. Power step effect on the overall error the tetrahedron of 10m depth,
`Tx=[1:10], Ty= 40m, Tz=40m, l =[0.1:1:10.1]
`
`A tetrahedron with a depth (D), as is shown in Fig. 3-a, of
`10m is tested for APM scheme error calculation. The average
`error is calculated at power step (l) of 0.5m as is measured
`using the configurable output power of the Skyetek-M9 UHF
`RFID reader 1. The average error of the different patterns are
`shown in Fig. 5. As evident, most of the calculated errors
`are below l/2. Despite low errors, there are certain locations
`(outside the tetrahedron space) that are affected by a non-
`intersecting spheres. This results into an invalid solution, i.e.,
`unable to estimate its location. In Fig. 5, the error values of
`more than 2m are not shown because the error values are either
`less than 2m or are the location points with invalid solution.
`the number of unestimated location is affected directly by the
`power step. Fig. 6 shows the effect of the powering stepping
`value on the overall error estimation of a randomly moving tag
`in an area of 40mx40m. The value of l is increased from 0.1m
`to 10.1m with a step of 1m at a time. The bright rectangles
`in Fig. 6 are the locations where no estimation is possible.
`
`B. APAA Scheme
`APAA scheme is also evaluated using the random movement
`illustrated in Fig. 4. The same values of the random paths that
`are used in testing the APM scheme are used to test the APAA
`scheme. In this scheme, The main parameters affecting the
`accuracy are defined by the angle step θsand the power step
`l. The scheme is evaluated for l=0.5m 1, and smart antennas
`with resolution of θs=10◦
`[6].
`As is depicted in Fig. 7, the overall accuracy of the APAA
`scheme is high and is void of any invalid solutions. However,
`for |θv| and |θh| angles greater than 45◦
`the accuracy starts to
`drop since the area covered in between θv and θh increases
`dramatically, (Area labeled 1 in Fig. 3-b has θh > 45◦
`,
`whereas Area labeled 2 has θh < 45◦
`).
`to 45◦
`In Fig. 8, the angle stepping from 1◦
`shows a linear
`trend with the error estimation when the RFID tags are sensed
`within −45◦
`and 45◦
`of the horizontal and vertical smart
`antennas. For the case when |θv| and |θh| angles are greater
`
`1http://www.skyetek.com/ProductsServices/EmbeddedRFIDReaders/
`SkyeModuleM9/tabid/208/Default.aspx
`
`Fig. 5. Average error in APM in a tetrahedron with a depth of 10m. Tx
`=[1:1:10], Ty= 40m, Tz=40m, l= 0.5m
`
`location in APAA scheme will fit in some angle and power
`level which guarantees a solution.
`
`IV. PERFORMANCE EVALUATION
`In this section, the proposed schemes are evaluated for
`its accuracy and efficiency compared to other schemes in
`liteature. The accuracy of the two schemes is tested using
`identical random movement patterns. Fig. 4 illustrates the test-
`ing methodology for the two schemes. The random movement
`patterns are lines with a fixed X coordinate (Tx in Fig. 4)
`and values of Y and Z coordinates are fluctuating randomly
`around the lines pattern. Tx determines the distance, from
`the reader, at which the schemes are tested. Ty is the hight
`of the testing sheet with array of lines, which will create a
`sheet of random movements at Tx meters from the reader. The
`random movements lengths are also bounded by Tz on the Z-
`coordinate. By changing the value of Tx, the 3D space will be
`covered in the evaluation of both schemes. The reader model
`and power stepping are simulated in MATLAB simulation tool.
`
`A. APM Scheme
`the accuracy of APM scheme is
`As discussed earlier,
`dictated mainly by the collinearity between the readers and
`the power stepping. In the testing of the APM scheme four
`non collinear readers are placed, as in Fig. 3-a, to maximize
`the accuracy. However, the power step is the main determining
`factor in the accuracy of the scheme since it defines the
`intersection points and therefore, making the desired solution
`as either valid or, if possible, invalid.
`
`4
`
`

`
`This full text paper was peer reviewed at the direction of IEEE Communications Society subject matter experts for publication in the IEEE ICC 2010 proceedings
`
`Scheme
`Alippi [4]
`APM
`APAA
`LANDMARC [3]
`SpotOn [2]
`
`System
`accuracy
`0.6m
`0.32m 3
`0.48m 3
`1.81m
`cluster size
`
`Advantages /
`Disadvantages
`passive tags / 2D
`3D / deploy sensitive
`3D / antenna resolution
`active tags only / 2D
`3D / dual. freq tags
`
`TABLE I
`COMPARISON OF VARIOUS LOCALIZATION SCHEMES
`
`RFID tag’s passive replies in order to estimate the power
`levels at which the tag is responsive. The first scheme, namely
`adaptive power multilateration, provides a high accuracy when
`at least four non-collinear readers are available with their
`intersecting interrogation range. The second scheme, namely
`adaptive power with antenna array, utilizes the AoA measure-
`ment and adaptive power levels to estimate the location of
`passive RFID tags in 3D. Our simulation results show that
`the proposed schemes provides accurate localization services
`hence, making them suitable for diverse RFID application, e.g.
`supply chain management, robotic guidance systems, apparel
`industry and many others.
`
`REFERENCES
`[1] Y. Gwon; Jain, R.; Kawahara, T., “Robust indoor location estimation of
`stationary and mobile users,” IEEE INFOCOM, pp. 1032-1043, March
`2004.
`[2] J. Hightower, R. Wantand and G. Borriello, “SpotOn: an indoor 3D
`location sensing technology based on RF signal strength,” Technical
`Report, University Of Washington, Department Of Computer Science
`And Engineering, 2000.
`[3] L. M. Ni, Y. Liu, Y. C. Lau and A. P. Patil, “LANDMARC: indoor
`location sensing using active RFID,” Proceedings of IEEE International
`Conference on Pervasive Computing and Communication, pp. 407-415,
`2003.
`[4] C. Alippi, D. Cogliati and G. Vanini, “A statistical approach to localize
`passive RFIDs,” in Proceedings of the IEEE International Symposium
`on Circuits and Systems (ISCAS), pp.843-846, 2006.
`[5] X. Li, Y. Zhang, and M. G. Amin, “Multifrequency-based range esti-
`mation of RFID tags,” in Proc. IEEE Int. Conf. RFID, pp. 147-154,
`2009.
`[6] D. Zhou, R. A. Abd-alhameed, P. S. Excell, C. H. See, M. M. Abusitta,
`Y. F. Hu, S. M. R. Jones, and N. J. Mcewan “Design of beam steering
`antenna array for RFID reader using fully controlled RF switches,”
`Progress in Electromagnetics Research Symposium, pp. 471-477, 2008.
`[7] J-W. Choi; D-I Oh; I-Y Song, “R-LIM: an affordable library search
`system based on RFID,” Proceedings of International Conference on
`Hybrid Information Technology, ICHIT, pp. 103-108, Nov. 2006.
`[8] S. Sakagami, S. Aoyama, K. Kuboi, S. Shirota, A. Akeyama, “Vehicle
`position estimates by multibeam antennas in multipath environments,”
`IEEE Trans. on Vehicular Technology, vol.41, no.1, pp. 63-68, 1992.
`[9] E. Doukhnitch, M. Salamah and E. Ozen “An efficient approach for
`trilateration in 3D positioning,” Computer Communications, vol.31
`no.17, pp. 4124-4129, 2008.
`[10] K. Ali, H. Hassanein, and A. M. Taha, “RFID Anti-collision Protocol
`for Dense Passive Tag Environments,” Proceedings of the 32nd IEEE
`Conference on Local Computer Networks, pp. 819-824, 2007.
`[11] K. Finkenzeller, “RFID Handbook: Fundamentals and Applications in
`Contactless Smart Cards and Identification,” John Wiley & Sons, Inc.,
`2003.
`
`Fig. 7. Average error in the APAA. With Tx=[1:1:10], Ty= 40m, Tz=40m,
`l= 0.5m
`
`Fig. 8. Error trend for angle steps between 1◦
`Ty= 40m, Tz=40m, l=0.5m.
`
`to 90◦
`
`. with Tx=[1:1:10],
`
`than 45◦
`, the quadratic increase in the area dominates the error
`estimation in the scheme. This is because the contribution of
`power stepping, in the total error, is no longer comparable to
`the area increase (i.e. no matter how small the power step is,
`the area is the main factor in the error calculation).
`A comparison between APM, APAA and other schemes
`from the literature are summarized in Table I. Due to space
`limitation, only a few metrics are used for comparison. The
`existing localization schemes has very coarse localization
`accuracy, only support 2D tag localization or are not designed
`for passive tag locations. On the other hand, both APM and
`APAA schemes support 3D passive RFID tag localization.
`The APAA scheme support reader and tag mobility with
`an acceptable localization error. The APM scheme shows
`the highest accuracy in comparison to [2]–[4] making it an
`efficient localization solution for certain applications such as
`patient monitoring, warehouse containers localization, and so
`forth. Whereas, mobility support along with relatively high
`accuracy makes the APAA scheme a suitable solution for item
`level localization and tracking, tunnel and mine operations, and
`dense environments.
`
`V. CONCLUSION
`Two indoor localization schemes using two different ap-
`proaches have been proposed to localize objects, with an
`attached RFID tag, in 3D space. The schemes benefit from
`
`2calculated at l = 0.5m using Skyetek M9 RFID reader
`
`5