一种基于二叉树形搜索的RFID防碰撞算法

　　0 引言

　　射频识别 (Radio Frequency Identification, RFID)的主要思想是通过射频信号自动识别目标对象并获取相关数据。RFID系统一般由电子标签( Tag)和阅读器(Reader)组成。阅读器负责发送广播并接收标签的标识信息;标签收到广播命令后将自身标识信息发送给阅读器。在数据传输的过程中从阅读器到标签的数据传输称作下传,从标签到阅读器的数据传输称作上传。

　　随着RFID的发展，其应用也越来越广泛，当阅读器识别区域内存在两个或者两个以上的标签在同一时刻向阅读器发送标识信息时,将产生碰撞问题。解决碰撞问题的方法主要有空分多址(SDMA)、时分多址(TDMA)、码分多址(CDMA)、频分多址(FDMA)四大类。而其中时分多址方法在RFID防碰撞问题上是普遍采用的，它在复杂度和成本等方面都比其它3种方法更具优越性。目前存在的基于TDMA 的反碰撞算法主要有两种: 二进制搜索算法和ALOHA 算法。ALOHA 算法采用无规则的时分多址，或者叫随机多址。ALOHA 算法操作简便，成本低。但在应用中随着标签数量的扩大，性能将会急剧恶化。二进制搜索算法的电路实现要比ALOHA 算法复杂，但算法识别率较高。动态二进制搜索防碰撞算法以其简明的思想、稳定的系统性能和较少的系统资源需求在ISO/IEC14443A标准中被推荐为抗碰撞算法。本文提出一种二叉树形搜索防碰撞算法，在平均时延等性能上相比动态二进制搜索算法有明显改进,其分别通过识别每个标签所需传输的平均比特数来反映。验结果可以证明该算法是一种有效的防碰撞算法。

　　1 二进制搜索算法

　　1.1 二进制搜索防碰撞算法

　　二进制搜索算法由一个读写器和多个标签之间规定的一组命令和应答规则构成,目的在于从多卡中选出任一个实现数据通信。该算法关键在于选用适当的易于识别的基带编码(如曼彻斯特码(Mancherster)编码)、利用标签卡序列号唯一的特性和设计一组有效的指令规则,高效、迅速地实现选卡。

　　在二进制搜索算法的实现中,起决定作用的是读写器所使用的信号编码必须能够确定碰撞的准确比特位置。曼彻斯特码(Mancherster) 可在多卡同时响应时,译出错误码字,可以按位识别出碰撞。这样可以根据碰撞的位置,按一定法则重新搜索标签。

　　二进制搜索法的实现需要每一个标签都拥有唯一的一个ID号，算法的工作流程是:

　　(1) 首先读写器发送一个与标签位数相同，数值全为1(即可能出现的最大码)到标签，所有标签均发回它们的序列号。

　　(2) 对比标签返回的各序列号相同位置上的位值(0或者1)，如果某一位上同时出现0和1，则译码将出现无法判断的位，即认为该位是碰撞的。

　　(3) 确定有碰撞后,把有不一致位的数从最高位到次低位依次置0 再输出序列号,即依次排除序列号大的数,至读写器对比标签响应的序列号的相同位数上的数完全一致时,说明无碰撞。这时就选出序列号最小的数。

　　(4) 选出序列号最小的数后,对该卡进行数据交换,然后使该卡进入“无声”状态,则在读写器范围也不再响应(移动该范围后移入可再次响应)。

　　(5) 重复步骤(1),选出不是无声状态的标签中序列号最小的标签进行数据交换。

　　(6) 多次循环后可完成所有标签的读取。

　　1.2 动态二进制搜索算法

　　考虑到RFID标签中的序列号长度标签的序列号可能很长，如EPC 编码的3 个版本中的编码长度分别为64 位、96 位和256位，而UID(Ubiquitous Identifications) 编码长度128 位，随着今后的发展可能需要扩展到更长的长度。如此看来，若每次读写器发送的命令请求和标签的回复均以全部序列号进行，会造成传输的数据量太大，降低了防碰撞算法的效率。动态二进制搜索算法提出的主要思想在于减少在识别过程中传输的数据量，其每一次读写器发送和标签回复总共发送的位数是ID的总长度。这在一次收发中使传输的数据量相比基本二进制搜索算法减少了50%。

　　下面介绍动态二进制搜索算法及其工作过程。设有M个标签，每个标签中ID码的长度为N。

