论文部分内容阅读
【摘要】在动态二进制防碰撞算法的基础上，提出了一个新的算法，该算法通过减少查询前缀和分裂二叉树的方法，采用深度优先的方式搜索标签，减少了查询次数和传输位数，提高了阅读器对标签的识别效率。
【关键词】RFID；防碰撞算法；电子标签
【中图分类号】TP391.44 【文献标识码】A 【文章编号】1672-5158（2012）11-0053-02
1、引言
RFID（Radio Frequency Identification）是物联网的基础，是20世纪80年代发展起来的一种非接触式的自动识别技术，主要用在物流管理、工商业自动化、交通运输以及防伪等领域。RFID系统中，阅读器和标签之间通过非接触地传递信息，获取被识别物体的信息，并进行处理。RFID系统的标签—般被放置于所需识别的物体上，其内部可以存储代表物体唯一性的信息，通常由耦合元件和电子芯片构成，阅读器则可以从标签中读出信息。本文中RFID系统发生了碰撞是指作用区域内一个阅读器和多个标签进行数据交换时，大量的标签在同一时刻应答同一个阅读器时，后果可能导致数据不能正确的传输，标签不能准确应答，这也可能造成标签信息的泄露。一个良好的标签防碰撞算法需要有效地解决RFID系统的防碰撞能力，能够高效地与标签进行通信。
RFID的目标和发展趋势是多目标快速识别。目前RFID技术存在许多不同的标准，主要涉及操作协议，编码规范，以及系统接口等问题。目前比较主流的相关规范有欧美的EPC（Electronic Product Code）]规范和日本的UID规范以及国际标准化组织ISO基于物品管理的射频识别标准IS018000系列规范等。目前，市场上广泛应用的欧美的EPC～IIS018000标准已成为主流的RFID标准。前RFID技术亟待解决的技术难题是在控制RFID系统成本的基础上，设计新的防冲突算法满足标签的快速高效识别，并且可以显著提高系统的防碰撞能力。现有的RFID系统防碰撞算法主要分为两大类，一类是基于概率防碰撞算法，也称为基于ALOHA机制算法，另一类是基于二进制的防碰撞算法。基于概率的防碰撞算法于是基于经典ALOHA算法，主要应用在少量标签识别的系统中，系统识别的可靠性相对差一些，优点是易于设计。本文主要研究基于二进制的防碰撞算法。
2、基于二进制的防碰撞算法
基于二进制RFlD防碰撞算法主要采用曼特斯特编码，如果多个标签同时发送的数据，在相同的位如果有两个值不同时，那么则接收的上升边和下降边互相抵消，使在整个比特长度内是不间断的副载波信号，这样采用曼特斯特编码可以识别碰撞位。
在_RFID系统中，每个标签的序列号都不一样，阅读器和标签对序列号进行比较式是按照对应位来比较，从低位向高位比较，并且约定0小于1，判断标签序列号的大小是先比较低位，比完低位再比高位，两数的大小由低位开始的第一个不相等位的大小决定，当两个序列号的所有数的全部位都相等时，才认为这两个序列号相等。
基于二进制的防碰撞算法中，主要使用了下面的指定指令：
（1）REQUEST指令：该指令由阅读器发送，并带有某个参数，该参数为某个序列号，阅读器发送一段序列号TD1，标签得到此序列号TD1，然后与自己的序列号ID进行比较，只有当自己的序列号小于或者等于阅读器发生的序列号时，标签才响应。其初始值通常设置为REQUEST（11111111）；
（2）sELECT指令，这是选择指令，阅读器接收电子标签传送的序列号，如果电子标签的序列号与自己发送的一致，则选中该标签，并与之通信；
（3）READATA指令，这是读取指令，阅读器读取选中的标签中的数据；
（4）UNSELECT指令，这是休眠指令，如果某个标签数据已经被读取，则发送该指令让标签不再响应阅读器的询问。
二进制防碰撞算法在工作的时候，首先由阅读器发出请求命名，等待电子标签的应答，如果没有接收到应答表示所在区域内没有电子标签，如果只有一个电子标签响应，那么该标签不会发生碰撞，阅读器则可以直接选择此标签，并与之通信。如果存在两个以上的电子标签响应，阅读器将检测是否发生碰撞，如果发生碰撞，则将序列号中碰撞的最高位置为0，其余的所有小于碰撞最高位值设置为1，并重新发送请求给电子标签，电子标签根据接收到的新的查询序列号，来判断是否需要应答，同样，需要应答的电子标签将自己的序列号传送给阅读器，阅读器同样检测是否发生碰撞，这个过程重复进行，直到没有碰撞发生，阅读器则与这些电子标签进行通讯。当电子标签与阅读器的通讯结束之后，阅读器发送命令使此标签不再对阅读器的查询命令，这个过程重复进行，直到所有标签发送完毕。从搜索过程可以看出，二进制防碰撞算法在搜索过程中重复搜索次数较多，传输位数较大。阅读器发送的参数和标签返回的序列号每次都要完整传输。实际应用中的序列号大多不只由一个字节所构成，按不同的规模甚至可以达到十个字节，这就造成了大量的信息冗余。动态二进制防碰撞算法在其基础上进行了改进，其基本思想是减少传送数据位数。假设x为碰撞最高位，传送位数为N，那么在（x-1）到0位总算被置为1的，不包括标签提供给阅读器的补充信息。标签应答的11）的第N-1到x位不包含给阅读器的补充信息，因此无需传输。上述想法引导出一种新算法：阅读器解码检测到冲突，将冲突起始位置0，数据高位不变，然后将原先碰撞前数据高位再加上碰撞起始位（置为O）作为新查询命令参数发送给标签，标签序列号则从数据高位开始比较，若对应的位等于该参数，则返回剩余数据位给阅读器，若剩余数据位上碰撞发生，则将碰撞最高位置为0加到原来Request@令参数末位最为新参数，继续上述过程，直至只有一个标签响应，阅读器检测到无碰撞发生，则将上一次发出的Request命令参数与标签返回的剩余位组合起来，该标签就被识别出来。因此设定新的请求格式Request（Ⅱ），w），其中s为7～x，在阅读器作用范围内的标签序列号的第7位到第x位与s卡日符的做出响应并返回剩余的w位给阅读器。动态二进制树算法的步骤如下： （1）阅读器发出一个序列号Request（null，8），全部标签均应答并返回完整序列号到阅读器。
（2）标签响应，如果标签超过2个，则发生碰撞。阅读器检测到碰撞位，设置碰撞位最高位为0加上发送冲突前的高位，更新标签要发送的序列号位数，将修改后的参数作为新的查询前缀。
（3）阅读发送更新后的请求查询指令给标签，标签序列号与参数值比较，匹配的标签将互补的序列号返回给阅读器。
（4）循环这个过程，直至阅读器识别到最小序列号的标签，选定该标签进行信息的读写，最后发送命令使该标签进入休眠状态，不再响应阅读器的请求命令。
（5）重复上述过程，直到阅读器依次识别出所有标签。
从算法搜索过程可以看出，动态二进制树算法中，阅读器命令与标签指令所携带的参数长度都在动态改变，因此该算法减少了传输信息量，一定程度上也节约了时间。但节点数目和循环次数没有发送改变。
3、一种新的防碰撞算法
新的RFID防碰撞的基本思路是减少所需传送的位数和查询次数。改进算法可以采用发送比特前缀，并且只有在阅读器解码得到碰撞位时才更新查询前缀的方式来优化，并采用宽度优先的方式构造一个二叉搜索树，在碰撞位按照左0右1分裂一个二叉树。基本原理如下：
阅读器在其作用区域内广播一个查询前缀0，若无标签应答则发送比特1，只有与查询前缀相符的ID才进行应答，标签并返回剩余ID给阅读器，阅读器检测是否发生碰撞，如果存在，则在最高碰撞位分裂为一个二叉树，再按照深度优先的方式搜索。算法如下：
（1）阅读器向作用区域内标签发送m比特查询前缀；
（2）当标签序列号的前m位与阅读器发送的m位查询前缀匹配时，则标签返回互补的第m位以后的序列号；否则不对阅读器进行响应；
（3）阅读器解码标签返回的第m位以后的序列号，若检测出第n位发生碰撞，则按照左0右1的方式分裂成一个二叉树，并向标签发出一个STOP指令使标签停止向阅读器继续应答序列号；
（4）阅读器根据以下三种状态对标签进行处理：（1）当第m位产生碰撞时，阅读器更新查询前缀，按照原阅读器发送前缀加上标签应答的比特（到）+“0/1”的二叉树深度优先的方式来更新.（2）若只剩下标签的最后一位发生碰撞，阅读器便裁定只余两个标签，这是由于任何一个标签11）都是独一无二的；（3）当碰撞没有发生，则发送sELECT命令选中该标签，读取该标签信息，最后令其“睡眠”。
（5）返回上次碰撞的节点，重复上述过程，直到所有标签被识别。
假设有4个标签，T1：10110010，T2：10100011，T3：10110011，T4：11100011
第一次，阅读器发送请求指令，向作用域内的标签广播查询前缀‘0’，没有标签匹配因此无响应。
第2次，阅读器发送查询前缀‘1’，四个标签都响应，并向阅读器返回剩余的11）序列号，在第6位就发生了碰撞，阅读器向标签发送sTOP指令，在第6应分裂出一个二叉树，再按照深度优先的方式更改查询前缀，即首先更新为10。
第3次，广播查询前缀10，标签1，2，3都应答，并检查出碰撞位在第4位。在该处分裂出一个二叉树。分别构成两个查询前缀1010和1011.
第4次，按照深度优先的方式，广播查询前缀11，可以识别出标签4。选中该标签进行信息传输，最后使其“休眠”。
第5次，广播查询前缀1010，标签中与1010前缀匹配的只有标签2，该标签被识别，选中该标签进行信息传输，最后使其“休眠”。
第6次，广播查询前缀1011，只有标签3响应，选中该标签进行信息传输，最后使其“休眠”。
我们根据上面的4个标签来分析改进后算法的性能，采用动态二进制数防碰撞算法时，阅读器发送的总比特数则为18比特，标签发送了54比特，共轮询9次，改进后的算法阅读器只需发送14比特，而标签只需传送17比特，共轮询6次，因此改进后算法的通信量明显减少。
4、结论
在分析动态二进制防碰撞算法的基础上提出了一个新的算法，该算法的阅读器通过广播查询前缀，并对响应的标签检测碰撞位，在碰撞位分裂出一个二叉树，按照深度优先的方式搜索，分析表明，改算法在通信量和查询次数方面明显优于动态二进制算法。
【关键词】RFID；防碰撞算法；电子标签
【中图分类号】TP391.44 【文献标识码】A 【文章编号】1672-5158（2012）11-0053-02
1、引言
RFID（Radio Frequency Identification）是物联网的基础，是20世纪80年代发展起来的一种非接触式的自动识别技术，主要用在物流管理、工商业自动化、交通运输以及防伪等领域。RFID系统中，阅读器和标签之间通过非接触地传递信息，获取被识别物体的信息，并进行处理。RFID系统的标签—般被放置于所需识别的物体上，其内部可以存储代表物体唯一性的信息，通常由耦合元件和电子芯片构成，阅读器则可以从标签中读出信息。本文中RFID系统发生了碰撞是指作用区域内一个阅读器和多个标签进行数据交换时，大量的标签在同一时刻应答同一个阅读器时，后果可能导致数据不能正确的传输，标签不能准确应答，这也可能造成标签信息的泄露。一个良好的标签防碰撞算法需要有效地解决RFID系统的防碰撞能力，能够高效地与标签进行通信。
RFID的目标和发展趋势是多目标快速识别。目前RFID技术存在许多不同的标准，主要涉及操作协议，编码规范，以及系统接口等问题。目前比较主流的相关规范有欧美的EPC（Electronic Product Code）]规范和日本的UID规范以及国际标准化组织ISO基于物品管理的射频识别标准IS018000系列规范等。目前，市场上广泛应用的欧美的EPC～IIS018000标准已成为主流的RFID标准。前RFID技术亟待解决的技术难题是在控制RFID系统成本的基础上，设计新的防冲突算法满足标签的快速高效识别，并且可以显著提高系统的防碰撞能力。现有的RFID系统防碰撞算法主要分为两大类，一类是基于概率防碰撞算法，也称为基于ALOHA机制算法，另一类是基于二进制的防碰撞算法。基于概率的防碰撞算法于是基于经典ALOHA算法，主要应用在少量标签识别的系统中，系统识别的可靠性相对差一些，优点是易于设计。本文主要研究基于二进制的防碰撞算法。
2、基于二进制的防碰撞算法
基于二进制RFlD防碰撞算法主要采用曼特斯特编码，如果多个标签同时发送的数据，在相同的位如果有两个值不同时，那么则接收的上升边和下降边互相抵消，使在整个比特长度内是不间断的副载波信号，这样采用曼特斯特编码可以识别碰撞位。
在_RFID系统中，每个标签的序列号都不一样，阅读器和标签对序列号进行比较式是按照对应位来比较，从低位向高位比较，并且约定0小于1，判断标签序列号的大小是先比较低位，比完低位再比高位，两数的大小由低位开始的第一个不相等位的大小决定，当两个序列号的所有数的全部位都相等时，才认为这两个序列号相等。
基于二进制的防碰撞算法中，主要使用了下面的指定指令：
（1）REQUEST指令：该指令由阅读器发送，并带有某个参数，该参数为某个序列号，阅读器发送一段序列号TD1，标签得到此序列号TD1，然后与自己的序列号ID进行比较，只有当自己的序列号小于或者等于阅读器发生的序列号时，标签才响应。其初始值通常设置为REQUEST（11111111）；
（2）sELECT指令，这是选择指令，阅读器接收电子标签传送的序列号，如果电子标签的序列号与自己发送的一致，则选中该标签，并与之通信；
（3）READATA指令，这是读取指令，阅读器读取选中的标签中的数据；
（4）UNSELECT指令，这是休眠指令，如果某个标签数据已经被读取，则发送该指令让标签不再响应阅读器的询问。
二进制防碰撞算法在工作的时候，首先由阅读器发出请求命名，等待电子标签的应答，如果没有接收到应答表示所在区域内没有电子标签，如果只有一个电子标签响应，那么该标签不会发生碰撞，阅读器则可以直接选择此标签，并与之通信。如果存在两个以上的电子标签响应，阅读器将检测是否发生碰撞，如果发生碰撞，则将序列号中碰撞的最高位置为0，其余的所有小于碰撞最高位值设置为1，并重新发送请求给电子标签，电子标签根据接收到的新的查询序列号，来判断是否需要应答，同样，需要应答的电子标签将自己的序列号传送给阅读器，阅读器同样检测是否发生碰撞，这个过程重复进行，直到没有碰撞发生，阅读器则与这些电子标签进行通讯。当电子标签与阅读器的通讯结束之后，阅读器发送命令使此标签不再对阅读器的查询命令，这个过程重复进行，直到所有标签发送完毕。从搜索过程可以看出，二进制防碰撞算法在搜索过程中重复搜索次数较多，传输位数较大。阅读器发送的参数和标签返回的序列号每次都要完整传输。实际应用中的序列号大多不只由一个字节所构成，按不同的规模甚至可以达到十个字节，这就造成了大量的信息冗余。动态二进制防碰撞算法在其基础上进行了改进，其基本思想是减少传送数据位数。假设x为碰撞最高位，传送位数为N，那么在（x-1）到0位总算被置为1的，不包括标签提供给阅读器的补充信息。标签应答的11）的第N-1到x位不包含给阅读器的补充信息，因此无需传输。上述想法引导出一种新算法：阅读器解码检测到冲突，将冲突起始位置0，数据高位不变，然后将原先碰撞前数据高位再加上碰撞起始位（置为O）作为新查询命令参数发送给标签，标签序列号则从数据高位开始比较，若对应的位等于该参数，则返回剩余数据位给阅读器，若剩余数据位上碰撞发生，则将碰撞最高位置为0加到原来Request@令参数末位最为新参数，继续上述过程，直至只有一个标签响应，阅读器检测到无碰撞发生，则将上一次发出的Request命令参数与标签返回的剩余位组合起来，该标签就被识别出来。因此设定新的请求格式Request（Ⅱ），w），其中s为7～x，在阅读器作用范围内的标签序列号的第7位到第x位与s卡日符的做出响应并返回剩余的w位给阅读器。动态二进制树算法的步骤如下： （1）阅读器发出一个序列号Request（null，8），全部标签均应答并返回完整序列号到阅读器。
（2）标签响应，如果标签超过2个，则发生碰撞。阅读器检测到碰撞位，设置碰撞位最高位为0加上发送冲突前的高位，更新标签要发送的序列号位数，将修改后的参数作为新的查询前缀。
（3）阅读发送更新后的请求查询指令给标签，标签序列号与参数值比较，匹配的标签将互补的序列号返回给阅读器。
（4）循环这个过程，直至阅读器识别到最小序列号的标签，选定该标签进行信息的读写，最后发送命令使该标签进入休眠状态，不再响应阅读器的请求命令。
（5）重复上述过程，直到阅读器依次识别出所有标签。
从算法搜索过程可以看出，动态二进制树算法中，阅读器命令与标签指令所携带的参数长度都在动态改变，因此该算法减少了传输信息量，一定程度上也节约了时间。但节点数目和循环次数没有发送改变。
3、一种新的防碰撞算法
新的RFID防碰撞的基本思路是减少所需传送的位数和查询次数。改进算法可以采用发送比特前缀，并且只有在阅读器解码得到碰撞位时才更新查询前缀的方式来优化，并采用宽度优先的方式构造一个二叉搜索树，在碰撞位按照左0右1分裂一个二叉树。基本原理如下：
阅读器在其作用区域内广播一个查询前缀0，若无标签应答则发送比特1，只有与查询前缀相符的ID才进行应答，标签并返回剩余ID给阅读器，阅读器检测是否发生碰撞，如果存在，则在最高碰撞位分裂为一个二叉树，再按照深度优先的方式搜索。算法如下：
（1）阅读器向作用区域内标签发送m比特查询前缀；
（2）当标签序列号的前m位与阅读器发送的m位查询前缀匹配时，则标签返回互补的第m位以后的序列号；否则不对阅读器进行响应；
（3）阅读器解码标签返回的第m位以后的序列号，若检测出第n位发生碰撞，则按照左0右1的方式分裂成一个二叉树，并向标签发出一个STOP指令使标签停止向阅读器继续应答序列号；
（4）阅读器根据以下三种状态对标签进行处理：（1）当第m位产生碰撞时，阅读器更新查询前缀，按照原阅读器发送前缀加上标签应答的比特（到）+“0/1”的二叉树深度优先的方式来更新.（2）若只剩下标签的最后一位发生碰撞，阅读器便裁定只余两个标签，这是由于任何一个标签11）都是独一无二的；（3）当碰撞没有发生，则发送sELECT命令选中该标签，读取该标签信息，最后令其“睡眠”。
（5）返回上次碰撞的节点，重复上述过程，直到所有标签被识别。
假设有4个标签，T1：10110010，T2：10100011，T3：10110011，T4：11100011
第一次，阅读器发送请求指令，向作用域内的标签广播查询前缀‘0’，没有标签匹配因此无响应。
第2次，阅读器发送查询前缀‘1’，四个标签都响应，并向阅读器返回剩余的11）序列号，在第6位就发生了碰撞，阅读器向标签发送sTOP指令，在第6应分裂出一个二叉树，再按照深度优先的方式更改查询前缀，即首先更新为10。
第3次，广播查询前缀10，标签1，2，3都应答，并检查出碰撞位在第4位。在该处分裂出一个二叉树。分别构成两个查询前缀1010和1011.
第4次，按照深度优先的方式，广播查询前缀11，可以识别出标签4。选中该标签进行信息传输，最后使其“休眠”。
第5次，广播查询前缀1010，标签中与1010前缀匹配的只有标签2，该标签被识别，选中该标签进行信息传输，最后使其“休眠”。
第6次，广播查询前缀1011，只有标签3响应，选中该标签进行信息传输，最后使其“休眠”。
我们根据上面的4个标签来分析改进后算法的性能，采用动态二进制数防碰撞算法时，阅读器发送的总比特数则为18比特，标签发送了54比特，共轮询9次，改进后的算法阅读器只需发送14比特，而标签只需传送17比特，共轮询6次，因此改进后算法的通信量明显减少。
4、结论
在分析动态二进制防碰撞算法的基础上提出了一个新的算法，该算法的阅读器通过广播查询前缀，并对响应的标签检测碰撞位，在碰撞位分裂出一个二叉树，按照深度优先的方式搜索，分析表明，改算法在通信量和查询次数方面明显优于动态二进制算法。