射频识别中确定性防碰撞算法研究

《微型机与应用》2017年第36卷第8期欢迎网上投稿www．pcachina．com射频识别中确定性防碰撞算法研究杨晓娇1，吴必造2（1．重庆交通大学信息技术中心，重庆400074；2．中移物联网有限公司解决方案中心，重庆401336）摘要：先对ＲFID 系统中的确定性防碰撞算法BS 的工作原理进行介绍，同时对基于BS 的改进算法原理做分析；然后介绍了QT 算法工作原理，并对基于QT 算法的改进算法工作原理做了分析；最后结合作者自身的经验对未来确定性防碰撞算法可以继续进行研究的方向给出建议，对确定性防碰撞算法的后续研究具有一定的参考价值。

关键词：ＲFID ；确定性防碰撞算法；BS ；QT 中图分类号：TP312文献标识码：ADOI ：10．19358/j．issn．1674-7720．2017．08．021引用格式：杨晓娇，吴必造．射频识别中确定性防碰撞算法研究［J ］．微型机与应用，2017，36（8）：67-69．Ｒesearch on the certainty anti-collision algorithm of radio frequency identification systemYang Xiaojiao 1，Wu Bizao 2（1．Information Technology Centre ，Chongqing Jiaotong University ，Chongqing 400074，China ；2．Solutions Center ，China Mobile IOT Company Limited ，Chongqing 401336，China ）Abstract ：This paper mainly focuses on the certainty anti-collision algorithm in Ｒadio Frequency Identification （ＲFID ）system．Firstly it pres-ents the basic working principles of Binary Search （BS ）algorithm and introduces some improved algorithms on the basis of BS．Then it discus-ses the basic working principles of Query Tree （QT ）algorithm and introduces some improved algorithms on the basis of QT．Finally ，combined with the author ’s own experience ，the directions for future research are proposed．So the work done in this paper will provide some reference for the follow-up study of certainty anti-collision．Key words ：ＲFID ；certainty anti-collision algorithm ；BS ；QT0引言射频识别（Ｒadio Frequency Identification ，ＲFID ）是一种新兴的无线通信技术，它可以利用无线电信号来实现目标的非接触式自动识别，是物联网底层关键支撑技术之一［1］。

在众多ＲFID 应用场景中，读写器往往需要同时与多个标签进行通信。

由于读写器与标签之间的通信信道是共享的，当多个标签同时向读写器发送数据时会产生多标签碰撞，进而引发带宽浪费、能量耗损和增加系统识别时延等一系列问题［2-3］。

为了解决多标签碰撞问题，读写器需要采用防碰撞算法来协调读写器与多标签之间的通信。

防碰撞算法主要有两类：确定性防碰撞算法和概率性防碰撞算法［4］。

概率性防碰撞算法即不确定性防碰撞算法（ALOHA ）及其改进算法的优点是算法复杂度较低，工程实现难度较低；缺点是存在标签饿死等情况。

确定性防碰撞算法的优点是不存在标签饿死的情况，即对标签的识别率能达到100%，算法稳定可靠；缺点是算法的时间复杂度和实现难度相对较高，其应用于对安全性要求较高的ＲFID 系统。

确定性标签防碰撞算法也是本文研究的重点，本文首先介绍了BS 算法及其较好的改进算法的流程，然后介绍了QT类改进算法的工作流程，并结合作者的经验说明了未来改进防碰撞算法的研究方向。

1BS算法及其衍生防碰撞算法图1BS 算法流程图确定性防碰撞算法主要包括二进制搜索（BinarySearch ，BS ）和查询树（Query Tree ，QT ）两种算法。

下面分别介绍这两类算法。

1．1BS 算法BS 算法的实现需要标签和阅读器之间有严格的时间同步［5］，算法基本流程如图1所示，阅读器先通过命令Ｒequest （N ）广播一个初始化的二进制部分ID 串号给其工作域内的标签。

当标签收到阅读器的查询命令后，将自身的ID 同接收到的串号相比较，那些ID 小于等于串号的标签会发送自身的ID 给阅读器。

当多个标签同时向阅读器发送ID 时，利用曼彻斯76特编码，阅读器就可以准确地检测到碰撞ID的具体位置［6］，然后根据最高碰撞位重新调整Ｒequest（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作为下一次查询命令Ｒequest（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的工作流程为：首先阅读器发送一个带有图2QT算法的程序流程图前缀N的Ｒequest（N）查询命令，若检测到碰撞，阅读器会将N0和N1压入堆栈；阅读器先发送带有前缀N0的查询命令，若检测到空闲，那么读写器就说明至少有2个标签与前缀N1匹配；若阅读器在下一个时隙发送带有前缀N1的查询命令，必然会引起碰撞，于是阅读器会先将N1前缀从堆栈中移除，然后将N10和N11压入堆栈。

（2）AQT（Aggressive advancement QT）算法该算法的核心是通过一次对多比特数据入栈的形式来更新查询前缀，因此相较于QT算法的每次单比特查询数据入栈，在标签数量较多时可减少阅读器的寻呼次数［9］。

AQT算法的流程为：首先阅读器发送一个带有前缀N的Ｒequest（N）查询命令，若发送查询前缀N后，标签回复有碰撞，阅读器会直接将前缀更新为N00、N01、N10和N11并压入堆栈；阅读器依次发送带有前缀的查询命令。

（3）QT-sl（QT short-long）算法该算法改进之处在于将阅读器的查询命令分为“长查询”和“短查询”，这样长短结合的查询命令有效减少了阅读器的冗余数据传输量。

算法在识别中如遇碰撞则采用短查询命令让标签只返回1bit数据，在匹配到的标签没有碰撞时则采用长查询命令让标签返回完整ID。

即当读写器知道仅有一个标签与当前的查询前缀匹配时才会发送“长查询”命令。

因此QT-sl算法相较于QT数据量较少。

2．3基于QT改进算法研究展望早期QT类算法都是采用单比特碰撞仲裁机制即类似二叉树的查询方法，现在研究者提出的许多QT算法都是基于多比特碰撞仲裁的，采用多比特入栈查询的方法，即多叉树查询的方式，主要包括：提高型四叉树查询树算法（Improved4-ary Query Tree Algorithm，I4QTA）、混合查询树（Hybrid Query Tree，HQT）算法、自适应多叉树（A-daptive Multi-tree Search，AMS）算法、自调整混合树（Ad-justive Hybrid Tree，AHT）算法、多进制查询树（M-ary Que-ry Tree，MQT）算法、基于碰撞位跟踪的分组N叉跟踪树形算法（Collision bit Tracking Tree Algorithm based on Grouping N-ary，CBGN）等［10］。

而未来的研究可以从如下几个方面着手：第一，可以沿用当前寻呼命令，通过多比特仲裁的方式减少寻呼次数令，从而提高算法性能；其次，可以改进寻呼命令来减少冗86《微型机与应用》2017年第36卷第8期《微型机与应用》2017年第36卷第8期欢迎网上投稿www．pcachina．com余数据的传输，从而提高算法效率；再者，也可以结合不确定性算法的优点从而减少算法的复杂度，进而提高效率。