基于序贯线性贝叶斯的RFID标签数量估计算法

王 帅, 杨晓东

(河南理工大学 电气工程与自动化学院，河南 焦作 454000)(*通信作者电子邮箱wangs2680@163.com)

0 引言

射频识别(Radio Frequency IDentification, RFID)技术是构建物联网应用的基础，与传统条形码技术相比，具有应用灵活、通信距离远、穿透性强和存储容量大等优点，目前已广泛用于物流、工农业生产和自动控制领域，在物体识别、产品管理和过程控制等方面发挥了巨大作用。RFID系统由读写器和标签构成，由读写器发出查询命令，处于读写器识别范围内的标签响应该命令并返回相应信息。目前应用的大多数标签为低成本的无源标签。无源标签从接收的读写器信号中获取能量，结构简单，但不具备信道监听能力，因此当多个标签同时处于读写器识别范围内时，读写器发出查询命令后，可能会有两个或两个以上的标签同时作出应答，这种情况称之为碰撞，产生碰撞后读写器将无法获取正确的标签信息。如果待识别的标签数量较多，频繁的碰撞将大幅降低标签读取成功率，需要设计有效的防碰撞算法提高识别效率[1-2]。在标签识别过程中防碰撞算法要根据待识别标签数量的变化进行参数调整和优化，因此标签数量估计是防碰撞算法设计的重要内容[3-6]。

本文针对目前标签数量估计算法中高精度算法复杂度较高，而低复杂度算法精度又难以满足实际要求的现状，提出了一种基于序贯线性贝叶斯的标签数量估计方法。该方法利用线性贝叶斯理论，将标签数量估计问题转化为线性模型，在充分利用观测信息保证估计精度的同时，通过线性拟合显著降低了算法复杂度，提高了估计方法的实用性。

1 相关工作

目前基于ALOHA的防碰撞算法广泛用于UHF(Ultra High Frequency)频段的标签，其中以动态帧时隙ALOHA(Dynamic Frame Slotted-ALOHA，DFSA)应用较为普及。在DFSA算法中，多个时隙组成一帧，读写器通过Query命令启动一帧的开始，标签在一帧内随机选择一个时隙发送数据。当前帧被成功识别的标签不参与下一帧的竞争，直至收到新的Query命令。采用这种方式，随着识别过程的进行，标签数量越来越少，直至所有标签被识别为止。在DFSA算法中，标签数量估计是决定算法性能的重要环节，DFSA算法需要根据估计的标签数量决定每一帧的长度。帧长和标签数量的差异对识别效率有着直接的影响:当帧长大于标签数量时，会产生过多的空闲时隙; 反之，当帧长小于标签数量时，碰撞时隙数会增多。理论上已经证明，当帧长与标签数量相等时，吞吐率可以达到最大[7]，因此标签数量估计的准确性是影响DFSA算法性能的重要因素。

目前的标签数量估计算法主要有两大类: 一种是采用固定因子或经验系数的估计方法[8-9]，该类算法具有复杂度小的优点，但估计误差较大; 另一种是根据设定的目标函数进行最优值搜索[10-11]，这类方法估计精度较高，但大范围的搜索也导致计算复杂度大，实用中受到很大局限。

(1)

其中:Si为成功时隙数量，Ci为碰撞时隙数量，L为帧长，k为固定系数，文中根据碰撞时隙所含的平均标签数量将其设为2.39。该算法的不足是以标签选择时隙概率服从泊松分布为假设条件，但实际中该假设并不严格成立，且当标签数量较多时算法误差较大。

文献[9]提出基于累计因子的标签数量估计算法，读写器接收第i帧后，根据上一帧估计的标签数量ni和累计因子d计算当前帧的标签数量ni+1：

ni+1=ni+d(2m+1-2m)

(2)

(3)

其中:m=「lbni⎤，d为累计因子，E、S和C分别为成功时隙、空闲时隙和碰撞时隙的数量，E0、S0和C0分别为相应时隙数量的期望值。该方法的局限是对标签数量初始值敏感，如果标签数量初始值与真实值差距较大，则需要多个帧的识别才能使标签数量估计值接近真实值，降低了识别效率。

基于最大后验概率的估计算法由文献[10]提出。该方法利用E、S和C计算后验概率：

(4)

