RFID系统中一种改良的防冲突算法的研究

引言 

　　无线射频识别（RFID）技术是一种非接触式的自动识别技术，其原理是利用射频信号的传输特性，对贴有标签的目标加以识别并获取相关信息。它成功地将射频识别技术和IC卡技术结合起来，解决了无源和免接触信号获取这一难题。由于目前对识别距离的要求越来越高，高频系统的研究已经成为一个热点。但在提供远距离多目标识别优点的同时，多个标签同时应答一个阅读器，或者多个阅读器同时对一个标签进行识别的数据冲突的情况也凸显出来，本文中，将重点讨论一种针对于UHF频段的改良动态二进制搜索算法，用于解决这种冲突问题。

1 目前基本的防冲突方法

　　RFID系统的防冲突问题属于多址通信问题，在目前的射频识别系统中，主要是采用TDMA技术，使每个电子标签在单独的某个时隙内占用信道与读卡器进行通信，防止碰撞的产生，数据能够准确地在读卡器和电子标签之间进行传输。实际的射频识别系统常用的防冲突算法主要有ALOHA算法、时隙ALOHA算法、二进制搜索算法和动态二进制搜索算法等。由于二进制搜索算法对于标签硬件要求较低，实现灵活等特点，下面主要介绍基于二进制搜索算法的一些防冲突算法及改良算法。

　　2 基于二进制搜索算法改良的防冲突算法

　　2．1 二进制搜索算法 

　　实际应用中，使用较多的防冲突算法是“二进制搜索算法”，二进制搜索算法系统是由在一个读写器和多个电子标签之间规定的相互作用顺序构成的，从同时进入读卡器作用范围的标签中选出一个电子标签进行通信。实现二进制算法需要三个必要条件。

　　A 读卡器能定位出在读卡器中数据碰撞比特的准确位置，这需要使用Manchester编码。
　　B 标识电子标签身份的序列号必须是唯一的。
　　C 需要一组指令，这组指令由读卡器和标签交互之用。

　　二进制搜索算法的工作流程如下：

　　①当射频卡进入读写器的工作范围时，读写器使用REQUEST（N）命令发出一个最大序列号让所有射频卡响应；同一时刻开始传输它们各自的序列号到读写器。
　　②读写器对比射频卡响应的序列号的相同位数上的数，如果出现不一致的现象，根据Manchester编码规则，在此位上的混合电平无法判断—既不是上升沿也不是下降沿，由此可判断出此Bit位有碰撞。
　　③当确定有碰撞后，把不一致比特位的数从最高位到次低次依次置1，再发送序列号，即依次排除序列号大的标签，直到读写器对比射频卡响应的序列号的相同位数上的数完全一致时，说明无碰撞。这时使用选择命令(SELECT)就选出了一个唯一的标签。
　　④选出唯一的标签后，对该标签进行数据交换，然后使用去选择命令(UNSELECT)使该卡进入“无声”状态，则在读出器范围也不再响应(移动该范围后移入可再次响应)。
　　⑤重复步骤①，选择剩余的射频卡进行数据交换。多次循环后即可完成所有射频卡的读取。

　　2．2 动态二进制搜索算法

    在二进制搜索法中，电子标签的序列号总是一次次完整地传输，然而，在实际应用中，电子标签的序列号一般在8个字节以上，仅仅为了选择一个单独的电子标签就不得不传输大量的数据。仔细的研究读卡器和单个电子标签之间的数据流可以得出以下结论：

　　用X表示序列号的最高位置，当判断出碰撞位P后，读卡器在REQUEST（请求）命令时，只需发送要搜索的序列号的已知部分（P—X）作为搜索的依据就可以了，所有在（P—X）位中的序列号与搜索依据相符的电子标签传输它们的序列号的剩余部分（0—P）即可。根据这样的思想，把数据分成两部分，收发双方各自传送其中一部分数据，可把传输的数据量减小到一半，达到缩短传送时间的目的。

　　2．3 改良的动态二进制搜索算法 

    从以上介绍中可以看出，无论是二进制搜索算法还是动态二进制搜索算法，在发送请求命令给电子标签时，其参数传递的都是标签的序列号，沿着动态二进制搜索算法改进的思路：可以再减少读卡器每次传输的时间，不直接传送标签的序列号或部分序列号，而是传送其序列号的位数。论文检测。同时注意到每次排除一部分标签后，当下次读卡器再次请求时，被排除在外的标签同样还会做出响应，这些响应是已知资源的浪费，我们可以设计一组休眠命令（REST），使每次排除在外的标签处于休眠状态，下次不再响应。直到一轮搜索结束后再发送唤醒命令（WAKE），使休眠命令的标签再次参与新的搜索。

