《电子技术应用》
您所在的位置:首页 > 通信与网络 > 设计应用 > RFID防碰撞算法研究
RFID防碰撞算法研究
来源:微型机与应用2011年第10期
王 珏,刘 陈
(南京邮电大学,江苏 南京210003)
摘要: 在分析了目前现有的时隙ALOHA算法和查询树QT算法后,结合这两类算法的优点,提出了一种混合型算法GFA-QT来解决RFID中的碰撞问题。理论与仿真表明,这种混合型的算法在系统效率上优于现有的算法。
Abstract:
Key words :

摘  要: 在分析了目前现有的时隙ALOHA算法和查询树QT算法后,结合这两类算法的优点,提出了一种混合型算法GFA-QT来解决RFID中的碰撞问题。理论与仿真表明,这种混合型的算法在系统效率上优于现有的算法。
关键词: 射频识别防碰撞;GFA-QT;吞吐量

    射频识别系统(RFID)是一种利用无线传输实现物体的非接触式识别的技术。自20世纪90年代兴起以来,该技术凭借数据存储量大、识别时间短、保密性好等优点在货物销售、物流仓储、安保及交通管理等众多领域得到广泛的应用[1]。RFID系统主要由阅读器Reader和标签Tag组成,阅读器通过发射天线发送一定频率的射频信号,当标签进入发射天线工作区域时将产生感应电流,获得能量从而被激活,并将自身的信息通过内置的天线发送出去,阅读器接收到从标签发来的载波信号后,对接收的信号进行解调和解码,并将标签编码等信息通过接口与上位控制计算机进行数据交换同时执行应用软件发来的命令,实现不同的应用功能[2]。
    作为一种无线通信技术,RFID同样不可避免地面临着多址接入的问题。在RFID系统中,阅读器与其工作域内的标签之间通过共享的无线信道进行通信,当多个标签同时与阅读器通信时,信号就会在共享的信道中产生碰撞,进而导致阅读器无法识别任何标签信息,这就是标签碰撞问题。
    目前解决RFID防碰撞问题的算法主要分为基于时隙ALOHA的随机型防碰撞算法和基于二进制树的确定型防碰撞算法,本文在分析这两种主流算法之后提出了一种混合型算法GFA-QT,该算法结合了时隙ALOHA和二进制树算法的优点。
1 RFID标签防碰撞技术
    多标签防碰撞问题的实质是多址接入问题,其解决方案主要可分为四类:空分多址(SDMA)、频分多址(FDMA)、时分多址(TDMA)和码分多址(CDMA)。基于SDMA、FDMA、CDMA的标签防碰撞算法理论上可以解决部分有源的标签防碰撞问题,但是目前大多数使用的是无源标签,受其功率的限制,采用上述方案会使得标签和阅读器的设计复杂、系统成本高,所以RFID防碰撞算法中更多采用的是基于TDMA思想的防碰撞算法。目前基于TDMA思想的防碰撞算法主要分为两大类:基于时隙ALOHA的随机接入型算法和基于二进制树的确定性算法。
1.1 时隙ALOHA算法
    时隙ALOHA算法中阅读器将一帧划分为多个时隙,在所有标签和阅读器取得同步基础上,规定标签仅能在每个时隙开始时才能发送数据。其算法的基本流程如下:(1)当阅读器向标签发送请求命令时会同步向所有标签广播时隙个数L(即帧长)。(2)标签会在帧长范围内随机地选择一个时隙响应阅读器的命令并发送自身的信息,若一个时隙中只有一个标签返回信息则称为成功时隙,没有标签返回信息称为空时隙,有2个或者更多的标签返回信息称为碰撞时隙,记一帧中空时隙数为C0,成功时隙数为C1,碰撞时隙数为Ck。发生碰撞的相关标签会在下一帧继续向阅读器发送数据。(3)算法根据前一帧的反馈值C0、C1、Ck采用标签估算方法来估算阅读器范围内未读标签数量,并根据此调整下一帧时隙数,得到一个使系统识别效率最高的时隙数L′。(4)读写器向标签广播新的时隙数,直至所有标签被识别完。

    通过仿真得到第4种标签估算模型准确度最高,系统的识别效率达到最大。
