一种改进的RFID标签防碰撞算法*

王　彬，李俊杰，张海鹏，陈紫菱，王利丹

（杭州电子科技大学电子信息学院，杭州 310018）

一种改进的RFID标签防碰撞算法*

王彬，李俊杰，张海鹏，陈紫菱，王利丹

（杭州电子科技大学电子信息学院，杭州 310018）

在已有RFID标签防碰撞ALOHA算法基础上，提出了一种改进的带中断机制的动态帧时隙ALOHA（ⅡDFSA）算法，一方面通过优化设置系统效率临界因子和参考碰撞时空比，比较系统效率判断是否改变帧的大小；另一方面通过比较碰撞时空比来判断帧大小的改变方向，从而有效降低标签识别时间，提高识别效率。计算机仿真结果表明，与传统的动态帧时隙ALOHA算法相比，当标签数低于200和高于800时，采用ⅡDFSA算法可以有效降低系统总识别时间，提高系统效率。当标签数介于200～800之间时，与传统的动态帧时隙ALOHA算法相当。

射频识别； ALOHA算法；系统效率临界因子；碰撞时空比

1　引言

近年来，射频识别技术由于其无接触、数据容量大、传输速度快而得到广泛应用。同时也引入了新的问题，例如系统中标签共享无线信道，当多个标签同时发送信号时，会引起信号之间相互碰撞，使阅读器无法正确识别标签。

目前，主要有两类方法解决标签冲突问题：一类为基于二进制搜索的确定性标签防碰撞算法；另一类为基于ALOHA算法的随机标签防冲突算法。由于随机标签防碰撞算法具有实现简单、识别速度快、受系统中标签数目影响小等优点，得到了广泛应用。

随机标签防碰撞算法分为纯ALOHA算法、时隙ALOHA算法（SA）、帧时隙ALOHA算法（FSA）和动态帧时隙ALOHA算法（DFSA）［1］。基于帧时隙ALOHA算法的随机标签防碰撞算法的工作机制如下：标签随机选择一个时隙发送数据给阅读器，当在一个时隙中有两个或多个标签时，阅读器无法正确识别，等待下一帧识别过程，在下一帧中，标签重复上述过程，直到被阅读器成功识别。

在标签识别的迭代过程中，当帧长度等于未识别的标签数目时，系统达到最大效率，约为0.368。因此在识别过程中要估算未被识别的标签数目，根据估算值动态改变帧的长度。目前，所使用的几种标签估计方法（TEM）多应用于对标签数目与帧长相近时进行估算并且未考虑捕获效应［2］，而对于标签数目与帧长相差很大时，估算方法复杂、错误率高。为此提出了带中断的动态帧时隙ALOHA防碰撞算法（ⅠDFSA）［3］，较好地处理了标签数目与帧长度相差很大的情况。本文提出的估计算法是基于带中断的动态帧时隙ALOHA防碰撞算法的改进算法（ⅡDFSA），在标签识别迭代过程中，阅读器不断判断成功识别率、碰撞时隙与空时隙的比值，根据判断结果改变下一个帧长，能明显改善系统的标签识别效率。

2　最优帧长证明

对于动态帧时隙ALOHA算法，最关键的问题是如何确定最优的帧长度。假设处于阅读器识别域内的标签数目为n，帧长为N，标签在一帧中对阅读器的响应服从二项分布［4］，即一个时隙中有r个标签的概率为：

则一帧中成功识别标签的时隙数为：

根据式（1）～（3）可得系统的效率为：

由以上分析可知，当帧长等于阅读器读写范围内的标签数目时，系统可获得最大效率。因此，当前主要任务是在标签数目未知的情况下如何估算标签数目，分配帧长。

3　标签估计算法

在DFSA算法中，阅读器每次发送的帧长度要随阅读器识别区域内标签数目的变化而变化，所以如何估计标签数目对于DFSA算法至关重要。在此介绍两种估计算法。

3.1标签估计算法一

根据Schoute提出的理论［5～7］，假设某一帧中某一时隙有传送数据的标签数目服从均值为1的泊松分布，则在一帧中第i个时隙有k个标签的概率为：

