978-1-4244-6857-7/10/$26.00 ©2010 IEEE
`301
`2010 5th International Symposium on Wireless Pervasive Computing (ISWPC)
`
`Kirti Chawla, Gabriel Robins, and Liuyi Zhang
`Department of Computer Science, University of Virginia
`Charlottesville, Virginia, 22904, USA
`{kirti, robins, lz3m}@virginia.edu
`
`methodology indoors to localize stationary objects, our
`framework is quite general and can be applied to many other
`scenarios, including outdoor environments, 3D localization,
`moving objects, various tag types, different combinations of
`tags, antennas and readers, etc. Our framework is highly
`scalable and can accommodate a wide range of requirements
`and tradeoffs among power, cost, accuracy and speed.
`We implemented, tested and evaluated the proposed
`framework, and experimentally confirmed its accuracy, speed
`and reliability in localizing objects. In order to ensure high
`reliability and accuracy in localization, our methodology
`addresses various practical issues such as “binning” the
`calibrated tags according to their detection sensitivities, which
`can vary significantly even among “identical” tags (due to
`manufacturing variability).
`This paper is organized as follows. In Section II, we
`describe the proposed localization framework. We present
`several localization algorithms and heuristics in Section III.
`We experimentally evaluate the proposed framework in
`Section IV, and conclude in Section V with extensions and
`future directions.
`
`II. THE LOCALIZATION FRAMEWORK
`The proposed localization method is based on continuously
`varying the power levels of the RFID readers in order to infer
`distance and position information about target tags. We use
`reference tags at known locations to help calibrate the power
`vs. distance relationships, and we employ several readers in
`order to reduce the localization uncertainty when inferring the
`position of target tags, as illustrated in Figure 1.
`
`
` RFID reader Target tag Reference tag
` Radio wave Localization error Intersection region
`
`
`
`
`
`
`
`
`
`
`
`
`
`Figure 1. Working principle of the proposed localization method
`
`Object Localization Using RFID
`
`
`Abstract — Object localization is a key primitive in pervasive
`computing environments, where numerous applications depend
`on the rapid and accurate position estimation of objects. We
`present a general RFID–based localization framework that
`reliably determines the positions of objects with unprecedented
`accuracy and speed. This is achieved by varying the power levels
`of the RFID readers, calibrated against reference tags of known
`sensitivity. Our implementation and experiments are able to
`localize objects to an accuracy of 15 cm within a few seconds, and
`this compares favorably with previous techniques. We also
`suggest several practical optimizations for further enhancing the
`speed and accuracy of the method.
`
`Keywords –RFID, localization, positioning algorithms
`
`I.
` INTRODUCTION
`is
`technology
`identification (RFID)
`Radio frequency
`rapidly transforming pervasive computing applications by
`offering new capabilities and a richer user experience [13].
`Capabilities such as object identification, real time tracking,
`and object localization are at the heart of numerous innovative
`RFID applications [9] [11]. While RFID technology enables
`object identification and tracking, it does not normally include
`object localization (i.e., positioning) capabilities. We propose
`to address this limitation by developing an RFID–based
`localization framework that accurately and quickly determines
`the positions of objects. In other words, our system offers a
`GPS-like positioning capability in an RFID environment.
`Obstacles to localization accuracy, speed and reliability,
`include environmental interferences and occlusions (e.g., the
`presence of liquids and metals), orientation and spatial
`arrangement of tags, ambient RF noise, tag sensitivity
`variations, readers' locations, etc. These factors can weaken,
`scatter, or occlude radio waves, and thus lead to unreliable
`detection and inaccurate positioning of objects [4] [5].
`Several RFID-based localization techniques have been
`proposed, either focusing on mobile objects (e.g., a robot) or
`stationary objects (e.g., a wallet) [6] [7] [12] [14]. However,
`previous techniques tend to sacrifice speed and accuracy in
`localizing objects in order to obtain reliable estimates (i.e.,
`repeated measurements should consistently yield the same
`outcome). Unfortunately, these resulting speed and accuracy
`degradations tend to reduce the efficacy of client applications.
`We propose a localization framework that enables accurate
`object position estimation, without compromising either speed
`or reliability. Our localization method varies the power levels
`of the readers, calibrated against a set of reference tags of
`known sensitivity, to accurately estimate target tag positions
`in a region of interest. Although we initially tested this
`
`APPLE EXHIBIT 1010
`Page 1 of 6
`
`

`

`302
`
`detection range. Thus, stepping the power level down instead
`of up will tend to reduce the average number of iterations to
`determine the minimum detection power level.
`
`
`
`Figure 2 describes this algorithm, called “Algorithm I”.
`The algorithm takes as input a unique tag id (Tag_ID), power
`(Power_Step),
`step
`and
`increment
`direction
`flag
`(Direction_Flag), and returns the minimum reader power
`level at which that tag becomes detectable. The time this
`algorithm requires to process a tag is linearly proportional to
`the number of distinct power levels used during the search.
`Thus, to process N tags using P power levels, this algorithm
`will run within time O(N⋅P) in the worst case.
`The overall running time can be further reduced by using a
`binary search on the power level instead of a linear search.
`This will enable a faster convergence on the minimum
`detection power level, requiring at most O(N⋅log P) steps to
`process N tags with a resolution of P power levels. We call
`this binary–search based approach “Algorithm II”.
`Another efficiency optimization leverages the capability of
`an RFID reader to simultaneously detect a large number of
`tags during the same read cycle. Therefore, instead of
`invoking Algorithm I separately for each tag ID, we can have
`it determine at each iteration all the tags that are detectable at
`that power level, and separately update the status of each one.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Input: Tag_ID, Power_Step, Direction_Flag
`Output: Minimum detection power level
`
`if (Direction_Flag = LOW_TO_HIGH) then
` Power = MIN_POWER_LEVEL
` repeat
` if (Power > MAX_POWER_LEVEL) then
` return NOT_FOUND
` end
` Set reader power-level to Power
` Search for tags until successful or time-out
` if Tag_ID is found then
` return Power
` end
` Power = Power + Power_Step
` end
`else
`
` Power = MAX_POWER_LEVEL
` Found_Power = NOT_FOUND
`
` repeat
`
` if (Power < 0) then
` return NOT_FOUND
`
` end
`
` Set reader power-level to Power
` Search for tags until successful or time-out
`
` if Tag_ID is found then
`
` Found_Power = Power
`
` else
`
` return Found_Power
` end
`
` Power = Power – Power_Step
`
` end
`
`end
`
`
`Figure 2. Algorithm I: Linear search for the minimum power-level
`
`Figure 1 depicts the intersection region covered by the
`lobes of radio waves emitted by different readers. Based on
`the relative power level that is necessary for a reader to detect
`a target tag, we can infer the distance between that tag and the
`reader. Moreover, several such power-distance correlations
`obtained from different readers can help localize a target tag
`with greater precision.
`The reference tags serve as a practical mechanism used to
`initially calibrate the power vs. distance relationships, in order
`to avoid relying on possibly erroneous formulas, unpredictable
`environmental conditions, etc. This constitutes a “feedback
`mechanism” that enables our system to dynamically adapt to
`unknown variables (e.g., noise, occlusions, interferences, etc.)
`that may adversely affect tag readability and localization.
`While the use of reference tags ascertains the actual power-
`distance relationships, it may also introduce errors in position
`estimates of target tags. When target tags are detected by
`varying the reader power levels, positions of the reference tags
`detected at the same power-level are used to infer (by
`interpolation) the position of target tags. This is a source of
`possible localization error, as depicted in above illustration.
`We apply different heuristics to minimize this error, based on
`the minimum reader power
`levels necessary
`to detect
`reference and target tags, as detailed in the next section.
`
`III. ALGORITHMS AND HEURISTICS
`that
`We now describe
`three
`localization algorithms
`incorporate the basic principles of the proposed localization
`framework, discuss possible sources of localization error, and
`present heuristics to minimize the error. The proposed
`localization method uses varying reader power levels to infer
`the position of target tags. We give three localization
`algorithms that control this key parameter (i.e., reader power
`level) in different ways in order to establish tradeoffs between
`accuracy and speed, as described below.
`A. Localization Algorithms
`In the first localization algorithm, we linearly increment the
`reader power level to determine the minimum power level at
`which reference (and therefore target) tags are detected. The
`variable Power_Step determines the size of the power level
`increment. The convergence time for the algorithm to find the
`minimum power level for tag detection is dependent on this
`Power_Step variable (i.e., the smaller this step size, the longer
`it may take to reach the desired detection threshold, but could
`yield greater localization accuracy). For example, if power
`level is varied between 0 and 33 dBm, and the Power_Step is
`0.25 dbm, then this algorithm will iterate up to (33 / 0.25) + 1
`= 133 times to ascertain the minimum detection power level.
`The algorithm varies the reader power level from lowest to
`highest to determine a minimum tag detection power level
`(other possible power varying strategies will be discussed
`later). While this approach finds the minimum detection
`power levels, it may require too long to converge. Optionally,
`we can instead vary the power level from highest to lowest,
`since tags are not typically located very near the reader, but
`rather are often found closer to the far end of the reader
`
`APPLE EXHIBIT 1010
`Page 2 of 6
`
`

`

`303
`
`H :Min (
`2
`∀
`J,K
`≠
`J K
`
`∑
`
`I=1
`
`(R )+
`J
`
`I
`
`∑
`
`I=1
`
`(R ))
`K
`
`I
`
`H :Min (
`3
`∀
`J,K
`≠
`J K
`
`M
`
`∑
`
`I=1
`
`Δ
`
`(R )+
`J
`
`I
`
`M
`
`∑
`
`I=1
`
`Δ
`
`(R ))
`K
`
`I
`
`
`
`J,K are neighbors
`
` (1)
`
`
` (2)
`
`
` (3)
`
`
`
`
`
`2) Minimum Power Reader Selection: This heuristic
`employs the minimum detection power levels from two
`(orthogonal) readers to compute the absolute difference
`between the power levels of the neighbouring reference and
`target tags. Two such heuristic variations are given as follows:
`
`
`
` (5)
`
`
` (6)
`
`J,K are neighbors
`
`(T)+
`
`Δ
`
`Δ
`(T));Min (
`∀
`S,J
`
`J
`
`Δ
`(R )),Min (
`S
`∀
`Q,K
`
`K
`
`(R ))
`Q
`
`K
`
`J
`
`Δ
`H : Min (
`9
`∀
`J,K,S,Q
`J K
`S Q
`
`≠≠
`
`(T)+
`
`Δ
`
`Δ
`(T));Min (
`∀
`S,J
`
`J
`
`Δ
`(R )),Min (
`S
`∀
`Q,K
`
`K
`
`(R ))
`Q
`
`K
`
`J
`
`Δ
`H : Min (
`10
`∀
`J,K,S,Q
`J K
`S Q
`
`≠≠
`
`S,Q are neighbors
`
`
`
`
`
`
`H :Min (
`4
`∀
`J,K
`≠
`J K
`
`M
`
`∑
`
`I=1
`
`Δ
`
`(R )+
`J
`
`I
`
`M
`
`∑
`
`I=1
`
`Δ
`
`(R ));
`K
`
`I
`
`M
`
`∑
`
`I=1
`
`Δ
`
`(R )<
`J
`
`I
`
`M
`
`∑
`
`I=1
`
`Δ
`
`I
`
` (4)
`(R )
`K
`
` = Target tag
`RI = Reference tag I
`H = Heuristic
`Power = Minimum detection power level for a tag
`M = Number of readers
`ΔΙ(R) = |Power(T) – Power(R)|
`S, Q, J, K= Iteration variables for neighbourhood tags
`I = Iteration variable for unmarked tag
`L = Heuristic iteration variable
`
`
`The above positioning heuristics are used as a post-
`processing step in our localization algorithm, once the
`minimum detection power levels of the reference and target
`tags have been determined. By employing different
`combinations of
`localization algorithms and positioning
`heuristics, a desired level of accuracy can be achieved.
`A key feature of the proposed framework is the flexibility
`to incorporate new localization algorithms and heuristics that
`may be developed in the future, which can enable the
`framework to localize objects with higher accuracy and speed.
`
`IV. EXPERIMENTAL EVALUATION
`In this section, we present our experimental evaluation
`methodology,
`report
`results
`regarding
`tag
`sensitivity,
`localization accuracy and speed, and compare the overall
`approach to existing techniques.
`
`
`3) Root Sum Square Absolute Difference: In
`these
`heuristics, we compute the square root of the sum of squares
`of the absolute difference between the minimum detection
`power levels of the neighbouring reference and target tags.
`The following heuristic variations are based on this approach:
`
`
`H :Min (
`5
`∀
`J
`
`M
`
`∑
`
`I=1
`
`Δ
`
`(R ) )
`2
`J
`
`I
`
`H :Min (
`6
`∀
`J,K
`≠
`J K
`
`H :Min (
`7
`∀
`J,K
`≠
`J K
`
`Δ
`
`(R ) +
`2
`J
`
`I
`
`M
`
`∑
`
`I=1
`
`M
`
`∑
`
`I=1
`
`M
`
`∑
`
`I=1
`
`Δ
`
`(R ) +
`2
`J
`
`I
`
`Δ
`
`(R ) +
`2
`J
`
`I
`
`J,K are neighbors
`
`Δ
`
`(R ) );
`2
`K
`
`I
`
`J,K are neighb
`ors
`
`M
`
`∑
`
`I=1
`
`M
`
`∑
`
`I=1
`
`Δ
`
`(R ) )
`2
`K
`
`I
`
`Δ
`
`(R ) )
`2
`K
`
`I
`
`M
`
`∑
`
`I=1
`
`Δ
`
`(R ) <
`2
`J
`
`I
`
`M
`
`∑
`
`I=1
`
`Δ
`
`I
`
`M
`
`∑
`
`I=1
`
`H :Min (
`8
`∀
`J,K
`≠
`J K
`
`
`
`
`
` (8)
`
`
` (9)
`
`
`
`
` (10)
`(R )
`K
`
`2
`
`4) All Heuristics Minimum:
` This “meta-heuristic”
`computes for a given target tag the minimum of all the other
`heuristics, as follows:
`
`H : Min(H )
`11
`L
`∀
`L
`
` (11)
`
`
`
`
`Where the following notation glossary applies to all of the
`above heuristics:
`
` T
`
` (7)
`
`
`
`Note that this is logically equivalent to running Algorithm I
`in parallel independently for each tag. Assuming that the
`number of tags does not exceed the maximum simultaneous
`tag reading capacity of the reader, this strategy will require
`O(P) steps using a resolution of P power levels, independently
`of the number of tags. We call this parallel–based approach
`“Algorithm III”.
`There are several sources of possible “localization errors”,
`including the “round off” error inherent in identifying a target
`tag with the “nearest” reference tag, as well as the errors
`inherent in the algorithms for estimating the minimum
`detection power level. We next discuss these errors and
`outline techniques to mitigate them.
`B. Localization Error Mitigation Heuristics
`Apart from the errors discussed above, other factors that
`contribute to localization errors include variability in tag
`sensitivity and environmental interferences [5]. In Section IV,
`we discuss the impact of variability in tag sensitivity on
`localization errors, and suggest practical methods to reduce it.
`We now present eleven heuristics for mitigating localization
`errors, grouped into four broad categories as follows.
`1) Absolute Difference: This heuristic takes into account
`the absolute difference between the minimum detection power
`levels for the neighbouring reference tags and the target tags.
`We suggest four heuristic variations of this type:
`
`
`H :Min (
`1
`∀
`J
`
`M
`
`∑
`
`I=1
`
`Δ
`
`(R ))
`J
`
`I
`
`M
`
`Δ
`
`M
`
`Δ
`
`APPLE EXHIBIT 1010
`Page 3 of 6
`
`

