物联网中标签持续到达的RFID防碰撞算法思路构建

摘 要

针对目前无线射频识别标签防碰撞算法中存在的识别效率在标签持续到达时的下降问题，本文提供了在给出标签到达与识别过程模型的前提下、支持标签持续到达的防碰撞算法的思路。本思路使用标签到达与识别的过程模型，所构造出来的算法能够对阅读器识别区域内的标签数量进行准确的估算。同时该算法使用排队论，对标签到达率的最大值进行了研究，确保了算法运行的稳定。

【关键词】物联网 标签 RIFD 防碰撞算法 思路

“物联网”一词随着电子信息技术、通信技术以及智能嵌入技术等的不断进步而频繁出现在人们的视线中。所谓物联网，即指物物相连的互联网。总共包含两层含义：一是其基础及核心依然是互联网。也就是说，物联网是互联网的扩展及延伸；二是客户端之间的信息交换延伸至任意的物品与物品之间。

1 网联网及RIFD概述

物联网的宗旨是使万物之间的信息传递更加方便快捷。要实现这一宗旨，要重要的就是要对物联网中的事物进行有效识别，这也是物联网的基础。在现今的技术手段下，自动识别技术是将物联网中的物和网进行有效连接的基本方式。

在物联网众多的自动识别技术中，RFID技术是一种实时、准确、快速的非接触式自动识别技术。RFID，即指无线射频识别技术。RFID利用射频信号以及空间耦合传输的特性，对目标对象进行自动识别，以此来获取所需的信息。由于RFID对物联网的需求具有很强的适应性，因此在物联网的物品自动识别技术中，它是最重要的识别技术。RFID具有的最突出的优势是能够对多目标进行识别及读取，刚好与物联网的全面感知及海量存储的要求不谋而合。

2 问题的提出

RIFD系统分别由标签和阅读器两部分组成。在标签较多时容易发生碰撞，因此降低其碰撞率是非常必要的，常使用的方法是防碰撞算法。

在RFID中，系统识别效率的高低与否取决于标签防碰撞算法的优劣。标签防碰撞算法又能对RFID在现实中的普及程度产生影响。在学术界，根据长期以来对相关理论及技术的研究，已经对RFID中的多目标碰撞识别算法问题形成了系统科学的体系。

碰撞协议主要有两种：时隙ALOHA类协议和树类协议。前一种协议的优势在于实现比较容易，因此在RFID系统中的应用比较广泛。后一种协议的优势在于能够对阅读器识别区域内的所有标签进行识别，但缺陷是延迟的时间较长。

当标签的数量帧内的时隙数一致时，时隙ALOHA类协的议识别效率也会达到最高。现有的相关研究也主要是集中于使二者的数值相等。但标签数量会在识别过程中发生一定的变化，因此需要一种动态协议。由此出现了与之相适应的动态帧时隙ALOHA协议，简称DFSA。DFSA在设置时将帧的长度与标签的数量设为一致，使得即使标签数量发生变化，识别效率依然最高。在标签数量不断变化的前提下，准确估计标签数量是保证识别效率最高的关键。目前的标签估计方法有很多。例如Schoute估计法、Cha估计法、Vogt法、Wen-Tzu Chen估计法等。以Cha估计法和为例，估计的标签数量n满足：

。其中l为帧长。而Wen-Tzu Chen估计法在所有算法中所产生的误差最小，平均大约为5%。上述方法均给定了标签，标签的数量是固定的。也就是说如果在识别时有外部标签进入，那么识别的误差就会加大，降低识别效率。换句话说，上述方法在阅读器无标签持续到达的静态情况下能够确定帧长，但如果是在标签持续到达的工厂自动化生产线上，则无法确定。本次研究针对这一问题，构建了一种能够支持标签持续到达的RFID防碰撞算法。在该算法中，帧长由两部分来决定，一是上一帧没有识别标签的数量，二是新到达标签的数量。该算法能够有效解决标签持续到达时系统的效率下降问题。

3 新算法的基本模型

