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

An anti-collision method is provided for a radio frequency identification (RFID) system including a reader, and two or more tags each having an ID. 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. Because collision pattern of the bits of respective IDs is recognized, and a plurality of IDs are recognized, the number of transmissions between the reader and the tags can be reduced.

CROSS-REFERENCE TO RELATED APPLICATIONS

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.

BACKGROUND OF THE INVENTION

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.

SUMMARY OF THE INVENTION

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.

DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS

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. 1shows 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 reader10and one or more tags20.

The reader10is usually provided with a memory which stores therein binary ID request values to provide to the tags20upon 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. 2depicts 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 reader10takes charge of tag1, tag2, tag3and tag4. IDs of the tag1, tag2, tag3and tag4are ‘10110101’, ‘10110100’, ‘10000100’, and ‘10100001’, respectively, which are eight bits long.

With reference to the table shown inFIG. 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 tags20. The row of ‘Downlink (Tag->Reader)’ shows in sequence the ID request value which is transmitted from the reader10to the tags20. 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 tags20to the reader10, and the collision bits are marked as ‘X’. The rows of ‘Tag1’, ‘Tag2’, ‘Tag3’, and ‘Tag4’ 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 reader10recognizes and identifies the IDs of tag1, tag2, tag3and tag4according to the anti-collision method.

The reader10inputs ‘0’ and ‘1’ as the ID request value IDreq. That is, the reader10first 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 tags20. The tags20, upon receiving the ID request value ‘0’, check whether the received ID request value ‘0’ matches their IDs. That is, the tags20check whether their IDs start with ‘0’.

Next, tag1, tag2, tag3and tag4, all of which start with ‘1’, confirm that their IDs do not start with ‘0’, and thus do not send any replies to the reader10. When no replies are received from the tags20within a predetermined time, the reader10outputs the next ID request value ‘1’. The ID request value ‘1’ is accordingly removed from the queue. The reader10transfers the ID request value ‘1’ to the tags20, and the tags20check whether the received request value ‘1’ matches their IDs. That is, the tags20check whether their IDs start with ‘1’.

Tag1, tag2, tag3and tag4confirm that their IDs start with ‘1’, and thus transfer their IDs ‘10110101’, ‘10110100’, ‘10000100’, and ‘10100001’ to the reader10.

When the transferred IDs do not collide with one another, the reader10can identify all of tag1, tag2, tag3and tag4based 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, tag1has the bit ‘1’ in the third, fourth, sixth and eighth bit positions of the ID, tag2has the bit ‘1’ in the third, fourth, and sixth bit position of the ID, tag3has the bit ‘1’ in the sixth order of the ID, and tag4has 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 reader10recognizes the collision bits as ‘X’, and therefore, an ID may be recognized as ‘10XX0X0X’.

The reader10then 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 reader10as ‘X’, as ‘1’, and a non-collision bit as ‘0’. Accordingly, when the reader10recognizes the collision ID bits as ‘10XX0X0X’, ‘00110101’ will be generated as the CBP value.

Next, the reader10transfers the ID request value ‘1’, which induced the ID collision, and the CBP value ‘00110101’ to the tags20. Upon receiving the ID request value ‘1’ and the CBP value ‘00110101’, the tags20check whether the ID request value ‘1’ matches their IDs. When the ID request value ‘1’ matches their IDs, the tags20generate 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 tag1generates the collision bits ‘1111’ based on the received CBP value, the tag2generates the collision bits ‘1110’ based on the CBP value, the tag3generates the collision bits ‘0010’ based on the CBP value, and the tag4generates the collision bits ‘1001’ based on the CBP value.

The number of bits that the tags20can transmit to the reader10as the CBDreq may be predetermined. If it is predetermined such that the tags20can transmit three bits as the CBDreq, for example, each of the tags20transfers the first three bits of the CBDreq, while excluding the last bit.

Therefore, the tags20transfer the generated CBDreq ‘111’, ‘111’, ‘001’, and ‘100’, respectively. The tags20may 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 tag1and the tag2may be expressed as ‘7’, CBDreq of the tag3may be expressed as ‘1’ and the CBDreq of the tag4may 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 tag1is expressed as ‘7’ in a decimal basis, the binary code ‘10000000’ is transferred. Because the CBDreq ‘111’ of the tag2is expressed as ‘7’ in a decimal basis, the binary code ‘10000000’ is transferred.

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

Upon receipt of the CBDreq, the reader10estimates the IDs within an identifiable range, using the ID bits ‘10XX0X0X’ as recognized by the collision, and the received CBDreq. The reader10estimates 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 tags20, the IDs with seven bits, that is, the IDs excluding the last X, are estimated.

The reader10then 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 tag20having the ID starting with ‘1011010’ transfers its ID to the reader10.

The reader10outputs 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 reader10transfers the ID request value ‘1011010’ to the tags20, and the tags20check whether the received ID request value ‘1011010’ matches their IDs. In other words, the tags20check whether their IDs start with ‘1011010’.

As a result, the tag1and tag2confirm that their IDs start with ‘1011010’, and transfer their IDs ‘10110101’ and ‘10110100’ to the reader10.

