# Patent

## Title
Anti-collision system and method for reducing the collision of data transmitted by RFID tags

## Abstract

Provided are an anti-collision system and method which address the mobility of radio frequency identification (RFID) tags. An RFID reader may transmit an identification start command to identify a plurality of RFID tags in an identification area of the RFID reader. The RFID tags compare the number of collisions of each RFID tag receiving the identification start command with a collision threshold Cth and attempt to be identified in a binary tree section of a frame or in a framed slotted ALOHA (FSA) section of the frame based on the comparison.

## Background
CROSS-REFERENCE TO RELATED APPLICATION(S)
This application claims the benefit under 35 USC §119(a) of Korean Patent Application No. 10-2011-0106399, filed on Oct. 18, 2011, in the Korean Intellectual Property Office, the entire disclosure of which is incorporated herein by reference for all purposes.
BACKGROUND
1. Field
The following description relates to an anti-collision system and method which reduce the collision of data transmitted by radio frequency identification (RFID) tags.
2. Discussion of Related Art
Similar to a bar code, a magnetic card, and the like, an RFID system may be used for automatic identification, and may be applied to many fields such as individual identification, product identification, location tracing, and financial services. A field that is currently drawing a lot of attention is physical distribution management, and the like, in which RFID systems are being used to replace existing bar code systems.
An RFID system may simultaneously identify a plurality of RFID tags that are present in a predetermined area. While an existing bar code system requires a line of sight (LOS) between a scanner and an object to be identified, the RFID system may identify an RFID tag without a LOS using a radio wave. Also, it is possible to identify a moving RFID tag in the predetermined area, which allows for a faster identification speed than existing identification systems.
In an RFID system, when an RFID reader attempts to identify an RFID tag in an RF area, and a plurality of RFID tags present in the RF area simultaneously transmit their identification information (identities (IDs)) to the RFID reader, the identification information may collide with each other which may prevent the RFID tags from being properly identified.
To prevent a collision of information, an RFID system may use anti-collision technology. Thus far, research has been conducted on anti-collision technology for a static situation in which an RFID tag does not move. However, an RFID system that continuously traces product movement, for example, on a conveyor belt system, and the like, must identify an RFID tag during a short time in which the RFID tag passes through the area of an RFID reader. In this example, the RFID reader fails in identification unless the RFID tag is identified in the predetermined time.
RFID anti-collision mechanisms are generally classified into framed slotted ALOHA (FSA)-based mechanisms and binary tree-based mechanisms. In a dynamic FSA (DFSA) mechanism, the number of RFID tags must be estimated to select an optimum frame size. However, when RFID tags move dynamically, it is difficult to accurately estimate the number of RFID tags.
Also, in the existing DFSA mechanism, there is no priority between an RFID tag that has undergone many collisions and an RFID tag that has not undergone many collisions. Thus, there is a high probability that an RFID tag in the identification area of an RFID reader that has undergone many collisions will compete with RFID tags that are new to the identification area. Accordingly, an RFID tag may fail to be identified, and may move out of the identification area due to its movement.
In an existing binary tree mechanism, once identification begins, RFID tags that newly flow in the identification area of an RFID reader cannot be identified until all RFID tags present in the identification area at the start of identification are identified. Because it is not possible to adjust the time to attempt identification and the number of times to attempt identification, the existing binary tree mechanism is not appropriate for a situation in which RFID tags dynamically move.
SUMMARY
In an aspect, there is provided a method for reducing the collision of data transmitted by radio frequency identification (RFID) tags, the method including transmitting, by an RFID reader, an identification start command which identifies one or more RFID tags in an identification area of the RFID reader, and comparing, at an RFID tag, a number of collisions of the respective RFID tag with a collision threshold (Cth), and adding an identification of the RFID tag in a binary tree section of a frame or in a framed slotted ALOHA (FSA) section of the frame based on the comparison.
In response to the RFID tag having a number of collisions equal to or more than Cth, the adding may comprise adding the identification of RFID tag to the binary tree section of the frame.
In response to the RFID tag having a number of collisions less than Cth, the adding may comprise adding the identification of the RFID tag to the FSA section of the frame after the binary tree section of the frame ends.
The method may further comprise transmitting, by the RFID reader, an FSA section start command in response to identification of the binary tree section being finished, and randomly selecting, by the RFID tag, natural numbers in a range from 0 to L−1 and that have decreasing transmission priorities in order of increasing value, as time slots of the FSA section of the frame with which to insert the identification of the RFID tag.
The method may further comprise transmitting, from the RFID reader, an acknowledgement (ACK) indicating that the RFID reader successfully identified the RFID tag.
In response to the RFID tag not receiving an ACK during a predetermined time period, the RFID tag may increase a number of collisions of the RFID tag by 1.
In an aspect, there is provided an anti-collision system using radio frequency identification (RFID), the anti-collision system including an RFID reader comprising an RF transceiver configured to perform transmission/reception with a plurality of RFID tags using an RF method, and an identification module configured to transmit an identification start command to identify one or more RFID tags that are present in an identification area of the RFID reader, and an RFID tag configured to compare a number of collisions of the RFID tag with a collision threshold (Cth), and to add an identification of the RFID tag in a binary tree section of a frame or in a framed slotted ALOHA (FSA) section of the frame based on the comparison.
In response to the RFID tag having a number of collisions less than Cth, the RFID tag may add the identification of the RFID tag in the FSA section of the frame after the binary tree section ends.
The identification module may transmit an FSA section start command to the RFID tag, in response to the identification of the binary tree section being finished.
The RFID tag may randomly select natural numbers in a range from 0 to L−1 and which have decreasing transmission priorities in order of increasing value, as time slots of the FSA section of the frame with which to insert the identification of the RFID tag.
The identification module may transmit an acknowledgment (ACK) to the RFID tag indicating that the RFID reader successfully identified the RFID tag.
The anti-collision system may further comprise, in response to the RFID tag not receiving an acknowledgment (ACK) within a predetermined time period, the RFID tag may increase a number of collisions of the RFID tag by 1.
The RFID tag may add the identification of the RFID tag in a next identification section of the frame.
The RFID reader may further comprise a frame determination module configured to determine a frame size L of the FSA section.
The frame determination module may calculate a number nnew of new RFID tags flowing in the identification area of the RFID reader using nnew=Tiden·Vtag·Dtag, where Vtag is a movement speed of the inflow RFID tags, and Dtag is a linear density of the inflow RFID tags.
The frame determination module may calculate a number n(i) of RFID tags having undergone collisions i times using n(i)=(Pc)i·nnew, where Pc is a probability of collision in the FSA section.
When a number of RFID tags to be identified in the binary tree section is set to n(Cth), the frame determination module may calculate the frame size L of the FSA section using




  L
  =
  
    
      ∑
      
        i
        =
        0
      
      
        
          C
          th
        
        -
        1
      
    
    ⁢
    
      
    
    ⁢
    
      
        n
        ⁡
        
          (
          i
          )
        
      
      .
    
  




