WO2008084998A1

WO2008084998A1 - Method of determining frame size in rfid reader, and rfid reader and recording medium using the same

Info

Publication number: WO2008084998A1
Application number: PCT/KR2008/000162
Authority: WO
Inventors: Sung Ho Cho; Sung Moon Jang; Woo Jin Lee
Original assignee: Industry University Cooperation Foundation IUCF HYU
Current assignee: Industry University Cooperation Foundation IUCF HYU
Priority date: 2007-01-10
Filing date: 2008-01-10
Publication date: 2008-07-17
Anticipated expiration: 2009-07-10
Also published as: KR20080065877A; KR100855826B1

Abstract

A method of determining a frame size in a Radio Frequency Identification (RFID) reader, an RFID reader using the method, and a recording medium storing a program for executing the method are provided. In the method of determining a frame size in order for the RFID reader to identify a transponder, a system efficiency of a current read cycle is calculated according to a result of reading a plurality of transponders, a system efficiency of one or more read cycles previously performed are compared with a system efficiency of the current read cycle, and a frame size of a next read cycle is determined. Accordingly, a system can be simply implemented, and a system performance can be optimized based on system efficiency.

Description

METHOD OF DETERMINING FRAME SIZE IN RFID READER, AND RFID READER AND RECORDING MEDIUM USING THE

SAME

Technical Field

[1] The present invention relates to a Radio Frequency Identification (RFID) reader, and more particularly, to a method of determining a frame size to be used in the RFID reader to identify a plurality of transponders. [2]

Background Art [3] In wireless identification technologies, there is a Radio Frequency Identification

(RFID) technology that identifies entities by using a Radio Frequency (RF) signal. [4] An RFID system is constructed of a reader and one or more transponders. When a plurality of transponders intend to simultaneously response to an instruction of the reader, responses of the transponders may collide with one another. Therefore, there is a need for an algorithm (e.g., Anti-collision algorithm) that can prevent collision between responses of the transponders. [5] A slotted Aloha procedure is a typical example of the anti-collision algorithm used in the conventional RFID system. The slotted Aloha procedure is a wireless identification technology which synchronizes each transponder, and transmits data by dividing a time period for transmitting the data into a unit of slot. [6] The conventional slotted Aloha procedure can be classified into a Basic Framed

Slotted Aloha (BFSA) algorithm, a Dynamic Framed Slotted Aloha (DFSA) algorithm, and an Advanced Framed Slotted Aloha (AFSA) algorithm. [7] According to the BFSA algorithm, implementation is simple because a size of frame used between a reader and a transponder is fixed. However, there is a demerit in that an identification efficiency of the transponder deteriorates. [8] For example, although the number of transponders is large, if a small-sized frame is used, the number of times of repeating a read cycle increases, thereby increasing a reading time. When the number of transponders is small, the use of a large sized- frame may result in waste of slots. [9] In the DFSA algorithm, a frame size is changed by considering data collision or the like. The AFSA algorithm is an improved algorithm of the conventional BFSA algorithm. [10] Specifically, in the DFSA algorithm and the AFSA algorithm, transponders are identified in such a manner that the number of transponders in an identification range of the reader is estimated, and an optimal frame size is determined to read the estimated number of transponders.

[11] Since the frame size is determined by estimating the number of transponders, the frame-slotted Aloha algorithms can identify transponders in a more effective way than any other conventional algorithms. However, the conventional technology has a problem in that an operation of estimating the number of transponders or the like results in an increase in implementation complexity, and thus a time for identifying all transponders may increases.

[12]

Disclosure of Invention Technical Problem

[13] The present invention provides a method of determining a frame size in a Radio

Frequency Identification (RFID) reader, of which performance can be optimized based on an identification rate of a transponder, that is, based on system efficiency, and which can be simply implemented, and an RFID reader using the method.

[14] The present invention also provides a method of determining a frame size in an RFID reader using a Throughput Adaptive Framed Slotted Aloha (TAFSA) algorithm capable of increasing a response time of a transponder and a system efficiency by adjusting the number of transponders, each of which responds to a request of the reader, to a frame size as much as possible, and an RFID reader using the method.

[15]

Technical Solution

[16] According to an aspect of the present invention, there is provided a method of determining a frame size in an RFID reader, comprising: in a process performed by repeating a read cycle in order for the RFID reader to identify a plurality of transponders, detecting frame sizes used in read cycles; among the detected frame sizes, comparing a frame size of a current read cycle with a frame size of a previous read cycle that is performed before the current read cycle is performed; calculating system efficiencies of the read cycles by using the detected frame sizes; among the calculated system efficiencies, comparing a system efficiency of the current read cycle with a system efficiency of the previous read cycle; and determining a frame size to be used in a next read cycle according to the frame size comparison result and the system efficiency comparison result.

[17] In the aforementioned aspect of the present invention, the previous read cycle compared with the current read cycle may be a read cycle performed immediately before the current read cycle. In addition, the system efficiency s, may be calculated by using Math Figure:

_ number of identified transponders _ ^ ^aSid total number of slots Tag _Id+Tag_Idle+Tag _Coll

, where

Tag coil denotes the number collision-generated slots,

Tag_Id denotes the number of slots that identify the transponders, and

Tagidie denotes the number of empty slots.

[18] In addition, the frame size to be used in the next read cycle may increase or decrease by a multiple of K (a predetermined arbitrary natural number) in comparison with the frame size of the current read cycle.

