田旺兰，李梦醒，谭 跃

（湖南城市学院通信与电子工程学院，湖南益阳 413000）

基于分组处理的RFID防碰撞算法＊

田旺兰，李梦醒，谭 跃

（湖南城市学院通信与电子工程学院，湖南益阳 413000）

防碰撞算法是射频识别系统实现多目标识别的关键技术.针对基于二叉树的标签防碰撞算法存在识别次数较多和通信数据量较大的问题，提出一种新的基于分组处理的防碰撞算法.该算法将标签进行分组处理，直接用4个2位长的查询前缀去分裂标签集，读写器检测到数据中有2个碰撞位后不再接收后续数据，整个识别过程采用后退策略.仿真结果表明，该算法在查询次数和数据传输量均有较大提高.

射频识别；防碰撞；二叉树；分组处理；后退策略

1 NTA算法

1.1 相关命令

（1）查询命令：REQUEST（p，m）.当m＝0时，p为2位长的查询前缀，标签把查询前缀p与ID进行比较，如果两者匹配，则发送ID剩余的部分.m＝1时，p为最高碰撞位的位置，ID第p位为‘0’的标签应答ID第p位以后的数据.

（2）分组处理命令：GROUPING（Group＿num）.标签接收到此命令后，随机产生一个0～Group＿num之间的数，并存于存储器TG中，TG中值相等的标签在同一组.

（3）分组选择命令：SELECT＿GROUP（GN）.TG中与GN相等的分组被选中.读写器在算法开始时或识别完一个组中的标签后发送此命令.

（4）有效标签：TAG-ACTIVE.读写器识别一个标签后，发送此命令，如果标签中计数器TC＞0，则进行TC减1操作.

（5）停止命令：STOP.读写器检测到接收的数据中有2个碰撞位后，发送此命令，标签立即停止发送数据.

（6）选择标签：SELECT（P）.

（7）读出标签数据：READ-DATA（P）.

（8）标签去选择：UNSELECT（P）.

1.2 NTA算法

图1 NTA算法防碰撞处理流程

文中算法把读写器作用区域内所有标签进行分组，从小到大依次识别每个标签分组就可以识别所有标签.读写器根据标签ID的前2位，可以生成4个查询前缀“00”、“01”，“10”，“11”.读写器根据这4个查询前缀可以把每个分组中的标签分裂成4个子集.读写器发送2位长的查询前缀，直接选中那些与查询前缀匹配的标签进行识别.每个标签分组经过这样处理，能缩短每次从根节点开始识别的分解延迟.读写器对整个标签分组的识别过程采用后退策略，以减少查询次数.图1为NTA算法的防碰撞处理流程.

NTA算法的主要步骤如下：

（1）读写器发送分组命令GROUPING（Group＿num）进行标签分组处理，所有标签产生［0～Group＿num）之间随机数并存入TG.

（2）读写器把4个查询前缀入栈RS.发送SELECT-GROUP（GN）命令，选中第GN组标签.当第1次发送分组选择命令时，GN＝0，选择第0组标签.

（3）读写器发送查询命令REQUEST（p，m）命令.第1次发送REQUEST命令时，p为查询前缀“00”，m＝0.

（4）读写器对标签发送的数据进行译码，根据译码结果判断是否有碰撞发生.如果没有碰撞发生，读写器可以识别1个标签.如果只有1个碰撞位，读写器可以用‘0’和‘1’代替此碰撞位，同时识别2个标签.读写器识别标签后，依次发送SELECT和READ-DATE命令，读出标签中存储的数据信息.之后，读写器发出UNSELECT命令，让成功读写的标签进入休眠状态.接着，读写器发送TAG-ACTIVE命令，那些TC＞0的标签进行TC减1操作.读写器对RS进行出栈操作，获得新的查询命令.

如果检测到接收的数据中有2个碰撞，读写器发送STOP命令，停止接收后续数据.读写器检测最高碰撞位位置p，并把m设置成1，生成新的查询命令参数.算法跳至步骤（3），继续查询过程.

（5）当被选中分组中所有标签都被识别完时，GN＋＋，选中下一个标签分组进行识别，算法跳至步骤（2）.当GN＝Group＿num－1时，为最后1个标签分组，并且该分组中的所有标签都被识别完时，整个算法识别过程结束.

2 算法分析

2.1 算法分析

假设读写器作用区域内存在N个标签，标签被划分成Group＿num组.识别这N个标签所需的总查询次数为识别每个分组所需的查询次数之和.假设识别第i个分组中的标签所需的查询次数为Q（i），传输的数据为D（i）（其中0≤i＜Group＿num）.那么识别N个标签总的通信次数为

数据通信量为

由此可知，NTA算法识别N个标签的整体性能由识别每个分组的性能决定，优化NTA算法必须从每个标签分组着手.如果标签产生的随机数绝对随机，每个分组中标签的数量都是N／Group＿num，那么优化1个标签分组的性能就能使整个算法达到最大效率.

