RFID系统中预先侦测查询树防碰撞算法的改进

朱林海，李 鸿，陈凌宇

（长沙理工大学 电气与信息工程学院，湖南 长沙410114）

0 引 言

由于射频识别 （RFID）系统存在多个标签处于阅读器范围内且共用同一个信道，标签在响应阅读器时会产生碰撞，导致识别失败、降低传输效率的问题，如何有效地处理该问题是提高射频识别系统性能的关键。

基于时分多路存储技术的防碰撞算法有2类：随机算法和确定性算法。随机算法包括纯ALOHA 算法、时隙ALOHA 算法等，这类算法标签的响应是随机的，有可能长时间都未能得到识别，会产生 “Tag starvation”问题，导致系统效率也很低，只能适用于少量的标签的场合。确定性算法典型的是树型算法，包括后退式二进制树算法、四元侦测查询树算法等，该类型算法只要时间足够，能成功识别每一个标签。其中，后退式二进制树算法每次只能生成2个子集，一旦标签数量过大，就会产生大量的碰撞时隙，使得系统的性能大大降低；四元预先侦测查询树算法虽然每次分裂生成4个子集且完全清除了空闲时隙，但是没有很有效地解决大量标签情况下的碰撞问题，标签响应阅读器时，标签返回的信息含有没有发生碰撞的位，即传输了没必要传输的数据位，使得通信量没得到明显的改善，阅读器的询问次数也没明显的减少，系统的吞吐率依旧不高。为了解决这些问题，本文提出了改进的预先侦测查询树防碰撞算法。

1 多标签防碰撞算法

1.1 BBS算法

文献 ［1］提出了后退式二进制树算法 （BBS），该算法在阅读器成功识别一个标签后后退到上一层碰撞父节点开始搜索，阅读器发送请求命令即序列号，当标签的ID 号小于序列号或者等于序列号的标签都对该请求命令进行响应，并且标签返回自身整个ID 号，如果发生了碰撞，则把最高碰撞位置 “0”，碰撞位后置 “1”，得到下一次请求命令序列，继续上一步骤；如果没发生碰撞，则表明阅读器成功识别了该标签，阅读器再发送命令使其处于睡眠状态，并后退到上一碰撞节点得到下一次请求命令序列，继续以上操作。

1.2 PDQT算法

文献 ［2］中的PDQT 算法在四元查询树的基础上引入了时隙预先侦测信号技术，结合了时隙预先侦测信号的机制，能够根据侦测的情况确定标签是否有应答。射频识别系统的阅读器发现标签在应答的过程中产生了碰撞，会把查询字符串扩展2位即00、01、10和11，假设形成新的查询字串为01 00、01 01、01 10、01 11，利用时隙预先侦测信号技术，侦测并判断标签的应答情况，删除不需要的扩展后的新查询字串［2］，如果01 10空闲，就把01 10删除，需要的扩展后的新查询字串01 00、01 01和01 11置入等待查询序列中，然后阅读器发送带有该查询字串的查询命令，继续以上步骤，直到每个标签被识别，其中01为上一次查询的字串。

2 改进的预先侦测查询树防碰撞算法

2.1 算法的优化

改进的预先侦测查询树防碰撞算法采用曼切斯特（Manchester）编码，能准确的判断标签的碰撞位。该算法做出了以下改进：

（1）对需要识别的标签进行一次预处理，把各标签ID的碰撞位提取出来，作为新的ID 与阅读器通信，并且结合动态二进制算法，标签返回的信息是除去阅读器发送查询字串即前缀的剩余ID 位，这样大大的减少了系统的传输位数。

（2）采用八叉树询问代替原算法的四叉树询问，减少了标签的碰撞数目，提高了算法的效率。

（3）利用后退式搜索与堆栈存储的方法以避免重复搜索和冗余搜索，阅读器成功识别标签后直接后退到上一层父节点搜索，而不是根节点，减少了询问次数。

2.2 算法的原理

本文提出的算法通过提取碰撞位信息来构建新的ID号，然后与阅读器通信，在引入PDQT 算法的时隙预先侦测信号机制的基础上，从原算法的4 个侦测时隙增加到8个侦测时隙，分别为dts1、dts2、dts3、dts4、dts5、dts6、dts7、dts8。在预先侦测机制中，阅读器发送查询的请求命令后，侦测前面8个侦测时隙，根据侦测时隙中是否含有前侦测信号来判断标签是否出现碰撞情况以及空闲状况。如图1和图2 所示，假设标签已经经过提取碰撞位处理，就最后一层的标签而言，dts2、dts3、dts4、dts5检测到前侦测信号，分别表示有符合查询前缀011 001、011 010、011 011、011 100 的标签存在；dts1、dts6、dts7、dts8 没有检测到前侦测信号，分别表示没有符合查询前缀011 000、011 101、011 110、011 111的标签的存在，其中011为上一次的查询前缀。这样阅读器可以知晓在下一次的查询命令，并且只发送查询前缀给存在的标签，因此阅读器会选择新的查询前缀011 001、011 010、011 011、011 100。阅读器不会发送查询前缀给不存在的标签，这样就删除了空闲时期，减少了阅读器的查询次数。

