Method for identifying tags using adaptive binary tree splitting technique in RFID system and RFID system therefore

• US 8,477,016 B2
• Filed: 09/08/2006
• Issued: 07/02/2013
• Est. Priority Date: 09/30/2005
• Status: Active Grant

• Current Assignee: SK Planet Company Limited 50%, SK Planet Co., Ltd. (SK Telecom Co., Ltd.)
• Original Assignee: SK Planet Co., Ltd. (SK Telecom Co., Ltd.), SK Telecom Co., Ltd.
• Inventors: Lee, Won-Jun, Myung, Ji-Hoon, Yoon, Jin-Hee, Lee, Sang-Yun, Lee, Myung-Sung, Seo, Kyung-Ho, Lee, Joo-Mun
• Primary Examiner(s): Mehmood, Jennifer
• Assistant Examiner(s): POINT, RUFUS C
• Application Number:
  US11/574,189
• Publication Number:
  US 20090040021A1
• Time in Patent Office: 2,489 Days
• Field of Search: 340/10.1, 340/10.2, 340/10.3
• US Class Current: 340/10.2
• 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 RFID system includes an RFID reader for sending information selected from among collision type information, idle type information, and readable type information, to all of the RFID tags depending on the number of signals in the corresponding time slot, and RFID tags for performing functions, in which, when information, indicating that a current time slot is a collision type, is fed back from the RFID reader, each of RFID tags selects one arbitrary value of either 0 or 1 and is assigned a time slot, in which a corresponding RFID tag will send a signal to the RFID reader, based on the selected value, a single tag group that caused a collision is divided into two sub-groups depending on the assigned time slots, and tags of the sub-groups send signals, including IDs thereof, to the RFID reader in different time slots for the respective sub-groups.

Claims

1. A Radio Frequency Identification (RFID) system limited to the use of a binary tree-based tag identification protocol for enabling an RFID reader to identify all RFID tags through continuous communication between the RFID tags and the RFID reader, comprising:

when a period, in which the RFID tags each send a signal, including an ID, to the RFID reader and the RFID reader sends feedback, is defined as a time slot,

the RFID reader for sending one piece of information selected from among collision type information, indicating that signals from the RFID tags collide with each other;

idle type information, indicating that there are no signals from the RFID tags; and

readable type information, indicating that a signal has been received from a single RFID tag and the corresponding RFID tag has been identified, to all of the RFID tags within an identification range of the RFID reader, as type information of a specific time slot, depending on the number of signals sent from the RFID tags in the corresponding time slot; and

the RFID tags for performing functions, in which, when information, indicating that a current time slot is a collision type, is fed back from the RFID reader, each of RFID tags that caused a collision selects one arbitrary value of either 0 or 1 and is assigned a time slot, in which a corresponding RFID tag will send a signal to the RFID reader, based on the selected value, a single tag group that caused a collision is divided into two sub-groups depending on the assigned time slots, and tags of the sub-groups send signals, including IDs thereof, to the RFID reader in different time slots for the respective sub-groups such that all of the RFID tags send signals in different time slots of a single tag identification frame

wherein the RFID reader can identify all of the RFID tags from the signals in different time slots.

2. The RFID system as set forth in claim 1, wherein:

each of the RFID tags, in a tag identification frame, including a plurality of time slots that are required by the RFID reader to identify all of the RFID tags within a current identification range of the RFID reader, has a progressive slot counter value, indicating a number of time slots in each of which an RFID tag has been identified, and an assigned slot counter value, that is, a time slot number, indicating a sequential position for sending of a signal to the RFID reader, and sends a signal to the RFID reader at a start of a time slot if the progressive slot counter value thereof is identical to the assigned slot counter value thereof; and

the RFID tag initializes the progressive slot counter value thereof to 0 at a start of a tag identification frame, increases the progressive slot counter value by 1 if time slot type information, fed back from the RFID reader, is a readable type, selects an arbitrary number of either 0 or 1 and then adds the selected number to the assigned slot counter value thereof if the time slot type information is a collision type, thereby allowing a tag group, including tags having caused a collision, to be divided into two sub-groups, and decreases the assigned slot counter value thereof by 1 to eliminate an unnecessary time slot if the time slot type information is an idle type.

3. The RFID system as set forth in claim 2, wherein the RFID tag decreases the assigned slot counter value thereof by 1 if the progressive slot counter value of the RFID tag is less than the assigned slot counter value of the RFID tag when time slot type information fed back from the RFID reader is an idle type.

