李 云，谢 刚，郑 重，杨江波

(太原理工大学信息工程学院，山西 太原 030024)

责任编辑:薛 京

射频识别(Radio Frequency Identification，RFID)系统运行时，当读写器作用区域内多个标签同时向读写器发送信号，会产生信号相互干扰的现象，这种现象称为标签的碰撞，而解决此类碰撞的算法则称为标签防碰撞算法。目前，现有的时分多路(TDMA)标签防碰撞算法可以分为基于ALOHA机制的随机性算法和基于二进制树的确定性算法两种类型［1］。基于ALOHA机制的算法操作简单、易于实现，但当标签数目较大时，部分标签可能会在相当长的一段时间内得不到识别，出现“饿死”现象［2］。目前研究较多的是帧时隙ALOHA算法［3-4］，主要是通过估计标签数量来确定帧长从而减少碰撞，但仍未解决标签“饿死”问题。基于二进制树的算法［5-9］识别率高，避免了标签“饿死”现象，适应标签数目较大的场合，但通信量大，且有相当长的延时。文献［5-6］通过后退策略降低了通信量，但是碰撞时隙较多，仍有相当长的延时。文献［7］是通过启发式函数h(x)的大小来估计节点内待识别的标签数量，由于每次搜索都要计算h(x)，虽然减少了搜索次数，但通信量仍然很大。文献［8］规定只有1位碰撞位时直接识别2个标签，文献［9］规定只有2位碰撞位时直接识别，两种改进都减少了搜索次数，但当标签较少时出现符合规定的概率较小。

本文针对以上算法存在的不足，提出了一种新的基于分组策略的RFID自适应防碰撞算法(AGS)，该算法在二叉树搜索算法的基础上引入分组策略、后退策略和自适应地选择四叉树搜索策略，大幅度地降低了读写器的搜索次数，减少了标签与读写器间的通信量与延时，提高了识别效率。

1 AGS算法原理

根据标签内部的计数器R的值将标签分为两组:A组(R=0)标签ID中“1”的个数为偶数;B组(R=1)标签ID中“1”的个数为奇数。读写器首先对A组标签发出搜索命令，符合条件的标签将自身的ID值传送给读写器，读写器根据曼切斯特解码检测本次响应标签的碰撞情况。若无碰撞，直接识别，读写器再对B组标签发出搜索命令;若有碰撞，则根据连续碰撞位的信息将该组标签分为不同的子集，即如果检测到有3位连续的比特位发生碰撞，则立刻停止对ID进行编解码，将该组标签分为“00”，“01”，“10”，“11”共4 个子集，并将已识别的比特位压栈;如果检测到3个非连续的比特位发生碰撞，则根据最高碰撞位的位置将该组标签分为“0”，“1”共2个子集。读写器继续发出命令，直到标签信息不再发生碰撞，标签被成功识别，读写器采用后退策略，继续发出前一条搜索命令，直到该组标签全部识别成功。具体算法流程如图1所示。

图1 AGS算法流程图

2 算法协议

为便于实现和描述该算法，提出如下算法协议对算法进行约束。

1)请求命令Request。命令有3种形式:Request(null，p)，Request(x，q)和 Request(x，y，q)。

Request(null，p)中p为0或1，读写器第一次搜索时发送，要求读写器作用区域内所有计数器R的值与p的值相同的标签响应;Request(x，q)中x为0或1，q为上一次搜索过程检测到的最高碰撞位;Request(x，y，q)中x，y分别为0或1，q为最高碰撞位，当上一次搜索过程检测到连续的3位碰撞位时使用此命令。

2)如果读写器检测到只有2个比特位发生碰撞时，读写器直接识别这2个标签。

3)当读写器检测到有3个比特位发生碰撞时，则立刻停止对ID进行编解码。

4)根据检测最高碰撞位连续个数自适应地确定搜索树的分叉数，即在某分支下检测出最高碰撞位连续的个数大于等于3时，则选择四叉树搜索，否则选择二叉树搜索。

3 算法步骤

假设读写器作用区域内有8个标签，各个标签的编码及其识别过程如图2所示。

图2 算法的搜索识别过程

1)读写器发送命令Request(null，0)，读写器作用区域内计数器R=0的所有标签均作出响应。本例中，D7D6D5均发生碰撞，则q=7。

2)读写器发送命令Request(0，0，7)，即选择D7D6为“00”的待命态标签，只有Tag4满足条件，不存在冲突问题而直接识别。

3) 读写器发送命令 Request(0，1，7)，Tag3，Tag5 满足条件并作出响应。此时，读写器解码得:1000??，只有2位碰撞位，由算法协议2)可知:读写器不必发送请求命令而直接识别 Tag3，Tag5。

4) 读写器发送命令 Request(1，0，7)，Tag1，Tag6，Tag7满足条件并作出响应。此时读写器解码得:1?0??，最高碰撞位为D4。

5) 读写器发送命令Request(0，4)，Tag6，Tag7 满足条件，并作出响应。此时，读写器解码得:000??，只有2位碰撞位，从而直接识别Tag6，Tag7。

6)读写器发送命令Request(1，4)，此时只有Tag1满足条件，不存在冲突问题直接识别。

7)读写器发送命令Request(1，1，7)，此时只有Tag2满足条件，直接识别。