[19] In addition, in the determining a frame size, if the frame size comparison result shows that the frame size of the current read cycle increases to be greater than the frame size of the previous read cycle, a frame size to be used in the next read cycle may be increased when the system efficiency comparison result shows that the system efficiency of the current read cycle is greater than the system efficiency of the previous read cycle, and the frame size to be used in the next read cycle may be decreased when the system efficiency of the current read cycle is less than the system efficiency of the previous read cycle. In the determining a frame size, if the frame size comparison result shows that the frame size of the current read cycle decreases to be less than the frame size of the previous read cycle, a frame size to be used in the next read cycle may be decreased when the system efficiency comparison result shows that the system efficiency of the current read cycle is greater than the system efficiency of the previous read cycle, and the frame size to be used in the next read cycle may be increased when the system efficiency of the current read cycle is less than the system efficiency of the previous read cycle. In the determining a frame size, if the system efficiency comparison result shows that the system efficiency of the current read cycle is equal to the system efficiency of the previous read cycle, the frame size to be used in the next read cycle may be determined to be equal to the frame size of the current read cycle.

[20] According to another aspect of the present invention, there is provided an RFID reader comprising: a frame size detector which detects frame sizes used in read cycles in a process performed by repeating a read cycle to identify a plurality of transponders; a frame size comparator which compares, among the detected frame sizes, a frame size of a current read cycle with a frame size of a previous read cycle that is performed before the current read cycle is performed; a system efficiency calculator which calculates system efficiencies of the read cycles by using the detected frame sizes; a system efficiency comparator which compares, among the calculated system efficiencies, a system efficiency of the previous read cycle with a system efficiency of the current read cycle; and a frame size determining unit which receives the comparisons results from the frame size comparator and the system efficiency comparators, and determines a frame size to be used in a next read cycle according to the comparison results. [21] In the aforementioned aspect of the present invention, the previous read cycle compared with the current read cycle may be a read cycle performed immediately before the current read cycle. In addition, the system efficiency

S₁ may be calculated by using Math Figure:

g = number of identified transponders * ^agid total number of slots Tag _Id+Tag_Idle+Tag _Co/;

, where

Tag_Coll denotes the number collision-generated slots,

Tag_M denotes the number of slots that identify the transponders, and

Tag_Idle denotes the number of empty slots. [22] In addition, if the result obtained from the frame size comparator shows that the frame size of the current read cycle increases to be greater than the frame size of the previous read cycle, the frame size determining unit may increase a frame size to be used in the next cycle when the result obtained from the system efficiency comparator shows that the system efficiency of the current read cycle is greater than the system efficiency of the previous read cycle, may decrease the frame size to be used in the next frame when the result shows that the system efficiency of the current read cycle is less than the system efficiency of the previous read cycle, and may maintain the frame size of the current read cycle when the system efficiency of the current read cycle is equal to the system efficiency of the previous read cycle. In addition, if the result obtained from the frame size comparator shows that the frame size of the current read cycle decreases to be less than the frame size of the previous read cycle, the frame size determining unit may decrease a frame size to be used in the next cycle when the result obtained from the system efficiency comparator shows that the system efficiency of the current read cycle is greater than the system efficiency of the previous read cycle, may increase the frame size to be used in the next frame when the result shows that the system efficiency of the current read cycle is less than the system efficiency of the previous read cycle, and may maintain the frame size of the current read cycle when the system efficiency of the current read cycle is equal to the system efficiency of the previous read cycle.

[23] In addition, the frame size to be used in the next read cycle may increase or decrease by a multiple of K (a predetermined arbitrary natural number) in comparison with the frame size of the current read cycle.

[24] According to another aspect of the present invention, there is provided a recording medium storing a program, which is readable by a data processing apparatus and comprises program codes executable by the digital processing apparatus, for executing a method of determining a frame size for identifying a transponder by an RFID reader using a frame-slotted Aloha algorithm, the method comprising: in a process performed by repeating a read cycle in order for the RFID reader to identify a plurality of transponders, detecting frame sizes used in read cycles; among the detected frame sizes, comparing a frame size of a current read cycle with a frame size of a previous read cycle that is performed before the current read cycle is performed; calculating system efficiencies of the read cycles by using the detected frame sizes; among the calculated system efficiencies, comparing a system efficiency of the current read cycle with a system efficiency of the previous read cycle; and determining a frame size to be used in a next read cycle according to the frame size comparison result and the system efficiency comparison result.

[25] In the aforementioned aspect of the present invention, the previous read cycle compared with the current read cycle may be read cycle performed immediately before the current read cycle. In addition, the system efficiency s, may be calculated by using Math Figure: number of identified transponders * ^agid total number of slots Tag_Id+Tag_Idk+Tag _Coll where Tag Coll denotes the number collision-generated slots,

Tag_Id denotes the number of slots that identify the transponders, and

Tagidie denotes the number of empty slots.

[26] In addition, in the determining a frame size, if the frame size comparison result shows that the frame size of the current read cycle increases to be greater than the frame size of the previous read cycle, a frame size to be used in the next read cycle may be increased when the system efficiency comparison result shows that the system efficiency of the current read cycle is greater than the system efficiency of the previous read cycle, and the frame size to be used in the next read cycle may be decreased when the system efficiency of the current read cycle is less than the system efficiency of the previous read cycle, if the frame size comparison result shows that the frame size of the current read cycle decreases to be less than the frame size of the previous read cycle, a frame size to be used in the next read cycle may be decreased when the system efficiency comparison result shows that the system efficiency of the current read cycle is greater than the system efficiency of the previous read cycle, and the frame size to be used in the next read cycle may be increased when the system efficiency of the current read cycle is less than the system efficiency of the previous read cycle, and if the system efficiency comparison result shows that the system efficiency of the current read cycle is equal to the system efficiency of the previous read cycle, the frame size to be used in the next read cycle may be determined to be equal to the frame size of the current read cycle.

