面向物联网的RFID碰撞问题分析

吴必造，杨晓娇

（1 中移物联网有限公司，重庆 401336；2 重庆交通大学信息技术中心，重庆 400074）

面向物联网的RFID碰撞问题分析

吴必造1，杨晓娇2

（1 中移物联网有限公司，重庆 401336；2 重庆交通大学信息技术中心，重庆 400074）

文中首先介绍了RFID系统中3种不同的碰撞的产生原理，然后研究了最常见的多标签碰撞问题及其对应的防碰撞算法，并重点研究了两种目前工程中较常用的防碰撞算法DFS-ALOHA和Q-ALOHA算法的性能及其应用场景。希望文中介绍对需要解决标签碰撞问题的读者具有一定的启发作用。

物联网；RFID；多标签防碰撞

物联网作为下一代网络的关键组成部分，核心是实现万物的互联与信息间的相互传递，因此若要实现物联网就需要实现物联网中物与物的互联，即首先要使用自动识别技术对接入物联网的物体进行识别。随着物联网的不断发展自动识别技术已经成为物联网的核心技术之一[1]。

物联网中的自动识别技术需要具有“海量存储”以及“广泛感知”的主要特点。RFID技术具有非接触、精度高、寿命长、抗污染能力强、数据存储容量大、安全性较高、多目标快速识别等优点，而从众多自动识别技术中脱颖而出被广泛应用于物联网的接入层[2]。目前RFID技术已广泛应用于身份识别、零售业、物流管理、药品防伪、公共交通管理等物联网领域。是物联网接入层中应用最广泛的自动识别技术。

综上，RFID技术未来发展前景无限，但是仍然存在诸如制造成本、协议的标准化、数据安全性、数据完整以及正确性等关键问题制约着RFID技术的进一步普及。数据完整以及正确性是决定RFID系统性能的重要因素，也是本文研究的重点[3]。导致这个问题的关键是碰撞。碰撞又分为标签碰撞和阅读器碰撞，在阅读器作用域内多个标签同时向阅读器发送数据或者一个阅读器在另一个阅读器的作用域内时，信号间发生相互干扰，导致阅读器接收到的数据错误，即无法完整的识别出标签，或者识别出错误的标签。因此多目标识别既是RFID的最大优势，也是急需解决的技术难点。

因此，本文首先探讨RFID中碰撞的分类及其相对应的解决方法，然后探讨了RFID算法的常用协议及其对应的RFID防碰撞算法，通过比较分析发现ALOHA算法是最常用的多标签碰撞算法，重点对比分析了两种ALOHA算法DFS-ALOHA和Q-ALOHA算法，并通过仿真算法执行的过程说明了算法的优劣及应用场景。

1 RFID碰撞分类

1.1 标签碰撞

当阅读器R1作用域内存在多个标签时，阅读器发送寻呼命令后，阅读器作用域内多个标签同时向阅读器发送信号时，会相互发生干扰，导致阅读器读取的数据错误或者不完整即发生了碰撞。如图1所示。

图1 多标签碰撞示意图

解决标签碰撞的标签防碰撞算法主要有Framed Slotted ALOHA、Btree、Random Slotted、Splitting Algorithm等算法。在本文第二部分会详细介绍算法流程以及应用场景。

1.2 阅读器碰撞

当使用相同频率进行通信的阅读器R1、R2同时发送寻呼命令后，处在阅读器RI、R2的交叠区域内的标签T3将同时接收到两个命令导致标签T3不能正确识别任何一个阅读器的寻呼命令，而导致T3无法被识别。这就是阅读器碰撞。如图2所示。

图2 阅读器碰撞示意图

阅读器标签碰撞解决算法主要是Slotted Scheduled Tag Access算法，即阅读器建需要时间同步，通过将时间分为时隙段的方式，每个阅读器占用一个时间段，当一个阅读器工作时其余阅读器休眠，就避免了阅读器碰撞问题。

2 标签碰撞算法

按照标签的应用场景不同，RFID技术采用频段也不同，常用的主要有如下几种协议ISO是国际化标准组织提出的协议，以及美国EPC[4]提出的EPC[5]协议。下面将常用的协议以及对应的防碰撞算法总结如表1所示。

表1 RFID标准及其对应的防碰撞算法

由表1可知碰撞算法主要分为ALOHA算法和Binary Tree（二进制树算法），而ALOHA算法实现的硬件成本低，算法复杂度较低，因此成为RFID领域内应用最广泛的防碰撞算法，广泛应用于仓储物流，动物识别，车联网中，同时也是接下来研究的重点。

2.1 ALOHA算法

ALOHA算法又称随即算法或不去定算法。在EPC和ISO协议的标准中涵盖了从低频中频以及高频各个频段的多种协议规定的防碰撞算法都是ALOHA及其改进算法。因此ALOHA算法是目前应用最广泛的标签防碰撞算法之一。目前很多的文章对标签估计都进行了研究，但大多标签估计算法复杂度高，加重了阅读器的负担，增加了读取时间。在工程中实用性较差，而实际中运用最多的ALOHA算法主要有DFS-ALOHA和Q-ALOHA下面具体介绍两种常见的ALOHA算法。

2.2 DFS-ALOHA算法

DFS(Dynamic Framed Slot)-ALOHA算法就是动态帧时隙ALOHA算法。如图3所示，将时间分为帧的形式，帧长N=2QT（Q为正整数，T为阅读器识别一个标签所需时间即单位时间），阅读器作用域内参与识别的n个标签随机选择N个时隙中的任意一个时隙[6]。当n个标签中超过一个标签选择了某个时隙即发生了碰撞如图3所示。

