捕获效应下RFID标签的CATPE防冲突协议

杨茜，吴海锋，曾玉

（云南民族大学 电气信息工程学院，云南 昆明 650500）

1 引言

在物联网[1]中，大量 RFID标签需被阅读器快速识别，为提高识别效率，阅读器通常一次识别多个标签。由于阅读器识别标签采用共享的无线信道，标签冲突不可避免[2]。通常阅读器采用防冲突协议来解决标签间冲突[3]，所以标签的防冲突协议在物联网中起到了重要作用。

在被动式RFID系统中，2个以上的标签同时发射信号并不一定导致冲突。在阅读器磁场范围内，标签距阅读器的位置远近不一，因此发射的信号也有强弱差别，而捕获效应可使信号较强的标签被阅读器识别，而信号较弱的标签将被捕获效应隐藏。由于许多传统的防冲突协议[3～17]均假设捕获效应不存在，但捕获效应恰恰在RFID系统中又是一个普遍现象。因此近几年，如何在捕获效应的情况下解决标签冲突问题得到越来越多的关注[18～21]。

在被动式RFID标签防冲突协议中，动态帧时隙 ALOHA 类协议应用非常广泛[4～10,20～24]。该协议的基本思想是每个帧的长度动态变化，即每个帧中的时隙数应为每个帧中待识别的标签数[5～8]。然而，当捕获效应发生时，该方法并不能使效率达到最优，因为此时的帧长不仅与标签数相关，还与捕获效应的概率相关[24]。由于标签数和概率值未知，因此需要估计它们。现有的算法虽然估计了这2个值，但是其复杂度较高。另外，现有算法均假定空时隙、成功时隙以及冲突时隙占用时间等长，以此设置最优帧长，而在实际的 RFID系统中，各时隙并不相同，如EPC C1 Gen2[21]标准中规定了各时隙不等长，因此该设置并不能使识别效率达到最优。

为优化识别效率，本文针对RFID动态帧时隙ALOHA防冲突协议提出了一种在捕获效应下的CATPE (capture-aware and tag-population estimation)协议。该协议通过空时隙数的观测值来估计标签数和捕获效应发生的概率值，然后再设置最优帧长。该算法降低了计算复杂度，并给出了兼容于EPC C1 Gen2 的非等时隙长下的最优帧长设置，从而提高了系统的识别效率。

2 相关工作

GBT 协议[18]是为解决捕获效应而提出的一种二进制树（BT）类协议[11]，该协议解决了传统BT类协议无法识别隐藏标签的问题，它让阅读器把识别的标签 ID返回给标签，那么隐藏的标签将会发现其自身的ID与阅读器返回的ID不符，然后再进入下一个识别循环再被识别。然而，GBT协议实质上将帧长设置为2，当捕获效应的概率较小时，其识别效率并不能达到最优。

最优Q算法[19]是EPC C1 Gen2标准中Q算法的改进算法，它假定标签数已知，让帧长等于标签数，这在无捕获效应的情况下识别效率能达到最优。然而，当捕获效应生时，最优效率却无法保证，因为此时的帧长不仅与标签数还与捕获效应发生的概率相关[24]。另外，在标签数未知的应用环境中，该方法也不适用。

CMEBE协议[24]通过二维搜索得到标签数和捕获效应概率值，然而其计算复杂度较高。并且，虽然该协议推导了最优帧长表达式，但是它假定各时隙等长，这与实际RFID并不相符。

3 捕获效应下的最优识别效率问题

在被动式RFID动态帧时隙ALOHA协议中，识别效率定义为成功识别的时隙时间与总的时隙时间的比值。由于以下原因，捕获效应下与没有捕获效应下的识别效率有所不同。第一，捕获效应使原先假定为冲突的时隙变为成功时隙，因此识别效率得到了提高；第二，被捕获效应隐藏的标签[18]会与其他未识别标签冲突。图1分别给出了捕获效应下RFID动态帧时隙ALOHA协议中2种帧长设置方式的识别效率随捕获效应概率值的变化曲线。方式1为传统方式，即帧长等于标签数，该方式已经被证明在无捕获效应条件下能够使标签识别效率达到最优[6～10]；方式2的帧长设置是关于标签数和捕获效应概率的函数，该方式在5.4节中被证明是捕获效应下的最优帧长。

