一种减少通信复杂度的RFID搜索树防碰撞算法*

莫 磊，唐 斌，房梦旭

(1.成都航空职业技术学院 信息工程学院，成都 610100；2.四川省高校校企联合“航空电子技术”应用技术创新基地，成都 610100)

0 引 言

典型的射频识别(Radio Frequency Identification,RFID)系统一般由电子标签和阅读器组成[1]，其防碰撞问题主要有三种情况，分别是一个阅读器作用范围内有多个标签、多个阅读器作用范围内有一个标签和多个阅读器作用范围内有多个标签，涉及的问题主要有多标签碰撞问题和多阅读器碰撞问题。由于标签的成本低、能量少、内存小、计算处理能力弱，RFID防碰撞问题的难点主要集中在多标签防碰撞方面。本文针对第一种情况进行研究。在这种情况下，由于所有的电子标签与阅读器共用一个信道，当有多个标签处于同一阅读器的作用范围内，在同一时刻向阅读器发送数据时就会发生碰撞，导致阅读器不能读取标签数据[2]。

现阶段多标签防碰撞算法一般是基于时分多路的方法，主要有基于二进制搜索树的防碰撞算法和基于ALOHA的防碰撞算法[3]。ALOHA算法是一种基于概率统计的防碰撞算法，读取量大，速度快，但很多情况下读取率达不到100%，存在由于多次读不到某一标签而出现“饥饿”问题[4]。二进制树算法是一种确定性算法，不存在“饥饿”问题，读取率可以达到100%，但通信量大，读取时间长[5]。本文重点研究二进制树算法。

在搜索树算法中，除了总时隙指标以外，通信复杂度也是非常重要的指标，它是识别所有标签所需传送的总比特数[6]，在查询时隙相同的情况下，单位时隙通信数据量越少，则通信复杂度越低。……