RFID中的不确定性标签防碰撞算法简介

杨晓娇，吴必造

(1． 重庆交通大学 信息技术中心，重庆 400074；2. 中移物联网有限公司 解决方案中心,重庆 401336)

RFID中的不确定性标签防碰撞算法简介

杨晓娇1，吴必造2

(1． 重庆交通大学 信息技术中心，重庆 400074；2. 中移物联网有限公司 解决方案中心,重庆 401336)

针对RFID系统中的不确定防碰撞算法即ALOHA算法进行分析，首先介绍了ALOHA算法的工作原理，并对该类算法的吞吐率进行理论分析;然后推算得出当时隙数等于标签个数时吞吐率最高为36.8%;最后分析了几类改进的ALOHA算法的工作原理，对比了几类改进算法的优缺点以及在实际工程实践中的实用性。本文对ALOHA算法的后续研究工作以及工程实践中ALOHA算法的选取以及应用具有参考价值。

时分多路算法；不确定算法；动态帧时隙ALOHA；时隙

0 引言

由于RFID具有同时快速识别多目标且存储信息量大等特点，从而被作为感知层的关键技术广泛应用于物流、工业、农业等物联网领域。要实现多目标快速识别就需要在RFID系统中实现防碰撞算法，这也是本文研究的重点。防碰撞算法主要有基于时分多路的防碰撞算法和基于频分多路的防碰撞算法。而目前应用最广泛防碰撞算法大多是时分多路的，主要有如下两类：确定性防碰撞算法和概率性防碰撞算法[1]。

确定性标签防碰撞算法主要有二进树算法及其改进算法，优点是能识别所有标签，没有标签“饿死”现象；缺点是该算法对阅读器硬件要求较高且算法的空间和时间复杂度较高。概率性标签防碰撞算法主要是指ALOHA及其改进算法，这类算法优点是复杂度小且容易实现，硬件成本相对较低；缺点是存在标签“饿死”的情况。由于ALOHA算法对硬件要求较低，且实现复杂度较低，因此在RFID标签防碰撞领域内ALOHA算法是应用最广泛的[2]。这也是本文探讨的重点。本文首先介绍了时隙ALOHA算法及动态帧时隙ALOHA算法；然后介绍了目前比较好的改进型ALOHA算法；最后对各种算法的使用情况以及性能做综合对比分析并给出总结。

1 时隙ALOHA算法

1.1 时隙ALOHA算法工作原理

图1 时隙ALOHA算法的示意图

时隙ALOHA(Slotted ALOHA)算法将标签与阅读器的通信时间分为如图1所示的若干个等长的时槽(每个时槽的长度大于标签与阅读器完成一次通信的时长)。根据时隙ALOHA算法的规定，标签在每个时隙开始时向阅读器传输数据，且在当前时隙结束时将本轮数据传输完毕。

1.2 时隙ALOHA算法吞吐率分析

根据泊松分布可以推导出，时隙ALOHA算法的吞吐率为[3]：

S=Ge-G

(1)

其中：S为吞吐率，表示实际传输的有效的数据率；G为输入负载，表示标签向阅读器发送的总数据率。

下面探讨时隙ALOHA算法的吞吐率极值，对公式(1)中的G求导可得：

(2)

然后把G=1带入式(1)可得S的最大值为：

Smax=e-1≈36.8%

(3)

由公式(3)可知，时隙ALOHA算法的吞吐率极值为36.8%。

2 帧时隙及动态帧时隙ALOHA算法

帧时隙以及动态帧时隙ALOHA算法都是在时隙ALOHA算法的基础上将N个时隙组成一帧，如图2所示，所有标签都在一帧内的N个时隙中选择一个时隙与阅读器进行通信，若由于碰撞导致无法识别标签，则对下一帧继续识别。

图2 帧时隙ALOHA算法的示意图

动态帧时隙ALOHA算法即根据标签个数n来动态调整帧长N的大小，使ALOHA算法的吞吐率最优。

已有很多文章对帧长N与标签个数n与吞吐率的关系做过论证。当N=n时帧时隙ALOHA算法的吞吐率最高。

3 改进的动态帧时隙ALOHA算法

改进的ALOHA算法主要有三种，下面分别对其进行分析。

3.1 基于数学分析的改进ALOHA算法

这类改进的动态帧时隙ALOHA算法本质上还是随机算法，算法的思想是通过对阅读器接收到的一帧中的碰撞、空闲以及成功时隙的个数进行数学建模和分析，推导出相应数学公式来估计阅读器作用域内处于活动状态的标签个数，这类算法推导公式的目的是尽量使估计到的标签个数接近实际的标签个数[4-5]。

估算结束后阅读器向标签广播的帧长N=估计出的标签个数n，从而使算法理论上的吞吐率尽量接近36.8%。注意，算法在实际实现过程中帧长N=2Q(Q=1，2，3，…)即N=2，4，8，16，32，64，128，…。

总之这类算法的吞吐率在理论上能够无限接近于36.8%，但是算法的时间复杂度较高，而RFID阅读器计算能力以及存储空间都有限，因此在实际工程中，若阅读器计算能力以及存储空间较优，则可以采用这类算法。

3.2 基于工程实现改进ALOHA 算法

由于实际应用中阅读器提供的时隙数N=2Q即N取值只能为2，4，8，16，32，64，128，…，且阅读器的存储能力以及运算能力都有限，因此有了基于EPC G1,G2协议中动态帧时隙ALOHA 算法的改进算法。

这类算法通过阅读器接收到空闲、成功以及碰撞时隙的个数，对帧长参数Q进行动态调整，调整的方法为检测到碰撞(空闲)时隙则Q+C(Q-C)。改进算法通过仿真数学运算选取一个合适的C值，使帧长调整更合理。这种算法较3.1节的算法时间复杂度更低，也更易实现。

