基于模运算标签分类的RFID标签防碰撞识别方法

梁彪 郑勇鑫 王玉莹 秦中元

摘 要：为了解决射频识别（RFID）系统中的多标签防碰撞问题，在分析帧时隙ALOHA算法的基础上，提出一种基于模运算标签分类的RFID标签防碰撞识别方法。引入一种检测信息碰撞的时隙选择信息，对标签所选取时隙的碰撞情况进行分析并估计标签数量；然后对标签EPC编码进行逐级的取模运算，将同余的标签归为一组。各个标签经过K次取模运算后，分为2k组，每组只有发生少量碰撞位的标签。再将标签按照分组对应的时隙发送，碰撞标签采用二叉树后退式算法处理。本方法极大的提高了标签的识别效率，适用于射频识别系统中阅读器对于大量电子标签的快速识别。

关键词：射频识别；标签防碰撞；模运算分组

RFID tag anti-collision identification method

based on modular arithmetic tag classification

Zheng Yongxin Wang Yuying Qin Zhongyuan（Southeast University，Nanjing China 211189）

Abstract：In order to solve the problem of multiple tags collision in RFID system，on the basis of ALOHA algorithm， RFID tag anti-collision identification method based on modular arithmetic tag classification was proposed. Bring in a kind of slot selection information used to detect information collision， it analyze the collision caused by slot and estimate the number of tag； Then do the modular arithmetic on the Tag EPC step by step， the tags with the same remainder are classified as a group.After K times modular arithmetic， tags are divided into 2K groups，The tag in each group has little collision bit. Then tags are sent according to the corresponding slot， collision tags can be dealed with binary tree backword algorithm. This method greatly improve the efficiency of the tag identification， it is suitable for readers which has a large number of electronic tags to identify in RFID system.

Key words：RFID；Tag anti-collision；Modular arithmetic

1 概述

無线射频识别技术（Radio Frequency Identification，简称RFID）是一种非接触的自动识别技术，其基本原理是利用射频信号或空间耦合（电感或电磁耦合）的传输特性，实现对物体或商品的自动识别。RFID技术同其它的自动识别技术（条形码技术、光学识别和生物识别技术，包括虹膜、面部、声音和指纹）相比，具有抗干扰能力强、信息量大、非视觉范围读写和寿命长等特点，被广泛应用于物流、供应链、动物和车辆识别、门禁系统、图书管理、自动收费和生产制造等领域[1]。RFID系统主要的难题在于多标签碰撞时较低的标签数据识读率，多标签碰撞是指当多个标签同时存在于同一个射频信道内时，阅读器无法读取标签数据的现象。目前，解决RFID标签阅读冲突问题最广泛的是帧时隙ALOHA算法和二进制搜索算法。由于简单实用，帧时隙ALOHA算法应用更为频繁[2]，例如ISO/IEC18000-6 Type A协议和EPC Class1协议都是使用帧时隙ALOHA算法。

2 基本算法研究

2.1 帧时隙ALOHA算法

帧时隙 ALOHA（Framed Slotted ALOHA，FSA）算法是一种随机时分多址方式的用户信息通信收发算法。该算法将信道用信息帧表示，其中，帧是指由阅读器要求的包含若干时隙的时间间隔。信息帧可以分成多个时隙，其中，时隙是指标签发送自身标识的时间长度。当一个时隙只被一个标签占有时，阅读器才会正确识别该标签，而当一个时隙内有2个或2个以上标签时，会发生碰撞，读写器无法正确识别，若时隙为空则跳过[3]。

ALOHA算法吞吐率低，仅为18.4%。帧时隙ALOHA算法FSA（Framed Slotted ALOHA）是基于ALOHA算法的扩展，FSA算法在帧长约等于未识别的标签数目时吞吐率最大，约为36.8%[4]。基于ALOHA算法的一些改进算法如动态帧时隙ALOHA算法ALOHA（Dynamic Slotted ALOHA）[5]是根据标签数量来动态调整帧长的方法以保证最大吞吐效率的。因此在标签数量少时这类概率性防碰撞算法的识别效率不高，而且消耗时隙量大。

2.2 二进制搜索算法

