一种基于二进制码调制的射频识别防碰撞算法

李志坚,肖熠琳

(1.华南理工大学电子与信息学院,广州510640;2.广州市光机电技术研究院,广州510663; 3.广东省现代控制与光机电技术公共实验室,广州510663)

一种基于二进制码调制的射频识别防碰撞算法

李志坚1,3,肖熠琳2

(1.华南理工大学电子与信息学院,广州510640;2.广州市光机电技术研究院,广州510663; 3.广东省现代控制与光机电技术公共实验室,广州510663)

针对射频识别(RFID)标签防碰撞算法识别效率低的问题,提出一种基于二进制码调制的RFID标签防碰撞算法BCMA。对传统多叉树防碰撞算法进行改进,活动标签采用位编码技术把标签ID在多叉数中的位置信息调制到一个2m位的二进制数主控继电器(MCR)上,并把MCR回送给阅读器;阅读器采用位跟踪技术,定位MCR碰撞发生的数位,从而解调出活动标签的分组信息。阅读器对待识别标签的分组是确定性的,进而避免空闲时隙的产生,提高系统识别效率。仿真结果表明,与常见的八叉树算法相比,BCMA算法使系统吞吐率提高168%。

射频识别;防碰撞算法;吞吐率;二进制码调制算法;多叉树;位跟踪技术

1 概述

射频识别(RadioFrequencyIdentification, RFID)是上世纪90年代兴起的一种非接触式自动识别技术。近年来,随着物联网技术的发展,RFID被广泛应用于供应链、卫生保健和公共管理等领域[1-2]。

通常,RFID系统由读写器、标签和天线3个部分组成。在多数应用系统中都会存在多个标签或者多个读写器。系统中所有的标签和读写器共用一个无线频道,当多读写器和多标签同时占用频道通信时,由于信号相互干扰,读写器和标签之间的通信不能正常进行,这样就发生了碰撞。

RFID多标签防碰撞算法主要使读写器正确识别有效通信范围内的多个标签。根据所采用的无线通信多址接入方式,这些算法可以分为时分多址(Time Division Multiple Access,TDMA)类[3-4],码分多址(Code Division Multiple Access,CDMA)类,空分多址(Space Division Multiple Access,SDMA)类和频分多址(Frequency Division Multiple Access, FDMA)类。然而,受RFID系统成本和资源约束,时分多址技术在RFID多标签防碰撞算法中应用最为广泛。基于TDMA技术的防碰撞算法又可分为随机ALOHA算法[5-6]和二进制树[7-8]2类。目前多标签防碰撞算法研究工作主要围绕这2类算法的改进展开[9]。从已发表文献情况来看,随机ALOHA算法易于实现,成本低廉,但是由于算法的时隙是随机分配,因此可能造成某些标签长时间无法识别,亦即存在标签饥饿问题[10-11]。二进制树算法是对待识别标签的反复分组,直到每个组内只含一个标签或者不含标签。这类不存在标签饥饿现象,但是识别时间较长[12]。

本文通过研究二进制编码特征,对基于二进制数的搜索算法进行改进,提出一种基于二进制码调制的RFID多标签防碰撞算法BCMA。

2 二进制树搜索算法

二进制树搜索算法的前提是阅读器能够正确判断碰撞的发生,这就要求系统设计满足2个预设条件:(1)活动标签能够同时响应读写器命令且信道延迟相同,也就是活动标签的反馈信息能够同时到达阅读器的接收端;(2)标签ID采用曼彻斯特编码,读写器能够正确识别碰撞位在标签ID中的位置[13-14]。

在二进制树搜索算法中,阅读器维持一个查询前缀序列堆栈,该堆栈的初始成员为“0”和“1”2个查询前缀序列。二进制树搜索算法流程如下:

Setp 1阅读器从堆栈中取出并广播栈顶查询前缀序列,识别范围内仅ID序列与查询前缀序列匹配的标签回送自己的ID给读写器,其他标签不响应。

Setp 2阅读器检测是否有碰撞发生:若无标签应答,则产生一个空闲时隙,阅读器不做任何操作;若有标签应答,但没有发生碰撞,则产生一个识别时隙,阅读器直接识别一个标签;若有多个标签应答,则产生一个碰撞时隙,阅读器检测到碰撞,则分别在本次查询的前缀序列后加“0”和“1”形成2个新的查询前缀序列,并把新产生的前缀序列压入栈底。

Setp 3重复Step1和Step2,直到查询序列前缀为空。

基本的二进制树查询算法识别在标签数量较大的情况下,由于存在大量碰撞时隙,识别效率低下。四叉树、八叉树等改进型算法可以减小基本二进制树查询算法中的碰撞时隙。但是,当叉树增多,会增加空闲时隙的数量。

