RFID防碰撞算法的研究

秦连芃， 王 喆

（兰州交通大学电子与信息工程学院 兰州 730070）

0 引言

射频识别技术（Radio Frequency Identification,RFID）是一种非接触式的自动识别技术，它通过射频信号自动识别目标对象并获取相关数据，识别过程无须人工干预，可工作于各种恶劣的环境。RFID领域处于物联网发展的最前端，也是实现物联网的基础技术之一[1]。

RFID系统主要包括标签（Tag）和读写器（Reader）两部分。标签适用于对象身份识别，它的主要模块集成在一个芯片中，芯片内存用来存储ID或其他数据。读写器主要由一个RF模块和控制单元组成，通常有内置天线，通过射频信号与标签通信，标签将自身ID号发送给读写器，达到身份识别的目的。阅读器作用范围内存在多个标签，同一时刻有两个或以上的标签向读写器返回信息时，将产生冲突，称为标签冲突。这个冲突被称为碰撞（collision），其结果将会导致一次传输的失败。为了解决上述问题而产生了防碰撞算法。

1 防碰撞算法

RFID防碰撞算法在广义上可分为码分多址（Code Domain Multiple Access，CDMA）、频分多址（Frequency Domain Multiple Access，FDMA）、时分多址（Time Domain Multiple Access，TDMA），以及空分多址（Space Domain Multiple Access，SDMA）4大类。目前在RFID系统中应用最多、种类最广的算法是基于TDMA的防碰撞算法。RFID防碰撞算法又可以分为确定性算法和非确定性算法2大类[2]。如图1所示。

表1对非确定性防碰撞算法与确定性防碰撞算法进行了比较，列出各自的优缺点。

图1 RFID防碰撞算法分类

表1 非确定性防碰撞算法与确定性防碰撞算法比较

2 非确定性防碰撞算法分析与仿真

非确定性防碰撞算法主要是在Aloha算法基础上的研究与改进，其基本原理是不同标签在不同的时隙发送识别编码，达到防碰撞的目的。其中包括纯ALOHA算法（Pure ALOHA，PA），时隙ALOHA算法（Slotted Aloha，SA），帧时隙ALOHA算法（Frame Slotted Aloha，FSA）及动态帧时隙ALOHA算法（Dynamic Frame Slotted Aloha，DFSA）。

PA算法是所有多路存取中最简单的一种方法，在阅读器作用范围内的标签随机产生应答时间。

SA算法是在PA算法的基础上，将信道分成若干时隙，标签只在规定的同步时隙内传输数据包，因此冲突只在时隙边界处才会发生。

FSA算法是在SA算法的基础上，将多个时隙组成一帧，标签在每一帧内随机选择一个时隙发送自己的数据信息。

DFSA算法通过估算阅读器作用范围内的标签数目动态地调整帧的长度，以求在减少冲突标签和避免空闲时隙之间寻找平衡点。

表2为非确定性防碰撞算法吞吐率计算公式及最大吞吐率的比较。

表2 非确定性防碰撞算法比较

表2中S为吞吐率，G为输入负载即系统交换的数据包量，n为读写器识别范围内的标签数，N为时隙数。其中动态帧时隙ALOHA算法的N是根据读写器识别范围内的标签数n不同而变化的。图2为非确定性防碰撞算法的仿真。

图2 非确定性防碰撞算法仿真

从图2中可以看出非确定性防碰撞算法对系统的利用率不高，理想状态下也只能达到36.8%。

3 确定性防碰撞算法分析与仿真

由于非确定性防碰撞算法无法保证在规定时间内完成阅读器作用范围里所有的标签的辩识，且信道利用率也较低，因此，对于希望识别率达到100%应用，尤其是在超高频段环境下，往往采用确定性的防碰撞算法。确定性防碰撞算法主要是基于树形的算法，包括树形分裂（Tree splitting，TS）算法、询问树（Query Tree，QT）算法、二进制搜索（Binary search，BS）算法及按位仲裁（Bit wise arbitration，BTA）算法。

TS算法基本思想是当碰撞发生时，采用随机方式将标签分成若干子组，分组数目会不断增加直到每组内仅包含一个标签。TS算法中的每个标签都要一个随机数产生器和一个计数器以追踪其在树上的位置，这增加了标签成本及计算复杂度。

QT算法则是将所有复杂运算交由阅读器处理，标签始终处于“无记忆”状态，仅需包含一个前缀匹配电路。该协议无需时隙划分，无须内存且能耗很小，但在标签位数较长时搜索范围很大，因此其应用受到一定限制。

在BS算法中，标签的序列号必须采用曼彻斯特编码。阅读器根据已接收到的来自标签的应答，找到碰撞位，并据此向它们发送不同的请求信号或命令，采用二叉树查找的方法，从作用范围内的标签中筛选出唯一一个标签进行通信。

BTA算法是按位对标签编码进行询问，其关键是所有标签同步发送位信息，当阅读器发现某一位有多个标签发生碰撞，则将从该位入手，对标签编码进行进一步分析。

表3为确定性防碰撞算法的比较。

表3 确定性防碰撞算法比较

表3中mi为第i组的标签数，n为总标签数，k为标签长度。图3为确定性防碰撞算法的仿真。

图3 确定性防碰撞算法仿真

从图3中可以看出确定性防碰撞算法随着标签数量的增加，阅读器对标签的搜索次数将急剧增加，这严重影响了读取速度。

4 结束语

非确定性防碰撞算法识别速度快，缺点是识别率低；确定性防碰撞算法识别率高，但当标签数量比较大时识别速度慢。在实际应用中，RFID系统必须在高误码率环境下，以最快的速度无漏读地识别大量标签。这就需要结合两种算法的优点设计一种新的算法，提高RFID系统识别速度和标签读取率。

[1]周晓光,王晓华.射频识别(RFID)技术原理与应用实例[M].北京:人民邮电出版社,2006.

[2]谭民,刘禹,曾隽芳,等.RFID技术系统工程及应用指南[M].北京:机械工业出版社,2007.

[3]于洁潇.基于RFID的情境感知关键技术研究[D].天津:天津大学,2010.

[4]崔沂峰,陈平.RFID电子标签防碰撞算法的研究[J].微计算机信息,2007(27):233-244.

[5]张刚建,邹传云.RFID系统防碰撞协议的研究[J].电子技术应用,2010(12).

[6]李宝山,罗春青.RFID防碰撞算法计算机仿真模型的研究[J].自动化与仪器仪表,2010(05).

[7]中华人民共和国科学技术部等十五部委.中国射频识别(RFID)技术政策白皮书[R].北京:中华人民共和国科学技术部等十五部委,2006.

[8]EPC global.Electronic product code [OL].http://www.epcglobalinc.org/home/.

[9]ISO.RFID Standards [OL].http://www.iso.org/iso/search.htm?qt=RFID&published=on&active tab=standards.

[10]Dheeraj K.Klair, Kwan-Wu Chin, Raad.A Survey and Tutorial of RFID Anti-Collision Protocols[J].IEEE Communications Surveys&Tutorials,Third Quarter,2010,12(3):400-420.

[11]J.Myung, W.Lee, J.Srivastava.Adaptive binary splitting for efficient RFIDtag anti-collision[J].IEEE Personal Commun.Mag,2006,10(3):144-146.