基于0—1分布的RFID标签估计算法

　　0引言

　　无线射频识别（RadioFrequencyIDentification，RFID）是一种非接触式识别技术，采用电感耦合和电磁反向散射耦合两种方式传递信息、交换数据。简单的结构、相对低的价格以及较大的存储容量使得RFID广泛应用于门禁、不停车收费、资产管理、物品追踪和仓储控制等领域[1]。当多个电子标签一起向阅读器（Reader）发送信息时将会出现相互干扰，称之为标签碰撞。如何解决RFID的碰撞问题是当前研究的重点。

　　当前用于解决RFID标签碰撞问题的方法有两类：基于树分叉的确定性算法[2-3]和基于ALOHA的非确定性算法[4]。基于树分叉的防碰撞算法把阅读器识别范围内的标签集分成多个子集，直至只包含单一标签的集合时识别标签，实际上是树的深度优先遍历。当标签数量相对较少时，利用树分叉的识别算法能够有效地减少标签碰撞的发生，提高系统的吞吐率；但是当标签数量相对较大时，树的深度将会变得非常大，以至于系统吞吐率变得很低。ALOHA算法是让阅读器识别范围内的所有标签随机地选择一个时隙（slot）向阅读器发送数据。因此，合理的ALOHA帧长能够很好地提高RFID系统的识别效率。标签估计算法可以用于调整ALOHA类算法的帧长。由此产生的标签估计问题也是拥有大量标签的RFID系统的重要任务。本文提出的基于0-1分布的标签估计算法，利用0-1分布的特性，设定标签响应阅读器盘存命令的策略，在降低估计时间的同时，保证了标签的低成本。

　　1标签估计算法

　　估计标签数量无论对于ALOHA类的标签识别，还是一些统计无线节点数量的领域都有着非常重要的意义[1]。现有的标签估计算法主要有LB（LowBond）估计算法、碰撞率估计算法[5]和切比雪夫不等式估算法[6]，以及通过阅读器对空时隙的检测提出的PZE及其改进算法EZB（EnhancedZerobasedEstimator）[7]。

　　碰撞率估计通过对一个帧长中出现的碰撞帧的检测，计算出实际的碰撞率作为Pc的值，再利用式（1）～（3）求出n的值。

　　切比雪夫不等式估计算法（Vgot估计算法）运用系统对空时隙、成功时隙和碰撞时隙的实际检测值和期望值找到期望值与检测值之间的最小差值，以确定n的值。此种方法相对精确，但是计算复杂。

　　无论PZE还是EZB都使用固定的概率p来确定标签是否发送信息，p=min（1，1.59/ρ），其中ρ为系统的加载因子（Loadfactor）[5]，是响应阅读器的标签数与帧长的比值。这两种方法需要动态修改ρ值，增加了系统的读取时间。

　　以上算法都有一个共同的缺点，即当系统中标签数量足够大，而系统的帧长相对较小时，系统出现空时隙和成功时隙的概率将很小，一旦阅读器没有检测到空时隙和成功时隙，则以上估计算法误差率将会很大。

　　文献[1]中提出了一种新的标签识别算法——LoF（LotteryFrame）标签估计算法，使得估计时间为对数级，其通过在标签中使用hash函数来选择是否响应阅读器。估计算法的精确度取决于所使用的hash函数；如果在标签中执行hash函数，需要增加存储hash函数的存储空间，增加了标签的成本；另外由于低成本的特性，现有的无源标签并不具备执行复杂hash函数的能力。若按照文献[8]中所提出的设计方法，使标签在生产过程中存储标签ID号的hash值，以减少标签执行hash函数的过程和降低标签成本，则将使现有标签无法使用。

　　为实现低成本无源标签在大规模RFID系统中的应用，本文根据0-1分布的特性，基于第1类第2代UHFRFID860MHz～960MHz通信协议标准中标签的基本硬件结构，提出了基于0-1分布的标签估计算法。

　　2基于0-1分布的标签估计

　　2.1算法原理

　　数学家德·摩根曾抛掷4092次硬币，得到正面向上的结果为2048次。由概率统计可知，抛掷硬币，其落地所得结果为正面或反面的概率均为1/2，服从0-1分布。本文根据0-1分布的此种特性，设定阅读器识别范围内的标签随机选择0或1两个时隙响应阅读器的盘存命令。若检测到0时隙碰撞，则令0时隙响应的标签重新选择0或1时隙响应盘存命令，直至出现非碰撞时隙。由于每次响应盘存命令的标签数量都约为前一次的一半，由此可以由查询次数估计标签的总数量。