Identification anti-collision method and radio frequency identification system using the same

This application claims priority from Korean Patent Application No. 10-2005-0046781 filed on Jun. 1, 2005 in the Korean Intellectual Property Office, the entire disclosure of which is incorporated herein by reference.

1. Field of The Invention

Methods and apparatuses consistent with the present invention relate to identification (ID) anti-collision and radio frequency identification (RFID) systems. More particularly, the present invention relates to an anti-collision method using a collision bit determination and a RFID system thereof.

2. Description of The Prior Art

RFID technology reads out information from the tags attached to objects via radio waves. RFID is applied to various fields such as product distribution management, security, delivery, and so on. Contact barcode system is replaced by RFID which can read out information much faster. RFID provides advantages such as wide range of operation, and product intelligence.

In a ubiquitous computing environment, multiple tags may come into a reading range of a reader. When the tags respond to a request of the reader at the same time, signals from the tags interfere and collide with one another.

An anti-collision algorithm is adopted to resolve interference between the reply signals of the tags to allow collision-free recognition of the replies from the tags.

Many anti-collision algorithms have been proposed. In one anti-collision algorithm, for example, a binary ID can be provided to a tag so that tags with unintended IDs are eliminated from the consideration. This will be explained briefly below.

First, a (n)-bit binary ID is provided to a tag, and a reader transmits ID request signal to a plurality of tags. The ID request signal includes a ‘0’ or ‘1’ binary ID request value. Upon receiving the ID request signal, each tag compares the ID request value with the first bit of its own ID, and if the data match, transmits its ID to the reader. For example, all the tags with IDs starting with ‘1’, transmit their IDs to the reader in response to ‘1’ ID request value. Likewise, all the tags with IDs starting with ‘0’ transmit their IDs to the reader in response to ‘0’ ID request value.

If one tag responds to the ID request signal, the responding tag is confirmed to be the tag desired by the reader. If more than one tag responds to the reader and first bits of the IDs collide against each other, the reader transmits ‘0’ or ‘1’ binary ID request signal with respect to the next bits of the tag IDs. The reader resets non-responding tags, and thus removes the non-responding tags from the consideration.

If more than one tag responds to the second ID request signal again, the reader transmits another ID request signal with respect to next bits of the IDs. This process repeats until only one tag responds to the ID request signal.

As explained above, conventionally, the reader repeatedly generates and transmits one-bit ID request signal when more than one tags respond. Therefore, it becomes problematic when the collision IDs are composed of many bits because much time is consumed. Additionally, the tags transmit their entire IDs rather than the bits of interest, thereby increasing power consumption.

Therefore, an RF system which operates with requiring reduced time and power, is necessary.

The invention provides an ID anti-collision method using a collision bit determination and an RFID system using the same.

According to an aspect of the invention, there is provided an anti-collision method of an RFID system comprising a reader, and two or more tags each having an ID, respectively. The anti-collision method includes transmitting an ID request value from the reader to the respective tags, the ID request value containing one or more of the codes forming the ID, receiving the ID from at least one of the tags which contain the ID request value, when a plurality of IDs collide, requesting the tags for a value representing a position of collision, and receiving the value representing the position of collision from the tags and identifying the IDs of the tags.

The ID comprises a binary bit, and in the transmitting the ID request value, ‘0’ or ‘1’ is transmitted.

When the IDs collide with each other, the reader recognizes the position of collision based on a code other than the binary bit.

The requesting the value representing the position of collision of the IDs comprises the step of generating a collision bit position (CBP) value, which indicates the position of collision ID based on a predetermined code, and transmitting the generated CBP value to the tags.

The requesting the value representing the position of collision of the IDs comprises the step of transmitting the ID request value.

The generating a collision bit determination request (CBDreq), which is a collection of consecutive bits representing the position of collision of each of the tags, may also be provided.

In the generating the CBDreq, bits representing the position of collision are converted to a decimal unit, and the CBDreq which indicates the position corresponding to the converted decimal value based on binary data ‘0’ or ‘1’, is generated.