在帧时隙ALOHA系统中，识别周期P是由许多帧Fi组成的，而则由多个时隙tij组成，Fi={tij|j=1，···，ni，}，其中ni为帧长。识别周期P={Fi|length（Fi）=ni，ni∈Z+}，Fi未识别的标签数量为ri（ri>0，0≤i≤u-1）。而帧Fi内每个时隙所到达标签的平均值为λi（0≤λi<1）。当λi=0时，表示识别过程中没有标签到达。现有算法对这种静态环境进行了研究；本文则是对0<λi<1时的动态环境进行研究。

帧Fi中的标签数量由两部分组成，一是未开始识别时启动时间T内到达的标签数量，二是新到的标签数量。识别前标签的到达率为λ0，标签数为r0=Tλ0；新到标签数为λini。因此帧内的标签总数即为mi（mi>0）即由未识别的标签数ri-1（1≤i≤u）和新到的标签数λini组成。识别过程见图1。

由上述内容可以得出，帧长取决于前一帧Fi-1未识别的标签数量和新到标签的到达率λi。在帧Fi没有开启的情况下，对λi进行估计是在标签持续到达的前提下，防碰撞算法对标签进行有效识别的核心和关键。在绝大多数情况下，标签的到达率是不断变化的，如果使用固定的到达率进行标签数量的计算，很明显不合理。因此进行标签数量估计的基本要求是对标签的到达率进行动态估计。由图1可知，帧Fi内的标签数量估算值为ri+si=ri-1+λini。进一步说，如果Fi内的成功识别时隙数为si，空闲时隙数为ki，碰撞时的时隙数为gi，那么可以得出，ni=si+ki+gi。

对于识别周期P的系统效率EP，不同文献有不同记载，本文中所指的是周期P以内总成功时隙数与总时隙数的比值，

。吞吐率，其中为时隙的时长。Fi的帧效率thi的定义为帧内标签的成功识别时隙数与帧长的比值，。假设标签的数量和帧长的数量相等时碰撞的时隙标签数为2.39，那么未识别标签的数量ri的估计值即为。x个标签被分配于n个时隙的帧内，帧效率在x=n的条件下达到最优，为0.368。

4 CDFSA算法

根据之前所论述的计算方法，会使帧的长度小于标签数，从而使系统的效率与最优值相比较小。本文提出的是一种对标签持续到达的过程进行分析的CDFSA算法。

4.1 对标签持续到达及识别过程的分析

根据上述所提到的效率最优原理，在CDFSA算法中，确定效率最优时的时长的关键是对下一帧的标签数量进行估计，也就是说要对新到标签的到达率进行估计。本文以定理的形式将结论呈现出来，同时对其进行证明。

定理1：帧Fi-1内的未识别标签在帧Fi中任意选择帧时隙的过程以及新到标签任意到达帧Fi内的时隙的过程皆可看做泊松到达过程，且两个过程相互独立。

证明：在帧时隙算法中，帧Fi-1内未识别的ri-1个标签在Fi内被识别时是任意选择时隙的，某一个时隙被选中的概率为1与时隙的比值。也就是说在ni时隙内到达的标签数量为ri-1个。而帧内标签一般较多，帧长也较大，那么某一时隙被选中的概率相对而言就会很小。根据概率的相关理论可知，时隙被选中的概率很小而到达标签数量较多时，帧Fi-1内的ri-1个未识别标签在帧Fi内任意选择时隙tij的过程与泊松到达过程较为接近。新到标签到达帧Fi的过程与这一过程类似，因此也可被认为是泊松到达过程。将单位时隙的平均标签数作为两个过程泊松到达的参数，用和分别表示。根据标签持续到达的过程可以得知，未识别标签任意选择时隙的过程与外部标签随机到达帧内时隙的过程相互独立。

定理2：帧Fi的帧长的计算公式为

证明：按照上文中提到的帧效率最优原理，Fi中参与识别过程的标签数量与帧长相同，也就是说Fi-1没有识别的标签数ri-1与Fi内新到达识别区域的标签数加起来为ni，帧效率能够达到0.368。由此可知，实现帧效率最高的条件是Fi中参与识别过程的标签在ni个时隙分布的泊松过程的参数为1。参与识别过程的标签是由两个泊松过程产生的，且二者互相独立。根据泊松叠加原理可知，。Fi-1的ri-1个标签在Fi内的平均到达率为。根据帧Fi未识别标签数的估计值计算公式，能够得出，因此。此外，由Fi阅读器周围标签的平均到达率计算公式可知，由此证明本式的正确性。