其中:NS(n,S)为n个标签分配到S个时隙的分法数量，NC(n,S,C)为n-S个标签分配到C个时隙的分法数量。该算法通过搜索找出能使式(4)最大的n作为估计值。该方法虽然充分利用成功时隙、空闲时隙和碰撞时隙数量的信息，提高了估计精度，但估计值需要在较大范围内搜索才能求出，计算复杂度较高。

文献[11]提出了基于马氏距离的估计算法，首先计算成功时隙数量X1、空闲时隙数量X2和碰撞时隙数量X3与对应期望值间的马氏距离，然后选择使该距离D最短的标签数量作为估计值：

(5)

其中:X=(X1,X2,X3)，E[X]和C分别为X的期望值向量和相关矩阵。该方法将各类型时隙数量间的相关性考虑在内，当标签数量较大时估计值仍能保持较高的准确性，其缺点仍然是需要较大范围的穷举搜索，所需计算量较大，对硬件资源有较高的要求。

除以上算法外，研究者们还对一些特定场景的标签数量估计问题作了相关研究。如文献[12]研究了针对多个标签集合的组合数量估计问题，由分布于不同区域的多个读写器协同工作，通过数据融合算法统计满足指定条件的标签数量。该方法可以满足不同限定条件下的标签数量估计需求，但需要多读写器间的通信联络，且算法需要计算量较大的最优值搜索，对硬件要求较高；文献[13]给出一种ART (Average Run-based Tag estimation)算法，该算法通过分析连续非空时隙个数与标签数量的关系，推导出标签数量估计的解析表达式,利用较少的观测信息获得较高精度的估计值，提高了估计效率，但估计式需要复杂的数值求解，仍存在运算量大的问题。

以上所列算法中，基于固定因子的解析式算法复杂度较小，但对标签数量变化的适应能力较弱，当标签数量较多时估计精度难以满足要求。基于最优值搜索的算法精度较高，在标签数量较宽的变化范围内均能达到较高的精度，但运算律较大，在应用中受到硬件条件的制约。针对现有算法存在的问题，本文利用线性贝叶斯理论推导出标签数量的线性估计式，估计式中的待定系数通过计算量较低的序贯方式求出。该方法以解析形式给出标签数量估计的最优解，避免了消耗大量资源的穷举搜索，同时通过待定系数的实时更新提高了对标签数量变化的适应能力，提高了算法的实用价值。

2 标签数量估计问题建模

(6)

设每个时隙为空闲、成功和碰撞的概率为p1、p2和p3，根据式(6)可得:

p1=B(0)=(1-1/L)n

(7)

(8)

p3=1-p1-p2

(9)

(10)

式中:a1、a2、a3和a4是待定系数。为了降低算法复杂度，可根据待求问题的特点作进一步简化。首先，由于M1为空闲时隙个数，空闲时隙不含标签，因此可忽略其对标签数量的贡献，将a1设为0。其次，由于每个成功时隙仅含一个标签，可以将a2设为1。综合以上，由于M3=Lob-M2-M1，令a=a3，a0=a4+a3Lob，可以将式(10)简化为以下形式：

(11)

这样经过简化后，标签数量估计值只与M1、M2有关，且仅有2个待定系数a和a0。

问题1 对于式(11)的线性估计模型，问题的目标是选择a和a0以最小化下面的MMSE函数：

(12)

式中E[·]是求数学期望的运算。

一般来说，标签数量与观测的M1、M2和M3呈非线性关系，采用线性模型会产生估计精度上的损失，但收益则是运算复杂度上的大幅降低。当一个帧中的碰撞时隙数量比例不是很大时，线性模型可以实现较好的近似。

综合式(11)、(12)，可以得到计算标签估计值的定理1。

定理1 对于由式(11)给出的标签估计值与空闲、成功和碰撞时隙个数的线性模型，通过求解问题1可获得该式中的待定系数a和a0为：

a0=E[n]-(-aE[M1]+(1-a)E[M2])

(13)

(14)

其中:M=(M1,M2)，Τ1=-(1,1)，Τ2=(0,1)，CMM是M的2×2协方差矩阵，CnM是n和M的1×2互协方差矢量。

证明

根据问题1的定义推导式(11)中的最佳待定系数。把式(11)代入式(12)，可得:

(15)

(16)

