RFID二进制搜索法防碰撞的实现

摘要 探索一种解决RFID系统中碰撞问题的方法，具体讨论防碰撞算法中的二进制搜索算法及其改进方法一一动态二进制搜索算法。动态二进制搜索算法考虑的是在UID位数不变的情况下，把数据分成两部分，收发双方各自传送其中一部分数据，可把传输的数据量减小到一半，缩短传送时间，提高RFID系统的效率。
关键词 射频识剐 读写器射频卡碰撞二进制搜索法

1 RFID技术概述
    射频识别技术RFID(Radio Frequeilcy Identification)是一种非接触式的自动识别技术。目前的RFID系统有很多工作频段：低频、高频和超高频段。工作原理也不尽相同，有的是利用近场的电磁感应(所以有人把射频卡称为“感应卡”)}有的是利用电磁波发射来实现非接触双向通信，以达到识别目的并交换数据。RFID技术由于可实现非接触目标识别、多目标识别和运动目标识别，具有防水、防磁、耐高温、使用寿命长、读取距离大、标签上数据可以加密、存储数据容量更大以及存储信息更改自如等优点，广泛应用于工业自动化、商业自动化和交通运输控制管理等众多领域。

    RFID系统，如图1所示，主要由射频卡(又称为“电子标签”)、读写器和计算机网络组成。其中最重要的是读写器(Reader Writer Device)和射频卡(Transponder)。读写器和射频卡之间采用无线通信方式，因此它们都有无线收发模块及天线(或感应线圈)。射频卡芯片上有内存部分用来存储序列号(识别号码)或其他数据。

2 防碰撞方法综述
    早期的系统中，1次只能读／写1个射频卡。射频卡之间要保持一定距离，确保一次只有一个卡在读写区域内，应用起来很不方便。很多时候不可避免地会出现多个射频卡进入识别区域时信号互相干扰的情况，即碰撞。具有防碰撞性能的系统可以同时识别进人识别距离的所有射频卡，其并行工作方式大大提高了系统的效率。

2．1 防碰撞方法的设计要求
    防碰撞技术主要解决RFID系统一次可以完成对多个射频卡的识别问题。假设同时进入读写器天线区域的射频卡共有n个，防碰撞设计要求如下：
    ①当1≤n≤N时，其中N为读写器一次可识别射频卡数量的上限，则在碰撞发生(n>1)的情况下，能识别n个射频卡并依次与它们完成通信。
    ②平均响应时闻τ足够短，τ为某一时段内完成通信的所有射频卡在系统内的平均停留时间。τ与算法有关，允许τ≤τ0。τ0为不同应用中所允许的最大时延。

2.2 RFID中防碰撞的基本原理
    由于射频卡含有可被识别的唯一信息(序列号)，RFID系统的目的就是要读出这些信息。如果只有一个射频卡位于阅读器的可读范围内，则无需其他的命令形式即可直接进行阅读。如果有多个射频卡同时位于一个阅读器的可读范围内，则射频卡的应答信号就会相互干扰形成所谓的数据冲突，从而造成阅读器和射频卡之间的通信失败。为了防止这些冲突的产生，RFID系统中需要设置一定的相关命令，解决冲突问题，这些命令被称为“防冲突命令或算法(anti-collision algorithms)”。

    在无线电技术中，实现防碰撞基本上有4种不同的方法：时分多路法、频分多路法、空分多路法以及码分多路法。时分多路(TDMA)法是把整个可供使用的通路容量按时间分配给多个用户的技术。TDMA在数字移动无线电系统中得到广泛应用。考虑到RFID系统通信形式、功耗、系统的复杂性及成本等因素，选择TCMA来实现射频识别系统的防碰撞机制是最普遍的方法。

    TDMA法通常被分为两大类：读写器控制防碰撞法和射频卡控制防碰撞法。
    读写器控制防碰撞法是以读写器为主动控制器，进入射频场的所有射频卡同时由读写器进行控制和检查。阅读器依据射频卡的ID号(Identification number)首先向射频卡发射不同的询问信号或指令，阅读器依据选举方法或二进制树寻找方法，在同一时间内总是建立起一个通信关系，并且可以快速地按时间顺序操作射频卡。

    射频卡控制法以射频卡为主控制器，读写器对数据传输没有控制。读写器发出指令后，由射频卡依据自己的ID号(每个射频卡的ID号是唯一的)随机产生应答时间。这时阅读器发送信息如果有冲突，则射频卡要等到下一个时隙到来时再重新产生响应时间(即自动排队)，使射频卡在不同的时间段发回数据，读写器只是被动的接收数据。若有两张以上的射频卡同时反应，则读写器认为该数据无效，会重发指令，直到识别出场中的所有射频卡。IS015693标准就采用了这种时隙方法。

    本文主要针对射频卡控制法，即基于TDMA的二进制搜索防碰撞算法进行分析和研究，并分别在性能上作分析。二进制搜索算法的思路是：通过定义读写器与多个射频卡之间一组规定的指令序列，从中选出一张卡，并完成二者的数据交换。

