分组自适应分配时隙的RFID防碰撞算法研究

张小红,胡应梦

(江西理工大学信息工程学院,江西赣州 341000)



分组自适应分配时隙的RFID防碰撞算法研究

张小红,胡应梦

(江西理工大学信息工程学院,江西赣州 341000)

为了解决射频识别(Radio Frequency IDentification,RFID)系统中的多标签防碰撞问题,在分析帧时隙ALOHA算法的基础上,提出一种基于分组自适应分配时隙的RFID防碰撞算法(GAAS).首先让阅读器对标签随机所选的时隙进行扫描统计,并将其发送给每一个标签,标签再进行相应地时隙调整,使阅读器跳过空闲时隙和碰撞时隙,自适应地分配有效时隙,进而对标签进行快速识别.当未识别标签数比较大时,算法采用分组以及动态调整帧长等策略,以减少时隙处理的时间.仿真结果表明:GAAS算法提高了系统的识别效率和稳定性,降低了传输开销.特别是当标签数超过1000时,该算法的吞吐率仍保持在71%以上,比传统的帧时隙ALOHA-256算法和分组动态帧时隙ALOHA算法的系统效率分别提高了300%和97.2%.

射频识别;ALOHA算法;标签分组;吞吐率;自适应分配时隙

1　引言

射频识别(Radio Frequency IDentification,RFID)是一种利用电磁波传播方式在阅读器和标签之间进行非接触双向数据传输,进而获取被标识物体信息的识别技术[1],被公认为21世纪的最具发展前景和变革力的高新技术.该技术具有数据交换快、追踪物体及时、无空间限制、穿透能力强、多目标识别和抗污染等优点,在物流管理、交通运输、自动化生产、公共信息服务等行业有着广泛的应用,可大幅提高管理与运作效率,降低成本[2,3].

RFID系统由电子标签(tag)、读写器(reader)和后端数据库(database)三大部分组成.在多个阅读器与多个标签的射频识别系统中,存在着两种形式的碰撞,即阅读器碰撞和标签碰撞[4].由于阅读器碰撞发生的概率较小且阅读器本身的处理能力较强,因此阅读器碰撞问题较容易解决.国内外的学者在多标签同时与读写器进行通信的碰撞问题方面已经做了大量的研究[5～7],这些方法一般被分为四类:空分多路法、频分多路法、码分多路法和时分多路法[8].由于标签的低功耗、低存储能力和有限的计算能力等特点,标签防碰撞方法主要采用时分多路法.

在时分多路法中,目前最常用的多标签防碰撞算法分为两种,一种是基于二进制树的确定型算法,其主要代表算法有二进制搜索算法[9]、动态二进制搜索算法[10]、跳跃式动态树算法[11]、查询树算法[12]等.该类法是由阅读器根据标签ID的唯一性来选择标签进行通信,所以搜索算法的性能会随ID位数的增加而急剧恶化.另一种是基于ALOHA的统计型算法.其主要算法包括时隙ALOHA(Slotted ALOHA,SA)算法[13]、帧时隙ALOHA(Frame-slotted ALOHA,FSA)算法[14]、动态帧时隙ALOHA(Dynamic Frame-slotted ALOHA,DFSA)算法[15],另外还有EPCglobal提出的EPC Class-1 Generation-2(EPC C1G2)标准[16]采用一种基于Q值的随机帧时隙算法[17,18]以及近期有文献提出基于碰撞预测的ALOHA防碰撞(Collision Prediction-ALOHA,CP-ALOAH)算法[19]等.这些防碰撞算法实现过程相对比较简单,标签内部也不需要设计复杂的电路,因此标签的成本也较低.然而,随着标签的数目增大,甚至上千时,发生碰撞的概率也随之增大,系统识别的性能急剧下降.针对于大量标签的识别问题,研究者们又提出分组的概念,有增强的动态帧时隙算法[20]、分组动态帧时隙ALOHA(Grouped Dynamic Frame-slotted ALOHA,GDFSA)算法[21]等.与之前的算法相比,分组类的防碰撞法其吞性能比较稳定,但是与其他算法一样,其吞吐率均比较低,只有40%～50%左右.