　　(1) 首先读写器发送一个完整的N位ID码 ,每个位上的码全为1,让所有标签都发回响应。

　　(2) 读写器判断所有返回的标签序列号，并把最高的碰撞位X找出并置0。然后传输N～X位的数据后即中断传输。标签接到这段数据与自己的标签从高到低比较,若相同则回传该标签ID的X-1～0，可看出一次收发以最高碰撞位为界，传输数据量减少一半。

　　(3) 读写器检测返回的序列号，若无碰撞则直接跳入步骤(4);若仍有碰撞，检测出最高碰撞位X\-1并置其为0，把上次发送的N～X位前缀加上这一次的N\-1～X\-1位数据发送后中断传输。标签把收到的码与其自身的N～X\-1位比较，若相同则返回其X\-1～0位，不同则不响应。重复步骤(3)。

　　(4) 若无冲突位则可以通过发送READ-DATA命令读取数据，并把该标签置“无声”状态，以后不再响应。

　　(5) 重复步骤(1),直到所有标签识别出来。

　　1.3 标签预处理算法

　　在RFID系统的实际应用中，标签的ID号中的碰撞位是不一定紧邻的，也就是说在两个相邻的碰撞位中，很可能存在着若干位不冲突的位值。显然这些位在防碰撞算法中是无关紧要的，所以如果在开始防碰撞算法前把所有标签中不冲突的位排除出去，之后不再传输这些位置上的数值，对ID号进行了压缩，这将减少防碰撞算法所需传输的数据量，提高防碰撞算法的效率。

　　标签预处理算法的过程如下：

　　(1) 读写器发送查询信号

　　(2) 所有标签均发回它们的完整ID号。

　　(3) 读写器检测这些ID号中的碰撞位，产生一个与ID号同等长度的序列记录碰撞的位置，0代表该位无冲突，1则代表该位有冲突。

　　(4) 读写器发送产生的冲突位置序列到标签， 标签中的存储器记录冲突的位置，之后标签的ID被压缩，只有冲突的位被保留在ID中。

　　2 二叉树形搜索防碰撞算法

　　在动态二进制搜索防碰撞算法中，每一次读写器与标签之间的通信所传输的数据是以一个碰撞位为界，读写器发送ID的前缀部分，标签发送ID的后续部分。由于标签ID一般比较长，希望能更进一步减少在标签识别过程中传输的数据量。本文提出一种二叉树形搜索防碰撞算法，因其搜索路径类似数据结构中二叉树而命此名。其最大的特点是每次读写器与标签的通信，两者均只需发送一比特有效数据。这极大程度的减少了平均最小时延和平均功率消耗，大大提高了防碰撞算法的识别效率。下面详细介绍该算法。

　　2.1 算法约定

　　(1) 每个标签中的ID都是唯一的。

　　(2) 每个标签中包含一个位置计数器P(用于记录当前响应读写器的是哪一位)。

　　(3) 每个标签中包含一个睡眠程度计数器S(用于记录该标签的睡眠程度)。

　　(4) 每个标签中包含一个已读标志位R(用于记录标签是否已经被读)。

　　2.2 指令规则

　　(1) REQ_0 ：0请求，该命令无参数，标签接收该命令后先检查S，若S>0则S加1，P不变;若S=0则检测ID(P)(ID中第P位数值)，若ID(P)=1则把S加1;若为ID(P)=0则把该标签的P增加1且发回P增加后所指的那位数值到读写器，特殊的是当P增加后已经指向ID的最后一位，则发回P所指的最后位再加上一位1表示P已经指在最后位。

　　(2) REQ_LONG：长请求，该命令无参数，设标签总长度为N，标签收到命令后发回其ID的P～N位。

　　(3) READ_X:读数据，带一位参数，X为参数(0或1)。标签收到命令将第P位与X比较，相等则将存储的数据发送给读写器，并把标签中的R置1,表示该标签已被读取,之后不再响应任何命令;不相等则不做反应。

　　(4) REQ_1 ：1请求，该命令无参数，所有R=0、S>0的标签收到命令都把S减1。如果R=0、S=0，则该标签的P增加1且发回位置P+1上的那位数值到读写器。特殊的是当标签是发送最后一位时，再加上一位1表示P已经指在最后位。

　　(5) CHG_POS：更改位置，该命令带一个位数为|log2 N|+1(表示不小于log2 N的最小整数，N为标签ID长度)的二进制数P'，表示响应的标签中P需要增加的数值。响应命令的标签把P改为P+P'-1 ，发回此时的第P位的值，特殊的是如果此时P为最后位，则发回最后位上的值再加上一位1表示已是最后。