4. The RFID system as set forth in claim 2, wherein, when the time slot type information fed back from the RFID reader is a collision type, the RFID tag selects one of either 0 or 1 and then adds the selected number to the assigned slot counter value thereof if the progressive slot counter value thereof is identical to the assigned slot counter value thereof, and adds 1 to the assigned slot counter value thereof if the progressive slot counter value Is less than the assigned slot counter value, therefore a currently created sub-group cannot be merged with another tag group.

5. The RFID system as set forth in claim 2, wherein the RFID tag maintains the assigned slot counter value thereof at the start of the tag identification frame, and initializes the assigned slot counter value thereof to 0 if the RFID tag does not have the assigned slot counter value.

6. The RFID system as set forth in any one of claims 1 to 5, wherein:

the RFID reader, in a tag identification frame, including a plurality of time slots that are required by the RFID reader to identify all of the RFID tags within a current identification range of the RFID reader, has a progressive slot counter value, indicating a number of time slots in each of which an RFID tag has been identified, and a termination slot counter value, indicating a number of tag groups to be identified, and becomes aware that all of the tags have been identified and then terminates a tag identification process when the termination slot counter value is identical to the progressive slot counter value; and

the RFID reader initializes the progressive slot counter value to 0 at a start of a tag identification frame, increases the progressive slot counter value by 1 if type information of a current time slot sent to an RFID tag is a readable type, increases the termination slot counter value by 1 if the type information is a collision type, and decreases the termination slot counter value by 1 if the type information is an idle type.

7. The RFID system as set forth in claim 6, wherein the RFID tag reader initializes the termination slot counter value thereof to 0 if the RFID tag reader does not have the termination slot counter value at the start of the tag identification frame.

8. The RFID system as set forth in claim 6, wherein:

the RFID reader notifies all of the tags within the identification range thereof of the termination slot counter value at the start of the tag identification frame; and

the RFID tag sets the assigned slot counter value thereof to an arbitrary value in values ranging from 0 to the termination slot counter value of the RFID reader if the assigned slot counter value of the RFID tag is greater than the termination slot counter value of the RFID reader at the start of the tag identification frame, thereby enabling identification of an RFID tag that newly enters the identification range of the RFID reader.

9. A method of identifying a plurality of tags using an adaptive binary tree splitting technique in an RFID system, the method, when a period, in which RFID tags each send a signal, including an ID, to an RFID reader and the RFID reader sends a feedback, is defined as a time slot, and a plurality of time slots, which are required by the RFID reader to identify all the RFID tags within a current identification range of the RFID reader, constitutes a tag identification frame, enabling the RFID reader to identify all of the RFID tags in such a way that the RFID tags send signals in different time slots of a single tag identification frame:

wherein each of the RFID tags has a progressive slot counter value, indicating a number of time slots in each of which an RFID tag has been identified, an assigned slot counter value, that is, a time slot number, indicating a sequential position for sending of a signal to the RFID reader and a termination slot counter value indicating the number of tag groups that should be identified by the reader in a tag identification frame;

the method comprising;

a first step of initializing the progressive slot counter value to 0 at a start of a tag identification frame;

a second step of determining whether the assigned slot counter value of the RFID tag is identical to the progressive slot counter value in a current time slot, and sending a signal, including an ID thereof, to the RFID reader if the two values are identical to each other, and maintaining a standby state if the two values are not identical to each other;

a third step of setting the progressive slot counter value and the assigned slot counter value according to received time slot type information when one piece of information selected from collision type information, indicating that signals from the RFID tags collide with each other, idle type information, indicating that there are no signals from the RFID tags, and readable type information, indicating that a signal has been received from a single RFID tag and the corresponding RFID tag has been identified, is received from the RFID reader that feeds type information of the current time slot back to all the RFID tags within an identification range of the RFID reader, depending on a number of signals received from the RFID tags;

wherein when the progressive slot counter value of each of the RFID tags equals the assigned slot counter value, each of the RFID tags that caused a collision selects a number of either a 1 or 0 which is added to the assigned slot counter value and the tag group of RFID tags that caused a collision is divided into two sub-groups with tags of the sub-groups sending signals, including IDs thereof, to the RFID reader in different time slots for the respective sub-groups such that all of the RFID tags will send signals in different time slots of a single tag identification frame, and

a fourth step of terminating the tag identification frame when the slot counter value is identical to the progressive slot counter value and returning to the second step if all of the tags have not been identified.

10. The method as set forth in claim 9, wherein step 3 comprises:

step 3-1 of determining whether the progressive slot counter value of the RFID tag is identical to the assigned slot counter value of the RFID tag when the RFID tag receives collision type information from the RFID reader; and

