基于多位碰撞检测的自适应树形RFID防碰撞算法*

梅佳伟，李 晖

（沈阳工业大学 信息科学与工程学院，辽宁 沈阳110870）

0 引 言

射频识别（Radio Frequency Identifcation，RFID）技术起始于1973年。作为自动识别和数据获取的一部分，RFID系统通过无线网与网络系统进行互交，能够单独识别追踪并捕获包装中货物、动物甚至人的标签状态或信息[1]。因此，RFID将会取代现在普遍使用的条形码广泛应用于物流、零售和存储管理等领域[2]。

由于标签的体积和造价等原因限制，一个阅读器读取范围内同时出现多个标签时，它们会同时响应阅读器的查询信息，而标签本身无法感知到周围标签的存在，此时就会出现标签信息的碰撞[3]，导致阅读器无法顺利获取标签信息。因此，射频标签的防碰撞成为射频识别过程中的一个关键技术[4]。

受现有标签技术和成本制约，目前的标签防碰撞算法主要分为两类：一种是以ALOHA算法为主的非确定性算法[5-8]，一种是以二进制搜索算法为基础的确定性算法。其中，ALOHA算法容易出现有一些标签可能长时间与其他标签发生碰撞而不能被识别的现象，即标签饿死现象。二进制树搜索的防碰撞算法主要包括动态的二分支搜索DBS算法、查询树QT算法[9]和碰撞树CT算法[10]等。这些算法主要通过不断对标签池查询的方式，达到完全识别未读取的标签的目的。它不存在标签饿死现象，但是造成了通信量的大量增加和识别时间长的问题。

在此基础上出现了一些多叉树的防碰撞算法，识别过程中通过降低查询轮数或者提高查询码的准确程度来降低通信量和空闲时隙。但是，由于二进制查询方式的逐位查询特点，遇到新的碰撞位标签就会向阅读器发送信息用以形成新的查询码，而阅读器能利用到的信息只有碰撞位信息，这样在碰撞密集的位置就会造成大量的通信资源浪费。例如，宋建华等人提出的AHT算法[11]，动态选择树形叉数，通过减少查询轮数来降低通信代价，但无法判别多位碰撞的碰撞类型，造成了不可避免的空闲时隙，识别效率不稳定。付钰等人在GBAQT算法[12]中通过增加仲裁位数，使阅读器与标签反复通信对比来确定多位碰撞的类型，使得系统的空闲时隙减少甚至消除来达到提高识别效率的目的，但大大提高了通信成本。Landaluce H等人在CT算法的基础上提出了CWT算法[13]，通过动态窗函数确定下一轮标签向阅读器的通信量，但在无碰撞时隙会出现阅读器不能读取到全部标签信息的情况，降低了整个系统的识别效率，增加了识别成本。本文提出一种自适应多位碰撞检测算法MCDT，通过检测到的最高2～3位碰撞位的间隔特点，借助于查询码，动态决定下一轮标签向阅读器传送的信息量，从而在保持较少空闲时隙维持稳定的识别时间的同时，大量降低标签到阅读器的通信量。

1 MCDT碰撞检测算法

1.1 碰撞树算法

CT碰撞树算法以及目前主要的二进制防碰撞算法都是通过曼切斯特编码对识别过程中的碰撞位进行追踪定位[14-16]。CT算法过程中，阅读器在一轮查询后接收到了标签发送来的信息，先判断信息中是否存在碰撞，如果存在碰撞则判断第一位碰撞位的具体位置，之后根据第一位碰撞位的具体位置形成2个新的查询码再进行查询过程。例如：在某轮中查询码的内容为q1q2…qi（若标签的ID信息总位数为k位，则i是小于等于k且大于零的整数)。本轮中阅读器接收到的信息为r1r2…rc-1rc，其中rc为检测到的第一位碰撞位，则将形成2个新的查询码q1q2…qir1r2…rc-10和q1q2…qir1r2…rc-11。重复上述过程，直到当前阅读器范围内不存在未读取的标签。

在CT算法和现有的二进制防碰撞算法中，都是通过提高识别效率、减少查询次数来简化系统的通信来降低通信量。不论是二叉树或者是多叉树算法，利用的都是检测到的最高几位的连续碰撞位形成新的查询码。CT算法主要利用一位碰撞位，而四叉树的算法会利用第1位和第2位碰撞位形成00、01、10、11这样4个分支。在一次查询过程中，最高几位碰撞位后的信息都是无用信息，如CT算法中阅读器接收到r1r2…rc-1rcrc+1…，其中rc+1…属于无用信息。标签在每一轮的查询过程中都会向阅读器传输大量无用信息，且回复的标签数目越多，碰撞位越密集，造成的浪费越多。

