王　阳　吴海锋　曾　玉

(云南民族大学电气信息工程学院　昆明　650500)(374697699@qq.com)



稠密RFID标签环境下捕获感知贝叶斯标签估计

王阳吴海锋曾玉

(云南民族大学电气信息工程学院昆明650500)(374697699@qq.com)

摘要动态帧时隙Aloha算法是一种常用的被动式射频识别(radio frequency identification, RFID)标签防冲突算法.在该算法中，帧长需要动态设置以保证较高的识别效率.通常，帧长的设置与标签数和捕获效应的发生概率相关.传统的估计算法虽然可以估计出标签数和捕获效应的发生概率，但是在稠密RFID标签环境下，标签数可能远大于初始帧长，其估计误差会显著增加.为了解决传统算法无法应用于稠密RFID标签环境的问题，提出了捕获感知贝叶斯标签估计，并且给出了非等长时隙下最优帧长的设置方法.从实验结果来看，提出算法的估计误差在稠密RFID标签环境下显著低于传统算法，而且根据估计结果设置帧长所得到的识别效率也高于传统算法.

关键词Aloha算法；射频识别；捕获感知；稠密；贝叶斯估计

射频识别(radio frequency identification, RFID)技术是物联网前端传感器的关键技术之一[1]，与传统的条形码相比，RFID技术的识别效率较高[2].RFID系统工作时，可能会有多个标签同时处于阅读器的磁场工作范围内，由于标签均采用共享无线信道与阅读器进行通信，因此当有2个或2个以上的标签同时占用信道时，就会导致冲突[3].当然，2个或2个以上的标签并不一定必然导致冲突.由于标签离阅读器的距离远近不一、发射的信号有强有弱，信号较强的标签会被阅读器识别，而信号较弱的标签则会被阅读器所忽略，这种现象称为捕获效应[4].由于捕获效应在RFID系统中普遍存在，因此如何在捕获效应发生的情况下解决标签冲突问题已得到越来越多的关注[4-7].

动态帧时隙Aloha算法[8-12]是一种常用的标签防冲突算法，在该算法中标签识别由若干个帧构成，标签只能在某个帧中随机选择一个时隙与阅读器通信.每个帧的帧长需要动态变化以保证较高的识别效率，最优帧长的设置需要标签数和捕获效应发生概率的信息[6-7].通常标签数和发生概率对阅读器均未知，因此需要对其估计.针对上述问题，本文提出了一种捕获感知贝叶斯标签估计方法，其主要贡献有2点：

1) 解决稠密RFID标签环境下的标签估计问题.在稠密RFID标签环境下，标签数可能远大于初始帧长，传统算法的估计误差会大幅增加.本文提出的算法通过判断初始帧中头几个时隙的状态来调整初始帧长，保证了在稠密RFID标签环境下可准确估计标签数和捕获效应概率.

2) 提出了一种可同时估计标签数和捕获概率的贝叶斯方法.通过采用不同的代价函数，推导出3种贝叶斯估计，它们可同时估计出标签数与捕获效应概率，进而可以根据估计值设置最优帧长，提高系统识别效率.

从实验结果来看，本文提出算法的估计误差要小于传统算法，特别是在稠密RFID标签环境下，标签估计误差要显著低于传统算法，而且具有较高的识别效率.

1问题提出

在被动式RFID系统中，标签随机选择一个时隙向阅读器发送信息，对于一个给定的时隙只可能产生3种情况：没有标签、有1个标签和有1个以上的标签选择时隙发送信息.在无捕获效应发生的情况下，这3种情况分别对应空、成功和冲突时隙，相应地，识别效率可定义为成功时隙的占用时间与总时隙时间的比值.在动态帧时隙Aloha算法中，帧长过长会导致空时隙增多，而帧长过短会导致冲突时隙增多，这均会降低系统的识别效率.因此，每个帧长需要动态调整以保证识别效率的最优.由于无捕获效应情况下，成功时隙数仅由帧长与标签数的相互关系来确定，所以最优帧长设置也只与标签数相关[3,9].此时，只需估计标签数即可.然而，当捕获效应发生时，有1个以上的标签选择同一时隙也能产生成功时隙，所以最优帧长设置还与捕获效应发生概率相关[6].因此，捕获效应下的最优帧长需要同时估计标签数和捕获效应概率.仅仅通过估计标签数来确定帧长，并不能使RFID系统的识别效率在捕获效应下达到最优.

2相关工作

