摘 要:为提高智能超市的管理水平，本文提出一种新的RFID防碰撞算法-规则约束二进制搜索算法。该算法通过删除校验位、倒置编码顺序、逐次递进深度搜索等策略，实现对商品标签的快速识别。最后通过仿真证明了该算法具有识别效率高等优点。

　　关键词: 射频识别;防碰撞;标签冲突;二进制搜索;

　　Abstract: In order to enhance the level of intelligent management of the supermarket, a new RFID anti-collision algorithm - Binary search algorithm rules. The algorithm by removing the parity bit, inverted coding sequence, the depth of search, such as successive progressive strategy to achieve quick identification of product labels. The simulation proved that the algorithm is to identify and high efficiency.

　　Key words: radio frequency identification; anti-collision; label conflict; binary search;

　　1 引言

　　为解决目前超市排长队结账的现象，让商家精准掌握货物信息，研究了一种基于射频识别(RFID)技术的智能超市[1]。该超市用915MHz的射频读写器对贴在商品上的电子标签进行远距离识别,达到远距离群识别的效果。要在极短的时间内达到准确、完全的识别商品的目标，必须对防碰撞算法进行研究。

　　目前无源标签使用的搜索算法较多的有二进制搜索算法、动态二进制搜索算法、二叉树堆栈算法[2]，但这些算法在智能超市都有一定局限性。于二进制搜索算法采用逐次比较的方法，虽然识别率高，但识别效率低。动态二进制算法采用去掉部分冗余编码的方法提高识别效率，同样在智能超市不能完全适用。二叉树堆栈算法的主要思想是将标签编码存入堆栈，这样以牺牲SRAM为代价。纵上所述，必须研究一种新的算法来解决上述问题。

　　2 标签编码描述

　　欧洲商品条码(European Article Number，简称EAN) [3]，目前已成为一种国际性的条码系统。EAN码有两种版本—标准版和缩短版。标准版用13位数字表示，又称为EAN13码，缩短版用8位数字表示，又称EAN8。两种条码的最后一位为校验位，由前面的12位或7位数字计算得出的。

　　EAN13码的数字含义：

　　左侧的前3位为国家代码，中国国家代码为690～692;

　　下4位为制造厂商代码(只能从0000～9999这一万组数字中进行分配);

　　下5位为产品代码(每个制造商可以对自己生产的10万种商品进行分配);

　　最后一位为校验码。

　　综上所述，超市商品要用13位的十进制编码来表示，如果转换成二进制，那么就是

　　10+14+17+4=45 (1)

　　即需要用45位二进制来表示商品条码。二进制搜索算法在实现碰撞的过程中，标签总是以完整的序列号作为应答，标签序列号过长，这样采用传统二进制搜索算法，实现识别起来效率低下，起不到提高超市效率和效益的作用。故需要研究出一种新的算法来解决这个问题.

　　3 防碰撞算法的简介

　　所谓防碰撞算法，就是在读写器天线的识别区域内同时有多个射频标签存在时，可以通过一种机制，使读写器可以逐个的对多个标签进行识别。实现这个目标主要有两种方法，其一，读写器可以正确识别多个电子标签同时发回的数据，也即采用并行的方式，以达到识别多卡识别的目的;其二，使电子标签在规定的时间内依次发回数据，即一张电子标签占用一段特定的时间，在这段时间内只有一张电子标签作为应答。

　　为了防止数据碰撞的发生，首先要确定发生碰撞的数据比特位的具体位置。在这里使用的是Manchester编码。上升沿表示逻辑“0”，下降沿表示逻辑“1”，不存在状态不变的情况。因此假如在数据传输过程中检测到编码状态不发生跳变，就可以认为数据在传输过程中发生了碰撞。两个发生碰撞的数据比特位必定有一个为逻辑“0”，一个为逻辑“1”，这样Manchester码的上升沿和下降沿相互抵消，使读写器在持续的时间内接收到状态持续不变的副载波信号，即出现了状态不跳变的情况，这在Manchester编码是不允许的，可以肯定该处出现了碰撞。因此可以用这种方法来按位跟踪发生碰撞的数据比特位的具体位置。

　　某堆标签中的标签1和标签2同时响应读写器的请求，同时向读写器发送数据串10100110和10010100.在图1中可以看到，读写器收到两个标签传来的数据码并检测到数据比特位D5、D4和D1出现了冲突，因此无法确定所收到的数据串究竟来自哪个标签。接下来读写器所做的工作就是要通过一种适当的防碰撞算法来不断重复查询哪两个标签了发生冲突，并在重复查询的过程中检测出碰撞位，完成识别标签的任务。

　　图1 曼彻斯特编码位碰撞情况Fig.1 The situation of Manchester code bits collision

　　当标签进入射频区域时，读写器开始针对所有的标签进行检测识别操作。其工作过程主要有如下四个状态：

　　1)Power off状态：标签尚未获得能量，而处于断电状态，因此也不能发射负载波。

　　2)IDLE状态：标签进入读写器工作区，被电磁场激活后，获得能量，生成电压，进入IDLE状态，同时能对已被调制信号解调，并认识来自读写器的REQUEST和WAKE UP命令。

　　3)READY 状态：当接收到一个有效的REQA或WAKE UP命令时，就进入READY状态，在这一状态中采用防碰撞方法，用UID(惟一标识符)从多张IC卡中选择出一张应答器，此时该应答器就进入ACITVE状态。

　　4)ACITVE 状态：在本状态，完成本次应用(一次交易)所需要的全部操作。

　　5)HALT 状态：读写器完成一次交易后，被置于HALT状态。图2位应答器各个状态之间的转换图。图2 状态转换图

　　Fig.2 The state transition diagram

　　4 规则约束二进制搜索算法

　　4.1 问题解析

　　RFID系统的一个重要特性在于是否可以多个标签同时识别，远距离多标签识别是射频识别比条形码技术优越所在。然而，在超市内多标签识别，比在其它工作环境要求更高。首先，超市内标签编码更长(位数长达45位)，这样二进制树高度更高，搜索时间更长。其次，超市对搜索成功率要求更高，必须达到100%。对于目前常用的二进制搜索算法(上述BS算法、DBS算法、ID-BTS算法)，在智能超市使用都有一定的局限性。如果采用规则约束二进制搜索算法，可以解决标签识别慢的缺点。

　　4.2 规则约束

　　通过对EAN编码的分析，为便于实现和描述该算法，提出如下防碰撞规则[4]，对算法进行约束：

　　规则一：标签识别时，屏蔽掉所有编码最后一位。根据EAN编码规则，其最后一位为校验位，是在前12位数字的基础上计算出来的。所以，读写器收到编码后，进行编码识别时，完全可以屏蔽掉该位，这样可以减少二进制位数，规则约束二进制搜索时，树的深度变浅，搜索速度得到提高。当标签识别完成后，可以再将校验位还原，进行标签编码校验。

 1/2    1 2 下一页 尾页