1.2 二进制树算法
    基于树结构的确定性算法是实现标签防碰撞算法的另一种解决思路,它是将阅读器工作区域内的标签不断地划分为p个子集(p>1),再对某个子集进行同样的划分,这样所划分子集内的标签数量越来越少,直至某子集内的标签数目为1,实现阅读器成功识别标签。当某个子集内的标签读取完毕,阅读器采用回溯的方式处理其他等待读取的标签。这样就可以将标签的分组过程看做是全部标签根据分组方案从根节点向叶节点逐层分流的过程,只有叶节点的标签能被成功读取。
    查询树QT[7](Query Tree)是一种典型的树结构算法,其算法原理:读写器发送长度为k的prefix;标签ID中前k bit与prefix匹配的tag反馈第(k+1)bit至最后1 bit。如果阅读器收到的标签ID碰撞,再分别将prefix加“1”和“0”,作为新的prefix发送出去。如果没有碰撞,就表明一个标签被识别了。
    图1给出了QT算法的实例,设标签的三个ID分别为“010”“011”“100”,阅读器的查询序列首先置为“0”、“1”,阅读器先发送序列“0”进行查询,发生碰撞,此时将序列置为“00”、“01”,再次分别发送,序列“00”没有响应,序列“01”发生碰撞,将序列置为“010”、“011”,成功识别。回溯到序列“1”,只有标签“100”响应,成功识别。

 

 

2 GFA-QT算法
    在上节介绍的时隙ALOHA算法中,系统实现起来较为容易,但是由于是随机接入的,所以在一定时间范围内可能会发生某个标签没有被读取(即标签“饿死”)的情形。而二进制树算法中每个标签会被成功识别,但是识别时延较长。本节将介绍一种混合的防碰撞算法GFA-QT,它将ALOHA算法和QT算法的优点结合起来,首先利用时隙ALOHA算法对标签数量进行估计,然后对标签进行分组,最后利用QT算法分别读取每一组标签。这种解决标签防碰撞算法称为GFA-QT(Grouping Framed Aloha with Query Tree)基于分组时隙ALOHA的查询树算法。
2.1 分组的概念
    在时隙ALOHA算法中,每个标签随机选择一个时隙向阅读器发送自身信息,当标签数量等于时隙数时,系统效率达到最高36.8%。但是事实上时隙数有限,而标签数可能远大于时隙数,所以对标签如何分组就显得尤为重要。由于阅读器在识别过程开始之前并不知晓其阅读范围内的剩余标签数量,在1.1节中对几种标签估算方法进行了比较,得到第4种数学模型计算的剩余标签数量最为准确。
    在QT算法中,当树的深度为2时该算法的性能最佳,因为阅读器发出查询序列“0”、“1”时恰好分别有一个标签响应。设标签数量为N,时隙数为L,则最佳时隙数满足N=2×L,即每个时隙内仅有两个标签。但是这样时隙数会过大,系统无法实现。通过仿真得到当时隙数为4,且每个时隙内标签数量也为4时,系统效率达到最大。
2.2 算法描述
    GFA-QT算法过程包括两个阶段:标签分组阶段和标签识别[8-9]阶段。算法的步骤如下:
    (1)预处理:首先将所有待识别的标签视为一组,阅读器设置时隙数为L=4,标签成功分组所需循环次数为I(I初始值为1),标签分裂系数M=4,标签分裂门限值pth=8,标签分组数为S;
    (2)阅读器向所有标签发送包含帧长的Probe命令,将时隙数L告知标签;
    (3)标签从1~L中随机选择一个时隙对阅读器做出反应,阅读器检测出一帧中没有标签响应的时隙数C0,只有一个标签响应的时隙数C1和有两个或者两个以上标签响应的时隙数Ck;
    (4)根据剩余标签估算模型4计算得出所有等待识别的标签数量Nleft,将Nleft与标签分裂门限值pth比较。若Nleft<pth,则分组结束;若Nleft>pth,则I=I+1,S=MI-1,利用分组函数将所有标签分为S组;
    (5)由于标签分组的随机性,在S组标签中任选一组标签重复步骤(2)~(4),直至该组标签数满足Nleft<pth。最终得到标签数组数S=MI-1,标签组数为[group1,…,groups];
    (6)利用QT算法分别读取[group1,…,groups],返回所有成功识别的标签。