If the transferred IDs do not collide with each other, the reader10can identify both the tag1and the tag2using the received IDs.

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

Accordingly, the reader10regenerates 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 reader10then transfers the ID request value ‘1011010’, which induced the ID collision, and the CBP value ‘00000001’ to the tags20. The tags20, upon receiving them, check whether the ID request value ‘1011010’ matches their IDs. When the ID request value ‘1011010’ matches their IDs, the tags20generates a CBDreq from the CBP value ‘00000001’.

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

Likewise, when transferring the CBDreq, the number of bits that the tag1and tag2transmit to the reader10may be predetermined. As the CBDreq does no exceed the predetermined number of bits ‘3’, the tag1and tag2transfers the CBDreq ‘1’ and ‘0’, respectively.

Since the CBDreq received from the tag1and tag2do not exceed the preset number of bits, the reader10can identify the IDs of the tag1and tag2as ‘10110101’ and ‘10110100’ based on the received CBDreq ‘1’ and ‘0’.

The tag1and tag2may convert the CBDreq to binary values when transferring the CBDreq.

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

After identifying the IDs of the tag1and tag2, the reader10outputs the second ID request value ‘1000010’. At this time, the stored ID request value ‘1000010’ is removed from the queue. The reader10transfers the ID request value ‘1000010’ to the tags20. The tags20check whether the received ID request value ‘1000010’ matches their IDs. That is, the tags20check whether their IDs start with ‘1000010’.

As a result, the tag3confirms that its ID starts with ‘1000010’ and thus transfers its ID ‘10000100’ to the reader10.

The reader10identifies the ID of the tag3‘10000100’ because the received ID has no collision.

After identifying the ID of the tag3, the reader10outputs the third ID request value ‘1010000’. At this time, the stored ID request value ‘1010000’ is removed from the queue.

The reader10transfers the ID request value ‘1010000’ to the tags20. In response, the tags20check whether the received ID request value ‘1010000’ matches their IDs. That is, the tags20check whether their IDs start with ‘1010000’.

Of tag1, tag2, tag3and tag4, the tag4confirms that its ID starts with ‘1010000’ and thus transfers its ID ‘10100001’ to the reader10.

Since the transferred ID has no collision, the reader10can identify the ID of the tag4‘10100001’.

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

First, the reader20inputs the ID request values ‘0’ and ‘1’ into the queue and sets the number of collision bits transmittable from tags N (S500). Next, the reader20checks whether the queue is empty (S505). When the queue is empty, the tag ID identification is ended (S510).

When the queue is not empty, the reader10outputs and transfers the ID request value ‘0’ in the queue, and requests the transfer of IDs that match the ID request value (S515). 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 reader20checks whether IDs matching the ID request value ‘0’ are received or not (S520). When no matching IDs are received, the reader20returns to operation S505and checks whether the queue is empty. When the queue is not empty, the reader10outputs and transfers the stored ID request value ‘1’, and thus requests the transfer of IDs matching the ID request value ‘1’ (S515). 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 reader20checks whether IDs matching the ID request value ‘1’ are received or not (S520). When matching IDs are received, the reader10checks whether the received IDs have collision (S525).

When there is no collision in the received IDs, the reader10identifies the received tag IDs (S530) and returns back to operation S505.

When the received IDs collide, the reader10generates a CBP value and transfers the generated CBP value together with the ID request value (S535). Next, the reader10receives a CBDreq of the collision IDs (S545), and checks whether the number of collision bits is greater than the preset number of the transmittable collision bits N (S550).

When the number of collision bits is not greater than the preset number of the transmittable collision bits N, the reader10identifies the received ID based on the received CBP value (S555) and returns back to operation S505.

When the number of collision bits is greater than the preset number of the transmittable collision bits N, the reader10generates a new ID request value using the received CBDreq and stores the new ID request value in the queue (S560). Next, the reader10returns back to operation S505.

Ultimately, the reader10repeats operations S505through S560until there are no ID request values stored in the queue. When there are no ID request values left in the queue, the reader10can completely identify all the tag IDs.

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

The tag20always waits to receive a message from the reader10(S565). The tag20checks whether an ID request value is received from the reader10(S570). When the ID request value is not received, the tag20maintains the standby state (S565). By contrast, when the ID request value is received, the tag20checks whether the received ID request value matches its tag ID (S575).

When the received ID request value does not match its tag ID, the tag20maintains the standby state (S565). When the received ID request value matches its tag ID, the tag20checks whether the ID request value is received alone or together with the BDP value (S580).

When only the ID request value is received, the tag20transfers its ID to the reader ID (S585). When both the ID request value and the BDP value are received, the tag20generates a CBDreq and transfers the generated BCD value with the maximum bits within the preset number of transmittable collision bits (S590). Next, the tag20returns to the standby state (S565).

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

InFIG. 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 replies500of the related art and replies is less than the slope relating to the increase of the number of requests and replies550of 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. 5depicts a graph of another experimental results of the anti-collision method of the present invention.

InFIG. 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 reader10generates and transfers the CBP value which indicates the collision spots, and the respective tags20generates 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 reader10and the tags20can 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.