国内航空货运过程中的数据采集与关键环节的货物识别和跟踪等工作主要是通过人工方式来完成，由于在流程上人为因素较多，导致货物流通时间长，货损率相对较高。随着航空物流货运量的快速增加，使得人为因素所造成的货物处理效率低下问题更加突出。因此，航空物流产业急需信息化建设。

目前，射频识别(Radio Frequency Identification, RFID)技术^[1]被广泛应用于现代物流产业中，如仓库管理、资产管理、货物定位追踪等。与人工方式相比，RFID技术在进行信息采集与货物识别和跟踪时更加准确与快速。但在实际应用场景中大多数RFID标签无源且不具有载波监听能力，当阅读器阅读范围内同时存在多个标签时，若多个标签同时响应阅读器指令，会出现信号冲突，阅读器就不能准确识别出所有标签，这就是标签碰撞。多标签碰撞是影响RFID系统识别效率的主要原因之一。解决这个问题的算法称为标签防碰撞算法，而对标签数的准确估计是提高标签防碰撞算法效率的重要环节。

为了提高RFID标签防碰撞算法的效率，本文提出一种基于粗精二次估计的RFID标签数目估算方法。对多标签碰撞过程进行建模，构建了更具适应能力的标签估计解析式，在此基础上，与基于先验知识的最大后验概率估计方法结合，改善了标签估计准确性与复杂度之间的矛盾，在确保估计准确性与估计稳定性的前提下显著降低了估计的复杂度。

1 相关工作

RFID防碰撞算法主要分为基于ALOHA(Aloha protocol)的防碰撞算法^[2-4]和基于树的防碰撞算法^[5-6]两大类。基于ALOHA的防碰撞算法当前研究热点为动态帧时隙ALOHA算法，在原帧时隙ALOHA算法的基础上，通过利用标签数估计值动态调整帧长，提高了标签识别效率。基于树的防碰撞算法中，根节点表示最先发生碰撞的标签集合，随后阅读器不断分裂碰撞标签集合，构成一系列子集，直到每个子集中只有一个电子标签，阅读器完成对标签的识别。此类算法中由未识别的标签数量来确定碰撞标签集合分裂的数量，估计标签数量可以使集合分裂数量更合理，提高算法的时隙利用率。但阅读器识别区域标签数量通常是未知的，所以准确估计标签数量，有利于提高标签防碰撞算法的效率。

现有的标签估计算法主要分为解析式估计算法^[7-9]和区间搜索估计算法^[10-12]两类。解析式估计算法包括Low Bound估计算法、Schoute估计算法、基于空闲时隙估计算法等；区间搜索估计算法包括基于切比雪夫不等式估计算法和最大后验概率估计算法等。

Low Bound估计算法基于每个碰撞时隙中至少存在2个标签的原理，得出待估计标签数目的最低估计值N_tag：

${N_{{\rm{tag}}}} = S + 2C$

(1)

其中：S为识别时隙数量，C为碰撞时隙数量。在标签规模小于50时，Low Bound算法估计效率很高。但随着标签规模的增大，算法误差增长率也随之增大，所以Low Bound算法不能适应大规模标签估计。Schoute估计算法假设阅读过程中标签选择某一时隙的概率服从泊松分布，基于此假设得出每个碰撞时隙中平均包含的标签数目为2.39个，进而可以得出未识别标签的数目为2.39C，其中C为碰撞时隙的数量。此算法的估计准确率优于Low Bound算法，但标签选择时隙的概率并不严格服从泊松分布，这就造成算法效率的不稳定，同时在标签规模过大的情况下也不适用。基于空闲时隙估计算法主要思想是根据一帧中空闲时隙的理论期望值与实验中统计得出的空闲时隙数值的关系进行标签数量的估计。文献[7]中提出的Adaptive Slotted ALOHA Protocol标签估计算法与文献[8]中提出的Fast Zero Estimation算法都是基于空闲时隙的标签估计算法。但随着标签规模的增大，帧长度却不能一直增大，一个时隙为空闲时隙的概率会越来越小，因此基于空闲时隙的估计算法准确度也会下降。