Vogt算法[9]是针对动态帧时隙Aloha系统而提出的1种标签估计方法，该方法通过搜寻空、成功和冲突时隙数观测值与其期望值间最小值来估计标签数.然而由第1节所述，该算法仅估计标签数来设置帧长，在捕获效应下并不能保证最优的识别效率.CMEBE(capture-aware backlog estimation method)算法[6]对Vogt算法做了改进，它采用二维搜索最小值来同时估计标签数和捕获效应的发生概率.然而，在稠密RFID标签环境下，标签数可能会远大于初始帧长，这会导致被搜索函数的最小值不存在，使得算法无法准确估计.

CAE(capture-aware estimation)算法[7]也是一种可以同时估计标签数和捕获效应概率的算法，相比于CMEBE算法，它无需进行搜索极值，仅通过一步计算便可估计出结果，因此计算复杂度得到了降低.然而，CAE算法需对空时隙数求对数，在稠密RFID标签环境中，标签数远大于帧长时，空时隙数的观测值可能为零，此时的计算结果将不存在.MAP算法[13]也是一种通过搜索极值来同时估计标签数和捕获效应概率的算法，但是该算法与CMEBE一样，当应用于稠密RFID标签识别环境时，极值将不存在.

将贝叶斯应用于RFID标签估计其实并不是一种新方法，文献[12]已提出了3种贝叶斯方法来估计标签.然而同Vogt方法一样，该方法仅仅估计标签数，并未考虑捕获效应问题.针对上述算法存在的问题，本文提出了一种新的贝叶斯估计方法，该方法考虑了捕获效应概率的估计问题，而且能在稠密RFID标签环境下仍然保证估计的准确性.

3捕获效应与动态帧时隙Aloha的效率

在RFID动态帧时隙Aloha协议中，标签的识别过程被分为若干个帧，而每个帧又被分为若干个时隙.标签在每个帧中只能随机选择一个时隙向阅读器发送信息，对于一个给定的时隙中没有标签、有1个标签和有1个以上标签发射信号的发生概率分别为[9-11]

(1)

其中，n为标签数，l为帧长，k为大于1的整数.这3种情况对应的时隙数则分别为

(2)

如果发生捕获效应，那么即使有2个标签发送信息，也可产生可读时隙.此时，空、可读和冲突时隙的发生概率分别为[6]

(3)

其中，α为捕获效应的发生概率.此时，空、可读和冲突时隙数的期望值a0，a1，ak可表示为

(4)

在Aloha协议中，当前帧中发生冲突的标签和被捕获效应隐藏的标签将进入下一个帧中继续被识别，直至所有的标签被阅读器全部识别，识别过程结束.RFID动态帧时隙Aloha中每个帧的长度动态变化，以保证较高的识别效率.若在该算法中，识别所有标签需要若干个帧，那么第i个帧的识别效率期望值可以定义为

(5)

其中，t0，t1，tk分别为空、可读和冲突时隙所占用的时间.通过把式(2)和式(4)代入式(5)后可知，Ps是关于标签数n和捕获效应概率α的函数，而n和α的值通常预先未知，因此要求得Ps的最优效率，需要对这两者进行估计.

4捕获感知的标签估计

4.1贝叶斯估计

本节将讨论采用贝叶斯方法的捕获感知标签估计，由于该方法不仅能估计标签数n，还能估计捕获效应概率α，因此具有捕获感知能力.该估计表达式为

(6)

(7)

其中:

C=c0,c1,ck.

(8)

集合Ω和Α分别表示为

(9)

其中，Nmax为系统所能读取标签数的最大值.

对式(6)采用3种不同的代价函数可得到3种形式的贝叶斯估计，贝叶斯均方估计的代价函数为

(10)

(11)

其中:

(12)

贝叶斯绝对估计的代价函数为

(13)

同理，把式(13)代入式(6)后可得：

(14)

贝叶斯均匀估计的代价函数为

(15)

其中，Δ为很小的常数.把式(15)代入式(6)可得：

(16)

式(16)的结果与文献[13]的估计方法具有相同的形式，实际为最大后验概率估计.

4.2稠密标签环境下的估计

在稠密RFID标签环境下，由于在阅读器的阅读范围内标签数n较大使得n≫l，因此可能发生空时隙数c0=0的情况.与Vogt，CMEBE一样，贝叶斯估计也是一个求极值的问题，当c0=0时，目标函数将不存在极小值.因此，4.1节的贝叶斯估计也不能直接用于稠密标签环境下.由于c0=0的原因在于n≫l，为此，我们可以加大帧长l直至c0≠0.然而，c0的值通常在一个帧结束后才能得到，若n≫l，则意味着该帧结束后将产生较多的冲突时隙，使得识别时间增大.其实，我们只需判断该帧的前几个时隙的状态就能预测是否c0=0，从而减少过多的冲突时隙.下面，我们将阐述该方法.