1.2 MCDT算法

针对CT算法中通信资源的浪费问题，提出MCDT算法来避免标签向阅读器传送大量无用信息。MCDT算法将查询码的形式由CT算法的q1q2…qi转变成q1q2…qi||T。新形成的查询码比原有的多出一位信息T。T的目的是辅助标签确定查询过程中需要向阅读器发送多少位的标签信息。T的具体数值利用阅读器检测到的最高第2位与第3位碰撞位之间间隔的比特位数S来控制计算的。图1演示了在后2位碰撞并不连续的情况下阅读器如何形成新的查询码的工作过程。若3个碰撞位在接收信息中的编号分别为r_c1、r_c2、r_c3。在检测到的第1位碰撞位r_c1处，阅读器会形成2个查询码。如图1所示，原查询码q_1q_2…q_i和检测到不发生碰撞的信息r_1r_2…r(c-1)、r_(c1+1)…r_(c2-1)不 变，r_c1在 上方查询码中转变为0，在下方查询码中为1。形成的两个新查询码为在 下 一 轮 查 询 的 过程中，得到的回复信息第一位必然是一个碰撞位。再通过第2、3位之间的间隔S来确定T的值。图1中S bit为接收到标签信息中从r_c2到r_c3共有S bit的数据。因为考虑到在接下来的查询过程中还需要至少3个碰撞位来辅助确定T的值，这里规定T必须是大于等于S+4。

实际情况中，并不是每次都是算法理想状况能出现3位碰撞，或者3个碰撞位是连续的中间没有不碰撞的信息位。这些情况在识别过程中总会发生，那么算法就要自适应去调整识别方式。规定在一次检测中只出现了2次或者1次碰撞，则T值就会被设置为k-i，即在这2种情况下，下一次的查询过程中标签传输除对应查询码位数的剩下的所有信息。

图1 新查询码形成过程

1.3 MCDT算法的流程

流程如图2所示，其中L为当前查询码长度，K为标签ID信息二进制码的长度。

图2 算法流程

步骤1：阅读器重置，初始化查询前缀堆栈，向堆栈中依次压入0|T、1|T；

步骤2：查询码存储单元弹出顶部的数据查询码。接着阅读器发送QUERY(q1q2…qi||T)，在当前的阅读器范围内与查询内容相符合的标签回应阅读器查询。

步骤3：标签检测自己的ID信息前缀与查询码q1q2…qi对应位置是否相同。检测结果相同的标签，响应阅读器的查询信息，且根据查询码中的T来确定要发送多少比特的信息给阅读器，然后执行步骤4；若是没有标签前缀与本次查询码相同，那么本轮查询便无响应，系统认定此次阅读器时隙开销为无用的空时隙，转到算法步骤6。

步骤4：阅读根据标签发来的标签信息，验证有无发生碰撞。如果没有碰撞发生，则记录标签信息成功识别次标签；若是发生碰撞，则执行步骤5。

步骤5：首先判断碰撞的类型。碰撞位是否大于等于3位，若成立，则在最第1位碰撞位处形成0和1两个分支，再加上第1位到第2位碰撞位之间的数据形成2个新的查询码，然后根据最高第2二位与第2位碰撞位之间的距离更新T的数值，即一个ST的过程，之后把这2个查询码压入堆栈。若碰撞位低于3位，则在最高位碰撞处形成0和1分支2个查询码，再将T设置为k-i压入堆栈，进入算法步骤6。

步骤6：检测当前查询码储存单元中是否还有查询码数据。若为空，则说明查询结束，退出算法循环；如果不为空，则转到算法步骤2，继续进行算法循环。

例如，第一次查询过程中阅读器接收到的信息为1XXX0011…XXX（一共是（k-1）比特信息），那么现在就可以判断S=2，ST之后查询码中T的数值被设置为T=2+4=6，那么下一次标签传送给阅读器的信息为XX0011（一共是6bit信息）。可见，一次查询过程中，标签要传送给阅读器的信息量大量减少，同时不影响阅读器形成新的查询码。

2 算法分析

在RFID系统中，主要用阅读器的识别效率、识别时间复杂度和阅读器与标签的通信复杂度衡量算法的性能[17]。MCDT算法与CT算法在识别效率方面大致相同。下面通过计算分析MCDT算法的性能。