3 计算机仿真及结果分析
    系统效率是衡量RFID防碰撞算法性能的重要指标,本文使用MATLAB对提出的GFA-QT防碰撞算法进行仿真,仿真了在不同的标签数量、不同的时隙数下GFA-QT的系统效率,并与时隙ALOHA算法中的DFSA(Dynamic Framed Slotted ALOHA)算法和二进制查询树QT算法的系统效率进行了比较。
3.1 仿真条件
    电子标签的ID码为64 bit,随机生成。在仿真时不考虑标签的运动、传输误码等因素。所有算法的指令头、尾以及链路时序符合ISO/IEC 18000-6C协议规范。在GFA-QT算法中,设置初始时隙数为4,分组数为1。
3.2 仿真结果
    本节首先研究了在不同的标签数量下,GFA-QT、DFSA、QT算法系统效率之间的差异。设标签数量从100逐步增加到2 000。仿真结果如图2所示。

    在该仿真中看出当标签数量较小时,GFA-QT算法的系统效率低于DFSA、QT算法的系统效率,这是因为标签数量小,分组优势不明显。当标签数增加时,GFA-QT算法的系统效率优于其他两种算法并且趋于稳定,说明该算法受标签数量影响不大。
    在图3中,探讨了不同时隙数对GFA-QT算法系统效率的影响,从仿真结果来看,当时隙数为4时算法的系统效率高于时隙数分别为2、8、16时的系统效率。这主要是因为当时隙数为8或者16时,造成时隙数过大,识别时延增加,当时隙数为2时,容易造成标签分布于各个时隙不均匀,使得阅读器无法达到最大识别效率。

    本文提出了一种基于时隙ALOHA算法和二进制查询树QT算法的混合型算法GFA-QT,用于RFID系统的防碰撞功能的实现,该算法的系统效率高于现有的算法。仿真结果表明,新的混合型算法将RFID系统识别效率提高至37.2%左右,高于DFSA算法和QT算法。
参考文献
[1] RAZA N, BRADSHAW V, HAGUE M.Applications of RFID technology[C]. IEEE Colloquium on RFID Technology,  London, England, 1999,10: 1/1-1/5.
[2] FLOR T, NIESS W, VOGLER G.RFID: the integration of  contactless identification technology and mobile computing[J]. Proc. of the 7th Int’l Conf. on Telecomm, Zagerb, Croatia, 2003,2(26): 619-623.
[3] CHA J R, KIM J H. Novel anti-collision algorithm for  fast objection identification in RFID systems[EB/OL]. http://ieeexplore.ieee.org/ie15/10248/32568/01524254.pdf, 2005.
[4] VOGT H.Efficient object identification with passive RFID tags[C].in IEEE PerCom, (TX,USA), 2002.
[5] CHA J R,KIM J H.Novel anti-collision algorithms for fast object identification in RFID system[C].The 11thIntl. Conference on Parallel and Distributed Systems,Korea, 2005:63-75.
[6] ZHEN B, KOBAYASHI M,SHIMIZU M.Framed aloha for  multiple RFID objects identification[C].IEICE Transactions  on Communications, 2005,E88-B:991-999.
[7] LAW C, LEE K,SIU K.Efficient memorials protocol for tag  identification[C].4th International Workshop on Discrete  Algorithms and Methods for Mobile Computing and Communications, 2000,ACM:75-84.
[8] SHIN J D, YEO S S, KIM T H,et al.Hybrid tag anticollision algorithms in RFID systems[C]. UK: Springer Berlin /Heidelberg,2007.
[9] CHOI S Y, LEE J, KIM S H,et al.Hybrid anti-collision method based on maximum throughput for RFID system[J]. Electronics Letters,2010,46(19).

此内容为AET网站原创,未经授权禁止转载。