动态RFID系统中一种准确标签估计的动态帧时隙ALOHA算法

王 达, 李晓武

(1. 湖北工业大学 太阳能高效利用湖北省协同创新中心， 湖北 武汉 430068； 2. 昆明理工大学 信息与自动化学院, 云南 昆明 650504； 3. 湖北工业大学 湖北省电网智能控制与装备工程技术研究中心， 湖北 武汉 430068)

RFID技术是一种远程数据录入技术，该技术能够较好地提高物流、超市、工厂的工作效率，RFID有如下特征：非接触性，UFH超高频阅读器识别距离能够达到1～15 m，甚至更远；快速识别性，在多标签环境下，大部分超高频阅读器的识别速度已经达到每秒识别100甚至更多的标签，远远超过条码的识别速度；较强的环境适应性，RFID能够抗冲击、振动、电磁、温度和化学腐蚀影响。

通常在射频通信系统中，阅读器和标签的通信是通过共享无线信道来实现的，当多个标签同时响应阅读器就会发生标签碰撞，阅读器不能正确读到任何信息，我们把这种现象称之为标签碰撞问题，标签碰撞使得阅读器的读写速度大幅度降低。为了避免碰撞问题的发生，防碰撞协议是非常有必要的，好的防碰撞协议能够有效提高阅读器的标签识别效率[1]。标签识别效率也可以称作吞吐量，是指单位时间(如时隙)内阅读器识别标签的数量[2]。迄今为止，传统标签识别环境(静态场景)下的防碰撞协议研究已经比较成熟，这些协议可以分为两类：随机算法和确定算法[2-3]。通过这些算法，静态场景下的标签碰撞问题能够得到较好的解决，静态场景下的标签识别效率能够达到90%[3]。静态场景下比较常见的协议类型是动态帧时隙ALOHA算法，该算法属于随机算法，当帧长等于未识别标签数时，标签的识别效率最大[4]。

RFID应用中还一类应用场景，在该场景中，标签附着在目标的表面并沿着阅读器信号区内的固定路径移动，这种场景被称为动态RFID系统[4-5]，动态RFID系统经常出现在物流的出入口。在动态RFID系统，标签持续性的进入和离开信号区，动态RFID系统的概念图见图1。图1中，阅读器在标签移动路径的上方，阴影部分是阅读器的应答区域，简称阅读器信号区，标签沿着直线AB和CD中间的轨道移动，标签从左边进入信号区，从右边离开信号区。根据标签的移动速度、阅读器的长度可知标签通过信号区所花费的时间，以上描述的场景是本论文要研究的场景。

和静态场景RFID系统相比较，动态RFID系统的特点是：

(1) 标签的可移动性。在识别过程中，标签是可以移动的，阅读器能够对移动标签进行识别。

(2) 标签逗留的短暂性。标签在阅读器信号区内逗留时间是有限的，这和标签移动速度、信号区长度有关，标签在进入信号区前或离开信号区后，阅读器不能识别标签，标签只有在阅读器信号区内才有机会被识别。

(3) 标签的丢失性。由于标签的可移动性和标签逗留的短暂性，标签可能没有被识别就离开阅读器的信号区，这种标签称之为丢失标签，在动态RFID系统中，减少标签丢失是最重要的工作。评价动态RFID系统重要的性能指标不再是标签识别效率，而是标签丢失率TLR，其定义为

( 1 )

标签丢失率TLR有如下特点：

(1) 当未识别标签数密度过大时，标签的丢失率会增加，如果标签密度过大，标签丢失不可避免，为减少标签丢失率，减小标签密度是必要的，实际应用中，有时标签密度不可调整，如贴有标签的商品已经装入卡车中。

(2) 标签移动速度过快，标签丢失率会增加。如果标签移动速度过快，标签丢失不可避免，为减少标签丢失率，减小标签移动速度是必要的，当标签密度不可调整时，调整标签移动速度就变得很重要。

尽量降低标签丢失率是动态RFID系统的重要任务，一般要求标签的丢失率尽可能低[5]。为了降低动态RFID系统的标签丢失率，需要对原有的标签识别协议做改进，本文主要对广泛使用的动态帧时隙协议做改进，这种改进主要体现在协议中的帧长调整算法，改进后的协议优点是：

(1) 考虑了当前帧识别结果对标签识别的影响。

(2) 考虑了新进标签对标签识别的影响。

(3) 考虑了部分未识别标签离开阅读器的信号区对标签识别的影响。

(4) 可以用来改进动态帧时隙算法，使其能够适应动态RFID系统。

由以上优点可以看出，改进的协议综合考虑了影响帧长的诸多因素，和传统的动态帧时隙ALOHA算法相比，帧长的估计更适合于动态RFID系统。

1 相关工作

目前，关于如何准确确定动态RFID系统的标签识别方法的研究不多，文献[6]通过路径损耗和多路径效应等物理参数来判断标签的数量，但这并非本文研究的重点。

