BINARY TREE METHOD FOR MULTI-TAG ANTI-COLLISION

• US 20100271185A1
• Filed: 07/11/2008
• Published: 10/28/2010
• Est. Priority Date: 11/20/2007
• Status: Active Grant

• Current Assignee: ZTE Corporation
• Original Assignee: ZTE Corporation
• Inventors: Zhou, Huan, Zhang, Jian, Jiao, Hongai
• Granted Patent: US 8,310,343 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/10029 the collision being resolved in the time domain, e.g. using binary tree search or RFID responses allocated to a random time slot
• CPC Class Codes: G06K 7/10049 binary tree

Abstract

A binary tree method for avoiding collision of multiple tags, comprising: during inventorying tags, a reader sending a re-splitting instruction to the tags and entering a next time slot for reception if the reader does not receive any reply information from the tags in a specified time slot and one of the following conditions is satisfied: the reader received incorrect reply information from the tags in the former time slot, or a re-splitting instruction was sent in the former time slot; and when the tags receive the re-splitting instruction, for tags whose counter values are not 1, the counter values remaining unchanged, and tags whose counter values are 1 splitting into two subsets 0 and 1, and those counter-0 tags replying to the reader. With the present invention, the inventorying flow of Binary Tree is optimized, the inventorying efficiency is improved, and the whole flow becomes more reasonable.

Claims

1. A binary tree method for avoiding collision of multiple tags, comprising:

during inventorying tags, a reader sending a re-splitting instruction to the tags and entering a next time slot for reception if the reader does not receive any reply information from the tags in a specified time slot and one of the following conditions is satisfied;

the reader received incorrectly reply information from the tags in a former time slot, or a re-splitting instruction was sent in the former time slot; and

when the tags receive the re-splitting instruction, for tags whose counter values are not 1, the counter values remaining unchanged, and tags whose counter values are 1 splitting into two subsets, counter values of tags in one of the subsets remaining unchanged, and counter values of tags in the other subset decreasing by 1, and then the tag whose counter value is 0 replying to the reader.

2. The method of claim 1, further comprising:

during inventorying the tags, the reader sending a success acknowledgement instruction to the tags and entering a next time slot for reception if the reader does not receive any reply information from the tags in a specified time slot and one of the following conditions is satisfied;

the reader did not receive any reply information from the tags or received correctly reply information from the tags in a former time slot; and

when the tags receive the success acknowledgement instruction, the tag replying information correctly leaving the inventorying process, and counter values of the tags replying information incorrectly decreasing by 1, and then the tag whose counter value is 0 replying to the reader.

3. The method of claim 1, further comprising:

during inventorying the tags, the reader sending a success acknowledgement instruction to the tags and entering a next time slot for reception if the reader receives reply information from the tags correctly in a specified time slot; and

when the tags receive the success acknowledgement instruction, the tag replying information correctly leaving the inventorying process, and counter values of the tags replying information incorrectly decreasing by 1, and then the tag whose counter value is 0 replying to the reader.

4. The method of claim 1, further comprising:

during inventorying the tags, the reader sending a failure acknowledgement instruction to the tags and entering a next time slot for reception if the reader receives reply information from the tags incorrectly in a specified time slot; and

when the tags receive the failure acknowledgement instruction, for tags whose counter values are not 0, the counter values increasing by 1; and

tags whose counter values are 0 splitting into two subsets, counter values of tags in one of the subsets remaining unchanged, and counter values of tags in the other subset increasing by 1, and then the tag whose counter value is 0 replying to the reader.

5. The method of claim 1, further comprising:

when the tags split, activating a random number generator which generates 1 for tags in one of the subsets and generates 0 for tags in the other subset, counters values of tags for which 0 is generated decreasing by 1, and counter values of tags for which 1 is generated remaining unchanged.

6. The method of claim 4, further comprising:

when the tags split, activating a random number generator which generates 1 for tags in one of the subsets and generates 0 for tags in the other subset, counters values of tags for which 0 is generated remaining unchanged, and counter values of tags for which 1 is generated increasing by 1.

7. The method of claim 3, further comprising:

if the reader does not receive any reply information from the tags in a specified time slot and a re-splitting instruction was sent in a former time slot, and if the number of times the re-splitting instruction has been sent consecutively is recorded as N and N<

n, then the reader sending the re-splitting instruction to the tags, otherwise, if N=n, the reader sending a success acknowledgement instruction to the tags and entering a next time slot for reception;

n being a permitted number of times the re-splitting instruction can be sent consecutively, value of which is determined by a system or user.

8. The method of claim 7, wherein the value of n is 2.