在动态帧时隙Aloha协议中，当标签数为n、帧长为l时，该帧中前m个时隙均不空的概率为

(17)

表1给出了当l=128，α=0.5，n取值为100～1 000时，P1，P2，P3，P4，P5的理论值和实际值，其中括号内为实际值.从表1可以看到，无论m取何值，Pm均会随着n的增大而增大，特别当n=1 000时，Pm接近于1.该结果表明，n值较大时，一个帧中前m个时隙均为非空的可能性也逐渐增大；而在稠密标签识别环境下，前m个时隙将很有可能均为非空.据此，当前m个时隙均为非空时，我们可通过

(18)

来调整初始帧长，其中K>1以保证帧长是在加大.注意到式(18)中，我们并不是如文献[15]中判断前m个时隙是否均为冲突，其原因在于，当存在捕获效应时，即使一个时隙有多个标签同时选择，也可能产生一个成功时隙而不是冲突时隙.

Table 1Probability that All of the FirstmSlots Are Non-idle Whenl=128 andα=0.5

表1　当l=128，α=0.5时前m个时隙都为非空的概率

Note: The values given in the brackets are computed from

equation (17).

5最优帧长设定

文献[5-9]中讨论了如何在动态帧时隙Aloha中设定最优帧长，然而这些方法均假定3种时隙所占用的时间相同.在实际的RFID系统中，如EPC C1 Gen2标准中[16]，空、成功和冲突时隙所占用的时间并不相等.因此，我们需要在非等长时隙下设置最优帧长.考虑一种线性模型，即帧长l与标签数n具有线性关系l=rn[12]，那么:

(19)

(20)

所以将式(2)(4)和式(19)(20)同时代入式(6)中，并令β=t0t1，γ=tkt1，化简后得：

Ps≈

(21)

让识别效率达到最大，我们有：

(22)

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

(23)

下面，我们给出在稠密标签环境下帧长设定的完整算法步骤：

1) 初始帧长为l=l0；

2) 阅读器向标签发出带有l的指令，标签在第1～l个时隙中随机应答；

3) 判断一个帧中前m个时隙是否均为非空，如果条件满足，执行式(18)并使l=lnext，转到步骤2；否则，转到步骤4；

4) 完成该帧的标签识别，统计帧中空、可读和冲突时隙数，通过执行式(11)(14)或式(16)来估计标签数和捕获效应概率；

5) 根据估计值，由式(23)设置下一帧的最优帧长.

6数字实验结果分析

6.1系统设置

本节给出计算机数字实验结果来验证所提出的估计算法的性能.在仿真实验中，我们假定该RFID系统中只有1个阅读器，所有标签在被阅读器识别的过程中一直处于阅读器的磁场范围，而且在整个过程中标签数目不会发生变化.计算机仿真采用蒙特卡罗法，实验结果为500次独立实验的平均值.我们把本文提出的TBMS，TBAV，TMAP算法与现有的CMEBE，CAE,Vogt,Traditional Bayes算法进行对比，这些算法分别是：

1) TBMS为二维贝叶斯均方估计(two-dimen-sional Bayesian mean square estimate)，其估计结果由式(11)(18)所得；

2) TBAV为二维贝叶斯绝对估计(two-dimen-sional Bayesian absolute value estimate)，其估计结果由式(14)(18)所得；

3) TMAP为二维贝叶斯最大后验概率估计(two-dimensional Bayesian maximum posterior probability estimate)，其估计结果由式(16)(18)所得；

4) CMEBE,CAE,Vogt,Traditional Bayes分别是在文献[6-7,9,12]中所介绍的算法.

以上这些算法的参数设置如下：

1) 初始帧长l0=128；

2) 标签数的搜索范围设置为Ν={c1+2ck≤n≤Nmax|n∈}，其中Nmax=1 000；

3) 捕获效应概率值的搜索范围A={0,0.1,0.2,…,1.0}；

4)m=3，即通过判断帧中前3个时隙的状态来调整帧长；

5)K=2，即调整的帧长为调整前帧长的2倍，之所以没有取更大的值是为了避免帧长调整过快而造成更多的空时隙；

