一种新颖的RFID标签防冲突算法

吕聪颖

LV Cong-ying

（南阳理工学院 计算机与信息工程学院，南阳 473000）

0 引言

RFID[1]技术被广泛用于运输系统、电子客票、访问控制、动物识别、物流及供应链管理等领域。在RFID系统中，当两个以上的标签在同一时刻向阅读器发送标识信号时，信号将产生叠加而导致阅读器不能正常解析标签发送的信号，即标签信号冲突问题。

基于ISO和EPC机构，有三类著名的解决标签信号冲突问题的算法：二叉树算法(Binary Tree,简写BT)、基于帧的时隙ALOHA算法(Framed Slotted ALOHA,简写FSA)及动态帧时隙ALOHA算法(Dynamic Framed Slotted ALOHA,简写DSFA)。然而，种种研究表明这些算法需要大量的时间去识别标签。

许多改进的防冲突算法已提出来了：Cho[2]等人提出在RFID系统中采用校验位的思想，不必检查标签中的所有位，该方法大大减少了阅读器发送请求的数量，从而可缩短在阅读器范围内识别所有标签的时间；滕培俊[3]等人通过对查询树算法及其性能的研究，提出了一种冲突跟踪树型算法，结果表明该算法在时间复杂度和通信复杂度两方面都有良好改善；王玉青[4]等人对帧长进行了研究，提出了一种动态改变帧长的方法。仿真结果表明，标签数量较大时，该方法可使系统效率达到最佳，时延最少；孙文胜[5]等人提出了根据帧时隙信息结合贝叶斯准则对标签数目进行估计，从提高估算准确性的角度对动态帧时隙ALOHA算法进行了改进。

文献[6]指出，当系统中的标签数量较少时，BT算法比FSA和DFSA更有效。而当标签数量较多时，BT算法比DFSA表现得糟糕。基于该结论及以往研究成果，本文提出了一种新颖的RFID防冲突算法，仿真结果表明该算法在所用时隙数量及获得吞吐量方面明显优于BT和DFSA算法。

1 新颖的防冲突算法

欲对标签进行分组，首先必须估计阅读器范围内的标签数目，从而才可以确定所用的组数。假定N表示时隙数，即帧长，规定N的最大值为Nmax=256；n表示待识别的标签数；c1表示只有一个标签发送数据的时隙数，即正确发送数据的时隙数；c0表示没有标签发送数据的时隙数，即空时隙数；ck≥2表示多于一个标签发送数据的时隙数，即碰撞时隙数。

1.1 标签数目的确定

文献[7]指出，vogt法需要在标签数取值范围内进行多次计算来确定极值，因此估算标签数较为准确。为此，本文借鉴vogt法来进行标签数目的确定。

由于每一次碰撞至少涉及两个标签，而每个标签只能选择一个时隙发送数据，因此，标签数目c的下限估算可采用下式：

该方法所引起的误差估计ε可通过将一个阅读周期内的各个加权误差相加获得：

使该误差值最小的n即为所估计的标签数目。

式(2)中，P(μ=mc)表示具有c(c=0,1,2,…,n)个标签的时隙数mc的分布概率，定义如下：

1.2 标签分组算法

为使算法更有效，分组数必须与标签数相一致。也即，标签数越少，组数越少。

根据统计学原理，每个标签以相同的概率1/N选择同一帧中的同一时隙做出响应，则l个标签选择同一帧中的同一时隙做出响应的概率B服从二项分布，即为：

由此可知，n与N大致相等时，系统吞吐量最大(约为36.8%)。当n远大于N时，可对标签进行分组，即限定每次识别标签的数目，且规定在同一时间只能有一组标签做出响应。定义标签分组数M为：

文献[8]提供了待识别标签数与最佳帧长下所对应的分组数，如表1所示。

表1 待识别标签数与最佳帧长和分组数的关系

1.3 具体算法流程

参数设置：Group：当前组数；Total_Tag：总的标签集合；Slot：识别某标签所用的时隙；Total_Slot：总时隙数。

步骤1：Total_Slot=0，Total_Tag={}；

步骤2：估算标签总数n；

步骤3：根据n计算分组数M；

步骤4：设定Group=1；

步骤5：如果Group＞M，则算法结束；

步骤6：采用QBT算法识别Group组中的标签，将识别的标签加入集合Total_Tag，并将所用时隙Slot加入Total_Slot；

步骤7：Group加1；转步骤5。

2 仿真测试

目的：通过统计标签数取值不同时所需的时隙数及系统的吞吐量来评估算法的性能。基于Matlab平台进行测试，n取值0～1000。

图1 标签数不同时各算法所需的时隙数

图2 标签数不同时各算法 获得的吞吐量

由图1可知，当标签数较少时，BT算法所需的时隙数与本算法相差不大，但当标签数＞500，本算法要大大优于其他两种算法。由图2可知，当标签数小于Nmax=256(最大帧长)，本算法所获得的系统吞吐量与DFSA相差不大，但当标签数远大于Nmax=256时，本算法所获得的系统吞吐量仍然保持35%，而DFSA却不容乐观。

3 结论

借鉴以往研究成果，提出了一种新颖的求解RFID标签冲突问题的算法：提出采用vogt来估计待识别标签数，并推导出相应的分组策略，接下来采用BT法对每组中的标签进行识别，发挥出BT法善于识别少量标签的特性。仿真结果表明，该算法在所需时隙数和获得系统吞吐量方面明显优于BT法和DFSA法。

[1] 陆冰清,牛国柱,赵英臣.一种新型RFID动态多叉树查询防碰撞算法[J].制造业自动化,2012,34(8):12-15.

[2] J.S.Cho,J.D.Shin,S.K.Kim. RFID Tag Anti-Collision Protocol: Query Tree with Reversed IDs[C].ICACT,2008:225-230.

[3] 滕培俊,熊伟,梁青,等.一种基于二进制树的RFID防冲突算法研究[J].通信技术,2009,42(7):94-96.

[4] 王玉青,李开宇,孙纯鹏. 改进动态帧时隙ALOHA算法[J].电子科技,2012,25(7):76-79.

[5] 孙文胜,金陈敏. 新型的RFID动态帧时隙ALOHA防碰撞算法[J].信息与控制,2012,41(2):233-237.

[6] S.Makwimanloy,P.Kovintavewat,U.Ketprom. A New Anti-Collision Based on A-Priori Information[C]. Proc.of ECTICON,2008: 733-736.

[7] Vogt H. Multiple object identification with passive RFID tags[C].Proceedings of IEEE International Conference on Systems,Man,and Cybernetics.Hammamet,Tunisia:IEEE,2002,1-6.

[8] Cha Jaeryong,Kim Jaehyun.Novel anti-collision algorithms for fast object identification in RFID system[C].IEEE Proceedings of the 11th International Conference on Parallel and Distributed Systems (ICPADS05),Fukuoka:IEEE CS Press,2005.

[9] 王雪,钱志鸿,胡正超,等.基于二叉树的RFID防碰撞算法的研究[J].通信学报,2010,31(6):49-57.