本文提出了自适应分配时隙(Adaptive Allocating Slots,AAS)算法,随着待识别标签数目的增加,又加入分组的概念,即分组自适应分配时隙(Grouped Adaptive Allocating Slots,GAAS)算法.该算法结合了传统GDFSA和CP-ALOHA算法的特点,在它们的基础上进行了优化和改进.首先估计标签数量,然后采用分组、动态调整帧长、时隙预约以及自适应分配时隙等策略对标签进行识别.仿真结果表明,新的算法降低了传输开销,简化了标签电路的设计,提高了系统的识别效率和稳定性.当标签数目大于1000时,其系统识别效率仍可达71%以上,与EPC标准协议相比,传输开销大约下降了48.1%,且随着标签数目的增加,新算法的优越性更加明显.

2　GAAS算法描述

2.1基本定义

定义1[22]设定一帧内的时隙数,即帧长为L,在对n个标签进行识别时,每一个标签都会随机选择一个时隙来发送自己的识别码信息,根据二项分布定理,某个标签占用帧内任意时隙的概率为p=1/L,则同一个时隙里有r个标签的概率可以表示为:

(1)

当r=0,即一个时隙里没有请求识别标签,该时隙称为空闲(idle)时隙,其概率为:

(2)

当r=1,即一个时隙里只有一个标签请求识别标签,该时隙称为成功(success)时隙,其概率为:

(3)

当r≥2,即一个时隙里有两个及以上的标签请求识别标签,该时隙称为碰撞(collision)时隙,其概率为:

Pc=1-Ps-Pi

(4)

(5)

(6)

(7)

定义2[23]RFID系统的吞吐率S是指阅读器在一个识别帧长的时间内成功传输信息的标签数目所占的比例,即:

(8)

2.2标签数目估计

GAAS算法要求阅读器在开始识别前,需估计剩下标签的数量.帧长的大小和未识别标签的数目越接近,系统效率越高,因此该过程对于整个识别过程起着至关重要的作用.目前已经提出了多种标签数目估计方法,有Vogt算法[24],Cratio算法[25],Schoute算法[26]和Low Bound算法[27].Vogt算法可以做出误差相对较为小且稳定的估计,因此本文采用Vogt算法来估计标签的数目.

(9)

2.3RFID系统最优帧长分析

阅读器在其可读范围内的标签数目进行估计之后,需要根据标签数目动态的调整帧长,如果帧长取值太大就会产生大量的空闲时隙,反之会导致碰撞时隙急剧上升,最终都将影响系统识别效率.因此要想取得较高的吞吐率效率,必须找出帧长与标签数目之间对应关系,即确定最优帧长[28].对式(8)求导:

(10)

令式(10)等于0,达到帧长L与标签的个数n应满足:

(11)

再由泰勒级数展开得到

(12)

由式(12)可知,当标签数n远大于1,并且n接近于帧长L时,系统的吞吐率达到最大.图1给出了L为不同固定值时系统吞吐率的仿真结果:

根据式(8),相邻固定帧长L1和L2的吞吐率曲线交点处的标签的数目,即为调整帧长的临界点.

(13)

(14)

其中⎣*」表示向下取整运算,从而得到了标签数目n和帧长L的对应关系,如表1所示.由标签数目的取值范围决定帧长的大小,当标签数目大于354时,仍以最大帧长256分别进行识别.

表1　帧长与标签数目对应关系

2.4标签分组原理

由于受到标签成本的限制,使得帧时隙数不能够随着标签数目的增加而无限地增加,所以针对于大量的标签的情况,只有通过限制每次响应的标签的数目,才能使系统保持相对较高的吞吐率.根据式(8),选取对标签进行分组的临界值[29],即两相邻帧的性能曲线交点Pa=Pb处的标签数值.

(15)

其中,a,b为标签的相邻分组数,例如当取a=1,b=2代入式(15)可得:

(16)

(17)

即n=354是将标签分为一组或两组的临界值,为了使系统保持较高的吞吐率效率,未识别标签数n不能大于354,当n大于354时,需要对未识别的标签进行分组.由式(15)可计算得到标签数量在2283以内的分组数,如表2所示.

表2　标签总数与分组数的对应关系

表2中的分组数1,2,4,6,8是自主设计的,各组中的最小标签数与最大标签数是式(15)中通过a,b数值计算出来的门限值.随着标签数目的增加,分组数也不断增大.

2.5分组自适应时隙分配算法

2.5.1GAAS算法约定