　　本改良方案主要设计了一组新的用于读卡器与卡交互的命令来实现上述目的，下面对这些命令进行说明：

　　REQUEST(N) – 请求命令。该命令带一个参数N，N表示标签序列号的位数。当标签收到此命令后，将小于等于N位的序列号回传给读卡器。 
　　REST(P) – 休眠命令。该命令带有一个参数P，P表示以0为基位的卡的序列号的第P位。当标签收到此命令后，如果其序列号第P位为0，则将自身置为休眠状态，即不再对REQUEST命令作出响应。
　　WAKE – 唤醒命令。该命令没有参数，当处于休眠状态的标签收到此命令后，将自身设置为正常等待状态。
　　SELECT（S）选择命令。该命令带有一个参数S，S表示具体的一个卡的序列号。当序列号为S的标签收到此命令后，即被选择。
　　 　　RD—DATA（）读卡命令。该命令没有参数，当被选择的标签收到此命令后可以通信。
　　UNSELECT（）去选择命令。该命令没有参数，当通信完成后，将标签去活。

　　 该改良算法的工作流程如下：
　　①读卡器发送REQUEST命令，参数N为序列号的位数。第一次发送序列号的最高位数，这时读卡器内所有的标签都满足条件，将自身的序列号回传给读卡器。
　　 ② 如果读卡器判断出第P位发生冲突时，发送REST（P）命令，序列号第P位为0的标签处于休眠状态。读卡器再次发送REQUEST命令，参数为P-1，这时读卡器内排除处休眠态的其它标签回传其序列号。当读卡器判断出第P位发生冲突时，则再次发送REST命令，如果没有冲突，则发送SELECT命令选择唯一的一个标签进行通信。
　　 ③通信完成后发送WAKE命令，唤醒处于休眠状态的标签，重复1，2操作，直到所有的标签被识别完。

　　2．4 改良的动态二进制搜索算法的仿真分析

    ●可行性分析：该改良算法经过了C++语言仿真，为简化起见，在仿真过程中，我们假设标签序列号为8位。为了模拟3个标签同时进入读卡器的情况，我们在主线程中新建了3个标签线程来实现这种同步，标签向读卡器发送其序列号的过程由3个标签线程来完成，读卡器发送的一系列命令由主线程来实现，由仿真结果（仿真结果图）可以看出，这种改良的动态二进制搜索算法可以实现。

　　●执行效率分析：
　　由二进制搜索算法的工作流程可知，防碰撞处理是在确认有碰撞的情况下，根据高低位不断降值的序列号一次次进行筛选出某一射频卡，从而可知射频卡的数量越多，防碰撞执行时间就将越长。平均搜索的次数N 可用下式来计算：
　　N=Integ(logM/log2) + 1 (1)
　　式中：M是读卡器作用范围内标签的数目；Integ 表示数值取整。序列号的位数越多，每次传送的时间加长，数据传送的时间就会增大。如每次都传输完整的序列号，每次时间为T，则用于传输序列号的通信时间为：
　　t=T×N (2)
　　动态二进制搜索算法在标签序列号位数不变的情况下，把数据分成两部分，收发双方各自传送其中一部分数据，可把传输的数据量减小到一半，其较二进制搜索算法而言效率提高了50%。
　　其用于传输序列号的通信时间为：
　　T=1/2×T×N (3)
　　 改良型动态二进制搜索算法每次请求时不传送序列号，而是传送序列号的位数，其代价是每排除一次碰撞就多传送了一个休眠指令，其平均搜索次数N可用下式来计算：
　　N=Integ(logM/log2)+ Integ(logM/log2) = 2*Integ(logM/log2)； (4)
　　其用于传输序列号的通信时间为：
　　T=1/SER×T×N （SER为序列号位数）(5)
　　由此可见，当序列号位数SER大于2时，其效率就高于动态二进制算法，SER越大，改良型算法提高的效率越高。

　　● 安全性分析：
　　由于读卡器不直接发送标签的序列号，而是发送序列号的位数，所以对比二进制及动态二进制搜索算法有较好的安全性。
　　由于本算法只是在原理层面上仿真研究，没有考虑到现实中不可避免的躁声等因素，这方面的研究还须日后讨论。