A time Tbin for the binary tree section and a time TFSA for the FSA section may satisfy Tiden≧Tbin+TFSA where Tiden is a total identification period.
The frame determination module may calculate the Tbin for the binary tree section using Tbin=2.9·n(Cth)·Tslot, where 2.9 is an average number of slots used for identifying one RFID tag using a binary tree.
The frame determination module may calculate the TFSA for the FSA section using TFSA=L·Tslot.
In response to the RFID tag having a number of collisions greater than or equal to Cth, the adding may comprise adding the identification of RFID tag to the binary tree section of the frame.
Other features and aspects may be apparent from the following detailed description, the drawings, and the claims.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a diagram illustrating an example of an anti-collision system based on the mobility of radio frequency identification (RFID) tags.
FIG. 2 is a diagram illustrating an example of a frame used in an anti-collision system based on the mobility of RFID tags.
FIG. 3 is a diagram illustrating an example of a process of an anti-collision system.
FIG. 4 is a diagram illustrating an example of a comparison between an anti-collision system based on the mobility of RFID tags and an existing system.
FIG. 5 is a flowchart illustrating an example of an anti-collision method based on the mobility of RFID tags.



Throughout the drawings and the detailed description, unless otherwise described, the same drawing reference numerals will be understood to refer to the same elements, features, and structures. The relative size and depiction of these elements may be exaggerated for clarity, illustration, and convenience.
DETAILED DESCRIPTION
The following detailed description is provided to assist the reader in gaining a comprehensive understanding of the methods, apparatuses, and/or systems described herein. Accordingly, various changes, modifications, and equivalents of the methods, apparatuses, and/or systems described herein will be suggested to those of ordinary skill in the art. Also, descriptions of well-known functions and constructions may be omitted for increased clarity and conciseness.
FIG. 1 illustrates an example of an anti-collision system based on the mobility of radio frequency identification (RFID) tags. FIG. 2 illustrates an example of a frame that may be used in an anti-collision system based on the mobility of RFID tags.
Referring to FIG. 1 and FIG. 2, the anti-collision system includes a plurality of RFID tags 10 (10-1 to 10-n (where n is a natural number)) and an RFID reader 20. The RFID reader 20 includes an RF transceiver 21, and a controller 22 which includes an identification module 22a and a frame determination module 22b. In the example of FIG. 1, the RFID reader 20 identifies the RFID tags 10 while the plurality of RFID tags 10 move along a conveyor belt. In this example, the RFID reader 20 may know the average movement speed of the RFID tags 10 (e.g., predetermined speed on a conveyor belt) and the density of the RFID tags 10. Movement speed and density of the RFID tags 10 are characteristics of an RFID application system, and may be calculated after the RFID reader 20 measures the amount of inflow of RFID tags 10, or may be directly input to the RFID reader 20, for example, by an administrator of the RFID application system. In addition, the respective RFID tags 10 (10-1 to 10-n) may store their respective collisions in memories M (M-1 to M-n) while identification occurs, that is, while power is supplied from the RFID reader 20.
According to various aspects, an identification section used in an anti-collision system may include a binary tree identification section and a framed slotted ALOHA (FSA) identification section as shown in FIG. 2.
In FIG. 2, Tframe is the length of a frame that may be obtained by summing the binary tree identification section and the FSA section, Tbin is the length of the binary tree identification section, and TFSA is the length of the FSA section. In various examples, the identification module 22a of the RFID reader 20 may attempt identification at intervals of Tiden. In this example, the length of time in which the identification module 22a is in a sleep state without performing an identification operation is defined as Tsleep.
In order to identify RFID tags 10 present in an identification area, the identification module 22a may control the RF transceiver 21 to transmit an identification start command.
An RFID tag 10 may receive the identification start command of the identification module 22a and compare its number of collisions with a collision threshold Cth, and may attempt transmission to the RFID reader 20 in the binary tree section when the number of collisions is at or above the collision threshold Cth. As another example, an RFID tag 10 of which the number of collisions is less than the collision threshold Cth may attempt to be identified by the RFID reader 20 in the FSA section after the binary tree section ends.
When identification of the binary tree section is finished, the identification module 22a may transmit an FSA section start command. For example, RFID tags 10 which receive the FSA section start command and which have a numbers of collisions that is less than the collision threshold Cth, may randomly select natural numbers in a range from 0 to L−1 by exchanging RF signals with the identification module 22a, and may select the corresponding slots in the FSA section such as in order of increasing number, thereby determining a transmission sequence. Here, RFID tags 10 that select slots that do not overlap with slots of other RFID tags 10 present in the identification area should be successfully identified. On the other hand, RFID tags 10 selecting slots that overlap with the slots of the other RFID tags 10 may not be identified by the RFID reader 20 because collisions may occur. Meanwhile, the identification module 22a may transmit an ACK to the successfully identified RFID tags 10 as a response to data transmission of the RFID tags 10. The RFID tags 10 undergoing collisions cannot receive the ACK. These RFID tags 10 may recognize their collisions and may increase their number of collisions by 1.
Before the identification module 22a transmits the FSA section start command to the plurality of RFID tags 10, the frame determination module 22b of the controller 22 may determine the frame size L of the FSA section. For example, an optimum frame size may be equal to the number of RFID tags 10 to be identified. Thus, the frame size L may be adjusted according to the number of the RFID tags 10 to be identified. During an interval of identification attempts of the RFID reader 20, a number nnew of RFID tags 10 that flow in the identification area of the RFID reader 20 is as shown in Equation 1 below.