The CBDreq is transmitted as many as a predetermined number of codes.

The identifying the IDs comprises putting the CBDreq in sequence into the position of. collision when the CBDreq is equal to, or smaller than the predetermined number of bits.

The identifying the IDs comprises generating an estimate ID, by putting the CBDreq in sequence into the position of collision when the CBDreq is greater than the predetermined number of bits; and transmitting the estimate ID to the respective tags as the ID request value.

The confirming an ID may also be provided, when the estimate ID as the ID request value does not have any collision.

If the estimate ID as the ID request value has a collision, the re-generating the CBP value with respect to the position of collision and transmitting the re-generated CBP value and the estimate ID to the colliding tag, may also be provided.

According to another aspect of the present invention, there is provided an RFID system comprising a reader and two or more tags having IDs, wherein, the tags each provides ID in response to a request from the reader, and when colliding with IDs of the other tags, provides the reader with a value representing the position of collision of the ID, and the reader transmits to each of the tags an ID request value which contains at least one of codes forming the ID, receives the ID from each of the tags, and when the tags collide with each other, receives from each of the tags a value representing the position of collision and identifies the IDs.

The above and/or other aspects of the invention will become apparent and more readily appreciated from the following description of exemplary embodiments, taken in conjunction with the accompanying drawing figures of which:

FIG. 1 is a diagram illustrating a construction of a radio frequency identification (RFID) system implementing an ID anti-collision method according to an exemplary embodiment of the present invention;

FIG. 2 is a diagram illustrating an ID anti-collision method according to an exemplary embodiment of the present invention;

FIG. 3A is a flowchart illustrating an operation of a reader of the RFID system according to an exemplary embodiment of the present invention;

FIG. 3B is a flowchart illustrating an operation of a tag of the RFID system according to an exemplary embodiment of the present invention;

FIG. 4 is a graph comparing experimental results of the anti-collision method between the related art and the present invention; and

FIG. 5 is a graph of another experimental results of the anti-collision method of the present invention.

Certain exemplary embodiments of the present invention will now be described in greater detail with reference to the accompanying drawings.

In the following description, same drawing reference numerals are used for the same elements even in different drawings. The matters defined in the description, such as detailed construction and element descriptions, are provided to assist in a comprehensive understanding of the invention. Also, well-known functions or constructions are not described in detail since they would obscure the invention in unnecessary detail.

FIG. 1 shows the structure of an RFID system which implements an ID anti-collision method according to an exemplary embodiment of the present invention. According to this exemplary embodiment, the RFID system includes a reader 10 and one or more tags 20 .

The reader 10 is usually provided with a memory which stores therein binary ID request values to provide to the tags 20 upon request. The memory also stores IDs which are anticipated according to the collision bits of the IDs. The memory may be implemented as a stack or a queue, and in the following example, the queue is employed.

FIG. 2 depicts an ID anti-collision method according to an exemplary embodiment of the present invention.

According to this exemplary embodiment of the present invention, it is assumed that the reader 10 takes charge of tag 1 , tag 2 , tag 3 and tag 4 . IDs of the tag 1 , tag 2 , tag 3 and tag 4 are ‘10110101’, ‘10110100’, ‘10000100’, and ‘10100001’, respectively, which are eight bits long.

With reference to the table shown in FIG. 2 , the process of anti-collision method according to an exemplary embodiment of the present invention will be explained below.

In the row of ‘Prefix Queue Initially 0, 1’, values stored in the queue are indicated. The queue initially receives ‘0’ and ‘1’ and then stores anticipated IDs after the collision of IDs of the tags 20 . The row of ‘Downlink (Tag->Reader)’ shows in sequence the ID request value which is transmitted from the reader 10 to the tags 20 . The stored values of the queue are sequentially used as the ID request value. The row of ‘Uplink’ shows response IDs which are transmitted from the tags 20 to the reader 10 , and the collision bits are marked as ‘X’. The rows of ‘Tag 1 ’, ‘Tag 2 ’, ‘Tag 3 ’, and ‘Tag 4 ’ indicate the IDs of the respective tags which are identified through the processes of Downlink and Uplink.