Advantageous Effects

[27] The present invention provides a method of determining a frame size in a Radio

Frequency Identification (RFID) reader, which can be simply implemented and of which performance can be optimized based on system efficiency, and an RFID reader using the method.

[28] In addition, the present invention can reduce a response time of a transponder and improve system efficiency since the number of transponders, each of which responds to a request of a reader, can be adjusted to a frame size as much as possible.

[29]

Brief Description of the Drawings

[30] The above and other features and advantages of the present invention will become more apparent by describing in detail exemplary embodiments thereof with reference to the attached drawings in which:

[31] Fig. 1 is a schematic view of a system including a Radio Frequency Identification

(RFID) reader and a plurality of transponders according to an embodiment of the present invention;

[32] Fig.2 is a flowchart illustrating a method of determining a frame size of first and second read cycles in an RFID reader using a Throughput Adaptive Framed Slotted Aloha (TAFSA) algorithm according to an embodiment of the present invention;

[33] Fig. 3 is a flowchart illustrating a procedure of determining a frame size of a third (or more) read cycle in an RFID reader using a TAFSA algorithm according to an embodiment of the present invention;

[34] Fig. 4 is a block diagram of a TAFSA system according to an embodiment of the present invention;

[35] Fig. 5 and Fig. 6 are respectively a graph and a table illustrating the number of read cycles and a frame size with respect to the number of transponders according to an embodiment of the present invention; and

[36] Fig. 7 is a graph for comparing a system efficiency of a TAFSA algorithm according to an embodiment of the present invention with a conventional BFSA algorithm, where the number of transponders is in the range of 1 to 50.

[37]

Mode for the Invention

[38] Although various modifications may be made in the present invention, and several exemplary embodiments of the present invention may be provided, the present invention will hereinafter be described in connection with what is presently considered to be practical exemplary embodiments. However, it is to be understood that the invention is not limited to the disclosed embodiments, but, on the contrary, is intended to cover various modifications and equivalent arrangements included within the spirit and scope of the appended claims.

[39] It will be understood that although the terms first and second are used herein to describe various elements, these elements should not be limited by these terms. These terms are only used to distinguish one element from another element. Thus, a first element discussed below may be termed a second element, and similarly, a second element may be termed a first element without departing from the scope of the present invention. As used herein the term "and/or" includes any and all combinations of one or more of the associated listed items.

[40] It will be understood that when an element is referred to as being "connected" or

"coupled" to another element, it can be directly connected or coupled to the other element or intervening elements may be present. In contrast, when an element is referred to as being "directly connected" or "directly coupled" to another element, there are no intervening elements present.

[41] The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the invention. As used herein, the singular forms "a", "an", and "the" are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms "comprises" and/or "comprising," or "includes" and/or "including", when used in this specification, specify the presence of stated features, regions, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, regions, integers, steps, operations, elements, components, and/or groups thereof.

[42] Unless otherwise defined, all terms (including technical and scientific terms) used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this invention belongs. It will be further understood that terms, such as those defined in commonly used dictionaries, should be interpreted as having a meaning that is consistent with their meaning in the context of the relevant art and the present disclosure, and will not be interpreted in an idealized or overly formal sense unless expressly so defined herein.

[43] Hereinafter, exemplary embodiments of the present invention will be described with reference to the accompanying drawings. It is to be noted that like reference numerals denote the same components in the drawings, and a detailed description of a known structure or function of the present invention will be omitted herein if it is deemed to obscure the subject matter of the present invention.

[44] Fig. 1 is a schematic view of a system including a Radio Frequency Identification

(RFID) reader and a plurality of transponders according to an embodiment of the present invention.

[45] Referring to Fig. 1, the RFID system includes an RFID reader 110 and a plurality of transponders 120-1 to 120-n (hereinafter, collectively referred to as 120). That is, in the RFID system, all RF transponders 120 located in an identification area of the RFID reader 110 concurrently receive Radio Frequency (RF) signals transmitted by the RFID reader 110 through a wireless channel, and respond to a transmission request of the RFID reader 110.

[46] The RFID reader 110 processes signals received from the transponders 120, and may store the signals in a memory or may transmit the signals to an external element in a later time. That is, the RFID reader 110 supplies power to the transponders 120 in a wireless fashion. Upon receiving sufficient power required for operations, the transponders 120 respond according to an instruction received from the RFID reader 110.

[47] As such, the plurality of transponders 120 included in the identification area of the

RFID reader 110 transmit response data according to an instruction signal received from the RFID reader 110. Collision may occur in the response data to be identified by the RFID reader 110 (that is, collision occurs when the plurality of transponders transmit the response data in the same slot). In this case, since the RFID reader 110 cannot identify the collision-generated response data, a retransmission instruction is sent to the corresponding transponders 120 at a next read cycle. As a result, a time required for the RFID reader 110 to identify all transponder 120 increases.

[48] In order to reduce collision of the response data and to increase system efficiency for identifying a transponder, a Throughput Adaptive Framed Slotted Aloha (TAFSA) algorithm of the present invention determines a frame size of the next read cycle by comparing a system efficiency of a current read cycle and a system efficiency of a previous read cycle.

[49] According to the present embodiment, an increase or decrease in the number of slots is controlled whenever a transmission request is generated. Therefore, waste in the number of slots can be prevented and the number of times of requesting retransmission can be reduced. As a result, an identification time of the transponder 120 can be reduced.

[50] One frame includes a time slot that is a specific time period during which an RF device uses a channel. That is, one frame can be divided into one or more slots in which one transponder 120 can transmit response data to the RFID reader 110. For example, if three slots constitute one frame, the RFID reader 110 can receive and process three pieces of response data during one frame.