8)读写器发送命令Request(null，1)，读写器作用区域内计数器R=1的所有标签均作出响应，此时只有Tag8满足条件，不存在冲突问题而直接识别。

4 算法仿真分析

设读写器作用区域内存在N个标签，标签ID为n位，由标签计数器R的值将N个标签分为两组:R值为0的标签个数为N1个;R值为1的标签个数为N2个。读写器识别两组标签的过程中，检测到只有2个碰撞位的情况分别为M1，M2次，使用四叉树时出现如图3a的情况分别为 P1，P2次，出现如图3c的情况分别为Q1，Q2次。

图3 四叉树代替二叉树可能出现的3种情况

策略1:后退策略

基于后退策略的二进制搜索算法识别N个标签所需搜索次数为

策略2:自适应策略

出现连续3位碰撞位时，采用四叉树代替二叉树有如图3所示的3种情况。假如读写器作用区域内存在00011101和00000001两个标签时，产生如图3a所示的情况，此时采用四叉树比二叉树增加了2次搜索;假如读写器作用区域内存在00011101，00000001和00001001这3个标签时，产生如图3b所示左边的情况，此时采用四叉树的搜索次数与二叉树的搜索次数相同;假如读写器作用区域内存在00011101，000110001，00000001和00001101这4个标签时，产生如图3c所示的情况，此时采用四叉树，比二叉树减少了2次搜索。

策略3:分组策略

由算法协议2)可知，在识别A组标签的过程中检测到M1次只有2个比特位发生碰撞时，采用本算法相当于在二叉树上减少了M1个叶子节点，即搜索次数减少2×M1次。

本算法将以上3种策略结合在一起，读写器识别计数器R=0的所有标签需要搜索次数为

同样，读写器识别计数器R=1的所有标签需要搜索次数为

因此，采用本算法读写器识别其作用区域内的所有标签所需的搜索次数为

本算法的吞吐率可表示为

在MATLAB仿真平台上对本算法、四叉树搜索算法、基于后退策略的二进制搜索算法、动态调整二进制搜索算法［8］和PDBS［9］进行仿真。目前 EPC 编码体系中使用较多的是EPC-64。在仿真实验中编码位数n由标签数量决定。现取n=8，n=16两种情况分别对读写器发出的搜索次数和系统的吞吐率进行仿真，结果如图4～图7所示。

1)由图4和图5可看出:当标签数目大于100时，与其余4种算法相比，本文算法的搜索次数明显减少，吞吐率增幅很大。

图7 n=16时吞吐率比较

2)由图6和图7可看出:当标签位数和标签数目一定时，本文算法和PDBS算法明显优于四叉树搜索算法、基于后退策略的二进制搜索算法和动态调整二进制搜索算法;随着标签数目的增加，本文算法的吞吐率较PDBS算法及其他算法越来越高。

3)由图4～图7可看出:当标签位数一定时，随着标签数目的增加，将后退策略、分组策略和自适应策略相结合的算法所得到的系统吞吐率明显高于单纯地选用四叉树策略、后退策略或分组策略所得到的系统吞吐率。即当标签位数一定时，随着读写器作用区域内的标签数量N的增大，检测出只有2位比特位发生碰撞的概率越大，发生图3c的概率也将远大于发生图3a的概率，即算法的吞吐率越大。

5 结束语

本文提出了一种基于分组策略的RFID自适应防碰撞算法，该算法在二进制搜索算法的基础上加入了分组策略、后退策略和自适应策略。分组策略和自适应策略的引入，有效地降低了标签间的碰撞次数，大幅地提高了读写器的吞吐率，再加上后退策略，又更进一步地减少了读写器与标签间的通信量。通过对新算法的性能分析及对仿真结果的比较证明，新算法更高效地解决了标签的碰撞问题，具有良好的应用前景。

［1］刘云浩.物联网导论［M］.北京:科学出版社，2011:33-37.

［2］王春华，许静，彭关超，等.改进的RFID标签识别防冲突算法［J］.计算机工程与应用，2011，47(31):104-107.

［3］FINKENZELLER K.RFID handbook fundamentals and applications in contactless smart cards and identification［M］.2nd ed.West Sussex:John Wiley ＆ Sons Ltd.，2003.

［4］郭志涛，程林林，周艳聪，等.动态帧时隙 ALOHA算法的改进［J］.计算机应用研究，2012，29(3):907-909.

［5］RYU J，LEE H，SEOK Y，et al.A hybrid query tree protocol for tag collision arbitration in RFID systems［C］//Proc.IEEE International Conference on Communications.［S.l.］:IEEE Press，2007:5981-5986.

［6］CHEN Y H，HORNG S J，RUN R S，et al.A novel anti-collision algorithm in RFID systems for identifying passive tags［J］.IEEE Trans.Industrial Information，2010，6(1):105-121.

［7］丁治国，朱学永，雷迎科，等.基于启发式函数的多叉树防碰撞算法［J］. 计算机应用，2012，32(3):665-668.

［8］谢振华，赖声礼，陈鹏.RFID技术和防碰撞算法［J］.计算机工程与应用，2007，43(6):223-225.

［9］伍继雄，江岸，黄生叶，等.RFID系统中二叉树防碰撞算法性能的提升［J］.湖南大学学报:自然科学版，2010，39(12):82-86.