nnew=Tiden·Vtag·Dtag  [Equation 1]

In Equation 1, Vtag is the movement speed of the RFID tags 10, and Dtag is the linear density of the RFID tags 10. Thus, the number n(i) of RFID tags 10 that have undergone collisions is as shown in Equation 2 below.

n(i)=(Pc)i·nnew  [Equation 2]

Here, Pc is the probability of collision in the FSA section. Thus, the number of RFID tags 10 to be identified in the binary tree section is n(Cth).
Also, the frame size L is the number of RFID tags 10 to be identified in the FSA section and is as shown in Equation 3 below.




  
    
      
        L
        =
        
          
            ∑
            
              i
              =
              0
            
            
              
                C
                th
              
              -
              1
            
          
          ⁢
          
            
          
          ⁢
          
            n
            ⁡
            
              (
              i
              )
            
          
        
      
    
    
      
        [
        
          Equation
          ⁢
          
            
          
          ⁢
          3
        
        ]
      
    
  




When the frame size is optimal, that is, when the number of RFID tags 10 to be identified equals the frame size, the probability of collision is about 0.24. Thus, by substituting 0.24 for Pc, the frame size L in the FSA section may be calculated. Meanwhile, even if the method proposed is employed, when RFID tags 10 exceeding the maximum throughput of the RFID reader 20 flow in, the identification ratio is lowered. Thus, a constraint condition for ensuring an identification ratio is proposed. To ensure an identification ratio, the time used for the binary tree section and the FSA section should be an identification period or less. In other words, Equation 4 below should be satisfied.