6) 各个时隙占用时长分别为t0=50μs，t1=400μs，tk=200μs[12].

6.2估计误差

本节给出标签估计误差e的曲线图，e由式(24)给出：

(24)

Fig. 1　Estimation errors of tags (l=128,n=200,K=2,m=3).图1　标签估计误差(l=128,n=200,K=2,m=3)

图2给出了以上7种算法在标签数n=600时标签数n的估计误差e.从图2可以看到，CMEBE，CAE算法的估计误差大约在20%～35%之间波动；而TBMS，TBAV，TMAP这3种算法的估计误差不超过5%.该结果表明，当标签数远大于帧长值时，CMEBE，CAE算法的估计误差将远高于TBMS，TBAV，TMAP算法.另外，Vogt，Traditional Bayes算法的估计误差从25%变化至80%，显著高于其余5种算法，其原因同样在于，这些算法没有考虑捕获效应对标签数估计的影响.另外，TBMS，TBAV，TMAP算法的标签估计误差远低于其余算法，原因在于考虑到了稠密RFID标签环境对标签估计的影响.

Fig. 2　Estimation errors of tags (l=128,n=600,K=2,m=3).图2　标签估计误差(l=128,n=600,K=2,m=3)

6.3识别效率

本节给出各个算法识别效率的对比结果，图3为Vogt，CMEBE，CAE，Traditional Bayes，TBMS，TBAV，TMAP算法通过估计结果设置帧长后所得到的系统识别效率曲线.其中，识别效率由式(6)给出，标签数n=600.当CAE无法估计出标签数时，则将估计值取标签数的搜索范围Ν的上限值.由于t0=50μs，t1=400μs，tk=200μs，所以可以得到β=0.125，γ=0.5.各个算法的最优帧长具体设置方法如下：

Vogt算法最优帧长设置为[9]

(25)

Traditional Bayes算法最优帧长设置为[12]

(26)

CMEBE和CAE算法采用相同的最优帧长设置方法，即[6-7]

(27)

TBMS，TBAV，TMAP算法的最优帧长由式(21)(22)(23)得到，其具体值由表2给出.

Fig. 3　Identification efficiency (l=128,n=600,K=2,m=3).图3　识别效率(l=128,n=600,K=2,m=3)

αl*Ps0.19600.73490.29000.75300.37800.77260.47200.79380.56000.81720.65400.84320.74200.87280.83000.90740.91800.94961.0601.0000

Notes:t0=50μs,t1=400μs,tk=200μs.

从图3可以看到TBMS，TBAV，TMAP算法的曲线处在最上方;而Vogt，Traditional Bayes算法的曲线处在最下方;CMEBE，CAE算法的曲线处在它们之间.将图3和图2结合起来可知，算法的估计结果与识别效率密切相关，估计误差较低的算法识别效率较高，而具有较高估计误差算法的识别效率较低.另外，由于TBMS，TBAV，TMAP采用了非等长时隙最优帧长设置方法，其识别效率也高于采用等长时隙最优帧长设置的其他方法.

7结论

本文针对RFID动态帧时隙Aloha系统提出了新的贝叶斯估计方法，并且为了得到最大识别效率还推导了最优帧长的表达式.根据本文的理论推导以及仿真结果可知，在标签数较少时，本文提出算法的估计性能与传统算法相近.然而，在稠密RFID标签环境下，即标签数远大于初始帧长，本文提出算法的估计误差要明显低于传统算法，而且，根据提出算法得到的系统识别效率也要高于传统算法.

参考文献

[1]Welbourne E, Battle L, Cole G, et al. 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]. 2nd ed. Hoboken, NJ: John Wiley and Sons, 2003

[3]Shin D H, Sun P L, Yen D C, et al. Taxonomy and survey of RFID anti-collision protocols[J]. Computer Communications, 2006, 29(11): 2150-2166

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

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

[6]Li B, Wang J Y. Efficient anti-collision algorithm utilizing the capture effect for ISO18000-6C RFID protocol[J]. IEEE Communications Letters, 2011, 15(3): 352-354

[7]Yang X, Wu H F, Zeng Y, et al. Capture-aware estimation for the number of RFID tags with lower complexity[J]. IEEE Communications Letters, 2013, 17(10): 1873-1876

[8]Schoute F C. Dynamic frame length Aloha[J]. IEEE Trans on Communication, 1983, 31(4): 565-568

[9]Vogt H. Efficient object identification with passive RFID tags[C] //Proc of Int Conf on Pervasive Computing. Berlin: Springer, 2002: 98-113