基于切比雪夫不等式的估计算法由H.Vogt提出，利用空闲时隙、识别时隙、碰撞时隙的统计量与理论期望值的距离进行标签数量估计。搜索使得该距离取得最小值的理论期望值并确定其所对应的标签数量N_tag。定义两个空间向量(N_E, N_S, N_C)、(N₀(L, n), N₁(L, n), N_x(L, n))分别代表时隙统计值与时隙理论期望值。其中N_E、N_S、N_C分别为空闲时隙、识别时隙、碰撞时隙的统计量；N₀(L, n), N₁(L, n), N_x(L, n)分别代表帧长为L，标签数量为n时空闲时隙、识别时隙、碰撞时隙的理论期望值，则N_tag为：

${N_{{\rm{tag}}}} = \mathop {\min }\limits_n \left| {\left( {\begin{array}{*{20}{c}} {{N_E}}\\ {{N_S}}\\ {{N_C}} \end{array}} \right) - \left( {\begin{array}{*{20}{c}} {{N_0}\left( {L,n} \right)}\\ {{N_1}\left( {L,n} \right)}\\ {{N_x}\left( {L,n} \right)} \end{array}} \right)} \right|$

(2)

切比雪夫估计算法相比于Low Bound和Schoute具有更高的估计准确率，但是估计过程中运算量过大，不适合性能有限的嵌入式系统。文献[11]提出的基于最大后验概率的估计算法，不同于其他基于各时隙分布期望值的估计算法，此算法将最大后验概率准则应用到标签数量估计中，提高了估计的精度。但因为估计过程中搜索范围太大需要进行多次的运算，同样存在估计运算量过大的问题。

上述的估计算法虽然有各自的优势，但都存在一定的问题。解析式估计算法由于方法关系式固定，难以适应标签数动态变化较大、标签数量较多等场景。区间搜索估计算法实现复杂、计算量大，难以在性能较差的嵌入式设备中使用。

2 粗精标签估计算法 2.1 粗精标签估计算法流程

粗精标签估计算法结合粗估计的快速、精估计的准确和二次估计算法性能的稳定性，使得估计算法效率更高，适应场景更广。图 1为算法的流程。

基于粗精二次估计的RFID标签估计算法主要分为三部分：标签的粗估计、评估粗估计值的可信度、标签的精估计。首先初始帧长为L，进行一次读取后统计该读取周期内的反馈信息：空闲时隙数E、识别时隙数S、碰撞时隙数C。利用这些反馈信息计算碰撞时隙所占总时隙的比例B_c= C/L。根据建模分析得出的B_c与每个碰撞时隙中平均标签数n_u的关系构建出的解析式粗估计算法的表达式来计算第一次标签估计值N_r。粗估计之后需要对估计值N_r进行评估，评估标准由统计分析大量实验中读取周期内空闲时隙的比例范围得出，可随应用场景调整。若粗估计值满足评估要求，则对标签的估计完成。反之，需要进行二次精估计。精估计采用基于先验知识的最大后验概率估计算法。设定粗估计值N_r为二次精估计搜索的起点，通过一次后验概率的计算来确定搜索的方向，然后按照确定的起点与方向进行最大后验概率搜索，当满足搜索停止条件时停止搜索，并输出当前的标签估计值。

2.2 解析式粗估计

解析式粗估计的数学模型定义如下：设阅读器使用帧长度L，对N个标签进行读取，则选择同一时隙的标签数量为r，概率为P=1/L的二项分布。

${B_{n,\frac{1}{L}}}\left( r \right) = \left( {\begin{array}{*{20}{l}} n\\ r \end{array}} \right){\left( {1/L} \right)^r}{\left( {1 - 1/L} \right)^{n - r}}$

(3)

