Abstract: To address the problem that the typical binary search algorithms have numerous searches, large amount of data transmission and low recognition efficiency, this paper presents a binary one-dimensional matrix search anti-collision improved algorithm. This algorithm structures a binary search matrix according to the detected tag collision, and determines the collision-bit corresponding value matrix to search tags. This improved algorithm makes the transmission capacity between the reader and the tags reduced by improving search prefix, and in the tag identification process, the search matrix and its corresponding value matrix can be modified to achieve a continuous search and identification on tags for the reader with the changes of collision bits. Examples and Matlab simulation results show that this algorithm has less increase in the number of searches and the total amount of data transmission with the increase in the number of tags, improves the system throughput, up to 66%~78%, and accelerates the identification process of the system.

Key words: radio frequency identification, anti-collision algorithm, Manchester encoding, binary search, matrix search

摘要： 针对典型二进制搜索算法存在的搜索次数多、数据传输量大、系统识别效率低的问题，提出了一种二进制一维矩阵搜索防碰撞改进算法。该算法根据检测到的标签碰撞位信息构造二进制搜索矩阵，并确定相应的碰撞位对应值矩阵对标签进行搜索，通过对搜索前缀进行改进，使得读写器与标签之间传输量减少，且在标签识别过程中，碰撞位矩阵及其对应值矩阵需根据碰撞位的改变进行修改，以实现读写器对标签的连续搜索及识别。实例说明及Matlab仿真结果表明，随着标签数目的增加，改进算法的搜索次数和总的数据传输量增加相对较少，系统吞吐率提高，可达66%~78%，系统的识别过程加快。

关键词: 射频识别, 防碰撞算法, 曼彻斯特编码, 二进制搜索, 矩阵搜索