贾小林 冯全源 雷全水

(1.西南科技大学计算机科学与技术学院 四川绵阳 621010;2.西南交通大学信息科学与技术学院 四川成都 610031)

射频识别(radio frequency identification，RFID)技术是一种基于无线射频通信原理的非接触式自动识别技术，是物联网(IOT)感知层的核心支撑技术之一［1－4］。RFID系统采用射频信号通过空间耦合方式实现无接触信息传递，并达到识别目标对象的目的，当多个标签在相同信道同时与阅读器进行通信时，信号在空中媒介发生干扰，就会引发碰撞(collision)，导致标签识别和数据传送失败［5－6］。因此，需要建立有效的防碰撞机制，即防碰撞算法(anti－collision algorithm)或防碰撞协议(anti－collision protocol)，来协调阅读器与标签之间的通信，以实现多个标签的同时识别。所以，防碰撞算法是RFID多标签识别的关键技术，也是RFID系统及应用研究的核心内容之一。

解决RFID多标签识别的防碰撞算法主要分为两个大类［7－10］:一类是基于 ALOHA的时隙类防碰撞算法，如:纯ALOHA算法、时隙ALOHA算法(SALOHA)、帧时隙ALOHA算法(FSA)、动态帧时隙ALOHA算法(DFSA);另一类是基于树搜索的防碰撞算法，如:查询树算法(QT)、二进制树算法(BT)、二进制搜索算法(BS)。这些算法是防碰撞算法研究和应用中的经典算法和基础算法，在其基础上产生了许多改进型或杂合型算法。研究表明［7－10］:经典防碰撞算法及其改进算法或杂合算法的识别效率通常只有34% ～36.8%，还不能满足RFID多标签识别系统的实际需要。

文献［11－12］提出了一种基于碰撞树的防碰撞算法，即碰撞树算法(collision tree protocol，CT)，将RFID多标签识别效率提高到50%以上。CT算法完全消除了RFID多标签识别过程中可能出现的空周期，打破了多标签识别的效率瓶颈，具有严格的树型结构对其识别性能和识别过程进行分析和描述。因此，CT算法开启了基于碰撞树的防碰撞算法系列，并成为该算法系列的代表算法。文献［13］提出了一种改进型碰撞树算法(ICT)，进一步提高了RFID多标签识别效率，特别是当标签编号连续分布时，标签识别效率达到100%以上。

本文提出另一种基于CT算法的高性能RFID多标签识别防碰撞算法，即多周期碰撞树算法(multi－cycles collision tree algorithm，MCT)。该算法在保持CT算法优势的同时，减少了阅读器的查询次数，降低了阅读器和标签的通信复杂度，将多标签识别效率提高到100%以上。

1 多周期碰撞树算法

1.1 基本原理

在RFID系统中，标签编号的每一位只有两种可能取值，即“0”和“1”，且每一次只能取其中之一。同时，根据标签编号中二进制位的取值情况，能且只能将集合中的标签划分为两个确定的子集，其中一个子集标签编号该位为“1”，而另一个子集标签编号该位为“0”。这种标签编号位的二元性与标签集合划分的二元性以及它们相互之间确定的对应关系，即为二元确定性原理［13］。

根据二元确定性原理，论文将RFID多标签识别中阅读器与标签之间完成通信的识别周期划分为3个子周期:阅读器查询周期Q，标签的响应周期R0和R1.标签根据收到的查询命令，确定标志位，并根据标志位的值(0或1)选择响应周期(R0或R1)响应阅读器的查询请求。由此，阅读器的一次查询可以获得两组标签的响应。

1.2 算法过程

多周期碰撞树算法(MCT)的基本过程如图1所示。

图1 多周期碰撞树算法(MCT)的工作流程Fig.1 Work processes of MCT

初始时，阅读器向前缀缓冲池中放入一个空串ε，并将标签编号tagID置为空NULL。开始识别时，阅读器从前缀缓冲池中取出一个前缀，并以此前缀为参数，发送查询命令Query(prefix)。阅读器进入等待状态，等待并接收标签的响应。

由于初始时搜索前缀prefix为空串，所以，在第一次查询中，所有标签均响应阅读器的查询请求。此时，标签编号的第一位即为首个标志位。标志位为0的标签，在R0中发送自己的编号ID，响应阅读的请求;标志位为1的标签，在R1中发送自己的编号ID，响应阅读的请求。

通常情况下，标签编号ID中与prefix匹配后，紧邻的一位为标志位。例如:对于前缀p1，p2…pk，标签编号r1r2…rjrj+1…与之相匹配，则rj+1为标志位。rj+1=0的标签在R0响应阅读器的查询，rj+1=1的标签在R1响应阅读器的查询。标签响应过程中，只需要传送编号ID中与p1p2…pk匹配之后的部分，即rj+1…，与前缀相同的部分，不需要发送。

