IDENTIFYING RFID CATEGORIES

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
1Forward
Citation 
0
Petitions 
4
Assignments
First Claim
1. . A tag for an RFID system, the RFID system further comprising a reader, the tag comprising:
 a memory adapted to store a tag identification (ID) value for the tag, the tag ID value comprising a category ID value and an instance value;
an antenna adapted to receive a downlink signal from the reader and transmit an uplink signal to the reader; and
a processor adapted to process the downlink signal and generate the uplink signal, wherein;
the processor is adapted to select at least one slot in a multislot frame based on the stored category ID value, but independent of the stored instance value; and
the tag is adapted to transmit the uplink signal in the at least one selected slot in the multislot frame.
4 Assignments
0 Petitions
Accused Products
Abstract
The set T of all categories in a population of RFID tags is estimated within a specified error bound. For each of one or more frames, a reader broadcasts a probability p, a multiplicity d, a frame size M, and a seed value R to the present tags. A deterministic algorithm on each tag, and known to the reader, calculates (i) whether the tag will transmit in this frame, and, if so, (ii) in which slots the tag will transmit a single “1.” When the tags have responded, the reader calculates set T by initially assuming that all possible categories are in set T and then eliminating those categories that would have transmitted in those slots in which no tag transmitted. Alternatively, the reader initially assumes that set T is empty, and adds those categories that would have transmitted in those slots in which one or more tags did transmit.
43 Citations
View as Search Results
Method for improved topology mapping in wireless communication networks  
Patent #
US 8,634,329 B2
Filed 01/31/2011

Current Assignee
AlcatelLucent SA

Sponsoring Entity
AlcatelLucent SA

FRAMEWORK FOR FAST RFID TAG READING IN STATIC AND MOBILE ENVIRONMENTS  
Patent #
US 20100039237A1
Filed 06/26/2009

Current Assignee
Venkatesh Sarangan, Malla Reddy Devarapalli, Sridhar Radhakrishnan

Sponsoring Entity
Venkatesh Sarangan, Malla Reddy Devarapalli, Sridhar Radhakrishnan

Data transmission method for wireless network  
Patent #
US 7,684,343 B2
Filed 03/20/2006

Current Assignee
Samsung Electronics Co. Ltd.

Sponsoring Entity
Samsung Electronics Co. Ltd.

Enhanced identification protocol for RFID systems  
Patent #
US 7,486,172 B2
Filed 03/04/2005

Current Assignee
Intermec IP Corporation

Sponsoring Entity
Intermec IP Corporation

PROVIDING ITEM BAGGING ADVISEMENTS TO BAGGERS  
Patent #
US 20090090584A1
Filed 10/04/2007

Current Assignee
Toshiba Global Commerce Solutions Holdings Corporation

Sponsoring Entity
Toshiba Global Commerce Solutions Holdings Corporation

TAG READING DEVICE  
Patent #
US 20090179738A1
Filed 09/21/2005

Current Assignee
Panasonic Corporation

Sponsoring Entity
Panasonic Corporation

SECURE RFID BASED ULTRAWIDEBAND TIMEHOPPED PULSEPOSITION MODULATION  
Patent #
US 20080012688A1
Filed 07/05/2007

Current Assignee
Schaumont Patrick, Dong Ha

Sponsoring Entity
Schaumont Patrick, Dong Ha

INTERROGATING RADIO FREQUENCY TAGS  
Patent #
US 20080150692A1
Filed 06/22/2007

Current Assignee
3M Innovative Properties Company

Sponsoring Entity


Method of communicating in a radio frequency identification system using aloha networks  
Patent #
US 20080180222A1
Filed 01/26/2007

Current Assignee
RF ACCELERATED LLC

Sponsoring Entity
RF ACCELERATED LLC

PIGGYBACK REQUESTS IN SCHEDULED TRANSMISSION  
Patent #
US 20080187003A1
Filed 06/29/2007

Current Assignee
ViaSat Incorporated

Sponsoring Entity
ViaSat Incorporated

REQUEST SIGNAL DESIGNS FOR MULTIPLE SERVICE TYPES  
Patent #
US 20080187002A1
Filed 06/29/2007

Current Assignee
ViaSat Incorporated

Sponsoring Entity


METHODS AND SYSTEMS OF RECEIVING DATA PAYLOAD OF RFID TAGS  
Patent #
US 20080297324A1
Filed 05/30/2007

Current Assignee
Round Rock Research LLC

Sponsoring Entity
Round Rock Research LLC

System and method for selecting a medium access technique for transmitting packets over a network  
Patent #
US 20070070896A1
Filed 09/29/2005

Current Assignee
ARRIS Enterprises LLC

Sponsoring Entity
ARRIS Enterprises LLC

Method and apparatus for avoiding radio frequency identification (RFID) tag response collisions  
Patent #
US 20070075838A1
Filed 10/04/2005

Current Assignee
Symbol Technologies Inc.

Sponsoring Entity
Symbol Technologies Inc.

Method for estimating number of tags in slotted alohabased RFID system  
Patent #
US 20070096877A1
Filed 08/02/2006

Current Assignee
Electronics and Telecommunications Research Institute

Sponsoring Entity
Electronics and Telecommunications Research Institute