Descriptions will now be made on how the reader 10 recognizes and identifies the IDs of tag 1 , tag 2 , tag 3 and tag 4 according to the anti-collision method.

The reader 10 inputs ‘0’ and ‘1’ as the ID request value IDreq. That is, the reader 10 first outputs the ID request value ‘0’ from the queue (the ID request value ‘0’ of the queue is accordingly deleted from the queue), and transmits the ID request value ‘0’ to the tags 20 . The tags 20 , upon receiving the ID request value ‘0’, check whether the received ID request value ‘0’ matches their IDs. That is, the tags 20 check whether their IDs start with ‘0’.

Next, tag 1 , tag 2 , tag 3 and tag 4 , all of which start with ‘1’, confirm that their IDs do not start with ‘0’, and thus do not send any replies to the reader 10 . When no replies are received from the tags 20 within a predetermined time, the reader 10 outputs the next ID request value ‘1’. The ID request value ‘1’ is accordingly removed from the queue. The reader 10 transfers the ID request value ‘1’ to the tags 20 , and the tags 20 check whether the received request value ‘1’ matches their IDs. That is, the tags 20 check whether their IDs start with ‘1’.

Tag 1 , tag 2 , tag 3 and tag 4 confirm that their IDs start with ‘1’, and thus transfer their IDs ‘10110101’, ‘10110100’, ‘10000100’, and ‘10100001’ to the reader 10 .

When the transferred IDs do not collide with one another, the reader 10 can identify all of tag 1 , tag 2 , tag 3 and tag 4 based on the received IDs.

However, in this particular example, the bits ‘1’ at the same bit positions of the respective IDs collide with one another. More specifically, tag 1 has the bit ‘1’ in the third, fourth, sixth and eighth bit positions of the ID, tag 2 has the bit ‘1’ in the third, fourth, and sixth bit position of the ID, tag 3 has the bit ‘1’ in the sixth order of the ID, and tag 4 has the bit ‘1’ in the third and the eighth bit position of the ID. Therefore, the third, fourth, sixth and eighth bits of the respective IDs collide with one another. The reader 10 recognizes the collision bits as ‘X’, and therefore, an ID may be recognized as ‘10XX0X0X’.

The reader 10 then generates collision bit position (CBP) value using the IDs which are bit-wise recognized as explained above. The CBP value is used to request the transfer of the collision bits among the bits of the tag IDs.

The CBP value indicates a collision bit, which is recognized by the reader 10 as ‘X’, as ‘1’, and a non-collision bit as ‘0’. Accordingly, when the reader 10 recognizes the collision ID bits as ‘10XX0X0X’, ‘00110101’ will be generated as the CBP value.

Next, the reader 10 transfers the ID request value ‘1’, which induced the ID collision, and the CBP value ‘00110101’ to the tags 20 . Upon receiving the ID request value ‘1’ and the CBP value ‘00110101’, the tags 20 check whether the ID request value ‘1’ matches their IDs. When the ID request value ‘1’ matches their IDs, the tags 20 generate a collision bit determination value CBDreq from the CBP value ‘00110101’.

The CBDreq is a collection of the collision bits of the ID. Specifically, the tag 1 generates the collision bits ‘1111’ based on the received CBP value, the tag 2 generates the collision bits ‘1110’ based on the CBP value, the tag 3 generates the collision bits ‘0010’ based on the CBP value, and the tag 4 generates the collision bits ‘1001’ based on the CBP value.

The number of bits that the tags 20 can transmit to the reader 10 as the CBDreq may be predetermined. If it is predetermined such that the tags 20 can transmit three bits as the CBDreq, for example, each of the tags 20 transfers the first three bits of the CBDreq, while excluding the last bit.

Therefore, the tags 20 transfer the generated CBDreq ‘111’, ‘111’, ‘001’, and ‘100’, respectively. The tags 20 may convert the CBDreq to another binary values to prevent collision among the CBDreq.