由式(16)可解出a0为:

a0=E[n]-(-aE[M1]+(1-a)E[M2])

(17)

将式(17)代入式(15)，可得:

(-aE[M1]+(1-a)E[M2])]2}=

E{[(aΤ1′+Τ2′)(M-E[M])-(n-E[n])]2}=

(18)

(19)

将式(13)和式(14)代入式(11)即可求出标签数量估计值。注意到式(13)和(14)是闭式解，只需求出n和M1、M2的统计量即可代入直接计算，避免了传统估计算法中常见的极值搜索操作，可以大幅简化算法的运算量。

3 M1、M2和n的序贯统计量计算

为了求出a0和a的值，首先需要求出n和M1、M2的一阶和二阶统计量E[n]、E[M1]、E[M2]、CMM和CnM。这些统计量可以在标签识别过程中以序贯的方式求出，以减少运算量。具体做法是，读写器在识别标签的过程中，每接收到一个新时隙，根据上一次求出的统计值和本次时隙状态的观测值更新各个统计量。下面详细介绍各统计量的序贯式求解方法。

因n的分布一般很难精确确定，实际中往往只能给出n的大致范围，因此本文假定n服从均匀分布，即n～U(nmin,nmax)，nmin和nmax分别为标签数量的下限和上限。

为了后续推导的方便起见，将推导中用到的变量和自定义函数定义如下：

δ=1-1/L

(20)

γ=1-2/L

(21)

Θ=nmax-nmin+1

(22)

Π=nmax+nmin

(23)

(24)

(25)

(26)

假定n服从均匀分布U(nmin,nmax),其中nmin和nmax分别为标签数量的下限和上限。对于帧长为L的一帧，将其中的时隙顺序编号为1～L。对于第l个时隙，定义两个二值随机变量il和sl：

在n已知的前提下，il和sl的条件期望如(27)和(28)所示:

E[il|n]=0+1×P(il=1|n)=(1-1/L)n

(27)

E[sl|n]=0+1×P(sl=1|n)=(n/L)(1-1/L)n-1

(28)

由于n服从均匀分布U(nmin,nmax)，其期望值容易求出：

E[n]=(nmax+nmin)/2=Π/2

(29)

使用记号X(k)表示接收到第k个时隙时统计量X的值。为简化起见，令A～H替代推导过程中的一些常值表达式。已知第k个时隙的统计量，接收到第k+1个时隙时各统计量的更新表达式推导如下：

M1的期望值为：

(k+1)A=Ek[M1]+A

(30)

同样可得M2的期望值：

(k+1)C=E(k)[M2]+C

(31)

对CnM=(CnM1,CnM2)，可以求出

(32)

(33)

kB+k(k-1)F-(k+1)2A2=

(34)

采用同样方式，可以得到:

(k+1)C/L+k(k+1)G/L2-(k+1)2C2=

(35)

对于CM1M2，可以求出:

(36)

4 算法复杂度分析

在实际应用中，受硬件计算资源的限制，算法复杂度是衡量算法实用性的重要指标。首先分析本文算法的复杂度。不失一般性，假设n服从均匀分布U(0,nmax)。由于乘法计算量要远大于加法，因此本文只以乘法运算次数作为评估计算复杂度的指标。在计算第1个时隙时，要首先计算出δ和γ，因为这两个量是其他函数和表达式的基本因子。很明显，计算这两个量所需的乘法数为2nmax。经过简单计算，可以依次得到Γ1(x)、Γ2(x)、Γ3(x)的乘法次数分别为4、7、20，每个时隙计算统计量所需总乘法次数为14，计算a0和a需乘法次数为2和16，计算式(11)需乘法次数为2。综合以上各项，总乘法数可以求出为2nmax+65。当计算后续时隙时，各统计量在原有统计量的基础上更新，只需计算增量部分的乘法次数，每个时隙总计需乘法次数为34，与nmax无关，即计算复杂度都为O(1)。另外，逐时隙估计[1]和累计因子[2]的标签估计式都为解析形式，计算式(1)和式(2)的乘法次数分别为4次和5次，因此计算复杂度都为O(1)。

