一种基于ID预测和二叉搜索的RFID标签防碰撞算法

李晓琴

(山西省电子工业科学研究所，山西 太原 030006)



一种基于ID预测和二叉搜索的RFID标签防碰撞算法

李晓琴

(山西省电子工业科学研究所，山西 太原 030006)

摘要：标签防碰撞问题是RFID系统的重要研究课题之一，本文在研究经典防碰撞算法的基础上，提出一种基于ID预测和二叉搜索的RFID防碰撞算法IDPBS，使用自定义编码方式，减少标签之间的干扰，结合二叉搜索机制，利用堆栈寻找碰撞位并完成标签识别。数据分析及实验结果表明，本文算法可以正确有效地完成RFID标签的识别。

关键词：物联网；RFID；防碰撞；二叉搜索

射频识别(RFID)是一种基于无线通信的非接触式标签识别技术，目前已被广泛用于识别、跟踪和管理生物体或非生物体[1]。RFID与现有的条形码识别技术类似，但功能更加丰富，例如RFID标签具有更大的存储容量、更远的识别半径以及多标签识别能力。RFID系统一般包括信息载体(射频标签)、信息获取装置(射频识读器)、空中接口和边缘服务器等部分[2]。标签的能量来源包括有源、无源和半有源三种，其中，无源标签的能量全部来自于射频识读器发射的电磁波，因此，无源标签成本低、寿命长，应用最为广泛[3]。

一般地，射频识读器通过射频信号广播数据收集请求，处于识读区域内的射频标签收到请求后通过无线电波应答，返回识读器请求的数据。由于识读器和标签之间的无线信道是共享的，当多个标签同时向识读器发送应答数据时，就会导致信道拥塞，也就是多标签碰撞[4]。多标签碰撞将会迅速降低网络吞吐量，造成带宽浪费和能量消耗，并影响网络的效率和可靠性。当前，已有一些学者对RFID标签碰撞问题进行了研究，并设计了一些行之有效的防碰撞协议，这些协议的共同目标是减少阅读器识别范围内全部标签所需的时间，比较典型的算法有基于帧时隙的ALOHA类方法和基于搜索树的二叉搜索类方法[5]。ALOHA类算法中，标签以随机方式响应，计算复杂度较低，实施成本低，但是在网络规模较大时容易产生“Tag Starvation”现象，即部分标签长时间不能被识别；而二叉搜索类算法采用逐位匹配的方式，如果运行足够长的时间，可以识别全部的标签，但是在标签数量较大时，算法性能会大大降低。同时，大部分防碰撞算法没有引入数据传输校验机制，无法确定数据传输的准确性。

本文在结合ALOHA类算法和二叉搜索类算法的优点的基础上，提出了一种基于ID预测和二叉搜索的IDPBS算法，首先在标签中设计标记区，用于标签预测和数据校验，然后在标签预测的基础上，采用二叉搜索算法对标签进行识别。实验结果表明，对于存储能力、计算能力均受限的无源RFID标签，IDPBS可以有效减少识读器的查询次数和标签回传的数据量，具有更优秀的性能。

1相关工作

1.1ALOHA类算法

ALOHA类算法是一类随机接入方法，当标签处于识别区域内时，就主动向识读器发送数据[6]。算法将传输时间分成多个离散的时间片，称为时隙，时隙长不小于一个帧(标签ID)传输所需时长。当某时隙中只有一个标签发送数据时，该标签就被成功识别。因此，每个时隙可能出现三种情况，即识别成功、标签碰撞和时隙空闲，如图1所示。

图1　ALOHA算法思想

假设网络吞吐量定义为一帧内成功发送的平均标签数。由于ALOHA算法在数学原理上是一个多重伯努利试验，假设一个标签发送成功的概率为P，则在未进行分片时，ALOHA算法在稳定状态下有如下公式：

S=G·P=Ge-2G.

(1)

时隙ALOHA算法规定标签只能选择时隙的分界处发送数据，这样数据只可能成功发送或发生碰撞，时隙ALOHA算法在稳定状态下：

S=G·P=Ge-G.

(2)

可以看出，相比纯ALOHA算法，时隙ALOHA算法系统吞吐量增大了一倍。在时隙算法的基础上，有人提出了一种基于Gen-2协议的SR算法，为每个标签设计一个随机数生成器和一个时隙计数器。SR算法可以在一个识读周期内，使部分未识别的标签调整数据发送时机，再次进行数据发送，增大标签被识别的机会，提高识别效率[7]。在SR算法中，算法参数(Q值)可以进行动态调整，避免时隙范围太大或太小引起的空闲时隙太多或者碰撞概率过大的问题。