[51] A read cycle relates to the number of times of sending a transmission instruction by a reader in order to read all transponders. One read cycle may indicate a time between a time point when the RFID reader 110 transmits an instruction to the transponder 120 and a time point when a next instruction is transmitted.

[52] A method of determining a frame size by comparing a system efficiency of a current read cycle with a system efficiency of a previous read cycle may be implemented in various manners.

[53] For example, the aforementioned previous read cycle may be a first read cycle, or a read cycle having the highest system efficiency among previous read cycles performed prior to the current read cycle, or an immediately -previous read cycle of the current ready cycle.

[54] Hereinafter, for convenience of explanation, the "previous read cycle" is assumed to be the immediately-previous read cycle of the current read cycle.

[55] In addition, in a procedure of determining a frame size according to the present em- bodiment, a first read cycle process, a second read cycle process, and a third (or more) read cycle process are performed in different manners.

[56] For example, for the first read cycle, the frame size may be pre-defined since there is no previous read cycle to be compared.

[57] In case of the second read cycle, the frame size may be determined in a default (or random) manner by comparing with the first read cycle. For example, if the frame size of the first read cycle is 5, the frame size of the second read cycle may be determined to be increased (or decreased) by 2 slots in a default manner. Alternatively, the number of slots to be increased or decreased may be defined in a random manner.

[58] In addition, a system efficiency of the first read cycle may be calculated, and whether to increase or decrease the frame size of the second read cycle may be determined according to the calculated system efficiency.

[59] Now, a frame determining procedure for the first and second read cycles will be described with reference to Fig. 2, and a frame determining procedure for the third (or more) read cycle will be described with reference to Fig. 3.

[60] Fig.2 is a flowchart illustrating a method of determining a frame size of first and second read cycles in an RFID reader according to an embodiment of the present invention.

[61] In the case of the first read cycle, the RFID reader 110 sets the frame size to a default

(or random) value in step 210. In step 220, the RFID reader 110 reads a transponder located within an identification area of the RFID reader 110 by using the frame size.

[62] In step 230, the RFID reader 110 determines whether all transponders 120 located in the identification area are identified. Whether all transponders 120 located in the identification area are successfully identified may be determined according to whether there is a slot identified during a frame in association with a read cycle.

[63] If even one slot is identified, it can be determined that all transponders 120 have failed to be identified. On the other hand, if no slot is identified, it can be determined that all transponders 120 have been successfully identified.

[64] If the determination result of step 230 shows that all transponders 120 have been identified, the RFID reader 110 no longer has to send a transmission request to the transponder 120. Therefore, the RFID reader 110 finishes a transponder identification process. However, this does not mean that the system finishes entire operations. Rather, the system may be regarded as being entered to a standby mode. That is, as soon as another transponder approaches to the identification area, the RFID reader 110 can read the transponder.

[65] Otherwise, if it is determined that there is a transponder 120 that has failed to be identified among the transponders 120 located in the identification area, in step 240, the RFID reader 110 compares a system efficiency S, of the first read cycle with a predetermined value L (e.g., 30%). A method of calculating the system efficiency

S₁ will be described below with reference to Fig. 3. [66] In step 250, if the system efficiency

S₁ is greater than or equal to the value L, the RFID reader 110 may increase the frame size of the second read cycle in step 260, and if it is less than the value L, the RFID reader 110 may decrease the frame size of the second read cycle in step 265. Of course, the RFID reader 110 may be configured to operate in an opposite way.

[67] When the frame size of up to the second read cycle is determined according to the aforementioned steps, the RFID reader 110 performs the second read cycle by reading the transponder 120 by the use of a corresponding frame in step 270.

[68] Thereafter, similar to step 230, the RFID reader 110 determines whether the identification process is finished by the second read cycle in step 280.

[69] If all transponders 120 are identified, the RFID reader 110 finishes the procedure, and enters to the standby mode. However, if the identification process is not finished, the RFID reader 110 enters to a second mode. The "second mode" represents a frame determining procedure for the third (or more) read cycle.

[70] Fig. 3 is a flowchart illustrating a procedure of determining a frame size of a third (or more) read cycle in an RFID reader using a TAFSA algorithm according to an embodiment of the present invention.

[71] Referring to Fig. 3, with respect to consecutive read cycles for identifying a transponder, the RFID reader 110 calculates a system efficiency

S₁ of each read cycle in step 320. Referring also to Fig. 2, in order to determine the frame size of the third read cycle, a system efficiency

S₁ of the second read cycle is calculated. In this case, the same result may be obtained even if the system efficiency computation for each read cycle is performed after step 330. [72] The system efficiency S₁ is provide by using the number of collision-generated slots

Tag_Coll

, the number of slots

Tag_Id that have identified the transponder 120, and the number of empty slots

Tag w_e

, and is expressed by the following Math Figure 1. [73] MathFigure 1

[Math.l]

_ number of identified transponders _ * ag_Id total number of slots Tag_Id+Tag_Idk+Tag_Coll

[74] In Math Figure 1, the system efficiency decreases when the number of collision- generated slots increases or when the number of empty slots increases.

[75] Therefore, in order to obtain an optimal system efficiency, a frame size has to be properly determined so that factors corresponding to the denominator of Math Figure 1 can decrease. That is, in order to decrease the number of collision-generated slots, the frame size has to be determined not to be too small, and in order to decrease the number of empty slots, the frame size has to be determined not to be too great.

[76] In summary, to obtain the highest system efficiency, the frame size needs to be maintained so that the number of slots is properly adjusted to the number of identifiable transponders 120.

[77] A process of detecting the number of slots, that is, the frame size, has to be first performed to calculate the system efficiency s,