step 3-2 of selecting an arbitrary number of either 0 or 1 and then adding the selected number to the assigned slot counter value if, as a result of the termination at step 3-1, the two values are identical to each other, and increasing the assigned slot counter number of the RFID tag by 1 if the two values are not identical to each other.

11. The method as set forth in claim 9, wherein step 3 is the step of increasing the progressive slot counter value of the RFID tag by 1 when the RFID tag receives readable type information from the RFID reader.

12. The method as set forth in claim 9, wherein step 3 comprises:

step 3-1 of determining whether the progressive slot counter value of the RFID tag is less than the assigned slot counter value of the RFID tag when the RFID tag receives idle type information from the RFID reader; and

step 3-2 of decreasing the assigned slot counter value by 1 if, as a result of the determination at step 3-1, the progressive slot counter value is less than the assigned slot counter value.

13. The method as set forth in any one of claims 9 to 12, further comprising, after step 1 and before step 2:

step 1-1 of initializing the assigned slot counter value to 0 if the RFID tag does not have an assigned slot counter value.

14. The method as set forth in any one of claims 9 to 12, wherein, before step 1, the RFID tag receives the termination slot counter value, indicating the number of groups of RFID tags to be identified by the RFID reader, from the RFID reader at the start of the tag identification frame;

and

further comprising, after step 1 and before step 2, step 1-2 of selecting an arbitrary value ranging from 0 to the termination slot counter value and then setting the selected value as the assigned slot counter value of the RFID tag if the assigned slot counter value of the RFID tag is greater than the termination slot counter value received from the RFID reader.

15. The method as set forth in any one of claims 9 to 12, wherein, at step 4, the RFID tag terminates the tag identification frame if a command to terminate the tag identification frame is received from the RFID reader after all of the tags within the identification range of the RFID reader have been identified by the RFID reader.

16. A method of identifying a plurality of tags using an adaptive binary tree splitting technique in an RFID system, the method, when a period, in which RFID tags each send a signal, including an ID, to an RFID reader and the RFID reader sends a feedback, is defined as a time slot, and a plurality of time slots, which are required by the RFID reader to identify all the RFID tags within a current identification range of the RFID reader, constitutes a tag identification frame, enabling the RFID reader to identify all the RFID tags in such a way that the RFID tags send signals in different time slots of a single tag identification frame:

wherein the RFID has a progressive slot counter value, indicating a number of time slots in each of which an RFID tag has been identified, and a termination slot counter value, indicating a number of tag groups to be identified by the RFID reader in a single tag identification frame;

the method comprising;

a first step of initializing the progressive slot counter value thereof to 0 at a start of a tag identification frame;

a second step of feeding one piece of information selected from collision type information of a current time slot when signals are received from a plurality of RFID tags which indicate that the received signals have collided with each other, idle type information, indicating that there are no signals from the RFID tags, and readable type information, indicating that a signal has been received from a single RFID tag and the corresponding RFID tag has been identified, back to all the RFID tags within the identification range of the RFID reader, as type information of a current time slot, depending on the number of signals received from the RFID tags, in the current time slot, and setting the progressive slot counter value and termination slot counter value of the RFID reader according to the sent time slot type information, wherein if the received signals indicate the plurality of RFID tags have collided decreasing the termination slot counter value by 1; and

a third step of determining whether the progressive slot counter value is identical to the termination slot counter value, terminating the tag identification frame if the two values are identical to each other, and returning to step 2 if the two values are not identical to each other.

17. The method as set forth in claim 16, wherein step 2 comprises:

step 2-1 of sending readable type information as type information of a current time slot if a signal is received from a single RFID tag and a corresponding tag is identified; and

step 2-2 of increasing the progressive slot counter value by 1.

18. The method as set forth in claim 16, wherein step 2 comprises:

step 2-1 of sending idle type information as type information of a current time slot if a signal is not received from an RFID tag; and

step 2-2 of increasing the termination slot counter value by 1.

19. The method as set forth in any one of claims 16 and 17-18, further comprising, before step 1:

the step of sending the termination slot counter value of the RFID reader to the RFID tags if the RFID reader has a termination slot counter value at the start of the tag identification frame, and initializing the termination slot counter value to 1 if the RFID reader does not have a termination slot counter value.

20. The method as set forth in any one of claims 16 and 17-18, wherein, at step 3, the RFID reader sends a command to terminate the tag identification frame to all of the RFID tags within the identification range, and then terminates the tag identification frame if the progressive slot counter value is identical to the termination slot counter value.