(1)Query(M)命令是碰撞时隙扫描的命令,其中的参数M是帧的时隙数.标签在这M个时隙中随机选取一个时隙,并加载到计数器中,同时向阅读器返回预约时隙数k,然后根据所选择的时隙进行相应的延时.

(2)Refresh-slot(Slots)命令,该命令是阅读器根据在碰撞时隙扫描的过程中,将时隙的选择情况发送给每一个标签,其中,Slots是一个数组.如果时隙能够完整读取就标记为0,反之则记为-1.标签接收到该命令之后,再进行时隙调整.

(3)Collection()命令,该命令是读取标签信息的命令.标签接收到这个命令之后,会根据上一个命令中更新的时隙,延迟响应时间,最后再将自身的数据发送至阅读器.

(4)Count()命令,该命令的作用是让标签时隙计数器减1,计数器为0的标签响应阅读器.

(5)S1eep()命令,该命令的作用是让标签暂时处于静默状态,使其不参与后面的查询.

2.5.2GAAS防碰撞协议

GAAS算法的核心就是在进行标签识别之前,首先进行时隙扫描操作,记录下标签所预约时隙的情况,然后在标签识别阶段,让阅读器跳过碰撞时隙和空闲时隙,而直接分配有效时隙,对成功预约的标签直接进行识别,从而提高了时隙的利用率.其协议流程如图2所示,协议过程可分为三个阶段:

(1)标签数目估计及分组阶段

①在识别开始阶段,用Vogt算法估计待识别标签的数目n.

②当标签数目小于354个时,采用动态帧时隙策略,动态调整识别帧的长度M,直接进入时隙处理阶段.当n大于354时,则需要对标签进行分组,由表2求得分组数g.

③标签在1到g之间随机选择一个数i,作为自己的组编号,同时把s[t]的值增加1,记录该组的标签数.

④初始化当前识别的组编号t=1,开始对第t组进行识别.

(2)时隙处理阶段

①在进行数据读取之前,首先进行时隙扫描,阅读器以广播的形式发送Query(M)命令给每个标签.标签收到该命令之后,再向阅读器返回各自所预约的时隙数.

②阅读器再根据所接收到的数据信息,来判断哪些时隙可以成功识别,哪些时隙将会产生碰撞或空闲时隙.如果能成功识别标签,就将相应的时隙标志位Flag设为0,其他情况就将Flag设为-1.

③阅读器根据标签所预约时隙的情况,将其通过命令Refresh-slot(Slots)发送给每个标签,让标签也能够知道其他标签选择时隙的情况,然后调整相应的时隙.Slots里面的元素就是在前面的时隙扫描过程中记录下的标记值,标签根据这个数组来调整相应所选择的时隙数.

(3)标签识别阶段

①由于阅读器在上一个阶段已经知道了各时隙的选择情况,在识别阶段直接分配有效时隙.接下来阅读器发送Collection()命令,标签接收到这个命令之后,就按照调整后的时隙依次向阅读器发送数据.

②阅读器发送Count()命令,让该组中各个标签的时隙计数器减1.

③最后阅读器发送S1eep()命令,在这一轮查询过程中被正确读取到的标签就会进入静默状态,即不参与接下来的查询.

④在每一轮识别结束以后,再估算剩余未识别标签的数目,若标签数目不为0,则重复上面②,③两个阶段,直至将该组剩下的标签全部识别完.

⑤组编号加1,即t=t+1,然后执行下述两种情况之一.

(a)如果t≤g,则表示存在没有识别的组,继续进行下一组的识别.

(b)如果t>g,即所有的组都识别完成,识别结束.

3　算法对比分析

3.1DFSA算法分析

动态帧时隙DFSA算法会根据前一帧的情况,估算出标签的数量,动态的调整帧的长度,这相对于FSA算法提高了效率.图3为DFSA算法的示意图,假设有8个标签,帧长为8,即每帧中含有8个时隙,各标签在每帧中随机选取一个时隙发送信息.DFSA算法的识别过程是:首先由阅读器向周围标签广播发送一个命令,通知标签该帧包含有8个时隙,然后标签从1～8时隙中随机选择一个作为自己的发送时隙,如果所选时隙上没有产生碰撞,则标签就会成功识别,接着退出系统.否则,阅读器将通知剩下未识别标签,在下一轮识别中重新选择发送时隙,直到所有的标签均被正确识别.

这种算法虽然简单,但是在其识别过程中会产生过多的碰撞时隙或空闲时隙,进而导致系统吞吐率不高.