1.2二进制搜索类算法

根据ISO/IEC 14443标准，RFID系统采用二进制搜索类算法时，应使用Manchester编码规则，理想情况下识读器可以同时获得全部标签返回的数据，并得到发生碰撞的位置的准确信息[8]。算法将处于冲突的标签划分为多个子集，然后对其中一个子集进行查询，如果没有产生冲突，那么可以正确识别一个标签，如果产生冲突，那么就将当前集合再划分为多个子集进行查询，直至正确识别一个标签。如图2所示。

图2　二进制搜索算法思想

在基本的二进制搜索防碰撞算法中，通常识读器首先广播一个与标签ID等长的查询序列QS，标签在收到广播信息后，将自身ID与QS进行比对，如果不发生冲突，则有一个标签被成功识别，如果发生冲突，则根据冲突信号将QS中对应最高碰撞位的数值置0，再次进行查询，重复此操作直至成功识别ID最小的标签并使其进入静默状态，不再响应识读器的广播信息。重复以上步骤，直至所有标签都被成功识别。

以基本的二进制搜索算法为基础，有学者提出了回退二进制搜索算法、多叉树混合搜索算法。由于二进制搜索类算法的计算过程与标签ID位数相关，因此计算量会随着ID位数的增长急剧上升，导致算法性能大幅下降，当ID为数过长时，二叉搜索算法无法保证在可接受的时间内识别所有的标签。

2算法设计

2.1标签编码设计

与条形码编码规则类似，RFID标签ID为等长且唯一的“0”“1”序列，是RFID标签的唯一标识。在传统的ID编码方式基础上，参考IPA算法编码方式，将ID分为标记区Tv与数据区Dv，其中标记区记录的是数据区中“1”的个数。

10010101010标记区数据区

在这种编码方式下，识读器需要记录的信息包括当前标签的ID和已识别的“1”的个数N1T。

如果Tv-N1T=1，说明标签T只有一个1未被识别，这个1可能处在发生冲突的任何位置，除了这个1所在的位置，其他位置均为0。

2.2通信命令设计

2.2.1识读器命令设计

activate(null/prefix)激活命令，如果参数为null，激活当前查询范围内的所有标签；如果参数为prefix，激活当前查询范围内的与此前缀匹配的所有标签。

require(Tv,0)请求命令，收到命令的所有标签响应，返回1，表明当前查询范围内有与此前缀匹配的标签。

require(Tv,prefix)请求命令，使处于active状态的与prefix匹配的标签响应，向识读器发送数据位信息。

read(ID)读取命令，读取成功识别的标签中存储的信息。

slience(prefix)休眠命令，使当前查询范围内的与此前缀匹配的所有标签进入休眠状态，这些标签在下次收到激活命令时，才会进入激活状态并响应识读器的请求。

stackpush(posi,1)压栈命令，将当前发生碰撞的最高位压入碰撞栈中。

stackpop()出栈命令，将碰撞栈的当前最高位弹出栈。

2.2.2标签状态设计

active：表明当前标签处于激活状态，等待响应识读器发布的指令。

sleep：表明当前标签处于休眠状态，本轮不再响应识读器发布的指令，等待下一次激活后才对识读器指令进行相应。

operative：表面当前标签在识别过程中发生碰撞，正在识别过程中。

2.3算法工作流程设计

IDPBS算法伪代码描述如下：

AlgorithmIDPBS(){//判断当前区域是否有待识别标签1activate(null);2if(noresponse)3end4 elsefor5(Tv=min(Tv);Tv

在IDPBS算法中，识读器首先广播激活命令activate(null)，区域内全部标签在收到此命令后，将自身的状态置为active。识读器广播标记区所有可能的情况，如果标签的标记区与识读器询问的相同，则向识读器发回简短的确认指令，表明当前区域有标记区为当前询问值的标签。然后对于每个识别出的Tv值，向对应的标签发送read(ID)命令进行识别并校验，识别过程可分为三种情况：1) 无碰撞现象，标签被直接识别；2) 满足2.1条件，标签被快速识别；3) 其他标签，采用二叉搜索算法进行识别。在识别并读取标签ID的过程中，识读器根据标记区校验数据，如果识别正确，发送slience(prefix)命令使其进入sleep状态，如果检测到ID识别错误，则将其丢弃。最后，IDPBS算法识别之前识别错误的标签。

3实验结果与分析

为验证本文算法的正确性和有效性，随机选取一组标签进行测试。标签采用Manchester编码。假设标签均处于识读器的识别范围内，在数据传输过程中互不干扰。待识别标签如表1所示。

表1　待识别标签

标签识别流程如下：