另一种是基于阈值跳变的时隙数调整算法，这类算法时隙数变化不与C值相关，阅读器维护一个时隙数跳变的列表，收到标签回复后根据标签总数和空闲碰撞时隙数所占的比例选取表中相应的时隙数。这种算法相比于C值调整时隙的算法避免了浮点运算，但对阅读器的存储能力要求较高[6-8]。

3.3 基于二分法的改进ALOHA 算法

将ALOHA算法与二进制搜索算法相结合，来提高算法的效率。具体实现是先用ALOHA算法对标签进行分流，如碰上碰撞时隙则对该碰撞时隙采用二分法进行分流，直至完全识别当前时隙的所有标签，再返回继续识别下一时隙[9-10]。这类算法由于需要应用到二进制搜索算法，因此算法需要阅读器在硬件上支持曼侧斯特编码，故该算法对系统硬件的要求相对较高，且算法的时间复杂度也相对较高，但是该算法的优势是吞吐率较高，且由于具有二分法的特点因此可以避随机算法中标签饿死的情况出现。

图3 吞吐率比较图

4 算法仿真

本文的所有仿真实验都是在MATLAB 7.0平台上进行的。分别编程实现不同算法识别标签的过程，再统计运行的结果，为了减小偶然因素对算法评估造成影响，图3中所有的结果都是对相同的标签识别10次后取平均值的结果。

从图3可以看出，基于二分的ALOHA算法吞吐率最高稳定在55%左右，但是需要结合二分法，硬件要支持曼侧斯特编码，且算法的复杂度相对较高。其次是基于EPC的改进算法吞吐率稳定在0.41%左右，在工程实现中推荐这种方法，吞吐率较高且算法复杂度较低，对硬件要求也不高。如图3数学估计算法中标签估计最准确吞吐率能接近35%，一般工程实现中不适用这种方法。

5 结论

本文首先介绍了ALOHA算法的基本原理和优缺点，然后介绍了ALOHA算法以及动态帧时隙的工作原理并对算法的理论吞吐率做了推导，得出当标签个数等于时隙数时ALOHA算法的理论最高吞吐率为36.8%，简介了当前主流的基于ALOHA算法的改进算法原理，并总结了算法的优缺点，最后对不同吞吐率仿真得出基于二分法的ALOHA算法吞吐率最高接近55%，但是实现难度较高，EPC改进算法吞吐率其次，接近41%，实现难度较低。本文可为RFID系统中防碰撞算法的研究工作提供参考。

[1] 孙其博，刘杰，黎羴，等．物联网:概念、架构与关键技术研究综述[J]．北京邮电大学学报，2010,33(3):2-3.

[2] 黄玉兰，夏璞，夏岩，等．物联网射频识别(RFID)核心技术详解[M]. 北京:人民邮电出版社，2012．

[3] CHA J R, KIM J H. Dynamic framed slotted ALOHA algorithm using fast tag estimation method for RFID system[C]. Consumer Communications and Networking Conference, 2006 CCNC.3 IEEE, 2006:768-772.

[4] 陈平华，王康顺，李超，等.基于线性回归的动态帧时隙ALOHA算法[J].计算机仿真，2014,31(7):259-263.

[5] 石封查，崔琛，余剑.基于标签运动的一种新型RFID防碰撞算法[J].计算机科学，2013,40(6): 76-79.

[6] EPC Global. EPC Radio-Frequency Identity Protocols Gengernation-2 UHF RFID Protocol for Communication at 860 MHz～960 MHz Version[S]. California: EPC Global ,2008.

[7] EPC Global. EPC Radio-Frequency Identity Protocols Gengernation-1[S]. American:UCC, 2013.

[8] 吴淼，刘德盟，张钊锋.基于EPC Gen2防碰撞机制的研究与优化[J]．微电子学与计算机，2013,30(5):101-104.

[9] 徐圆圆，曾隽芳，刘禹.基于Aloha算法的帧长及分组数改进研究[J]. 计算机应用，2008,28(3):588-590.

[10] 鞠伟成，俞承芳.一种基于动态二进制的RFID抗冲突算法[J]. 复旦大学学报(自然科学版)，2005，44(1):46-50.

of uncertainly anti-collision algorithm in RFIDYang Xiaojiao1， Wu Bizao2(1.Information Technology Centre, Chongqing Jiaotong University, Chongqing 400074, China;2.Solutions Center, China Mobile IOT Company Limited, Chongqing 401336, China)

This paper mainly discussed the uncertainly anti-collision (ALOHA) algorithm. This article firstly introduced the work and principles of process of ALOHA algorithm, then showed that when the slot number is equal to the tag number the ALOHA algorithm, the maximum throughout value is 36.8%. Finally, it analyzed different classes of ALOHA algorithm and how it works, compared their advantages and disadvantages, and analyzed their practicality. This article has some reference values for further study of ALOHA algorithm and choosing the proper algorithm in actual project.

time division multiple access algorithm; uncertainly algorithm; dynamic framed slotted ALOHA； slot

TP312

A

10.19358/j.issn.1674- 7720.2017.06.004

杨晓娇，吴必造. RFID中的不确定性标签防碰撞算法简介[J].微型机与应用，2017,36(6)：10-12.

2016-09-27)

杨晓娇(1988-),通信作者，女，硕士，助理工程师，主要研究方向：无线传感网、RFID。E-mail:yangxiaojiao@cqjtu.edu.cn。

吴必造(1985-)，男，硕士，软件工程师，主要研究方向：物联网安全、物联网传输、RFID。