基于能量优化的射频识别标签防碰撞算法研究

,苗长胜,鲁恩

(1.国网四川省电力公司计量中心，成都 610000;2.北京智芯微电子科技有限公司，北京 100192)

0 引言

在研究基于云平台和RFID实现闭环模式下智能表全寿命周期管理系统工程的过程中，射频识别标签防碰撞算法是其中关键的研发重点，如何实现射频识别标签防碰撞算法性能高的同时又能尽量的节能，成为基于云平台和RFID实现闭环模式下智能表全寿命周期管理系统中重点研究以及实现的问题。

射频识别(radio frequency identification，RFID)是一种利用无线射频信号实现无接触信息的传递，再利用这些信息达到识别对象的技术[1-2]。这种射频识别的硬件系统一般由阅读器与电子标签构成，而在一些复杂的系统中，会使用到计算机系统。在射频识别系统中，阅读器是对电子标签进行读写的仪器，在整个系统中起着至关重要的作用；系统中的电子标签则是对所要识别对象信息的载体设备，一般会被安置在所要识别的物体之上，所得到的数据由计算机系统进行处理[3-4]。

无线射频、芯片以及计算机等技术的发展为RFID系统提供了快速发展的前提[5]。当前RFID系统发展迅速，其生产成本、体积以及能耗都得到了改进，而且功能也非常丰富。RFID系统在发达国家较为成熟，在各种领域都有着深入的应用，如商品管理、生产控制等[6]。国内虽然RFID系统应用出现的时间较晚，但是实际应的领域在不断扩大，发展异常迅速，如停车收费系统、火车车号识别系统等都已经在市场中广泛使用。RFID对人类生产、生活的帮助使得它的应用涉及到了各行各业，但是RFID技术在对多目标识别时仍然存在着一定的问题，这也成为制约RFID技术进一步发展的瓶颈所在[7-8]。

Jacomet在1999年提出一种查询树算法，但是他的算法计算时耗时太长，因此无法满足射频识别标签防碰撞快速识别的需求[9]。2003年，Claus Finkenzeller提出一种射频识别标签防碰撞算法，这种算法是一种二进制搜索算法，随后一些研究者依据他的算法提出一些改进的算法[10]。余松森在2004年提出了返回式二进制搜索算法,鞠伟成在2005年提出了动态二进制搜索算法，从不同的角度对二进制算法进行了改进，提高了射频识别标签防碰撞算法的性能[11]。返回式二进制搜索算法对减少了阅读器的查询次数，而动态二进制算法则减少了查询时单次标签与阅读器之间信息处理的数量。在此之后王雪等人在2010年提出了锁位后退式算法、冯娜、潘伟杰等人于2012年提出了跳跃式动态搜索算算法等等[12]。

截至目前，针对射频识别标签防碰撞算法的研究成为了物联网技术的一个重要的研究方向。在防碰撞研究领域，虽然有着很多的研究工作，但是如何使得算法具有低复杂度、效率高仍然具有很大的挑战难度。本文提出一种基于功率控制的分组算法，以达到提高防碰撞算法性能的目标。另一方面，由于功率控制的使用，使系统中的阅读器可以利用不同的发射功率来实现与不同距离的标签进行通信，所以该种方案可以在提高了系统性能的同时实现节能。

1 RFID基本原理以及基础知识

电磁波在空间中散射时，会遇到各种不同的目标，在电磁波到达目标后，一部分会被吸收到，一部分则会继续向外散射。反射的能量中的一部分会回到天线中，这部分被称为回波。在雷达中，该原理常用于目标距离的测量和定位。

图1 RFID的原理结构图

1.1 阅读器到标签能量传输

在距离为R的电子标签处的功率密度计算方式如公式(1)所示：

(1)

在公式(1)中，PTx是系统读写器的发射功率，GTx则是代表发射天线的增益，R是标签到读写器之间的距离。在理论上，标签可以吸到的功率计算方式如公式(2)所示：

(2)

在公式(2)中，GTag代表的是标签天线的增益。在RFID系统中，由于标签的能量来自于阅读器的天线所发射出的电磁场，所写标签的功耗与读写距离是负相关的，功耗越小距离就会越大，反之则越小。标签的功能能能否正常发挥功能由标签的电压决定，这也对系统识别的距离有着决定性的作用。当前在技术不断成熟的情况下，标签芯片的能耗已经降至几微瓦，因此，即使阅读器的功率受到限制，RFID的识别距离也得到极大的提升。

1.2 标签阅读器的能量传输

标签所反射回去的能量与雷达散射的截面是正比关系。标签会将一部分电磁波吸收用于自身的工作，另一部分则会发射回阅读器中，在阅读器中所接收到的标签信号总功率计算方式如式(3)所示：

(3)