对于静态场景下的RFID标签的防碰撞协议已经研究的比较成熟[7-12]，本文首先说明一种经典的随机型标签防碰撞算法Vogt-DFSA[11]，该算法为本文所提协议的基础算法，了解了Vogt-DFSA协议及其改进算法，有助于实现其他经典及高效协议，Vogt-DFSA协议的步骤如下：

Step1在帧循环开始时，阅读器对信号区内的所有标签广播一个请求命令“Query”，该命令包括一个动态帧长参数L。

Step2信号区内所有收到“Query”命令的标签随机选择一个0到L-1的时隙，然后在选择的时隙传输其ID给阅读器。对于任意时隙，根据传输的情况，时隙分为空闲、成功及碰撞时隙3种。空闲时隙指的是没有任何标签选择该时隙传输其ID给阅读器。成功时隙是指只有一个标签选择该时隙传输其ID。碰撞时隙表示有两个或两个以上标签选择该时隙传输其ID号。

Step3当一个帧所有时隙都处理完，假如出现E个空闲时隙，S个成功时隙，C个碰撞时隙，并且E+S+C=L。根据概率论如果碰撞时隙数C较大，可以判断帧长设置过小，相对帧长而言，未识别标签数过多。如果空闲时隙E较大，说明帧长设置过大，相对帧长而言，未识别标签数较少。因此帧结束后根据当前识别状况(如碰撞数、成功时隙数、空闲时隙数)重新设置帧长是有意义的，可以减少碰撞或空闲时隙的大量出现。帧长设置的原则是当帧长等于未识别标签数时，标签的识别效率最优。一种简单的调整帧长方案为[11]

L=2.39×C

( 2 )

如果当前帧没有出现碰撞，标签识别处理结束；否则执行Step1。式( 2 )假设的是未识别标签数等于碰撞数的2.39倍。

以上是静态场景下动态帧时隙ALOHA算法设计的主要步骤和构想，帧长调整的主要目标是使得帧长大小等于未识别标签数，并且帧长调整主要依靠帧结束后的碰撞数、成功时隙数、空闲时隙数进行判断[7-9]。

对于动态RFID系统，如果只依靠帧结束后的碰撞数、成功时隙数、空闲时隙数来调整帧长是不合理的。因为在动态RFID系统一帧执行完后，未识别标签数由新进标签和当前帧引起碰撞时隙的部分标签组成。为了分析在动态RFID系统中未识别标签数，假设：

(1) 标签的流量等于tra，单位为标签/时隙。假如标签流量tra等于0.8，意味着一个时隙只有0.8个标签进入信号区，这样规定标签流量的单位有利于分析动态RFID系统的性能。

(2) 标签的帧长用L来表示，单位为时隙。

(3) 标签的逗留时间用Dcov表示，单位为时隙，意味着标签通过阅读器信号区需要Dcov个时隙，超过Dcov时隙，标签将离开阅读器信号区。

(4) 一帧结束后，阅读器能统计到E个空闲时隙、S个成功时隙、C个碰撞时隙。

基于以上假设和分析，当前帧识别过程中，新进标签数nnew为

nnew=tra×L

( 3 )

当前帧识别过程中，碰撞标签也属于未识别标签，碰撞标签导致的未识别标签数nc为

nc=2.39×C

( 4 )

本文中采用碰撞时隙数的2.39倍作为参与碰撞的标签数量[11]。因为碰撞标签与新进标签相比，比较接近信号区的出口，部分碰撞标签可能没有等到下一帧的识别就离开阅读器信号区，为了便于理解，图2为前后两帧信号区内未识别标签的分布情况。

图2(a)为帧识别前的未识别标签分布情况，图2(b)中，虚线左边为帧识别过程中进入信号区的未识别标签分布情况，虚线右边为参与帧识别后的未识别标签分布，这些未识别标签是由于标签碰撞产生的。可以看出，当标签流量恒定时(这是本文的研究场景)，新进标签的标签密度更大，而已参与帧识别标签的标签密度更低。因此，虚线左边的标签密度大于虚线右边的标签密度，并且，虚线右边的标签又分为两份，其中，虚线右侧和信号区右边界左侧的标签是未离开信号区的碰撞标签；信号区右边界右侧的标签为离开信号区的未识别标签。

( 5 )

根据以上的分析，一帧后未识别标签数nui或新帧长L′应设置为

( 6 )

当标签识别处于开始阶段(见图3)，图3(a)表示阅读器刚开始识别标签，信号区内未识别标签数量只分布在信号区的左边，图3(b)显示一帧执行完后，前一帧剩余未识别的标签分布在虚线右边，并且没有碰撞标签离开阅读器的信号区，因此，式( 6 )应改变为

L=nui=tra×L+2.39×C

( 7 )

式( 7 )的使用条件为

∑L(i)

( 8 )

式( 8 )所给条件表示识别的起始若干帧长小于标签的逗留时间Dcov时，帧长调整采用式( 7 )，否则帧长调整采用式( 6 )。在本文中不讨论标签识别末期没有新标签进入信号区的情况，这是因为采用动态帧时隙ALOHA算法识别标签的阅读器不能检测是否有新进标签进入。

