`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`2
`
`
`
`
`
`Int. J. Radio Frequency Identification Technology and Applications, Vol. 3, Nos. 1/2, 2011
`
`
`
`An RFID-based object localisation framework
`
`Kirti Chawla* and
`Gabriel Robins
`Department of Computer Science,
`University of Virginia,
`Charlottesville, 22904, USA
`Email: kirti@virginia.edu
`Email: robins@virginia.edu
`*Corresponding author
`
`Abstract: Numerous ubiquitous computing applications depend on the
`ability to locate objects as a key functionality. We show that Radio Frequency
`Identification (RFID) technology can be leveraged to achieve object localisation
`in an inexpensive, reliable, flexible, and scalable manner. We outline the
`challenges that can adversely affect RFID-based localisation techniques, and
`propose practical mitigating solutions. We present several new algorithms for
`RFID-based object localisation that compare favourably with previous methods
`in terms of accuracy, speed, reliability, scalability, and cost.
`
`Keywords: RFID; RFID-based positioning; object localisation; localisation
`algorithms; power-distance relationship.
`
`Reference to this paper should be made as follows: Chawla, K. and Robins, G.
`(2011) ‘An RFID-based object localisation framework’, Int. J. Radio Frequency
`Identification Technology and Applications, Vol. 3, Nos. 1/2, pp.2–30.
`
`Biographical notes: Kirti Chawla is currently a PhD student in the Department
`of Computer Science at the University of Virginia. He received an MTech in
`Information Technology from the Indian Institute of Technology (IIT) in 2003.
`His research interests include RFID, ubiquitous computing, computer security,
`wireless sensors, and embedded systems. He co-authored five refereed
`publications and three patents. From 2003 to 2007 he held software engineering
`and research positions at Samsung Electronics (India), Samsung Semiconductor
`(South Korea), and the Prabhu Goel Research Centre (India). He is a member
`of IEEE, ACM, and the Cryptology Research Society of India.
`
`Gabriel Robins is Professor of Computer Science at the University of Virginia.
`He received a PhD in Computer Science from UCLA in 1992. His research
`interests include algorithms, optimisation, RFID, VLSI CAD, and bioinformatics.
`He co-authored a book and almost 100 refereed papers. His recognitions
`include a Packard Foundation Fellowship, a National Science Foundation Young
`Investigator Award, the SIAM Outstanding Paper Prize, and several teaching
`awards. He served on the US Army Science Board, and on the editorial
`boards and technical programme committees of several leading journals and
`conferences. He consults as an expert witness in major intellectual property
`litigations.
`
`
`
`Copyright © 2011 Inderscience Enterprises Ltd.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`APPLE EXHIBIT 1012
`Page 1 of 29
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`1
`
`An RFID-based object localisation framework
`
`3
`
`Introduction
`
`The confluence of Radio Frequency Identification (RFID) and other wireless technologies
`lies at the heart of many emerging applications, such as remote medicine, robotic teams,
`wireless sensing, early warning systems (e.g. for tsunamis, earthquakes, chemical spills,
`etc.), locating points of interests (e.g. ATMs, banks, hospitals, etc.), and automated
`inventory management (Abowd and Mynatt, 2000; Hightower and Borriello, 2001;
`Mattern, 2001; Satyanarayanan, 2001; Estrin et al., 2002; Romer and Domnitcheva,
`2002; Vogt, 2002; Fontelo et al., 2003; Schilit, 2003; Merrell et al., 2005; Muthukrishnan
`et al., 2005; Romer et al., 2005; Blewitt et al., 2006; Liu et al., 2006; Wang et al.,
`2007; Want, 2008). Such applications require capabilities that include real-time object
`identification, object tracking, and position localisation.
`While typical RFID technology is sufficient for object tracking (i.e. registering the
`presence/absence of an object in a radio field) and identification (i.e. matching an
`onboard RFID tag ID with a trusted database), it does not normally provide object
`localisation capabilities (i.e. precisely locating the position of an object). Several RFID-
`based localisation techniques for stationary and mobile objects have been proposed
`(Ni et al., 2003; Alippi et al., 2006; Senta et al., 2007; Milella et al., 2009). However,
`these techniques tend to compromise key requirements such as accuracy, speed, cost,
`scalability, and reliability, thus severely degrading the utility of these methods. Moreover,
`some previous localisation methods also require cumbersome non-RFID technologies
`such as ultrasonic sensors, vision sensors, cameras, and lasers, which again make them
`unsuitable for practical use in typical environments.
`We address these limitations by developing a scalable and reliable RFID-based
`localisation framework that accurately and rapidly determines the positions of stationary
`and mobile objects. Our approach consists of separate techniques to localise target tags,
`as well as localise readers attached to mobile objects. To localise stationary and mobile
`target tags, we vary the reader power levels over a set of calibrated reference tags having
`known sensitivities. Separately, we determine the positions of target mobile readers by
`measuring their proximity to known reference tags. Moreover, these two approaches can
`be combined to yield even higher accuracy and efficiency.
`We implemented, tested, and evaluated the proposed approach to confirm its general
`applicability, scalability, and reliability. Our approach suits a wide range of requirements
`and trade-offs including accuracy, speed, and cost. We have also identified several key
`challenges (e.g. environmental interferences, tag sensitivity, spatial arrangement of tags,
`etc.) that adversely affect the performance of RFID-based object localisation, and we
`propose mitigating techniques.
`This paper is organised as follows. Section 2 describes related research work in
`RFID-based object localisation. We formulate the problem of object localisation using
`RFID in Section 3. Section 4 presents several localisation challenges and mitigating
`techniques. We describe our object localisation framework in Section 5, and discuss the
`experimental evaluation and results in Section 6. Section 7 outlines key lessons learned,
`and Section 8 concludes with future research directions.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`APPLE EXHIBIT 1012
`Page 2 of 29
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`4
`
`
`
`K. Chawla and G. Robins
`
`2 Related work
`
`Recent advances in ubiquitous computing have necessitated RFID-based object localisation
`capabilities, with research efforts specifically targeting the positioning of either stationary
`or mobile objects. RFID-based localisation techniques can be broadly classified as reader
`and tag-based approaches. In reader-based localisation techniques, the positions of RFID
`readers are ascertained, while in tag-based localisation techniques, the positions of RFID
`tags are determined. Note that RFID tags and readers can each be either stationary or
`mobile. In this paper, we focus on pure-RFID object localisation techniques, utilising
`only the interaction between RFID readers and tags (i.e. other RF-based approaches
`utilising near-field propagation, surface acoustic waves, microwaves, cameras, ultrasonics,
`etc., are outside the scope of this work, and arguably are not as useful in many RFID
`scenarios). Existing RFID-based stationary object localisation techniques are described
`below.
`Ni et al. (2003) propose placing active reference tags and determining the Euclidean
`distance between the reference and the target tags. K-nearest reference tags are used to
`determine the position estimates of a target tag, with a maximum localisation error of less
`than two metres. Alippi et al. (2006) model the indoor localisation problem as a non-
`linear stochastic inversion problem. Their experimental 2D environment has multiple
`readers at fixed locations and tags at unknown locations. Data is gathered using multiple
`antennas at different orientations. A conditional probability-based model is used, wherein
`tag detection probabilities vary at different power levels, yielding an average localisation
`error of 0.68 metres. Bekkali et al. (2007) use two mobile readers, a probabilistic RFID
`map, and a Kalman filter-based technique to minimise the localisation error variance.
`Position estimates of the target tags are determined using a Received Signal Strength
`Indicator (RSSI)-based metric, and a probability density function generates the probability
`map for each reference tag. The localisation error of this approach has a root mean square
`in the range of 0.5 to 1 metres.
`Joho et al. (2009) develop a probabilistic sensor model based on the tag RSSI
`measurement, the antenna orientation, and tag location. A mobile reader moves through
`the environment to gather tag measurements and correlates them with the true locations.
`Multiple iterations are required to improve the tag position estimates, resulting in an
`average localisation error of 0.375 metres. Zhang et al. (2007) introduce the concept of
`virtual tags and a proximity map. Their key idea is to consider the presence of virtual tags
`with the reference tags. The RSSI values of virtual tags from each reader are calculated
`using a linear interpolation algorithm. Different proximity maps are generated for each
`reader, and the intersection of these maps is used to determine the location of the target
`tags. The localisation error of this approach is in the range of 0.14 to 0.29 metres.
`Wang et al. (2007) propose a 3D tag positioning scheme, wherein reference tags are
`placed either on the floor or ceiling and at least four readers are placed on the vertices of
`a hexahedron. Readers gradually increase their transmission power until responses are
`received from the reference and target tags. Statistical averaging and the simplex method
`are used to reduce the localisation error to a range of 0.1 to 0.9 metres, but at the cost
`of high hardware expense and long positioning times. Choi and Lee (2009) study the
`characteristics of a passive UHF RFID system and propose an RSSI-based localisation
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`APPLE EXHIBIT 1012
`Page 3 of 29
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`An RFID-based object localisation framework
`
`5
`
`approach using passive tags. The K-nearest neighbours algorithm is utilised to compute
`the differences of the RSSI-based metric of various reference tags in order to localise a
`single target tag, with an average localisation error of 0.21 metres.
`Hekimian-Williams et al. (2010) utilise the phase difference of the signals received
`at two separate antennas to localise the active tags. Additionally, they make use of
`software-defined radios coupled with accurately sampled clocks to implement various
`phase difference estimation algorithms. Thus, clock precision is an important factor in
`determining the localisation accuracy. While their system yields high accuracy under
`ideal conditions, they do not take into account key factors such as multi-path scattering
`and tag sensitivity. Jin et al. (2006) propose to improve the localisation accuracy of the
`LANDMARC system (Ni et al., 2003) by selecting only a few reference tags that have
`the least distance from a target tag. They utilise multiple readers to localise the target tags
`to within an average localisation accuracy of 0.72 metres. Zhang et al. (2007) propose
`using the direction of arrival of tag responses in order to localise the target tags.
`Simulations indicate an average localisation error of 1 metre. However, the effects of
`multi-path scattering, environmental interferences, and tag sensitivity variations are not
`considered.
`Some RFID-based positioning techniques are specifically designed to localise mobile
`objects (as opposed to stationary ones). For example, Chae and Han (2005) propose a
`two-step approach to localise mobile robots in an indoor environment. In their first step,
`an onboard RFID reader is coarsely localised with respect to neighbourhood active
`reference tags. In the second step, a vision sensor combined with a feature detection
`algorithm identifies key environmental features to minimise the average localisation error
`to 0.23 metres. Their approach is less applicable in different scenarios since the onboard
`vision sensor requires a sufficiently illuminated environment and objects must be within
`line-of-sight (a fundamental drawback that RFID technology was intended to eliminate in
`the first place).
`Choi and Lee (2009) propose to localise mobile robots in an indoor environment by
`utilising ultrasonic sensors in combination with an onboard reader. Their localisation
`approach has two stages. In the first stage, the global position of the mobile robot is
`estimated through onboard reader localisation with respect to the neighbourhood passive
`reference tags. The second stage uses ultrasonic sensors for local position estimates.
`While their approach can yield higher accuracy, it is inherently not a pure RFID-based
`method, but rather a sound-based approach and is thus highly limited by issues such as
`environmental noise, line-of-sight, echoes, etc.
`Hähnel et al. (2004) propose a laser range scanner combined with an RFID reader
`onboard a mobile robot. The laser range scanner is used to learn a map comprised of
`reference tags, which in turn is used to estimate the position and orientation of mobile
`robots. However, this approach imposes line-of-sight constraints, and moreover tag
`orientation issues degrade the detection probability of the reference tags, resulting in high
`localisation errors in the 1 to 10 metres range. Han et al. (2007) propose a mobile object
`localisation technique by using reference tags and onboard mobile readers. They show
`that the particular spatial arrangement of tags affects the localisation error and propose a
`triangular tag arrangement scheme to minimise it. Their approach yields an average
`localisation error of 0.09 metres in a small test region of one metre square.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`APPLE EXHIBIT 1012
`Page 4 of 29
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`6
`
`
`
`K. Chawla and G. Robins
`
`Milella et al. (2009) utilise an onboard monocular camera, a reader and a tag bearing
`estimation technique based on a ‘fuzzy inference system’ to localise mobile robots
`to within an average error of 0.64 metres. Senta et al. (2007) present a mobile robot
`localisation technique based on reference tags, onboard readers, and a support vector
`machine (SVM)-based machine learning approach. This method yields localisation errors
`of over 0.2 metres, and is limited by the tag spatial arrangement, measurement noise, and
`tag-reader proximity. Seo and Lee (2008) describe a mobile object localisation system
`that transmits an RFID signal from an onboard reader to the neighbourhood beacon,
`which in return responds with an ultrasonic signal. The estimated distance is computed
`based on the time difference between transmitted and received signals, with an average
`localisation error in the range of 0.2 to 1.6 metres. Vorst et al. (2008) present a
`mobile object localisation approach using reference tags, onboard readers, and a particle
`filter-based technique. They compare prior-obtained training data with real-time RFID
`measurements to yield an average localisation error in the range of 0.2 to 0.6 metres.
`Currently, the effectiveness of several of the previous approaches is hindered by
`reliance on line-of-sight techniques, combining multiple non-RFID (e.g. ultrasonic sensors,
`cameras, lasers, etc.) and RFID components in an ad-hoc manner, large number of onboard
`components, and high localisation delays (Chae and Han, 2005; Hähnel et al., 2004;
`Choi and Lee, 2009; Milella et al., 2009). Moreover, some of the above methods are too
`expensive or unwieldy due to the cost, size, and weight of the required infrastructure.
`Finally, the above approaches ignore the key issue that the RFID equipment itself can
`introduce significant amount of experimental errors. For example, previous works ignore
`the fact that ‘identical’ tags can have widely varying detection sensitivities, which can
`greatly affect the experimental outcomes (Chawla et al., 2010a; Chawla et al., 2010b).
`Thus, instead of addressing and mitigating these basic principles (as we do in our
`approach), previous research works resort to Herculean efforts in order to reduce the
`errors on other fronts, while ignoring bigger error sources, resulting in a hodgepodge of
`ad-hoc and sometimes ineffectual techniques.
`
`3 Problem statement: object localisation using RFID
`
`We address the problem of localising stationary and mobile objects by utilising ‘only’
`RFID-based technology (as opposed to relying on non-RFID technology such as lasers,
`ultrasonic sensors, cameras, etc.). In this section, we describe the underlying principles of
`the proposed approach and the key performance parameters for optimisation. RFID-based
`object localisation requires determining the positions of stationary and mobile objects
`affixed with tags and/or readers. Radio signal properties such as power-distance
`relationships can ascertain these locations. Theoretically, the radio wave’s power-distance
`relationship can be characterised based on the Friis transmission equation as follows
`(Finkenzeller, 2003):
`
`2
`
`
`
`(1)
`
`λ π
`
`D
`
`4
`
`=
`
`G G
`R
`T
`
`TP
`
`R
`P
`
`⎛
`⎞
`⎜
`⎟
`⎝
`⎠
`Here, PR is the power transmitted by the reader, PT is the power received at the tag, GR
`and GT are the respective antenna gains of the reader and the tag, λ is the radio wave
`wavelength, and D is the distance between the tag and reader. For a typical RFID system,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`APPLE EXHIBIT 1012
`Page 5 of 29
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`An RFID-based object localisation framework
`
`7
`
`variables such as λ, GR and GT are some of the main design parameters. Thus, by
`knowing the power levels at the reader and the tag, the distance between them can be
`estimated. Alternatively, if the distance between the readers and tags are known, then the
`received power level at the tags can be determined.
`Thus, our overall RFID localisation strategy is as follows. We slowly increase the
`reader’s power level from low to high in small increments. When a given tag becomes
`detectable to a reader for the first time, the power level at which this first detection event
`happens indicates the tag’s distance from that reader. As different readers perform such
`readings (from different directions), the tag’s position can be estimated with increasing
`accuracy by considering the intersections of these detection regions.
`Figure 1 illustrates a shared region induced by the geometric intersections of the radio
`wave lobes used to detect a tag by several readers. Such intersection regions, if small
`enough in size, can help minimise the error in position when estimating the locations of
`target objects using reference tags (i.e. regions overlapped by more radio wave lobes
`have a smaller area than other more peripheral regions covered by fewer lobes, resulting
`in increased localisation accuracy). Note, however, that this intuitive intersection-of-
`regions analogy is only a conceptual explanatory tool. Our system does not explicitly
`compute geometrical regions, nor is it even particularly aware of geometry in general.
`Rather, our system compares the detection power levels of target tags with those of
`known reference tags, in order to infer the target tag’s position. In other words, our
`approach is ‘relativised’ in that it tries to match the behaviours of known and unknown
`tags, under the key assumption that if the behaviours and responses of two tags are very
`similar, then their positions must be very close as well.
`
`Figure 1 A shared region induced by the intersection of radio wave lobes
`
` 
`
`
` RFID Antenna Intersection Region Radio Wave
`
`
`
`At first glance it may seem contradictory that a positioning system can be mostly
`oblivious to geometrical considerations. However, because of all the real-world factors
`that interfere with accurate RF transmission and reception, correlating a complex geometry
`with precise levels of RF receptivity is difficult. Our system sidesteps these complicated
`issues by ignoring the geometry, and instead takes a pragmatic relative approach by
`observing and comparing behaviours rather than trying to accurately predict them. Note
`that such an empirical approach naturally adapts and automatically calibrates to unknown
`conditions and unexpected effects, since these would presumably affect (identical) target
`and reference tags in a very similar way. Thus, the geometry-obliviousness feature of our
`system is not a weakness but rather a deliberate capability that yields performance
`advantages.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`APPLE EXHIBIT 1012
`Page 6 of 29
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`8
`
`
`
`K. Chawla and G. Robins
`
`In real-world scenarios, various ad-hoc interfering factors (e.g. environmental
`conditions, multi-path scattering, and RF occlusions due to liquids and metals, etc.) affect
`signal strengths and received power levels. Moreover, variability in detection sensitivities
`across ‘identical’ tags poses a unique challenge in reliably establishing and leveraging
`the empirical power-distance relationship. To understand the implications of this variability,
`consider two tags of the same type (e.g. ‘Impinj Dogbone Monza 3’ UHF passive tag)
`having different sensitivities (due to manufacturing variations).
`These tags, when kept at the same fixed location from the reader, will be initially
`detected at different reader power levels, thereby skewing the observed empirical power-
`distance relationship. Our proposed object localisation framework considers these
`challenges and takes the pragmatic approach of only using uniformly sensitive reference
`tags to establish the empirical power-distance relationship. Section 5.1 below will discuss
`this sensitivity analysis in greater detail.
`
`4 Localisation challenges
`
`As discussed above, all RFID-based object localisation techniques have inherent position
`estimate errors due to various external (e.g. environmental interferences) and internal
`(e.g. RFID tags and reader related) factors. This section describes several key challenges
`that could induce localisation errors and our proposed techniques to mitigate them.
`
`4.1
`
`Interference and RF occlusion
`
`Environmental factors such as radio noise and occlusions by liquids or metals (which
`tend to be opaque to RF signals) can cause radio wave scattering and attenuation, which
`in turn can result in localisation errors. Mitigating techniques such as electrostatic
`shielding, full Faraday cycle analysis, and path-loss contour mapping can help reduce the
`impact of such factors on localisation accuracy (Sweeney, 2005). Deploying more tags
`and readers in the region of interest can also reduce adverse effects due to interferences
`and occlusions.
`
`4.2 Tag sensitivity
`
`Tag detection sensitivity is characterised by the minimum power needed to read the tag at
`a particular distance. It is a function of chip threshold power sensitivity, tag antenna gain,
`and chip’s high impedance state (Nikitin and Rao, 2008). Moreover, tag manufacturing
`variability can dramatically affect the detection sensitivities of tags. Thus, tags with low
`sensitivities become invisible at shorter distances than their higher sensitivity counterparts,
`leading to localisation errors. To address this issue, we propose a pre-processing step of
`sorting (i.e. ‘binning’) the tags based on their detection sensitivities. We thus classify
`tags as ‘highly sensitive’, ‘average sensitive’, and ‘low sensitive’ using read measurements
`over different power and distance combinations (Chawla et al., 2010a; Chawla et al.,
`2010b), as detailed in Section 5 below. This enables only uniformly sensitive tags to
`be deployed in the same experiment, resulting in more consistent and meaningful
`experimental results. Curiously, previous works all seem to ignore this critical issue.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`APPLE EXHIBIT 1012
`Page 7 of 29
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`An RFID-based object localisation framework
`
`9
`
`4.3 Tag spatiality
`
`RFID-based object localisation techniques typically utilise reference tags placed at known
`locations. The positions and arrangements of these reference tags can significantly affect
`the localisation accuracy. Regular placements of the reference tags (as opposed to
`random arrangements) tend to yield lower positioning errors (Han et al., 2007).
`
`4.4 Tag orientation
`
`Tag orientation significantly affects tag and reader interaction. For example, Bolotnyy
`and Robins (2007a, 2007b, 2009) analysed how tag orientation impacts the tag detection
`probability. In particular, they discovered that when multiple tags are placed on the same
`object, orthogonal orientations yield much higher detection probabilities than parallel
`orientations.
`Figure 2a, shows a 3D object with multiple orthogonally oriented RFID tags. Figure 2b
`shows orthogonal planar (i.e. horizontal and vertical) orientations of two tags. In Section 5,
`our experiments indicate that horizontal planar orientations increase the tag’s sensitivity.
`Thus, utilising multiple tags in orthogonal spatial and horizontal planar orientations tends
`to improve the overall localisation accuracy.
`
`Figure 2 Tag orientations
`
` 
`
`
`
`(a) 3D orthogonal (b) Planar orthogonal
`
`
`
`4.5 Reader locality
`
`Theoretically, the usable power in the radio waves emitted by the reader attenuates
`inversely proportional to the cube (for near-field) and square (for far-field) of the
`distance (as given by the Friis transmission equation). This determines the operating/
`detection region for the tags with respect to the readers. Thus, the reader’s location and
`proximity to a tag impacts the tag’s localisation accuracy. We propose that more tags
`should be placed in regions likely to be nearer to the objects being localised in order to
`improve the overall localisation accuracy.
`The main guiding principle behind all the above mitigating techniques is to identify
`and minimise possible errors at the sources where they arise. This leads to efficient
`localisation techniques, fewer onboard components, higher localisation accuracy and speed.
`In the following section, we use this principle with the proposed object localisation
`framework to improve the localisation accuracy and speed.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`APPLE EXHIBIT 1012
`Page 8 of 29
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`10
`
`
`
`K. Chawla and G. Robins
`
`5 Object localisation framework
`
`The proposed localisation approach utilises two different techniques. In the first
`technique, an onboard reader and reference tags embedded in the environment are used
`to coarsely localise the mobile object. The second technique varies the power levels of
`environment-embedded readers to localise the onboard tag via the empirical power-
`distance relationship (calibrated using reference tags at known positions). To ensure uniform
`behaviour from the tags, we test, sort, and select them based on their (similar) detection
`sensitivity. Also, by employing multi-tags (Bolotnyy and Robins, 2007a; Bolotnyy and
`Robins, 2007b; Bolotnyy and Robins, 2009), we reduce the uncertainties when inferring
`tag positions. Finally, we combine these localisation techniques and propose several
`heuristics for significantly improving the localisation accuracy.
`While tags are sorted, placed, and calibrated as part of an offline pre-processing
`phase, the actual localisation and error minimisation heuristics are performed in real
`time. The calibration process may be repeated occasionally, in order to adjust the system
`to varying environmental conditions. Re-calibration may also be performed in parallel
`with actual localisation operations to accommodate ‘drifts’ in the empirical power-distance
`relationship. Below we describe key aspects of the proposed localisation approach.
`
`5.1 Tag sensitivity analysis
`
`Tag manufacturing variability can dramatically affect the detection sensitivity of tags (i.e.
`the minimum reader power level needed to successfully read a tag at a given location). In
`fact, a small fraction of any commercially obtained batch of tags are typically even
`‘dead’ (i.e. non-functional) altogether. While the localisation speed will increase with
`higher tag sensitivities, the accuracy of the proposed localisation framework depends on
`the uniform detection sensitivities of the tags. Thus, an offline pre-processing quality-
`control check provides a characterisation of the sensitivities to ensure that only tags with
`uniform (and reasonably high) sensitivities contribute to our subsequent localisation
`experiments.
`Our experimental evaluation showed that tag sensitivity varied considerably across a
`group of 243 tags of the same type. We have characterised the tag sensitivities based on
`the read counts under different reader power levels and distance combinations. Thus,
`given a fixed reader power level, if a tag has low read counts among its peers, we call it
`‘low sensitive’. Similarly, tags with high read counts are labelled as ‘highly sensitive’,
`and tags having equal read count are called ‘average sensitive’. We performed two
`experiments to quantify single tag sensitivities by varying the power levels and distances
`between the readers and the tags. While these experiments use EPC Gen2 passive tags,
`this tag binning approach is equally applicable to other types of RFID tags.
`
`5.1.1 Single tag calibration
`In this experiment, a batch of four tags was placed at a distance of 2.54 metres from the
`reader. We varied the reader power level from 25.6 dBm to 31.6 dBm, in steps of 3 dBm.
`We recorded the cumulative read counts of each tag for 60 seconds (i.e. 3 read iterations
`lasting 20 seconds each). We found that 114 out of 243 tags had cumulative read counts
`of zero at 25.6 dBm, while remaining tags had read counts in the range of 3 to 9 (some
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`APPLE EXHIBIT 1012
`Page 9 of 29
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`An RFID-based object localisation framework
`
`11
`
`tags had read counts as high as 10). Moreover, at a reader power level of 28.6 dBm, most
`of the tags had cumulative read counts in the range 6 to 11, and the cumulative read
`counts ranged between 5 and 11 at 31.6 dBm.
`We labelled tags as ‘low sensitive’ only if they had zero cumulative read counts at a
`power level of 25.6 dBm. Also, tags were labelled as ‘low sensitive’ at 28.6 dBm only
`if they were also labelled as ‘low sensitive’ at 25.6 dBm. Similarly, we labelled tags
`as ‘highly sensitive’ at 25.6 dBm only if they were also labelled as ‘highly sensitive’ at
`31.6 dBm. While the combination of power levels and distance ranges was comparatively
`small, variations in tag sensitivities were evident even at this scale. Using this process,
`89 out of 243 tags were classified as highly sensitive, 133 tags ranked as average
`sensitive, and the remaining tags were considered to be low sensitive (and some tags
`were dead altogether). Thus, this experiment classified 243 tags into three sensitivity
`categories based on the reader power levels required to detect them.
`Similarly, in another set of experiments, we kept the reader power level constant and
`varied the distance between the tags and the reader with the same increments as above.
`T