从图1得知，当系统存在捕获效应时，方式1所得到的识别效率低于方式 2。为使识别效率得到提高，需采用方式 2帧长设置方式，而这种方式不仅需要标签数的信息还需要捕获效应发生概率的信息，因此必须要对标签数和捕获效应概率进行估计。

图1 捕获效应下的系统识别效率

4 系统描述

在RFID动态帧时隙ALOHA协议中，标签的识别过程被分为若干帧，每帧又被分为若干时隙。标签在每个帧中只能随机选择一个时隙向阅读器发送信息。对于一个给定的时隙只能产生3种情况：没有标签、有一个标签或有2个以上的标签发射信号。若没发生捕获效应，这3种情况分别对应于空、可读和冲突时隙；若发生捕获效应，那么即使有 2个标签发送信息，也可产生可读时隙。在该协议中，当前帧中发生冲突的标签和被隐藏的标签将进入下一帧中继续被识别，当所有标签均被阅读器识别，整个识别结束。RFID动态帧时隙ALOHA协议中每个帧的长度动态变化，该值与待识别的标签数和捕获效应概率保持一定比例以保证较高的识别效率。给出定义如下。

定义1 l表示RFID动态帧时隙ALOHA协议的第i个阅读帧长，可定义为

其中，c0、c1和ck分别表示第i帧中的空时隙数、成功时隙数和冲突时隙数的观测值，那么阅读器成功阅读所有标签所需要的总时隙数定义为

其中，m为成功阅读所有标签所需要的帧个数。

定义2 第i帧中发生捕获效应的概率p定义为

其中，s表示第i帧中发生捕获效应的时隙数的期望值，ak′为第i帧中有2个或2个以上的标签选择同一个时隙个数的期望值。

定义3 第i帧中阅读器识别效率P定义为

其中，t0、t1和tk分别表示第i帧中空时隙、成功时隙和冲突时隙所占用的时间。

5 捕获效应下的CATPE 协议

5.1 低复杂度标签数和捕获效应概率估计

由于标签选择时隙相互独立，且标签每次选择某个时隙结果只有2种情况，即选择或不选择，则标签选择时隙是一个二次项伯努利试验。因此，当系统存在n个标签，第i帧长为l时，有r个标签同时选择一个时隙的概率为[6～11]

那么，被r个标签同时选中的时隙数的期望值为

在RFID动态帧时隙ALOHA协议中，若第i个帧中发生捕获效应的概率为p，那么在该帧中空时隙数、成功时隙数和冲突时隙数的期望值分别为

把 a0=c0代入式(8)中，那么该帧中标签数可估计为

同时，由式(6)、式(7)可得

5.2 bit-slot分组及帧长调整系数

在RFID动态帧时隙ALOHA协议中，用式(9)估计标签数需满足c0≠0。然而当初始时刻的待识别标签数n0＞＞l0时，c0将趋近于 0。此时为保证c0≠0可重新调整帧长，使其增大M倍，即

其中，M可选大于2的整数。当然如果多次调整帧长才产生空时隙数，会产生过多的冲突时隙，从而增加识别时间。因此，可采用 bit-slot方法[25]来检测是否调整后的帧中产生了空时隙，如图2所示。阅读器在设置初始帧长时可先发送带有参数l0的命令给标签，标签接收到命令后在l0个时隙中随机选择一个时隙发送1个bit的信息。如果某个时隙中没有检测到bit，则该时隙为空时隙，那么帧长调整结束。在此方法中，由于标签只发送1个bit，而不是其ID信息，因此可减少调整帧长的时间。

图2 bit-slot协议

下面将确定帧长调整系数M的取值。首先，把一小概率事件的概率阈值表示为Δ(0＜Δ≤1)，那么，当空时隙概率小于或等于Δ时，一个帧中空时隙数接近于 0。假定系统中标签数与帧长为线性关系，即li=kni，则由式（7）可得

因此，若要使得空时隙数不为零，则应使

5.3 估计复杂度分析

一些用来估计标签数的传统估计方法，如VOGT估计[5]需搜索来找到极值，CMEBE[24]则需要进行二维搜索来时估计标签数和捕获效应概率值。在文献[4]中所提出的CMEBE方法通过下式估计标签数和捕获效应概率

VOGT估计仅对标签数进行估计，所以穷尽搜索次数为v。相反，本文 CATPE 协议的估计算法不需要进行搜索，它只需通过式(13)一步计算即可得到标签数，捕获效应概率值估计也不需要通过搜索算法，仅通过式(15)的求伪逆即可得到。表 1中给出了VOGT、CMEBE以及CATPE 3种方法的搜索次数比较。

