基于ＲＦＩＤ无线通信系统的防碰撞算法设计与研究

桂卫华　肖又正

[摘要]针对动态帧时隙ALOHA算法(DFSA)不适用于有大量标签的情况,参考Binary Tree算法,提出一种新的解决方案,先将标签分组,使每组只含有少量标签,然后针对每组标签再分别采用DFSA算法进行读取,这样就可以解决DFSA算法读取大量标签的问题。并对其进行仿真试验,经过仿真验证,该算法在保证正确选择分组数的条件下,比DFSA算法有所改进,能够提高读卡器的读取效率。

[关键词]射频识别 防碰撞算法 RFID系统 ALOHA算法

中图分类号:TN92文献标识码:A文章编号:1671-7597(2009)0920049-02

一、引言

射频识别技术(Radio Frequency Identification,RFID)是一种非接触式的自动识别技术[1]。一般由阅读器(Reader)和电子标签(Tag)两部分构成。对于一个RFID系统,同一时间可能有多个电子标签进入射频区,在与读写器进行通讯时将产生通常所说的碰撞。防碰撞研究主要解决如何快速和准确地从多个电子标签中选出一个与阅读器进行数据交流,而其他未被选中的标签则在此后的防碰撞循环中被选出与阅读器通讯[2]。现有的解决此问题的方法有二进制搜索算法、ALOHA算法、Q-选择算法等[3]。其中二进制搜索算法经部分学者改进后产生了返回式二进制树型搜索算法,并在较大程度上改进了算法的性能,但二进制算法并不适用于标签内EPC位数较多的情况[4]。Q-选择算法是由EPCglobal制定的最新的RFID通信标准,它不受标签EPC位数的影响。对本标准的研究,业界还处于起步阶段[5]。

ALOHA算法基于TDMA思想,是一种概率算法,属于电子标签控制算法。当电子标签进入读写器的作用范围内,就自动向阅读器发送自身的序列号,随即与阅读器开始通信。在一个电子标签向读写器发送信息的过程中,如果另外一个电子标签也在发送数据,就会产生信息碰撞。ALOHA算法分为纯ALOHA算法、时隙ALOHA算法、帧时隙ALOHA算法和动态帧时隙ALOHA算法(DFSA)[6]。由于DFSA算法实现起来比较简单,因此目前大量产品都采用DFSA的算法,但是DFSA不适用于有大量标签的情况[7],为了解决这一问题,本文参考Binary Tree算法,提出一种新的解决方案,先将标签分组,使每组只含有少量标签,然后针对每组标签再分别采用DFSA算法进行读取,这样就可以解决DFSA算法读取大量标签的问题。并对其进行了仿真试验,经过仿真验证,该算法在保证正确选择分组数的条件下,比DFSA算法有所改进,能够提高读卡器的读取效率。

二、RFID简介

RFID是无线射频识别技术(Radio Frequency Identification)的简称,是一种从20世纪90年代兴起的,通过电磁感应或电磁传播方式,对目标进行非接触识别跟踪和双向数据通信的新型自动识别技术。相比于条码、磁条、磁卡、指纹、光学字符等自动识别技术,RFID具有可无线读/写、信号穿透能力强、识别距离远、使用寿命长、环境适应性好、可多标签同时识别、信息存储容量大和数据可改写等优点[8]。RFID在交通与配送管理、生产制造管理、资产管理、人员门禁与防伪等领域获得了越来越广泛的应用,其中尤以商品零售和物流管理领域为甚。2003年年底,全球最大的商品零售商沃尔玛宣布其将有计划地全面实施其RFID技术,从而在全球范围内进一步掀起了RFID热潮。