阅读器重复上述查询过程，直到前缀池为空(NULL)，即完成所有标签的识别。

1.3 算法实例

图2给出了MCT算法的一个实例，即采用MCT算法识别标签 组 {001010，011100，000110，010101，111001，110001，110010，111010}的基本过程及树型结构。如图2所示，MCT算法经过7次查询和响应过程，完成了这8个标签的识别。每次阅读器查询，两组标签分别在R0和R1对阅读器的请求发出响应。如果一个响应子周期只有一个标签满足条件，发出了响应，则阅读器识别到该标签，而且，阅读器可以在一次查询中识别到两个标签，如图2中粗体表示的结点所示。

图2 MCT算法的识别实例Fig.2 An example of MCT

表1给出了MCT算法实例(图2)中阅读器与标签之间的通信过程。首次查询，阅读器以空串ε作为前缀，所有标签以首位为标志位，并根据标志位的值，选取响应子周期，发送各自的编号ID。阅读器收到的响应中，如果发生碰撞(表1中用“x”表示)，则生成一个新前缀，放入前缀池;如果没有发生碰撞，则成功识别到一个标签。除首次响应外，标签在响应阅读器请求时，只发送与前缀匹配后余下的编号位。当前缀池为空(NULL)时，阅读器完成全部标签识别。

表1 MCT算法实例中阅读器与标签之间的通信过程Table 1 Communications between the reader and tags in the example of MCT

为了便于比较分析，图3给出了采用CT算法识别这组标签的基本过程及树型结构。如图3所示，经过15次查询和响应过程，CT算法完成这8个标签的识别。阅读器每次查询只能获得一组标签响应。如果只有一个标签响应，没有发生碰撞，则阅读器识别到一个标签，如图3中叶节点所示。

图3 CT算法识别图2中标签的基本过程Fig.3 Basic Process of using CT to identify the tags in Fig.2

2 MCT算法性能分析

2.1 时间复杂度

在RFID系统中，防碰撞算法的时间复杂度(time complexity)是指完成标签集合中全部标签的识别所需要的查询周期数。树型防碰撞算法中，多标签识别的过程就是从根节点搜索叶节点的过程，因此，防碰撞算法的时间复杂度与树型结构中节点总数相等。由MCT算法与CT算法的识别过程可知，MCT算法中每一个节点涵盖了CT算法中3个节点，包括双亲节点及其两个孩子节点，如图2和图3所示。所以，MCT算法树型结构中的节点总数与CT算法树型结构中的中间节点数相等。因此，除去CT算法树型结构中的叶节点，即可得到MCT算法的树型结构。

由文献［11］的分析:CT算法的时间复杂度为:

其中，n为识别标签的数量，且等于CT算法树型结构中叶节点的数量。所以，由MCT算法和CT算法的关系，可以得到MCT算法的时间复杂度为:

其中，n＞1。当n=1时，T(n)=1。

2.2 通信复杂度

防碰撞算法的通信复杂度(communication complexity)是指RFID多标签识别过程中阅读器和标签传输二进制数的位数。设C(n)为MCT算法的通信复杂度，CR(n)和CT(n)分别为其阅读器通信复杂度和标签通信复杂度，其中，n为标签数量，则有:

设lcom为标签识别过程中命令字的长度，lpre，i为阅读器在识别周期i发送的前缀长度，lrep，i为标签在识别周期i发送的响应二进制位串的长度，则公式(3)可改写为:

其中，T(n)为MCT算法的时间复杂度。设lID为标签编号的长度，由MCT算法阅读器和标签通信响应过程，则有:

由公式(2)，(4)，(5)，可得:

2.3 识别效率

防碰撞算法的识别效率(identification efficiency)是指识别标签的数量与完成这些标签识别所需要的查询周期数量之间的比率。设E(n)为MCT算法的识别效率，则由公式(2)可得:

由于n为正整数，n＞1，所以有:

3 实验及结果分析

论文主要将MCT算法与几种经典的主流防碰撞算法进行实验对比，对比算法包括:CT算法、QT算 法［9，12］、BT 算 法［9，12］、BS 算 法［6］、FSA 算法［7－8，10］。参照 EPCglobal Class 1 Generation 2 相关要求，实验环境设置如下［11－13］:

系统为单阅读器多标签识别系统，标签数量从4个增加到4 096个，标签编号长度为96位;所有实验组的标签编号均匀分布，且其中没有任何两个标签的编号相同;选用两个必要的通信命令:Query命令(22位)用于阅读器查询标签，ACK命令(18位)用于通知成功识别到的标签。

3.1 时间复杂度比较