2.2 标签分组分析

以1个标签分组为实验，标签ID为96bit，随机生成，标签数量从2个逐渐增加到15个，在理想信道下进行仿真.观察识别该分组标签所需的平均查询次数和平均传输的数据量这2个方面的性能，程序连续运行5 000次取平均值.

图2为识别每个标签所需的平均查询次数.当标签数量大于5时，平均查询次数随着标签数量的增加而增大.当标签数量小于5时，平均查询次数会随着标签数量的下降会快速上升.

图3为平均识别1个标签产生的空查询数.当标签数量小于7时，空时隙数随着标签数目的减少会急剧增加.当标签数量大于7时，空查询次数逐渐降低，并趋于0.

图4为识别每个标签所传输的平均数据量，平均传输的数据量随着标签数量的增加呈上升趋势.分组中标签越多，平均传输的数据就会越多.

图2 平均查询次数与标签数量关系曲线

图3 平均空查询数与标签数量关系曲线

图4 平均传输的数据与标签数量关系曲线

综合考虑查询次数、传输的数据量、空时隙等因素，并且考虑到实际应用中标签产生的随机数并不是绝对随机，文中每个分组中标签数量的期望值为7，即总的分组数为N／7

3 仿真分析

文中提出的算法（NTA）与二叉树搜索算法（BS）、动态二叉树搜索算法（DBS）、后退式二叉树搜索算法（RBS）、陈炳才等［10］提出的RDS算法与王雪等［11］提出的BLBO算法进行比较，标签数量从50取到1 000，间隔50.通过对比不同标签数目下读写器成功识别所有标签所需的总查询次数和传输的总数据量来比较算法效率.不计控制、前后缀、校验冗余等开销，在理想信道下进行仿真.假设标签ID长96bit，ID随机生成.为提高数据精度，连续仿真100次取平均值.

图5为各算法识别标签所需的查询次数比较.从图中可以看出，BS算法和DBS算法所需的查询次数最多.RBS算法平均每识别1个标签需要查询2次.RDS算法和BLBO算法所需的查询次数与RBS算法相等.由于NTA算法采用分组策略，减少了每次应答标签的数量，并且采用2位长的查询前缀代替从根节点开始识别，故而能够减少查询次数.在这几种算法中，NTA算法所需的查询次数最少，平均识别1个标签约需要查询1.6次.

图6为各算法数据传输量的比较.这几种算法中，BS算法识别标签所传输的数据最多，DBS算法有所提高，为BS的50%.由于RBS算法所需的查询次数远远少于BS和DBS，RBS算法的数据传输量比BS和DBS都要少.RDS算法和BLBO算法都是基于后退机制的改进算法，它们的数据传输量相对RBS算法都有不同程度的改善.由于NTA算法减少了读写器的查询次数，并且标签只应答最高碰撞位以后的数据.所以，NTA算法能够降低数据传输量，约为DBS算法的1／6，优于RBS、RDS和BLBO等算法.

图5 不同算法识别标签的查询次数的比较

图6 不同算法数据传输量的比较

4 结语

提出了一种改进的基于树的防碰撞算法.新的算法把标签进行分组处理以减少每次应答标签的数量，用4个查询前缀去分裂标签集以减少从根节点开始识别的分解延时，算法整个识别过程采用后退策略.通过仿真分析得出了1个适当的标签分组数，使算法的整体性能达到了最佳.仿真实验证明了算法的有效性，在标签密集的场合，可有效地减少查询次数、降低数据传输量，提高识别效率.

［1］ 王中祥，王俊宇，刘 丹，等.BIS：一种降低空时隙开销的RFID防碰撞算法［J］.通信学报，2009，30（9）：1－6.

［2］ KLAIR D K，CHIN K W，RAAD R.ASurvey and Tutorial of RFID Anti-Collision Protocols［J］.IEEE Communication Surveys and Tutorials，2010，12（3）：400－421.

［3］ MOESSNER M，GUL N K.Secure Authentication Scheme for Passive Class1Generation2RFID Tags［J］.Computer Networks，2011，51（6）：273－286.

［4］ 陈 章，廖明宏.快速RFID防冲突算法［J］.计算机应用，2010，30（1）：18－20.

［5］ EOM J B，LEE T J.AnEfficient Framed-Slotted ALOHA Algorithm with Pilot Frame and Binary Selection for Anti-Collision for RFID Tags［J］.IEEE Communications Letters，2008，12（11）：861－863.

［6］ QUAN C H，HONG W K，LEE Y D，et al.A Study on the Tree Based Memoryless Anti-Collision Algorithm for RFID System［J］.Korean Information and Processing Society Transactions，2001，11（6）：851－862.

［7］ FINKENZELLER K.射频识别技术［M］.第3版，吴晓峰，陈大才，译.北京：电子工业出版社，2001.

［8］ 谢振华，赖声礼，陈 鹏.RFID技术和防冲突算法［J］.计算机工程与应用，2007，43（6）：223－226.

