Anti-collision method and system using optimized binary search tree

• US 20060158312A1
• Filed: 12/27/2005
• Published: 07/20/2006
• Est. Priority Date: 01/12/2005
• Status: Active Grant

• Current Assignee: Samsung Electro-Mechanics Co., Ltd. (Samsung Group)
• Original Assignee: Samsung Electro-Mechanics Co., Ltd. (Samsung Group)
• Inventors: Park, Kyung-ho, Kim, Seon-wook, Kang, Woo-shik, An, Sun-shin, Jung, Young-hwan
• Granted Patent: US 7,741,955 B2
• Time in Patent Office: Days
• US Class Current: 340/10.200
• CPC Class Codes: G06K 7/0008 General problems related to the reading of electronic memory record carriers, independent of its reading method, e.g. power transfer
• CPC Class Codes: G06K 7/10049 binary tree

Abstract

Method for rapidly detecting identifier (ID) of tags, by radio frequency identification (RFID) reader in communication system that includes RFID reader and at least two tags communicating with RFID reader, is provided. RFID reader generates a prefix when IDs contained in at least two messages received collide with each other, prefix including a first colliding bit, which is set to ‘0’ or ‘1’, from high-order bits and non-colliding high-order bits. RFID reader sends a first message containing information that requests transmission of an assigned ID in a preset transmission period when the bits of the generated prefix match bits corresponding to the prefix, in the assigned ID. Tags receive a first message that contains a prefix including at least one bit, and sends a second message containing an assigned ID during a preset transmission period when the bits of the prefix match bits corresponding to the prefix, in assigned ID.

Claims

1. A method for detecting an identifier (ID) of radio frequency (RF) devices, the ID consisting of a plurality of bits, the method comprising:

generating a prefix when a first ID in a first message collides with a second ID in a second message to generate a third ID, the prefix including a first colliding bit of the third ID, which is set to ‘

0’

or ‘

1’ and

at least one non-colliding high-order bit if the third ID includes the at least one non-colliding high-order bit; and

sending a third message which contains information that requests a transmission of an assigned ID in a preset transmission period if bits of the generated prefix match corresponding bits in the assigned ID.

2. The method of claim 1, wherein a transmission period of the first message and the second message and a transmission period of the third message are arranged in an alternating temporal manner.

3. The method of claim 2, wherein the transmission period of the first message and the second message includes a first transmission period and a second transmission period.

4. The method of claim 3, wherein the first message is transmitted during the first transmission period if a low-order bit of the first ID is ‘

0’

, and the second message is transmitted during the second transmission period if a low-order bit of the second ID is ‘

1’

.

5. The method of claim 4, wherein an order of the low-order bit of the first ID is lower than the first colliding bit of the prefix.

6. The method of claim 1, wherein the information that requests the transmission of the assigned ID requests a transmission of bits of the assigned ID other than the corresponding bits of the assigned ID.

7. The method of claim 1, wherein the information requests the transmission of the assigned ID only to an RF device having the assigned ID.

8. The method of claim 1, wherein an order of the first colliding bit is the highest among colliding bits of the third I]D.

9. The method of claim 8, wherein the colliding bits are corrupted bits not identifiable to any ID.

10. The method of claim 8, wherein an order of the at least one non-colliding high-order bit is higher than an order of the first colliding bit.

11. A method for transmitting an identifier (ID) from radio frequency (RF) devices, the ID consisting of a plurality of bits, to an RF reader communicating with the RF devices, the method comprising:

receiving a first message that contains a prefix including at least one bit; and

sending a second message containing an assigned ID during a preset transmission period if the at least one bit of the prefix matches corresponding at least one bit in the assigned ID.

12. The method of claim 11, wherein a transmission period of the first message and a transmission period of the second message are arranged in an alternating temporal manner.

13. The method of claim 12, wherein the transmission period of the second message includes a first transmission period and a second transmission period.

14. The method of claim 13, wherein an RF device transmits the assigned ID during the first transmission period if a low-order bit of the assigned ID is ‘

0’

, and the RF device transmits the assigned ID during the second transmission period if the low-order bit is ‘

1’

.

15. The method of claim 13, wherein the RF device transmits bits of the assigned ID other than the corresponding at least one bit in the assigned ID if the at least one bit of the prefix matches the corresponding at least one bit of the assigned ID.

16. An identifier (ID) detection system comprising a first radio frequency (RF) device and a second RF device and a third RF device, the second device and the third RF device communicating with the first RF device, wherein:

the first RF device generates a prefix if a first ID contained in a first message and a second ID contained in a second message collide with each other to generate a third ID, the prefix including a first colliding bit of the third ID, which is set to ‘

0’

or ‘

1’ and

at least one non-colliding high-order bit if the third ID includes the at least one non-colliding high-order bit, and sending a third message which contains information that requests a transmission of an assigned ID during a preset transmission period if bits of the generated prefix match corresponding bits in the assigned ID; and

the second RF device and the third RF device are operable to respectively send the first message containing the first ID and the second message containing the second ID, to the RFID reader.

17. The ID detection system of claim 16, wherein a transmission period of the first message and the second message and a transmission period of the third message are arranged in an alternating temporal manner.

18. The ID detection system of claim 17, wherein the transmission period of the first message and the second message includes a first transmission period and a second transmission period.

19. The ID detection system of claim 16, wherein the first RF device requests the transmission of bits of the assigned ID other than the bits of the assigned ID corresponding to the bits of the generated prefix if the bits of the generated prefix match corresponding bits of the assigned ID.

20. An identifier (ID) detection system comprising a radio frequency identification (RFID) reader and at least a first tag and a second tag communicating with the RFID reader, wherein:

the RFID reader transmits a first message containing a prefix;

the first tag and the second tag receive the first message that contains the prefix including at least one bit; and

at least one of the first tag and the second tag sends a second message containing an assigned ID of the at least one of the first tag and the second tag during a preset transmission period if bits of the prefix match corresponding bits in the assigned ID.

21. The ID detection system of claim 20, wherein a transmission period of the first message and a transmission period of the second message are arranged in an alternating temporal manner.

22. The ID detection system of claim 21, wherein the transmission period of the second message includes a first transmission period and a second transmission period.

23. The ID detection system of claim 22, wherein the at least one of the first tag and the second tag transmits the assigned ID during the first transmission period if a low-order bit of the assigned ID is ‘

0’

, and the at least one of the first tag and the second tag transmits the assigned ID during the second transmission period if the low-order bit is ‘

1’

.