TAG ESTIMATION METHOD AND TAG IDENTIFICATION METHOD FOR RFID SYSTEM

• US 20090134975A1
• Filed: 02/07/2008
• Published: 05/28/2009
• Est. Priority Date: 11/23/2007
• Status: Active Grant

• Current Assignee: Intellectual Discovery Co., Ltd.
• Original Assignee: Sungkyunkwan University Foundation For Corporate Collaboration (SungKyunKwan University)
• Inventors: Lee, Taejin, EOM, Junbong
• Granted Patent: US 8,115,602 B2
• Time in Patent Office: Days
• US Class Current: 340/10.200
• 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
• CPC Class Codes: H04W 8/005 Discovery of network devices, e.g. terminals

Abstract

Provided are a tag estimation method and a tag identification method using the same in a RFID system. In the tag estimating method, a reader divides tags in an identifiable area into a predetermined number of groups. Tags are identified by applying a pilot frame L_p to a first group among the divided groups. The reader calculates a collision probability P_coll of tags after the pilot frame ends. Then, unidentified tags of the first group, which are not identified for the pilot frame, are identified by allocating an additional pilot slot L_add at an end of the pilot frame or generating a new frame L₁ according to the collision probability Pcoll.

Claims

1. A method for estimating the number of tags in a RFID system, comprising the steps of:

a) at a reader, dividing tags in an identifiable area into a predetermined number of groups;

b) identifying tags by applying a pilot frame L_p to a first group among the divided groups in the step a);

c) at a reader, calculating a collision probability P_coll of tags after the pilot frame ends; and

d) identifying unidentified tags of the first group, which are not identified for the pilot frame, by allocating an additional pilot slot Ladd at an end of the pilot frame or generating a new frame L₁ according to the collision probability P_coll.

2. The method of claim 1, wherein in the step a), the reader uses a bit mask to divide tags into a predetermined number of groups.

3. The method of claim 2, wherein in the step b), when tags collide during the pilot frame L_p, random counters of collided tags are changed according to the number of remaining time slots in the pilot frame and a collision order in the pilot frame and an identification number of a tag is transmitted at a time slot where the random counter become 0.

4. The method of claim 3, wherein the random counters of tags collided for the pilot frame L_p is changed based on equation:

Counter=the number of time slots remained in L_p+2×

(collision order−

1)+rand(0 or

     1).

5. The method of claim 4, wherein the step d) includes the step of comparing the collision probability P_coll with a predetermined threshold P_th,

wherein if the collision probability P_coll is smaller than the predetermined threshold P_th, an additional time slot L_add is allocated at an end of the pilot frame, and unidentified tags in the first group are identified, and

wherein if the collision probability P_coll is larger than the predetermined threshold P_th, unidentified tags in the first group are identified by generating a new frame after the pilot frame.

6. The method of claim 5, wherein in the additional time slot L_add,

tags transmit identification numbers thereof to a reader when random counters of the tags, which continuously decrease from the pilot frame L_p, become 0, and

collided tags in the additional time slot L_add select 0 or 1 as a random counter, remaining unidentified tags increase random counters by 1, each of tags decreases a random counter sequentially, and each of tags transmits an identification unit at a time slot where a random counter becomes 0.

7. The method of claim 6, wherein in the new frame L₁,

unidentified tags, which are not identified in the pilot frame L_p, begins counting a new random counter and transmits an identification number to a reader when the new random counter become 0, and

collided tags in the new frame L₁ select 0 or 1 as a random counter, remaining unidentified tags increase random counters by 1, each of tags sequentially decreases a random counter, and each of tags transmits an identification number at a time slot where a random counter becomes 0.

8. The method of claim 7, wherein a size of the new frame L1 is decided a minimum value of n that satisfy an equation:

$\begin{array}{c}{P}_{\mathrm{coll}}=1-P_{\mathrm{idle}}-P_{\mathrm{succ}}\\ =1-{\left(1-\frac{1}{L_P}\right)}^n-n<br><br><br><br>\frac{1}{L_P}<br><br>{\left(1-\frac{1}{L_P}\right)}^{n-1}.,\end{array}$

where, n denotes the number of tags, L_p denotes a size of a pilot frame, P_coll denotes a collision probability, P_idle denotes a valid probability, and P_succ is a success probability.

9. A method for identifying tags in a RFID system, comprising the steps of:

a) at a reader, dividing tags in an identifiable area into a predetermined number of groups;

b) identifying tags by applying a pilot frame L_p to a first group among the divided groups in the step a);

c) at a reader, calculating a collision probability P_coll of tags after the pilot frame ends;

d) identifying unidentified tags of the first group, which are not identified for the pilot frame, by allocating an additional pilot slot Ladd at an end of the pilot frame or generating a new frame L₁ according to the collision probability P_coll,

e) deciding an optimal frame size L_opt based on the number of tags of the first group, which are estimated through the steps a) to d);

f) identifying tags in a second group by applying the decided optimal frame size L_opt; and

g) identifying tags of a current group by applying an optimal frame size L_opt decided based on the number of identified tags in a previously group, and repeating the step g) for identifying tags in remaining groups after the second group.

10. The method of claim 9, wherein the optimal frame size L_opt is decided by differentiating an equation for the number n of tags identified in a previously groups, where the equation is:

$T=\underset{k=0}{\overset{n}{\sum <br><br>}}<br><br>{{}_{n}C_k<br><br>\left(\frac{1}{L_{\mathrm{opt}}}\right)}^k<br><br>{\left(1-\frac{1}{L_{\mathrm{opt}}}\right)}^{n-k}<br><br>L_{\mathrm{opt}}<br><br>\left({\mathrm{\alpha <br><br>}}_k+1\right).,$

wherein T denotes the total number of time slots for identifying tags, n is the number of identified tags in a previous group. k is the number of tags transmitted in one time slot, and α

k is the average number of time slots used for a binary tree algorithm when collision occurs.

11. The method of claim 10, wherein the optimal frame size is 0.88n where n is the number of identified tags in a previous group.

12. The method of claim 11, wherein in the steps f) and g), each of tags transmits an identification number to a reader when a random counter becomes 0, tags collided in a corresponding frame select 0 or 1 as a random counter, each of remaining unidentified tags increases a random counter by 1, each of tags sequentially decreases a random counter, and each of tags transmits an identification number at a time slot where a random counter becomes 0.