3.2GAAS算法分析

仍以上面的例子,我们以GAAS算法进行分析.首先进行时隙扫描,阅读器以广播的形式发送Query(8)命令给每个标签,每个标签就从8个时隙中随机选择一个作为自己的时隙,并按照所选时隙进行相应的延时,然后向阅读器返回一个时长非常短的预约帧.由于受到标签成本的限制,所预约的时隙数不会超过256个,即8bit,为了尽量避免预约帧产生碰撞,后面的协议都将预约帧规定为16bit,即2个字节,按照IS018000-6协议规定,数据速率为40Kbps,每个普通数据帧为16个字节,可知发送预约帧只需1/8个时隙,所以发送预约帧非常快.假设有8个标签,帧长为8,即M=8.如表3所示,其中φ表示没有标签.

表3　时隙扫描过程中时隙的选择情况

然后阅读器发送Refresh-slot(Slots)命令,其中数组Slots为[-1,0,0,-1,-1,0,-1,-1],标签就会根据这个数组来调整将要发送数据的时隙.例如标签1,7开始所预约的时隙为1,但是该时隙上产生了碰撞,故将时隙数调整为0,所以标签1,7就不再参加后面的查询过程.标签2开始所选时隙为2,则根据数组的前2个数值来调整,即2-1=1,所以标签2将在时隙1中上传数据.同理,可以求得其他标签最终所选择的时隙,并且将进行相应的延时.标签调整之后的时隙数如表4所示.

接下来阅读器发送Collection()命令,标签接收到这个命令之后,就会按照调整后的时隙依次发送数据.只有标签2,3和6号标签选择了有效时隙,分别为新时隙1,2,3.如图4所示.阅读器跳过了碰撞时隙以及空闲时隙,自适应地分配有效时隙,因此就提高了信道的利用率.假设每个时隙为5ms,可以看到在这一轮查询过程中总的时间消耗为8个预约帧为5ms,然后是15ms的读取时隙,所以一共消耗了20ms.相对于前面DFSA算法而言,减少了20ms的时间,当标签的数目增加,帧长值更大时,该算法将会节省更多的时隙.

表4　调整后的时隙选择情况

以上仅是一个简单的范例.由2.5.2节可知整个算法可分为三个阶段:标签数目估计及分组阶段,时隙处理阶段和标签识别阶段.由于第一阶段所消耗的时隙很少,所以本文主要讨论后面两个阶段.

阅读器首先根据在其作用范围内标签的数目分配一定数量的时隙(如表5所示,与识别帧的长度有关),以便获得标签预约时隙的情况,然后再根据协议,让标签重新调整时隙,进入标签识别阶段.阅读器再根据标签成功预约的数目,自适应地分配相应数量的时隙,最后将此次成功预约的标签全部识别出来.

表5　标签数与时隙预测阶段消耗的时隙数对应关系

从图5可知,当标签数目不断增大时,系统的性能急剧下降,因此需要对其进行分组.但是,分组越多,其消耗的时隙会相应的增加,调整时隙的时间也会越长.当标签的数目在0～600之间时,分四组反而会降低系统的性能.所以GAAS算法采取自适应分组的方法,根据标签的数目自主进行分组.该策略能够解决标签数目较大而致识别效率过低的问题,同时也能使系统性能保持相对稳定,减少了标签的识别时间.

4　算法性能分析

为了从实验角度证实GAAS算法的有效性,在Windows7操作系统,2G内存的环境下,利用仿真软件MATLAB分别对FSA-256算法、DFSA算法、EPC标准算法、GDFSA算法以及GAAS算法进行仿真.假设系统的标签分布是均匀的,标签个数取1500以上,为了与分析相对应,仿真的结果是取相同条件下100次实验的平均值.

4.1标签电路复杂度分析

假设标签随机选取时隙的随机数为R,则需⎣log2R」位随机数,由于本算法采取分组的方法,R最大值设为256,仅需8位即可,所以标签只需8位随机数产生电路.而EPC C1G2防碰撞协议除了产生选取时隙的随机数需4位外,还要求生成16位RN16随机数,一共需要16+4=20位随机数产生电路.因此,本算法对标签设计随机数电路复杂性明显低于EPC C1G2标签.此外,标签中还有基于状态机的控制器来执行命,EPC C1G2标签需执行主要命令有5个(Query,QueryAdjust,QueryRep,Ack,RN16),本文协议中标签也需执行5个(Query,Refresh-slot,Count,Collection,Sleep),故GAAS协议标签的控制器电路复杂性也与EPC C1G2协议相当.综上所述,GAAS协议标签电路设计比EPC C1G2协议简单,从而降低了标签的成本.