表1 VOGT、CMEBE以及CATPE 算法的搜索次数

5.4 最优帧长设置

5.4.1 等时隙时长的最优帧长

等时隙时长下，由于t0=t1=tk，根据定义3可得第i帧识别效率为

为了获得最优帧长，将式(7)代入式(17)，对l求导，并使式(17)等于零，可得最优帧长为

5.4.2 非等时隙时长的最优帧长

在实际的RFID系统中空、成功和冲突时隙所占用的时间不一定相等，例如在EPC C1 Gen2标准[21]中，这些时隙所占用的时间就不一样，空时隙数的时间最短，其次是冲突时隙，而成功时隙所用时间最长[8]。下面将推导非等时隙时长的最优帧长。

首先，考虑一种线性模型，第i帧长l与标签数n具有线性关系l=rn，那么

将式(19)、式(20)代入定义3，并令α=t0t1，β=tk/t1，有

若

其中，R为r的取值集合，那么最优帧长为

5.5 协议描述

初始时，阅读器设置初始帧长为l0，标签在该帧中选择时隙，阅读器通过bit-slot方法检测是否存在空时隙，若空时隙为0，则重新设置初始帧长；否则，阅读器将记录标签选择的空、成功和冲突时隙数，以此估计标签数和捕获效应概率。得到标签数和概率值估计值后，将以估计的结果来设置下一个帧的最优帧长。由于第i帧的标签数

且假定该帧的捕获效应概率pi+1是关于pi的函数，即

通常，函数f(·)并不能轻易获得，该函数不仅与选取的帧长相关，而且与标签的实际识别环境相关，例如标签与阅读器距离的远近，标签散射信号的强弱[5,18]。为便于验证最优帧长的选取，采用文献[19,24]实验中所采用的捕获效应模型，pi+1=f(pi)=pi，即捕获效应的概率是一个恒值。

将式(24)和式(25)代入式(18)，等时隙时长第i+1帧的最优帧长可设置为

同理，将式(24)和式(25)代入式(23)～式(25)，非等时隙时长第i+1帧的最优帧长可设置为

图3给出了阅读器端CATPE 协议的流程。初始时，阅读器通过观测值c0调整帧长，采用bit-slot方法来统计空时隙数。如果空时隙数为0，则通过式(13)重新设置初始帧长。然后，阅读器将执行动态帧Aloha算法。首先，统计当前帧中空、成功和冲突时隙数；然后据此通过式(9)和式(12)来估计标签数和捕获效应概率；判断（c1!=0或ck!=0）是否为真，如果为真则通过式(26)或式(27)设置最优帧长，并继续阅读标签直到（c1!=0或ck!=0）为假。

图3 阅读器端CATPE协议流程

6 计算机仿真结果

6.1 仿真系统设置

本部分通过计算机仿真的实验结果验证本文提出的 CATPE协议，在仿真实验中，采用一个阅读器识别多个标签的情况，并且假定在识别过程中标签不会离开阅读器的磁场范围，也不会有新的标签进入阅读器磁场。使用以下指标来评价标签识别的性能。

1)估计误差：观测在一个帧内估计的标签数及捕获效应发生概率的估计相对误差，定义为

2)搜索次数：观测在一个帧内估计标签数和捕获效应概率值所需要的搜索次数，较少的搜索次数将具有较低的计算复杂度。

3)总识别效率：该效率定义为在m帧内识别完所有标签的识别效率，表示为

较少的空时隙和冲突时隙将得到较高的总识别效率。

4)标签平均识别时间：观测在一个帧内识别每个标签所花费的时间，定义为

较少的平均识别时间所得到总的识别时间也较少。

在仿真中，对每个实验重复执行500次，最后的实验结果为500次结果的平均值。把本文提出的CATPE 协议与现有的Optimal Q、GBT和CMEBE协议进行对比，这些协议的参数如下。

1)Optimal Q：Q0取4.0，同时根据文献[19]，假定第n个帧长的标签数Tn已知，那么第n个帧长的Qn为。

2)GBT协议：初始时，所有标签的计数器均为0。被捕获效应隐藏的标签将进入下一个二进制树循环[18]，其中，一个二进制树循环定义为在这个循环中所有冲突时隙均被分解为可读时隙或空时隙。