Because there are three bits of CBDreq in this exemplary embodiment, the CBDreq, when expressed in a decimal basis, will be one of integers 0 to 7. In other words, the CBDreq of the tag 1 and the tag 2 may be expressed as ‘7’, CBDreq of the tag 3 may be expressed as ‘1’ and the CBDreq of the tag 4 may be expressed as ‘4’.

In binarizing the CBDreq, eight binary codes are generated from the eight CBDreq (0˜7) so that decimal value is expressed by ‘0’ or ‘1’.

For example, when the CBDreq is ‘0’ in a decimal basis, the binary code ‘00000000’ may be set. When the CBDreq is ‘1’ in a decimal basis, the binary code ‘00000010’ may be set. When the decimal CBDreq is ‘2’ in a decimal basis, the binary code ‘00000100’ may be set. When the decimal CBDreq is ‘3’ in a decimal basis, the binary code ‘00001000’ may be set. When the decimal CBDreq is ‘4’ in a decimal basis, the binary code ‘00010000’ may be set. When the decimal CBDreq is ‘5’ in a decimal basis, the binary code ‘00100000’ may be set. When the decimal CBDreq is ‘6’ in a decimal basis, the binary code ‘01000000’ may be set. When the decimal CBDreq is ‘7’ in a decimal basis, the binary code ‘10000000’ may be set.

Because the CBDreq ‘111’ of the tag 1 is expressed as ‘7’ in a decimal basis, the binary code ‘10000000’ is transferred. Because the CBDreq ‘111’ of the tag 2 is expressed as ‘7’ in a decimal basis, the binary code ‘10000000’ is transferred.

Because the CBDreq ‘001’ of the tag 3 is expressed as ‘1’ in a decimal basis, the binary code ‘00000010’ is transferred. Because the CBDreq ‘100’ of the tag 4 is expressed as ‘4’ in a decimal basis, the binary code ‘00010000’ is transferred.

Upon receipt of the CBDreq, the reader 10 estimates the IDs within an identifiable range, using the ID bits ‘10XX0X0X’ as recognized by the collision, and the received CBDreq. The reader 10 estimates the IDs by putting in order the received CBDreq in the ‘X’s of ‘10XX0X0X’.

By putting the received CBDreq ‘111’, ‘001’ and ‘100’ into the ‘X’s, respectively, IDs ‘1011010’, ‘1000010’, and ‘1010000’ are estimated. Because the CBDreq for the first three collision bits are provided from the respective tags 20 , the IDs with seven bits, that is, the IDs excluding the last X, are estimated.

The reader 10 then stores the estimated IDs ‘1011010’, ‘1000010’, and ‘1010000’ in the queue as the ID request values.

Therefore, when the ID request value is ‘1011010’, every tag 20 having the ID starting with ‘1011010’ transfers its ID to the reader 10 .

The reader 10 outputs the first ID request value ‘1011010’ among the ID request values generated and stored in the queue (‘1011010’ is accordingly removed from the queue). The reader 10 transfers the ID request value ‘1011010’ to the tags 20 , and the tags 20 check whether the received ID request value ‘1011010’ matches their IDs. In other words, the tags 20 check whether their IDs start with ‘1011010’.

As a result, the tag 1 and tag 2 confirm that their IDs start with ‘1011010’, and transfer their IDs ‘10110101’ and ‘10110100’ to the reader 10 .

If the transferred IDs do not collide with each other, the reader 10 can identify both the tag 1 and the tag 2 using the received IDs.

However, in the exemplary embodiment of the present invention, the transferred IDs collide with each other at the reader 10 , and the reader 10 recognizes the collision ID bits as ‘X’. The collision ID can be then expressed as ‘1011010X’.

Accordingly, the reader 10 regenerates a CBP value from the collision IDs. As aforementioned, the CBP value is used to request the transfer of only collision bits of the tag ID.