4.2传输开销分析

传输开销是评估一个算法的重要指标,其包括阅读器开销和标签开销两部分.分别对AAS算法、GAAS算法以及EPC标准中的算法在标签识别过程中的传输开销进行仿真,仿真中用到的GAAS命令和参数长度如表6所示.

4.2.1阅读器的开销

设标签数量在区间[0,2000]内变化,读写器传输的比特数如图6所示,随着标签数目的增加,阅读器的开销也不断增大.当标签的数目少于1300时,AAS算法与GAAS算法阅读器开销相当,而当标签的数目超过1300时,GAAS算法的优势开始凸显出来.这是因为AAS算法没有将标签进行分组处理,随着标签数目的增加,标签碰撞的概率急剧上升,阅读器发送的指令也会随之增加.当标签数目为2000时,AAS算法中读写器比特数为66790,EPC标准算法分别为60527,而GAAS算法为54245,比AAS算法的开销下降了18.8%,比ECP标准算法下降了10.4%.

表6　GAAS算法中涉及的命令和参数长度

4.2.2标签的开销

图7显示了三种算法标签的开销,随着标签数目的增加,AAS算法中标签传送比特数接近指数增长,而GAAS算法和EPC标准算法近似线性增长,其中GAAS增长最为缓慢.当标签的数目为2000时,AAS算法中读写器比特数为422135,EPC标准算法分别为121545,而GAAS算法仅为39601,比AAS算法标签的开销下降了96.1%,比ECP标准算法下降了67.4%.

4.3总时隙数分析

总时隙是决定系统效率的一个关键因素,总时隙数越少,系统的性能越好.从上面分析可知,整个算法分为两个阶段:时隙扫描阶段和标签识别阶段,所以查询总时隙也是这两个阶段消耗时隙之和.

对FSA-256算法、DFSA算法、GDFSA算法以及GAAS算法的总时隙数进行仿真,仿真结果如图8所示.标签数量从0变化到1500的过程中,FSA-256算法和DFSA算法所需要的总时隙数随标签数量的增加呈指数增长,GDFSA算法和GAAS算法呈线性增长,其中FSA-256算法增长速度最快,而GAAS算法最慢,其次是GDFSA算法.特别是当标签数目较大时,GAAS算法的优势更加明显.当标签数目为1000时,GAAS算法只需要约1400个时隙,比FSA-256减少约4165,比DFSA减少约3727,比GDFS减少约1366.

4.4吞吐率分析

系统吞吐率也是衡量系统性能的一个重要指标.从图9可以看出,当标签少于354时,GDFSA与DFSA吞吐率相同,FSA-256算法最低,仅有0.2左右,而GAAS算法最高,可达0.7以上.GDFSA、DFSA、GAAS算法都能根据实际标签数目,自适应地分配有效时隙进行识别,而FSA-256算法采用固定帧长256.当标签数大于354时,FSA-256、DFSA算法的吞吐率均急剧下降,而GDFSA、GAAS算法则将标签分为多组,通过动态调整帧长对各组标签进行识别,使得吞吐率稳定在一定范围内.本文算法的系统吞吐率比其他三种算法显然要大得多,FSA-256算法的吞吐率在0.1～0.25之间,DFSA算法则在0.2～0.36之间,GDFSA算法仅维持在0.36左右,而GAAS算法比它们都要高.当标签的数目达到1000时,与FSA-256和GDFSA相比,GAAS算法的系统效率分别提高了300%和97.2%.

5　结论

本文提出了一种分组自适应分配时隙RFID防碰撞(GAAS)算法,通过对标签数量的估计和分组、时隙预约以及自适应分配时隙等策略对标签进行快速识别.仿真结果表明,随着标签数量的不断增加,特别是当标签的数目超过1000时,GAAS算法的吞吐率维持在0.71以上,比基于ALOHA的传统算法的吞吐率都较大幅度的提高,整个识别过程所需要的时隙总数和传输开销几乎保持了线性增加.能有效地提高RFID系统的工作效率,增加了系统吞吐率的稳定性,降低了标签的成本.针对于大量的标签的识别,GAAS算法的优势尤为显著,具有广阔的应用前景.

