基于EPC-C1G2标准的标签防碰撞算法

2011-07-09邹宽城吴海飞

长春工业大学学报 2011年3期

刘宣, 邹宽城, 吴海飞

(长春工业大学计算机科学与工程学院,吉林长春 130012)

0 引言

射频识别即RFID(Radio Frequency IDentification)技术是一种快速、安全且具有高效自动识别的技术,利用射频信号通过空间耦合(交变磁场或电磁场)实现无接触信息传递,并通过所传递的信息达到识别目的[1]。RFID技术最早应用于第二次世界大战期间,在20世纪80年代走向成熟,经过几十年的发展,RFID技术已在各行各业得到广泛应用。目前,它已经逐渐成为提高现代物流工作效率的技术工具和手段。现代物流充分运用信息技术,将运输、仓储、装卸、加工整理、配送等有机结合,形成完整的供应链,并越来越呈现出信息化、网络化、自动化、模块、标准化等发展趋势,其中信息化是现代物流的核心。在近几年物流业的快速发展中,现代物流已经采用了大量信息及自动化技术来提高效率,但有很多工作仍主要依靠人工来完成,例如数据录入、货物的清点和盘库等,而手持式条形码识别器等辅助工具对上述问题也不能根本有效解决。正是由于这种信息采集手段落后或工作效率的问题而造成信息采集和传输过程中的错误,从而影响了物流效率。无线射频识别技术(RFID)在数据采集、数据传递方面具有独到的优势。与条码技术相比,具有识别速度快,阅读距离远,使用寿命长,无需对准识别等诸多优点,并且可以实现多目标识别和运动目标识别。它作为信息传递的载体,可以有效避免人工输入可能出现的失误,大大提高入库、出库、验货、盘点、补货等工作效率,在物流供应链管理领域具有很大的应用潜力。推广RFID技术,让该技术尽快发挥其对物流行业强大推动作用,是国际物流企业技术应用的大趋势。

射频识别系统主要由电子标签和读写器两部分组成,电子标签是电子产品代码的载体,附着于需跟踪的物体上,读写器通过无线信道按照一定的协议读写标签。RFID系统工作时,经常有一个以上电子标签同时处于阅读器的作用范围内。当这些电子标签同时将自身携带的数据传送给读写器时,就会出现冲突,这将导致读写器不能正确读出数据,这就是标签的防冲突算法解决的问题。常用的防碰撞算法主要有基于二进制搜索的确定性算法[2]和基于时隙的随机标签防冲突算法ALOHA[3]。二进制搜索算法是以标签的唯一序列号为基础来实现防冲突的,采用Manchester编码准确地找到冲突位,然后强迫其中一方的标签暂时退出,以此类推,在判断完整个序列号之后,将得到唯一的序列号。随机性算法的特点是标签向读写器发送数据的时间是随机的,冲突发生后利用退避算法思想进行重发,目前各种随机性算法都是在ALOHA算法上发展起来。文中主要研究由EPC global组织制订的EPC-C1G2[4]标准的时隙随机算法防碰撞算法SR(Slot Random)[5],并在此算法基础上进行改进。

1 基于EPC-C1G2标准的时隙随机算法

基于EPC-C1G2的防碰撞算法是在动态帧时隙ALOHA(Dynamic Framed Slotted ALOHA,DFSA)算法基础上改进的时隙随机算法,该算法没有帧的概念,取而代之的是识别周期,即读写器两次发送Query指令的间隔。时隙随机算法同样需要标签随机选择响应时隙,区别在于,该算法可以在识别周期内的任何时刻更改时隙数,使未识别标签重新选择响应时隙,以实现识别时隙的自适应。

EPC-C1G2标签包含一个16 bit的随机数生成器和一个15 bit的时隙计数器。在识别标签的过程中,所涉及的主要命令有Query,QueryAdjust,QueryRep,并通过这3个命令来调节时隙数量。

在每个识别周期,读写器首先通过Query指令开启新的盘存周期,并确定哪个标签参与该盘存周期。Query命令含有时隙计数器参数Q,Q的取值范围为0～15。收到Query命令后,参与标签应在0至2Q-1内挑选一个15 bit的随机数,并应将该数值载入其时隙计数器。

挑选时隙为0的标签应转换成应答状态。

1)若只有一个标签应答,阅读器发送QueryRep命令,使标签时隙计数器中的时隙减1。

2)若没有标签应答,阅读器发送QueryRep命令,使标签时隙计数器中的时隙减1,或发送QueryAdjust命令减小Q的值,使所有未被识别的标签进入到下一轮周期识别循环操作中。

3)若有多个标签应答,阅读器发送QueryRep命令或发送QueryAdjust命令增大Q的值,使所有未被识别的标签进入到下一轮周期识别循环操作中。

从SR算法中可以看出,Q值越大,时隙的范围也就越大,发生冲突的可能性就会越小,但将导致空闲时隙增加;反之,Q值越小,标签发生冲突的可能性就会越大,导致冲突时隙增加。过多的空闲时隙和冲突时隙都会降低识别效率,因此读写器需要不断地调整Q值,使时隙数量接近于标签的数量,从而使得标签在最为合理的取值范围内随机选择时隙。