很多文献中对帧长N的选取都有探讨，可以得出当N=阅读器作用域内标签个数时算法的吞吐率最高，而实际应用中阅读器不知道其作用域内的标签个数，只能通过阅读器收到的一帧中碰撞，空闲以及成功时隙的个数来估计标签个数[7]。如图4中就是通过收到的时隙数来调整帧长。

图3 动态帧时隙ALOHA算法时隙选择图

图4 DFS-ALOHA算法帧长改变流程图

DFS-ALOHA算法的特点是在算法执行过程中运用的命令较简单，即只需应用到协议中规定的命令：Query(Q)帧寻呼命令；QueryAdjust(Q)更新Q值命令；QueryPep帧内寻呼下一时隙命令。没有像很多改进算法一样额外的增加寻呼命令而造成阅读器的负担。具体命令的用法读者可以参照ISO标准，由于版面有限这里就不再累述。DFS-ALOHA算法的思想是：当一帧所有时隙识别完成后，通过统计得出的碰撞时隙NC，空闲时隙NI进行计算判断若Pc=(NC/N)＞0.75或者PI=(NI/N)＞0.3调整帧长，直至帧长N=0，即识表示识别完所有标签为止。由于这类算法易实现且对硬件要求较低，不许复杂的运算以及浮点运算，因此这类算法是工程中最常用的ALOHA算法[8]。

2.3 Q-ALOHA算法

Q算法本质也是ALOHA算法，Q-ALOHA算法和DFS-ALOHA算法的区别主要是帧长的调整方式不同，区别是Q算法通过引入浮点数Qfp和C来动态调整帧长，当Q值达到需要调整的阈值时不论本帧是否识别完毕，都结束对当前帧的识别，立即采用QueryAdjust(Q)调整帧长，因此Q算法对帧长的调整更加灵活。

如图5中可以看出当检测到碰撞时隙时浮点数Qfp值增加C，检测到空闲时隙时Qfp值减少C，EPC标准中建议C值的选取为0.2～0.5。每结束一个时隙就对Qfp值四舍五入取整，若取整后Q值相较之前值发生了变化则立即停止当前帧的识别过程，用QueryAdjust(Q)命令更改帧长。本算法相较于DFS-ALOHA算法不同的是引入了浮点数Qfp和C来及时的改变帧长Q，随着浮点数的引入就增加了浮点运算，因此需要射频芯片支持浮点运算，当然目前基本主流的射频芯片都支持浮点运算。由于算法适应性更好因此运算效率较高。但由于需要进行浮点运算因此算法的复杂度也较高。

图5 Q-ALOHA算法帧长改变流程图

3 算法性能对比

在Matlab7.0平台上，模拟两种算法的实际执行过程，以阅读器范围内标签个数为n个（x轴），识别晚阅读器内n个标签需要的时隙数N个（y轴），反复运行50次求平均值。

Q-ALOHA算法识别相同的标签需要的时隙数总体是少于DFS-ALOHA算法的，在标签数少于100时，差距不大，但是随着标签个数的增加时隙数相差越来越大。因此在工程中可以根据实际应用场景选取合适的算法，如果待识别标签少于100建议采用DFS-ALOHA算法，当标签大于100时为了减少识别时间，提高准确率可以采用Q-ALOHA算法。

4 小结

本文首先分析了物联网中自动识别技术RFID中碰撞产生的原因及分类，然后针对RFID技术中最常见的碰撞类型——多标签碰撞进行了分析，针对工程实际中较常用的标签碰撞算法DFS-ALOHA以及Q-ALOHA算法的工作流程进行分析，并通过Matlab模拟算法的实际执行过程，对比分析了算法的效率实用性，应用场合等。

[1] 游战清. 无线射频技术(RFID)理论与应用[M]. 北京：电子工业出版社，2004,30-38.

[2] 黄玉兰. 射频识别(RFID)核心技术详解[M]. 北京：人民邮电出版社，2010.

[3] 中国行业研究网. 未来超高频RFID发展趋势分析[EB/OL]. http://www.chinairn.com. Xiao X, Wang WP, Yang L M, et al. Wireless broadcasting retransmission approach based on network coding[J]. Journal on Communications,2009,30(9):69-75.

[4] EPC Global. EPC Radio-Frequency Identity Protocols Gengernation-1[S].

[5] ISO/IEC. TR 24729-1-2008.Information technology-Radio frequency identification for item management-Implementation guidelines-Part 1[S].

[6] Lee S R, Joo S D, Lee C W. An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification[C]. Mobile and Ubiquitous Systems: Networking and Services, 2005. MobiQuitous 2005. The Second Annual International Conference on[C]. IEEE, 2005: 166-172.

[7] 梁钊. ALOHA随机多址通信技术-从纯ALOHA到扩展ALOHA[J].移动通信, 1999(5):17-20.

[8] 吴春华, 陈军. 动态ALOHAX法在解决RFID反碰撞问题中的应用[J]. 电子器件, 2003,26(2):173-176.

Introduction of collisions of RFID in Internet of Things

WU Bi-zao1, YANG Xiao-jiao2
(1 China Mobile IoT Company Limited, Chongqing 401336, China; 2 Information Technology Centre, Chongqing Jiaotong University, Chongqing 400074, China)

This paper introduce the collision cause of radio frequency identif i cation system, then discussed the most common collision form that is multi-tag collision and its anti-collision algorithm. This paper mainly focus on the performance and the application scenarios of dynamic framed slot ALOHA and query ALOHA algorithm whichmostly used in engineering. Therefore I hope that through this paper will enlighten those readers which need to solve multi-tag collision problem.

Internet of Things; radio frequency of identif i cation; multi-tag anti-collision

TP393

A

1008-5599（2017）05-0022-04

2017-04-10