另一个高精度标签估计算法是文献[11]提出的马氏距离估计算法。该算法采用与最大后验概率估计方法类似的穷举搜索方式寻找最优估计值。每次计算式(5)需要36次乘法，整个搜索过程共需要36nmax次乘法，复杂度为O(n)。虽然该算法的复杂度与nmax呈线性关系，但当nmax较大时序贯线性贝叶斯算法与之相比仍具有明显优势。另外，序贯线性贝叶斯算法在估计精度方面要优于该算法，具体的性能比较可见后面的仿真结果。

5 性能仿真

为验证算法的有效性，将本文提出的序贯线性贝叶斯算法与现有四种算法逐时隙估计[8]、累计因子[9]、最大后验概率[10]和马氏距离[11]进行性能比较。首先比较标签数量估计精度，帧长为64，标签数量设为50。

如图1所示，随着观测时隙数的增加，各算法的估计精度都逐渐提高，说明样本数的增加可以使估计更加准确。同时还可看出，随着观测时隙数的增加，各算法的估计值都逐渐趋向于稳定，在观测过程中序贯线性贝叶斯方法的误差始终小于其他算法，且具有更快的收敛速度，当观测时隙数为16时估计误差已小于10%，观测时隙数为帧长一半时误差近似为4%。这说明序贯线性贝叶斯算法可以在观测时隙数较少的情况下给出更精确的估计，使系统可以更早地作出正确的帧长调整，这将减少整个识别过程的时间消耗。

图2比较了序贯线性贝叶斯与其他算法在识别效率上的性能差异。一个完整的RFID识别过程包括初始帧和其后的若干个帧，设初始帧的帧长为128，用识别标签所需的全部时隙数目评价算法的识别效率。由图2可见，在5种算法中，使用序贯贝叶斯方法识别全部标签耗时最少，识别效率最高，当标签数量为100和200时所需时隙数分别为260和540。序贯贝叶斯识别效率高的主要原因有: 一是标签数量估计精度高，可使每个识别帧的长度接近最优值；二是由于采用序贯式估计方式，当标签数量与帧长不匹配时，可以及时结束当前帧，使用最优帧长启动下一帧，从而进一步缩短了识别时间。

图1 标签数量估计精度比较

图2 识别所有标签所需的时隙总数

读写器与标签通信过程需要的总帧数也是影响识别效率的重要因素，总帧数越多，用于握手过程的通信开销就越大。图3比较了几种算法需要的总帧数。逐时隙估计算法由于估计精度最低，所需总帧数最多，而累计因子、最大后验概率和马氏距离的估计精度依次提高，所需总帧数也相应减少。本文提出的序贯贝叶斯由于具有较高的标签数量估计精度，每帧长度接近最优帧长，标签成功读取率高，在5种算法中所需总帧数最少，当标签数量为100和200时所需帧数分别为8和10，可以有效减少通信开销，提高识别效率。

图3 识别标签所需的总帧数

图4比较了几种算法的计算复杂度，为便于观察，采用自然对数坐标表示。如图4所示，最大后验概率算法算法由于所需乘法数与标签数量的平方成正比，复杂度在三种算法中最高，随标签数量的增加上升速度最快。马氏距离的复杂度与标签数量呈线性关系，增长幅度较为缓慢。累计因子、逐时隙估计和序贯线性贝叶斯算法复杂度为O(1)，算法复杂度受标签数量影响最小。当待识别的标签数量较多时，序贯线性贝叶斯算法的这种特性具有很大的优势，可以大幅降低计算复杂度，节省计算资源和能量消耗，尤其适用于移动读写器这种资源受限的设备。

图4 不同标签数下算法复杂度比较

表1列出了不同标签数量估计算法的性能对比。基于序贯线性贝叶斯的估计算法由于使用线性模型并充分利用了时隙状态信息，能够在保证高精度的同时减少计算复杂度，使其在计算资源有限的条件下仍能实现准确的估计。

表1 不同标签数量估计算法性能比较

6 结语

本文在分析比较现有标签数量估计算法的基础上，将序贯线性贝叶斯理论应用于标签数量估计，提出了随时隙更新的标签数量估计算法，推导了估计式和各阶统计量的闭式表达式。该算法可与DFSA协议有效结合，每接收到一个时隙后及时计算标签数量并调整帧长，大幅提高标签识别效率。所提的算法在保证高精度估计的同时，通过序贯式更新统计量的方式，显著降低了计算复杂度，提高了算法的实用性。