Tiden≧Tbin+TFSA  [Equation 4]

Here, Tbin can be calculated as shown in Equation 5 below.

Tbin=2.9·n(Cth)·Tslot  [Equation 5]

Existing research has analyzed that the average number of slots required for identifying one RFID tag 10 using a binary tree is about 2.9. Here, Tslot is the length of one slot. Also, TFSA can be calculated as shown in Equation 6 below.

TFSA=L·Tslot  [Equation 6]

When the amount Vtag·Dtag of inflow of the RFID tags 10 is maximized while Equation 4 is satisfied, the throughput of the RFID reader 20 may be maximized while the identification ratio is ensured.
FIG. 3 illustrates an example of a process of an anti-collision system based on the mobility of RFID tags.
Referring to FIG. 3, the collision threshold Cth is 2. In this example, first and second RFID tags 10 that have undergone two collisions already attempt transmission using a binary tree mechanism. Here, the RFID reader 20 consumes a total of three slots to identify the first and second RFID tags 10. After the binary tree section ends, the FSA section starts through an FSA section start command of the RFID reader 20. As shown in the drawing, the frame size of the FSA section is 7. During the FSA section, fourth, fifth and ninth RFID tags 10 are successfully identified by the RFID reader 20. In this example, the remaining RFID tags including third, sixth, seventh and eighth RFID tags 10 are not identified by the RFID reader 20 due to collisions, and attempt to be identified again in the next identification section Tiden. Among the remaining RFID tags, the number of collisions of the third RFID tag 10 becomes 2. Accordingly, the third RFID tag 10 preferentially attempts to be identified using the binary tree mechanism.
FIG. 4 illustrates an example of a comparison between an anti-collision system based on the mobility of RFID tags and an existing system.
Referring to FIG. 4, the performance of the anti-collision system based on the mobility of RFID tags was checked. In this simulation, the radius of the identification area of the RFID reader 20 was set to 10 m, the density Dtag of RFID tags 10 was set to 70 tags/m, Cth was set to 5, and the length of one slot Tslot was set to 4 ms. In addition, the performance of identification ratio was simulated while the speed of the RFID tags 10 was increased in the anti-collision system and respective systems employing dynamic FSA (DFSA) and binary tree mechanisms.
Referring to the simulation results of FIG. 4, in the systems employing the existing DFSA and binary tree mechanisms, there were no identification priorities among the RFID tags 10, and thus, even when the RFID tags 10 moved at low speed, some RFID tags 10 moved out of the identification area of the RFID reader 20 without being identified.
However, in the method described herein according to various aspects, the identification ratio was lowered even though the RFID tags 10 moved at a speed faster than 4 m/s. This was because the amount of inflow of the RFID tags 10 exceeded the maximum throughput of the RFID reader 20. As shown in FIG. 4, the identification ratio of the proposed method was higher than the identification ratio of the existing DFSA and binary tree mechanisms.
FIG. 5 illustrates an example of an anti-collision method based on the mobility of RF tags. Referring to FIG. 1 to FIG. 5, the RFID reader 20 transmits an identification start command to identify RFID tags 10 present in its identification area in 500.
In 501, the RFID tags 10 receiving the identification start command of the RFID reader 20 may compare their numbers of collisions with a collision threshold Cth, and configure identification attempts in the binary tree section and the FSA section. For example, RFID tags 10 having a number of collisions equal to or greater than Cth attempt to be identified in the binary tree section by the RFID reader 20. In addition, RFID tags 10 having a number of collisions less than Cth attempt to be identified in the FSA section by the RFID reader 20 after the binary tree section ends.
When identification in the binary tree is finished, the RFID reader 20 transmits an FSA section start command in 502. Accordingly, the RFID tags 10 that have numbers of collisions less than Cth and receive the FSA section start command, randomly select natural numbers in a range from 0 to L−1, thereby determining a transmission sequence in the corresponding slots of the FSA section in order of increasing number in 503. For example, RFID tags 10 selecting slots that do not overlap slots of other RFID tags 10 present in the identification area of the RFID reader 20 may be successfully identified, whereas RFID tags 10 selecting slots that overlap the slots of the other RFID tags 10 may not be identified because collisions may occur. In 504, the RFID reader 20 transmits an ACK to the successfully identified RFID tags 10 as a response to data transmission of the RFID tags 10.
Accordingly, the RFID tags 10 that undergo collisions cannot receive the ACK, thereby recognizing their collisions and increasing their number of collisions by 1 in 505. In 506, the RFID tags 10 that have not been identified due to collisions attempt to be identified in the next identification section.
According to various aspects, the anti-collision system may improve an identification ratio in a case in which RFID tags move in an RFID system, thereby improving reliability and maximum throughput of the RFID system. For example, RFID tags may be identified using an FSA mechanism. During this process, the number of transmission attempts made due to collisions between each RFID tag and other RFID tags is recorded, and another identification method is attempted for the corresponding RFID tags when the number of transmission attempts reaches a predetermined threshold or more.
In addition, an RFID tag that is highly likely to fail in identification based on the binary tree mechanism is preferentially identified, such that reliability and maximum throughput of an RFID system can be improved.
Furthermore, the anti-collision system may enable an increase in the maximum movement speed of an RFID tag due to improved reliability of identification of an RFID tag in an RFID system, and also a reduction in cost by reducing the number of RFID readers.
Program instructions to perform a method described herein, or one or more operations thereof, may be recorded, stored, or fixed in one or more computer-readable storage media. The program instructions may be implemented by a computer. For example, the computer may cause a processor to execute the program instructions. The media may include, alone or in combination with the program instructions, data files, data structures, and the like. Examples of computer-readable storage media include magnetic media, such as hard disks, floppy disks, and magnetic tape; optical media such as CD ROM disks and DVDs; magneto-optical media, such as optical disks; and hardware devices that are specially configured to store and perform program instructions, such as read-only memory (ROM), random access memory (RAM), flash memory, and the like. Examples of program instructions include machine code, such as produced by a compiler, and files containing higher level code that may be executed by the computer using an interpreter. The program instructions, that is, software, may be distributed over network coupled computer systems so that the software is stored and executed in a distributed fashion. For example, the software and data may be stored by one or more computer readable storage mediums. Also, functional programs, codes, and code segments for accomplishing the example embodiments disclosed herein can be easily construed by programmers skilled in the art to which the embodiments pertain based on and using the flow diagrams and block diagrams of the figures and their corresponding descriptions as provided herein. Also, the described unit to perform an operation or a method may be hardware, software, or some combination of hardware and software. For example, the unit may be a software package running on a computer or the computer on which that software is running.
A number of examples have been described above. Nevertheless, it will be understood that various modifications may be made. For example, suitable results may be achieved if the described techniques are performed in a different order and/or if components in a described system, architecture, device, or circuit are combined in a different manner and/or replaced or supplemented by other components or their equivalents. Accordingly, other implementations are within the scope of the following claims.