3)CMEBE协议：标签值及捕获效应概率值搜索范围分别设置为Ni={c1i+2cki≤n≤Nmax|n∈Z}，其中Nmax=500，P={0,0.1,…,1.0}。

4)Bayes方法：采用非等长时隙参数，即t0≠t1≠tk。

本部分的仿真结果将分为以下几部分：第一部分给出CATPE 协议与现有协议在估计误差的对比结果，第二部分给出 CATPE 与现有协议在估计复杂度的对比结果，最后一部分给出协议的总识别效率。本仿真系统所涉及到的其他参数如下。

1)待识别标签数：n0=300。

2)初始帧长：l0=128。

3)时隙时长：等时隙时长时，t0=t1=tk；非等时隙时长时，t0=50μs，t1=400μs，tk=200μs[8]。

4)捕获效应概率模型：采用文献[19,24]中的模型，即pi=p。

5)帧长调整系数：设置小概率事件阈值Δ=2×10-2，则取M=4。

6.2 估计误差

给出CATPE 和CMEBE对标签数以及捕获效应概率的估计相对误差随捕获效应概率值pi的变化曲线。图4给出了在第一帧中的估计结果，从图4可以看到，4条曲线的估计误差基本都在0～3%之间，这一结果表明，CATPE 和 CMEBE的估计误差很接近。

6.3 计算复杂度

给出 CATPE 及 CMEBE的搜索次数，以搜索次数来评价估计的计算复杂度。图5给出了在不同标签数条件下，第一帧中搜索次数随捕获效应概率值变化的曲线。从图5可以看出，CMEBE算法的搜索次数远大于 CATPE 算法的，其原因在于，CATPE 算法无需进行搜索，其搜索次数始终为1。

图4 估计误差

图5 CATPE 和CMEBE搜索次数

6.4 系统总识别效率和识别时间

本节首先给出等时隙时长下的总的识别效率比较结果。图6给出了Optimal Q、GBT、CATPE 和CMEBE 4种协议在捕获效应概率从0变化到1.0的识别效率曲线。从图中可以看到，CATPE 的识别效率优于GBT和Optimal Q算法，其曲线与CMEBE的曲线基本重合。

下面再给出非等时隙时长的仿真结果。由于t0=50μs， t1=400μs，tk=200μs，相应地，α=0.125，β=0.2。由Bayes方法[8]可知，当不存在捕获效应时，最优帧长r*=1.7，因此给出本文的最优帧长与Bayes和CMEBE的对比结果。图7给出了第二帧中的标签平均识别时间随捕获效应概率变化的曲线图，其中之所以没有给出初始帧结果的原因是，初始帧中l0=128，n0=300，它并不满足最优帧长设置的条件。从图 7中可以看到，当 r*设置为1.7或按照 l=p+(1-p)n时，即Bayes和CMEBE的方法，其识别时间均比设置最优帧长的识别时间更长。表2还给出了在 α=0.125，β=0.2的情况下的系统识别效率P以及最优帧长线性系数 r*的值。

图6 系统识别效率

图7 标签平均识别时间

表2 α=0.125,β=0.5条件下 r*与 P

7 结束语

本文针对RFID动态帧时隙ALOHA协议，提出了一种在捕获效应下的RFID标签防冲突协议，实验仿真结果说明，该协议系统识别效率要高于现有的GBT和Optimal Q协议算法，与CMEBE协议相接近，但其计算复杂度却低于 CMEBE。另外，本文还推导出了在非等时隙时长下的线性最优帧长设置，仿真结果显示，在满足该最优帧长条件下，标签的平均识别时间要少于传统的 Bayes和CMEBE方法。

[1]WELBOURNE E,BATTLE L,COLE G. Building the Internet of things using RFID: the RFID ecosystem experience[J]. IEEE Internet Computing,2009,13(3):48-55.

[2]FINKENZELLER K. RFID Handbook: Radio-frequency Identification Fundamentals and Applications[M]. England: John Wiley and Sons,2003.

[3]SHIN D H,SUN P L,YEN D C. Taxonomy and survey of RFID anti-collision protocols[J]. Computer Communications,2006,29(11):2150-2166.

[4]SCHOUTE F C. Dynamic frame length aloha[J]. IEEE Transaction on Communication,1983,31(4):565-568.

[5]VOGT H. Efficient object identification with passive RFID tags[A].Proceedings of International Conference on Pervasive Computing[C].Zurich,Switzerland,2002. 98-113.