所以，根据上一帧的碰撞时隙个数C，可以计算未识别的标签数目，进而改变下一帧帧长：

F=2.39C （9）

然而，当初始帧长与标签数目相差很大时，识别出所有标签所需的总时隙数较大，系统效率低。

3.2标签估计算法二

针对估计算法一中初始帧长与标签数目相差很大时系统效率低的情况，文献［3］提出了一种带中断机制的动态帧时隙ALOHA算法，利用抽样定理，根据部分时隙的统计特性，决定是否继续对剩余时隙进行识别。文献［3］指出，当碰撞时隙数占抽取部分

时隙的75%以上时产生中断，帧长倍乘2，若空时隙数占抽取部分时隙的75%以上，则帧长减半，否则按标签估计算法一进行估计。根据文献［3］中所示，选取初始帧长F=256、中断因子β=0.25，即抽样时隙数为f=F×β时，系统效率最高。但判定条件定义不甚合理，且在标签数目很低时，所需总的时隙数仍然很大，效果改善不明显。

4　改进算法（ⅡDFSA）

根据标签估计算法二，本文提出了一种改进的带中断机制的标签碰撞算法（ⅡDFSA）。我们定义系统效率因子E为抽样时隙中成功时隙与抽样时隙的比值

定义碰撞时空比R为抽样时隙中碰撞时隙与空时隙的比值，即：

我们仍采用初始帧长F=256，中断因子β=0.25。改进算法描述如图1。当抽样时隙中E大于系统效率临界值E0时，继续完成剩余帧长的识别，标签估计算法采用估计算法一，否则产生中断，改变帧长；帧长改变方向由R决定，若R大于临界值R0，则帧长倍乘2，否则帧长减半。

图1　ⅡDFSA算法流程图

首先，我们讨论临界值E0、R0的取值。图2所示为系统效率随标签数的变化情况。

图2　在不同帧长时系统效率随标签数的变化情况

为了使系统效率最高，E0采用帧长F=256与F=512交点处的E值，而将F=256与F=512交点处的R值作为临界值R0。根据式（4），交点处的系统效率相等，即：

可得交点处的标签数目为：

由于在标签识别过程中，第二次甚至以后的迭代，F可能不为256或2n，所以需要适当调整E0和R0的值。我们分别取E0为0.25、0.3、0.35，R0为1、1.5、2，对标签数为0～1300进行仿真，计算识别所有标签所需的总时隙数。仿真结果如图3～图5。

图3　当E0=0.25时，R0对系统效率的影响

图4　当E0=0.3时，R0对系统效率的影响

图5　当E0=0.35时，R0对系统效率的影响

由图3可知，在R0=1和1.5时，系统效率相近且优于R0=2。由图3和图4可以看出，随着标签数的增加，在R0=1.5时，系统效率稍高且平坦性比较好，由此确定参数R0为1.5。然后通过固定临界值R0=1.5， 分别对E0为0.25、0.3、0.35进行仿真，仿真结果如图6所示。由图6可知，在E0=0.3的情况下，系统效率比较平稳，相对比较理想，因此确定参数E0=0.3和R0=1.5。

图6　当R0=1.5时，E0对系统效率的影响

5　系统仿真

通过MATLAB仿真，得出标签数为10～1300之间时所需的总时隙数。三种算法的帧初始值都为256，中断因子为0.25，仿真结果分别如图7～图9所示。

图7　标签数为0～200时，读标签所需总时隙数

图8　标签数为200～800时，读标签所需总时隙数

图9　标签数为800～1 300时，读标签所需总时隙数

由图7可知，在标签数小于初始帧长时，ⅡDFSA算法总体上所需总时隙数明显减小；在标签数小于40时，ⅡDFSA算法与ⅠDFSA算法基本相当，但显著优于DFSA算法；标签数在40～150之间时，ⅡDFSA算法优于DFSA和ⅠDFSA算法；而当标签数为150～200时，ⅡDFSA算法优于ⅠDFSA算法，与DFSA算法相当。