因此,如何在增加叉树减小碰撞时隙的同时减小空闲时隙,是多叉树算法的关键问题。文献[15]提出了基于碰撞因子的自适应多叉树算法和基于分组码的八叉树算法,取得了很好的仿真对比结果。本文提出另一种基于位编码方式的多叉树算法,能够避免空闲时隙的产生。

3 基于位编码的多叉树防碰撞算法

3.1 算法预设条件

标签ID采用曼彻斯特编码,长度为L,阅读器能够正确识别非碰撞位和碰撞位。阅读器中设置一个查询前缀堆栈S和一个寄存器RBM(Recognized Bits Mask),用于记录已识别位数据。

标签中设置一个2m位的编码寄存器MCR。在查询过程中,ID号与查询前缀匹配的标签可根据查询前缀后的高m位ID数据,对MCR进行调制。若某次查询,查询前缀Q为“q(0):q(x)”,某标签查询前缀后的高m位数据为“ID(L-1-x):ID(L-1-x-m)”,则把MCR的第“ID(L-1-x):ID(L-1-x-m)”位置“1”,其他位置“0”。

3.2 算法基本操作

算法基本操作如下:

(1)阅读器查询命令Request(Q):参数Q是x位查询前缀序列“q0q1…qx”。一次查询过程由阅读器广播该命令发起。有效识别范围内,ID号与Q匹配的标签响应查询命令,其他标签不响应。Q值缺省情况下,有效识别范围内所有标签响应查询命令。

(2)标签响应阅读器查询回送数据Data:设某次查询,标签接收到的查询前缀序列“q0q1…qx”,若标签高x位与查询前缀序列匹配,则响应查询,回送数据Data格式如图1所示。回送数据的高2m位是标签当前编码寄存器MCR内容,回送数据的后L-x-m位为标签ID的低位数据。

图1 标签回送的数据格式

(3)阅读器接收标签回送数据,分别跟踪接收数据的MCR区碰撞位和ID区碰撞位,阅读器通过对接收数据的MCR区碰撞位解调,确定本次查询前缀序列对应结点的子结点。设MCR区碰撞位数量为J,ID区碰撞位数量为K,若:

1)J=0,K=0,则无碰撞发生,阅读器直接识别一个标签。

2)J=0,K=1,在剩余ID中仅有一个碰撞位(One Bit Collision Time-slot,OIBCT),由于标签ID的唯一性,阅读器可直接识别2个标签。

3)J=0,K＞1,阅读器通过接收数据MCR区“1”的位置解调出本结点的唯一子结点序号;并把子结点序号接在本次查询前缀序列后,形成一个新的查询前缀序列,压入堆栈S。

4)J≠0,K=0,剩余标签ID无碰撞,但MCR存在碰撞(Multiple MCR Bits Collision Time-slot, MMBCT),则说明子结点均为树叶,可直接识别J个标签。

5)J≠0,K≠0,阅读器检测到不可识别碰撞。此时,阅读器通过解调接收数据的MCR区碰撞位,获得本次结点的J个子结点序号,并分别把每个子结点序号增补在原查询前缀序列后,形成J个新的查询前缀序列,压入堆栈S。

3.3 BCMA算法流程

如图2所示,BCMA的基本步骤如下:

(1)系统初始化,阅读器清空查询前缀堆栈S。

(2)阅读器广播命令Request(),有效通信范围内所有标签响应读写器查询命令。

(3)阅读器接收标签回送数据,跟踪碰撞位,记录MCR区碰撞位位数J和ID区碰撞位位数K,并对MCR区碰撞信息进行解调,计算子结点序号。

(4)阅读器根据J,K的数量关系,直接识别标签或产生新的查询前缀序列入栈。

(5)阅读器查询前缀堆栈S是否为空,若为空,则说明所有标签都已经正确识别,程序退出,否则转步骤(6)。

(6)阅读器从查询前缀堆栈中取栈顶序列Q,并发送查询命令Request(Q),有效通信范围内ID与Q匹配的标签响应阅读器命令,其他标签不响应。程序返回步骤(3)。

3.4 示例分析

设m=3,识别范围内存在8个待识别标签TagA～TagH,各自ID号如表1所示。

表1 待识别标签及其ID号

系阅读器广播Request()命令后,对接收数据MCR进行解调,发现根结点上有4个非空子结点,节点序号分别为“000”,“010”,“011”和“101”。阅读器依次访问这4个结点。具体识别过程如表2所示。若采用常见八叉树算法识别上述8个标签,阅读器需要向标签发送32次查询命令。而在基于位编码的八叉树识别算法里不存在空闲时隙,阅读器识别这8个标签仅需发送9次查询命令,显著提高了系统识别效率。

表2 CBMA识别信息

4 算法性能分析