Method and system for optimizing radio frequency identification (RFID) reader operation  
Patent #
US 20070126555A1
Filed 12/06/2005

Current Assignee
Symbol Technologies Inc.

Sponsoring Entity
Symbol Technologies Inc.

Tiered contention multiple access (TCMA): a method for prioritybased shared channel access  
Patent #
US 7,095,754 B2
Filed 11/02/2001

Current Assignee
ATT Intellectual Property I LP

Sponsoring Entity
ATT Inc.

Anticollision protocol with fast read request and additional schemes for reading multiple transponders in an RFID system  
Patent #
US 6,963,270 B1
Filed 10/27/1999

Current Assignee
CHECKPOINT SYSTEMS INC., Mitsubishi Materials Corporation

Sponsoring Entity
Microchip Technology Incorporated

Demand assignment system and method for mobile users in a community of interest  
Patent #
US 5,506,848 A
Filed 06/22/1994

Current Assignee
ATT Inc.

Sponsoring Entity
ATT Inc.

Enhanced uplink modulated backscatter system  
Patent #
US 5,940,006 A
Filed 12/12/1995

Current Assignee
ATT Inc.

Sponsoring Entity


Distributed control methods for management of migrating data stations in a wireless communications network  
Patent #
US 5,212,806 A
Filed 10/29/1990

Current Assignee
International Business Machines Corporation

Sponsoring Entity
International Business Machines Corporation

Method for selecting one or more transponders  
Patent #
US 20060044114A1
Filed 08/25/2005

Current Assignee
Atmel Corporation

Sponsoring Entity
Atmel Corporation

Adaptively adjusting a query parameter Q used for inventorying RFID tags  
Patent #
US 20060071758A1
Filed 08/24/2005

Current Assignee
Impinj Incorporated

Sponsoring Entity
Impinj Incorporated

System and method for electronic inventory  
Patent #
US 7,035,818 B1
Filed 06/01/1999

Current Assignee
Symbol Technologies LLC

Sponsoring Entity
Symbol Technologies Inc.

Apparatus and method for allocating data bursts in a broadband wireless communication system  
Patent #
US 20060101168A1
Filed 10/20/2005

Current Assignee
Samsung Electronics Co. Ltd.

Sponsoring Entity
Samsung Electronics Co. Ltd.

Wireless terminal and RFID system for providing additional information and a method for providing additional information using wireless terminal and RFID system  
Patent #
US 20060208860A1
Filed 03/16/2006

Current Assignee
Samsung Electronics Co. Ltd.

Sponsoring Entity
Samsung Electronics Co. Ltd.

Method and system for mapping traffic predictions with respect to telematics and route guidance applications  
Patent #
US 7,103,470 B2
Filed 02/08/2002

Current Assignee
Josef Mintz

Sponsoring Entity
Josef Mintz

Efficient memoryless protocol for tag identification  
Patent #
US 6,859,801 B1
Filed 05/30/2001

Current Assignee
Massachusetts Institute of Technology

Sponsoring Entity
Massachusetts Institute of Technology

Method and system for inventory count of articles with RFID tags  
Patent #
US 20050035849A1
Filed 08/12/2003

Current Assignee
Yadgar Yizhack

Sponsoring Entity
Yadgar Yizhack

Anticollision method for contactless electronic module  
Patent #
US 20040012486A1
Filed 06/03/2003

Current Assignee
Stmicroelectronics SA

Sponsoring Entity
Stmicroelectronics SA

Protocol for addressing groups of RFID tags  
Patent #
US 20040046642A1
Filed 09/05/2002

Current Assignee
Honeywell International Inc.

Sponsoring Entity
Honeywell International Inc.

RF transponder identification system and protocol  
Patent #
US 6,538,563 B1
Filed 01/05/1999

Current Assignee
National University of Singapore

Sponsoring Entity
National University of Singapore

Interrogation, monitoring and data exchange using RFID tags  
Patent #
US 6,563,417 B1
Filed 10/26/1999

Current Assignee
Identec Solutions AG

Sponsoring Entity
Identec Solutions Inc.

Handling support method and handling support system  
Patent #
US 20030105853A1
Filed 11/27/2002

Current Assignee
Hitachi Ltd.

Sponsoring Entity


Method and system for optimizing an interrogation of a tag population  
Patent #
US 20030214389A1
Filed 04/01/2003

Current Assignee
Symbol Technologies LLC

Sponsoring Entity


Method and system for communicating with and tracking RFID transponders  
Patent #
US 20020063622A1
Filed 11/29/2000

Current Assignee
Ludwig Kipp

Sponsoring Entity
Ludwig Kipp

Scoring methodology for purchasing card fraud detection  
Patent #
US 6,418,436 B1
Filed 12/20/1999

Current Assignee
First Data Corporation

Sponsoring Entity
First Data Corporation

Method of optimizing random access performance in a mobile communications network using dynamically controlled persistence techniques  
Patent #
US 20020118661A1
Filed 12/22/2000

Current Assignee
COMSAT Corporation

Sponsoring Entity
COMSAT Corporation

Random medium access methods with backoff adaptation to traffic  
Patent #
US 20020154653A1
Filed 01/02/2002

Current Assignee
ATT Inc.

Sponsoring Entity
ATT Intellectual Property I LP

