基于TDMA的RFID多标签识别防碰撞算法研究

贺晓霞 秦松 贾小林

摘 要：射频识别技术是一种非接触式自动识别技术，是物联网（IoT）的核心技术之一。RFID技术可通过射频信号快速、准确地自动识别目标对象并获取相关数据，识别工作无需人工干预。然而影响RFID系统识别效率的重要因素之一就是标签碰撞问题，所以高效的防碰撞算法对于RFID系统而言非常重要。现有的RFID防碰撞算法大都基于时分多址（TDMA）算法，可划分为Aloha类算法、树搜索类算法和混合算法。文中主要对Aloha类算法、树搜索算法、混合算法以及主要的改进算法进行分析研究，并对未来研究方向提出一些见解。

关键词：RFID；防碰撞算法；Aloha算法；树搜索算法；混合算法

中图分类号：TP39；TN911 文献标识码：A 文章编号：2095-1302（2018）07-00-04

0 引 言

射频识别技术（Radio Frequency Identification，RFID）是一种非接触式自动识别技术，随着物联网的快速发展，RFID技术也受到越来越多的关注。一般RFID系统由阅读器设备、电子标签以及计算机数据管理系统组成，通过DSRC短程通信技术进行数据传输和交换。标签具有唯一的ID号，目前该项技术已经广泛应用于金融支付、身份识别、交通管理及物流跟踪等方面，但是RFID系统中多标签碰撞问题一直是制约其发展的主要因素。

在RFID系统中，如果在阅读器读写范围内存在多张电子标签，当阅读器发出查询命令后，多张标签同时做出应答就会产生多标签碰撞问题，使得标签的数据混叠，如图1所示。在RFID阅读器的读写范围内存在4张电子标签，当这些标签同时应答发送自身的数据信息时就会相互干扰产生冲突，如果没有合适的防碰撞算法加以解决，会大大影响系统的识别效率，甚至影响运转。

现有的RFID防碰撞算法大都基于时分多址（TDMA）算法，可将其划分为基于Aloha算法和基于二进制搜索BS（Binary Search）算法两大类，以及正在发展的结合前两种算法的混合协议，其中还包括大量改进算法。

1 基于Aloha协议

Aloha算法是一种随机的、不确定性算法[1]，该算法的核心思想就是当多个标签发生碰撞时，阅读器将发送命令让标签停止发送，随机等待一段时间后再重新发起查询。该算法的特点是简单、便于实现，但是因为该算法的随机性较大，识别效率不太理想，故适用于低成本RFID系统。Aloha算法可以细分为以下几种。

1.1 纯Aloha（PA）算法

在基于PA的RFID系统中，当标签进入阅读器读取范围被通电激活之后随机地用其ID进行响应。然后等待阅读器回复，当阅读器发出肯定确认（ACK）时，表示该标签的ID已被正确接收，反之发送否定确认（NACK），这意味着标签之间发生了碰撞。如果两个或两个以上的标签发送时产生冲突，则随机后退等待一段时间后再传递其ID。但是早期的纯Aloha算法识别效率较低，最大吞吐率仅为18.4%[2]。

1.2 时隙Aloha（SA）算法

在基于Slotted Aloha（SA）的RFID系统中，将时间划分为多个离散的时隙，标签以同步时隙发送其ID。如果存在标签冲突，即在同一个时隙内有多个标签响应，则在随机延迟后重新发送标签，直到所有的标签被成功识别。SA克服了PA部分碰撞的缺点，减少了时间开销，SA算法的最大吞吐率可以达到36.8%[2]。

1.3 FSA与DFSA

改进的DFSA算法[3]在多轮中运行，并且还可以结合提前结束功能。然而，关键的区别是在每个读取循环中，阅读器可以使用标签估计功能来改变其帧长。

标签估计函数根据来自阅读器帧的反馈来计算标签的数量，其中包括用0填充的时隙数（c0）、用1填充的时隙数（c1）和多个签响应（ck）。

标签估计函数主要包括Vogt，Cha-I，Q协议，这里主要讲解前两种。

1.3.1 Vogt

Vogt具有两种标签估计功能[4]，分别表示为Vogt-I和Vogt-II。Vogt-I在碰撞期间至少涉及两个标签，因此标签估计是c1+2ck。Vogt还提出了一组帧的大小，见表1所列。例如，当存在1～9个标签时，帧的大小等于16，被认为最佳。基于他们的实验，还提出1.4×（c1+2.39ck）作为标签估计。另一方面，对于静音环境，则0.65×（c1+2.39ck）为最佳。

