一种改进的混合查询树防碰撞算法研究与仿真
开篇：润墨网以专业的文秘视角，为您筛选了一篇一种改进的混合查询树防碰撞算法研究与仿真范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：本算法在混合查询树算法的基础上，利用最高碰撞位和最低碰撞位的组合信息，对标签进行分组。根据标签最高、最低碰撞位的组合信息，将标签放入四个矩阵中分别进行响应，减少标签碰撞。性能分析结果表明，该算法优于QT、HQT 算法，减少了查询次数和系统通信量，标签识别效率明显提高。
关键词：混合查询树算法 最高碰撞位 最低碰撞位 防碰撞算法
中图分类号：TP391.44 文献标识码：A 文章编号：1007-9416（2015）09-0000-00
Abstract：Based on the Hybrid Query tree algorithm， this enhanced algorithm， utilizing the combined information of the highest and the lowest bit of collision， categorizes the tags. And the tags are put in four matrixes respectively to react to reduce collision. The analysis of function shows that this proposed algorithm is superior to QT and HQT by decreasing the number of query and the frequency of system communication. Hence， the efficiency of tag identification is greatly enhanced.
Keywords：Hybrid Query Tree Algorithm； Highest Bit Of Collision； Lowest Bit Of Collision； Anti-Collision Algorithm
RFID 技术是RFID系统架构中感知层的关键技术之一。RFID系统主要由阅读器、电子标签、RFID中间件和应用系统软件四个部分组成，阅读器和电子标签通过一条共用的通信通道进行无线通信完成数据传输。如果两个及以上处于同一阅读器可读范围内的标签同时与阅读器通信时，就会出现数据碰撞问题，造成阅读器无法识别标签。RFID标签防碰撞算法是RFID系统中的一个核心问题，标签碰撞问题的解决对 RFID 系统性能的提高至关重要。
目前标签防碰撞算法有两种：基于ALOHA 的非确定性算法和基于二进制树型结构的确定性算法[1]。非确定性算法包括：ALOHA 算法、时隙ALOHA 算法、帧时隙ALOHA 算法和帧时隙ALOHA 算法，算法随机性大，信道利用率低（理想状态为36.8%），而且会出现个别标签无法识别（即“饿死”现象）；确定性算法包括：二进制搜索算法、动态二进制搜索算法、后退式二进制算法和查询树算法，算法标签识别率高，但识别延迟率高。本文欲在混合查询树算法基础上，根据最高和最低碰撞位的具体信息，动态生成四个矩阵去分别响应，减少标签识别的查询次数和通信量。
1 算法相关理论基础
1.1 曼彻斯特编码
曼彻斯特编码[2]是RFID系统中的一种编码方式。该编码约定“0”表示上升沿，“1”表示下降沿。当多个标签同时向阅读器发送不同数据时，则对应曼彻斯特编码的上升沿和下降沿相互抵消，出现“没有变化”的状态，阅读器由此可以确定碰撞的准确位置。假设有两个标签：10010110和10100011同时响应阅读器的请求，阅读器获得的信息为10XX0X1X，X表示为碰撞。工作原理如图1所示。
图1 曼彻斯特编码
1.2 查询树算法
查询树算法简称为QT算法[3]，算法原理：阅读器从查询队列中选择一个查询前缀发送给标签，具有相同前缀的标签响应阅读器，如果有多于一个标签响应，则发生了碰撞，阅读器在查询前缀后加0和1，生成新的查询前缀，添加到查询队列中；如果只有一个标签响应，则正确识别该标签。通过不断地增加查询前缀的长度，直至所有标签都被正确识别。如有4个标签：0010、0110、1001和1010等待识别，其识别过程如图2所示。
1.3 混合查询树算法
混合查询树算法简称为HQT算法[4]，算法原理与QT算法类似，只是在发生碰撞时，阅读器在查询前缀后增加2位二进制数位：00、01、10和11，生成新的查询前缀，添加到查询队列中，通过不断地增加查询前缀的长度，直至所有标签都被正确识别。对于相同的4个标签：0010、0110、1001和1010，其识别过程如图3所示。
2.1 算法指令约定
为了充分利用已得到的碰撞位信息，减少查询次数和通信量，本算法对原有的算法指令进行了如下改进：
（1）查询指令REQUEST。REQUEST指令中的参数设有单参数、双参数两种形式，分别有REQUEST（bit），REQUEST（D1，D2）两个指令。REQUEST（bit）为最初查询指令，要求阅读器范围内的所有标签都得响应；REQUEST（D1，D2r）中的D1和D2是标签响应REQUEST（bit）发生碰撞所得到最高碰撞位和最低碰撞位，REQUEST（D1，D2）要求标签计算组合xy的十进制值并存入自己的累加器sums中。（2）选择指令SELECT。SELECT（ID）选择编号为ID标签，为读出或写入数据作准备。（3）读指令READ。READ（ID） 读出编号为ID标签中的数据。（4）屏蔽指令UNSELECT。UNSELECT（ID） 让编号为ID标签处于非激活状态，对收到的REQUEST指令不作应答。
2.2 算法描述
本算法根据最高碰撞位D1和最低碰撞位D2的组合xy值，将标签放到生成的四个矩阵中去分别响应阅读器。四个统计Request指令发送次数的累加器new0、new1、new2、new3，初始值都为1。算法流程如图4所示。
（1）假设阅读器识别范围内有N个等待识别的标签，阅读器首先发送Request（bit），N个标签都响应，根据曼彻斯特编码原理解码生成相应的比特流，从中取得最高碰撞位D1，最低碰撞位D2，构成一个新查询组合参数（D1，D2）。阅读器根据组合参数（D1，D2）生成查询命令Request（D1，D2），发送给标签。标签分别计算其第D1，D2碰撞位的组合XY对应的十进制值，存放在自身的累加器sums中，然后根据自己的sums值在对应的矩阵a0、a1、a2、a3中进行响应。（2）如果只有一个标签响应，则直接识别该标签，使用UNSELECT指令屏蔽该标签。否则，进入第（3）步。（3）某一个矩阵内多个标签响应时也会发生碰撞，从中得到最高碰撞位D1，最低碰撞位D2，构成新的查询组合参数（D1，D2），阅读器根据组合参数（D1，D2）生成新的查询命令Request（D1，D2），发送给标签。标签分别计算其第D1，D2碰撞位的组合XY对应的十进制值，存放在自身的累加器sums中，然后根据自己的sums值在对应的新矩阵a0、a1、a2、a3中进行响应。当新矩阵a0、a1、a2、a3中的任意一个存在多个标签响应时重复以上步骤。当D1=D2时，调用sel函数，利用二叉树搜索算法识别标签。（4）当矩阵a0、a1、a2、a3都为空时，表明N个标签全部识别，算法结束。否则，返回到第（3）步。
2.3 算法举例
下面通过一个实例来说明算法的实现过程，假设阅读器识别范围内有8个等待识别的标签，标签的ID 号为8位，如表1 所示。
算法的实现过程如下：
（1）阅读器初始化bit=11111111。
（2）阅读器发送Request（bit），阅读器识别范围内的所有标签都响应，根据曼彻斯特编码原理得到的解码信息为XXXXXXXX，如表2所示。最高碰撞位为D1=1， 最低碰撞位为D2=8。阅读器生成新的询问命令Request（1，8），发送给标签。同时，标签分别计算其最高和最低碰撞位（第1、8位）的组合xy对应的十进制值，存放在自身的累加器sums中，然后根据sums值在对应的情况中响应阅读器。Tag2的xy=01，对应sums= 1， 在矩阵a1中响应并识别。Tag6和Tag7的xy=00，对应sums= 0，在矩阵a0中响应。Tag3和Tag4的xy=11，对应sums= 3，在矩阵a3中响应。Tag1、Tag5和Tag8的xy=10，对应sums= 2，在矩阵a2中响应，发生碰撞。如表3所示。
（3）表3表明Tag6和Tag7在矩阵a0中响应，其xy组合值为00，在第2至7位置发生碰撞，碰撞位信息如表4所示。最高碰撞位为D1=2， 最低碰撞位为D2=7， 阅读器生成新的询问命令Request（2，7），发送给标签，并分别计算标签第2、7碰撞位组合xy对应的十进制值存放在自身的累加器sums中，然后根据sums值在对应的矩阵中进行响应并被识别。如表5所示。
（4）表3表明Tag1、 Tag5和Tag8在矩阵a2中响应，其xy组合值为10，在第2至7位置发生碰撞，碰撞位信息如表6所示。最高碰撞位为D1=2， 最低碰撞位为D2=7， 阅读器生成新的询问命令Request（2，7），发送给标签，并分别计算标签第2、7碰撞位组合xy对应的十进制值存放在自身的累加器sums中，然后根据sums值在对应的矩阵中进行响应并被识别。如表7所示。
（5）表7表明Tag1、 Tag5在矩阵a2中响应，其xy组合值为10，两者只在第4位发生碰撞，碰撞位信息如表8所示。由于只有一个碰撞位，所以直接采用二叉树搜索算法将两者识别。
（6）表3表明Tag3和Tag4在矩阵a3中响应，其xy组合值为11，在第2至7位置发生碰撞，碰撞位信息如表9所示。最高碰撞位为D1=2， 最低碰撞位为D2=7， 阅读器生成新的询问命令Request（2，7），发送给标签，并分别计算标签第2、7碰撞位组合xy对应的十进制值存放在自身的累加器sums中，然后根据sums值在对应的矩阵中进行响应并被识别。如表10所示。
（7）上述8个标签的识别过程对应的树型结构如图5所示。根据最高碰撞位和最低碰撞位构建成一棵四叉树，树高为4层，碰撞矩阵为5个，空闲矩阵为6个，与QT、HQT算法相比，减少了查询次数和系统通信量，算法效率明显提高。
3 算法仿真验证
本文使用Matlab 仿真工具对该算法进行仿真验证。仿真结果在相同实验条件下，在识别次数和传输数据量等方面，将IHQT算法与QT 算法、HQT 算法进行对比，如图6所示。仿真结果表明，IHQT算法与QT 算法、HQT 算法相比，在识别延时性能上有明显改善。
图6 三种算法标签识别延迟对比
4 结语
本文提出的算法在混合查询树算法基础上，根据标签最高、最低碰撞位的组合信息，将标签放入四个矩阵中分别进行响应，减少标签碰撞，标签识别的查询次数和通信量明显减少。仿真结果表明，该算法与QT、HQT两种算法相比，性能方面明显提高。
参考文献
[1] SCHOUTEFS.Dynamic frame length ALOHA [J].IEEE Transactions on Communications Letters，1983，31（4）：565-568.
[2] 伍继雄，江岸，黄生叶 等.RFID系统中二叉树防碰撞算法性能的提升[J].湖南大学学报：（自然科学版），2010，（12）：82-86.
[3] 程文青，赵梦欣，徐晶 等.改进的RFID动态帧时隙 ALOHA 算法[J].华中科技大学学报：（自然科学版），2007（6）：14-16.
[4] Ryu J，Lee Hojin，Seok Y，et al.A Hybrid Query Tree Protocol for Tag Collision Arbitration in RFID System[C]//Proceedings of the IEEE international conference on communications.Glasgow： IEEE，2007：5981-5986.
收稿日期：2015-09-02
基金项目：湖南省科技计划项目（NO：2013SK3178）、衡阳市科技计划项目（NO：2013KS70）、
湖南省大学生研究性学习和创新性实验计划项目（NO：201510546007）
作者简介：邓红卫（1970―），男，湖南祁阳人，副教授，硕士，研究方向：计算机通信网络和嵌入式系统。E-mail：