RFID多标签识别防碰撞算法的研究与分析

陈鸿俊

（四川水利职业技术学院）

RFID多标签识别防碰撞算法的研究与分析

陈鸿俊

（四川水利职业技术学院）

无线射频识别技术是一种非接触的自动识别技术，具有识别距离远、穿透能力强、多物体识别等优点，现已广泛应用于自动化、交通运输、控制管理、产品服务、证件防伪等领域。RFID 系统由于信号在无线信道中相互干扰，就会发生冲突或碰撞，致使标签识别或数据采集失败，这就需要建立有效的防碰撞机制，即防碰撞算法或防碰撞协议，来协调标签与阅读器间的通信。

RFID;防碰撞算法;二叉树搜索;ALOHA

1 无线射频识别技术

无线射频识别技术 属于新近出现的先进无线通信技术，能够在无线电讯号下，对目标进行特定性识别，并对目标数据进行自动读写。这种技术在上世纪末开始兴起，技术最大的特点是非接触性。这种RFID信号可以使电磁场中的无线电频率有效调节，因此在拥有此频率的电磁场中，能够将信息数据通过粘贴的标签传送到相应阅读器，从而实现对物品的自动识别及追踪。某些标签在识别过程中可以在阅读器发出的电磁场中获得能量，不需要额外的电池支持；还有些标签本身就包含电源，能够自主进行无线电信号的发送。一般来说，阅读器在数米之内所接收到的电子标签存储信息都能进行识别。

目前常用的自动识别技术中，条码技术和磁卡技术所涉及设备成本较低、操作简单、数据采集速度快、可靠性高灵活实用，只是数据存储量不大，抗磨损性差。IC卡数据存储量大，安全保密性好，每次修改都需要输入密码，重量不大，便于携带，但是使用寿命也不高。而当前的射频卡操作便捷，能远程操作，可以穿透很厚障碍，不会产生机械磨损，拥有较长使用寿命。同时射频识别还有良好的抗干扰能力，耐久性强，对环境要求不高，在各种环境下都能够正常工作，且射频识别对视线范围没有局限，在识别的有效距离上远高于当前的光学系统。由于无线射频识别技术能轻松的免除在物体跟踪过程中由于人为干预出现的错误，因此该技术能大大简化在物流、运输及商品供应链中的产品跟踪管理，能快速、有效地满足当前信息处理量的不断增长的需求。在物流行业高速发展的今天，该项技术正以其独特的优势，成为大家所关注的热点之一。

2 无线射频识别技术的发展

RFID技术最早使用在第二次世界大战中，在这场战役中，各国的空军就是用此技术来实现彼此间的相互识别的。1948年奠定了RFID技术的理论基础；1950年以后各国对RFID技术开始通过实验室研究进行有效探索；1960年之后，在各种研究基础上，RFID技术已经得到进一步发展，人们通过设计一些诸如电子商品监视设备这样的简单商用RFID系统，将此技术做了程序上的应用尝试；1980年后，RFID技术在各种应用系统中尝试应用，使RFID技术在各个行业得到了开发及应用；过去十年中，人们对产品标准化不断关注，并且伴随科技经济的飞速发展，RFID产品的种类更为丰富齐全，各种类型的标签技术应运而生，有效地降低了电子标签的成本。

RFID系统有三部分组成，分别为：阅读器（ Reader）、标签（ Tag）及数据处理系统。标签可以对所标识物品的身份和属性信息进行有效存储，阅读器作为信息采集终端，利用射频信号对标签进行识别，并与数据处理系统进行通信。鉴于阅读器同所有待识别的标签间的沟通是通过无线信道所进行的，当多个待识别标签共同与阅读器通信，此时信号之间会互相碰撞，标签间信号出现冲突，不能被准确识别，通信数据传送失败，这就形成了标签冲突( tag collision)。这时就需要我们采用适当方法对多标签识别冲突有效解决，一般我们是通过防碰撞算法来解决这类问题的。而这种防碰撞算法当前已经成为多标签识别中最主要的一个研究热点。在应用中我们多通过防碰撞速度，识别准确率，信道利用率高低，技术成本及安全性，还有技术应用中的稳定性几个指标来判断防碰撞算法的优劣。