图1是RFID系统的主要组成框图,RFID系统主要包括读卡器(Reade动、标签(Tag)两部分[9]。读卡器通常包含一个射频收发模块,一个控制模块。另外,某些读卡器还包含其他数据接口系统(RS232,RS 485,以太网接口等),以便将数据转发到其他计算机系统。

电子标签是射频识别系统的核心,用于保存被标识物体的属性、状态、编号等信息。一般电子标签由标签天线和标签专用芯片(IC)组成,该标签芯片相当于一个片上系统soc(system on chip),具有能量接收、信息收发和存储功能。读卡器是用于阅读以及向标签写入数据的装置,一般读卡器是针对特定的电子标签而设计的,其主要功能是:查阅电子标签中当前贮存的数据信息;向电子标签中写入欲贮存的数据信息;修改电子标签中的数据信息。

三、防碰撞算法简述

(一)ALOHAT算法

ALOHA算法是最简单最基本的一种防碰撞算法,它是基于TDMA的思想,是一种基于概率的算法。该算法是指标签在进入读卡器的读取范田会随即向读卡器发送其消息,当读卡器准确分辨出唯一的标签时与该标签开始通信。采用ALOHA算法的基本思想是在标签发送数据的过程中,若有其他标签也在发送数据,那么发生信号重叠从而导致完全冲突或部分冲突。图2给出了Aloha算法标签发送数据部分冲突和完全冲突情况的示意图。读卡器检测接收到的信号来判断有无冲突。一旦发生冲突,读卡器就发送命令让标签停止发送,随机等待一段时间后再重新发送以减少冲突。纯ALOHA算法存在的一个严重问题是存在错误判决的问题,即对同一个标签,如果连续多次发生冲突,这将导致读卡器出现错误判断,认为这个标签不在自己的作用范围。纯Aloha存在的另一个问题是数据帧的发送过程中发生冲突的概率很大。

(二)时隙ALOHA算法

时隙ALOHA(Slotted Aloha)算法是ALOHA算法的改进算法。这种算法在ALOHA算法的基础上把时间分成多个离散时隙,并且每个时隙长度要大于标签回复的数据长度,标签只能在每个时隙内发送数据。每个时隙存在下面3种情况:

1.无标签响应:在此时隙内没有标签发送;

2.一个标签响应:在此时隙内只有一个标签发送,标签能够被正确识别;

3.多个标签响应:在此时隙内多个标签发送,产生冲突。

这样标签或成功发送或完全冲突,避免了原Aloha算法中的部分冲突,提高了信道的利用率。但是这种方法需要一个同步时钟以使读卡器阅读区域内的所有标签的时隙同步。

(三)FSA算法

ALOHA算法的另一种扩展算法是Framed Slotted Aloha算法,简称FSA算法。它是在时隙ALOHA算法的基础上把N个时隙组成一帧,标签在每个帧内随机选择一个时隙发送数据。这种算法适于传输信息量较大的场合,与时隙ALOHA算法相同,FSA算法也需要一个同步开销。一个帧包含多个时隙,N个时隙的长度要足够让一个标签回答完,其体时间山读卡器定义。在读卡器发送读取命令后,要等待一定时间等待标签的回答。在一个时隙中只有一个标签回答时,读卡器可以分辨出标签;在一个时隙中没有标签回答时,跳过此时隙:当在一个时隙中有多个标签回答时,发生冲突,需要重新开始读取过程。FSA算法存在一个缺点,当标签数量远大于时隙个数时,读取标签的时间将会大大增加,而在标签个数远小于时隙个数时,会造成时隙的浪费。

(四)一种改进的DFSA算法

由于DFSA算法实现起来比较简单,因此目前大量产品都采用DFSA的算法,但通过上面分析可知,DFSA不适用于有大量标签的情况,为了解决这一问题,本文参考Binary Tree算法,可以先将标签分组,使每组只含有少量标签,然后针对每组标签再分别采用DFSA算法进行读取,这样就可以解决DFSA算法读取大量标签的问题。具体实现过程为:

1.标签有一个随机数生成器,可生成0到N之间的随机数,这个随机数代表着分组的组数,在读卡器发送分组命令时,标签随机选择一个数字即选择一个组组内进行回答。

2.读卡器从第0组开始读取标签,在组内采用DFSA算法解决标签碰撞问题,当读取完该组内所有标签后,将组数加1,重复这一步骤。

根据表1我们可以看出,采用了分组的方法后,随着分组数目的增加所用的总时隙数不断减少,但是分组数过大时,所用时隙却有所增加,产生了大量的余,当分组后每组的标签数目在50左右的时候,所得的总体效果较好。实验表明本文算法在保证正确选择分组数的条件下,比DFSA算法有所改进,能够提高读卡器的读取效率。

四、结论

由于DFSA算法实现起来比较简单,因此目前大量产品都采用DFSA的算法,但是DFSA不适用于有大量标签的情况,为了解决这一问题,本文参考Binary Tree算法,提出一种新的解决方案,先将标签分组,使每组只含有少量标签,然后针对每组标签再分别采用DFSA算法进行读取,这样就可以解决DFSA算法读取大量标签的问题。并对其进行了仿真试验,经过仿真验证,该算法在保证正确选择分组数的条件下,比DFSA算法有所改进,能够提高读卡器的读取效率。

参考文献:

[1]Law C,Lee K,KaiYeung S.Eficient memoryless protocol for tag identification[C].Proceeding of ACM DI-ALM'00.2000:75-84.

[2]Sangjun Kim.Euiho Suh and Keedong Yoo.A study of context inference for Web based information systems.Electronic Commerce Research and Applications,In Press,Uncorrected Proof,Available online 21 December 2006.

[3]刘冬生、邹雪城、李泳生等,射频识别系统中的防碰撞算法[J].华中科技大学学报:自然科学版,2006,34(9):57-59.

[4]梁彪、胡爱群、秦中元,一种新的RFID防碰撞算法设计[J].电子与信息学报,2007,29(9):2158-2160.

[5]吕炳赟、潘剑侠、马琪等,RFID防碰撞算法的研究进展与应用[J].电讯技术,2008,48(7):124-128.

[6]丁治国、郭立、刘琦,一种基于搜索矩阵的自适应防碰撞算法[J].模式识别与人工智能,2008,21(4):476-481.

[7]刘佳、张有光,基于时隙的RFID防碰撞算法分析[J].电子技术应用,2007(5):94-100.

[8]李世煜、冯全源、鲁飞,基于BIBD(4,2,1)的RFID防碰撞算法[J].计算机工程,2009,35(3):279-281.

[9]彭木根、王文博、张倩倩,异构无线通信系统的协同分集性能研究[J].电子学报,2009,37(1):21-25.