3 二进制搜索算法
    二进制搜索算法的方法类似于在天平中采用的逐次比较方法。通过多次比较，不断筛选出不同的序列号，时分复用地进行读写器和射频卡之问的信号交换，以一个独特的序列号来识别射频卡为基础。为了从一组射频卡中选择其中之一，读写器发出一个请求命令有意识地将射频卡序列号传输时的数据碰撞引导到读写器上，即通过读写器判断是否有碰撞发生。如果有碰撞，则缩小范围进行进一步的搜索。

    二进制搜索算法由一个读写器和多个射频卡之间规定的一组命令和应答规则构成，目的在于从多卡中选出任一个实现数据通信。

    该算法有3个关键要素：①选用适当的基带编码(易于识别碰撞)。②利用射频卡卡序列号唯一的特性。③设计一组有效的指令规则，高效、迅速地实现选卡。

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

3.2 防碰撞指令规则
    典型指令规则：
    ①REQuEST——请求(序列号)。此命令发送一序列号作为参数给射频卡。应答规则是，射频卡把自己的序列号与接收到的序列号比较，如果自身序列号小于或等于REQUEST指令序列号参数，则此射频卡回送其序列号给读写器。这样可以缩小预选的射频卡的范围；如果大于，则不响应。
    ②SELECT——选择(序列号)。用某个(事先确定的)序列号作为参数发送给射频卡。具有相同序列号的射频卡将以此作为执行其他命令(例如读出和写入数据)的切入开关，即选择这个射频卡。具有其他序列号的射频卡只对REQUEST命令应答。
    ③READ-DATA——读出数据。选中的射频卡将存储的数据发送给读写器。
    ④UNSELECT ——去选择。取消一个事先选中的射频卡，射频卡进入“无声”状态，在这种状态下射频卡完全是非激活的，对收到的REQUEST命令不作应答。为了重新话化射频卡，必须先将射频卡移出读写器的作用范围再进入，以实行复位。

3.3 工作流程
    在二进制搜索算法中，要能够检测出多张卡的存在，卡片的返回数据必须具有唯一性，且卡片在传输其UID(Ubiquitous IDentifications，身份识别标签)时必须准确、同步。这样终端才能在位级上检测出多张卡片的存在，这是防碰撞检测的关键。

    射频卡工作的特点是，当读到读写器发出的序列号大于自身序列号时，则对系统作出响应。根据这一特点，二进制搜索算法的工作流程是：

    ①射频卡进入读写器的工作范围，读写器发出一个最大序列号让所有射频卡响应；同一时刻开始传输它们的序列号到读写器的接收模块。
    ②读写器对比射频卡响应的序列号的相同位数上的数，如果出现不一致的现象(即有的序列号该位为0，而有的序列号该位为1)，则可判断出有碰撞。
    ③确定有碰撞后，把有不一致位的数从最高位到次低次依次置O再输出系列号，即依次排除序列号大的数，至读写器对比射频卡响应的序列号的相同位数上的数完全一致时，说明无碰撞。这时就选出序列号最小的数。
    ④选出序列号最小的数后，对该}进行数据交换，然后使该卡进入“无声”状态，则在读出器范围也不再响应(移动该范围后移入可再次响应)。
    ⑤重复流程①，选出序列号倒数第二的射频卡进行数据交换。
    ⑥多次循环后可完成所有射频卡的读取。