3 国内外关于防碰撞算法的研究

RFID系统中所使用的防碰撞方法主要有4种，分别是：TDMA（时分多路法）、FDMA（频分多路法）、SDMA（空分多路法）、及CDMA（码分多路法）。其中时分多路方法在RFID系统中应用最为广泛，而二进制树搜索算法(Binary Tree-Scanning)还有ALOHA算法则是RFID系统中使用频率最多的算法。

近年来，我国国内关于RFID 技术及防碰撞算法的研究也如雨后春笋般展开。很多学者专家对防碰撞算法依据使用环境进行了改良，让RFID系统在实际环境中的应用效率大大提高。在文献[5]中，研究者将矩阵搜索算法应用于生产领域，这是防碰撞算法在生产领域的有效改良。这种算法可以对多种标签的数据请求信息所形成的信息数据进行同时响应，避免信息碰撞矩阵的出现，使二叉树搜索算法中逐位搜索的方法得到了改善，有效提高了工作效率。并且这种算法下，依据碰撞堆栈理念，能够对搜索途径自发动态调整，这样就能够使标签碰撞次数还有传输中空闲时隙数有效减少，使搜索效率大大提高[5]。在文献[6]中，研究者在防碰撞算应用中提出要降低空时隙的开销，并据此制定出专门算法。这种算法可以对命令帧中空时隙的位置在识别前先行扫描，对标签数量进行估算，并据此动态调整命令帧的长度，以减少空时隙的时间浪费，达到提高系统读取效率的目的。

4 防碰撞算法存在问题分析

目前RFID 防碰撞算法主要还存在如下一些问题：

（1）基于ALOHA 的防碰撞算法采用随机申请时隙的方法，不能保证标签的完全识别，不能避免标签饥饿（tag starvation）现象，即存在标签长期或一直不能被成功识别的现象，而且随着待识别标签数量的增加，算法性能急剧下降。

（2）这些算法不能消除识别过程中的空闲周期或时隙（idle cycle），即这些周期或时隙中没有任何标签响应阅读器的质询（Query）,造成不必要的时空开销和能量消耗，影响标签的识别速度。

（3）算法识别效率较低，ISO/IEC 18000 系列标准推荐使用的QT、BS、S-ALOHA 和DS-ALOHA 等算法的识别效率一般情况下在34%左右，众多新算法或改进算法性能也低于50%，且算法较为复杂，难以付诸实际应用，因此，不能满足现实应用的需求。

（4）算法稳定性较差，随着待识别标签的数量和标签编号的分布情况不同，算法的识别性能差异很多大，不便于计算完成一批标签识别的准确时间，这给RFID 在流水生产或实时数据采集等方面的应用造成困难。

（5）算法仅考虑或假设标签编号成均匀分布状态，而在实际应用中其它分布状况也大量存在，如集装箱码头、大型货舱等场合，均需要对同一厂家或类型的批量商品进行快速准确的识别检测，而这时的标签编号通常为连续分布方式。

5 防碰撞算法的发展趋势和展望

标签冲突是RFID 应用系统中的关键问题之一。通过对ALOHA 法和二进制树搜索算法以及在此基础上发展起来的其他一些比较重要的防碰撞算法的分析比较, 可以看出:

(1) ALOHA 算法实现较简单, 但是存在错误判决问题, 其信道利用率最大为36%, 在标签数目不大的场合, 可以用到时隙ALOHA 法和DFSA 算法。

(2) 二进制树算法识别率高, 信道利用率可达43%, 不存在错误判别问题, 适用于标签数目较大的场合。

(3) ALOHA 法只适于中低频被动式只读电子标签, 如校园一卡通; 而高频和微波系统则多用二进制搜索。但是采用二进制树算法时延长, 泄露的信息较多, 安全性较差。在设计系统时要根据系统的应用场合选择合适的防冲突算法。