可以得出空闲时隙概率P_e、碰撞时隙概率P_c、识别时隙概率P_s。

${P_e} = B\left( {r = 0} \right) = {(1 - p)^N}$

(4)

${P_s} = B\left( {r = 1} \right) = Np{\left( {1 - p} \right)^{N - 1}}$

(5)

${P_c} = B\left( {r = x} \right) = 1 - {P_e} - {P_s}$

(6)

一次读取后统计出一帧中空闲时隙数为E、碰撞时隙数为C、识别时隙数为S，且E+S+C=L。

以此数学模型为基础有几种解析式估计方法。Low Bound估计算法与Schoute估计算法都是在假设每个碰撞时隙中的标签数量的基础上进行标签的估计，而每个碰撞时隙中标签的数量为固定的值，并不能随标签规模的增大而变化，所以随着标签规模增大估计误差也会大幅增加。空闲时隙标签估计算法优于以上两种估计算法的原因是可以根据空闲时隙所占比例的变化动态地估计标签的数量。如图 2所示空闲时隙的比例在N/L大于2.5时变化趋于平缓，标签数量的增加已经不能通过空闲时隙的比例得到体现，所以空闲时隙标签估计算法已经不再适用。根据这个思路观察图 2可以看出。

碰撞时隙所占比例B_c随N/L增加呈现单调变化，同时更加接近线性变化。所以用B_c来估计标签数量效果会更好。由于估计算法初始帧长固定，所以估计算法应不受不同帧长的影响。经过建模分析得出每个碰撞时隙中平均标签数n_u与碰撞时隙的比例B_c的关系不受帧长度影响。

图 3是帧长L分别为128、256、512，标签数从100~1 000的条件下，进行10 000次实验统计所得。由图 2可知，N/L小于2时，B_c小于0.6，N/L小于4时，B_c小于0.9。图 3中点的分布与此一致，可以看出：同等标签数量在不同帧长条件下n_u与B_c的关系稳定；当B_c变化时，n_u的变化呈现一定的规律性。按照n_u的变化率可划分成三个阶段，对三个阶段分别进行函数拟合。

图 4为n_u与B_c的分段拟合图，获得三段拟合曲线的数学表达式：

${n_u} = \left\{ {\begin{array}{*{20}{l}} {1.9 \times B_c^{1.7} + 2.2,{\rm{ }}}& {{B_c} ＜ 0.6}\\ {2.4 \times B_c^{4.6} + 2.8,}& {0.6 \le {B_c} ＜ 0.9}\\ {4.4 \times B_c^{46.5} + 4.5,}& {{B_c} \ge 0.9} \end{array}} \right.$

(7)

根据拟合曲线的数学表达式，阅读器在一次搜索后依据反馈信息可以简单地获取n_u的值，进而得出标签数粗估计的结果N_r。

${N_r} = {n_u} \times C + S$

(8)

2.3 标签估计值评价过程与标准

设定评价标准来评价粗估计得到结果的准确性，决定是否需要进行第二次估计。

图 5是不同实验条件下，一个读取周期后空闲时隙占总时隙比例分布图。图中理论值随着标签数量的变化稳定在0.367；实验数据是在最优帧长条件下(即L=N)，空闲时隙所占比例的分布；误差1(模拟标签估计值大于实际值)为在标签数量大于帧长5%的条件下，空闲时隙所占比例的分布；误差2(模拟标签估计值小于估计值)为在标签数量小于帧长5%的条件下，空闲时隙所占比例的分布。

分析图 5可知，当标签估计误差超过5%时，空闲时隙所占比例分布与估计准确的情况下的分布有很大不同。在标签数量小于200时分布有10%的重合，因为标签数量小于200时粗估计的准确度高，所以重合部分影响很小。根据上述规律，可以设计基于空闲时隙比例的标签估计值评价标准。如表 1所示，不同的标签数量对应着不同的空闲时隙比例范围。进行标签估计值评估的过程为：

1) 根据粗估计的标签数量初始化阅读器评估指标。