在EPC-C1G2标准中提出了一个选取Q值的方法[3],如图1所示。

图1 时隙计数器参数Q算法

其中,Qfp为Q的浮点表示,读写器将Qfp四舍五入为一个整数值,并用这个整数值代替Query命令中的Q值。C的典型值为0.1＜C＜0.5。当Q值较大时,读写器一般用C的较小值,如果Q值较小,则用C的较大值[6]。

2 改进的算法

在理想通信状态下,发生冲突的概率和出现时隙闲置的概率是不同的,而在SR算法中Q值固定的情况下,发生冲突时和出现空闲时隙时的Q的改变量是相同的,这样不利于时隙的分布达到最佳的状态。且当冲突发生时,冲突标签只能在新的识别周期操作中重新随机选择时隙,而重新选择后仍会存在冲突时隙与空闲时隙的数量无法调整的现象,这将影响标签的识别速度,从而影响了RFID的信息采集,不利于物流的信息化平台的建设。针对这些问题,文中做出了改进。

2.1 算法的改进

文中对Q的改变量Qchange做出了改进,并在此基础上重新通过实验设置Cn的分段值,以及对发生冲突后的标签的时隙的调整做出了改进。

2.1.1 Q的改变量Qchange的改进

定义待识别的标签数n,时隙数N,成功识别标签的时隙数n1。

由于标签时隙计数器的值是随机选取的,则每个标签选取时隙的概率相同,即1/N,符合贝努利分布[7]。

成功识别一个标签的概率为:

出现空闲时隙的概率为:

发生碰撞的概率为:

对p1求导,可得当N=n时,p1可以取得最大值为36.8%[8]。

当N=n时,p0≈p1=36.8%,则pc=1-p0-p1=26.4%,即在理想状态下,读写器可达到成功识别标签的概率为36.8%,空闲时隙的概率为36.8%,发生碰撞的概率为26.4%,则p0/p1=1.4。

为了快速地使标签的读取效率达到此种状态,设定Q的改变量Qchange为:

2.1.2 Cn分段取值的调整

在运用式(1)改变Q值的基础上,为了找到Q与Cn之间的一般规律,对Q算法按Cn取值的不同进行了仿真。由于Q算法是一种基于概率的算法,仿真采用计算10次求平均的方法,在C分别取不同值、Q初始值均为4的情况下计算当标签数按2的幂次方规律变化时的系统吞吐率,即标签数与所用时隙数的比值,仿真环境为Matlab7.0,仿真结果保留四位小数,具体结果见表1。

表1 Cn取不同值时系统吞吐量的变化

根据表1可以得出,在Q不同值时,对应的Cn的取值见表2。

表2 Q不同值时对应Cn的取值

2.1.3 冲突标签的时隙调整

对发生冲突后的标签的时隙调整做出了改进,算法将发生冲突的标签在其临近时隙内重新分布。定义1个命令random0:对时隙为0的标签在0和1中随机选取时隙。这样可以使发生冲突的标签能够尽快得到识别。

改进后的算法实现的过程如下:

1)设置Q的初始值为4.0,执行Query命令,为标签随机分配时隙。

2)读写器接收应答,会出现2),3),4)三种状态中的一种。

3)只有一个标签应答,则成功识别次标签,执行Queryrep命令。

4)没有标签应答,则根据当前Q的值,选择Cn来调节Q的值,即Qchange=Qfp-Cn。

5)有多个标签应答,则根据当前Q的值,选择Cn来调节Q的值,即Qchange=Qfp+1.4*Cn。执行random0命令,为发生冲突的标签在0和1中随机分配时隙,其它标签的时隙都加1,开始新的周期的识别,会出现6),7),8)三种状态。

6)读写器接收应答,会出现7),8),9)三种状态中的一种。

7)只有一个标签应答,则成功识别标签,转到11)。

8)没有标签应答,则Queryrep命令,读写器接收应答,random0为时隙为0的标签在0和1中重新随机分配时隙。未达到指定的循环次数,则转到6),否则转到11)。

9)有多个标签应答,则random0为时隙为0的标签在0和1中重新随机分配时隙。未达到指定的循环次数,则转到6),否则转到11)。

10)若达到制定的循环次数后,没能识别标签,则改变Q的值,重新为标签分配时隙。

11)判断Q的值是否改变,若改变执行Queryadjust,否则Queryrep命令识别下一个标签返回2),否则退出。

2.2 改进前后两种算法性能的比较

采用了基于在EPC-Gen2协议中标签的防碰撞算法的研究,为了便于仿真分析并假设检测到一个标签响应信息时,即认为该标签可以被正识别,仿真中调整冲突标签的时隙的循环次数为3次,采用计算100次求平均的方法通过仿真结果,得到标签数量和系统吞吐率之间的关系,采用原算法和改进算法识别一定数目的标签所需的总时隙数和系统吞吐率如图2所示。

仿真结果显示和原算法相比,改进后的算法可以大大提高标签识别率,系统吞吐率提高了7%。