二进制搜索算法又称为二叉树搜索算法，它要求能够在阅读器中确定数据碰撞位的准确位置。因此，必须要有合适的位编码法。曼彻斯特码用上升沿表示0，用下降沿表示1，在数据传输过程中不允许/没有变化0的状态。如果采用ASK调制方式，当2个（或多个）应答器同时发送的数据位为不同的值，则对应的曼彻斯特码的上升沿和下降沿互相抵消，接收到的副载波就是不间断的，造成一种错误的状态，从而可以确定碰撞位置。

基于二进制的防碰撞算法，国外的研究有很多，比如BBT（bit-by-bit tree）[6]算法。BBT算法的基本思想是：阅读器发送请求命令，请求标签回送序列号。响应的标签每次只发送1 位序列号。如果阅读器端没有发生冲突，则在内存中保存该接收位，然后请求下一位；如果阅读器处发生冲突，则将该冲突位分为2支，即分支0和分支1，从中选择一个分支，然后请求下一位。阅读器重复上述过程直至序列号的每一位都被识别。国内主要研究的有：基于后退式的二进制搜索算法[7]，当识别出一个标签后，算法根据上一次请求命令参数来获得下一个请求命令，以此来极大地缩短识别过程；动态二进制搜索算法和多状态二进制搜索算法[8]等，主要通过减少基本算法中阅读器命令和标签响应信息中存在的大量冗余数据来提高识别效率。虽然这类确定性防碰撞算法识别率高，适应大规模标签数量的场合，但是这类算法需要发送全部或部分标签EPC进行搜索，对于标签代码位数较多的情况，存在标签与阅读器之间的通信量过大的问题[9]。

3 基于模运算标签分类的RFID标签防碰撞识别方法

为了提高大量标签存在时的识别效率，提出了一种基于模运算标签分类的RFID标签防碰撞识别方法，采用逐级分组机制，每一组只有少量标签，一般可将每组标签数控制在少于4个。本方法构造出一种有利于标签识别的碰撞环境，使得每组的标签具有大量相同位和少量碰撞位的特征，结合曼彻斯特编码的特征和二进制搜索算法的特点可以高效的识别标签。阅读器识别标签的具体步骤如图1所示

3.1 标签数量估计

阅读器初始化，使所有标签进入激活状态。接着阅读器选择一个数估计帧长，一般选择较大的数，例如256。阅读器向可读取范围内的所有标签发送标签预估命令-Estimate命令，标签根据最大帧长的ALOHA算法发送各自EPC编码，阅读器统计碰撞时隙，空闲时隙和成功识别时隙个数，利用概率知识估算标签数量。

3.2 标签分组

3.2.1 阅读器发送分组次数

阅读器计算标签分组次数k，k的计算方法：

其中N为第一步估计出的标签数量。阅读器将k作为参数附加请求与命令Query一起发送给所有标签，作为这一帧的开始。假设经过第一轮的标签估计，标签数量为N=100，计算标签分组次数k=6。阅读器设置这一帧的时隙个数为2k=64，即帧长L为64。

3.2.2 标签分组计算

根据上文计算出的分组次数k，对标签的EPC编码进行k次摸2运算，根据运算结果对标签进行分组。下面详细说明：标签收到RFID阅读器发送的k值后，将计数器的值设为k。开始进行k次取模运算。由于标签ID模2运算相当于右移一位操作，下文将以标签ID位数来更直观的说明，如图2所示。第1次分组，将余数为0的分为一组，在前32个时隙发送，余数为1的分为另一组，在后32个时隙发送，相当于将EPC编码最低位为0和最低位为1的标签分开。执行该次运算后，标签将0或1存储在临时寄存器的最高位，计数器值减一。第2次分组，标签EPC编码模22运算，将次低位分别为0和1的ID分开，即分为“00”，“10”，“01”，“11”四组，标签将0或1存储在临时寄存器的次高位，依此类推，通过6次分组后，100个标签被分为64组，分别在64个时隙里发送。通过比较标签ID和时隙的对应关系可以发现，EPC编码的后k位数和发送的时隙之间存在逆序关系，例如ID后6位为101100的标签将在第001101（即十进制数13）个时隙发送。将经过逆序处理之后的标签分组序列存储在临时寄存器中，以供标签匹配。