`

`304
`
`A. Experimental Setup
`We evaluated the proposed localization framework to
`localize stationary objects in an indoor environment using one
`reader connected to four antennas. Our goals for this
`evaluation were to first classify the tags based on their
`detection sensitivity (i.e., “binning” them by quality), then
`ascertain the localization accuracy and speed of the proposed
`method, and finally compare the overall performance with
`existing
`localization
`techniques.
` Table I details
`the
`experimental setup used in our experiments.
`
`
`TABLE I
`EXPERIMENTAL SETUP DETAILS
`
`Type
`
`Technology Parameters
`
`CPU
`
`RAM
`
`AMD Athlon 64
`@ 2 GHz
`1 GBytes
`
`Hard Disk
`
`100 GBytes
`
`OS
`Prog.
`Support
`API
`
`Reader
`
`ThingMagic M4
`
`Protocol
`
`Workstation
`
`RFID
`Backend
`
`Environment
`
`Antenna
`Sector
`Map Area
`Room
`Volume
`
`Linear
`
`Readers
`
`6 square meters
`
`41 cubic meters
`
`EPC Gen2
`UHF passive
`tags (96 bit)
`
`Antennas
`References
`Tags
`
`Model
`
`Tags
`
`Type
`
`
`
`WinXP
`
`C++/C#
`
`M4 LIB
`EPC
`Gen2
`1
`
`4
`
`32
`Impinj
`“Dogbone
`Monza 3”
`93×23mm
`
`Our experiment was deployed in a rectangular region
`having an area of 6 square meters (2m × 3m). This region was
`divided into eight equal sub-regions called “sectors”, each
`having an area of 0.75 square meters (1m × 0.75m).
`Furthermore, we divide each sector into four equal-sized sub-
`sectors called “quadrants”, each having an area of 0.19 square
`meters (0.5m × 0.375m), as shown in Figure 3.
`One reference tag was placed in each quadrant, with a total
`of 32 reference tags evenly distributed throughout the entire
`region. The tag type we used was an EPC Gen2 96-bit UHF
`passive tag, model “Dogbone Monza 3”, manufactured by
`Impinj, Inc.
`B. Binning Tags According to their Sensitivity
`the
`Manufacturing variability can dramatically affect
`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” altogether. The accuracy of our
`localization methodology depends on the uniformity of the
`detection sensitivities across all tags, while the localization
`speed will increase with higher tag sensitivities. As a pre-
`processing quality-control check, we therefore tested and
`characterized the sensitivities of all the tags, to ensure that
`only tags with similar (and high) sensitivities are used in our
`localization experiments.
`
`
`
` R
`
` Top-left
`
`
`
`
`Q
`
`
`
`S
`
`T
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` Bottom-right
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Figure 3. The experimental region with sectors (S), quadrants (Q), reference
`tags (T), and reader antennas (R)
`
`
`Our experimental evaluation showed that tag sensitivity
`varied considerably across a group of 243 tags of the same
`type. We have characterized the tag sensitivities based on the
`read counts using different reader power levels. Thus, given a
`reader power level, if a tag has low read counts among its
`peers, we call it “non-sensitive”. Similarly, tags with high
`read counts relative to their peers are labelled as “highly
`sensitive”, while tags having equal read count are called
`“equally sensitive”.
`We have performed two experiments to quantify tag
`sensitivities by varying the power levels and distances
`between the readers and the tags. While these experiments
`used EPC Gen2 passive tags, our “tag binning” approach is
`equally applicable to other types of tags. We now describe
`these sensitivity analysis experiments in detail below.
`1) Constant Distance / Variable Power: In this experiment,
`a batch of four tags was positioned at a distance of 2.5 meters
`from the reader’s antenna, while the reader power level was
`varied 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 (3 read iterations lasting 20 seconds per iteration).
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Figure 4. Tag senstivity measurements for constant distance / variable power
`
`Cumulative Read Count Vs Number of Tags
`
`25.6 dBm
`
`28.6 dBm
`
`48
`
`36
`
`24
`
`12
`
`0
`
`0.0
`
`2.4
`
`4.8
`
`7.2
`
`9.6
`
`12.0
`
`14.4
`
`-6
`
`-3
`
`0
`
`3
`6
`31.6 dBm
`
`9
`
`12
`
`15
`
`25.6 dBm
`Mean
`4.263
`StDev 4.548
`N
`243
`28.6 dBm
`Mean
`8.979
`StDev 2.931
`N
`243
`31.6 dBm
`Mean
`9.251
`StDev 2.733
`N
`243
`
`0.0
`
`2.4
`
`4.8
`
`7.2
`
`9.6
`
`12.0
`14.4
`Cumulative Read Count
`
`100
`
`75
`
`50
`
`25
`
`0
`
`60
`
`45
`
`30
`
`15
`
`0
`
`Number of Tags
`
`APPLE EXHIBIT 1010
`Page 4 of 6
`
`