4 二进制搜索算法的改进分析
4．1 二进制搜索算法的传输时间
    由二进制搜索算法的工作流程可知，防碰撞处理是在确认有碰撞的情况下，根据高低位不断降值的序列号一次次进行筛选出某一射频卡，从而可知射频卡的数量越多，防碰撞执行时间就将越长。搜索的次数N可用下式来计算： 
    N=Integ(1Og M/log2)+1
    式中：M是终端作用范围内射频卡片数日；Integ表示数值取整。

    UID的位数越多(如ICODE达64位)，每次传送的时间加长，数据传送的时间就会增大。如每次都传输完整的UID，每次时间为T，则用于传输UID的通信时间为：
    t=T×N
    即终端作用范围内射频卡片数越多，UID位数越多，传送时间越长，总的防碰撞执行时问肯定也就越长。

4.2 动态二进制搜索算法
    动态二进制搜索算法考虑的是在UID位数不变的情况下，尽量减少传输的数据量，使传送时间缩短，提高RFID系统的效率。其改进思路是把数据分成两部分，收发双方各自传送其中一部分数据，可把传输的数据量减小到一半，达到缩短传送时间的目的。

    通常序列号的规模在8字节以上。为选择一个单独的射频卡，每次都不得不传输大量的数据，效率非常低。根据二进制搜索算法的思路进行改良，可以减少每次传送的位数，也可缩短传送的时间，从而缩短防碰撞执行时间。下面分析动态二进制搜索算法的工作过程。在例子中，射频卡有3张，序列号分别是：卡1，11010111；卡2，11010101；卡3，11111101。

(1)动态二进制搜索算法的工作步骤
    ①读写器第一次发出一个完整的UID位数码N，每个位上的码全为l，让所有射频卡都发回响应。
    ②读写器判断有碰撞的最高位数X，把该位置O。然后传输N～X位的数据后即中断传输。射频卡接到这些数据后马上响应，回传的信号位是X一1～1。即读写器和射频卡以最高碰撞位为界分别传送前后信号。传递的总数据量可减小一半。
    ③读写器检测第二次返回的最高碰撞位数X’是否小于前一次检测回传的次高碰撞位数。若不是，则直接把该位置“O”；若是，则要把前一次检测的次高位也填“O”。然后向射频卡发出信号。发出信号的位数为N～X’，射频卡接收到信号这一级信号出现小于或等于相应数据时后马上响应，回传的信号只是序列号中最高碰撞位后的数。即X—l～l位。若射频卡返回信号表示无碰撞，则对该序列号的射频卡进行读／写处理，然后使其进入“不响应状态”。
    ④重复步骤①，多次重复后可完成射频卡的交换数据工作。

(2)动态二进制搜索算法与工作步骤相对应的示例
    ①例如N=8，传送数据为11111111b。最高位为第8位，最低位为l位。根据响应可判断第6位、第4位、第2位有碰撞。
    ②X=6，即第6位有碰撞，则传送数据变为11011111b。传送时，只传送前面3位数11Ob。这时卡1和卡2响应，其序列号的前3位与射频卡相同，不回传，只回传各自的后5位数据。卡1为lOlllb，卡2为10101b。可判断第2位有碰撞。
    ③X’=2，根据要求第4位也要补零，则传送数据变为110101O1b，传送时只传送110101Ob。这时只有卡2响应，并返回1b，表明无碰撞。读写器选中卡2进行数据交换，读／写完毕后卡2进行“休眠”。
    ④重复步骤①，按序可读／写卡1、卡3。
    在动态二进制搜索算法的工作过程中，要注意通过附加参数把有效位的编号发送到射频卡，从而保证每次响应的位置是正确的。

5 总 结
    防碰撞是RFID技术中的一项重要技术。二进制搜索算法是基于TDMA的一种适用于阅读区内射频卡数量不多的情况。根据这一算法进行编程，结构比较简单，容易实现防碰撞功能。采用动态二进制搜索方法可提高执行防碰撞的速度，实现高效率的控制。