[1]Want R.An introduction to RFID technology[J].IEEE Pervasive Computing,2006,5(1):25-33.

[2]宁焕生,张瑜,刘芳丽,等.中国物联网信息服务系统研究[J].电子学报,2006,34(12A):2514-2517.NING H S,ZHANG Y,LIU F L,et al.Research onchina internet of things’ services and management[J].Acta Electronica Sinica,2006,34(12A):2514-2517.(in Chinese)

[3]Hunt V D,Puglia A,Puglia M.RFID:A Guide to Radio Frequency Identification[M].New Jersey:John Wiley & Sons,2007.

[4]Yoon W,Vaidya N H.RFID reader collision problem:performance analysis and medium access[J].Wireless Communications andMobile Computing,2012,12(5):420-430.

[5]李萌,钱志鸿,张旭,等.基于时隙预测的RFID防碰撞ALOHA算法[J].通信学报,2012,32(12):43-50.

Li Meng,Qian Zhi-hong,Zhang Xu,et al.Slot-predicting based ALOHA algorithm for RFID anti-collision[J].Journal on Communications,2012,32(12):43-50.(in Chinese)

[6]Wu H,Zeng Y.Bayesian tag estimate and optimal frame length for anti-collision ALOHA RFID system[J].IEEE Transactions on Automation Science and Engineering,2010,7(4):963-969.

[7]Deng D J,Tsao H W.Optimal dynamic framed slotted ALOHA based anti-collision algorithm for RFID systems[J].Wireless Personal Communications,2011,59(1):109-122.

[8]Küpper A.Front Matter[M].New Jersey:John Wiley & Sons,Ltd,2005.

[9]Finkenzeller K.Example Applications[M].New Jersey:John Wiley & Sons,Ltd,2003.

[10]Crain T,Gramoli V,Raynal M.A speculation-friendly binary search tree[J].Acm Sigplan Notices,2012,47(8):161-170.

[11]王亚奇,蒋国平.基于分组机制的跳跃式动态二进制防碰撞算法[J].自动化学报,2010,36(10):1390-1400.

Wang Ya-qi,Jiang Guo-ping.Anti-collisionalgorithm based on grouping mechanism and jumping dynamic binary[J].Acta Automatica Sinica,2010,36(10):1390-1400.(in Chinese)

[12]Yang C N,He J Y.An effective 16-bit random number aided query tree algorithm for RFID tag anti-collision[J].IEEE Communications Letters,2011,15(5):539-541.

[13]Liva G.Graph-based analysis and optimization of contention resolution diversity slotted ALOHA[J].IEEE Transactions on Communications,2011,59(2):477-487.

[14]Wu H,Zeng Y.Efficient framed slotted ALOHA protocol for RFID tag anti-collision[J].IEEE Transactions on Automation Science and Engineering,2011,8(3):581-588.

[15]Deng D J,Tsao H W.Optimaldynamic framed slotted ALOHA based anti-collision algorithm for RFID systems[J].Wireless Personal Communications,2011,59(1):109-122.

[16]Chien H Y,Chen C H.Mutual authentication protocol for RFID conforming to EPC Class-1 Generation-2 standards[J].Computer Standards & Interfaces,2007,29(2):254-259.

[17]Chen W T.Afeasible and easy-to-implement anti-collision algorithm for the EPC global UHF Class-1 Generation-2 RFID protocol[J].IEEE Transactions on Automation Science and Engineering,2014,11(2):485-491.

[18]张小红,张留洋.RFID防碰撞时隙应变协处理算法研究[J].电子学报,2013,42(6):1139-1146.

ZHANG Xiao-hong,ZHANG Liu-yang.Research on RFID anti-collision algorithm of slot responding in real-time and co-processing[J].Acta Electronica Sinica,2013,42(6):1139-1146.(in Chinese)

[19]龚冰青.一种433MHz有源RFID标签的设计与实现[D].成都:电子科技大学,2013.Gong Bing-qing.Desing and implementation of active RFID tag with 433MHZ[D].Chengdu:University of Electronic Science and Technology of China,2013.(in Chinese)

[20]Wang C Y,Lee C C,Lee M C.An enhanced dynamic framed slotted ALOHA anti-collision method for mobile RFID tag identification[J].Journal of Convergence Information Technology,2011,6(4):340-351.

