汤宏斌，周尚波

(1.重庆第二师范学院 数学与信息工程系，重庆 400067；2.重庆大学 计算机学院，重庆 400044)

基于锁位的奇偶分区二进制树算法

汤宏斌1，2，周尚波2

(1.重庆第二师范学院 数学与信息工程系，重庆 400067；2.重庆大学 计算机学院，重庆 400044)

无线射频识别(radio frequency identification, RFID)是物联网的技术核心，防碰撞技术则是FRID必须面对的问题，针对二进制树算法时延较长，寻呼次数过多，效率低下的特点，在现有改进的二进制树算法基础上，提出一种奇偶区域锁位的二进制树算法。通过将寻呼区域划分为奇偶2个区域，并进行分区搜索，在每个搜索周期内，自动识别1位或2位碰撞标签，减少了寻呼次数，以提高搜索效率；采取增加锁位寻呼指令，将标签的应答位数限制在只传送发生碰撞的比特上，由于每次寻呼的时候，已经检测出的比特位无需再传输，可以减少总的传输比特数量，大大降低了传输时延，理论分析和仿真结果都表明该算法的有效性和优越性。

无线射频识别；奇偶区域； 锁位；防碰撞 ；二进制树

0 引 言

无线射频识别(radio frequency identification, RFID)技术在多标签识别中的关键是防碰撞问题。目前，常用的防碰撞算法都是基于时分多路(time division multiple access, TDMA)算法，防碰撞算法可根据标签的响应方式不同分为 ALOHA算法和二进制树算法2种。ALOHA算法有个致命的缺点是：标签有可能出现不被识别的情况[1-4]，二进制树算法可以全部识别标签，但缺点是识别周期较长[5-6]。

基本二进制树(binary search, BS)的防碰撞机制是以标签序列编号UID(ubiquitous identification)的唯一性为基础。第一次寻呼时，阅读器发出全1的查询指令，所有标签都做出响应，若只有一个标签，则无碰撞；……