0 引言

无线射频识别(Radio Frequency Identification，RFID)是一种利用射频识别方式进行无线非接触双向通信的自动识别技术。随着物联网技术的日益成熟，RFID技术得到了快速的发展，但其存在的问题也越来越凸显出来。目前RFID技术的主要问题包括：标准不统一问题、数据安全问题、电磁干扰问题、标签碰撞问题等，其中标签碰撞问题严重制约着RFID的发展，如何有效解决标签碰撞问题是RFID技术研究的重点和难点。目前解决标签碰撞问题的防碰撞算法主要分为两类^[1]：基于树类的确定性算法和基于ALOHA类的随机性防碰撞算法。

基于树类的确定性算法分为二进制树(Binary Search Tree，BT)类和查询树(Query Tree，QT)类算法。在BT类算法中，读写器逐时隙生成随机数0和1，进而形成新的路径来识别标签。在QT类算法中，读写器根据标签ID的二进制树状结构特点，形成唯一响应路径的策略来识别标签。学者们根据树类算法的特点，提出大量改进的防碰撞算法^[2-6]，但仍产生大量的空闲和碰撞时隙。基于ALOHA的随机性算法^[7-11]采用时隙随机分配的工作方式，执行过程相对简单，易于实现。当前该类算法又主要分为动态帧时隙算法(Dynamic Frame Slot Aloha，DFSA）和Q算法。前者通过将帧长设定为估计标签数量的近似值，使系统以最高的效率识别标签，标签数量估算精度和帧长的动态调整是制约DFSA算法识别效率的主要原因。后者避免了待识别标签数量的估计，同时解决了DFSA算法在识别帧中不能动态调整帧长的问题，但其使用单一的调整因子不能单独考虑空闲时隙和碰撞时隙。

本文针对DFSA类算法对帧长调整的不灵敏性以及Q算法中Q值调整的高计算复杂度，提出了基于连续时隙探测的RFID防碰撞算法(Continuous Slot Detection，CSD)。CSD算法引入了时隙探测的概念，通过判断识别帧中连续时隙的应答情况，动态调整帧长。仿真结果显示，与其他防碰撞算法相比，CSD算法具有较低的识别时延和较快的识别速度，并且在较多标签存在的环境下有明显优势。

1 连续时隙探测的防碰撞算法

1.1 CSD算法思想

针对DFSA类算法对帧长调整的不灵敏性以及Q算法中Q值调整的高计算复杂度，本文提出的CSD算法主要有以下两个方面的改进：

(1)缓解标签识别初始阶段的标签与帧长不匹配问题。对于DFSA算法，无论当前时隙是空闲还是碰撞，读写器都要查阅完整个时隙才能调整帧长，因此在标签与帧长不匹配的初始阶段，DFSA无法迅速根据标签数量调整帧长。CSD算法结合理论分析和实验推导，在大规模标签群下，通过判断初始条件下待识别帧起始3个连续时隙的应答状况，迅速调整帧长，使系统工作在最优状态。

(2)降低浮点数运算的计算复杂度。计算机中所有的数据均以二进制形式表示，浮点数也不例外。当在大规模标签群时，读写器多次对浮点参数进行近似计算，不仅造成误差累加，而且降低系统的识别效率。CSD算法利用判断帧中连续3个时隙的状态替代浮点参数c调整帧长，降低了运算量，加快了识别速度。

1.2 CSD算法关键参数的确定

为了详细描述CSD算法，现定义以下概念：

定义1 标签帧长比α为待识别标签数量n与识别帧长F的比值：

定义2 单位碰撞标签量β_k为连续碰撞时隙内的每个时隙的标签量，k为连续状态相同的时隙个数。

定义3 η_k表示连续k个空闲时隙发生的概率。

定义4 γ_k表示连续k个碰撞时隙发生的概率。

定义5 连续碰撞时隙计数器(Continuous Collision Slot Count，CCSC)用于统计连续碰撞时隙的数量；连续空闲时隙计数器(Continuous Idle Slot Count，CISC)用于统计连续空闲时隙的数量。

1.2.1 连续空闲时隙数量的确定

标签的碰撞问题从数学的角度上说是一个多重伯努利实验问题。理论条件下一个时隙内出现r个标签可以记为：

因此，对于帧长中k个连续时隙全部为空闲的概率为：

采用Python 2.7对式(5)进行描点，得到了在不同k值下标签帧长比α与连续个空闲时隙发生的概率η_k之间的关系，如图1所示。

从图1中可以看出，α与η_k成反比关系，α值越大，η_k值越小，这是因为当标签的数量大于帧长时，每一个时隙内平均存在的标签数量不少于1个，因此出现连续空闲时隙的概率是不断减小的；同时，在相同α值下，k与η_k也成反比关系。

当α>0.75，k≥3时，有：

即当α≤0.75时，结合式(6)、式(8)和式(9)，k=η_min(i)，i≥3，即k=3。因此，可认定当帧中出现连续3个空闲时隙时，此时的帧长与待识别标签数量不匹配，需要重新调整帧长识别。

文献[9]中已证明，当待识别的帧长F与标签数量n近似相等时，系统会得到最大的识别效率。结合式(8)和式(9)，以F/2的标签估计误差小于F时的误差，即标签的数量近似于F/2，则调整当前帧长为F/2，得到最佳的系统效率。

1.2.2 连续碰撞时隙数量的确定

根据式(2)，对于帧长中出现连续k个碰撞时隙的概率γ_k可计算为：

为了便于描述β的取值范围，同时考虑到β₁，β₂，…，β_k的值远小于待识别标签的数量，现令β₁，β₂，…，β_k∈[2，t]，t<k成反比关系，如图2所示。

从图2(a)中可以看出，当k=2，α→2时，无论t取何值，γ₂的值都近似为1，即标签的数量为帧长两倍的条件下，识别帧中一定出现两个连续碰撞时隙；从图2(c)中可以看出，当k=4时，在无论t取何值，γ的值都很小趋近于0，这是因为当有α值较小时，发生连续碰撞的概率本来就是小概率事件，而当α值较大时，其值又受限于β的取值。

对于k=3，当α>1.5，t≥10时，有：

当帧中出现连续3个碰撞时隙时，以2·F的标签估计误差小于F时的误差，即标签的数量接近2·F，则调整当前帧长为2·F，得到最佳的系统效率。

2 仿真实验与分析

本节利用计算机仿真的实验结果验证本文提出的算法。标签数目分别为100，200，…，1000。每设置1次标签数目，实验重复100次取平均值。本文主要从识别时延、最优帧平均查询次数和识别速度3个方面分析CSD算法。

2.1 识别时延

在常规标签群下(标签数量从100～1 000递增变化)，将CSD算法与传统的DFSA算法和Q算法的识别时延进行比较，对比结果如图3所示。因为CSD算法通过对连续时隙的探测，利用帧长调整规则，迅速调整到最优帧长。在标签数量为1 000时，CSD算法的总时隙数为2 911个，比LB、Schoute、Vgot和QA分别降低了12%、10%、9%和4%。

2.2 最优帧平均查询次数

在常规标签群下(标签数量从100～1 000递增变化)，将CSD算法与传统的DFSA算法和Q算法的最优帧平均查询次数进行对比，最优帧平均查询次数定义为系统从初始帧长调整到最优帧长下读写器重发布帧长调整命令的次数，对比结果如图4所示。可以看出，CSD算法要优于其他算法。在标签量为1 000时，CSD算法比QA算法和Vgot算法分别减少了6%和22%的查询次数。

2.3 识别速度

在常规标签群下(标签数量从100～1 000递增变化)，将CSD算法与传统的DFSA算法和Q算法的识别速度进行对比，对比结果如图5所示。LB算法和Schoute算法的读取速度分别约为250和260，QA算法的读取速度约为290，而CSD算法的读取速度最快，约为310，比LB算法、Schoute算法、QA算法分别提高了24%、19%、6%。

3 结论

本文提出了基于连续时隙探测的RFID防碰撞算法CSD。该算法利用数学模型及描点方式得出通过判断3个连续时隙的状况，动态调整帧长，解决了DFSA类算法对帧长调整的不灵敏性以及Q算法中Q值调整高计算复杂度的缺点。仿真结果显示，在标签数量为1 000的条件下，CSD算法比QA算法减少了4%的识别时延、降低了6%的查询次数以及提升了6%的标签识别速度。

本文通过数学模型推导出了识别帧中出现不同数量连续时隙的概率，对于求值都采用数据描点的方式，因此下一步的工作是优化数学模型的求值方法，进而能够通过理论方式求出其解。

参考文献

[1] FINKENZELLER K.RFID Handbook：Radio-frequency identification fundamentals and applications(Second Edition)[M].England：John Wiley and Sons，2003.

[2] JIA X，FENG Q，YU L.Stability analysis of an efficient anti-collision protocol for RFID tag identification[J].IEEE Transactions on Communications，2012，60(8)：2285-2294.

[3] SHIN J，JEON B，YANG D.Multiple RFID tags identification with M-ary query tree scheme[J].IEEE Communications Letters，2013，17(3)：604-607.

[4] 吴跃前，辜大光，范振粤，等.RFID系统防碰撞算法比较分析及其改进算法[J].计算机工程与应用，2009(3)：210-213.

[5] 黄琼，凌江涛，张敏，等.LRST：低冗余搜索树防碰撞算法[J].通信学报，2014，35(6)：110-116.

[6] 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.

[7] 任守纲，杨帆，徐焕良.一种双权重参数的RFID防碰撞Q值算法研究[J].计算机科学，2014，41(4)：256-259.

[8] 吴海锋，曾玉.RFID动态帧时隙ALOHA防冲突中的标签估计和帧长确定[J].自动化学报，2010，36(4)：620-624.

[9] 任守纲，杨帆，王浩云，等.基于判决门限的RFID防碰撞Q值算法[J].计算机科学，2014，41(8)：154-157.

[10] 张小红，张留洋.RFID防碰撞时隙应变协处理算法研究[J].电子学报，2014，42(6)：1139-1146.

[11] 杨帆，徐焕良，谢俊，等.基于双空闲因子的RFID防碰撞算法研究[J].计算机工程与科学，2016，38(7)：1440-1446.

作者信息:

杨 帆1，任守纲2，郝水侠1，周 俊3，袁培森2

(1.江苏师范大学 数学与统计学院，江苏 徐州221116；

2.南京农业大学 信息科学技术学院，江苏 南京210095；

3.南京农业大学 江苏省智能农业装备重点实验室，江苏 南京210031)