## Claims

1. A method for reducing the collision of data transmitted by radio frequency identification (RFID) tags, the method comprising:
transmitting, by an RFID reader, an identification start command which identifies one or more RFID tags in an identification area of the RFID reader; and
comparing, at an RFID tag, a number of collisions of the respective RFID tag with a collision threshold (Cth), and adding an identification of the RFID tag in a binary tree section of a frame or in a framed slotted (ALOHA (FSA)) section of the frame based on the comparison.

2. The method of claim 1, wherein, in response to the RFID tag having a number of collisions equal to or more than Cth, the adding comprises adding the identification of RFID tag to the binary tree section of the frame.

3. The method of claim 1, wherein, in response to the RFID tag having a number of collisions less than Cth, the adding comprises adding the identification of the RFID tag to the FSA section of the frame after the binary tree section of the frame ends.

4. The method of claim 3, further comprising:
transmitting, by the RFID reader, an FSA section start command in response to identification of the binary tree section being finished; and
randomly selecting, by the RFID tag, natural numbers in a range from 0 to L-1 and that have decreasing transmission priorities in order of increasing value, as time slots of the FSA section of the frame with which to insert the identification of the RFID tag.

5. The method of claim 4, further comprising transmitting, from the RFID reader, an acknowledgement (ACK) indicating that the RFID reader successfully identified the RFID tag.