定理3：外部新到标签的平均到达率是保证系统稳定运行的基本条件。

证明：标签的识别过程结束后，离开是在离散间隙内，形成了离散时间排队系统。阅读器可以被当做这一排队系统的服务器，标签被当做客户，离去规则为随机离去。根据定理1及其证明过程可以得出，标签的到达间隔为几何状，到达概率为λ，也就是说标签的平均到达速度为λ。帧效率在时隙ALOHA算法中的最大值为0.368，也可以认为是在时隙内以0.368的概率对每一个标签进行识别，也就是说μ=0.368，同时服务时间的间隔也是几何状的，因此这一离散排队系统为Geom/Geom/1。根据该系统的稳定条件可知，当μ=0.368时，λ<0.368；λ>0.368时，ρ>1，此时系统不稳定，帧的长度也会不断变长。在阅读器的服务效率有限的情况下，会造成标签的相关信息遗失。这对RFID系统来说是不能出现的，因此可将这一数据作为对标签速度进行控制的根据。

4.2 具体算法

本文所提出的CDFSA算法的基本过程如下：

（1）对参数T及λ0进行初始化。

（2）将帧F1的长度设置为Tλ0。取整数：，而且。

（3）帧计数器i=1。

（4）阅读器帧i长度的计算：

（5）当n1=0时结束；n1≠0时继续。

（6）阅读器对还没有识别的标签进行防碰撞控制，使其处于不断被激活的状态。所有标签所构成的集合Tagi形成参与帧F1识别的标签集合。在进行防碰撞控制的同时，还对循环时隙数也就是帧长ni进行控制。将时隙计数器tr设置为1，碰撞时隙计算器gi=0，成功的时隙计数器si=0，将记录识别成功标签的RID清空。

（7）对区域内处于不断激活状态的标签k进行识别，同时对时隙tij进行随机识别，时隙计数器uk=1。

（8）阅读器在时隙tr这一位置上发送包括tr目前的数值以及被成功识别标签的RID值在内的时隙同步命令Ctr。

（9）对处于不断激活状态的标签s{s}的IDs在时隙tr中是否与Ctr中的RID相等进行比较，如果二者相等，则转为表示标签已经识别成功的静默状态，{s}。对循环激活状态的标签q与tr进行比较，如果二者相等，则向阅读器传送其值，；与其不相等部分的标签m{m且}，。对于外部新到的标签部分，在到达时隙时立刻向阅读器传送ID，那么帧Fi中参与识别过程的标签数量就会增加：，标签转为不断激活状态。

（10）在tr的后半段时，阅读器对标签是否识别成功进行检查。如果已经识别成功且得到正确的那么，且；若碰撞，那么。

（11）阅读器对进行检查看是否成立。如果成立，那么转入下一步骤，如果不成立，则转入步骤8。

（12）阅读器对本帧外部标签的额到达率λi进行计算，计算公式为

。然后转入步骤4。

5 结束语

针对目前的防碰撞算法中存在的在标签持续到达时识别效率下降的问题，本文提出了一种在标签持续到达时能够进行有效识别的CDFSA模型及具体算法。该算法具有计算量小的优势。

参考文献

[1]赵曦，张有光.一种新颖的RFID多标签防碰撞算法[J].北京航空航天大学学报，2008，（3）.

[2]刘冬生，邹雪城，李泳生等.射频识别系统中的防碰撞算法[J].华中科技大学学报（自然科学版），2006，（9）.

[3]刘子龙，纪金水，刘彩虹等.基于连续碰撞位探测的防碰撞算法研究[J].电子学报，2013，（11）.

[4]王雪，钱志鸿，胡正超等.基于二叉树的RFID防碰撞算法的研究[J].通信学报，2010，（06）.

[5]李志坚，赖顺桥.一种基于碰撞位指示的射频识别标签防碰撞算法[J].电子与信息学报，2014，（12）.

作者简介

刘忠群（1981-），男，江苏省丰县人，大学本科学历。现为江苏省徐州经贸高等职业学校讲师。研究方向为物联网应用技术、软件技术。

作者单位

江苏省徐州经贸高等职业学校 江苏省徐州市 221004