1) 识读器广播命令，8个标签均尝试发送标记区位数信息，表明当前区域有待识别标签并说明Tv区域大小。

2) 识读器广播轮询所有可能的Tv值，标签收到广播后与自身的标记区比对，如果匹配则向识读器返回确认信息。识读器将有确认信息的标记值保存，即001，010，100，101。

3) 识读器广播消息，要求标记区为“001”的标签响应，即tag8。tag8被识别。

4) 识读器广播消息，要求标记区为“010”的标签响应，即tag6和tag7响应。识读器收到的标签信息为“1X00000X”，对于tag6和tag7，识读器计算可得Tv-N1T=1，tag6的冲突位中，只有一处可能为1，其他冲突位为0，识读器更改查询参数，识别tag6，并以同样的方式识别tag7。

5) 识读器广播消息，要求标记区为“100”的标签响应，即tag4和tag5响应。识读器收到的标签信息为“XXXX1010”，将冲突位信息从低位到高位依次压入碰撞栈。识读器修改require参数，执行require(100,0)，此时只有tag4响应，tag4被识别。之后执行出栈命令，产生新的请求命令require(100,0)，此时只有tag5响应，tag5被识别。

6) 识读器广播消息，要求标记区为“101”的标签响应，即tag1,tag2,tag3响应，识读器收到的标签信息为“1XX101XX”，将冲突位信息从低位到高位依次压入碰撞栈，修改require参数，执行require(101,11)，此时只有tag2响应，tag2被识别。之后执行出栈命令，产生新的请求命令，发生碰撞，将冲突为信息从低位到高位依次压入碰撞栈，发送新的请求命令require(101,110010)此时只有tag3响应，tag3被识别。之后执行出栈命令，识别tag1。

识读器在读取标签ID后，根据标记区的信息校验ID是否识别正确，如果校验错误，则丢弃该标签的ID信息，重新识别。

可以看出，IDPBS算法根据标签标记区将标签分为不同的分组，在组内使用二叉搜素算法识别，在识别后对标签ID进行校验，丢弃错误数据，保证了标签识别的效率和准确性。

4结论

本文针对RFID标签碰撞问题进行了研究，在分析经典防碰撞算法的基础上，提出了一种基于ID预测和二叉搜索的RFID防碰撞算法IDPBS，在减小标签识别冲突域的基础上还增加了数据校验功能，试验结果表明，IDPBS算法能够正确有效地识别区域内全部RFID标签。

参考文献

[1]Namboodiri V,Desilva M,Deegala K,et al.An Extensive Study of Slotted Aloha-based RFID Anti-collision Protocols[J].Computer Communications,2012,35(16):1955-1966.

[2]黄玉兰.物联网射频识别(RFID)核心技术详解[M].北京：人民邮电出版社, 2010.

[3]Shahzad M,Liu A X.Probabilistic Optimal Tree Hopping for RFID Identification[J].Networking IEEE/ACM Transactions on,2015,23(1):796-809.

[4]岳克强.RFID多标签防碰撞算法研究及应用[D].杭州：浙江大学,2014.

[5]潘昊，陈蒙.物联网中无线射频识别读写器系统防碰撞算法优化[J].计算机应用,2015,35(1):23-26.

[6]史长琼，肖瑞强，吴丹.改进的动态帧时隙ALOHA防碰撞算法[J].计算机工程与设计,2014,35(6):1897-1900.

[7]孙文胜，刘先宝.RFID系统标签防碰撞的研究与改进[J].计算机工程与应用,2012(16):103-106.

[8]李聪，谷晓忱，李建成，等.一种对时钟偏差不敏感的无源RFID标签编解码算法[J].国防科技大学学报,2013,35(3):126-131.

收稿日期：2015-12-11

作者简介：李晓琴(1975- )，女，山西沁源人，助理工程师，主要从事无线电技术工作。

文章编号：1674- 4578(2016)02- 0017- 03

中图分类号：TP391，TN92

文献标识码：A

An RFID Tag Anti-collision Algorithm Based on ID Prediction and Binary Search

Li Xiaoqin

(ShanxiProvinceElectronicIndustryScienceInstitute,TaiyuanShanxi030006,China)

Abstract:The tag anti-collision problem is an important research topic in RFID systems. This paper studies the classical anti-collision algorithm and proposes an RFID tag anti-collision algorithm IDPBS based on ID prediction and binary search. The IDPBS uses a custom encoding method to reduce the interference between tags, then uses the stack and binary search mechanism to find the collision position and completes the tag identification. The algorithm analysis and experimental results show that IDPBS can identify the RFID tags correctly and effectively.

Key words:Internet of Things; RFID; anti-collision; binary search