GRx代表的就是系统中阅读器的天线增益，λ是标签发射能量的效率，依据公式(3)，如果将阅读器所接收到的标签发送能量为标准，则可以认定反向散射工作模式的RFID系统的识别距离的四次方与系统阅读器的发射功率成正比。

2 一种新的基于能量优化的射频识别标签防碰撞算法

2.1 RFID系统中的能量传输以及阅读器的范围分析

首先对RFID系统中的能量传输以及阅读器的范围进行分析，进而使得问题得以简化。首先分析单阅读器、单标签模型下的情况。

阅读器给定的输出功率为Pt,此时标签所得到的阅读器所发送的功率计算方式如公式(4)所示。

(4)

在式(4)中，Gt,Gr分别代表阅读器与标签天线，λ1,λ2代表阅读器与标签之间的通信前后与后向链路的工作波长，η则是代表标签能量反射效率，ri代表阅读器与标签i之间相应的距离，Pr-i就是指标签返射回阅读器的功率。

在实际的应用中，由于信息传递环境以及信道情况带来的影响，式(4)可以变更成为：

(5)

在式(5)中，q代表的就是环境因子，其值由实际的应用场景决定。

阅读器的询问范围是一个非常重要的指标，设定阅读器的接收功率的检测阈值为Prequired，此时可以得出：

Rinterrogation_range=sufriPr-i≥Prequired

(6)

将式(6)代入式(5)可得：

(7)

本文算法在防碰撞性能上达到了50%以上，对系统的有效服务率有着很大的提升。

2.2 算法的实现

前文分析的是单阅读器、单标签模型。但是在实际的应用中，存在着多阅读器多标签模型的情况，因此可以对这种单阅读器、单标签模型进行扩展。

参照公式(7)可以得出Rinterrogation_range是Pt的函数，因此只要对阅读器的输出功率进行控制，就可以对阅读器的询问范围进行调整。通过对阅读器的输出功率逐步提升，步距为Pstepped，此时就能够获得一组Rinterrogation_range。这一组输出功率可以把所要识别的区域进行划分，可以得到N个子区域，即Zone1，Zone2…ZoneN。此时，每次在与阅读器通信时，只选定其中一部分指定的区域进行通信，这样一来就可以实现阅读器与不同距离标签通信的功能。利用这种方案即能够使得标签的防碰撞性能得到提升，也可以使得系统的能量消耗得到减少，因此实用价值较高。

本文的算法主要涉及到所识别标签三个不同的状态，即“准备”、“待命”以及“静默”三个状态。算法的具体步骤如下。

步骤一：阅读器使用功率和标签通信，这样一来使得一部分的标签能够进入“准备”的状态。

步骤二：对处于“准备”状态的标签进行初始化，把它们的的状态改变，变成“待命”状态。处于“待命”状态的标签，会对阅读器的命令响应，反馈自己的数据信息。

IfPr

---Pt←Pt+Pstepped

---回到步骤一

ElseifPr≥Prequired

---对Zone i 区域中的标签数量估算

IfN≤1

---Zone I 的标签被识别。由于N是一个估算出来的值，此时其值仍可能大于1，所以仍然可能出现碰撞的情况，因此这里可以使用传统的标签冲突算法来解决，如Framed Slotted ALOHA。此处所使用的传统算法标记为Subroutine2。

--- 使用Subroutine2来解决碰撞问题

步骤三：

IfPt=Pmax

---退出算法

ElseifPt

---Pt←Pt+Pstepped

---回到步骤一

2.3 算法有效服务率分析

(8)

对于处于同一个碰撞时隙内的标签有两个及以上时，这些签在这个时隙内就会出现碰撞，此时我们使用p来代表硬币拋出0的概率，这就意味着在n个信息包中i个拋0的概率计算方式为：

(9)

CRI的长度由上式(9)得出计算方式如下：

(10)

K0=K1=1

(11)

Kn|i=E[Kn|i～]=1+Ki+Ki+1n≥2

(12)

因此，可以得到：

(13)

依据上式，n≥2时，利用递归可得：

(14)

依据式(9)以及(11)就可以把式(14)变换成为：

(15)

在后退式无线密码引的二进制算法中：

K1=1

(16)

在识别区域内有两个标签时，阅读器问询后标签信息包应答时就会出现碰撞。因为标签的EPC代码是唯一的，因此在运算后M1相同并且在同一个区域内的几率非常小，在两个不同的标签中，有着不同的二进制位数，这样一来就可以避免两个标签发出冲突的Request命令。因为在算法中，标签识别的前行与后退有着相对应的关系，因此：

K2=3

(17)

设定：Kn=2n-1n>2

(18)

在识别区域有n+1个标签时，新增加的标签信息包与原有M1的值是不同的，为保证把它与匹配度最高的标签落区别开，就需要在原有的二进制搜索树中添加一个节点，该节点间只有父子关系，并且有两边相连，因此：

Kn+1=(2n-1)+2=2(2n+1)-1

(19)

