978-1-4244-7742-5/10/$26.00 ©2010 IEEE
`683
`IEEE International Workshop on Selected Topics in Mobile and Wireless Computing
`
`Gabriel Robins
`Department of Computer Science
`University of Virginia
`Charlottesville, VA, 22904, USA
`robins@virginia.edu
`
`
`
`
`Efficient RFID-Based Mobile Object Localization
`
`Kirti Chawla
`Department of Computer Science
`University of Virginia
`Charlottesville, VA, 22904, USA
`kirti@virginia.edu
`
`Liuyi Zhang
`Department of Computer Science
`University of Virginia
`Charlottesville, VA, 22904, USA
`lz3m@virginia.edu
`
`We have implemented, tested, and evaluated the proposed
`approach to confirm its general applicability, scalability, and
`reliability. Our approach suits a wide-range of requirements
`and tradeoffs including accuracy, speed, cost, and power. We
`have also identified several key challenges (e.g., environmental
`interferences, tag sensitivity, spatial arrangements of tags etc.)
`that adversely affect the performance of RFID-based object
`localization, and we propose mitigating techniques.
`This paper is organized as follows. In section II, we
`describe related research efforts to localize mobile objects
`based on RFID technology. Several localization challenges and
`mitigating techniques are presented in section III. We present
`our localization approach in section IV, discuss implementation
`details and results in section V, and conclude in section VI with
`future research directions.
`
`II. RELATED WORK
`RFID-based localization for mobile objects can be broadly
`classified into tag and reader-based localization techniques,
`wherein position estimates of tags and readers attached to such
`objects are determined. In this paper, we focus on the
`localization of mobile objects by utilizing the far-field radio-
`wave interaction between the RFID tags and readers (i.e., other
`RF-based localization approaches utilizing near-field, surface
`acoustic waves, microwaves, GPS, etc. are outside the scope of
`this work). Related research work includes the following.
`Chae and Han [5] describe a two-step approach to localize
`mobile robots in an indoor environment. In their first step, an
`onboard RFID reader is coarsely localized with respect to
`neighborhood active reference tags. In the second step, a vision
`sensor combined with a feature detection algorithm identifies
`key environmental features to minimize the localization error to
`an average of 0.23 meters. Their approach is less applicable in
`different scenarios as the onboard vision sensor requires a
`sufficiently illuminated environment and objects must be
`within line-of-sight (a fundamental drawback that RFID was
`intended to eliminate in the first place).
`Choi and Lee [8] propose to localize mobile robots in an
`indoor environment by utilizing ultrasonic sensors
`in
`combination with an onboard reader. In the first stage, the
`global position of the mobile robot is estimated through
`onboard reader localization with respect to the neighborhood
`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,
`
`Abstract—Location-awareness of mobile objects is the key to
`numerous emerging ubiquitous computing applications. We show
`that RFID technology can be leveraged to achieve mobile object
`localization in an inexpensive, power efficient, scalable, widely
`applicable, flexible, and user-friendly manner. We outline the
`challenges that can adversely affect RFID-based localization
`techniques, and propose solutions to mitigate them. We present
`several algorithms for RFID-based mobile object localization that
`compare favorably or exceed previous methods in terms of
`accuracy, speed, reliability, scalability, and cost.
`
`Keywords - RFID, Object localization, RFID-based positioning
`
`I.
`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,
`and chemical spills), locating points of interests (e.g., ATMs,
`banks, and hospitals), and automated inventory management
`[1, 2, 9, 10, 13, 15, 16, 17, 24]. Such applications require
`capabilities that include object identification, real-time object
`tracking, and position localization.
`While typical RFID technology is sufficient for object
`tracking and identification, it does not normally provide object
`localization capabilities. Several RFID-based
`localization
`techniques for mobile objects have been proposed [5, 8, 11,
`12]. However,
`these
`localization
`techniques
`tend
`to
`compromise key requirements such as accuracy, speed, power,
`cost, scalability, and reliability, which severely degrade the
`utility of these methods. Moreover, some previous localization
`methods also require cumbersome non-RFID technologies such
`as ultrasonic sensors, vision sensors, cameras, etc.
`We propose to address these limitations by developing a
`scalable and reliable RFID-based localization approach that
`accurately and quickly determines the positions of mobile
`objects. Our approach consists of two separate techniques to
`localize target tags, as well as localize readers attached to
`mobile objects. To localize 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 reference tags. Moreover, these two approaches can be
`combined to yield even higher accuracy and efficiency.
`
`This research is supported by National Science Foundation grant CNS-0716635
`(Principal Investigator: Professor Gabriel Robins).
`
`APPLE EXHIBIT 1011
`Page 1 of 8
`
`

`

`684
`
`but rather a sound-based approach and is thus highly limited by
`issues such as environmental noise, line-of-sight, etc.
`Hähnel et al [11] propose using 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 localization errors in the 1 to 10 meters range.
`Han et al [12] propose mobile object localization by using
`reference tags and onboard mobile readers. Localization error
`is minimized using a triangular tag arrangement scheme,
`yielding average localization error of 0.09 meter in a small test
`region of one meter square. Koch et al [14] propose mobile
`object localization technique based on passive and active
`reference tags and onboard readers. Position estimates of the
`mobile objects can be determined within 0.1 meter accuracy on
`average.
`Milella et al [18] utilize an onboard monocular camera, a
`reader and a tag bearing estimation technique based on “fuzzy
`inference system” to localize mobile robots. The average
`localization error is 0.64 meter. Senta et al [20] present a
`mobile robot localization technique based on reference tags,
`onboard readers, and a support vector machine (SVM)-based
`machine learning approach. This method yields localization
`errors of over 0.2 meters, and is limited by the spatial tag
`arrangement, measurement noise, and tag-reader proximity.
`Seo and Lee [21] describe a mobile object localization
`system that transmits an RFID signal from an onboard reader to
`the neighborhood beacon, which in turn responds with an
`ultrasonic signal. The estimated distance is computed based on
`the time difference between transmitted and received signals,
`with an average localization error in the range of 0.2 to 1.6
`meters. Vorst et al [23] present a mobile object localization
`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
`localization error in the range of 0.2 to 0.6 meters.
`The effectiveness 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 numbers of onboard
`components, high
`localization delays, and heavy power
`requirements [5, 8, 11, 18]. 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, as shown by Chawla,
`Robins, and Zhang [6]. Thus, instead of addressing and
`mitigating these basic principles (as we do in this paper),
`previous research efforts resort to Herculean efforts to reduce
`errors on other fronts, often resulting in a hodgepodge of ad-
`hoc and ineffectual techniques.
`
`III. LOCALIZATION CHALLENGES
`All RFID-based localization techniques have inherent
`position estimate errors due
`to various external (e.g.,
`environmental) and internal (e.g., RFID tags and reader related)
`factors. This section describes key
`issues
`that
`induce
`localization errors and propose techniques to mitigate them.
`
`A. Interferrence and RF Occlusion
`Environmental factors such as radio noise and occlusions
`by liquids or metals can cause radio-wave scattering and
`attenuation, which can in turn result in localization 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 localization accuracy [22].
`Deploying more tags and readers in the experimental region
`can also reduce adverse interference and occlusion effects.
`
`B. Tag Sensitivity
`Tag detection sensitivity is characterized 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 the chip’s high impedance state [19]. 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 position estimation errors. To address
`this issue, we propose a pre-processing step of sorting (i.e.,
`“binning”) the tags based on their detection sensitivities, and
`classify them as “highly sensitive”, “average sensitive” and
`“low sensitive” using read measurements over different power
`and distance combinations [6]. This enables only uniformly-
`sensitive tags to be deployed in the same experiment, resulting
`in more meaningful and consistent experimental results.
`Curiously, previous works all seem to ignore this critical issue.
`
`C. Tag Spatiality
`RFID-based mobile localization techniques typically utilize
`reference tags placed in known locations. The positions of
`these reference tags can significantly affect the localization
`accuracy, and regular placements of reference tags tend to yield
`lower positioning errors, as opposed to random arrangements.
`
`D. Tag Orientation
`Tag and reader interaction is significantly affected by the
`tag orientation. For example, Bolotnyy and Robins analyzed
`how tag orientation impacts the tag detection probability [3, 4].
`In particular, they discovered that when multiple tags are
`placed on same object, orthogonal orientations yield much
`higher detection probabilities than parallel orientations.
`
`
`
` (a)
`
` (b)
`
`Figure 1. Tag orientations: (a) 3D orthogonal, (b) Planar orthogonal
`
`APPLE EXHIBIT 1011
`Page 2 of 8
`
`

`

`685
`
`E. Reader Locality
`Theoretically, the RFID power-distance relationship is
`characterized based on the Friis transmission equation given as
`follows [7]:
`
`
`
`
`
`
`Here, PR is the power transmitted by the reader, PT is the
`power received at the tag, GR and GT are the antenna gain 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, the variables λ, GR, and GT are the design parameters.
`Thus, by knowing the reader and tag power levels, the distance
`between them can be estimated. Alternatively, if the distance
`between the readers and tags are known, then the received
`power at the tags can be determined. Thus, the reader location
`impacts the localization accuracy. We propose that more tags
`should be placed in the region near the trajectory of mobile
`objects in order to improve the overall localization accuracy.
`Our main principle behind above mitigating techniques is
`“to identify and minimize possible errors at the sources where
`they arise”. This leads to efficient localization techniques,
`fewer onboard components, lower power requirements, and
`higher localization accuracy. In the following section, we use
`this principle to develop techniques for minimizing the mobile
`localization errors.
`
`IV. MOBILE OBJECT LOCALIZATION USING RFID
`The proposed localization approach utilizes two different
`techniques. In the first technique, an onboard reader and
`reference tags embedded in the environment are used to
`coarsely localize the mobile object. The second technique
`varies the power levels of environment-embedded readers to
`localize the onboard tag via the empirical power-distance
`relationship
`(calibrated using
`reference
`tags at known
`positions). To ensure uniform behavior from the tags, we test,
`sort, and select them on their (similar) detection sensitivity.
`Also, by employing multi-tags [3, 4], we reduce
`the
`uncertainties when inferring the position of onboard tags.
`Finally, we combine these localization techniques and propose
`several heuristics for significantly improving the localization
`accuracy.
`While tags are sorted, placed, and calibrated as part of
`offline pre-processing phase, the actual localization and error-
`minimization heuristics are performed in real-time. By dividing
`the task of localization into separate phases, we reduce the time
`required to estimate positions of mobile objects. We describe
`key aspects of the proposed localization approach below.
`
`Figure 1(a), shows a 3D object with multiple orthogonally
`oriented tags, and Figure 1(b) shows an orthogonal planar (i.e.,
`horizontal and vertical) orientations of two tags. In section IV,
`our experiments indicate that horizontal planar orientation
`increases tag sensitivity. Thus, utilizing multiple tags in
`orthogonal spatial and horizontal planar orientation improves
`localization accuracy.
`
`P
`R
`P
`T
`
`= G G
`R
`
`T
`
`λ
`4πD
`
`⎛
`⎜
`⎝
`
`2
`
`⎞
`⎟
`⎠
`
`(1)
`
`A. Calibrated Tags
`The accuracy of our localization approach relies on the tags
`having uniform detection sensitivities. Also, this property can
`help localization speed improve with higher tag sensitivities.
`Thus, as an offline pre-processing quality-control check, the
`sensitivities of all the tags are tested and characterized, to
`ensure that only tags with uniform (and high) sensitivities are
`used in our subsequent localization experiments. We have also
`developed a four-way multi-tag platform that provides higher
`operational reliability, as illustrated in Figure 2.
`
`
`
`
`
`
`
`
`
`Figure 2. A four-way multi-tag platform
`
`Figure 2 shows the design of our four-way multi-tag
`platform consisting of four “Impinj Dogbone Monza 3” UHF
`passive tags mounted on a vertical stand made of Lego bricks
`(our choice of Lego components is based on the versatility of
`Lego bricks as well as the transparency of their plastic material
`to radio-waves). We have built 33 such platforms, and each tag
`on the platform was calibrated separately using the techniques
`described by Chawla, Robins, and Zhang [6]. We have
`performed two types of platform calibration experiments to
`ensure uniform detection sensitivity across variables such as
`tag rotation and proximity, described as follows.
`1) Proximity Sensitivity Calibration: In this experiment,
`we ensured that the four-way multi-tag platforms consisting of
`four proximate equally sensitive tags (Figure 2) all have
`similar sensitivities. This was achieved by determining the
`average read count of constituent tags having matching
`orientations with respect to the reader’s antennas. Thus, tags at
`position one, two, three, and four were oriented towards
`antenna one, two, three, and four, respectively. We kept the
`reader power level constant at 31.6 dBm and varied the
`distance between the reader and the multi-tags within the
`range of 1.27 to 3.81 meters.
`
`We also varied the reader power level within the range of
`25.6 to 31.6 dBm, keeping the distance between them constant
`at 2.54 meters. We repeated the calibration experiment three
`times and computed the average. While the combination of
`power level and distance range was comparatively small,
`variations in the tag sensitivities are evident at this scale.
`Figures 3(a), 3(b), and 3(c) illustrate the results of this
`experiment by varying the distance and keeping the reader
`power constant. For example, at a distance of 2.54 meters
`away from the reader, position four yields the highest average
`read counts. This is due to antenna four being nearer to the tag
`at position four than antenna one. Also, at 2.54 meters tag
`position three yields the lowest average read count, due to the
`shape of the RF signal lobe emitted by the antenna. Similar
`conclusions can be drawn from Figures 3(d), 3(e), and 3(f).
`
`APPLE EXHIBIT 1011
`Page 3 of 8
`
`

`

`686
`
`2) Rotation Sensitivity Calibration: In this experiment, we
`determined the impact on tag sensitivity of rotating the multi-
`tag platforms. We varied the reader power level between 25.6
`and 31.6 dBm and kept the distance between the reader and
`the four-way multi-tag platform constant at 2.54 meters.
`Separately, we varied the distance between the reader and the
`four-way multi-tag platform within the range of 1.27 to 3.81
`meters and kept the reader power level constant at 31.6 dBm.
`We then rotated each multi-tag platform counter-clockwise,
`repeating each calibration three more times and computed
`their average.
`Figures 4(a)-4(l) and 5(a)-5(l) illustrate the impact of
`rotation on the average read-counts. In particular, each row of
`graphs depicts the average read count of four tags facing four
`antennas. When the platform is rotated counter-clockwise,
`these values are interchanged (e.g., tag at position one faces
`antenna one, and after a rotation, tag two takes that position
`and retains the read-count within permissible error range).
`By combining the calibration results from the proximity
`and rotation experiments, it is evident that the 33 four-way
`multi-tags consisting of individually equally-sensitive tags are
`sensitivity invariant. This provides confidence that using these
`uniformly-sensitive multi-tags
`in subsequent
`localization
`experiments will help to minimize uncertainties due to tag
`variations, measurement noise, spatial orientations, etc.
`
`B. Localization Approach
`We now describe the proposed mobile object localization
`approach that consists of two different techniques based on the
`four localization algorithms. In the first technique, we localize
`readers onboard the mobile objects with respect to an
`environment instrumented with stationary reference four-way
`multi-tags. We measure the encountered unique tag IDs as the
`object moves around
`the environment. We associate a
`timestamp with each such measurement, resulting in a list of
`tuples of the type 〈Tag ID, Timestamp〉. Thus, we determine
`the path of the mobile objects by knowing the location of
`
`reference tags and the measurement time. We call this
`algorithm “Measure and Report”.
`Mobile objects can be localized more accurately by using a
`regular arrangement of stationary reference tags. However, the
`limited read-range of the onboard reader, as well as the
`uncertainties in the actual locations of the reference tags, can
`introduce errors into the resulting position estimates. To
`minimize such errors, in our second technique we vary the
`power levels of the readers embedded in the environment in
`order to localize the target multi-tags onboard mobile objects
`using empirical power-distance relationships calibrated against
`reference tags. We provide three algorithms that control the
`reader power level in different ways, yielding tradeoffs
`between localization accuracy and overall speed.
`In the first algorithm, we linearly increment the reader
`power level from lowest to highest in order to determine the
`minimum power level required to detect reference and onboard
`multi-tags. While this approach finds the minimum tag
`detection power levels, it may take more time to converge.
`Alternatively, we can instead vary the power level from highest
`to lowest in order to detect tags, since tags are typically not
`located near readers. Thus, stepping down the power level (i.e.,
`from highest to lowest) will minimize the average number of
`iterations required to determine the minimum tag detection
`power level. We call this algorithm “Linear Search”.
`In the second algorithm, we start at a mid-value power
`level, and then either step-up or step-down based on the
`reader’s ability to find the tags. Thus, we can converge faster
`on the minimum power level required for tag detection. We call
`this algorithm “Binary Search”. Note that these two algorithms
`search for only one tag per execution cycle. Our third algorithm
`addresses this limitation by determining the minimum power
`levels of large groups of tags in parallel. Thus, it is equivalent
`to running a Linear Search algorithm in parallel for all the tags.
`This algorithm is called “Parallel Search”. Since Parallel
`Search can determine the minimum power-levels of onboard
`tags in parallel, it enables the simultaneous localization of
`multiple mobile objects.
`
`
`
`(a) (b) (c)
`
`(d) (e) (f)
`
`Figure 3. Multi-tag sensitivity measurements under proximity metric using constant-distance/variable-power and variable-distance/constant-power configurations.
`
`APPLE EXHIBIT 1011
`Page 4 of 8
`
`

`

`687
`
`
`
`(a) (b) (c) (d)
`
`(e) (f) (g) (h)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(i) (j) (k) (l)
`
`Figure 4. Multi-tag sensitivity measurements under rotation metric using variable-distance/constant-power configuration
`
`(a) (b) (c) (d)
`
`
`(e) (f) (g) (h)
`
`
`(i) (j) (k) (l)
`
`Figure 5. Multi-tag sensitivity measurements under rotation metric using constant-distance/variable-power configuration.
`
`Table I gives the time complexity of each algorithm. While
`the Measure-and-Report algorithm is the fastest algorithm, both
`the Linear Search and Binary Search algorithms
`take
`
`considerably more time due to their operating in a serial
`manner. Since, the Parallel Search algorithm is independent of
`the number of tags and only dependent on the number of power
`
`APPLE EXHIBIT 1011
`Page 5 of 8
`
`

`

`688
`
`C. Localization Error and Heuristics
`Localization errors occur in the first technique (i.e.,
`onboard reader localization) due to limitations in the power and
`read-range of the onboard reader. Since mobile objects can
`move arbitrarily, an inexpensive and reliable way to reduce this
`type of error is by placing more densely/regularly arranged
`reference tags in the nearby region. In the second technique
`(i.e., onboard tag localization), errors in position estimates
`occur by identifying the onboard multi-tag with the nearest
`neighborhood reference tags.
`
` RFID antenna Target tag Reference tag Radio wave Localization error
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Figure 6. Sources of localization errors.
`
`Figure 6 depicts four antennas emitting radio waves
`forming an intersection region where onboard target tags (i.e.,
`four-way multi-tag platforms) are likely to be present. This
`intersection region gives coarse-level position estimates of the
`four-way multi-tag platforms, which is further refined by using
`the positions of nearby reference tags to estimate the positions
`of multi-tags. However, this can lead to potential “round off”
`
`levels, it requires less time than the Linear Search or Binary
`Search algorithms. Moreover, the algorithms that take more
`time tend to generate higher resolutions of the minimum power
`level required to detect tags. Alternatively, the faster algorithms
`trade off localization accuracy for speed.
`
`TABLE I.
`Localization
`Technique
`Reader Localization
`
`Tag Localization
`
`Time Complexity
`O(1)
`O(N·P)
`O(N·LogP)
`O(P)
`
`TIME-COMPLEXITY OF LOCALIZATION ALGORITHMS
`Localization
`Algorithm
`Measure and Report
`Linear Search [6]
`Binary Search [6]
`Parallel Search [6]
`N = Number of tags, P = Number of reader power levels used
`We can utilize these algorithms in different combinations to
`trade off localization accuracy, speed and power requirements.
`Furthermore, localization errors can occur due to (1) the
`onboard reader operating range, (2) implicitly identifying the
`four-way multi-tag platforms with the nearest reference tags,
`and (3) the inherent minimum power level estimation errors of
`the algorithms. We discuss these errors along with mitigating
`techniques below.
`
`errors. In order to minimize possible localization errors, we
`have developed eleven heuristics that utilize the differences in
`the reader power levels, the orthogonal positions of the readers,
`and the neighborhood reference tags. We describe these error
`mitigation heuristics in detail below.
`
`TABLE II.
`
`LOCALIZATION ERROR HEURISTICS
`
`Error Heuristic
`
`Absolute Difference [6]
`
`Minimum Power
`Reader Selection [6]
`
`Root Sum Square
`Absolute Difference [6]
`
`Meta-Heuristic [6]
`
`
`
`Description
`Compute the absolute difference of the reader power
`levels between the neighborhood and onboard multi-
`tags. There are four such heuristics.
`Compute the absolute difference of the power levels
`between the neighborhood and onboard multi-tags
`using the minimum power levels of the two orthogonal
`readers. There are two such heuristics.
`Compute the square root of the sum of squares of the
`absolute difference of the reader power levels between
`the neighborhood and onboard multi-tags. There are
`four such heuristics.
`Compute the minimum over all power levels obtained
`using above the heuristics. Thus, it is a meta-heuristic
`that enables minimum tag detection power levels.
`
`V. EXPERIMENTS AND RESULTS
`This section presents the implementation details, evaluation
`methodology, and experimental results pertaining to the
`proposed mobile object localization approach. Furthermore, we
`compare the proposed localization approach with existing
`mobile object localization techniques. Our experiments were
`performed in an indoor environment using one onboard reader
`and one four-way multi-tag platform per mobile object. Also,
`one stationary reader, four antennas, and 33 reference tags were
`embedded in the surrounding environment. Table III describes
`the experimental setup and implementation details.
`
`TABLE III.
`
`EXPERIMENTAL SETUP DETAILS
`
`Type
`
`Workstation
`
`RFID
`Equipment
`
`Environment
`
`Robots
`
`CPU
`RAM
`Hard Disk
`Reader
`Type
`
`Antenna
`
`Tag
`
`Map Area
`Room
`Volume
`Kit
`
`Onboard Control
`
`Model
`
`Technology Parameters
`AMD Athlon
`OS
`64 @ 2GHz
`PL
`1 GBytes
`API
`100 GBytes
`ThingMagic
`M4 iDtronic
`Voltaire CF
`Linear with
`6dBi gain
`Impinj
`Dogbone
`Monza 3
`93x23 mm
`8 m2
`41 m3
`Lego
`Mindstorms
`HP iPAQ
`hx2490
`
`Protocol
`
`Reader
`Devices
`
`Antennas
`
`Reference
`Multi-Tags
`
`Robots
`
`PDAs
`
`Onboard Link
`
`Type
`
`Bluetooth
`
`Bluetooth
`Dongles
`
`
`
`WinXP
`C++/C#
`M4 LIB
`EPC
`Gen2
`
`3
`
`6
`
`33
`
`2
`
`2
`
`2
`
`We developed two mobile robots using Lego Mindstorm
`kits. Figure 7(a) illustrates the mobile robots with their onboard
`controller consisting of one HP iPAQ hx2490, one iDtronic
`Voltaire portable RFID reader, and one four-way multi-tag
`platform. Figure 7(b) depicts our experimental railroad track
`for operating these mobile robots. Also, shown are the four-
`
`APPLE EXHIBIT 1011
`Page 6 of 8
`
`

`

`689
`
`way multi-tag platforms used as the reference tags. We
`coarsely localize the mobile objects by utilizing the onboard
`reader to read the reference tags encountered during motion
`and transmit the tag IDs to the backend workstation using the
`onboard bluetooth link. At any location we can further refine
`the coarse-level position estimates by varying the stationary
`reader power levels to localize the onboard multi-tags.
`
`
`
`
`
`
`
`
`
`
` (a) (b)
`
`Figure 7. Experiment components: (a) Mobile robot platform, and (b) Track
`
`Note that approaches that utilize only RFID technology for
`precise localization impose speed limits on the moving objects
`due to the delays inherent in determining the minimum tag
`detection power levels, and the reader's operational speed.
`Thus, while coarser position estimates can be obtained for tags
`moving at several meters per second, slower speeds are still
`necessary for more precise localization. Such locomotion speed
`limitations are also present in other existing RFID-based
`mobile object localization techniques.
`A key aspect of the proposed localization approach is to
`limit/eliminate the use of onboard non-RFID components,
`while still obtaining good localization accuracy and speed. This
`approach enables low on-board power consumption, as well as
`reduced overall cost and complexity. Our localization apparatus
`uses a single rechargeable 1440 mAh Lithium-Ion battery for
`the onboard PDA control, RFID reader and bluetooth link.
`Thus, by reducing the needed onboard components, we reduce
`the power requirements of the mobile objects. Furthermore, to
`improve localization speed, we divide the proposed localization
`approach into a setup phase and a localization phase, thus
`decoupling the initial time-consuming calibration process from
`
`the subsequent localizations of the mobile objects.
`During the setup phase, we distributed 33 reference tags
`across a 2D region and calibrated their empirical power-
`distance relationships. In the localization phase, we estimated
`positions by using the proposed localization approach. For each
`phase, we utilized the localization algorithms in different
`combinations in order to minimize localization errors. We used
`the Linear Search algorithm in the setup phase, while the
`Binary Search algorithm was used in the localization phase,
`combined with the Measure and Report algorithm. Figures 8(a)
`and 8(b) illustrate the localization accuracy independently
`along the X and Y-axis. Our data confirms that along both axes
`the proposed localization approach closely approximates the
`actual mobile robot positions.
`Also, we hypothesized that increasing the number of
`reference tags increases the localization accuracy only up to a
`certain point. To test this hypothesis, we varied the number of
`references tags from 1 to 33 and determined that the range of
`localization error varied from 1.2 to 0.2 meters, as depicted in
`Figure 8(c). Thus, addi