1.2 RFID System Anti-Collision Technology
21
(2) Regressive-style binary search tree, RBST
After the basic binary search tree algorithm completes a recognition, it loops from
the root node to the next reading process. In order to reduce the search times of the
algorithm, the regressive-style binary search tree will not go back to the root node
for re-identification after the completion of one time of recognition, but will go back
to the node of the last collision to continue the query.
The steps of the regressive-style binary tree algorithm are as follows:
(1) The tag enters the working range of the reader, and the reader sends a maximum
serial number signal. The serial number of all tags is less than or equal to the
maximum serial number, so the tag transponder sends its serial number back
to the reader at the same time.
(2) Because of the uniqueness of the tag sequence number, if the number of tags
is not less than two, the system will collide. At this point, the starting position
of the corresponding collision in the maximum sequence number will be 0. If
it is lower than that, then it stays the same. If it is higher than that, then it is 1.
(3) The reader sends the processed maximum sequence number to the tag, and the
tag transponder compares its own sequence number to that value and sends
back its own sequence number if it is less than or equal to that value.
(4) Loop through the above steps until a transponder with the minimum serial
number is selected, and after communicating with it normally, the tag
transponder is ordered to sleep, that is, it will not respond to the reader request
command unless it is reenergized.
(5) Return to the last node where the collision occurred, obtain the maximum
sequence number corresponding to the node, and repeat the above process to
identify each tag from small to large.
Following the example above, assuming the tag 0100 is identified in a search,
instead of the root node 0 returned by the base binary search tree, the reader
returns the collision node 010 and searches for the tag 0101 (the maximum
value of the collision node). In this way, the next tag can be immediately
identified, improving the identification efficiency.
(6) Dynamic Binary Search Tree, DBST.
The improvement of the dynamic binary search algorithm to basic binary search
algorithm focuses on reducing the amount of information transferred to the
system. In practical application, the identification serial number of RFID tags
may be more than 4 bits, as many as a dozen bytes. For such a tag with a
long serial number, if the value of the serial number is transmitted completely
every time, the amount of data to be transmitted will be relatively larger and
the time will be longer. The dynamic binary search was developed to solve this
problem.
The steps of the dynamic binary tree algorithm are as follows:
(1) The tag enters the working range of the reader, and the reader sends a maximum
serial number signal. The serial number of all tags is less than or equal to the
21
(2) Regressive-style binary search tree, RBST
After the basic binary search tree algorithm completes a recognition, it loops from
the root node to the next reading process. In order to reduce the search times of the
algorithm, the regressive-style binary search tree will not go back to the root node
for re-identification after the completion of one time of recognition, but will go back
to the node of the last collision to continue the query.
The steps of the regressive-style binary tree algorithm are as follows:
(1) The tag enters the working range of the reader, and the reader sends a maximum
serial number signal. The serial number of all tags is less than or equal to the
maximum serial number, so the tag transponder sends its serial number back
to the reader at the same time.
(2) Because of the uniqueness of the tag sequence number, if the number of tags
is not less than two, the system will collide. At this point, the starting position
of the corresponding collision in the maximum sequence number will be 0. If
it is lower than that, then it stays the same. If it is higher than that, then it is 1.
(3) The reader sends the processed maximum sequence number to the tag, and the
tag transponder compares its own sequence number to that value and sends
back its own sequence number if it is less than or equal to that value.
(4) Loop through the above steps until a transponder with the minimum serial
number is selected, and after communicating with it normally, the tag
transponder is ordered to sleep, that is, it will not respond to the reader request
command unless it is reenergized.
(5) Return to the last node where the collision occurred, obtain the maximum
sequence number corresponding to the node, and repeat the above process to
identify each tag from small to large.
Following the example above, assuming the tag 0100 is identified in a search,
instead of the root node 0 returned by the base binary search tree, the reader
returns the collision node 010 and searches for the tag 0101 (the maximum
value of the collision node). In this way, the next tag can be immediately
identified, improving the identification efficiency.
(6) Dynamic Binary Search Tree, DBST.
The improvement of the dynamic binary search algorithm to basic binary search
algorithm focuses on reducing the amount of information transferred to the
system. In practical application, the identification serial number of RFID tags
may be more than 4 bits, as many as a dozen bytes. For such a tag with a
long serial number, if the value of the serial number is transmitted completely
every time, the amount of data to be transmitted will be relatively larger and
the time will be longer. The dynamic binary search was developed to solve this
problem.
The steps of the dynamic binary tree algorithm are as follows:
(1) The tag enters the working range of the reader, and the reader sends a maximum
serial number signal. The serial number of all tags is less than or equal to the