2 动态RFID系统中一种考虑新进标签动态帧时隙ALOHA协议

动态RFID系统中考虑新进标签动态帧时隙ALOHA协议(以下简称DFSA-CN协议)的步骤为:

Step1在帧循环开始时，阅读器对信号区内的所有标签广播一个请求命令“Query”，该命令包括了一个动态帧长参数L，初始帧长设置为128。

Step2信号区内所有收到“Query”命令的标签随机选择一个0到L-1的时隙，然后在选择的时隙传输它的ID给阅读器。

Step3当一个帧所有时隙都处理完，根据前文分析调整下一帧的帧长，调整算法为

( 9 )

如果当前帧的成功时隙数和碰撞时隙数的和为0，标签识别处理结束；否则执行Step1。

Step4阅读器识别结束的条件是成功时隙数和碰撞时隙数之和为0，因为在标签流入信号区流量恒定的条件下，在一帧结束后，成功时隙数和碰撞时隙数之和大于0，只有当标签流入信号区为0时，才会出现成功时隙数和碰撞时隙数之和为0。

从以上的算法可见，当一帧结束后，DFSA-CN协议将会考虑新进标签和未识别标签离开信号区对帧长的影响，这就是该协议与原有DFSA协议的关键不同点。

3 仿真和结果

为了评估本文所给协议的性能，把DFSA-CN和经典的动态帧时隙ALOHA协议(DFSA)进行比较，通过变化标签流量tra、标签逗留时间Dcov和初始帧长L三个角度分析它们对两种协议标签丢失率TLR的影响。本文仿真采用蒙特卡洛方法，仿真不考虑阅读器对标签发送指令所耗费的时间，只考虑标签向阅读器发送信息所耗费的时间(用时隙来表示)，因为RFID系统通信的主要时间损耗发生在标签向阅读器发送信息的过程中。

在图4(a)为tra变化对标签丢失率TLR的影响，该仿真实验环境参数为：Dcov=1 000时隙，L=32时隙。仿真中，流量的单位是每时隙有多少个标签进入阅读器信号区内，如当标签流量为0.5时，这表示一个时隙内有0.5个标签进入阅读器信号区，即两个时隙有一个标签进入信号区，从该仿真可见：

(1) 随着标签流量tra的增加，两种协议的标签丢失率都在增加，因为在相同的时间内进入阅读器信号区的标签数量更多，导致标签丢失较多。

图4(b)为Dcov变化对标签丢失率TLR的影响，该仿真实验环境参数为：tra=0.8标签/时隙，L=32时隙。在该仿真中，标签逗留时间单位是时隙，由图4(b)可见：

(1) 随着标签逗留时间Dcov的增加，两种协议的TRL缓慢降低，降低速度较慢，因为随着标签逗留时间增加，阅读器有更多机会识别碰撞标签，而TRL降低缓慢的原因是标签进入信号区的流量没有改变，标签流量的变化是标签丢失率变化的主要因素。

(2)在相同的标签逗留时间Dcov条件下，DFSA-CN的标签丢失率小于DFSA的标签丢失率，如在标签逗留时间为2 000时隙时，DFSA-CN丢失率为0. 206 1，而DFSA的标签丢失率则为0.266 4，这是因为DFSA-CN协议考虑了新进信号区标签和离开信号区标签对标签识别的影响。

图4(c)为L变化对标签丢失率TLR的影响，该仿真实验环境参数为：tra=0.5标签/时隙，Dcov=1 000 时隙。仿真中帧长单位是时隙，由图4(c)可见：

(1) 随着初始帧长L的增加，两种协议的标签丢失率TRL先降低后增加，这是因为太小的帧长，将导致碰撞较多，这会增加标签的丢失率。同样帧长太长将产生过多的空闲时隙，这也会增加标签的丢失率。

(2) 在相同的初始帧长L条件下，DFSA-CN的标签丢失率小于DFSA的标签丢失率，如初始帧长为128时隙时，DFSA-CN丢失率为0.238 3，而DFSA的标签丢失率为0.296 9，因为DFSA-CN协议考虑了新进信号区标签和离开信号区标签对标签识别的影响。

图4的仿真结果从3个角度分析了DFSA-CN协议的性能，这些仿真都显示本文所给协议DFSA-CN具有更优良的性能，即在相同的条件下，DFSA-CN的标签丢失率都低于DFSA。

4 结束语

本文对动态RFID系统进行了深入分析，并给出适合动态RFID系统的DFSA-CN协议，文中分析了动态RFID系统未识别标签的新进标签、碰撞标签组成部分，一帧结束后新标签进入信号区的数量，一帧结束后离开信号区的碰撞标签数量。由于所给协议DFSA-CN能准确确定未读标签的数量，从而给出了较为合理的帧长函数。本文调整帧长的思路可以用于改进大部分动态帧时隙ALOHA协议的标签估计算法。