The CBP value indicates the ‘X’ collision bit as ‘1’, and the non-collision bit as ‘0’. Thus, when the collision recognized ID bits are ‘1011010X’, CBP value ‘00000001’ is generated.

The reader 10 then transfers the ID request value ‘1011010’, which induced the ID collision, and the CBP value ‘00000001’ to the tags 20 . The tags 20 , upon receiving them, check whether the ID request value ‘1011010’ matches their IDs. When the ID request value ‘1011010’ matches their IDs, the tags 20 generates a CBDreq from the CBP value ‘00000001’.

The CBDreq is a collection of collision bits in the ID. Specifically, the tag 1 generates the CBDreq ‘1’ based on the received CBP value, and the tag 2 generates the CBDreq ‘0’ based on the CBP value.

Likewise, when transferring the CBDreq, the number of bits that the tag 1 and tag 2 transmit to the reader 10 may be predetermined. As the CBDreq does no exceed the predetermined number of bits ‘3’, the tag 1 and tag 2 transfers the CBDreq ‘1’ and ‘0’, respectively.

Since the CBDreq received from the tag 1 and tag 2 do not exceed the preset number of bits, the reader 10 can identify the IDs of the tag 1 and tag 2 as ‘10110101’ and ‘10110100’ based on the received CBDreq ‘1’ and ‘0’.

The tag 1 and tag 2 may convert the CBDreq to binary values when transferring the CBDreq.

Specifically, since the CBDreq ‘1’ of the tag 1 is expressed as a decimal ‘1’, a binary code ‘00000010’ is transferred. Since the CBDreq ‘0’ of the tag 2 is expressed as a decimal ‘0’, a binary code ‘00000000’ is transferred.

After identifying the IDs of the tag 1 and tag 2 , the reader 10 outputs the second ID request value ‘1000010’. At this time, the stored ID request value ‘1000010’ is removed from the queue. The reader 10 transfers the ID request value ‘1000010’ to the tags 20 . The tags 20 check whether the received ID request value ‘1000010’ matches their IDs. That is, the tags 20 check whether their IDs start with ‘1000010’.

As a result, the tag 3 confirms that its ID starts with ‘1000010’ and thus transfers its ID ‘10000100’ to the reader 10 .

The reader 10 identifies the ID of the tag 3 ‘10000100’ because the received ID has no collision.

After identifying the ID of the tag 3 , the reader 10 outputs the third ID request value ‘1010000’. At this time, the stored ID request value ‘1010000’ is removed from the queue.

The reader 10 transfers the ID request value ‘1010000’ to the tags 20 . In response, the tags 20 check whether the received ID request value ‘1010000’ matches their IDs. That is, the tags 20 check whether their IDs start with ‘1010000’.

Of tag 1 , tag 2 , tag 3 and tag 4 , the tag 4 confirms that its ID starts with ‘1010000’ and thus transfers its ID ‘10100001’ to the reader 10 .

Since the transferred ID has no collision, the reader 10 can identify the ID of the tag 4 ‘10100001’.

FIG. 3A is a flowchart illustrating an operation of a reader in the RFID system according to an exemplary embodiment of the present invention.

First, the reader 20 inputs the ID request values ‘0’ and ‘1’ into the queue and sets the number of collision bits transmittable from tags N (S 500 ). Next, the reader 20 checks whether the queue is empty (S 505 ). When the queue is empty, the tag ID identification is ended (S 510 ).

When the queue is not empty, the reader 10 outputs and transfers the ID request value ‘0’ in the queue, and requests the transfer of IDs that match the ID request value (S 515 ). The ID request value ‘0’, which has been input and stored in the queue, is removed from the queue upon the output from the queue.

The reader 20 checks whether IDs matching the ID request value ‘0’ are received or not (S 520 ). When no matching IDs are received, the reader 20 returns to operation S 505 and checks whether the queue is empty. When the queue is not empty, the reader 10 outputs and transfers the stored ID request value ‘1’, and thus requests the transfer of IDs matching the ID request value ‘1’ (S 515 ). At this time, the ID request value ‘1’, which has been input and stored in the queue, is removed from the queue upon the output from the queue.