[6]LEE S R,JOO S D,LEE C W. An enhanced dynamic framed ALOHA algorithm for RFID tag identification[A]. Proceedings International Conference Mobile and Ubiquitous Systems[C]. San Diego,USA,2005. 1-5.

[7]CHEN W T. An accurate tag estimate method for improving the performance of an RFID anticollision algorithm based on dynamic frame length ALOHA[J]. IEEE Transactions on Automation Science and Engineering,2008,6(1):9-15.

[8]吴海锋,曾玉. 自适应帧ALOHA的RFID标签防冲突协议[J]. 计算机研究与发展,2011,48(5): 802-811.WU H F,ZENG Y. ADFA protocol for RFID tag collision arbitration[J]. Journal of Computer Research and Development,2011,48(5):802-811.

[9]BONUCCELLI M A,LONETTI F,MARTELLI F. Tree slotted ALOHA: a new protocol for tag identification in RFID networks[A].Proceedings of International Symposium on a World of Wireless[C].NY,USA,2006. 1-6.

[10]WU H F,ZENG Y,Efficient framed slotted aloha protocol RFID tag anti-collision[J]. IEEE Transactions on Automation Science and Engineering,2011,8(3):581-588.

[11]CAPETANAKIS J I. Tree algorithms for packet broadcast channels[J].IEEE Trans Information Theory,1979,25(5):505-515.

[12]HUSH D R,WOOD C. Analysis of tree algorithm for RFID arbitra-tion[A]. Proc IEEE International Symposium on Information Theory[C]. Cambridge,UK,1998. 107-117.

[13]冯波,李锦涛,郑为民. 一种新的 RFID 标签识别防冲突算法[J].自动化学报,2008,34(6):632-638.FENG B,LI J T,ZHENG W M. A novel anti-collision algorithm for tag identification in RFID systems [J]. Acta Automatica Sinica,2008,34(6):632-638.

[14]MYUNG J,LEE W J,SRIVASTAVA. Tag-splitting: adaptive collision arbitration protocols for RFID tag identification[J]. IEEE Trans Parallel and Distributed Systems,2007,18(6):763-775.

[15]QIAN C,NGAN H,LIU Y. Cardinality estimation for large-scale RFID systems[J]. IEEE Trans Parallel and Distributed Systems,2011,22(9):1441-1454.

[16]WU H F,ZENG Y,FENG J. Binary tree slotted ALOHA for passive RFID tag anti-collision[J]. IEEE Trans Parallel and Distributed Systems,2012,99:1-14.

[17]ORTA L T,MASELLI G,PETRIOLI C. Anti-collision protocols for single-reader RFID systems: temporal analysis and optimization[J].IEEE Trans on Mobile Computing,2011,10(2):267-279.

[18]LAI Y,HSIAO L. General binary tree protocol for coping with the capture effect in RFID tag identification[J]. IEEE Comm,Letters,2010,14(3):208-210.

[19]MAGUIRE Y,PAPPU R. An optimal Q-algorithm for the ISO 18000-6C RFID protocol[J]. IEEE Trans Automation Science and Engineering,2009,6(1):16-24.

[20]ISO/IEC 18000-6. Information technology—radio frequency identification(RFID)for item management—Part 6: Parameters for air interface communications at 860MHz to 960MHz,Amendment1: extension with type C and update of types A and B[S].

[21]EPC radio-frequency identification protocols class-1 generation-2 UHF RFID protocol for communications at 860MHz-960MHz Version 1.1.0 Draft1[S]. EPCglobal Inc,2005.

[22]KHANDELWAL G,YENER A,LEE K. ASAP : A MAC protocol for dense and time constrained RFID systems[A]. Proc of IEEE International Conference on Communications[C]. Istanbul,Turkey,2006.4028-4033.

[23]ISO/IEC 18000-6. Information technology—radio frequency identification(RFID)for item management—Part 6: Parameters for air interface communications at 860 MHz to 960 MHz[S].

[24]LI B,WANG J Y. Efficient anti-collision algorithm utilizing the capture effect for ISO18000-6C RFID protocol[J]. IEEE Commun Lett,2011,15(3):352-354.

[25]WONG C P,FENG Q. Grouping based bit-slot ALOHA protocol for tag anti-collision in RFID systems[J]. IEEE Commun Lett,2007,11(12):946-948.