20
1 Overview of RFID System Anti-Collision Technology
Fig. 1.7 Tree algorithm schematic diagram
cannot be identified for a long time, so it is called the deterministic method. The
basic binary search tree, the backward binary search tree, and the dynamic binary
table tree are introduced here.
(1) Binary search tree, BST
Binary search tree algorithm is similar to dichotomy, searching by a tree branch. All
tag sequence numbers uniquely identified in binary form can form a complete binary
tree. The serial number of the tag that synchronously sends signals to the reader
within the scope of the reader also constitutes a binary tree. The reader repeatedly
screens the branches of the complete binary tree according to the collision of signals,
and finally finds the corresponding tags.
As shown in Fig. 1.7, suppose you have six tags with ids of 0010,0100,0101,
1001,1110, 1111. The query starts from the parent node, and the reader sends information 0 to the tag. All tags with ID first 0 respond, and the response signal is sent to
the reader, that is, a collision occurs at node 0; The reader again sends a message 00
to the response tag, and only the tag 0010 responds, that is, the tag is recognized; The
reader sends the message 01 again, the tags 0100 and 0101 respond, and the reader
sends the response signal, that is, the collision occurs at node 01; The reader sends
the information 010 again, tags 0100 and 0101 respond, and the reader sends the
response signal, that is, a collision occurs at node 010; The reader sends a message
0100 to the response tag again. Only the tag 0100 responds, that is, the tag is recognized; The reader again sends the message 0101 to the response tag, and only the tag
0101 responds, that is, the tag is recognized. At this point, the tag query of node 0 is
finished, and the tag query of node 1 is the same.
1 Overview of RFID System Anti-Collision Technology
Fig. 1.7 Tree algorithm schematic diagram
cannot be identified for a long time, so it is called the deterministic method. The
basic binary search tree, the backward binary search tree, and the dynamic binary
table tree are introduced here.
(1) Binary search tree, BST
Binary search tree algorithm is similar to dichotomy, searching by a tree branch. All
tag sequence numbers uniquely identified in binary form can form a complete binary
tree. The serial number of the tag that synchronously sends signals to the reader
within the scope of the reader also constitutes a binary tree. The reader repeatedly
screens the branches of the complete binary tree according to the collision of signals,
and finally finds the corresponding tags.
As shown in Fig. 1.7, suppose you have six tags with ids of 0010,0100,0101,
1001,1110, 1111. The query starts from the parent node, and the reader sends information 0 to the tag. All tags with ID first 0 respond, and the response signal is sent to
the reader, that is, a collision occurs at node 0; The reader again sends a message 00
to the response tag, and only the tag 0010 responds, that is, the tag is recognized; The
reader sends the message 01 again, the tags 0100 and 0101 respond, and the reader
sends the response signal, that is, the collision occurs at node 01; The reader sends
the information 010 again, tags 0100 and 0101 respond, and the reader sends the
response signal, that is, a collision occurs at node 010; The reader sends a message
0100 to the response tag again. Only the tag 0100 responds, that is, the tag is recognized; The reader again sends the message 0101 to the response tag, and only the tag
0101 responds, that is, the tag is recognized. At this point, the tag query of node 0 is
finished, and the tag query of node 1 is the same.