1.3.2 Cha-I

Cha-I通过计算具有冲突的时隙数和帧长的比率来估计标签[5]，并由下式给出，其中n是标签个数，Cratio碰撞率为冲突时隙数和帧长的比值，Cratio=ck/N。在Cha-II中，标签估计只是2.39ck。

1.4 增强型DFSA（EDFSA）

DFSA算法的限制是帧长的最大值被限制为256或512。如果标签的数量超过此值，则持续的冲突成為关键问题。为此，Lee等人提出了DFSA的增强版本[6]，称为增强型DFSA或EDFSA。其中，如果标签群体大于可用的最大帧长，则将标签分为M组。表2显示给定标签范围的M值。

2 基于树的协议

基于树的算法可以分为树分裂（TS）、查询树（Qt）、二进制搜索（BS）以及按位仲裁（BTA）等。

2.1 树分裂（TS）

Tree Splitting（树分裂）算法：TS算法通过使用随机数发生器将响应标签分成多个子集来操作。Hush[7]等人提出BTS，一种通过将碰撞标签分解为几个不相交的子集来解决冲突的算法。这些子集变得越来越小，直到它们包含一个标签为止。在一系列时隙中，每个标签都有一个随机的计数器，将结果记录在树中的位置。计数器为0时，标签处于发送状态，否则处于等待或睡眠状态。在每个时隙中阅读器会通知标签是否发生碰撞、单响应、无响应，如果冲突，则计数器随机生成一个二进制数，加到当前计数器中。另外一方面，等待状态的标签计数器值加1。在空闲或单响应时，等待状态标签计数器值减1。

采用BTS算法識别{A = 010，B = 011，C = 100，D = 110}的基本过程见表3所列。

2.2 查询树Qt

查询树算法[8]（Qt）是一种典型的树形结构算法。阅读器选取搜索前缀（Prefix），发送Query命令，询问其识别区域中的待识别标签。标签收到命令后，前缀与自身编号匹配。如果阅读器收到标签ID发生碰撞，再分别将Prefix加“1”和“0”作为新的Prefix发送出去。如果没有碰撞则表明一个标签被成功识别，直到所有的标签都被成功识别。

图2给出了采用Qt算法识别{1010，1011，1100，1101}的基本过程。经过13个周期完成了对这4个标签的识别。

Qt算法只与当前查询有关，不需要存储先前查询和响应状态信息。Qt算法被称为无记忆算法，是查询树算法的基础和代表。

2.3 BS算法

BS算法[8]涉及阅读器将序列号传输到标签，然后将其与ID比较等内容。序列号长度与标签编号长度一致，初始值由可能的最大标签编号构成。当ID等于或低于序列号时标签响应，然后，阅读器通过使用曼彻斯特编码对标签的回复进行监视，一旦发生碰撞，阅读器就会根据碰撞位减小序号，然后继续搜索。如果没有发生碰撞，则阅读器成功识别一个标签，并以初始序列号为参数重新开始搜索，直到识别出所有标签。图3给出了采用BS算法识别标签{1010，1011，1100，1101}的基本过程。初始序列号ID值为“1111”，4个标签的编号小于初始序号，标签全部响应。由于标签编号在空中媒介中的相互干扰，阅读器收到“1XXX”，这表明标签后三个比特都经历过碰撞。然后阅读器根据碰撞位，减小序列号为“1011”，继续搜索，阅读器收到“101X”。在第三个周期中，只有一个标签“1010”响应，阅读器在收到响应时没有碰撞，完成了标签的识别。接着又以初始序列号“1111”重新开始搜索，直到全部标签识别完成。此次标签识别采用BS算法经过8个周期，完成了对这4个标签的识别。

BS算法具有很高的稳定性，易于软件实现，吞吐率最高可达36.4%。但ID越长所需时间也就越长，时间超过一定限度后，BS算法将不再适用。

3 混合协议

混合协议是一项新的标签阅读协议的分支，该算法结合了Aloha算法与基于二进制搜索树算法的优点，是碰撞算法的重要研究方向。

3.1 树时隙 Aloha（TSA）

