一种基于分组动态帧与二叉树递归识别的射频识别防冲突算法

An RFID Anti-collision Algorithm Based on Grouped Dynamic Frame and Binary Tree Recursive Identification

首先分析和比较了传统射频识别防冲突算法的时间复杂度和通信复杂度,并在总结各自缺点的基础上提出了一种新颖的射频识别防冲突算法。该算法基于标签最优分组、最优帧长选择以及碰撞时隙内二叉树递归识别等策略。其次,建立了系统模型,并对该算法的时间复杂度和通信复杂度进行了数学推导。仿真数据表明,以上指标的理论值和模拟值有较好的一致性。与传统算法相比,该算法具有较佳的总体性能,系统吞吐率达到0.41左右,通信复杂度与EDFSA算法近似,但与树形算法相比减少了50%以上;此外,该算法受初始标签数量估计值及标签ID长度的影响均较小。

This paper firstly analyzes and compares the time complexity and communication complexity of tranditional RFID （radio frequency identification） anti-collision algorithms. Their weaknesses are summarized, and a novel RFID anticollision algorithm is proposed based on the strategies of optimal group number, optimal frame size and binary tree recursive identification in each collision slot. Secondly, a system model is set up and mathematical deductions of time complexity and communication complexity are achieved. Simulations show that the simulative values of the above indexes are in good accordance with their theoretical values. Compared with traditional anti-collision algorithms, the presented algorithm exhibits excellent general performances： the system throughput is around 0.41, and the communication complexity approximates to that of EDFSA and is less than half of that of the tree-based algorithms. Moreover, the new algorithm is tolerant to the inaccuracy of initial tag estimation and the variation of tag＇s ID length.