6. The method of claim 5, wherein, in response to the RFID tag not receiving an acknowledgement (ACK) during a predetermined time period, the RFID tag increases a number of collisions of the RFID tag by 1.

7. The method of claim 1, wherein the RFID tags recognize their collisions.

8. The method of claim 1, wherein the collision threshold (Cth) prevents a missing tag that could not be identified by the RFID reader.

9. An anti-collision apparatus using radio frequency identification (RFID), the anti-collision apparatus comprising:
an RFID reader comprising
an RF transceiver configured to perform transmission/reception with RFID tags using an RF method; and
an identification module configured to transmit an identification start command to identify one or more RFID tags that are present in an identification area of the RFID reader; and

an RFID tag configured to compare a number of collisions of the RFID tag with a collision threshold (Cth), and to add an identification of the RFID tag in a binary tree section of a frame or in a framed slotted (ALOHA (FSA)) section of the frame based on the comparison.

10. The anti-collision apparatus of claim 9, wherein, in response to the RFID tag having a number of collisions less than Cth, the RFID tag adds the identification of the RFID tag in the FSA section of the frame after the binary tree section ends.

11. The anti-collision apparatus of claim 10, wherein the RFID tag randomly selects natural numbers in a range from 0 to L-1 and which have decreasing transmission priorities in order of increasing value, as time slots of the FSA section of the frame with which to insert the identification of the RFID tag.

12. The anti-collision apparatus of claim 10, wherein the identification module transmits an acknowledgment (ACK) to the RFID tag indicating that the RFID reader successfully identified the RFID tag.

13. The anti-collision apparatus claim 10, further comprising, in response to the RFID tag not receiving an acknowledgment (ACK) within a predetermined time period, the RFID tag increases a number of collisions of the RFID tag by 1.

14. The anti-collision apparatus of claim 13, wherein the RFID tag adds the identification of the RFID tag in a next identification section of the frame.

15. The anti-collision apparatus claim 9, wherein the identification module transmits an FSA section start command to the RFID tag, in response to the identification of the binary tree section being finished.

16. The anti-collision apparatus of claim 9, wherein the RFID reader further comprises a frame determination module configured to determine a frame size L of the FSA section.

17. The anti-collision apparatus of claim 16, wherein the frame determination module calculates a number nnew, of new RFID tags flowing in the identification area of the RFID reader using nnew=Tiden·Vtag·Dtag, where Vtag is a movement speed of the inflow RFID tags, and Dtag is a linear density of the inflow RFID tags.

18. The anti-collision apparatus of claim 16, wherein the frame determination module calculates a number n(i) of RFID tags having undergone collisions i times using n(i)=(Pc)i·nnew, where Pc is a probability of collision in the FSA section.

19. The anti-collision apparatus of claim 16, wherein, when a number of RFID tags to be identified in the binary tree section is set to n(Cth), the frame determination module calculates the frame size L of the FSA section using




  L
  =
  
    
      ∑
      
        i
        =
        0
      
      
        
          C
          th
        
        -
        1
      
    
    ⁢
    
      
    
    ⁢
    
      
        n
        ⁡
        
          (
          i
          )
        
      
      .

20. The anti-collision apparatus claim 9, wherein a time Tbinfor the binary tree section and a time TFSA for the FSA section satisfy Tiden≧Tbin+TFSA where Tidenis a total identification period.

21. The anti-collision apparatus of claim 20, wherein the frame determination module calculates the Tbinfor the binary tree section using Tbin=2.9·n(cth)·Tslot, where 2.9 is an average number of slots used for identifying one RFID tag using a binary tree.

22. The anti-collision apparatus claim 20, wherein the frame determination module calculates the TFSA for the FSA section using TFSA=L ·TSlot.

23. The anti-collision apparatus of claim 9, wherein, in response to the RFID tag having a number of collisions greater than or equal to Cth, the adding comprises adding the identification of RFID tag to the binary tree section of the frame.