2) 设置帧长L为当前估计值的最优帧长。

3) 阅读器进行一次读取并统计这次读取周期内的空闲时隙个数。

4) 根据L计算空闲时隙所占的比例并判断是否符合评估的标准。

5) 若空闲时隙所占比例符合评估标准，粗估计的标签数量为可信值；反之，粗估计的标签数量不可信，需进行二次精估计。

1 000次最优帧长条件下的实验中有大约95%空闲时隙比例在标准比例范围中，标签估计值准确的情况下评估准确率为95%。标签估计值误差为5%时，2 000次实验中有9%在标准比例范围内，且大多都集中在标签数量小于200的区间，若标签估计误差合格范围设为5%，则标签估计值错误的情况下评估的准确率最小为91%。综上，基于空闲时隙的标签估计值评估标准对标签粗估计值的评估准确率可以达到92%。

2.4 基于先验知识的后验概率分布标签精估计

将帧时隙ALOHA防碰撞算法对标签的一次读取过程建模看作具有重复独立实验的多项分布(每个实验为帧中的一个时隙)，其中每个实验有三个结果：空时隙、识别时隙、碰撞时隙；且每个时隙是空时隙的概率为P_e，是识别时隙的概率为P_s，是碰撞时隙的概率为P_c，约束条件为P_e+P_s+P_c=1。

在帧长L的读取过程中，空时隙数量为E，识别时隙数量为S，碰撞时隙数量为C，这种情况发生的概率为P(E, S, C)。

$P\left( {E,S,C} \right) = \frac{{L!}}{{E!S!C!}}P_e^EP_s^SP_c^C$

(9)

P(E, S, C)为(P_e+P_s+P_c)^L多项式展开的一般项。因此，对于具有帧长度L的读取周期，当帧中时隙的分布为E个空时隙、S个识别时隙和C个碰撞时隙时，对于标签数量n具有后验概率，如下：

$\begin{array}{l} P\left( {n|E,S,C} \right) = \frac{{L!}}{{E!S!C!}}{\rm{ }} \times \\ \quad {\left[ {{{\left( {1 - 1/L} \right)}^n}} \right]^E}{\left[ {\left( {n/L} \right){{\left( {1 - 1/L} \right)}^{\left( {n - 1} \right)}}} \right]^S} \times \\ \quad {\left[ {1 - {{\left( {1 - 1/L} \right)}^n} - \left( {n/L} \right){{\left( {1 - 1/L} \right)}^{\left( {n - 1} \right)}}} \right]^C} \end{array}$

(10)

基于后验概率分布，确定使得概率最大化的标签数量n。因此，利用后验概率估计标签数量的决策规则为：搜索标签数量n_g=n使得P(n|E, S, C)取得最大值。

在一次读取周期中，若没有先验知识进行标签数量n_g的搜索则不能确定大致的搜索范围，而每次搜索计算P(n|E, S, C)的运算量很大。这就导致标签估计算法的效率很差，甚至在一些计算性能有限的系统中无法应用。

针对这一问题，提出基于解析式粗估计值的后验概率标签估计方法。该方法利用解析式估计的结果作为先验知识，根据粗估计的值N_r确定搜索的大致范围，通过结合N_r的大小和解析式估计的特点，决定搜索方向。

根据图 6所示，后验概率随标签数量的变化呈正态分布。在进行后验概率最优搜索时，以粗估计标签数量值N_r为开始，根据解析式估计在不同N_r大小时估计误差分布情况选择向前或向后搜索。

确定搜索结束的不同情况：第一次搜索利用N_r计算出后验概率P₁。根据确定的方向进行第二次搜索，会出现两种情况。

1) 若第二次搜索的后验概率P₂>P₁，继续按照此方向搜索，当后验概率值不再增加时，停止搜索，前一次搜索的n值即为标签的估计数。