[10]Lee S R, Joo S D, Lee C W. An enhanced dynamic framed ALOHA algorithm for RFID tag identification[C] //Proc of Int Conf Mobile and Ubiquitous Systems: Networking and Services. Piscataway, NJ: IEEE, 2005: 1-5

[11]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 Trans on Automation Science and Engineering, 2008, 6(1): 9-15

[12]Wu Haifeng, Zeng Yu. Tag estimate and fame length for dynamic frame slotted ALOHA anti-collision RFID system[J]. Acta Automatica Sinica, 2010, 36(4): 620-624 (in Chinese)(吴海锋, 曾玉. RFID动态帧时隙ALOHA防冲突中的标签估计和帧长确定[J]. 自动化学报, 2010, 36(4): 620-624)

[13]Yang X, Wu H F, Tan Y, et al. Improving the performance of RFID tag anti-collision for capture effect[J]. Applied Mechanics and Materials, 2013, 416/417: 1484-1488

[14]Shen Fenglin, Ye Zhongfu, Qian Yumei. Statistics and Process of Signal[M]. Hefei: University of Science and Technology of China Press, 2003: 389-392 (in Chinese)(沈凤麟, 叶中付, 钱玉美. 信号统计分析与处理[M]. 合肥: 中国科学技术大学出版社, 2003: 389-392)

[15]Cui Y H, Zhao Y P. A modified Q-parameter anti-collision scheme for RFID systems[C] //Proc of Int Conf on Ultra Modern Telecommunications & Workshops (ICUMT’09). Piscataway, NJ: IEEE, 2009: 1-4

[16]EPCglobal Inc. EPC radio-frequency identification protocols class-1 generation-2 UHF RFID protocol for communications at 860MHz-960MHz version 1.1.0 draft1[S]. New York: EPCglobal Inc, 2005

Wang Yang, born in 1990. Master in communication and information systems from Yunnan Minzu University. His main research interests include mobile communi-cations and RF engineering.

Wu Haifeng, born in 1977. Received his PhD degree in communication and information systems from Sun Yat-sen University. Professor at the School of Electrical and Information Technology, Yunnan Minzu University. His main research interests include cooperative sensor networks, mobile communications, RF engineering and signal processing (whf5469@gmail.com).

Zeng Yu, born in 1981. Received her MSc degree in communication and information systems from Yunnan University. Lecturer at the School of Electrical and Information Technology, Yunnan Minzu University. Her main research interests include wireless network and mobile communications.

Capture-Aware Bayesian Tag Estimation for Dense RFID Tags Environment

Wang Yang, Wu Haifeng, and Zeng Yu

(SchoolofElectricalandInformationTechnology,YunnanMinzuUniversity,Kunming650500)

AbstractDynamic framed slotted Aloha algorithm is one kind of commonly used passive radio frequency identification (RFID) tag anti-collision algorithms. In the algorithm, the frame length requires dynamical set to ensure high identification efficiency. Generally, the settings of the frame length are associated with the number of tags and the probability of capture effect. Traditional estimation algorithms can estimate the number of tags and the probability of capture effect, but the number of tags is greater than an initial frame length when it is in dense RFID tags environment, and the estimation errors will increase significantly. In order to solve the problem that the conventional algorithms can not be applied to dense RFID tags environment, capture-aware Bayesian tag estimation is proposed in the paper, and the settings of optimal frame length with non-isometric slots are given. From the experimental results, the proposed algorithms have significantly lower estimation errors than traditional algorithms in dense RFID tags environment. And the identification efficiency got by setting the frame length according to the estimation results is also higher than that of traditional algorithms.

Key wordsAloha algorithm; radio frequency identification (RFID); capture-aware; dense; Bayesian Estimation

收稿日期：2014-12-23；修回日期：2015-06-08

基金项目：国家自然科学基金项目(61262091)；云南省第17批中青年学术和技术带头人资助项目(2014HB019)；云南省教育厅科学基金重大项目(ZD2011009)；云南省教育厅科学基金重点项目(2014Z093)

通信作者：吴海锋(whf5469@gmail.com)

中图法分类号TP393.04

This work was supported by the National Natural Science Foundation of China (61262091), the 17th Batches of Young and Middle-Aged Leaders in Academic and Technical Reserved Talents Project of Yunnan Province (2014HB019), the Project of Scientific Research Foundation of Yunnan Provincial Department of Education (ZD2011009), and the Project of Scientific Research Foundation of Yunnan Provincial Department of Education (2014Z093).