`

`305
`
`experiments, we selected all reference and target tags from
`this equally-sensitive tag set.
`C. Localization Accuracy and Speed
`We measured localization accuracy by determining the
`effect of the parameter Power_Step on the minimum detection
`power levels. This is accomplished by determining for a
`given target tag, the minimum detection power levels over
`different power steps. These measurements are given below.
`
`
`
`Accuracy: Power-step Vs Power-Level
`Variable
`Alg-I-Ant-I-HTL
`Alg-I-Ant-II-HTL
`Alg-I-Ant-I-LTH
`Alg-I-Ant-II-LTH
`Alg-II-Ant-I-HTL
`Alg-II-Ant-II-HTL
`Alg-II-Ant-I-LTH
`Alg-II-Ant-II-LTH
`Alg-III-Ant-I-HTL
`Alg-III-Ant-II-HTL
`
`30.0
`
`27.5
`
`25.0
`
`22.5
`
`20.0
`
`17.5
`
`15.0
`
`Power-level (dBm)
`
`
`
`
`
`
`
`
`
`
`
`
`
`0.125
`
`0.25
`0.5
`Power-step (dBm)
`
`1.0
`
`Figure 6. Power level comparison for algorithms I, II, and III
`
`
`Figure 6 gives the minimum detection power levels of a tag
`for four different power steps, measured using the three
`localization algorithms using
`two orthogonally placed
`antennas. Algorithm I (in low-to-high LTH mode) reports the
`lowest minimum detection power level, while Algorithm III
`(in high-to-low HTL mode) yields the highest minimum
`detection power level for the same tag for all the algorithms
`and power steps. Since localization accuracy is based on
`determining minimum detection power levels, the Algorithms
`I, II, and III are able to trade off accuracy and speed.
`The time required for localization is heavily dependent on
`the time required to detect tags. Figure 7 gives the time
`required to detect tags placed at eight random locations in the
`region for all three algorithms (using two orthogonal reader
`antennas). The data confirms our hypothesis that varying the
`power levels from high to low is typically more efficient for
`localizing tags farther away from the reader.
`While Algorithm II consistently requires less time to find
`tags, it yields sub-optimal minimum detection power level
`estimates, due to the coarser granularity of the binary search
`as compared to the linear search of Algorithm I. Also,
`Algorithm III requires the smallest search time to find tags,
`unless the tags are placed very near to the antennas, which
`then enables Algorithm I to find them more quickly.
`Thus, by combining different algorithms, we can choose
`appropriate application-driven tradeoffs between localization
`accuracy and localization speed.
`
`
`Figure 4 shows that 114 out of 243 tags had cumulative
`read counts of zero at 25.6 dBm, with most of the tags having
`read counts in the range of 3 to 9 (with some tags having read
`counts as high as 12). Moreover, at a reader power level of
`28.6 dBm, most of the tags had cumulative read counts in the
`range 6 to 12. Finally, at 31.6 dBm, the cumulative read
`counts all ranged between 5 and 12. Tags were labelled as
`non-sensitive if they had zero cumulative read counts at a
`power level of 25.6 dBm. Tags were labelled as non-sensitive
`at 28.6 dBm only if they were also labelled as non-sensitive at
`25.6 dBm. Similarly, we labelled tags as highly-sensitive at
`25.6 dBm only if they were labelled as highly-sensitive at 31.6
`dBm.
`Using this process, 89 out of 243 tags were marked as
`highly-sensitive, 133 tags as equally-sensitive, and the
`remaining tags were considered to be non-sensitive. Thus, this
`experiment classified all 243 tags into three sensitivity
`categories, based on reader power levels needed for detection.
`2) Variable Distance / Constant Power: In the second tag
`sensitivity experiment, we fixed the reader power level to 31.6
`dBm and varied the distance between the tags and the reader
`from 1.27 meters to 3.81 meters, in steps of 1.27 meters. We
`labelled tags as non-sensitive if they had low read counts at
`1.27 meters. Tags were labelled as non-sensitive at 2.54
`meters only if they were also labelled as non-sensitive at 1.27
`meters. Similarly, we labelled tags as highly-sensitive at 1.27
`meters only if they were also labelled as highly-sensitive at
`3.81 meters.
`This approach classified 61 out of the 243 tags as non-
`sensitive, 161 tags as equally-sensitive, and 21 tags as highly-
`sensitive, based on the minimum detection distances between
`the tags and the reader. Figure 5 gives the distribution of the
`cumulative read counts of the tags, taken over the three testing
`distances, for a duration of 60 seconds each.
`
`
`Cumulative Read Count Vs Number of Tags
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Figure 5. Tag senstivity measurements for variable distance / constant power
`
`1.27 Meters
`
`2.54 Meters
`
`40
`
`30
`
`20
`
`10
`
`0
`
`0.0
`
`2.4
`
`4.8
`
`7.2
`
`9.6
`
`12.0
`
`14.4
`
`0
`
`2
`
`4
`
`6
`8
`10
`3.81 Meters
`
`12
`
`14
`
`1.27 Meters
`Mean
`9.303
`StDev 2.742
`N
`243
`2.54 Meters
`Mean
`8.460
`StDev 3.284
`N
`243
`3.81 Meters
`Mean
`3.505
`StDev 4.240
`N
`243
`
`-6
`
`-3
`
`0
`
`3
`
`6
`
`9
`12
`Cumulative Read Count
`
`80
`
`60
`
`40
`
`20
`
`0
`
`120
`
`90
`
`60
`
`30
`
`0
`
`Number of Tags
`
`Based on the combined outcomes of these two sensitivity
`experiments, we classified 133 tags as equally-sensitive (i.e.,
`by taking the intersection of the equally-sensitive tag sets
`from each experiment).
` In our ensuing
`localization
`
`APPLE EXHIBIT 1010
`Page 5 of 6
`
`

`

