杨晓娇1，吴必造2

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

     摘要：先对RFID系统中的确定性防碰撞算法BS的工作原理进行介绍，同时对基于BS的改进算法原理做分析；然后介绍了QT算法工作原理，并对基于QT算法的改进算法工作原理做了分析；最后结合作者自身的经验对未来确定性防碰撞算法可以继续进行研究的方向给出建议，对确定性防碰撞算法的后续研究具有一定的参考价值。

　　关键词：RFID；确定性防碰撞算法；BS；QT

　　中图分类号：TP312文献标识码：ADOI： 10.19358/j.issn.1674-7720.2017.08.021

　　引用格式：杨晓娇，吴必造.射频识别中确定性防碰撞算法研究［J］.微型机与应用，2017,36（8）：67-69.

0引言

　　射频识别(Radio Frequency Identification, RFID)是一种新兴的无线通信技术，它可以利用无线电信号来实现目标的非接触式自动识别，是物联网底层关键支撑技术之一［1］。在众多RFID应用场景中，读写器往往需要同时与多个标签进行通信。由于读写器与标签之间的通信信道是共享的，当多个标签同时向读写器发送数据时会产生多标签碰撞，进而引发带宽浪费、能量耗损和增加系统识别时延等一系列问题［23］。为了解决多标签碰撞问题，读写器需要采用防碰撞算法来协调读写器与多标签之间的通信。防碰撞算法主要有两类：确定性防碰撞算法和概率性防碰撞算法［4］。

　　概率性防碰撞算法即不确定性防碰撞算法（ALOHA）及其改进算法的优点是算法复杂度较低，工程实现难度较低；缺点是存在标签饿死等情况。确定性防碰撞算法的优点是不存在标签饿死的情况，即对标签的识别率能达到100%，算法稳定可靠；缺点是算法的时间复杂度和实现难度相对较高，其应用于对安全性要求较高的RFID系统。确定性标签防碰撞算法也是本文研究的重点，本文首先介绍了BS算法及其较好的改进算法的流程，然后介绍了QT类改进算法的工作流程，并结合作者的经验说明了未来改进防碰撞算法的研究方向。

1BS算法及其衍生防碰撞算法

　　图1BS算法流程图确定性防碰撞算法主要包括二进制搜索(Binary Search, BS)和查询树(Query Tree, QT)两种算法。下面分别介绍这两类算法。

　　1.1BS算法

　　BS算法的实现需要标签和阅读器之间有严格的时间同步［5］，算法基本流程如图1所示，阅读器先通过命令Request(N)广播一个初始化的二进制部分ID串号给其工作域内的标签。当标签收到阅读器的查询命令后，将自身的ID同接收到的串号相比较，那些ID小于等于串号的标签会发送自身的ID给阅读器。当多个标签同时向阅读器发送ID时，利用曼彻斯特编码，阅读器就可以准确地检测到碰撞ID的具体位置［6］，然后根据最高碰撞位重新调整Request(N)中ID串即N的值对标签。

　　继续进行分组。当某组中只存在一个标签时，阅读器就可以成功识别标签。读写器成功识别到一个标签后，会发送初始化串号来重启识别过程。

　　1.2增强型的二进制搜索算法

　　余松森等人在BS算法的基础上引入了回退机制［7］，即每当阅读器成功识别一个标签后，不会发送初始的串号来重启识别过程，而是发送当前节点的上一级碰撞位的数据。这种算法又称为增强型的二进制搜索算法(Enhanced Binary Splitting Algorithm, EBSA)，由于每次识别结束后EBSA算法不需要返回根节点，因此相对于BS算法，EBSA算法中阅读器的寻呼次数较少。

　　1.3动态二进制搜索算法

　　由于BS算法要求标签每次都传输完整的ID，造成了带宽的浪费，增加了识别延迟。为了降低传输延迟，又有学者提出了动态二进制搜索算法(Dynamic Binary Search Algorithm, DBSA)。在DBSA算法中，标签只需要向阅读器回复与查询前缀匹配后的剩余ID即可。例如，假设阅读器接收到标签回复的数据为“1011x1x1”，那么在下一个时隙，标签只需要传输1011之后的最后四位ID即可，因为阅读器已经将成功识别部分的ID进行存储，并会将正确识别的部分ID作为下一次查询命令Request(N)的参数N。相比于BS算法和EBSA算法，DBSA有效地减少了阅读器与标签通信过程中的传输数据量。

2QT算法及其衍生算法

　　目前，QT类算法是应用和研究最广泛的一种确定性算法。QT算法最早由LAW C提出［6］。下面分别介绍QT算法及其改进算法。

　　2.1QT算法

　　QT算法规定阅读器使用一个堆栈来存储查询前缀。在每一次寻呼过程中，读写器都会向其工作域内的标签广播携带标签部分ID前缀的查询命令，与BS算法的区别是只有和查询前缀相匹配的标签会回复阅读器。如果有多个标签同时请求通信，此时就会产生碰撞，阅读器先将当前的查询前缀压入堆栈，然后根据接收到的碰撞位来更新查询前缀。如果正确识别标签则阅读器将重堆栈中取出查询前缀作为查询命令的参数，直到堆栈为空时，整个识别过程才会结束，算法流程如图2所示。

　　2.2基于QT的改进算法

　　下面有针对性地介绍几类不同的基于QT的改进算法。

　　(1)SQT(Shortcutting QT)算法