考虑到两类算法各具优点, 有人考虑将二者结合起来得出新算法;也有人提出采用码分多址和空分多址的方法,通过为每个标签分配不同的PN 码来避免冲突, 空分多址通常是将标签定位达到隔离和识别的目的。这种方法可通过改变读写器的阅读范围或使用智能天线来实现。这两种方法能大大提高RFID 系统的防冲突能力, 但系统设计较为复杂, 标签的成本较高, 其主要适于超高频和微波等宽带应用场景。以上各种方法都有待进一步研究。

从RFID 应用的角度来看, 目前的防碰撞算法的识别率、识别速度、信道利用率都有待提高, 识别过程较复杂, 对安全和个人隐私等问题考虑不周, 这些问题都有待进一步研究和改进, 以适应高速运动、多目标识别复杂系统的应用。

[1] Rao,K.V.S. An overview of backscattered radio frequency identification system(RFID)[J]．Microwave Conference,1999,3: 746—749.

[2] K.Finkenzeller. RFID Handbook[M]. 第四版.北京:北京大学出版社, 2 0 0 3. 206-219.

[3] 高乐. RFID技术中的防碰撞算法研究[D]. 成都:电子科技大学，2006.2

[4] 陈飞宇. 基于动态二进制RFID防碰撞算法的改进[D]. 上海:上海交通大学, 2011.6.

[5] 丁治国,郭立,刘琦. 一种基于搜索矩阵的自适应防碰撞算法[J]. 模式识别与人工智能,2008,21(4): 476-481.

[6] 王中祥,王俊宇,刘丹,闵昊. 一种降低空时隙开销的RFID防碰撞算法[J]. 通信学报,2009,30(9): 1-6.

[7] M.A. Bonuccelli, F. Lonetti and F. Martelli, Instant collision resolution for tagidentification in RFID networks, Elsevier, Ad Hoc Networks, vol.5, no.8, pp.1220-1232,2007.

[8] J.Choi and W.Lee, Comparative evaluation of probabilistic and deterministic taganti-collision protocols for RFID networks, EUC Workshops, pp.538-549, 2007.

[9] D.H.Shih, P.L.Sun, D.C.Yen and S.M.Huang, “Taxonomy and survey of RFID anti-collision protocols,” Computer Communications, vol. 29, no.11, pp.2150-2166,July 2006

[10] 聂赛如,刘有源. RFID 防碰撞算法研究现状与发展趋势综述. 技术与方法,2008.3

陈鸿俊（1981-），四川成都人，四川水利职业技术学院，讲师，主要从事计算机应用技术研究。

Research and analysis of RFID multi tag identification anti collision algorithm

Chen Hongjun
(Sichuan Water Conservancy vocational College)

Wireless radio frequency identification technology is a non-contact automatic identification technology,which has many advantages,such as high identification distance,penetrating ability,multi object recognition,etc.,has been widely used in the field of automation,transportation, control management,product service,document security and other fields. Because of the interference of the signal in wireless channel,the RFID system has a collision or collision, which leads to the failure of tag identification or data acquisition,which requires the establishment of an effective collision avoidance mechanism,i.e.,anti collision algorithm or anti collision protocol,to coordinate the communication between the tag and the reader.At present,the research of RFID anti collision algorithm is mainly focused on the Aloha slot collision avoidance algorithm and the two fork tree search anti collision algorithm. However, the Aloha time slot collision avoidance algorithm has the phenomenon that a tag is not recognized. Two binary tree search algorithm can avoid this problem, but when the number of tags is large,the identification period is long, which affects the efficiency of RFID reader.

RFID;anti collision algorithm;two fork tree search;ALOHA

项目编号是:四川科技厅项目编号2012GZ0112。

目前，RFID防碰撞算法的研究主要集中在Aloha时隙防碰撞算法和二叉树搜索防碰撞算法。但Aloha时隙防碰撞算法存在某个标签始终无法被识别的现象；二叉树搜索算法可以避免这个问题，但当标签数量比较大时，识别周期长，影响了RFID读写器的效率。