　　2.3 算法流程说明

　　算法的流程图如图2所示。结合流程图对算法的流程说明如下：

　　首先，只有R=0的标签才对上述指令规则中的命令响应;其中只有S=0且R=0的标签才对REQ_LONG、READ_X、CHG_POS命令响应。识别过程开始前先进行初始化，使所有标签中的S=0,R=0,P=1。表示均处于非睡眠未读状态，且当前P指向ID中的第1位。

　　其次，对流程图中5个分支判断过程说明如下：

　　(1) 是否有停止位? 该判断分支的输入是标签发送给读写器的回复，如果有停止位，说明发回信息的标签中P已经指向最后一位;没有停止位则说明发回信息的标签中的P还没有指向最后位。

　　(2) 是否碰撞?该判断分支的输入是判断(1)的N分支，也就是无停止位的情况。此时仅判断收到的这位数值信息是否有碰撞发生，如果有碰撞则使用REQ_0命令继续分离碰撞的标签;如果无碰撞，说明发回信息的标签中P所指的数值是相同的，但不能断定P以后的位置上的数值不发生碰撞，所以使用REQ_LONG命令来使标签发回ID的P~N位，用于获取P以后的最近碰撞位。

　　(3) 是否碰撞?REQ_LONG命令后，响应命令的标签发回ID的P~N位。如果无碰撞出现，根据ID的唯一性，可以断定此时仅一个标签响应，接下来便可使用READ_X命令读取数据，参数X显然就是发回的信息中的首位数值信息;如果有碰撞出现，则计算到最早出现的碰撞位，使用CHG_POS命令把这些标签中的P增加到最早出现碰撞的位置，标签发回新的P所指的位置上的数值信息，并根据P是否指向最后位来决定是否加停止位。

　　(4) 是否碰撞?该判断分支的输入是判断(1)的Y分支，也就是确定标签的回复中包含停止位的情况。此时对数值位检测碰撞发生情况：如果有碰撞，可以确定此时发回信息的标签只有两个，且它们的ID的最后一位不同，即可连续使用READ_0、READ_1读取这两个标签的数据;如果无碰撞，则可断定只有一个标签发回信息，直接使用READ_X命令读取该标签的数据，参数X显然是两位回复信息中的第一位(数值位)。

　　(5) 有回复?该判断分支在REQ_1命令之后，该命令会唤醒睡眠程度S=1的标签，并使这些被唤醒的标签发回P+1所指位置上的数值信息，转到判断分支(1)对标签进行分离识别。如果在命令REQ_1后没有任何回复，则识别过程结束。

　　算法流程如图2所示。

　　 2.4 算法举例

　　假设有4个标签，分别是：Tag1：011000；Tag2：110011；Tag3：001011；Tag4：11001；

　　所有标签在刚进入读写器射频覆盖范围时都进行初始化，所有的S=0，P=1，R=0,。识别过程如表1所示。

　　3 算法性能分析与比较

　　本文提出的算法，其最大特点在于，相比二进制动态搜索算法而言，极大程度上减少了每次读写器与标签的通信过程中所需的数据量，读写器所发送的命令基本上已经无需携带额外的参数，标签的回复信息一般缩短到只需1~2位数值信息，有一种例外的情况是当标签在收到REQ_LONG命令后会回复标签中P～N位置的一串码。但不难看出，出现这种命令的机率会随着标签数目的增加而减少。因为标签数越多，在REQ_LONG命令之前收到的返回码发生冲突的可能性越大，由流程图可看出识别过程转向下一个REQ_0的机率也就越大，这就降低了出现REQ_LONG命令的出现概率。也就是说，改进算法在识别过程中的所需收发的平均比特数对于标签总数N的增大是收敛的。所以该算法在标签识别的平均最小时延方面得到了很大的改进。

　　为了更清晰的反映本文提出的算法在RFID的平均最小时延方面的高效性，对标签识别过程进行实验仿真，并与ISO/IEC14443A标准中推荐的动态二进制搜索防碰撞算法在相同的实验条件下进行结果比较。

　　EPC编码的3个版本中的编码长度分别为64 位、96 位和256位，在下述实验中编码长度采用96位，读写器的命令长度根据ISO/IEC14443A标准采用9比特。

　　其编码格式为：

　　由于标签识别中的平均最小时延是通过识别每个标签所需的平均比特数来反映，实验中定义一个称为平均比特数(AverageBit)的比较量，来衡量算法的性能。