The reader 20 checks whether IDs matching the ID request value ‘1’ are received or not (S 520 ). When matching IDs are received, the reader 10 checks whether the received IDs have collision (S 525 ).

When there is no collision in the received IDs, the reader 10 identifies the received tag IDs (S 530 ) and returns back to operation S 505 .

When the received IDs collide, the reader 10 generates a CBP value and transfers the generated CBP value together with the ID request value (S 535 ). Next, the reader 10 receives a CBDreq of the collision IDs (S 545 ), and checks whether the number of collision bits is greater than the preset number of the transmittable collision bits N (S 550 ).

When the number of collision bits is not greater than the preset number of the transmittable collision bits N, the reader 10 identifies the received ID based on the received CBP value (S 555 ) and returns back to operation S 505 .

When the number of collision bits is greater than the preset number of the transmittable collision bits N, the reader 10 generates a new ID request value using the received CBDreq and stores the new ID request value in the queue (S 560 ). Next, the reader 10 returns back to operation S 505 .

Ultimately, the reader 10 repeats operations S 505 through S 560 until there are no ID request values stored in the queue. When there are no ID request values left in the queue, the reader 10 can completely identify all the tag IDs.

FIG. 3B is a flowchart illustrating an operation of a tag in the RFID system according to an exemplary embodiment of the present invention.

The tag 20 always waits to receive a message from the reader 10 (S 565 ). The tag 20 checks whether an ID request value is received from the reader 10 (S 570 ). When the ID request value is not received, the tag 20 maintains the standby state (S 565 ). By contrast, when the ID request value is received, the tag 20 checks whether the received ID request value matches its tag ID (S 575 ).

When the received ID request value does not match its tag ID, the tag 20 maintains the standby state (S 565 ). When the received ID request value matches its tag ID, the tag 20 checks whether the ID request value is received alone or together with the BDP value (S 580 ).

When only the ID request value is received, the tag 20 transfers its ID to the reader ID (S 585 ). When both the ID request value and the BDP value are received, the tag 20 generates a CBDreq and transfers the generated BCD value with the maximum bits within the preset number of transmittable collision bits (S 590 ). Next, the tag 20 returns to the standby state (S 565 ).

FIG. 4 depicts a graph comparing experimental results of the anti-collision method between the related art and the present invention.

In FIG. 4 , experiments have been conducted by using 96-bit IDs and setting the number of bits of the transmittable BCD value to 6. As the number of tags increases, the number of requests and replies also increases linearly. Meanwhile, it can be seen that the slope relating to the increase of the number of requests and replies 500 of the related art and replies is less than the slope relating to the increase of the number of requests and replies 550 of the present invention.

It is noted that the present invention drastically reduces the number of requests and replies with respect to the increasing number of tags, comparing with the related art.

FIG. 5 depicts a graph of another experimental results of the anti-collision method of the present invention.

In FIG. 5 , experiments have been conducted by using 96-bit IDs and setting the number of tags to 1,000. The number of requests and replies between the reader and the tags is measured while the number of bits of the CBDreq to be transferred from the tags is increased from 1 to 17. As a result, the minimum number of requests and replies is obtained when the number of bits of the CBDreq is set to 6. It can be seen that the most efficient implementation of the present invention is to set the number of bits of the CBDreq transferred from the tag to 6 when the 96-bit IDs are adapted.

As set forth above, the reader 10 generates and transfers the CBP value which indicates the collision spots, and the respective tags 20 generates CBDreq with respect to the collision bits only and transfers the generated CBDreq. Therefore, patterns of collision ID bits are recognized without suffering collision. Because a plurality of IDs can be identified at one time, the number of messages transferred between the reader 10 and the tags 20 can be reduced. Additionally, because the CBDreq is shorter than an ID, power consumption for the transfer can be reduced. As a result, the time and power efficiencies of the RFID system can be improved.

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 invention as defined by the appended claims.