新型的RFID混合防碰撞算法

　　射频识别RFID(Radio Frequency Identification)是一种非接触式自动识别技术，它通过无线射频方式进行非接触双向数据通信，能够自动识别目标对象并获取相关数据，无需人工接触，能够实现自动化且不易损坏。可识别高速运动物体,并可同时识别多个射频标签，操作快捷方便。射频识别技术被广泛应用于工业自动化、商业自动化、交通运输控制管理等众多领域。RFID系统一般包含电子标签，读写器(RFID天线和RFID控制器)和计算机数据管理系统三部分。RFID系统工作时，在读写器的作用范围内可能存在多个标签，这些标签在同时响应读写器的查询时会出现数据碰撞，导致读写器无法正确读出标签数据，这就是RFID系统中的碰撞问题。因此，用于解决读写器作用范围内多标签识别问题的防碰撞算法已成为该领域研究的热点之一。

　　目前比较经典的防碰撞算法主要有基于Aloha的防碰撞算法和二进制搜索BS(Binary Search)算法[1-2]。基于Aloha的防碰撞算法包括帧时隙Aloha FSA(Frame Slotted Aloha)算法和动态帧时隙DFSA(Dynamic Frame Slotted Aloha)算法[3-4]及其改进算法。该算法操作简便，便于实际应用。但是由于该算法的时隙是随机分配的，当大量标签并存时，帧冲突严重，存在“标签饥饿”问题。而基于二进制搜索算法，包括动态二进制搜索DBS(Dynamic Binary search)算法[1]、自适应二叉树搜索(Adaptive Binary Splitting)算法[5]和查询树搜索算法[6]QT(Query Tree)等。这类算法的电路实现比Aloha算法复杂，增加了不必要的识别时延。鉴于此，本文提出了新型的RFID混合防碰撞算法。该算法结合帧时隙Aloha算法(FSA)和动态二进制搜索算法(DBS)，大大提高了系统的识别效率。

　　1 新型的RFID混合防碰撞算法

　　本文提出的RFID混合防碰撞算法是基于两方面的目的：(1)通过FSA算法在第一个阶段来减少碰撞发生的次数; (2)通过DBS算法在第二个阶段处理发生的碰撞。本算法步骤如下：

　　(1)读写器发送查询指令和帧长N，通过FSA算法对时隙进行查询。如果一帧中某个时隙为成功时隙，可直接读取标签，然后标签进入“休眠”状态;如果为空闲时隙，则不进行任何操作;如果为碰撞时隙，读写器估算出当前的碰撞时隙数Ck。

　　(2)计算Ck/N,如果Ck/N≤?酌(0.5≤?酌≤1)，则发生碰撞的时隙小于帧长的一半。这时处于读写器作用范围内的待识别标签较少，此时这些待识别标签直接采用DBS算法。当Ck/N≤?酌时，则发生的碰撞时隙较多，待识别的标签也较多，此时需要通过比较标签ID的一部分比特位，以限制响应请求命令的标签数。读写器向标签发送比较的开始位，比较位的长度和基准值;标签接收到这些数据后，将自己的部分序列号与规定的比较基准值相比较，如若小于比较基准值，该标签响应读写器，开始采用DBS算法对符合条件的标签进行查询,直到这部分标签全部正确识别并进入休眠状态。进而判断是否仍有标签存在，如有标签可继续重复步骤(1)和步骤(2)直到所有标签全被正确识别;如没有标签，则该算法结束。例如，假设标签的ID号为64 bit的二进制数，比较开始位为第35位,比较位的长度为6，比较基准值为100 000。如果标签的第35位到30位的比特数小于或等于比较基准值，则该标签响应读写器，采用DBS算法;大于比较基准值则标签不响应读写器，处于等待状态等待下一次的查询。如果此时直接采用动态DBS算法，会造成很多碰撞，浪费大量资源。因为DBS在标签相对较少的情况下,可以对标签进行快速高效地识别;而当标签数量较多时,由于初期对标签的选择识别会发生较多碰撞,造成浪费过多的时隙和信道资源，降低了算法的识别效率。图1为该算法的搜索流程图。

　　2 算法性能的分析比较

　　2.1理论性能分析

　　根据混合防碰撞算法描述，可知该算法的步骤(1)通过采用FSA算法识别标签并估算当前碰撞时隙数Ck，然后计算Ck/N，并判断是否直接采用DBS算法。因此混合防碰撞算法时隙数是FSA算法时隙数和DBS算法时隙数之和。

　　通过式(9)可以看出β>0.5，即混合防碰撞算法的识别效率要高于其他两种算法。

　　2.2仿真结果分析

　　假定标签均匀地分布在读写器作用的范围内，已经被识别的标签性能较稳定。图2所示为三种算法在系统的识别效率和查询时隙数这两方面的Matlab仿真比较。从图2可以看出当标签数量超过一定值时，混合防碰撞算法的识别效率要比其他两种算法高，可达61%。而FSA算法的系统识别效率最高达到36.8%，DBS算法的系统识别效率保持在50%左右。图3则表明混合算法优于其他两种算法，该算法能够减少总的查询时隙数，加快标签识别过程。总之，通过各方面的比较，混合防碰撞算法的性能要比其他两种算法更具有优势，系统性能更好。

　　在RFID识别系统中，标签防碰撞是RFID系统中一个关键问题。本文在FSA算法和DBS算法的基础上提出了一种混合防碰撞算法。经一系列理论分析和仿真实验证明该算法明显比FSA算法和DBS算法更具有优势，能够提高系统的识别效率并减少查询的时隙数，使系统达到最好的性能，从而更有效地解决射频识别系统中多目标识别的防碰撞问题。