文献[16]对传统基于二进制树算法性能进行了详尽反洗,若标签ID位长为L,待识别标签数为N,搜索树深度K,则传统B叉树所需的时隙数为:

其中,碰撞时隙和识别时隙数分别为:

空闲时隙数量为:

与传统的B叉树防碰撞算法不同,本文算法利用标签ID的唯一性和不同二进制编码同数位数码的互斥性,通过二进制编码调制的方式去除了空闲时隙,提高识别效率。新算法的空闲时隙树为零。由于存在MMBCT时隙,在传统B叉树中为碰撞时隙,在新算法中为一个可识别多个标签的识别时隙,因此新算法的碰撞时隙将小于传统B叉树算法。同时,由于存在一个时隙识别多个标签,因此新算法的识别时隙将小于传统算法的识别时隙数。但是在标签数目很大时,MMBCT和OIBCT数目将减少,对识别时隙和碰撞时隙数的影响可以忽略。在大标签数量情况下,新算法的总时隙数为:

式(1)减去式(5),可得新算法节省总时隙数为:

新算法的吞吐率为:

5 仿真分析

要验证所提算法的有效性,可在Matlab环境下对算法进行仿真。设标签ID位数为64位;标签ID服从均匀分布;标签数目分别为10,100,200,…, 1000。每设置一次标签数目,实验重复100次,平均时隙为100次取平均。

图3所示为标签MCR长度是8位时,八叉树算法和BCMA的平均时隙数和吞吐率对比仿真结果。仿真结果表明,BCMA的空闲时隙为零,碰撞时隙与八叉树算法相同,总时隙数明显小于八叉树算法。仿真结果还表明,BCMA显著提高了系统的吞吐率。BCMA的平均吞吐率为0.67 slot/标签,八叉树的平均吞吐率为0.25 slot/标签,BCMA使系统吞吐率提高了168%。

图3 BCMA与八叉树算法性能对比

图4所示为标签MCR位数在1～8之间动态变化时,BCMA系统吞吐率的仿真结果。仿真结果表明,BCMA系统吞吐率随着MCR位数的增大呈现先增大后减小的变化趋势。当MCR位数为lbL(L为标签ID位数)时,系统吞吐率达到最大。仿真结果还表明,当标签数量较小时,系统吞吐率起伏比较大,当标签数量较大时,系统吞吐率趋于稳定。这是因为,在标签数量较少时,多位同时发生碰撞的概率较低, MMBCT和OIBCT会对系统吞吐率产生影响。

图4 MCR位数对BCMA系统吞吐率的影响

MCR位数的增大,增加了标签的复杂度,同时也增大了系统的通信载荷。BCMA在提高系统吞吐率的同时需要兼顾成本和通信载荷,因此,标签MCR位数不宜过高,通常取4位或8位。

6 结束语

本文提出一种基于二进制码调制的RFID多标签防碰撞算法BCMA。通过确定性分组,避免空闲时隙的产生,显著提高识别效率。理论分析和仿真实验表明,BCMA性能优于常见的多叉树算法,显著提高了系统吞吐率。BCMA对常见的多叉数算法进行了改进,具有一定的创新性。同时提高了RFID系统识别效率,具有一定的实用性。下一步工作是设计并实现能够支持本文算法的标签和读写器并开展应用。

[1] Zuo Yanjun.Survivable RFID Systems:Issues,Challenges and Techniques[J].IEEE Transactions on Systems,Man, and Cybernetics-Part C:Applications and Reviews,2010, 40(4):406-418.

[2] Mohamed B,Adel M,Belkacem F.Dual Antenna for Physical Layer UHF RFID Collision Cancelling[C]// Proceedings of International Conference on Multimedia Computing and Systems.[S.l.]:IEEE Press,2012:623-628.

[3] Lee Chi-Chung,Lin Shengyue.A Double Blocking Dynamic Framed Slotted ALOHA Anti-collision Method for Mobile RFID Systems[C]//Proceedings of the 6th International Conference on Genetic and Evolutionary Computing.[S.l.]:Springer,2012:581-584.

[4] Jiang Chenyi,XuYinfei,WangQiao.Cancellation Strategy in Dynamic Framed Slotted ALOHA for RFID System[C]//Proceedings of IEEE Wireless Communications and Networking Conference.[S.l.]:IEEE Press,2013:854-859.

[5] Yang Qing,Li Jiancheng,Wang Hongyi,et al.A Dynamic Framed Slotted ALOHA Anti-collision Algorithm BasedonTag-groupingforRFIDSystems[C]// Proceedings of the11th International Conference on Digital Object Identifier.[S.l.]:IEEE Press,2012:1-3.

[6] Wang Shuai,Hong Weijun,Li Shufang.A Slot-wise LMMSE Estimate Algorithm for Frame Slotted Aloha Protocol of RFID System[C]//Proceedings of the 8th International Conference on Wireless Communications, Networking and Mobile Computing.[S.l.]:IEEE Press,2012:1-5.

