规则二：屏蔽掉校验码后的编码，必须直接倒置。即编码由EAN[0:40]变成EAN[40:0]。对于国内超市，其产品绝大部分来源国内，所以EAN0[0:9]识别时重复概率较高，放入底部，缩短二进制树的搜索路径。

　　规则三：标签进行深度搜索时，标签响应返回数据只包括发送碰撞位后面几位数据，碰撞位前面位忽略。这样做的目的是通过减少传输数据位数，提高有用数据的处理速度。同时，这样可以避免每次从标签第一位搜索，能够缩短搜索路径，提高搜索效率。

　　规则四：当有标签识别出时，先将其变成睡眠状态，然后从其前一碰撞位开始重新识别

　　4.3 算法原理

　　假设标签的编码为10位，读写器作用范围内有5个标签，如表1 所示。

　　表1 标签及编码

　　Tab.1 Label and Code 标签1 101 100 100 1 标签2 101 101 110 0 标签3 110 100 001 1 标签4 101 001 010 1 标签5 110 101 111 1

　　其具体执行过程如下：

　　第1步 读写器发送Request命令，读写器作用范围内的所有标签应答，根据Manchester编码原理，解码得到的为1***0*****，碰撞位为D[0]、D[1]、D[2]、D[3]、D[4]、D[6]、D[7]、D[8]。根据上述规则一，忽略掉D[0]位，这样冲突位由原来8位变成7位。

　　第2步 将标签编码进行倒置，数据顺序由原来的D[9]～D[1]变成D[1]～D[9]。

　　第3步 读写器发送命令字，要求应答器序列号中D[1]位为‘1’的标签作出响应，发送其自身剩余部分的有效信息位，这样就排除了标签1、2、4。

　　第4步 标签3、5作出响应，传送自己剩余的有效信息位。读写器检测到冲突位为D[6]并记录下来。

　　第5步 读写器发送命令字，要求标签编码中D[6]位为‘l’的标签做出响应，发送其自身剩余部分的有效位，这样就排除了标签3。读写器此时发现无标签发送冲突，这样标签3被识别出来，读出其编码和标签内部信息，然后将其转为睡眠状态。

　　第6步 读写器发送命令字，要求应答器序列号中D[6]位为‘0’的应答器做出响应，发送其自身剩余部分的有效位，这样就识别出标签5。

　　第7步 标签5变为睡眠状态之后，将D[1]为变为‘0’，继续进行识别。

　　经过上述几个步骤以后，读写器顺利的识别出所有标签。利用这种基于规则约束的二进制搜索算法来识别应答器，可以将传输数据量和传输时间都大大减少，极大的提高识别效率。

　　4.4 算法分析

　　假设读写器检测出的标签数为n，标签编码位数为h=45，将所有标签定义为个序列，即D={D1,D2,D3……Dn}。

　　在标签搜寻过程中，不采用规则，直接用二进制搜索算法进行搜索时，其搜索次数为:

(2)

　　当将标签编码中的校验位去掉后，二进制树的高度变成(h-3)，此时总搜索次数为：

(3)

　　当将所有编码顺序倒置之后，然后采用逐次递进深度搜索后，其搜索次数变为：

(4)

　　对于上述三个公式，令m=3，应用Matlab仿真，结果如图3所示。图中最上面一条曲线对应的是公式(2)，最下面的一条曲线对应的是公式(4)。图纵坐标代表搜索次数S(n)，横坐标代表的是标签个数n。从仿真结果，我们可以得出如下结论：对于相同个数的标签，采用规则约束二进制算法，可以明显降低搜索次数，提高标签识别效率。

　　图3 算法仿真结果Fig.3 The results of algorithm simulation

　　5 结论

　　本文针对超市使用的情况，介绍了防碰撞算法出现的原因、现象和解决办法。简单介绍了防碰撞算法，重点阐述了无源标签使用的二进制搜索算法。在分析和比较常用的二进制搜索算法基础上，结合商品标签编码特点，研究出一种规则约束二进制搜索算法，来解决超市标签碰撞问题。通过仿真证明了该算法具有识别效率高等优点。从而解决了约束RFID系统快速读取的瓶颈,提高商品实时数据的采集,使商品的采购、仓储、配送过程更加便捷,对商业应用中大批量物品的识别和管理具有重要意义。

　　参考文献 :

　　[1] 王亚奇 ,顾亦然 ,蒋国平. 改进型的二进制搜索 RFID系统反碰撞算法[J]. 计算机应用,2007, 27(11).

　　[2] JIAO Chuan-hai.Multi-branch query tree protocol for solving RFID tag collision problem[J].Journal of China Universities of Posts and Telecommunications, 15(4),2008:51-54.

　　[3] Jung-Sik Cho.RFID Tag Anti-Collision Protocol: Query Tree with Reversed Ids[M].International Conference on Advanced Communication Technology, ICACT, v1 , 2008: 225-230.

　　[4] Jihoon Myung.Adaptive Binary Splitting: A RFID Tag Collision Arbitration Protocol for Tag Identification[J].Mobile Networks and Applications, 11(5) , 2006: 711-722..

　　[5]喻武龙.无线射频识别系统的算法研究与实现[D].广州：暨南大学，2007.

　　[6]何娜.射频识别系统中防冲突算法研究及其硬件实现[D].广州：暨南大学，2007

 2/2   首页 上一页 1 2