图1 改进的四元查询树算法实例

图2 时隙前侦测信号技术实例

算法还利用了后退式索引与堆栈技术，把扩展后的查询前缀置入栈中，阅读器取栈顶前缀发送。

2.3 算法约定

本算法需要以下6 种基本基本指令：Request（null）、Request（prefix）、Select（prefix）、Rw－data、Unselect 和Ext－Collision－Bit.

（1）Request（null）—请求命令，作用范围的每一个标签都响应阅读器，标签返回整个ID 号。

（2）Request（prefix）—请求命令，其中prefix为查询前缀，即扩展后的新的查询字串，满足查询前缀的标签响应。

（3）Select（prefix）—选择指令，标签的前缀跟阅读器发送的前缀一致，响应选择这个命令请求。

（4）Rw－date—读取数据指令，阅读器成功识别标签后，读取标签的ID 值。

（5）Unselect—退出选择命令，被识别的标签处于退选状态，使得标签处于休眠状态，不在响应任何指令，要重新激活必须使得标签重新进入阅读器范围。

（6）Extract－Collision－Bit—提取各标签的碰撞位信息发至各标签，标签返回有碰撞标记的位作为新的ID 与阅读器通信。

2.4 算法步骤

步骤1 阅读器发送Request（null），作用范围类每一个标签都响应该请求命令，并返回ID 中每一位，阅读器检测冲突位，把冲突位标记为 “1”，无冲突位标记 “0”，并初始化查询栈Q。

步骤2 阅读器发送Extract－Collision－Bit指令，冲突信息发送给标签，标签返回有冲突标记的位作为新的ID与阅读器通信。

步骤3 标签的应答产生碰撞，在上一次查询前缀的基础上扩展3位，形成新的查询前缀，然后利用时隙预先侦测信号技术，删除不需要的前缀，其他需要的前缀置入栈Q。

步骤4 阅读器取栈顶Q 中的前缀并发送，如果在应答的时候没有标签产生碰撞，阅读器发送指令使其休眠，则识别成功；如果标签在应答时产生了碰撞，返回步骤3。

步骤5 判断栈Q 是否为空，如果不为空，返回步骤4；如果为空，则算法结束。

2.5 算法举例

下面通过一个实例来详细说明算法的实现过程，假设有5 个10 位的标签待识别，分别为tag1：1000011011；tag2：1100101011；tag3：1100111010；tag4：1100111110；tag5：1101111010。算法的执行过程如下：

（1）阅读器发送Request（null），，阅读器作用范围的标签响应，ID 的每一位都都返回来，阅读器检测碰撞位信息，把有冲突位标记为 “1”，无冲突位标记为 “0”。

（2）阅读器发送Extract－Collision－Bit指令，tag1、tag2、tag3、tag4、tag5 形 成 新 的ID，分 别 为000101、101001、101100、101110、111100，并与阅读器通信。

（3）查询前缀扩展3位，利用预先侦测技术，删除不需要的前缀001、010、011、100、110，需要的前缀000、101、111压入栈Q 中。阅读器读取栈Q 中查询前缀000，生成请求命令Request（000）。

（4）阅读器发送Request（000），此时仅有tag1应答，tag1被正确识别，阅读器发送Unselect指令，让其处于休眠状态。阅读器读取栈Q 中101，生成新的请求命令Request（101）。

（5）阅 读 器 发 送Request （101），此 时tag2、tag3、tag4应答，产生了碰撞，在上一次查询前缀的基础上，扩展3 位，得到新的查询前缀101000、101001、101010、101011、101100、101101、101110、101111，利用预先侦测技术，删除101000、101010、101011、101101、101111这些不需要的查询前缀，需要的查询前缀101001、101100、101110压入栈Q 中。阅读器取栈Q 中的101001，生成新的请求命令Request（101001）。

（6）阅读器发送Request（101001），此时仅有tag2成功识别，阅读器发送指令使其休眠。阅读器读取栈Q 中查询前缀101100，生成命令Request（101100）。

（7）阅读器发送Request（101100），此时仅有tag3成功识别，阅读器读取其数据，并发送指令使其休眠。阅读器读取栈Q 中101110，生成命令Request（101110）。

（8）阅读器发送Request（101110），此时只有tag4响应，成功识别，阅读器读取数据，发送指令使其休眠。阅读器读取栈Q 中查询前缀111，生成命令Request（111）。