Tiered contention multiple access (TCMA): a method for prioritybased shared channel access  
Patent #
US 20020163933A1
Filed 11/02/2001

Current Assignee
ATT Intellectual Property I LP

Sponsoring Entity
ATT Intellectual Property I LP

System for storage and communication of information  
Patent #
US 5,530,702 A
Filed 05/31/1994

Current Assignee
Mobile Technics LLC

Sponsoring Entity
Ludwig Kipp

Method for the transmission of data packets  
Patent #
US 4,398,289 A
Filed 02/17/1981

Current Assignee
US Philips Corporation

Sponsoring Entity
US Philips Corporation

Communication processing device, information processing device, communication system, communication processing method, information processing method, and program  
Patent #
US 20070286227A1
Filed 05/24/2007

Current Assignee
Omron Corporation

Sponsoring Entity
Omron Corporation

19 Claims
 1. . A tag for an RFID system, the RFID system further comprising a reader, the tag comprising:
a memory adapted to store a tag identification (ID) value for the tag, the tag ID value comprising a category ID value and an instance value; an antenna adapted to receive a downlink signal from the reader and transmit an uplink signal to the reader; and a processor adapted to process the downlink signal and generate the uplink signal, wherein; the processor is adapted to select at least one slot in a multislot frame based on the stored category ID value, but independent of the stored instance value; and the tag is adapted to transmit the uplink signal in the at least one selected slot in the multislot frame.  View Dependent Claims (2, 3, 4, 5, 6)
 7. . A tag for an RFID system, the RFID system further comprising a reader, the tag comprising:
a memory adapted to store a tag identification (ID) value for the tag, the tag ID value comprising a category ID value and an instance value; an antenna adapted to receive a downlink signal from the reader and transmit an uplink signal to the reader; and a processor adapted to process the downlink signal and generate the uplink signal, wherein; the processor is adapted to select two or more different slots in a multislot frame; and the tag is adapted to transmit the uplink signal in each of the two or more different selected slots in the multislot frame.  View Dependent Claims (8, 9, 10)
 11. . A tag for an RFID system, the RFID system further comprising a reader, the tag comprising:
a memory adapted to store a tag identification (ID) value for the tag, the tag ID value comprising a category ID value and an instance value; an antenna adapted to receive a downlink signal from the reader and transmit an uplink signal to the reader; and a processor adapted to process the downlink signal and generate the uplink signal, wherein the uplink signal corresponds to a single bit value.  View Dependent Claims (12)
 13. . A reader for an RFID system, the RFID system further comprising one or more tags, the reader comprising:
a processor adapted to generate a downlink signal; an antenna adapted to transmit the downlink signal to the one or more tags and receive one or more uplink signals from the one or more tags, wherein; the processor is further adapted to process the one or more uplink signals; and the downlink signal comprises a multiplicity value indicating a number of slots, such that a tag that transmits an uplink signal in response to receipt of the downlink signal will (1) select two or more different slots in a multislot frame based on the multiplicity value and (2) transmit the uplink signal in each of the two or more different selected slots in the multislot frame.  View Dependent Claims (14)
 15. . A reader for an RFID system, the RFID system further comprising one or more tags, the reader comprising:
a processor adapted to generate a downlink signal; an antenna adapted to transmit the downlink signal to the one or more tags and receive one or more uplink signals from the one or more tags, wherein; each tag is associated with a tag ID value comprising a category ID value and an instance value; the one or more tags correspond to one or more categories; and the processor is further adapted to process the one or more uplink signals to estimate the one or more categories without identifying any of the one or more tags.  View Dependent Claims (16, 17, 18, 19)
1 Specification
1. Field of the Invention
The invention relates to digital communication, and more specifically to Radio Frequency Identification (RFID).
2. Description of the Related Art
Advances in supplychain technologies are promoting the rapid deployment of RFID tags to identify individual items, such as passports, retails products, books, or even humans.
Reader 110 comprises an antenna 112, a processor 114, and a memory 116. A typical tag 130 comprises (i) an antenna 132, (ii) a memory 136, and (iii) a processor 134 for rudimentary calculations.
A typical use of system 100 is to determine which tags, and hence, which objects are within the system. This determination is made by performing an interrogation. For a time duration known as a frame, reader 110 emits from antenna 112 a downlink signal, which energizes tags 130 within interrogation zone 120. Also within the frame duration, each energized tag 130 transmits an uplink signal back to reader 110. A typical uplink signal contains the tag ID value. Reader 110 collects and collates the received tag IDs and generates a list of which tag IDs are in the system.
A potential problem with the interrogation procedure is collisions, i.e., when two or more tags transmit at the same time. A reader that receives a collision typically cannot determine how many tags transmitted to generate the collision, or which tags transmitted to generate the collision. As such, the reader cannot state with certainty which tags are in the system.
One protocol, called framed slotted ALOHA, reduces collisions by dividing the frame into a number M of equalsized slots, where each slot has a time duration long enough for a tag to transmit the information requested, e.g., the tag ID. The number M of slots in a frame is also referred to as the frame size M.
At the start of a frame, the reader sends two pieces of information to the tags: the frame size M and a seed value R. Each tag'"'"'s integrated circuit is capable of implementing a tag algorithm (e.g., a uniform hash function) that takes the seed value R, the frame size M, and the tag ID, and generates a pseudorandom slot index number. Each tag transmits its tag ID during the slot corresponding to its generated slot index number. Depending on the tag algorithm, the algorithm'"'"'s input parameters, and the different tags are that present in the system, a tag may be the only tag transmitting in its slot or the tag'"'"'s slot may correspond to a collision, in which the tag and one or more other tags transmit their tag IDs at the same time. When a tag is the only tag transmitting in its slot, then the reader is able to identify that tag as being present. When a collision occurs in a slot, the reader is unable to identify the particular tags transmitting during that slot.
If the reader detects one or more collisions, then the reader selects a different seed value R and starts another frame. Because the seed R is different, the tags will generate a different pseudorandom set of slots in which to transmit, such that tags that previously collided with other tags might not collide in the current frame.
Frames are performed until all tags have been identified, or the process is terminated by some specified threshold, such as a maximum number of frames. The total number of performed frames is denoted r. The total number of slots in all the performed frames is known as the scan length in. Thus, m=r·M. The one or more frames used to identify the tags in the system may be referred to as corresponding to a single interrogation of the system.
The example given above focused on determining the particular tag IDs that are present in a system. However, some applications might need to know only the categories of products that are present in the system without having to identify each different product. For such applications, it may be sufficient to identify only the different category IDs for the tags that are present in the system, as opposed to identifying the particular tags IDs.
In one embodiment, the invention is a tag for an RFID system further comprising a reader. The tag comprises a memory, an antenna, and a processor. The memory is adapted to store a tag identification (ID) value for the tag, the tag ID value comprising a category ID value and an instance value. The antenna is adapted to receive a downlink signal from the reader and transmit an uplink signal to the reader. The processor is adapted to process the downlink signal and generate the uplink signal. Specifically, the processor is adapted to (i) select at least one slot in a multislot frame based on the stored category ID value, but independent of the stored instance value, and (ii) transmit the uplink signal in the at least one selected slot in the multislot frame.
In another embodiment, the invention is a tag for an RFID system further comprising a reader. The tag comprises a memory, an antenna, and a processor. The memory is adapted to store a tag identification (ID) value for the tag, the tag ID value comprising a category ID value and an instance value. The antenna is adapted to receive a downlink signal from the reader and transmit an uplink signal to the reader. The processor is adapted to process the downlink signal and generate the uplink signal, wherein the processor is adapted to (i) select two or more different slots in a multislot frame, and (ii) transmit the uplink signal in each of the two or more different selected slots in the multislot frame.
In yet another embodiment, the invention is a tag for an RFID system further comprising a reader. The tag comprises a memory, an antenna, and a processor. The memory is adapted to store a tag identification (ID) value for the tag, the tag ID value comprising a category ID value and an instance value. The antenna is adapted to receive a downlink signal from the reader and transmit an uplink signal to the reader. The processor is adapted to process the downlink signal and generate the uplink signal, wherein the uplink signal corresponds to a single bit value.
In yet another embodiment, the invention is a reader for an RFID system further comprising one or more tags, the reader comprising a processor and an antenna. The processor is adapted to generate a downlink signal, and the antenna is adapted to transmit the downlink signal to the one or more tags and receive one or more uplink signals from the one or more tags. The processor is further adapted to process the one or more uplink signals. The downlink signal comprises a multiplicity value indicating a number of slots, such that a tag that transmits an uplink signal in response to receipt of the downlink signal will (1) select two or more different slots in a multislot frame based on the multiplicity value and (2) transmit the uplink signal in each of the two or more different selected slots in the multislot frame.
In yet another embodiment, the invention is a reader for an RFID system further comprising one or more tags. The reader comprises a processor adapted to generate a downlink signal and an antenna adapted to transmit the downlink signal to the one or more tags and receive one or more uplink signals from the one or more tags. Each tag is associated with a tag ID value comprising a category ID value and an instance value. The one or more tags correspond to one or more categories. The processor is further adapted to process the one or more uplink signals to estimate the one or more categories without identifying any of the one or more tags.
Other aspects, features, and advantages of the invention will become more fully apparent from the following detailed description, the appended claims, and the accompanying drawings in which like reference numerals identify similar or identical elements.
The set of all possible tag categories is denoted N, and the number of distinct categories in set N, i.e., the cardinality of set N, is denoted n. The set of distinct categories currently present in a particular RFID system is denoted T, and the number of distinct categories in set T, i.e., the cardinality of set T, is denoted t. It is assumed that set N and cardinality n are known quantities, and that cardinality t can be estimated. One method for estimating cardinality t can be found in U.S. patent application Ser. No. 11/525,339 filed on Sep. 22, 2006 as attorney docket no. Kodialam 469, which application is herein incorporated by reference in its entirety.
Various embodiments of the present invention are systems and methods for efficiently determining, with probability greater than 1−∈, where 0<∈<1, the set T of distinct categories present in an RFID system. In other words, on average, out of 1/∈ interrogations to identify set T, no more than one interrogation should have any false positive or false negative.
An RFID system according to various embodiments of the present invention is analogous to RFID system 100 of
According to various embodiments of the present invention, all tags 130 in RFID system 100 contain an identical, deterministic tag algorithm that takes (i) parameters received from the reader and (ii) the tag'"'"'s category ID and determines (a) whether a tag will transmit in a given frame, and, if so, (b) the slot(s) in which the tag will transmit. Because the tag algorithm is deterministic and identical for all tags, all tags with the same category ID will transmit in the same frames, and in the exact same slots within those selected frames. It is possible for tags belonging to two or more different categories to transmit in the same slot in a given frame. It is also possible for a tag to transmit in a slot that would also have been used by tags of a different category that is not present in the system.
According to various embodiments of the present invention, tags transmit a single bit, i.e., a slot can be as small as one bit long. If no tag transmits in a given slot, then the slot is referred to as a zero slot. If one or more tags transmit in a given slot, then the slot is referred to as a nonzero slot. Nonzero slots include both (i) slots where only a single tag transmits and (ii) slots where multiple tags transmit, resulting in collisions.
The reader knows the tag algorithm. Thus, the reader can determine, a priori, which categories of tags can and cannot transmit in a given slot. Furthermore, because the set N of all possible categories, the number n of distinct categories in set N, and the number t of distinct categories in the system are known quantities, the reader can calculate (e.g., see Equations (1)(25), below), a priori, the minimum number in of total slots required to identify the distinct categories within a specified error threshold.
Interrogation Procedure
Processing starts at step 302 and proceeds to step 304 where a frame counter is initialized to 1. Next, at step 306, reader 110 selects a new seed value R. Next, at step 308, reader 110 energizes tags 130 in the system and broadcasts the frame size M, a multiplicity value d, a probability value p, and the seed value R. This particular scheme is referred to as an (M,d,p) scheme. The probability value p, which ranges from 0 to 1, indicates the relative probability that a tag will participate in the current frame. If all tags are expected to participate in that frame, e.g., in a singleframe interrogation procedure, then the probability value p will be set to 1. If a tag determines that it is to participate in the current frame, then the multiplicity value d indicates the number of slots in that frame during which the tag will transmit.
Next, in step 310, each tag (i) takes the frame size M, multiplicity d, probability p, seed value R, and the tag'"'"'s category ID, (ii) determines whether to transmit in the current frame, and, if so, calculates the d slots in which to transmit, and (iii) transmits a “1” in each of the d slots. Step 310 is discussed in greater detail in the discussion of
Next, in step 312, the frame counter is incremented. Then, at step 314, it is determined whether the frame counter is greater than the total number r of frames in the current interrogation, i.e., whether all r frames have been performed. If so, then interrogation procedure 204 terminates at step 316; otherwise, processing loops back to step 306 for the next frame in the current interrogation.
Next, in step 406, the tag pseudorandomly picks a number X between 1 and M/p. In particular, in one implementation, the tag generates the number X by concatenating the seed value R and the tag'"'"'s category ID, hashing the result with a standard hash algorithm (e.g., SHA1, MD5), and then calculating the hash result modulo M/p. In one possible implementation, the seed value R is an 8digit hexadecimal number.
Step 408 determines whether or not the tag will transmit during the current frame. In particular, if the number X is greater than the frame size M, then the tag will not transmit during the current frame and process 310 terminates at step 414; otherwise, the tag will transmit during the current frame and processing continues to step 410. Note that, in a singleframe interrogation procedure, the probability value p will be set to 1, and, thus, step 408 will always evaluate to yes.
In step 410, the tag algorithm computes the d slots in which the tag is to transmit. Specifically, for each index value i from 0 to d−1, a sum is generated by adding together the tag'"'"'s category ID, the index value i, and the seed value R, and the sum is then hashed using a standard hash function (e.g., SHA1, MD5). The resulting hash value modulo the frame size M identifies one of the d slots in which the tag is to transmit.
Then, at step 412, the tag transmits a “1” in the d calculated slots. Processing then terminates at step 414.
Interrogation procedure 204 can accommodate any number of frames in an interrogation. If there is no limit on the frame size M, or if the number t of categories is small compared to frame size M, then a single frame may be sufficient to correctly estimate set T with a probability greater than 1−∈. In cases where there is restriction on the maximum frame size, the singleframe method gives a lower bound on the number of slots needed. Note that, in a singleframe scenario, the scan length m equals the frame size M. Furthermore, in the singleframe interrogation procedure, all tags, and thus, all categories in set T, will transmit in the frame, i.e., the probability value p is set to 1. Thus, a singleframe scheme may be referred to as an (M,d) or (m,d) scheme.
If, instead, there are a large number of categories to be identified by a system utilizing a fixed frame size, then multiple frames may be required to perform the interrogation procedure to within the desired level of accuracy. Thus, the scan length m will correspond to a number r of fixed frames of size M, i.e., m=r−M.
Note that, while interrogation procedure 204 is the same for singleframe or multipleframe interrogations, the categoryidentification algorithms 206 used for the two scenarios might differ. The variants of categoryidentification algorithm 206 are explained in greater detail below. Likewise, the process for determining the optimal parameters for a singleframe interrogation procedure differs from the analogous process for a multipleframe interrogation procedure. Both of these processes are described in greater detail below.
CategoryIdentification Algorithms
At the end of interrogation procedure 204, the reader knows the set Z of zero slots and the set C of nonzero slots. Additionally, because the reader knows the deterministic algorithm used by the tags to select frames and slots in which to transmit, the reader knows the set of categories that can transmit in any given slot. Given these inputs, the task is to determine, with a probability greater than 1−∈, the set T of all distinct categories present in the system.
In certain embodiments of the present invention, categoryidentification algorithm 206 is based on category elimination. The categoryelimination algorithm starts by assuming that T contains all categories that could have transmitted during the interrogation.
In a singleframe scenario, where probability p is equal to 1 and thus all tags in the system will transmit in the interrogation'"'"'s single frame, the elimination algorithm starts by setting set T equal to the set N of all possible categories. For each zero slot, the reader determines which categories would have transmitted in the slot, had they been present, and deletes those categories from T. When all zero slots have been processed, T is declared final.
In a multipleframe scenario, the elimination algorithm first determines, for a frame k, the set T_{k }of categories that could have participated in frame k. For each zero slot in k, the reader determines which categories would have transmitted in the slot, had they been present, and deletes those categories from T_{k}. When all zero slots in k have been processed, T_{k }is declared final. When all frames have been processed in this manner, T is set equal to the union of all sets T_{k}.
In other embodiments of the present invention, categoryidentification algorithm 206 is based on category inclusion. An inclusionbased algorithm initially assumes that set T is empty, and, for each nonzero slot, adds to T all categories that could have transmitted in that nonzero slot. The inclusionbased algorithm is the same for both singleframe and multiframe scenarios.
Determining Optimal Scanlength in for SingleFrame CategoryIdentification Scheme
An operator of an RFID system typically wants to know the optimal scanlength m, i.e., the minimum total number in of slots required to identify the categories in the system with a probability greater than 1−∈. This is typically a function of the number t of categories present, the potential number n of categories, as well as the error bound E. The optimal scanlength in may be important to know when using batteryoperated readers that have limited scanlengths, or where the items to be identified are in motion (e.g., railroad, ships) and thus might be in the reader'"'"'s interrogation zone for only a relatively short time.
The probability that a given slot j is picked by tags of a category in set T is the multiplicity d divided by the scanlength m, i.e., d/m. Consequently, the probability that slot j is not picked by a category in set T is
Therefore, the probability that none of the t categories pick slot j, i.e., that slot j is a member of the set Z of zero slots, is given by Equation (1):
Let y_{i}^{k }denote the kth slot (with respect to the d slots, not the in slots) picked by tags of category i. The probability that slot y_{i}^{k }is not a member of the set Z of zero slots is equal to 1 minus the probability from Equation (1). Thus, Equation (2):
Since the d slots are picked pseudorandomly by each category, the probability that all d slots picked by category i are not elements of the set Z of zero slots is equal to the probability of Equation (2) raised to the power of d. Thus, in Equation (3):
For any category i∈N\T, if there is at least one slot y_{i}^{k }in the set Z of zero slots, then category i is eliminated from set T. Category i is said to be in set G if there exists a value k where 1≦k≦d such that slot y_{i}^{k}∈Z. In other words, G is the set of all categories i that are eliminated from set T. Thus, the probability that category i is a member of set G is equal to 1 minus the probability of Equation (3). Therefore, in Equation (4):
The fact that categories pick slots in a pseudorandom manner means that the probability that a member of set Twill be found to be a member of set G is equal to the probability of Equation (4) raised to the power of n−t, i.e., the number of categories that are not members of set T. Thus, Equations (5) and (6):
Note that, when all categories i∉T belong to set G, then all these categories will be eliminated, and the remaining categories will belong to set T. Since the goal is to identify set T with probability greater than 1−∈, in Equation (7):
In other words, the goal is to pick an (m,d) scheme that achieves the bound of Equation (7) using the minimum scanlength m. The value of multiplicity d is chosen appropriately to minimize the value of scanlength m. Another way of looking at this problem is to fix the value of scanlength m and find the value of multiplicity d that minimizes the following Equation (8):
Once this is done, a value of scanlength m is found that meets the high probability bound. In order to find the optimal value of multiplicity d, an approximation is made by setting
which, when used in Equation (8), yields the following Equation (9):
Note that the above Equation (9) is minimized when the exponent is maximized. This occurs when
which implies that multiplicity
Submitting this value for the multiplicity d in g(m,d) of Equation (7) yields Equation (10):
We now set
using the binomial equality. This implies that
Solving for scanlength m, and using α<1 yields the following Equation (11):
Using the value of a from Equation (10) in Equation (11), and using −1/ln α=(ln 2)^{−2}≦2.082, yields the following theorem. In the singleframe categoryidentification scheme described above, given the number n of possible categories, the number t of categories present, and an experimental error bound ∈, the minimum number m of slots needed by the singleframe identification algorithm to correctly identify the set T of categories present with probability 1−∈ is given by the following Equation (12):
Note that the number of slots increases linearly with the number t of categories present, but only increases logarithmically with the total potential number n of categories. Since the total category space is constant, the scanning delay for category identification is linear in cardinality t.
In a singleframe system optimized according to Equation (12), m/d=1.44t.
Alternative SingleFrame Interrogation Procedure
In an alternative singleframe interrogation procedure, each frame is divided into d subframes, where each subframe has [m/d]=[1.44t] slots (where the ┌ ┐ brackets indicate that the result should be rounded up to the next integer. The value of 1.44t comes from the singleframe optimization of Equation (12).
The multiplicity d is set to 1, i.e., if a tag participates in a subframe, then the tag will transmit on a single slot. The interrogation procedure used is procedure 204 of
In the exemplary singleframe interrogation procedure described earlier, tags need to be able to (i) calculate the index numbers of d slots in which to transmit, (ii) store all d calculated slot index values, and (iii) sort the d slot index values in ascending order. In contrast, the alternative singleframe interrogation procedure requires the tag to calculate only one slot per subframe. As such, the alternative singleframe interrogation procedure requires fewer computing resources on the tag.
Determining Optimal Scanlength in for MultipleFrame CategoryIdentification Method
In order for the multiframe elimination algorithm to correctly identify set T, two conditions must be satisfied. First, each category i that is a member of the set N\T of all categories that are not present in the system, should be “scheduled” to participate in at least one frame. Scheduled means that the system parameters are selected such that if category i were present, it would participate in at least one frame. Second, if category i is not an element of set T, i.e., i∈N\T, then category i should not be identified as having participated in any time slot.
Users of an RFID system typically want to know the optimal system parameters for a multipleframe scenario, i.e., given a fixed frame size M, what is the minimum number r of frames (and, thus, the minimum scanlength m) needed to satisfy these two conditions with probability greater than 1−∈.
Let k index the frames, let j index the slots, and let S_{j}^{k }denote the set of categories that are supposed to transmit in slot j in frame k (given the probability p). Let Z_{k }denote the set of zero slots in frame k. Let Y_{i}^{k }denote the indicator that will be set to one if we determine that category i is present in frame k.
If a nonpresent category i (i.e., i∈N\T) is not eliminated in frame k, then either (i) category i is not scheduled in frame k with probability (1−p) or (ii) category i is scheduled in frame k, but not detected, i.e., none of the slots picked by category i map to any slot in the set Z_{k }of zero slots of frame k (i.e., other, present categories transmit in each of categories i'"'"'s slots in frame k). The probability that a nonpresent category is not eliminated in frame k is expressed in Equation (14):
Pr[Y_{i}^{k}≠0,i∈N\T]=(1−p)+p(Pr[i∈∪_{j∈Z}_{k}S_{j}^{k}]) (14)
where the first term on the righthand side (R.H.S.) represents the probability that the category does not participate in this frame, and the second term on the R.H.S. represents the probability that the category is scheduled for frame k, but not detected.
The probability that a category i participates in a frame is p. The probability that category i picks a given slot j within a frame is
Thus, the probability that category i does not pick slot j is
The probability that no category in set T picks slot j is
A slot j is empty (i.e., j∈Z^{k}) if none of the categories in set T maps to slot j. Thus, the probability that slot j is empty is expressed in Equation (15):
If the probability that a slot is empty is
then the probability that a slot is not empty is
Thus, the probability that all d slots that would have been selected by a scheduled, nonpresent category i are not empty is
Plugging this expression into the second term of the R.H.S. of Equation (14) yields the following Equation (16):
The probability ψ is the probability Pr[Y_{i}^{k}≠0,i∈N\T] of Equation (14) that a scheduled, but nonpresent category i does not get eliminated in a frame. Thus, the probability that a nonpresent category i does not get eliminated in all r frames is Φr. Consequently, the probability that a nonpresent category i does get eliminated after processing all r frames is (1−ψ^{r}). Thus, the probability that all nonpresent categories (i.e., all categories in set N\T) are scheduled and mapped to at least one zero slot in the r frames, thereby getting eliminated, is given by (1−ψ^{r})^{nt}.
If a category is not scheduled (using the probability p) in any of the r frames, then the category is marked as present. Any category in set T, if scheduled in a frame, will never map to a zero slot. This implies that, for certain implementations of the probabilistic category identification algorithm to be successful, only nonpresent categories need to be eliminated. Thus, the probability that all categories in N\T can be eliminated and every category in set T can be identified is given by (1−ψ^{r})^{nt}. In order to achieve the target estimation error requirement, the probability that every category in set T can be identified must be greater than 1 minus the error bound ∈, or, as defined by Equation (17):
(1−ψ^{r})^{nt}≧1−∈ (17)
The L.H.S. of Equation (17) can be maximized by minimizing the probability ψ. Unlike the singleframe analysis, here the number t of categories can be much larger than the frame size M. If the probability ψ is minimized with respect to the multiplicity d, subject to the fact that d≧1, the minimum is obtained when d=1 for t≧M ln 2. Similarly, it can also be shown that, for t≦M, the probability ψ is minimized when the probability p=1. Given these two observation, there are two separate optimization algorithms: one for t≦M, and another for t>M.
Optimizing MultipleFrame CategoryIdentification for t≦M
For the range t≦M, the probability p=1, and the multiplicity d is computed to minimize the probability ψ as shown in Equation (18):
ψ=[1−e^{−td/M}]^{d} (18)
Minimizing the probability ψ with respect to the multiplicity d is similar to the singleframe analysis, and yields e^{−td/M}=0.5, leading to
since the multiplicity d has to be an integer. Note that, for M ln 2≦t≦M, d=1. In order to eliminate all categories in set N\T with high probability, the system is configured so as to satisfy Equation (19):
The lower bound for the number r of frames is derived from Equation (19). An approximation similar to the singleframe case is used, resulting in the following theorem. Given a fixed frame size M, the number n of possible categories, the number t of categories present where t≦M, and an error bound ∈, the number r of fixed frames needed by the multipleframe identification procedure to identify, with probability 1−∈, the set T of categories present is given by the following Equation (20):
Optimizing MultipleFrame Category Identification for t>M
For the range t>M, d=1, and the probability p is computed to minimize the probability ψ in Equation (21):
Minimizing the probability ψ with respect to the number t of categories yields the optimum probability p=M/(t+1). The minimum probability ψ≈1−M/et, where e is the base of the natural logarithm (2.71828 . . . ). To eliminate categories that are not present, values are set in accordance with Equation (22):
Approximating Equation (22), as in the previous cases, yields Equation (23):
In order to get a simplified picture about the dependence of the number r of frames on the number t of categories, it is assumed that M<0.01∈t, and the above Equation (23) is rewritten as Equation (24):
Equation (24) provides the lower bound on the number of frames. In other words, given a fixed frame size M, the number n of possible categories, the number t of categories present in the system where t>M, and an error bound ∈, the number r of frames needed by the multipleframe identification method to identify the set T of categories present with probability 1−∈ is given by Equation (25):
Each tag participates once in each frame with a probability of M/(t+1).
The categoryidentification processing time of some priorart RFID identification methods, e.g., framed slotted ALOHA, is a linear function of the number of tags in the system. In other words, the larger the number of tags in the system, the longer it will take framed slotted ALOHA to identify set T. In contrast, the processing time of certain embodiments of the present invention scale linearly with the number t of distinct categories in the system. Thus, for example, certain embodiments of the present invention will take the same amount of time to identify set T in a system with t distinct categories, regardless of whether that system contains 10 tags or 1,000 tags.
Furthermore, certain embodiments of the present invention perform within a constant factor of a hypothetical oracle. The hypothetical oracle is an ideal category identification scheme in which all category IDs are serially transmitted without any collisions. Each transmission takes log_{2 }n=1.44 ln n bits. Embodiments of the present invention have a competitive ratio of 1.44(1+log_{n}(1/∈)) with respect to the hypothetical oracle. For n=10^{9}, ∈=0.001, the competitive ratio is 1.92.
Yet further, certain embodiments of the present invention offer security benefits not offered by other schemes. When responding to interrogation, tags respond with only a “1”, and not the category ID or the tag ID. To determine the categories present, one needs to know the particular tag algorithm used. Assuming that the tag algorithm has been kept confidential, an adversary cannot listen in on an interrogation and thus learn which categories are present in a system.
Although the present invention has been described in the context of identifying the set T of distinct categories in a population of tags, the invention is not so limited. The present invention could also be used to generate a set of distinct tag IDs in the system. Instead of N representing the set of all categories, N would now represent the set of all possible tag IDs. Thus, for each slot, the reader would need to calculate which tag IDs can/cannot transmit in the slot.
The present invention can be embodied in the form of methods and apparatuses for practicing those methods. The present invention can also be embodied in the form of program code embodied in tangible media, such as magnetic recording media, optical recording media, solid state memory, floppy diskettes, CDROMs, hard drives, or any other machinereadable storage medium, wherein, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the invention. The present invention can also be embodied in the form of program code, for example, whether stored in a storage medium, loaded into and/or executed by a machine, or transmitted over some transmission medium or carrier, such as over electrical wiring or cabling, through fiber optics, or via electromagnetic radiation, wherein, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the invention. When implemented on a generalpurpose processor, the program code segments combine with the processor to provide a unique device that operates analogously to specific logic circuits.
Unless explicitly stated otherwise, each numerical value and range should be interpreted as being approximate as if the word “about” or “approximately” preceded the value of the value or range.
It will be further understood that various changes in the details, materials, and arrangements of the parts which have been described and illustrated in order to explain the nature of this invention may be made by those skilled in the art without departing from the scope of the invention as expressed in the following claims.
As used herein in reference to an element and a standard, the term “compatible” means that the element communicates with other elements in a manner wholly or partially specified by the standard, and would be recognized by other elements as sufficiently capable of communicating with the other elements in the manner specified by the standard. The compatible element does not need to operate internally in a manner specified by the standard.
The use of figure numbers and/or figure reference labels in the claims is intended to identify one or more possible embodiments of the claimed subject matter in order to facilitate the interpretation of the claims. Such use is not to be construed as necessarily limiting the scope of those claims to the embodiments shown in the corresponding figures.
It should be understood that the steps of the exemplary methods set forth herein are not necessarily required to be performed in the order described, and the order of the steps of such methods should be understood to be merely exemplary. Likewise, additional steps may be included in such methods, and certain steps may be omitted or combined, in methods consistent with various embodiments of the present invention.
Although the elements in the following method claims, if any, are recited in a particular sequence with corresponding labeling, unless the claim recitations otherwise imply a particular sequence for implementing some or all of those elements, those elements are not necessarily intended to be limited to being implemented in that particular sequence.
Reference herein to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment can be included in at least one embodiment of the invention. The appearances of the phrase “in one embodiment” in various places in the specification are not necessarily all referring to the same embodiment, nor are separate or alternative embodiments necessarily mutually exclusive of other embodiments. The same applies to the term “implementation.”