. To this purpose, the RFID reader 110 detects a frame size of each read cycle in step 310 before the system efficiency is calculated in step 320.

[78] In step 330, the RFID reader 110 determines whether a frame size of a current read cycle increases in comparison with a previous read cycle. Although it is shown in Fig. 3 that step 330 is performed after step 320, steps 330 and 320 may be simultaneously performed or may be performed in a reverse order as long as step 320 is performed prior to steps 340 and 350. [79] If the determination result of step 330 shows that the frame size of the current read cycle increases to be greater than the frame size of the previous read cycle, the RFID reader 110 compares a system efficiency

of the previous cycle with the system efficiency s, of the current read cycle in step 340.

[80] If the comparison result of step 340 shows that the system efficiency of the current read cycle is equal to the system efficiency of the previous read cycle (i.e.,

), in step 355, the RFID reader 110 equates a frame size to be used in a next read cycle to the frame size of the current read cycle (that is, the number of slots is fixed). [81] If the system efficiency of the current read cycle is less than the system efficiency of the immediately-previous read cycle (i.e.,

S_1- 1> S₁

), in step 360, the RFID reader 110 decreases the number of slots to be used in the next read cycle. [82] The reason above is that, if the system efficiency of the current read cycle has decreased to be lower than the system efficiency of the immediately-previous read cycle as the frame size increases, a better system efficiency can be expected in a next read cycle by further decreasing the frame size. [83] Therefore, according to the present embodiment, the number of empty slots

Tag w_e is decreased to prevent waste of slots, and thus the optimal system efficiency can be maintained.

[84] If the comparison result of step 340 shows that the system efficiency of the current read cycle is greater than the system efficiency of the immediately -previous read cycle (i.e.,

), the RFID reader 110 increases the number of slots and thus increases the frame size of the next read cycle in step 365. [85] The reason of increasing the frame size can be understood in the same context as described in step 360. That is, if the system efficiency of the current read cycle increases to be greater than the system efficiency of the previous read cycle by increasing the frame size, improvement of system efficiency can be expected in a next read cycle by further increasing the frame size.

[86] If the frame size is decreased in step 330, the TAFSA algorithm operates in an opposite manner to the above descriptions. That is, if the system efficiency of the current read cycle is superior to the system efficiency of the previous read cycle, the frame size is further decreased, and otherwise, the frame size is increased. If there is no change in the system efficiency, the frame size does not change either.

[87] Specifically, the RFID reader 110 compares the system efficiency s, of the current read cycle with that of the previous read cycle in step 350. [88] If the comparison result of step 350 shows that the system efficiency of the current read cycle is greater than the system efficiency of the previous read cycle (i.e.,

), the RFID reader 110 decreases the number of slots of the next read cycle in step 360.

[89] If the system efficiency of the current read cycle is less than the system efficiency of the previous read cycle (i.e.,

), the RFID reader 110 increases the number of slots of frame in step 365. [90] If system efficiency of the current read cycle is equal to the system efficiency of the previous read cycle (i.e.,

), the RFID reader 110 fixes the number of slots so that the frame size of the current read cycle is maintained in the next read cycle in step 370.

[91] After determining the frame size of the next read cycle, in step 380, the RFID reader

110 sends a transmission request to the transponder 120 which has not been received response data, and then repeats a process of reading the transponder 120 which has sent a response thereof. Since this is well-known to those who skilled in the art, detailed descriptions thereof will be omitted.

[92] In step 390, the RFID reader 110 determines whether the process of identifying the transponder 120 is finished, that is, whether all transponders 120 have been identified.

[93] If the RFID reader 110 has identified all transponders 120, the procedure is finished. As described above, the procedure is finished by entering to the standby mode. However, if the RFID reader 110 determines that the identification process is not finished, a next read cycle is performed by repeating steps 310 to 390.

[94] Meanwhile, in the TAFSA algorithm of the present invention, the number of slots can be expressed in an exponential form. For example, the frame size of the current read cycle, that is, the number slots, can be expressed by the following Math Figure 2.

[95] MathFigure 2

[Math.2]

Frame _ SiZe(I₁ ) = K "^■ (0 ≤ Tt₁ < Q)

[96] Herein, K is a variable that represents a ratio of increase or decrease in a frame size.

That is, when the frame size increases, the number of slots of the RFID reader 110 increases by K times, and on the contrary, when the frame size decreases, the number of slots thereof decreases by K times. [97] K is a natural number, and preferably is a predetermined value. Considering system operating costs as well as system efficiency, more preferably, K is 2. Instead of a form of

, if a larger integer value (e.g., ,-v n

5"

, etc.) is used, the system operating costs increase since the number of slots used in a frame increases. However, there is an advantage in that a time for reaching a maximum efficiency can be further reduced. [98] In addition,

is an exponent of K, and determines the frame size together with K. As described above,

is in the range of

0 ≤ n, ≤ Q

[99] Since Q is a maximum value of , a maximum size of a frame is eventually determined by the value Q. Details of the value Q will be described below with reference to Fig. 5 and Fig. 6. [100] If the frame size (the number of slots) has to increase as described in step 260 and step 365, the frame size of the next read cycle can be expressed by the following Math

Figure 3. [101] MathFigure 3

[Math.3]

Frame _sfze(l,__i ) = K""' (0 ≤ n, ≤ O)

[102] This means that the frame size of the next read cycle increases by K times higher than the frame size of the current read cycle. Of course, Math Figure 3 is only an example. Thus, the frame size may increase in various manners, for example, in proportion to a square or cube of K.

[103] On the contrary, if the frame size has to decrease as described in step 265 and step 360, the frame size of the next read cycle can be expressed by the following Math figure 4.