（9）阅读器发送Request（111），此时只有tag5响应，成功识别，阅读器读取其数据，发送指令使其休眠。栈Q为空，识别结束。

3 实验分析与仿真

通过时隙数和吞吐率的计算，对本文的算法的性能进行分析。但是一般情况下很难得到一个精确的公式来计算。

本文算法利用了预先侦测查询树的方法，删除了空闲时隙，因此算法的总时隙为

系统的吞吐率为

本文的算法是基于PDQT 算法的基础提出来的，并且BBS算法又是比较经典的二进制树型算法，因此把本文提出的算法和这2种算法进行了相互之间的比较。利用Matlab仿真软件对以上3种算法进行理想情况下的仿真实验。仿真过程中系统的标签假设分布是均匀的，并且系统采用32位EPC编码的电子标签。在相同的仿真环境下，仿真结果取20次的实验平均值，分别比较了PDQT、BBS、本文的算法的查询次数、吞吐率和通信量，如图3、图4、图5所示。仿真结果可以看到，本文改进的算法，有效的减少了询问次数、总的传输位数，系统的效率也就是吞吐率也有了很大的改善，实验结果表明，本文改进的算法提升了整个RFID 系统的性能。

图3 查询次数的比较

图4 吞吐率的比较

图5 总传输位数的比较

4 结束语

本文提出了一种改进的预先侦测查询树防碰撞算法，创造性地结合了多种方法，包括八元查询树、提取碰撞位、预先侦测查询树、后退式索引、堆栈。这些方法的综合，无论是阅读器的询问次数、通信量，还是系统的吞吐率都达到了理想的效果，比改进前的算法，具有优越性。当电子标签的长度和数量逐渐增加时，本文提出的算法的性能的优势就更明显。因此，该算法具有一定的实用性和创新性。

［1］YU Songsen，ZHAN Yiju，PENG Weidong，et al.An anticollision based on binary tree searching of regressive index and its practice［J］.Computer Engineering and Application，2004，40 （16）：26－28 （in Chinese）. ［余 松 森，詹 宜 巨，彭 卫 东，等.基于后退索引的二进制树形搜索防碰撞算法及其实现［J］.计算机工程与应用，2004，40 （16）：26－28.］

［2］WANG Quan，HUA Nan.A new anticollision algorithm based on the quaternary query tree a algorithm ［J］.Journal of Air Force Engineering University （Natural Science Edition），2012，13 （6）：75－79 （in Chinese）.［王荃，滑楠.基于四元查询树算法的改进防碰撞算法 ［J］.空军工程大学学报 （自然科版），2012，13 （6）：75－79.］

［3］ZHOU Qing，CAI Ming.Improved hybrid query tree anticollision algorithm in RFID system ［J］.Computer Engineering and Design，2012，33 （1）：209－212 （in Chinese）.［周清，蔡明.改进的RFID 混合查询树防碰撞算法 ［J］.计算机工程与设计，2012，33 （1）：209－212.］

［4］XIANG Chuiyi，HE Yigang，LI Bing，et al.Improvement of dynamic binary system tree search algorithm ［J］.Computer Engineering，2010，36 （2）：260－264 （in Chinese）.［向垂益，何怡刚，李兵，等.动态二进制树搜搜算法的改进 ［J］.计算机工程，2010，36 （2）：260－264.］

［5］SUN Wensheng，LIU Ting.Improved anticollision algorithm based on binary－tree search ［J］.Computer Engineering，2011，37 （10）：257－259 （in Chinese）.［孙文胜，刘婷.一种改进的基于二叉树搜索树的防碰撞算法 ［J］.计算机工程，2011，37 （10）：257－259.］

［6］Jiho Ryu，Hojin Lee，Yongho Seok.et al.A hybrid query tree protocol for tag collision algorithm in RFID system ［C］／／IEEE International Conference on Communication，2007：5981－5986.

［7］Sung Hyun Kin，Poo Gyeon.Park an efficient tree based tag anticollision protocol for RFID system ［J］.IEEE Communication Letters，2007，11 （5）：449－451

［8］DING Zhiguo，ZHU Xueyong，GUO Li.An adaptive anti－collision algorithm based on multi－tree search ［J］.Acta Automatic Sinica，2010，36 （2）：237－241 （in Chinese）. ［丁治国，朱学永，郭立.自适应多叉树防碰撞算法研究 ［J］.自动化学报，2010，36 （2）：237－241.］

［9］CHOI JH，LEE D，LEE H.Query tree based reservation for efficient RFID tag anticollision ［J］.IEEE Communications Letters，2007，11 （1）：85－87.

［10］Klair DK，Read R.An investigation into the energy efficiency of pure and slotted aloha based RFID anticollision protocols［C］／／Proc of IEEE International Symposium on World of Wireless Mobile and Multimedia Networks，2007：1－4.