Abstract: In order to overcome the low efficiency of traditional binary-tree anti-collision algorithms, an adaptive multi-tree anti-collision algorithm based on heuristic function was presented in the paper. By defining the heuristic function which was computed by the number of collision bits, the new algorithm can estimate the number of tags in the branch effectively. Because the new algorithm can adjust the number of searching fork in different branches and depths dynamically, it improves the searching efficiency. The theoretical analyses and simulation results show that the new algorithm overcomes the deficiency of traditional algorithms. For the large number of tags in particular, it can reduce the searching and recognition time and increase the throughput of Radio Frequency IDentification (RFID) system.

Key words: Radio Frequency IDentification (RFID), anti-collision algorithm, heuristic function, multi-tree, throughput

摘要： 为克服传统二叉树防碰撞算法搜索效率低的缺点,提出了一种基于启发式函数的自适应多叉树防碰撞算法。新算法通过定义和计算启发式函数,有效地利用碰撞比特信息来估计节点内待识别标签的数量。新算法根据节点内的标签数量,可在不同节点和深度,自适应地调整搜索叉数,从而有效地提高了算法的搜索效率。理论分析和仿真实验证明:新算法克服了传统防碰撞算法的缺点,尤其在待识别标签数量较多场合,可有效地减少搜索和识别时间,提高射频识别系统的吞吐率。

关键词: 射频识别, 防碰撞算法, 启发式函数, 多叉树, 吞吐率