[104] MathFigure 4 [Math.4]

Frame _ s?ze(/_!__l ) = K "-¹ (0 < n, ≤ O)

[105] Similar to Math Figure 3, Math Figure 4 is only an example of the present invention.

Thus, a decrement of a frame may be implemented in various manners which can be assumed by those skilled in the art. [106] Herein, K is a variable that represents a ratio of increase or decrease in a frame size.

That is, when the frame size increases, the number of slots of the RFID reader 110 increases by K times, and on the contrary, when the frame size decreases, the number of slots thereof decreases by K times. [107] K is preferably a natural number. Considering system operating costs as well as system efficiency, more preferably, K is 2. Instead of a form of

, if a larger integer value (e.g., n

5"

, etc.) is used, the system operating costs increase since the number of slots used in a frame increases. However, there is an advantage in that a time for reaching a maximum efficiency can be further reduced. [108] In addition,

is in the range of

⁰ ≤ ", ^≤ Q

[109] Since Q is a maximum value of

, a maximum size of a frame is eventually determined by the value Q. Details of the value Q will be described below with reference to Fig. 5 and Fig. 6.

[110] Fig. 4 is a block diagram of a TAFSA system according to an embodiment of the present invention.

[I l l] The aforementioned RFID reader 110 includes a frame size detector 410, a frame size comparator 420, a system efficiency calculator 430, a system efficiency comparator 440, and a frame size determining unit 450. These elements of the RFID reader 110 do not have to be implemented in hardware, and thus may be implemented in software such as programs. Although not shown, the RFID reader 110 may further include a reader unit for reading a transponder by emitting a frequency having a specific amplitude.

[112] The frame size detector 410 detects a frame size used in each cycle to identify each transponder.

[113] The frame size comparator 420 receives the frame size detected by the frame size detector 410, and then compares a frame size of each read cycle, in particular, a frame size of a previous read cycle, with a frame size of a current read cycle.

[114] The system efficiency calculator 430 calculates a system efficiency of a read cycle according to a result of reading a plurality of transponders. Since a method of calculating the system efficiency has been described above, detailed descriptions on the system efficiency calculator 430 will be omitted.

[115] The system efficiency comparator 440 compares system efficiencies of read cycles, which are calculated by the system efficiency calculator 430. That is, the system efficiency comparator 440 compares the system efficiency of the current read cycle with the system efficiency of the previous read cycle.

[116] The frame size determining unit 450 determines a frame size to be used in a next read cycle according to comparison results obtained from the frame size comparator 420 and the system efficiency comparator 440.

[117] In a case where the frame size of the current read cycle increases to be greater than the frame size of the previous read cycle, if the system efficiency of the current read cycle is greater than the system efficiency of the previous read cycle, the frame size determining unit 450 increases a frame size of a next read cycle. On the other hand, if the system efficiency of the current read cycle is less than the system efficiency of the previous read cycle, the frame size determining unit 450 decreases the frame size to be used in the next read cycle, and if the system efficiency of the current read cycle is equal to the system efficiency of the previous read cycle, the frame size determining unit 450 maintains the frame size of the current read cycle.

[118] On the contrary, in a case where the frame size of the current read cycle increases to be less than the frame size of the previous read cycle, if the system efficiency of the current read cycle is greater than the system efficiency of the previous read cycle, the frame size determining unit 450 decreases the frame size, and if the system efficiency of the current read cycle is less that the system efficiency of the previous read cycle, the frame size determining unit 450 increases the frame size.

[119] Of course, if the system efficiency of the current read cycle is equal to the system efficiency of the previous read cycle, the frame size of the current read cycle is maintained in the same case as when the frame size is increased.

[120] As described above, the frame size to be used in the next read cycle may be increased or decreased in an integer multiple in comparison with the frame size of the current read cycle. Preferably, the frame size is increased or decreased by a multiple of 2.

[121] Fig. 5 and Fig. 6 are respectively a graph and a table illustrating the number of read cycles and a frame size with respect to the number of transponders according to an embodiment of the present invention.

[122] Referring to Fig. 5, the X-axis represents the number of transponders 120 located within a radius of the RFID reader 110, and the Y-axis represents a frame size and the number of read cycles. Specifically, a reference numeral 510 indicates a frame size corresponding to the number of transponders 120, and a reference numeral 520 is in association with the number of read cycles.

[123] For example, if the number of transponders is in the range of 41 to 81, it is desirable that read cycles are repeated about 15 to 20 times when a maximum frame size is set to 64, that is, Q=6 (where, K is assumed to 2). On the other hand, if the number of transponders is in the range of 82 to 176, the number of times of repeating the read cycle increases when the frame size is determined to 64. Therefore, in this case, the frame size is preferably determined to 128 (i.e., Q=7).

[124] Accordingly, through experimentations, it can be known that, when the frame size is similar to the number of transponders, the number of times of repeating the read cycle decreases, and a time required for the RFID reader 110 to identify all transponders decreases.

[125] By considering this fact, a maximum frame size that can be set for each transponder is described in Fig. 6. The reason of setting the frame size to the maximum value (i.e., value Q) is because it is not desirable that the frame size increases infinitely when system operation costs are taken into account.

[126] Referring to Fig. 6, the maximum frame size is set similar to the number of transponders. This is because a maximum system efficiency can be obtained when the frame size used in the RFID reader 110 is similar to the number of transponders. That is, if a system efficiency of a frame having a value Q is a maximum system efficiency, the system efficiency decreases thereafter. Therefore, in terms of the system operation costs, it is not desirable to use a slot exceeding the value Q.