`306
`
`REFERENCES
`
`
`[1] C. Alippi, D. Cogliati, and G. Vanini, “A Statistical Approach to
`Localize Passive RFIDs”, IEEE International Symposium on Circuits
`and Systems (ISCAS 2006), Island of Kos, Greece, Sep. 2006, pp. 843-
`846.
`[2] T. F. Bechteler and H. Yenigun, “2-D Localization and Identification
`Based on SAW ID-Tags at 2.5 GHz”, IEEE Transactions on Microwave
`Theory and Techniques, IEEE Press, Vol. 7, Issue. 2, May 2003, pp.
`1584-1590.
`[3] A. Bekkali, H. Sanson, and M. Matsumoto, “RFID Indoor Positioning
`based on Probabilistic RFID Map and Kalman Filtering”, 3rd
`International Conference on Wireless and Mobile Computing,
`Networking and Communications (WiMOB 2007), New York, Oct.
`2007, pp. 21-21.
`[4] L. Bolotnyy and G. Robins, “The Case for Multi-Tag RFID Systems”,
`IEEE International Conference on Wireless Algorithms, Systems and
`Applications (WASA 2007), Chicago, Aug. 2007, pp. 174-186.
`[5] L. Bolotnyy and G. Robins, “Multi-tag RFID systems”, Security in
`RFID and Sensor Networks, Auerbach Publications, CRC Press, Taylor
`& Francis Group, 2009, pp. 3-28.
`[6] M. Bouet and A. Santos, “RFID Tags–Positioning Principles and
`Localization Techniques”, IFIP Wireless Days – 2nd International Home
`Networking Conference (IHN 2008), Dubai, UAE, Nov. 2008.
`[7] L. Jing and P. Yang, “A Localization Algorithm for Mobile Robots in
`IEEE
`International Conference on Wireless
`RFID
`system”,
`Communications, Networking and Mobile Computing (WICOM 2007),
`Shanghai, China, Sep. 2007, pp. 2109-2112.
`[8] D. Joho, C. Plagemann, and W. Burgard, “Modeling RFID Signal
`Strength and Tag Detection for Localization and Mapping”, IEEE
`International Conference on Robotics and Automation (ICRA 2009),
`Kobe, Japan, May 2009, pp. 3160-3165.
`[9] X. Liu, M. Corner, and P. Shenoy, “Ferret: RFID Localization for
`Pervasive Multimedia”, Lecture Notes in Computer Science, Berlin,
`Germary, Springer Press, Sep. 2006, Vol. 4206/2006, pp. 422-440.
`[10] L. Ni, Y. Liu, Y. Lau, and A. Patil, “LANDMARC: Indoor Location
`Sensing Using Active RFID”, 1st International Conference on Pervasive
`Computing (PerCom 2003), Arlington, Texas, Dec. 2003, pp. 407-415.
`[11] D. Papadogkonas, G. Roussos, and M. Levene. “Discovery and Ranking
`of Significant Trails”, 2nd International. Workshop on Exploiting
`Context History in Smart Environments (ECHISE 2006), Irvine, CA,
`Sep. 2006.
`[12] T. Sanpechuda and L. Kovavisaruch, “A Review of RFID Localization:
`Applications and Techniques”, 5th International Conference on
`Electrical Engineering/Electronics, Computer, Telecommunications and
`Information Technology (ECTI-CON 2008), Krabi, Thailand, Vol. 2,
`May 2008, pp. 769-772.
`[13] P. J. Sweeney, “RFID for Dummies”, Wiley Publishing, New Jersey,
`2005.
`[14] T. Wada, N. Uchitomi, Y. Ota, T. Hori, K. Mutsuura, and H. Okada, “A
`Novel Scheme for Spatial Localization of Passive RFID Tags;
`IEEE
`Communication Range Recognition
`(CRR) Scheme”,
`International Conference on Communications (ICC 2009), Dresden,
`Germany, IEEE Press, Jun. 2009, pp. 1-6.
`[15] C. Wang, H. Wu, and N. Tzeng, “RFID-Based 3-D Positioning
`IEEE
`International Conference
`on Computer
`Schemes”,
`Communications (INFOCOM 2007), Alaska, May 2007, pp. 1235-1243.
`[16] J. Zhou and J. Shi, “RFID Localization Algorithms and Applications—a
`Review”, Journal of
`International Manufacturing, Netherlands,
`Springer Press, Aug. 2008, pp. 695-707.
`
`
`Speed: Random Location Vs Time
`Variable
`Alg-I-Ant-I-HTL
`Alg-I-Ant-II-HTL
`Alg-I-Ant-I-LTH
`Alg-I-Ant-II-LTH
`Alg-II-Ant-I-HTL
`Alg-II-Ant-II-HTL
`Alg-II-Ant-I-LTH
`Alg-II-Ant-II-LTH
`Alg-III-Ant-I-HTL
`Alg-III-Ant-II-HTL
`
`1
`
`2
`
`3
`4
`5
`6
`Stationary Object Random Location
`
`7
`
`8
`
`Figure 7. Search time comparison for algorithms I, II, and III
`
`25
`
`20
`
`15
`
`10
`
`5
`
`0
`
`
`
`Time (Seconds)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Table II compare our proposed framework with existing
`localization techniques. We report separately the run times
`for the “setup stage” (calibration using reference tags) and the
`“localization stage” (localizing target tags). Note that the
`setup stage is performed only once at the beginning of the
`experiment. In summary, our approach is able to localize
`objects with an average accuracy of 15cm, and an average run
`time under 26 seconds using two antennas (or 54 seconds
`using four antennas in order to yield higher accuracy).
`
`
`TABLE II
`COMPARISON OF THE PROPOSED FRAMEWORK WITH EXISTING
`RFID-BASED LOCALIZATION TECHNIQUES
`Average time (min)
`Test area
`(square
`Setup
`Localization
`meters)
`Stage
`Stage
`NR
`NR
`NR
`NR
`NR
`20
`~27
`NR
`NR
`NR
`NR
`NR
`NR
`NR
`NR
`NR
`NR
`NR
`NR
`NR
`9
`6
`0.72
`19.3
`0.48
`14.7
`0.91
`3.6
`
`Technique
`
`Ni et al [10]
`Alippi et al [1]
`Joho et al [8]
`Zhou et al [16]
`Bechteler et al [2]
`Wang et al [15]
`Bekkali et al [3]
`Proposed
`Framework
`Algorithms I, II, III
`* NR – Not Reported
`
`Error
`(meters)
`
`~2
`0.68
`0.375
`0.19
`0.2
`0.1 – 0.9
`0.5 – 1.0
`0.08 – 0.31
`Avg.= 0.15
`
`V. CONCLUSION
`We proposed a low-cost and efficient object localization
`framework using RFID. The framework is quite general and
`can be extended to many different environments, scenarios,
`and types of RFID readers and tags. Future work includes
`reducing the average time required to localize an object,
`improving the localization accuracy, and testing in different
`environments (e.g., outdoors, 3D space, moving objects etc.).
`
`ACKNOWLEDGMENT
`This research is supported by National Science Foundation
`grant CNS-0716635 (PI: Professor Gabriel Robins). We
`thank the anonymous reviewers for their helpful suggestions.
`
`APPLE EXHIBIT 1010
`Page 6 of 6
`
`