　　平均比特数(AverageBit)=

　　如果读写器命令带参数的把附加参数长度加在命令长度上。

　　考虑到标签识别应用中可能出现一批相同种类的商品，也可能出现不同种类的商品。这些不同情况下标签中随机位数是不同的。使用均匀分布随机函数产生随机位数为36、60、88的3种情况，分别进行仿真。

　　前面提及的标签预处理算法对本文提出的二叉树形搜索防碰撞算法也是有效的，因为改预处理可以使得标签在识别过程中跳过那些数值相同的位数，相当于使标签ID的有效长度缩短，冲突位更加紧凑，这大大减少了二叉树形搜索算法中出现REQ_LONG命令的次数，会使得平均比特数更少，使算法性能提高。实验中也增加了与预处理后的二叉树形搜索算法的比较。实验结果如图3、4、5所示。

　　由图示实验结果可以得出：

　　(1) 二叉树形搜索防碰撞算法是收敛的，算法性能曲线随着标签总数的增加最终趋于平缓。标签总数足够大时，识别标签的平均比特数趋于一个稳定的值，这个值随着标签ID中随机位数的减少有变小的趋势，原因在于对于相同的标签总数，随机位数越少则会使标签ID的冲突位更加紧凑，可以更大的体现出二叉树形搜索算法的有效性能。

　　(2) 二叉树形搜索防碰撞算法的性能相比动态二进制搜索防碰撞算法有了很大的改进，在标签总数N大于10时可以很明显看出两算法的性能差距。由于二叉树形搜索算法中一次收发中所需传送的比特数相比动态二进制搜索算法急骤减少，从而使二叉树形搜索算法识别过程的平均比特数大大减少，算法性能提高。

　　(3) 标签预处理算法对于二叉树形搜索算法是有效的。它能在真正开始标签识别过程前去除ID中不冲突的位置，这会使冲突的位置紧凑，有利于二叉树形搜索算法中少出现REQ_LONG问答，更好地发挥算法优势。由以上各图可看出使用预处理的二叉树形搜索算法平均比特数有了更进一步的减少，表现出更佳的性能。

　　4 结束语

　　本文的二叉树形搜索防碰撞算法相比ISO/IEC14443A标准中的动态二进制搜索算法大大减少了识别每个标签的平均比特数，也即是在最小时延和平均功耗方面比标准算法有了明显的改进。尤其是在结合标签预处理算法后，该算法的性能更得到了进一步的提高。标签ID冲突位的分布对该算法性能有着一定的影响，冲突位分布越紧凑，算法在识别过程中的平均比特数越少，性能越好。该算法采用二叉树型的搜索路径对识别范围内的标签进行快速识别，把平均每次标签与读写器的数据传输所需比特数降低到了最少，且不随标签ID的长度变化而影响。因此，该算法对于RFID防碰撞技术有着极其重要的意义。

　　参考文献：

　　[1\] 余松森，詹宜巨，彭卫东.返回式索引的二进制树形搜索反碰撞算法及其实现\[J\].计算机工程与应用,2004(16).

　　[2\] DONG-HER SHIH,PO-LING SUN,DAVID C. YEN. Taxonomy and survey of RFID anti-collision protocols\[J\].Computer Coummunications，2006(11).

　　[3\] FINKENZELLER K, RFID-HANDBOOK, Fundamentals and applications in contactless smart cards identification(Sencend Edition)\[M\].Wiley & Sons LTD,2003.

　　[4\] 姜丽芬，卢桂章，辛运帷.射频识别系统中的防碰撞算法研究\[J\].计算机工程与应用,2007(15).

　　[5\] ISO/IEC 14443-3 Identification cards contactless integrated circuit(s) cards-proximity cards part 3: initialization and anti-collision\[S\].2003.

　　[6\] JI HWAN CHOI,DONGWOOK LEE,YOUNGWOO YOUN.Scanning-based pre-processing for enhanced RFID tag anti-collision protocols\[C\].ISCIT，2006.

　　[7\] F ZHOU,D JING,C HUANG ，et al.Optimize the Power Consumption of Passive Electronic Tags for Anti-collision Schemes\[C\].The 5th ASICON, Oct,2003 Beijing, China.

　　[7\] FENG ZHOU,DAWEI JIN,CHENLING HUANG,MIN HAO.Optimize the power consumption of passive electronic tags for anti-collision schemes\[C\].Beijing, China: ASIC, 2003(2).