TSA算法是增强的FSA算法，在识别过程中使用树状结构[8]。在第一次读取过程中传递的时隙用树的根节点表示。每个标签记住它们用于传输的时隙编号，如果在读取周期内产生碰撞，阅读器就会为每个发生碰撞的时隙开始一个新的阅读周期，与树的更新有关。每个标签都有一个计数器来记住它在树中的位置。每当发生碰撞时，就会将一个新节点插入到树中，并启动另一个阅读周期。此过程重复进行，直到没有碰撞发生。

3.2 混合查询树（HQT）[9]

该算法是将Qt算法与时隙的随机回退机制相结合。基于该算法的识别过程：首先阅读器向标签发送两位查询，然后在回退延迟后发送前缀匹配的标签。假设有0001，0011和0010，三个标签如果阅读器发送查询00，那么每个标签查询之后的两位是01，11和10。然后这些标签分别将一个和两个时隙的回退定时器设置为0。

3.3 HQT改进算法[10]

将Qt和Frame Aloha算法结合的两种算法，即帧查询树算法和查询树Aloha算法[11]。帧查询树算法：阅读器发送一帧给标签，标签随机选择一个时隙。在每个时隙中，Qt用于识别标签。查询树Aloha算法：阅读器发送一个前缀和帧长，然后前缀匹配的标签在帧中随机选择一个时隙。换句话说，匹配的前缀标签使用帧的Aloha协议进行识别。

4 结 语

本文对基于时分多址的RFID多标签防碰撞算法做了全面的调查和分析。划分为Aloha算法、树搜索算法以及混合算法。

Aloha算法的最大优点是动态适应性，可以对不同的负载和低读取器进行标签命令，该算法简单易于实现，适用于低成本RFID系统。研究出一种高效率的基于标签估计函数的DFSA算法是当前任务，因为该算法对于给定的标签范围的准确性更高。

对于树协议，Qt算法只需要一个前缀匹配和一个同步电路。然而，Qt算法的一个关键缺点是查询的长度与构建树的深度成比例，另一个问题是识别延迟随ID大小而增加。因此，一个有趣的研究方向是使用伪ID来提升性能。

目前混合算法的数量还较少，鉴于Aloha和树算法的数量，一个具有挑战性的研究方向是确定具有最高读取速率的组合。

随着RFID技术的发展，每年电子标签的使用量也呈指数增长。因此，一个高效准确且安全性高的防碰撞算法是未来的研究方向，以此适用于标签范围较大且识别系统较复杂的场景。

参考文献

[1]周少珂，邓淼磊.ALOHA标签防碰撞算法综述[J].计算机工程与应用，2017，53（14）：9-17.

[2]王勇，李婷.改进的基于ALOHA的RFID防碰撞算法[J].电信科学，2016，32（8）：77-81.

[3] FINKENZELLER K. RFID handbook：fundamentals and applications in contactless smart cards，radio frequency identification and near-field communication[Z]. New York：Wiley，2010：189-212.

[4] VOGT H. Multiple object identification with passive RFID tags[C]// International Conference on Pervasive Computing. Springer，Berlin，Heidelberg，2002：98-113.

[5] WANG J，ZHAO Y，WANG D. A Novel Fast Anti-Collision Algorithm for RFID Systems[C]// International Conference on Wireless Communications，Networking and Mobile Computing. IEEE，2007：2044-2047.

[6] LEE S R，LEE C W. An enhanced dynamic framed slotted aloha anti-collision algorithm [J]. Lecture notes in computer science，2006，4097：403-412.

[7] HUSH D R，WOOD C. Analysis of tree algorithms for RFID arbitration[C]// IEEE International Symposium on Information Theory，1998. Proceedings. IEEE，2002：15-23.

[8] BONUCCELLI M A，LONETTI F，MARTELLI F. Tree slotted aloha：a new protocol for tag identification in RFID networks[C]. 2006 International Symposium on a World of Wireless，Mobile and Multimedia Networks（WoWMoM'06），Buffalo-Niagara Falls，NY，2006：600-608.

[9] SHIN J D，YEO S S，KIM T H，et al. Hybrid tag anti-collision algorithms in RFID systems[C]// International Conference on Computational Science. Springer-Verlag，2007：693-700.

[10]錢东昊.基于标签识别码分组的混合防碰撞算法研究[D].天津：河北工业大学，2014.

[11]孙文胜，陈安辉.高效的RFID混合询问树防碰撞算法[J].计算机应用研究，2011，28（10）：3717-3719.

[12]苏健，谢良波，杨颖，等.基于空闲时隙消除的超高频RFID防碰撞算法[J].电子学报，2017，45（2）：307-314.