[21]Lin C F,Lin F Y S.Efficient estimation and collision-group-based anti-collision algorithms for dynamic frame-slotted ALOHA in RFID networks[J].IEEE Transactions on Automation Science and Engineering,2010,7(4):840-848.

[22]Park J,Chung M Y,Lee T J.Identification of RFID tags in framed-slotted ALOHA with robust estimation and binary selection[J].IEEE Communications Letters,2007,11(5):452-454.

[23]庞宇,彭琦,林金朝,等.基于分组动态帧时隙的射频识别防碰撞算法[J].物理学报,2013,62(14):148401-148401.Pang Yu,Peng Qi,Lin Jin-zhao,et al.Reducing tag collision in radio frequency identification systems by using a grouped dynamic frame slotted ALOHA algorithm[J].Acta Phys Sin,2013,62(14):148401-148401.(in Chinese)

[24]吴海锋,曾玉.RFID 动态帧时隙 ALOHA 防冲突中的标签估计和帧长确定[J].自动化学报,2010,36(4):620-624.Wu Hai-feng,Zeng Yu.Tagestimate and fame length for dynamic frame slotted ALOHA anti-collision RFID system[J].Acta Automatica Sinica,2010,36(4):620-624.(in Chinese)

[25]Eom J B,Lee T J.Accurate tag estimation for dynamic framed-slotted ALOHA in RFID systems[J].IEEE Communications Letters,2010,14(1):60-62.

[26]Schoute F C.Dynamic frame length ALOHA[J].IEEE Transactions on Communications,1983,31(4):565-568.

[27]Chen W T.An accurate tag estimate method for improving the performance of an RFID anti-collision algorithm based on dynamic frame length ALOHA[J].IEEE Transactions on Automation Science and Engineering,2009,6(1):9-15.

[28]Cha J R,Kim J H.Novel anti-collision algorithms for fast object identification in RFID system[A].Proceedings ofthe 2005 Eleventh International Conference on Parallel and Distributed Systems[C].Fukuoka:IEEE,2005.63-67.

[29]Lee S R,Joo S D,Lee C W.An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification[A].Proceedings ofthe Second Annual International Conference on Mobile and Ubiquitous Systems:Networking and Services[C].California:IEEE,2005.166-172.

张小红女,1966年8月出生,河北昌黎人,现为江西理工大学信息工程学院教授、博士、硕士生导师,研究方向:无线传感器网络、非线性动力学理论、混沌保密通信.

E-mail:xiaohongzh@263.net

胡应梦男,1989年11月出生,湖南娄底人,现为江西理工大学信息工程学院硕士研究生,研究方向:RFID防碰撞算法、可信认证协议.

E-mail:huyingmeng89@163.com

Research on a Grouped Adaptive Allocating Slot Anti-collision Algorithm in RFID System

ZHANG Xiao-hong,HU Ying-meng

(SchoolofInformationEngineering,JiangxiUniversityofScienceandTechnology,Ganzhou,Jiangxi341000,China)

Based on frame slotted ALOHA algorithm, a grouped adaptive allocating slots (GAAS) anti-collision algorithm is presented to solve the problem of collision between the reader and multi-tag in radio frequency identification(RFID) system. First, the reader needs to obtain the time slots chosen randomly by tags and send the results to each tag; then the tags rectify the time according to the instruction; moreover, the reader skips free and collision time slots, and adaptively distributes valid ones; finally, the tags are quickly recognized in GAAS. When the number of unidentified tags is very large, the tags are grouped and the frame sizes are adjusted dynamically to reduce the processing time. The simulation results show that GAAS has higher identification efficiency and stability, and lower cost of communication. Particularly, when the number of tags is over 1000，the throughput rate still maintains above 71%. Compared with the framed slotted ALOHA-256 algorithm and the grouped dynamic framed slotted ALOHA algorithm, the proposed algorithm enhances the system efficiency by 300% and 97.2% respectively.

RFID;ALOHA algorithm;tags grouping;throughput rate;adaptively allocating slots

2014-09-08;修回日期:2014-12-01;责任编辑:梅志强

国家自然科学基金(No.61363076,11062002);江西省自然科学基金(No.20142BAB207020);江西省教育厅科技项目(No.GJJ14465);江西省研究生创新专项资金(No.YC2014-S370)

TN911.23

A

0372-2112 (2016)06-1328-08