　　该算法的主要改进之处是在原始QT算法的基础上通过减少QT算法的冗余查询次数，从而减少了算法的识别时间［8］。SQT的工作流程为：首先阅读器发送一个带有前缀N的Request(N)查询命令，若检测到碰撞，阅读器会将N0和N1压入堆栈；阅读器先发送带有前缀N0的查询命令，若检测到空闲，那么读写器就说明至少有2个标签与前缀N1匹配；若阅读器在下一个时隙发送带有前缀N1的查询命令，必然会引起碰撞，于是阅读器会先将N1前缀从堆栈中移除，然后将N10和N11压入堆栈。

　　（2）AQT(Aggressive advancement QT)算法

　　该算法的核心是通过一次对多比特数据入栈的形式来更新查询前缀，因此相较于QT算法的每次单比特查询数据入栈，在标签数量较多时可减少阅读器的寻呼次数［9］。AQT算法的流程为：首先阅读器发送一个带有前缀N的Request(N)查询命令，若发送查询前缀N后，标签回复有碰撞，阅读器会直接将前缀更新为N00、N01、N10和N11并压入堆栈；阅读器依次发送带有前缀的查询命令。

　　（3）QTsl（QT short-long）算法

　　该算法改进之处在于将阅读器的查询命令分为“长查询”和“短查询”，这样长短结合的查询命令有效减少了阅读器的冗余数据传输量。算法在识别中如遇碰撞则采用短查询命令让标签只返回1 bit数据，在匹配到的标签没有碰撞时则采用长查询命令让标签返回完整ID。即当读写器知道仅有一个标签与当前的查询前缀匹配时才会发送“长查询”命令。因此QTsl算法相较于QT数据量较少。

　　2.3基于QT改进算法研究展望

　　早期QT类算法都是采用单比特碰撞仲裁机制即类似二叉树的查询方法，现在研究者提出的许多QT算法都是基于多比特碰撞仲裁的，采用多比特入栈查询的方法，即多叉树查询的方式，主要包括：提高型四叉树查询树算法(Improved 4ary Query Tree Algorithm, I4QTA)、混合查询树(Hybrid Query Tree, HQT)算法、自适应多叉树(Adaptive Multitree Search, AMS)算法、自调整混合树(Adjustive Hybrid Tree, AHT)算法、多进制查询树(Mary Query Tree, MQT)算法、基于碰撞位跟踪的分组N叉跟踪树形算法(Collision bit Tracking Tree Algorithm based on Grouping Nary, CBGN)等［10］。

　　而未来的研究可以从如下几个方面着手：第一，可以沿用当前寻呼命令，通过多比特仲裁的方式减少寻呼次数令，从而提高算法性能；其次，可以改进寻呼命令来减少冗余数据的传输，从而提高算法效率；再者，也可以结合不确定性算法的优点从而减少算法的复杂度，进而提高效率。

3结论

　　确定性算法的优点是不存在标签饿死的问题，即在一定的时间内算法对阅读器作用域内标签的识别率能达到100%，且相较于不确定性算法吞吐率较高，因此适用于对标签读取准确性研究较高的情况。其不足是算法的时间复杂度较高、需要硬件支持曼侧斯特编码和严格的时间同步，要求阅读器内部设计一个堆栈来记录查询前缀信息，标签内部设计一个前缀匹配电路来配合阅读器的查询。因此系统的硬件成本和工程实现的复杂度较不确定性算法高。

　　确定性算法的基本算法是BS算法，而现在针对确定性算法的研究主要集中在QT算法上。QT算法基本是基于二叉树的算法，现在的研究通过查询前缀将算法进行改进，主要集中在多叉树以及二叉树与多叉树动态结合来减少查询命令的次数，从而提高算法效率。本文介绍了多种比较好的基于QT的改进算法，为防碰撞算法的后续研究提供参考，并结合作者的个人经验，建议针对确定性算法接下来可以继续研究的方向，对确定性算法的研究具有一定的参考价值。

参考文献

　　［1］ 宁焕生, 王炳辉. RFID重大工程与国家物联网［M］. 北京：机械工业出版社, 2009.

　　［2］ 黄玉兰.物联网射频识别(RFID)核心技术详解［M］. 北京：人民邮电出版社，2012.

　　［3］ 王晓华，周晓光，王伟. 射频识别（RFID）系统设计，仿真与应用［M］. 北京：人民邮电出版社，2008.

　　［4］ LANDT J. The history of RFID［J］. IEEE Potentials, 2005, 24(4): 811.

　　［5］ FINKENZELLER K. RFID handbook: fundaments and application in contactless smart card and identification［M］. Hoboken: John Wiley & Sons, 2003.

　　［6］ LAW C, LEE K, SIU K Y. Efficient memoryless protocol for tag identification［C］. Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM for Mobility), Boston, 2000, 12(5): 32-38.

　　［7］ 余松森，詹宜巨，王志平，等. 跳跃式动态树形反碰撞算法及其分析［J］. 计算机工程，2005，31(9): 19-20.

　　［8］ 丁治国，朱学永，郭立，等. 自适应多叉树防碰撞算法研究［J］. 自动化学报，2010，36(2): 237-341.

　　［9］ DJEDDOU M, KHELLADI R, BENSSALAH M. Improved RFID anticollision algorithm［J］. AEUInternational Journal of Electronics and Communications, 2013, 67(3): 256262.

　　［10］ 王鑫，贾庆轩，高欣，等. 分组N叉跟踪树形RFID防碰撞算法研究［J］. 电子学报，2016，44(2): 437-444.