[7] Xue Jianbin,Wang Wenhua,Li Songbai,et al.Anticollision Algorithm Based on Counting Mechanism and Multi-stateBinary[C]//Proceedingsofthe5th Conference on Measuring Technology and Mechatronics Automation.[S.l.]:IEEE Press,2013:276-282.

[8] Landaluce H,Perallos A,Zuazola I J G.A Fast RFID Identification Protocol with Low Tag Complexity[J]. IEEE Communications Letters,2013,17(9):1704-1706.

[9] Lai Yuancheng,Hsiao Ling-Yen,Chen Hongjie,et al.A Novel Query Tree Protocol with Bit Tracking in RFID Tag Identification[J].IEEE Transactions on Mobile Computing,2013,12(10):2063-2075.

[10] Yang Yongkang,Cui Chunsheng,Zhou Tuanfeng,et al. ImprovementonRFID-basedBinaryAnti-collision Algorithm[C]//Proceedings of International Conference on Computer Science and Service System.[S.l.]:IEEE Press,2012:515-518.

[11] Di Jin,Ma Yanmin,Fan ZhiPeng,et al.A RFID Anticollision Algorithm Based on Multithread Regressivestyle Binary System[C]//Proceedings of International Conference on Measurement,Information and Control. [S.l.]:IEEE Press,2012:365-369.

[12] Liang Chiu-Kuo,Lin Hsin-Mo.Using Dynamic Slots Collision Tracking Tree Technique Towards an Efficient Tag Anti-collision Algorithm in RFID Systems[C]// Proceedings of the 9th International Conference on Autonomic&Trusted Computing.[S.l.]:IEEE Press, 2012:272-277.

[13] Piao Chunhui.Fan Zhenjiang.Yang Chunyan,et al. ResearchonGroup-basedPollingAnti-collision AlgorithmforRFIDTagIdentification[C]// Proceedings ofInternationalForumonInformation Technology and Applications.[S.l.]:IEEE Press, 2010:185-188.

[14] Bai Yu,Xuan Xiuwei,Teng Jianfu,et al.An Anticollision Algorithm Based on Collision Bit Position and Splitting[C]//Proceedings of the 6th International Conference on Wireless Communications Networking and Mobile Computing.[S.l.]:IEEE Press,2010:1-4.

[15] 张学军,王绪海,蔡文琦.基于分组码的改进型防碰撞算法研究[J].计算机应用研究,2012,29(11): 4265-4268.

[16] Hush D R,Wood C.Analysis of Tree Algorithms for RFID Arbitration[C]//Proceedings of International Symposium on Information Theory.[S.l.]:IEEE Press,1998:1-10.

编辑 顾逸斐

A Radio Frequency Identification Anti-collision Algorithm Based on Binary Code Modulation

LI Zhijian1,3,XIAO Yilin2
(1.School of Electronic and Information Engineering,South China University of China,Guangzhou 510640,China;
2.Guangzhou Research Institute of Optical Mechanical Electrics Technology,Guangzhou 510663,China;
3.Guangdong Public Laboratory of Modern Control and Optical Mechanical Electrics Technology,Guangzhou 510663,China)

To improve the identification efficiency and reduce the communication overhead,a novel algorithm,Binary Code Modulation Algorithm(BCMA)is proposed.BCMA works as follows:the activated tag generates and sends back a 2mbit binary code,Master Control Relay(MCR),on which the location information of the tag’s ID in the multi-branch tree is modulated.After receiving the MCR,the reader finds out the collided bits,demodulates the branch information,and groups the tags into determinate subsets.It is obvious that BCMA avoids generating idle slots.Analysis results and simulations show that compared with other existing multi-branch algorithms,as the common octree algorithm,BCMA improves the system throughput by168%.

Radio Frequency Identification(RFID);anti-collision algorithm;throughput;Binary Code Modulation Algorithm(BCMA);multi-branch tree;bit tracking technique

李志坚,肖熠琳.一种基于二进制码调制的射频识别防碰撞算法[J].计算机工程,2015,41(2): 308-312.

英文引用格式:Li Zhijian,Xiao Yilin.A Radio Frequency Identification Anti-collision Algorithm Based on Binary Code Modulation[J].Computer Engineering,2015,41(2):308-312.

1000-3428(2015)02-0308-05

:A

:TN92

10.3969/j.issn.1000-3428.2015.02.059

广东省科技计划基金资助项目(2010A011300016,2011J4100034,2011J4300078)。

李志坚(1981-),男,讲师、博士研究生,主研方向:RFID技术,信号处理,物联网应用;肖熠琳,工程师。

2014-01-03

:2014-03-31E-mail:lizhjian@scut.edu.cn