摘要: 通过对现有防碰撞算法的分析,在二叉树搜索算法的基础上提出一种新的以矩阵形式为搜索结构的混合树防碰撞算法。该算法采取段式搜索,即每次发送的碰撞前缀为多个非碰撞位与碰撞位的组合,在碰撞位位数的选取上采取遇到单个碰撞位进行二叉树分裂,遇到连续碰撞位进行四叉树分裂的策略,从而缩短标签识别时间,并通过理论证明了该算法的有效性。
关键词:
无线射频识别,
防碰撞,
矩阵,
二叉树搜索,
四叉树搜索
Abstract: This paper analyzes the anti-collision algorithm in existence, and proposes a new algorithm based on binary-tree search algorithm with matrix form. The algorithm takes use of several bits but not one as search prefix. It means that the search prefix is made up of non-collision bits and collision bits. When continuous collision is appeared, it takes quad tree structure and when there is only one collision bit, it takes binary-tree structure. In this way, the time of identifying the tag is shorter and it also proves to be effective.
Key words:
Radio Frequency IDentification(RFID),
anti-collision,
matrix,
binary-tree search,
quad-tree search
中图分类号:
孙文胜, 刘婷. 一种改进的基于二叉树搜索的防碰撞算法[J]. 计算机工程, 2011, 37(10): 257-259.
SUN Wen-Qing, LIU Ting. Improved Anti-collision Algorithm Based on Binary-tree Search[J]. Computer Engineering, 2011, 37(10): 257-259.