Tag anti-collision RFID system and method for tag identification

• US 8,028,910 B2
• Filed: 12/14/2005
• Issued: 10/04/2011
• Est. Priority Date: 03/10/2005
• Status: Expired due to Fees

• Current Assignee: SK Telecom Co., Ltd.
• Original Assignee: SK Telecom Co., Ltd.
• Inventors: Seo, Kyung-Ho, Oh, Se-hyun, Yoon, Jin-Hee, Lee, Joo-Mun, Lee, Won-Jun, Myung, Ji-Hoon
• Primary Examiner(s): Hess, Daniel
• Assistant Examiner(s): KELLY, RAFFERTY D
• Application Number:
  US11/817,333
• Publication Number:
  US 20080283600A1
• Time in Patent Office: 2,120 Days
• Field of Search: 235/439, 370/320, 370/335
• US Class Current: 235/439
• CPC Class Codes: G06K 7/0008 General problems related to the reading of electronic memory record carriers, independent of its reading method, e.g. power transfer
• CPC Class Codes: G06K 7/10049 binary tree

Abstract

The present invention relates to a tag anti-collision Radio Frequency Identification (RFID) system and a method for tag identification. The method for tag identification consists of a first step of initializing a queue (Q) field and storing a prefix of a candidate queue (CQ) field in the queue field; a second step of transmitting a query including the prefix stored in the queue field to the RFID tags, and deleting the transmitted prefix from the queue field; a third step of inserting a prefix, in which prefixes 0 and 1 are inserted into a rear portion of a prefix of a previously transmitted query, into the queue field if two or more tags respond to the previously transmitted prefix and, therefore, the tags cannot be identified, and inserting the prefix of the previously transmitted query into the candidate queue field and deleting an unnecessary prefix stored in the candidate queue if there is no response or only one tag responds with respect to the previously transmitted prefix; and a fourth step of determining whether a prefix stored in the queue field exists, and returning to the second step if there is a prefix stored in the queue field.

Claims

1. A method for tag identification of a Radio Frequency Identification (RFID) reader within the identification range of the RFID reader for identifying a plurality of RFID tags which transmit their own IDs to the RFID reader when prefixes of queries received from the RFID reader match front portions of the RFID tags'"'"' IDs, comprising:

a first step of initializing a queue (Q) field and storing a prefix having 1 to n bits (n=the bit numbers of a tag'"'"'s ID) of a candidate queue (CQ) field in the queue field,

wherein, assuming that a pair of processes, in which the RFID reader transmits a query and one or more RFID tag respond to it, is one round, the RFID reader has a data field including the queue field and the candidate queue field which store prefixes to be transmitted in a subsequent round, wherein the RFID reader re-transmits prefixes one bit longer than prefixes previously transmitted in each successive round and continues to extend prefixes until the ID'"'"'s of all tags have been identified;

a second step of transmitting a query with the prefix stored in the queue field to the RFID tags, and deleting the transmitted prefix from the queue field;

a third step of inserting a prefix, in which prefixes 0 and 1 corresponding to one bit are inserted into a rear portion of a prefix of a previously transmitted query, into the queue field if two or more tags respond to the previously transmitted prefix and, therefore, the tags cannot be identified, and inserting the prefix of the previously transmitted query into the candidate queue field and deleting an unnecessary prefix stored in the candidate queue if there is no response or only one tag responds with respect to the previously transmitted prefix; and

a fourth step of determining whether a prefix stored in the queue field exists, and returning to the second step if there is a prefix stored in the queue field,

wherein the RFID reader identifies a new tag entering identification range of the RFID reader based upon the prefixes of identified nodes stored in the candidate queue field when an ID of the new tag matches one of the prefixes of the identified nodes and identifies the new tag based on the prefixes of no-response nodes stored in the candidate queue field when the ID of the new tag does not match one of the prefixes of the identified nodes.

2. The method as set forth in claim 1, wherein the deletion of the unnecessary prefix at the third step is performed by deleting prefixes of child nodes when prefixes of the child nodes of a node corresponding to the previously transmitted prefix are stored in the candidate queue if there is no response or only one tag responds with respect to the previously transmitted prefix.

3. The method as set forth in claim 2, wherein, at the third step, the RFID reader repeatedly performs the step of deleting the prefixes of the corresponding child nodes and inserting a prefix of a corresponding parent node until neither an identified node and a no-response node, nor a no-response node and a no-response node, exist in the candidate queue, the two nodes having an identical parent node, thereby deleting all prefixes of unnecessary no-response nodes from the candidate queue.

4. The method as set forth in claim 1, wherein, at the first step, the RFID reader is initialized by storing prefixes 0 and 1 in the queue field when there is no prefix stored in the candidate queue field.

5. A tag anti-collision RFID system, comprising:

RFID tags transmitting their own IDs to a RFID reader when prefixes of queries received from the RFID reader matches the front portions of the RFID tags'"'"' IDs; and

a RFID reader having a data field including a queue (Q) field and a candidate queue (CQ) field which, assuming that a pair of processes in which the RFID transmits a query and one or more RFID tags respond to it, store prefixes to be transmitted in a subsequent round, initializing the queue field, storing a prefix of the candidate queue field in the queue field, sequentially transmitting a query with the prefix stored in the queue field to the RFID tags until all of the tags are identified, deleting the transmitted prefix from the queue field, inserting a prefix, in which prefixes 0 and 1 corresponding to one bit are inserted into a rear portion of a prefix of a previously transmitted query, into the queue field if two or more tags respond to the previously transmitted prefix, and inserting the prefix of the previously transmitted query into the candidate queue field and deleting an unnecessary prefix stored in a candidate queue if there is no response or only one tag responds with respect to the previously transmitted prefix,

wherein the RFID reader identifies a new tag based upon the prefixes of identified nodes stored in the candidate queue field when an ID of the new tag matches one of the prefixes of the identified nodes and identifies the new tag based on the prefixes of no-response nodes stored in the candidate queue field when the ID of the new tag does not match one of the prefixes of the identified nodes.

6. The system as set forth in claim 5, wherein the RFID reader deletes the prefixes of child nodes when the prefixes for the child nodes of a node corresponding to the previously transmitted prefix are stored in the candidate queue if there is no response or only one tag responds with respect to the previously transmitted prefix.

7. The system as set forth in claim 6, wherein the RFID reader repeatedly performs the step of deleting the prefixes of the corresponding child nodes and inserting a prefix of a corresponding parent node until no pair of an identified node and a no-response node;

or of a no-response node and a no-response node, exists in the candidate queue, the two nodes having an identical parent node, thereby deleting all prefixes having unnecessary no-response nodes from the candidate queue.

8. The system as set forth in claim 5, wherein the RFID reader is initialized by storing prefixes 0 and 1 in the queue field when there is no prefix stored in the candidate queue field.