[127] Meanwhile, the frame size of Fig. 6 is calculated by substituting K to Math Figure 2 under the assumption that K is 2 as described above. This can be expressed by the following Math Figure 5.

[128] MathFigure 5 [Math.5]

Frame SiZe(I₁ ) = 2." (0 < «, < O)

[129] According to anther aspect of the present embodiment,

« / may be Q+α. Optionally,

may exceed Q. In this case, even if the system efficiency does not reach a theoretical maximum value, the system may be facilitated to operate effectively.

[130] Fig. 7 is a graph for comparing a system efficiency of a TAFSA algorithm according to an embodiment of the present invention with a conventional BFSA algorithm, where the number of transponders is in the range of 1 to 50.

[131] Referring to Fig. 7, when a fixed frame size is used as in the conventional BFSA algorithm (indicated by 710 to 750), the system efficiency increases to some extent as the number of transponders 120 changes. However, after reaching a maximum efficiency, the system efficiency decreases.

[132] Specifically, according to the BFSA algorithm shown in Fig. 7, frames are constructed of 4, 8, 16, 31, and 64 fixed slots. Referring to each graph (indicated by reference numerals 710 to 750) depicted for each frame size, up to about 35% of system efficiency is shown when the number of transponders is within a predetermined range, and the system efficiency decreases to be less than 35% when the number of transponders is out of the predetermined range. Specifically, if the frame size, that is, the number of slots, is 4 (indicated by 710), the system efficiency exceeds 35% as a maximum system efficiency when the number of transponders is 3, and the system efficiency is about 35% when the number of transponders is 4. However, when the number of transponders is above or below this value, the system efficiency rapidly decreases. When the frame size is 8 (indicated by 720), the maximum system efficiency is shown when the number of transponders is 6 or 7, and the system efficiency rapidly decreases when the number of transponders is above 9 or below 5. Similarly, when the frame size is 16 (indicated by 730), 32 (indicated by 740), or 64 (indicated by 750), according to the number of transponders, the system efficiency significantly varies starting from a point where a system efficiency has a maximum value.

[133] As such, when using the fixed frame, the system efficiency varies depending on the number of transponders 120, and this can be explained as follows. That is, in a case where the number of transponders 120 is greater than the frame size, even if a read cycle is repeated several times, an identification efficiency of the transponder 120 significantly decreases due to collision between the transponders 120. In addition, even in a case where the number of transponders 120 is less than the frame size, the system efficiency decreases as the number of empty slots increases.

[134] In comparison, when the TAFSA algorithm of the present invention is used, the frame size changes according to the system efficiency of the previous read cycle and the current read cycle. Therefore, as indicated by 760 in Fig. 7, the maximum system efficiency can be continuously maintained.

[135] That is, as the number of transponders 120 increases from 1 to 50, the frame size used in the RFID reader 110 also increases in powers of 2, for example, 4, 8, 16, 32, 64, etc. In this manner, the system efficiency can be continuously maintained to be high.

[136] In the embodiment of Fig. 7, the maximum frame size of the present invention is limited to 64 slots, that is, Q=6. Herein, the value Q of Fig. 6 is used by considering that the maximum number of transponders is 50.

[137] According to the present invention, the frame size used in the RFID reader 110 is regulated to read a plurality of transponders 120. Thus, performance of the RFID reader 110 can be improved in comparison with the conventional BFSA algorithm.

[138] The embodiments of the present invention can be written as computer programs and can be implemented in general-use digital computers that execute the programs using a computer readable recording medium. Examples of the computer readable recording medium include Read-Only Memory (ROM), Random- Access Memory (RAM), Compact Disk (CD)-ROMs, floppy disks, hard disks, optical data storage devices, etc. While the present invention has been particularly shown and described with reference to exemplary embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the present invention as defined by the appended claims.

Claims

[1] A method of determining a frame size in a Radio Frequency Identification

(RFID) reader, comprising: in a process performed by repeating a read cycle in order for the RFID reader to identify a plurality of transponders, detecting frame sizes used in read cycles; among the detected frame sizes, comparing a frame size of a current read cycle with a frame size of a previous read cycle that is performed before the current read cycle is performed; calculating system efficiencies of the read cycles by using the detected frame sizes; among the calculated system efficiencies, comparing a system efficiency of the current read cycle with a system efficiency of the previous read cycle; and determining a frame size to be used in a next read cycle according to the frame size comparison result and the system efficiency comparison result.

[2] The method of claim 1, wherein the previous read cycle compared with the current read cycle is a read cycle performed immediately before the current read cycle.

[3] The method of claim 1, wherein the system efficiency s, is calculated by using Math Figure:

_ number of identified transponders _ * ^agid total number of slots Tag_Id+Tag_Id[e+Tag _Coll

where

^Tag coil denotes the number collision-generated slots,

Tag_Id denotes the number of slots that identify the transponders, and

Tagidie denotes the number of empty slots.

[4] The method of claim 1, wherein the frame size to be used in the next read cycle increases or decreases by a multiple of K (a predetermined arbitrary natural number) in comparison with the frame size of the current read cycle.

[5] The method of any one of claims 1 to 4, wherein, in the determining a frame size, if the frame size comparison result shows that the frame size of the current read cycle increases to be greater than the frame size of the previous read cycle, a frame size to be used in the next read cycle is increased when the system efficiency comparison result shows that the system efficiency of the current read cycle is greater than the system efficiency of the previous read cycle, and the frame size to be used in the next read cycle is decreased when the system efficiency of the current read cycle is less than the system efficiency of the previous read cycle.

[6] The method of any one of claims 1 to 4, wherein, in the determining a frame size, if the frame size comparison result shows that the frame size of the current read cycle decreases to be less than the frame size of the previous read cycle, a frame size to be used in the next read cycle is decreased when the system efficiency comparison result shows that the system efficiency of the current read cycle is greater than the system efficiency of the previous read cycle, and the frame size to be used in the next read cycle is increased when the system efficiency of the current read cycle is less than the system efficiency of the previous read cycle.

[7] The method of any one of claims 1 to 4, wherein, in the determining a frame size, if the system efficiency comparison result shows that the system efficiency of the current read cycle is equal to the system efficiency of the previous read cycle, the frame size to be used in the next read cycle is determined to be equal to the frame size of the current read cycle.

[8] A Radio Frequency Identification (RFID) reader comprising: a frame size detector which detects frame sizes used in read cycles in a process performed by repeating a read cycle to identify a plurality of transponders; a frame size comparator which compares, among the detected frame sizes, a frame size of a current read cycle with a frame size of a previous read cycle that is performed before the current read cycle is performed; a system efficiency calculator which calculates system efficiencies of the read cycles by using the detected frame sizes; a system efficiency comparator which compares, among the calculated system efficiencies, a system efficiency of the previous read cycle with a system efficiency of the current read cycle; and a frame size determining unit which receives the comparisons results from the frame size comparator and the system efficiency comparators, and determines a frame size to be used in a next read cycle according to the comparison results.

[9] The RFID reader of claim 8, wherein the previous read cycle compared with the current read cycle is a read cycle performed immediately before the current read cycle.

[10] The RFID reader of claim 8, wherein the system efficiency

S₁ is calculated by using Math Figure:

_ number of identified transponders _ ^ ^aSid total number of slots Tag_Id+Tag_IcUe+Tag_Coll

where

denotes the number collision-generated slots,

Tag_M denotes the number of slots that identify the transponders, and

Tag_Idle denotes the number of empty slots.

[11] The RFID reader of any one of claims 8 to 10, wherein, if the result obtained from the frame size comparator shows that the frame size of the current read cycle increases to be greater than the frame size of the previous read cycle, the frame size determining unit increases a frame size to be used in the next cycle when the result obtained from the system efficiency comparator shows that the system efficiency of the current read cycle is greater than the system efficiency of the previous read cycle, decreases the frame size to be used in the next frame when the result shows that the system efficiency of the current read cycle is less than the system efficiency of the previous read cycle, and maintains the frame size of the current read cycle when the system efficiency of the current read cycle is equal to the system efficiency of the previous read cycle.

[12] The RFID reader of any one of claims 8 to 10, wherein, if the result obtained from the frame size comparator shows that the frame size of the current read cycle decreases to be less than the frame size of the previous read cycle, the frame size determining unit decreases a frame size to be used in the next cycle when the result obtained from the system efficiency comparator shows that the system efficiency of the current read cycle is greater than the system efficiency of the previous read cycle, increases the frame size to be used in the next frame when the result shows that the system efficiency of the current read cycle is less than the system efficiency of the previous read cycle, and maintains the frame size of the current read cycle when the system efficiency of the current read cycle is equal to the system efficiency of the previous read cycle.

[13] The RFID reader of any one of claims 8 to 10, wherein the frame size to be used in the next read cycle increases or decreases by a multiple of K (a predetermined arbitrary natural number) in comparison with the frame size of the current read cycle.

[14] A recording medium storing a program, which is readable by a data processing apparatus and comprises program codes executable by the digital processing apparatus, for executing a method of determining a frame size in a Radio Frequency Identification (RFID) reader for identifying a transponder by using a frame-slotted Aloha algorithm, the method comprising: in a process performed by repeating a read cycle in order for the RFID reader to identify a plurality of transponders, detecting frame sizes used in read cycles; among the detected frame sizes, comparing a frame size of a current read cycle with a frame size of a previous read cycle that is performed before the current read cycle is performed; calculating system efficiencies of the read cycles by using the detected frame sizes; among the calculated system efficiencies, comparing a system efficiency of the current read cycle with a system efficiency of the previous read cycle; and determining a frame size to be used in a next read cycle according to the frame size comparison result and the system efficiency comparison result.

[15] The recording medium of claim 14, wherein the previous read cycle compared with the current read cycle is a read cycle performed immediately before the current read cycle.

[16] The recording medium of claim 14, wherein the system efficiency s, is calculated by using Math Figure:

_ number of identified transponders _ Tag_Id

' 1 total number of slots Tag^+Tag_j^+Tag_f.^

where

Tag coil denotes the number collision-generated slots, Tag_M denotes the number of slots that identify the transponders, and

Tag_Idle denotes the number of empty slots.

[17] The recording medium of any one of claims 14 to 16, wherein, in the determining a frame size, if the frame size comparison result shows that the frame size of the current read cycle increases to be greater than the frame size of the previous read cycle, a frame size to be used in the next read cycle is increased when the system efficiency comparison result shows that the system efficiency of the current read cycle is greater than the system efficiency of the previous read cycle, and the frame size to be used in the next read cycle is decreased when the system efficiency of the current read cycle is less than the system efficiency of the previous read cycle, if the frame size comparison result shows that the frame size of the current read cycle decreases to be less than the frame size of the previous read cycle, a frame size to be used in the next read cycle is decreased when the system efficiency comparison result shows that the system efficiency of the current read cycle is greater than the system efficiency of the previous read cycle, and the frame size to be used in the next read cycle is increased when the system efficiency of the current read cycle is less than the system efficiency of the previous read cycle, and if the system efficiency comparison result shows that the system efficiency of the current read cycle is equal to the system efficiency of the previous read cycle, the frame size to be used in the next read cycle is determined to be equal to the frame size of the current read cycle.