MDCT算法在识别过程中主要采用二叉树的分支方式。识别过程是由阅读器查询到标签回应的一个个周期组成。这里设需要识别的标签数量为n，由于每次都是在碰撞点进行分支，所以CT算法中不存在空时隙，也就是没有标签回应的时隙，故二叉树的叶子节点数也是n。

碰撞树中节点数目为：

每一个节点处，阅读器都要进行一轮查询，那么二叉树中的节点数目就是完整的识别过程中阅读器需要查询的次数，也就是阅读器需要开销的时隙数。设第N轮的查询时间为TN，那么阅读器查询过程的时间复杂度T就可以表示为：

每进行一轮查询阅读器就会有一个时隙开销。在防碰撞算法中，算法效率主要是指要识别的标签数量与阅读形成的总的时隙数量的比值，即识别效率E可表示为：

可知，CT算法的整体效率略大于50%。

标签的通信复杂度主要是指在识别过程中，标签需要向阅读器发送的二进制数据的位数，所需要传送的数据量越大，标签需要的能量就越多，对标签成本的要求就越高。

若设C为查询过程的通信量，lc.N、lq.N分别为阅读器在第N个周期查询过程中发出的命令和查询码的长度。lr.N是在本周期标签响应阅读器命令回复的二进制数据长度，那么C可以表示为：

在原本的碰撞树和相关的改进算法中，若设每个标签的ID信息二进制数据长度为k，那么：

MCDT算法中，由于会根据碰撞的情况去决定下一次标签向阅读器传输的二进制数据长度lr.N，那么在碰撞符合条件的情况下，回复的长度为lr.N1，则：

因此，新的通信量C1为：

由此可知，MCDT算法在整个识别过程中的通信复杂度会低于原有的碰撞树相关算法。

3 算法的仿真以及验证

使用Matlab2014b作为仿真平台，对碰撞树算法（CT）、查询树算法（QT）、自适应的A4PQT四叉树算法[18]和本文的自适应多位碰撞检测算法（MCDT）进行对比仿真。仿真的内容主要是识别效率、识别时间和标签对阅读器的通信复杂度。使用现在主流的96bit长度标签进行仿真，而为了数据能够更加清晰，标签的数量从100到1000，每次增长50个。

图3是4种算法的识别效率对比图。

图3 效率对比

可以看出，在识别效率方面，MCDT算法与碰撞树CT算法基本一致。由于每次都是在碰撞位置形成新的查询码，所以基本没有无应答时隙，效率基本稳定在0.5，与标签的数量无关联。A4PQT算法由于在连续2位碰撞时会出现4个分支，这样一次分支就有可能造成最多2个空时隙，故识别相同数目标签时效率会低于MCDT算法和CT算法。

图4是4种算法识别时间的对比仿真。可以看出，由于QT算法和A4PQT算法中存在较多的空时隙，也就是存在很多轮次的查询是没有标签回应的，故查询完成的总时间明显高于另外2种算法。而从图4中可以看出，MCDT算法在标签数目较多时，查询完成时间略低于CT算法；数目较低时，查询时间则基本与CT算法持平。

图4 识别时间对比

如图5所示，是4种算法在标签到阅读器的通信量的对比仿真。可以看出，由于QT算法无论碰撞与否，每次只增加一位查询码。在这种情况下，标签发送给阅读器的信息量明显高于在碰撞点形成查询码的CT算法。当遇到连续碰撞的情况时，如果存在00、01、10、11这4种情况的碰撞，那么A4PQTMCDT算法与CT算法相比，就会降低查询次数。从图5也可以看出，A4PQT算法的通信量比CT算法有明显下降。与MCDT算法相较，因为新算法会根据碰撞信息来调整标签向阅读器的通信量，所以每次只发送有用的碰撞信息，最后才发送完整的标签信息，故通信量降低的幅度非常明显，且标签越多碰撞情况越复杂，所以标签越多时通信量的优势越明显。

图5 通信量对比

由以上3个对比仿真可以看出，本文提出的MCDT算法在识别效率和识别时间方面都有较好表现，且大大降低了通信量，优势明显。

4 结 语

本文基于二进制防碰撞算法中的碰撞检测方法，提出了一种利用2～3位碰撞位的自适应多位碰撞检测的防碰撞MCDT算法。该算法通过检测最高2～3位的碰撞位来辅助判断标签在下一轮中需要传递给阅读器的标签信息，避免在多次查询过程中或者是碰撞密集环境下标签向阅读器传输过多的无用信息而浪费能量。