由数学归纳法可知假设成立，所以本文在解决碰撞时，Kn以及有效服务率n/Kn为：

Kn=2n-1n≥1

(20)

(21)

本文算法在防碰撞性能上达到了50%以上，对系统的有效服务率有着很大的提升。

3 实验结果与分析

在进行仿真前，首先对防碰撞算法的原理进行阐述。防碰撞算法的核心是要对在识别范围内的的多个电子标签进行有续访问。因此，系统中采用的算法能够使得在一个时间内只让一个标签与读写器建立通信，通信结束后即进入休眠，待下一个通信建立，如此循环只到所有的标签被识别完为止。这种方案是以状态机的形式实现。多标签防碰撞算法依据标准协议的要求嵌入到RFID系统的芯片中，提高读写器能够同时阅读标签的数量。防读写器会推送一个周期指令用于清点标签，在一个清点周期内，可能有一个或者多个标签参与，标签接收到指令后会在 (O，2Q.1)(Q为指令的参数)内产生一个随机数并将该数放入到计数器中。如果这个随机数是0的时候，该标签就会回复一个十六位的随机数，不是0则进入arbitrate状态，等待下一步的指令即QueryRep和 QueryAdjust指令。如果此时只有一个标签回复了信息，那么读写器就会确认该标签再由读写器发送QueryRep指令继续识别工作。如果没有回复或者有多个标签回复，那么读写器就会发送QueryAjust或者QueryRep指令。QueryAdjust指令用于改变参数Q的值，但不改变其它参数，这样就会使得标签依据新参数产生随机数；QueryRep指令则令计数器自减1。

仿真参数的设置流程如下：

1)使用subsystem对50个标签进行封装，再与阅读器连接；

2)将参数Q的值设为3，Qfp=3，时隙计数器值na=2Q=8，碰撞计数器nf=0，正确识别标签计数器nr=0；

3)系统的阅读器会依据下一个时隙内的回复信息的处理结果处理计数器，即回复信息有效时，保留标签信息并让接收器自增1，若回复信息无效则让碰撞计数器自增1；

4)把时隙计数器的值减1，并对此时的值进入判断，如果为0时，对碰撞发生器的值进行判断，若为0，这个清点周期结可，若不为零，依据算法对Q值进行调节并进入步骤1；若时隙计数器不为0时，阅读器利用算法对Q参数的值进行调节，并对系统发送Queryrep或 QueryAjust指令此时进入步骤2。

下面本文从算法的防碰撞性以及节能性能来对算法的性能进行分析。算法的防碰撞性分析由吞吐率分析进行，算法的节能性能分析由本文算法与传统算法的能耗相比得出。

依据相关的协议以及实际中的应用场景，算法的仿真设置参数为：Gr=2 dBi,Gt=6 dBi,f=900 MHz,q=1.5,Prequired=-60 dBm，阅读器设定的最大输出功率为Pmax=32 dBm,阅读器的最小输出功率Pmin=0 dBm,Pstepped=3 dBm。仿真分析依据蒙特卡罗方法进行，针对不同的应用场景的仿真结果见下文。

1)当标签在询问区内随机分布时，算法的性能对比如图2～4所示。

图2 标签随机分布下TAPC的标签防碰撞性能

从图2中可以看到，在识别标签片是随机分布在阅读器的询问题区域内，并且标签的数量在10到50之间时，TAPC的算法在防碰撞性能表现与Basic Framed Slotted ALOHA(BFSA)算法以及Dynamic Framed Slotted ALOHA(DFSA)算法相比要优秀的多。从图中可以看到TAPC算法在吞吐量小于60以下时，保持在0.45以上，与传统的算法相比，有着较大的优势。

图3 标签高斯分布下TAPC的防碰撞性能(标签数10～60)

2)传统的标签防碰撞算法有着能耗较高的不足之处，本文为了解决这一问题，提出了以功率控制为基础的标签防碰撞算法，即TAPC。依据仿真结果，可知TAPC算法使得RFID系统的能耗降低，并且提高了系统的防碰撞性能，在实际的应用中有着较大的价值。本文在复杂度没有提高的情况下改进了传统标签防碰撞算法中存在的不足之处，使得算法更加完善。所以本文的算法在实际应用的价值较大，另一方面，本文的研究成果也为RFID的防碰撞研究领域提供了新的参考，在理论研究上也具有一定的意义。

4 总结

针对射频识别标签防碰撞算法的研究成为了物联网技术的一个重要的研究方向。在射频识别标签防碰撞算法研究领域，虽然专家们有着很多的研究工作，但是如何使得算法具有低复杂度、效率高仍然具有很大的挑战难度。本文提出一种基于功率控制的分组算法，以达到提高防碰撞算法性能的目标。另一方面，由于功率控制的使用，使系统中的阅读器可以利用不同的发射功率来实现与不同距离的标签进行通信，所以该种方案可以在提高了系统性能的同时实现节能。