图4给出了MCT算法在时间复杂度方面的比较优势曲线。与其它几种防碰撞算法的时间复杂度相比，MCT算法在时间复杂度性能上具有明显的优势。完成一个标签的识别，MCT算法平均仅需要1次查询搜索，CT算法需要2次，QT算法需要3次，而FSA算法、BT算法、BS算法则需要花费更多次的搜索查询。

图4 MCT算法的时间复杂度优势Fig.4 Advantage of time complexity of MCT

3.2 通信复杂度比较

图5给出了MCT算法在通信复杂度方面的比较优势曲线。在通信复杂度方面，MCT算法也具有明显的优势。完成一个标签的识别，MCT算法的平均数据传输量只有CT算法的75%左右，QT算法的50%左右。通信复杂度在一定程度上反映了在多标签识别过程中系统的能量消耗。因此，在系统能耗方面MCT算法也具有明显的优势。

由于在FSA算法中标签通过随机生成的时隙号选择一帧中的时隙进行数据传送，阅读器也不需要发送前缀信息。因此，FSA算法的通信复杂度低于其它几种防碰撞算法的通信复杂度，但是，FSA算法的通信复杂度却比MCT算法高出约20%。

图5 MCT算法的通信复杂度优势Fig.5 Advantage of communication complexity of MCT

3.3 识别效率比较

在识别效率方面，MCT算法的性能远远超过了其它防碰撞算法。如图6所示，MCT算法的识别效率始终在100%以上，CT算法的识别效率为50%，QT算法的识别效率约为34%，其它几种防碰撞算法的识别效率更低。除CT算法和MCT算法外，其它防碰撞算法的识别效率均在50%以下。

图6 MCT算法的识别效率优势Fig.6 Advanfage of Identification efficiency of MCT

4 结论

本文提出了一种高性能的RFID多标签识别防碰撞算法，即多周期碰撞树算法(MCT)。MCT算法在降低算法时间复杂度、通信复杂度和系统能耗的同时，提高了多标签识别的效率，在识别性能上具有明显的优势。同时，在MCT算法中，标签的每次响应只与当前收到的前缀有关，而与过往的查询过程和响应历史无关。因此，同CT算法一样，MCT算法也属于无记忆(memoryless)防碰撞算法，可适用于无源被动RFID多标签识别系统及其它RFID应用系统，解决标签碰撞问题。

［1］中国科技部，等.中国射频识别(RFID)技术政策白皮书［Z］.2006.

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

［3］WANG Yong－ heng，ZHANG Xiao－ ming.Internet of Things［M］.InternationalWorkshop IOT 2012，Springer－Verlag，Berlin，Heidelberg，2012.

［4］JIA Xiao － lin，FENG Quan － yuan，FAN Tai－ hua，et al.RFID Technology and Its Applications in Internet Of Things(IOT)［C］.2nd International Conference on Consumer Electronics，Communications and Networks，2012，(2):1282 －1285.

［5］Bang O，Choi JH，Lee D，et al.Efficient Novel Anticollision Protocols for Passive RFID Tags:Bi－slotted Tree Based RFID Tag Anti－ collision Protocols，Query Tree Based Reservation，and the Combining Method of Them［R］.Auto－ID Labs White Paper WP－HARDWARE －050，MIT，2009.

［6］FINKENZELLER K.RFID Handbook:Fundamentals and Applications in Contactless Smart Cards，Radio Frequen-cy Identification and Near Field Communication［M］.New York:Wiley，2010.

［7］KLAIR D K，CHIN KW，RAADR.A survey and tutorial of RFID anti－ collision protocols［J］.IEEE Communications Surveys＆ Tutorials，2010，12(3):400－421.

［8］SHIH D H，SUN P L，YEN D C，et al.Taxonomy and survey of RFID anti－ collision protocols［J］.Computer Communications，2006，29(11):2150 －2166.

［9］JIA Xiao － lin，FENG Quan － yuan，FAN Tai－ hua，et al.Analysis of Anti－collision Protocols for RFID Tag Identification［C］.2nd International Conference on Consumer Electronics，Communications and Networks，2012(2):877－880.

［10］BONUCCELLIM A，LONETTIF，MARTELLIF.Instant collision resolution for tag identification in RFID networks［J］.Elsevier，Ad Hoc Networks，2007，5(8):1220 －1232.

［11］JIA Xiao－lin，FENG Quan－yuan，MA Cheng－zhen.An efficient anti－collision protocol for RFID tag identification［J］.IEEE Communications Letters，2010，14(11):1014－1016.

［12］JIA Xiao－lin，FENG Quan－yuan，YU Li－shan.Stability analysis of an efficient anti－collision protocol for RFID tag identification［J］.IEEE Transactions on Communications，2012，60(8):2285 －2294.

［13］JIA Xiao－lin，FENG Quan－yuan.An improved anticollision protocol for radio frequency identification tag［J］.International Journal of Communication Systems，2013.［on line］