2) 若第二次搜索的后验概率P₂＜P₁，改变搜索的方向，若第三次搜索的后验概率P₃＜P₁，停止搜索，P₁即为最大值。反之，按照改变后的方向继续搜索。当后验概率值不在增加时，停止搜索，前一次搜索的n值即为标签的估计数。

基于先验知识的最大后验概率标签估计算法工作流程如图 7所示。

基于解析式粗估计值的后验概率标签估计方法相较于基于后验概率的标签估计方法能减少大约90%的搜索范围，极大地降低了估计算法的运算量，提高了算法的运行效率。

3 算法仿真与分析

为了衡量基于粗精二次估计的RFID标签数目估算方法的性能，进行了基于Matlab软件平台的仿真测试。与之前的算法进行比较，从估计误差、稳定性和运算量的大小三方面来说明算法的性能。初始帧长设为128，标签量级为1 000以内。

3.1 估算误差

估计误差ε作为评估标签估计方法准确性的指标，定义如式(11) 所示，其中N_s为实际标签数，N_g为标签估计值。

$\varepsilon = \left| {{N_s} - {N_g}} \right|/{N_s}$

(11)

在标签随机分布的情况下不同估计方法的误差如图 8所示，随着标签数量的增加，不同标签估计方法的误差率变化趋势各异。Low Bound估计方法与Schoute估计方法误差变化趋势相近，Schoute估计方法在各个阶段均优于Low Bound估计方法。解析式估计的误差率随着标签数量的增加呈现出不稳定状态，估算误差在标签数量小于400时保持在5%以下，但在标签数量为500时误差率却达到10.33%；之后估算误差率保持在10%以下，但在标签数量为800时误差率剧增为42.38%。后验概率标签估计方法的误差率随着标签数量的增加变化比较平缓，误差率保持在5%~10%。基于粗精二次估计的标签估计算法的误差率随标签数量增加变化最平缓且误差率最低，算法的平均误差率为3.8%。

为了进一步评估不同估计算法的性能，固定标签数量，对各个估计算法在不同标签分布情况下的误差进行了比较。设定标签数量为500，标签分布分散级别为从1~10，级别1表示标签整体随机分布，位置没有明显规律，级别2表示标签聚集在2个不同位置上，以此类推级别10表示标签聚集在10个不同位置上。各个估计算法估计误差如图 9所示。

随着标签分布分散程度级别的增加，Low bound估计算法和Schoute估计算法误差率只有小幅的上升，但误差率都在40%以上。解析式估计算法的误差率从级别1到级别5表现平稳，保持在10%以下，但在级别5之后有大幅的增加，误差率在级别10时达到30%。最大后验概率估计算法的误差率前期表现与解析式估计算法相近，在级别5之下误差率保持在9%以下，但之后也出现了小幅的上升，最后误差率稳定在15%左右。粗精二次估计算法的误差率一直保持在5%以下，在级别7之后有小幅上升，但误差率一直保持10%以下。在不同标签分布分散级别下，粗精估计算法平均误差率为6%。

综上所述，相较于其他几种估算方法，粗精二次估计算法在不同标签数量和不同标签分布情况下的平均误差率都保持最低，所以粗精二次估计算法标签估计的结果更准确。

3.2 估计稳定性

标签估计是对一个随机过程进行估计，不可避免地会出现随机性误差，估计算法应该具备一定抵抗随机性误差的能力，这种能力被称为估计稳定性。定义估计稳定性的量化指标α=K_c/K_z，其中K_z为总的实验次数，K_c为估计成功的实验次数。估计成功定义为误差率小于5%。量化指标α的数值越大说明估计算法的稳定性越高，通过量化指标α来说明估计算法的稳定性。每个估计算法进行10 000次实验，次数在不同的标签数量下平均分布。