［9］ 余松森，詹宜巨，彭卫东，等.基于后退式索引的二进制树形搜索反碰撞算法及其实现［J］.计算机工程与应用，2004，40（16）：26－28.

［10］ 陈炳才，徐东升，顾国昌，等.一种基于堆栈存储的RFID防冲突算法［J］.计算机应用，2009，29（6）：1 483－1 486.

［11］ 王 雪，钱志鸿，胡正超，等.基于二叉树的RFID防碰撞算法的研究［J］.通信学报，2010，31（6）：49－57.

［12］ 王春华，许 静，彭关超，等.改进的RFID标签识别防冲突算法［J］.计算机工程与应用，2011，47（31）：104－107.

（责任编辑 陈炳权）

Tree-Based Anti-Collision Algorithm Radio Frequency Identification System

TIAN Wang-lan，LI Meng-xing，TAN Yue
（College of Communication and Electron Engineering，Hunan City University，Yiyang 413000，Hunan China）

The anti-collision algorithm is the key technology of radio frequency identification system to achieve multi-target recognition.To solve the problem of too many identification times and transmitted bits in some binary tree based schemes，a new tree-based anti-collision algorithm is proposed.The algorithm divides tags into several groups.Four query prefixes which consist of two bits are directly used to split tag set，and the backtrack strategy is adopted to reduce identification times.The simulation results show that the algorithm significantly improves the query times and the data transmission.

radio frequency identification；anti-collision；binary Tree；grouping process；backtrack strategy

TP301.6

A

10.3969／j.issn.1007－2985.2013.05.016

1007－2985（2013）05－0066－04

射频识别（Radio Frequency Identification，RFID）技术是近年来新兴的一种非接触自动识别技术.由于RFID具有识别距离远、数据容量大、可以非视距通信等特点［1］，被广泛应用在物流跟踪、供应链管理、电子支付等领域［2］.典型的RFID系统通常由读写器、电子标签和后台计算机系统3个部分构成［3］.RFID系统通过在读写器与电子标签之间构建一个无线双向信息传输通道来实现电子标签的自动识别.当多个标签同时响应读写器时，标签信号会相互干扰，读写器不能正确识别标签信息，发生标签碰撞［4］.标签碰撞会减慢识别过程，甚至读写器无法识别标签.因此需要防碰撞算法去解决标签碰撞问题，以提高系统识别效率.

目前，大多数标签防碰撞算法都是基于时分多址技术，主要有2大类：基于ALOHA的概率性算法和基于树的确定性算法［5－6］.由于基于树的算法不存在“标签饥饿”问题，被得到广泛应用.二叉树算法根据标签ID或者随机产生的二进制0和1把标签集划分成2个子集.若有碰撞，继续分裂子集，直到每个集合中只含有1个标签，读写器就能识别作用范围内所有标签.典型的基于树的算法包括二叉树搜索算法（Binary Search Tree，BS）［7］、动态二叉树搜索算法（Dynamic Binary Search Tree，DBS）［8］、后退式二叉树搜索算法（Regressive Binary Search Tree，RBS）［9］等.陈炳才等［10］在结合DBS与RBS算法优点的基础上，提出了一种基于堆栈的动态减位防冲突算法（Reduces Dynamic binary algorithm on Stack，RDS），RDS算法能够减少读写器与标签的数据传输量，但是识别标签所需的查询次数却仍与RBS算法相当.王雪等［11］提出了一种锁位后退防碰撞算法（Bit-locking backoff anti-collision algorithm，BLBO），BLBO算法采用后退机制，并且每轮查询中，读写器和电子标签都只处理那些在第1轮查询中发生碰撞的位.所以，BLBO算法能够显著地降低数据通信量，但是查询次数却没有得到改善，与RBS算法相同.王春华等［12］提出了一种改进的基于堆栈的二进制树防冲突算法（IBSTS），IBSTS算法用堆栈存储识别过程产生的信息，读写器和标签只处理上一轮查询中发生碰撞的位，算法采用后退机制，IBSTS算法在数据通信量方面有较大改善，但查询次数还是与RBS算法相等.

同时考虑通信数据量与查询次数2个方面，笔者提出一种新的基于树的防碰撞算法（New tree-basedanti-collision Algorithm，NTA）.提出的算法对标签进行分组处理，直接用4个2位长的查询前缀去分裂标签集，并且识别过程采用后退策略以提升系统的识别效率.

2013－06－11

湖南省教育厅科学研究资助项目（11C0249）

田旺兰（1977－），女，湖南娄底人，湖南城市学院讲师，硕士，主要从事RFID技术、无线传感网络研究；李

梦醒（1972－），男，湖南宁乡人，湖南城市学院副教授，博士，主要从事现代信号处理在通信系统中的应用研究；谭跃（1974－），男，湖南安化人，湖南城市学院副教授，博士，主要从事自动控制研究.