通过仿真结果可以看出，MCDT算法能够减少阅读器与标签的通信量，降低标签成本，且在维持查询效率、查询时间时有较好表现，同时有效降低了标签向阅读器的通信复杂度。根据仿真结果可以知道，在标签数量快速增加的同时，通信量降低幅度显著。因此，MCDT算法适合于同一个阅读器范围内标签数目较多或者需要连续读取较多标签的场景，符合现代大型仓储物流、无人超市的应用环境。

参考文献：

[1] He M,Horng S J,Fan P,et al.A Fast RFID Tag Identification Algorithm Based on Counter and Stack[J].Expert Systems with Applications An International Journal,2011,38(06):6829-6838.

[2] Safa H,El-Hajj W,Meguerditchian C.A Distributed Multi-Channel Reader Anti-collision Algorithm for RFID Environments[J].Computer Communicatio ns,2015,64(01):44-56.

[3] Hsu C H,Chao H C,Park J H.Threshold Jumping and Wrap-around Scan Techniques Toward Efficient Tag Identification in High Density RFID Systems[J].Information Systems Frontiers,2011,13(04):471-480.

[4] Li T,Wu S S,Chen S,et al.Generalized Energy-efficient Algorithms for the RFID Estimation Problem[J].IEEE/ACM Transactions on Networking,2012,20(06):1978-1990.

[5] He Y,Wang X.An ALOHA-based Improved Anticollision Algorithm for RFID Systems[J].IEEE Wireless Communications,2013,20(05):152-158.

[6] 陈毅红,冯全源.按需时隙分配RFID防碰撞协议研究[J].电子学报,2014,42(02):377-382.CHEN Yi-hong,FENG Quan-yuan.Research on RFID Anti-collision Protocol for on-demand Time Slot Allocation[J].Acta Electronica Sinica,2014,42(02):377-382.

[7] Wang H,Xiao S,Lin F,et al.Group Improved Enhanced Dynamic Frame Slotted ALOHA Anti-collision Algorithm[J].Journal of Supercomputing,2014,69(03):1235-1253.

[8] 丁治国,丁莉,汤红飞.基于动态预约机制的防碰撞算法[J].计算机工程,2017,43(02):317-321.DING Zhi-guo,DING Li,TANG Hong-fei.AnticollisionAlgorithm Based on Dynamic Reservarion Mechanism[J].Computer Engineering,2017,43(02):317-321.

[9] Hush D R,Wood C.Analysis of Tree Algorithms for RFID Arbitration[C].IEEE International Symposium on Information Theory,2002:15-23.

[10] Jia X,Feng Q,Ma C.An Efficient Anti-Collision Protocol for RFID Tag Identification[J].IEEE Communications Letters,2010,14(11):1014-1016.

[11] 宋建华,郭亚军,韩兰胜等.自调整混合树RFID多标签防碰撞算法[J].电子学报,2014,42(04):685-689.SONG Jian-hua,GUO Ya-jun,HAN Lan-sheng.An Adjustive Hybrid Tree Anti-CollisionAlgorithm for RFID Multi-Tag Identification[J].Acta Electronica Sinica,2014,42(04):685-689.

[12] 付钰,钱志鸿,程超等.基于分组机制的位仲裁查询树防碰撞算法[J].通信学报,2016,37(01):123-129.FU Yu,QIAN Zhi-hong,CHENG Chao,et al.Bit Arbitration Query Tree Anti-CollisionAlgorithm Based on Grouping Mechanism[J].Journal on Communicatio ns,2016,37(01):123-129.

[13] Landaluce H,Perallos A,Bengtsson L,et al.Simplified Computation in Memoryless Anti-collision RFID Identification Protocols[J].Electronics Letters,2014,50(17):1250-1252.

[14] Shin J,Jeon B,Yang D.Multiple RFID Tags Identification with M-ary Query Tree Scheme[J].IEEE Communications Letters,2013,17(03):604-607.

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

[16] Lai Y C,Hsiao L Y,Chen H J,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.

[17] Jiang Y,Zhang R.An Adaptive Combination Query Tree Protocol for Tag Identification in RFID Systems[J].IEEE Communications Letters,2012,16(08):1192-1195.

[18] Zhang W,Guo Y,Tang X,et al.An Efficient Adaptive Anti Collision Algorithm Based on 4-Ary Pruning Query Tree[J].International Journal of Distributed Sensor Networks,2013(01):1-7.