不同标签估计算法的稳定性如图 10所示，随着标签数量的增加，不同估计算法稳定性变化各异。Low Bound估计算法和Schoute估计算法的稳定性极差，在标签数量为100时取得最大值，分别为0.36、0.79，之后稳定性急剧下降。解析式估计稳定性相较于前两者有了大幅的提高，但随着标签数量的增加降低幅度太大，在标签数大于300时稳定性已经在0.6以下，之后稳定性总体呈下降趋势。后验概率估计稳定性在标签数量小于400时可以达到0.8以上，同时稳定性下降幅度也小于解析式估计。粗精二次估计由于结合了解析式估计与后验概率估计，具有更强的抵抗随机性误差的能力，其稳定性表现优于其余的估计算法。在标签数量小于600时稳定性变化幅度平缓保持在0.9以上，之后稳定性下降幅度有所增加，但相较于其他估计算法还是具有明显优势。

3.3 估计运算量

由于嵌入式设备的性能限制，标签估计算法在保持估计的准确性与稳定性的同时还需控制算法的运算量。

Low Bound估计算法和Schoute估计算法都是基于固定的计算公式，算法的运算量不随标签规模的增加变化，一直保持在1次加法运算和1次乘法运算。不同于上面两种估计算法，解析式估计算法的运算量会随着标签规模的增加有小幅增加。其中B_c的值随标签数量的增加而改变，当B_c＜0.6时，估计算法运算量为5次乘法运算和2次加法运算；当0.6＜B_c＜0.9时，估计算法运算量为8次乘法运算和2次加法运算；当B_c>0.9时，估计算法的运算量为50次乘法运算和2次加法运算。以上三种标签估计算法的计算复杂度为O(1)。当待估计标签数量是N_t时，最大后验概率估计算法的运算量约为$\sum\limits_{n = 1}^{{N_t}} {\left( {3L + 4n + 6} \right)} $次乘法运算和$\sum\limits_{n = 1}^{{N_t}} {6n} $次减法运算。最大后验概率估计算法的计算复杂度为O(n²)，待估标签数量比较大时，估计算法的计算量过大，不适合再进行标签数的估计。粗精二次估计算法第一次粗估计采用解析式估计，当粗估计结果满足评价标准时，算法结束，运算量与解析式估计算法相同。当粗估计结果不满足评价标准时，将粗估计值作为先验知识进行二次精估计，此时最大后验概率估计的搜索范围减少了90%左右，所以精估计的运算量约为最大后验概率估计算法的10%。总的来说粗精二次估计算法将90%的最大后验概率估计算法的运算量转换成了解析式估计的运算量，其计算复杂度约为O(n)。

表 2所示为不同标签估计算法的性能指标对比。粗精二次估计算法通过结合解析式估计与后验概率估计的优点，在保证低误差与高稳定性的同时降低算法的运算量。

图 11为不同标签数量下各估计算法运算时间的对比结果，Low Bound估计算法、Schoute估计算法与解析式估计算法的计算复杂度为O(1)，算法运行时间不受标签数量的影响，随着标签数量的增加，这三种算法的运行时间没有太大的变化。最大后验概率估计算法的计算复杂度为O(n²)，随标签数量的增加，算法的运行时间急剧增加。粗精二次估计算法的计算复杂度约为O(n)，随标签数量增加，算法的运算时间的增加趋势大致呈线性。对比最大后验概率估计算法，粗精二次估计算法的运行时间降低约90%。

4 结语

通过对RFID标签读写过程的建模分析，针对现有标签估计算法存在的估计准确性与算法复杂性之间的矛盾，本文提出基于粗精二次估计的RFID标签数目估算方法。通过仿真实验，该方法比其他几种标签估计算法具有较低的平均误差率，减少了标签识别过程中的运算量。利用粗精二次估计使得算法对标签估计过程中的随机误差具有更强的抵抗能力，算法的稳定性优于其他几种标签估计算法。在解决了估计准确性与运算量之间的矛盾的同时，其高稳定性使得算法适用于计算性能有限的场景，有利于提高标签防碰撞算法的效率。