由图8可知，在标签数近似等于或略大于初始帧长度的情况下，帧长基本未被倍乘或由于倍乘因子2.39与2相近，使得三种算法所需总时隙数相近。

在图9中，随着标签数目的增加，ⅡDFSA算法略优于前两种。

由以上分析可知，ⅡDFSA算法在标签数范围很大时整体上具有较好的性能，与DFSA 和ⅠDFSA相比具有明显改进。

6　结论

本文提出了一种改进的带中断机制的动态帧时隙ALOHA算法——ⅡDFSA。在该算法中，首先通过计算得出系统效率的临界值E0=0.346和碰撞时空比参考值R0=1.68；然后，通过仿真，对E0、R0进行适当调整，根据仿真结果中系统效率高和波动性小的判决条件，确定了帧改变时的临界值E0=0.3和帧长改变方向的临界值R0=1.5；最后对算法性能进行仿真验证。仿真实验结果表明，改进算法的系统效率在标签数较低时有明显改善，较高时略有改善，介于中间区域时不劣于DFSA 和ⅠDFSA算法。故采用所提出的ⅡDFSA实现RFID标签防碰撞系统可能有助于明显改善系统的标签识别效率。

［1］ W M Wong， P Yun. The Optimal Multicopy Aloha ［J］. IEEE Transaction on automatic control， 1994， 39（6）.

［2］ Sunwoong Choi， Jaehyuk Choi， Joon Yoo. An efficient anticollision protocol for tag identification in RFID systems with capture effect ［C］. 2012 Fourth International Conference on Ubiquitous and Future Networks（ICUFN）， 2012， 482-483.

［3］ Y Cui， H Wang. A New Anti-Collision Method for RFID System ［C］. 2011 IEEE 12th International Symposium on Computational Intelligence and Informatics（CINTI），2011， 51-55.

［4］ 魏欣. RFID标签及阅读器防冲突算法研究［D］. 成都：电子科技大学，2009.

［5］ F C Schoute. Dynamic frame length ALOHA ［J］. IEEE trans. Commun. 1983， 31（4）： 565-568.

［6］ J R Cha， J H Kim. Novel anti-collision algorithm for fast object identification in RFID system ［C］. The 11th Intl. Conference on Parallel and Distributed System， 2005. 63-67.

［7］ C Floerkemeier. Transmission control scheme for fast RFID object identification ［C］. Proceedings of the International Conference on Pervasive Computing Communication Workspaces， 2006. 457-462.

An Improved Anti-collision Method for Identification of RFID Tag

WANG Bin， LI Junjie， ZHANG Haipeng， CHEN Ziling， WANG Lidan
（School of Electronics and Information， Hangzhou Dianzi University， Hangzhou 310018， China）

In the paper， an Improved Dynamic Frame-Slotted ALOHA algorithm with Interrupt Mechanism（ⅡDFSA）was brought forward based on the previously reported ALOHA algorithms. The proposedⅡDFSA can be realized as follows. Firstly， the

ystem efficiency and ratio of the collision to empty slots have been optimized and then the frame size is adjusted by comparing the system efficiency with the reference system efficiency. On the other hand， the change direction of the frame size is determined by the ratio of the collision to empty slots. Thus， the proposedⅡDFSA is helpful to effectively reduce the recognition time and improve the system efficiency. Results obtained through computer simulation indicate thatⅡDFSA algorithm can effectively decrease the total recognition time and improve the system efficiency when the tag number less than 200 or more than 800 by comparing with the traditional DFSA andⅠDFSA， and the system efficiency of the proposedⅡDFSA is not worse than those of them while the tag number drops in between 200 and 800.

RFID； ALOHA algorithm； system efficiency； ratio of the collision to empty slots

TN402

A

1681-1070（2015）03-00018-04

王彬（1973—），男，江苏仪征人，教授，2001年获美国马里兰大学微电子可靠性工程博士学位，主要研究方向为电子存储器及无线射频识别（RFID）技术。

2014-11-04

浙江省智慧城市中心暨企业研究院人才培养项目（GK130902299002/007）