无需先验RFID标签数信息的基于树时隙Aloha的防冲突算法

邓中婷

摘 要：为优化射频识别（Radio frequency identification， RFID）标签的识别效率，本文在树时隙Aloha（TSA） [1]基础上提出了一种新的防冲突协议。该协议采用FKSS（Fast k-Slot Selection）算法，对每个帧中的开始若干个时隙，通过判断是否为空时隙或冲突时隙来动态调整帧中的时隙数，即帧长。本文提出的协议的最大优点是，无需先验的RFID标签信息，无论标签突然增大和减小，系统均能使帧长与标签数保持在合理水平，从而使系统吞吐量的变化不受标签数的影响。从仿真结果看，本文提出的协议的最高吞吐量在0.43左右，高于传统的动态帧时隙协议和Q算法[5]协议，同时与TSA相比较，在标签数没有接近初始帧长时其吞吐量曲线要高于TSA的吞吐量曲线。）

关键词：RFID；防冲突；Tree Slotted Aloha；FKSS算法

1 引言

RFID是物联网中的一个关键技术， 其中阅读器识别标签采用共享的无线信道，因此标签的冲突不可避免。通常阅读器采用防冲突算法[2]来解决该问题，TSA算法是其中一个重要算法。

本文在TSA算法的基础上提出了一种FKSS（Fast k-Slot Selection）的防冲突算法，该算法也是把标签的访问时间分配到一个帧中的多个时隙之内，通过判断一个帧时隙内开始的若干个时隙是否全为空或冲突时隙来动态调整帧长，使帧长与标签数保持在一个合理的水平，从而保证较高的系统吞吐量。

本文提出算法的最大优点在于，无论标签增大还是减小，系统吞吐量都不会显著的降低，因而无需先验的标签数信息即可保证较高的系统吞吐量。从仿真结果来看，本文的算法取得的最大吞吐量为0.43，与DyTSA算法[3] [4]相当，但是当标签数明显降低和减少时却高于TSA算法。同时，其吞吐量曲线要高于Q算法和DFSA算法。

本文剩余部分做如下安排：第2部分由系统效率图指出TSA算法存在的问题；第3部分针对TSA算法的问题，提出了基于TSA的FKSS算法，并给出具体的数学推导、算法的基本流程；最后一部分给出系统识别性能的仿真与分析。

2 问题的提出

下图为TSA算法系统效率图。从图中可以看到，只有标签数接近于初始帧长时，吞吐量才能取得最大值，当标签数远离初始帧长时，系统吞吐量将大幅下降。因此，当标签数突然增多或者突然下降时，TSA算法的系统吞吐量将会迅速恶化。

图1 TSA系统效率

3 FKSS算法

针对上一节提出的TSA算法的问题，本节提出一种FKSS算法。

在Aloha协议中，我们设一个时隙发生冲突的概率为Pc，发生空的概率为Pi，成功时隙数则设为Ps，若已知标签数N和帧长L，则三个概率可表示为

（1）

由式（1）可知，如果待阅读的标签数n远大于初始帧长L，那么Pc就会很大；相反，如果待阅读的标签数n远小于初始帧长L，那么Pi就会很大。若只考虑一个信息帧的头几个时隙全为冲突或全为空的概率，我们可以引入Markov算法。

令Pci为一个信息帧中的前i个时隙都是冲突时隙的概率，Pii为一个信息帧中的前i个时隙都是空时隙的概率，Pss表示这头几个时隙中出现成功时隙的概率，则Markov计算公式为

（2）

由式（2）的Markov计算公式，我们可以得到信息帧的前k个时隙的状态概率。当给定初始帧长L0=128，当标签数增大，Pci增大，Pii减小；当标签数减小，Pci减小，Pii增大，其中i=1，2，3。

设k为连续时隙的门限值，Cc表示一个帧中头个时隙均为空时隙的数目，当Ci=k时，帧长为为原帧长的一半；Ci表示一个帧中头几个时隙均为冲突时隙的数目，当Cs=k时，帧长为为原帧长的一倍。该算法表示为

（6）

由式（6），我们给出FKSS算法的步骤，总结如下：

1.确定初始帧长，L=L0，其中L0为阅读器预先设定的初始值。

2.阅读器向标签发出带有初始帧长L信息的指令，标签在第0个到L-1个时隙中随机应答。

3.令Ci，Cs分别表示一个帧中头几个均为空时隙和冲突时隙的数目。若Ci= k， L=L/2，转向步骤2；若Cs=k， L=2L，转向步骤2；否则，L=L，转向步骤4。

4.TSA算法。

5.结束。

4 实验仿真

为了证明我们前面提出的FKSS算法，以下给出仿真结果，计算过程全部采用蒙特卡洛方法，结果由独立做500次试验平均得到。

图4 中初始帧长L0=128，N从10到500。可以看出，Q算法的吞吐量最低，最大也只能达到约0.34；DFSA算法的吞吐量相对来说也较低，其最大吞吐量无法超过0.40。混合型协议中的树时隙Aloha（TSA），动态树时隙（DyTSA）相比Q算法和DFSA算法，系统吞吐量得到了大幅提高，最高可达到约0.43；但是，在TSA算法中，只有当初始帧长与标签数相等时，吞吐量才能达到最大值，而当初始帧长大于标签数或小于标签数，吞吐量会从峰值0.43左右大幅下降到0.38左右。而我们提出的FKSS算法取得的最大吞吐量为0.43，与DyTSA算法相当，但是无论标签增大还是减小，系统吞吐量都不会显著的降低，都会保持在0.40以上，高于TSA协议，同时，其吞吐量曲线也高于Q算法和DFSA算法。

图2 不同算法下的系统效率

5 结论

本文在树时隙Aloha（TSA）基础上提出了新的FKSS算法，它的最大优点是，无需先验的RFID标签信息，无论标签突然增大和减小，系统均能使帧长与标签数保持在合理水平，从而使系统吞吐量的变化不受标签数的影响。

由仿真实验得到它的最大吞吐量高于TSA算法，而且无论标签增大还是减小，系统吞吐量都不会显著的降低，且一直高于TSA协议，同时，其吞吐量曲线也高于Q算法、DyTSA算法和DFSA算法。

参考文献

[1]I Hush D R，Wood C.Analysis of tree algorithm for RFID abitration.In： Proceeds of IEEE International Symposium on Information Theory.Cambridge，USA：IEEE，1998.107.

[2]EPC Radio-Frequency Identity Protocols Class-I Generation-2 UHF RFlD Protocol for Communications at 860Mhz-960Mhz version 1.0.9 2004.

[3]Wu， H， Zeng， Y. Bayesian Tag Estimate and Optimal Frame Length for Anti-Collision Aloha RFID System. IEEE Transactions on Automation Science and Engineering， 2010， PP（99）： 1-7.

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

[5]冯波，李锦涛，郑为民，张平，丁振华.一种新的RFID标签识别防冲突算法，自动化学报，34卷，6期，2008，631-638