3.2.3 标签按时隙发送

标签分组完成后，检测当前时隙号和标签临时寄存器中存储的分组号是否匹配，若匹配则标签发送信息，若不匹配则标签设为silence状态。

4 仿真分析

在RFID系统中，吞吐率和系统识别率是衡量RFID系统好坏的主要指标。而吞吐率和系统识别率这两个參数是紧密联系的，故在此仅讨论系统识别率。系统识别率公式：

其中α为系统识别率，NT为标签数量，S为总时隙数。下面结合具体实例进行分析。假设第1到20时隙的分组结果为：

表中第一列为时隙号，其余列的每行为在该时隙发送的标签的EPC编码。由于时隙号对应EPC编码，因此标签只需发送部分EPC编码即可。例如第2个时隙中的标签，其后6位的编码为100000（逆序），所以EPC编码为928的标签只需发送前4位1110即可（EPC编码10位情况下）。

再根据曼切斯特编码的特性结合二进制搜索算法，以第2个时隙为例，阅读器收到标签信息后，得到信号为X1XX，阅读器再次发送QueryAdjust命令附加参数0111，当前时隙的三个标签收到该命令后，检测发送编码是否小于0111，小于则计数器置0并回复EPC编码，大于则计数器置1并转为wait状态。阅读器成功识别编码为0110（416）的标签后，再次发送QueryAdjust命令附加参数1111，剩余两个标签计数器置0并回复，接下来的过程和二进制搜索算法相同。在第2个时隙中，需要阅读器与标签5回合的交互来完成识别。当时隙中标签数量为2个时，则只需要3回合的交互。

阅读器通过这一帧64个时隙后，识别全部标签，整个读取过程结束。

下面通过计算机对ALOHA算法、二叉树后退式索引算法和本文所提出的算法进行Matlab仿真实验，实验条件相同，标签为100-1000个。在仿真中，横坐标为标签数目，纵坐标为系统识别率，可得仿真结果如图2所示。

如图2所示，经过Matlab仿真计算，在相同标签数目条件下，本文提出的方案系统识别率较高。

5 结论

本方法可以对大量标签进行快速分组，同时对标签进行排序，不断减少同组标签的碰撞位，以利用曼彻斯特编码的性质一次识别两个标签。通过标签分组序列号和时隙号的对应关系，减少标签发送编码的长度。由于分组中的标签数量非常少，而且标签具有大量相同的位，因此本方法很好的发挥了曼彻斯特编码的特性和二进制后退式搜索算法的特点，提高了多标签识别效率。

[参考文献]

[1]丁治国.RFID关键技术研究与实现[D].安徽：中国科学技术大学， 2009，05.

[2]Finkenzeller K.RFID Handbook，Fundamentals and Applicationsin Contactless Smart Cards and Identification[M]. 2nd ed.Chichester，UK：John Wiley and Sons Ltd.，2003.

[3]Finkenzeller K.射频识别技术[M].3版.吴晓峰，陈大才，译.北京：电子工业出版社，2006.

[4]李萌，钱志鸿，张旭，等.基于时隙预测的RFID防碰撞ALOHA算法[J].通信学报，2011，32（12）：43-50.

[5]姜立芬，卢桂章.射频识别系统中防碰撞算法研究[J].计算机工程与应用，2007，43（5）：29-32.

[6]MATEUL，MOLLF.Review of energy harvesting techniques and application for microelectronics[C].Proc of SPIE，2009：359-373.

[7]RAGUNATHANV，KANSALA，HSUJ.Design consideration for solar energy harvesting wireless embedded system[C].Proc of the 4th International Symposium on Information Proceeding in Sensor Networks，Piscataway，IEEE Press，2009：457-462.

[8]GAO Yi，SUN Guiling，LI Weixiang，et al.Wireless sensor node design based on solar energy supply[C].Proc of the 2nd International Conference on Power Electronics and Intelligent Transportation System，2009：203-207.

[9]刘猛，徐展.RFID中多标签识别缺陷与防碰撞算法分析[J].单片机与嵌入式系统应用，2010（1）：18-20.

[10]郎為民，陶少国.电子产品代码（EPC）标准化进展[J].信息通信，2006，3（3）：9-14.