采用RFID技术查找畅销类产品

闫丽娟 赵菊敏 李灯熬

(太原理工大学信息工程学院，山西 太原 030024)

采用RFID技术查找畅销类产品

闫丽娟 赵菊敏 李灯熬

(太原理工大学信息工程学院，山西 太原 030024)

在基于有源电子标签构建的RFID系统中，如何以时间、能量有效的方式查找出畅销类产品是一个重要的研究问题。针对多阅读器RFID系统，首次对查找畅销类产品过程中的能量问题进行了研究，提出了一种基于分组机制的ETBC查找协议。该协议的核心思想是采用分组机制将同一属性产品上附着的标签分为一组，根据查找要求在相应组中找出样本标签，并基于样本标签回复的信息对其进行畅销类标签的查找。理论分析和仿真结果均表明了ETBC协议的有效性。相比针对全部标签进行查找的协议，ETBC协议的能耗要低很多，协议执行时间也大幅度减少。

RFID 有源标签 能量 分组机制 无线通信

0 引言

射频识别(radio frequency identification，RFID)是一种无线通信技术。在很多应用中，RFID系统可以用来追踪产品的信息、对象跟踪、超级市场和供应链的管理等[1-7]。目前有源电子标签被大量使用，由于其工作的能量全部由电池提供，且更换大规模标签的电池是个棘手问题，因此针对基于有源电子标签构建的RFID系统,设计能量有效的监控和识别协议是目前国内外的一个研究热点[8-10]。

目前，对于查找畅销类产品这一领域的研究很少，且对标签的研究大多集中在以减少时间为目的。RFID标签的能量作为新的指标越来越受到重视。鉴于此，提出了改进的阈值分类(enhanced threshold-based classification，ETBC)协议，实现畅销类产品的提取和分析，便于对产品的状态进行直观评判。其主要目的就是在众多产品中以高效、节能的方式查找出畅销类产品，主要贡献是首次提出了基于时间和能量有效的ETBC查找协议，并首次考虑了查找过程中的能量问题。

1 系统模型

本文考虑的RFID系统由3部分组成：后台服务器、一组RFID阅读器以及大量的RFID标签。假设后台服务器存储着系统中所有标签的信息，且阅读器和标签之间的通信采用帧-时隙 ALOHA协议。在执行协议的过程中，阅读器首先向标签发送查询命令，然后标签接收命令并返回相应的回复信息。每一轮响应中，阅读器广播查询命令和当前帧的时隙个数，每个标签通过Hash函数运算，随机选择此帧中的一个时隙对阅读器进行回复。具体来说，在每个查询帧的开始，阅读器广播两个参数：帧大小f和一个随机数ri，其中f也就是帧包含的时隙个数，而ri用来帮助标签在该帧中通过Hash函数选择一个时隙对阅读器进行回复。

2 问题定义

在阅读器的覆盖范围内，假设有n件附有RFID标签的产品，每一类产品拥有唯一的Cid和tid。设N为任意类别的标签数量，畅销类标签必须满足式(1)中的两个限制条件，其中Vh、Vl、α和β为给定的已知参数，Vh和Vl为阈值，α和β为概率值。任何一类标签数量超过Vh时被报道的概率至少为α，同时任何一类标签数量低于Vl时被报道的概率最多为β。

(1)

3 ETBC协议

针对查找畅销类标签这一研究领域，ETBC协议分为分组阶段、样本标签选择阶段、映射阶段、回复阶段和最优参数估计阶段这5个阶段。

3.1 分组阶段

分组阶段采用分组机制，即哈希分桶机制。在此阶段，拥有同一属性的标签属于同一组，同一组中包含若干类标签。例如在一个超市中，定义组G1代表的是洗漱用品，那么G1中包含洗发水、牙膏和沐浴露等类别的产品。具体的分组机制如下：首先通过式(2)的哈希函数得到组号Gi，rj为随机数；然后排除其他组的标签，直接从Gi组中查找畅销类标签，这个Gi其实就是每个桶，这就是哈希分桶的原理。简单来说，就是根据每个标签的Cid，通过哈希函数产生哈希值，然后将相同哈希值的标签放在同一组Gi中，就可以通过Hash这个间接作用，缩小标签的查找范围，从而减少执行时间。

(2)

3.2 样本标签选择阶段

样本标签选择阶段的主要思想是用哈希函数h(tid，ri)对标签进行映射，其中，密钥ri= f/p，f 为帧长，p为采样概率。经过映射后，帧长被扩展成为f/p，再将扩展的f/p均匀分为1/p个时间段，然后依次选取时间段里的标签作为样本标签。这样就成功地将所有标签几乎均等地分成 j 组采样标签集合S1～Sj。

假设w、p 和 f 为已知参数， w为仿真轮数。当 w < j 时，Sj集合中的标签在第 j 轮响应，其余轮属于休眠状态；当w > j 时，标签集合Sj的全部响应轮数 i 的规律如式(3)所示：

(3)

式中：a为整数，其值为[0，wp]间的所有整数。

当标签知道它们的所有响应轮数 i 时，对应的样本标签集合Sj就会在第i 轮保持通信状态，其他样本标签集合则保持休眠状态。通过通信和休眠两种状态的切换，就达到了减少标签能量开销的目的。

3.3 映射阶段

本阶段对同一组中的所有标签进行映射，对属于同一组的不同类的标签依次进行映射。一类标签中的任意标签tid选择时隙值为1+h(tid,ri)+(d-1)x的时隙进行映射，从而形成映射图Bi。其中，Bi的长度是f； h(·)是一个哈希函数，它的范围是[0，x-1]；x为一类标签映射的帧长；d是本组中每类标签的响应次序。根据每类标签的响应次序，可以得到映射图LBi，其中LBi的长度是x。根据Gi、Bi和f 的不同，本文可以有效地缩小标签查找范围。

3.4 回复阶段

在第i轮中，因为 LBi(Cid)的长度为x且一个标签只能使逻辑位图中的一个位为1，所以标签选择映射图LBi(Cid)中的任意一位并将其置“ 1 ” 的概率为1/x。而其他类的任意一个标签将这个位置“1”的概率为1/f。因此，LBi(Cid)中任意一位保持零的概率为：

(4)

因此，本文运用似然函数L来观察此帧中所有zi的值。在k个LBi中，有：

(5)

(6)

似然函数求极大值等价于对数似然函数求极大值。式(5)的对数似然函数形式如下：

(7)

由于ln(L)对k的导数存在，故将ln(L)对k进行求导，令其为0，得似然方程：

(8)

对式(8)结果进行化简，得到如下估计量：

其次，学生管理者的引导教育作用。学生管理者对学生的要求和引导是培养学生基本素质的关键，如果学生管理者每一项工作都对学生要求严格，精益求精，会对学生产生潜移默化的影响，让学生在耳濡目染中形成工匠精神。

(9)

3.5 最优参数估计阶段

(10)

把式(9)代入式(10)，可得：

(11)

因此，阅读器报道一个符合条件的Cid的概率为：

(12)

根据zi的分布，可以得到下面的式子：

因此有：

(13)

(14)

类似地，式(1)中的第二个限制如下：

(15)

4 仿真结果

4.1 设置参数

本文的仿真基于PhilipsI-Code的系统，ETBC协议只需要确定空和非空时隙，而tshort可以满足这个要求，其值为321μs。假设n=1 000 000，将标签分为G1和G2两个组。G1中n=600 000，G2中n=400 000，G1和G2中分别包含2 000类标签。首先，针对G1随机地从[300，600]分别选取y个值作为y类畅销类标签的数量，然后将剩余标签数量分到其余的非畅销类标签中, 非畅销类标签数量必须低于300。G2中的分组方法和G1类似。G1中每类标签的范围为(0，600]，Vh=300。G2中每类标签的范围为(0，400]，Vh=200。在每次仿真中，ETBC计算wf的最小值，即tshortwf+广播轮询请求的时间，但广播轮询请求的时间可以忽略。

4.2 试验结果与分析

下面进行了多次仿真来测试所提出协议的性能，主要测试协议两方面的性能：时间有效性和能量有效性。假设通过分析后查找的是G1中的畅销类标签，得到下面的仿真数据。

4.2.1 时间有效性

作为对比，将ETBC协议和目前最好的阈值分类(threshold-basedclassification，TBC)[3]协议进行比较。TBC协议是对所有标签进行查找，而ETBC协议是对pn个标签进行查找。

不同α、β时两种协议执行时间的变化情况如图1、图2所示。仿真结果表明，ETBC协议执行时间明显比TBC协议小。当采集概率p不同时，执行时间也不同，显然，p对执行时间有一定的影响。通过对比发现ETBC协议的性能最好，相比于p=1，ETBC在p=0.5时其执行时间较小。

图1 当α= 95%，β=5%时不同p值下两种协议的执行时间比较曲线

图2 当α= 90%，β=10%时不同p值下

从图1和图2可以看出，在给定p值情况下，随着α减小、β增加，TBC和ETBC的执行时间也同时减少，这是因为较大的α和较小的β意味着对执行时间有更高的精度要求。

4.2.2 能量有效性

通过分析采样概率p和执行时间之间的关系，发现随着p的减小，执行时间也减小。当阈值Vl固定且p变化时，得到了表1的数据。如表1所示，采样概率p和执行时间之间存在着一定的关系，即当p∈[0,0.09]时，随着采样概率p的增加，执行时间逐渐减低，而当p∈[0.1,1.0]时，随着p的增加，执行时间逐渐增加。下面的试验结果是在α、β、Vl、p四个参数不同时，根据ETBC方案中的限制条件(1)得出的执行时间。

表1 能量-时间对应关系

当p∈[0.1，1]时，执行ETBC协议时最小的执行时间如表1所示。当p∈[0,0.09]时，可以看出能量和时间之间存在一种权衡的关系。

图3、图4比较了ETBC在不同的α、β、Vl下的能量-时间权衡图。当α、β的值不同时，执行时间和采样概率p也不同，能量-时间权衡曲线也不一样。在图3、图4中，曲线最低点的执行时间是最小的，但其能量消耗并不是最小的。

数据表明，采样概率p越小意味着能量开销越小，但p不能随便选取，必须符合式(1)的限制。

图3 能量-时间权衡曲线1

图4 能量-时间权衡曲线2

5 结束语

本文针对基于有源标签构建的RFID系统[11]，提出了一种基于分组机制的时间、能量有效的快速畅销类产品查找协议ETBC。以前的研究大部分关注于时间，而本文首次关注了查找过程中的能量问题，并发现了ETBC协议查找过程中能量和时间之间存在的一种权衡关系。经一系列的理论推导和试验表明，ETBC可灵活地选择参数，操作简单，可在任何精度下查找出畅销类标签。

相比针对全部标签进行查找的协议，ETBC协议的能耗要低很多，特别适用于利用内嵌电池供电的有源标签。同时，ETBC协议的执行时间也显著低于TBC协议。仿真结果显示，ETBC可以减少执行时间和能量开销，是一种高效的方法，即使在高度精确的环境下也可以执行得很好。

[1] 李建坡，姜雪，隋吉生.电动汽车充电站RFID智能信息管理系统[J].自动化仪表，2014,34(11)：62-65.

[2] 靳祖光，陈超，唐坚.一种室内导盲机器人的RFID语音交互系统设计[J].自动化仪表，2014,35(3)：73-76.

[3] Luo W，Qiao Y，Chen S.An efficient protocol for RFID multigroup threshold-based classification[C]∥Proceeding of IEEE Infocom，2013.

[4] Zheng Y，Li M.ZOE:fast cardinality estimation for large-scale RFID Systems[C]∥Proceeding of Infocom，2013.

[5] Li T,Chen S,Ling Y.Identifying the missing tags in a large RFID system[C]∥Proceeding of ACM Mobihoc，2010.

[6] Kodialam M，Lau W C，Nandagopal T.Identifying RFID tag categories in linear time[C]∥Proceeding of ACM Mobihoc，2009.

[7] Sheng B，Chiu C T，Li Q，et al.Finding popular categories for RFID Tags[C]∥Proceeding ACM Mobihoc，2008.

[8] Li T，Wu S，Chen S.Energy efficient algorithms for the RFID estimation problem[C]∥Proceeding of IEEE Infocom，2010.

[9] Qiao Y,Chen S,Li T.Energy-efficient polling protocols in RFID Systems[C]∥Proceeding of ACM Mobihoc，2011.

[10]Luo W，Chen S，Li T，et al.Probabilistic missing-tag detection and energy-time tradeoff in large-scale RFID systems[C]∥Proceeding of ACM Mobihoc，2012.

[11]胡文锋，王玲玲，翁绍捷.RFID技术在高校实验室设备管理中的应用[J].科技资讯，2011(32)：33-34.

Finding Bestsellers Categories by Using RFID Technology

In the RFID systems that constructed based on active tags, how to find the bestsellers categories in both time and energy efficient manner is an important research topic. Aiming at the multi-reader RFID system, for the first time, the energy issue in process of finding bestseller categories is researched, and the enhanced threshold-based classification(ETBC) finding protocol based on grouping mechanism is proposed. The core ideas of this protocol is using grouping mechanism, to make the tags adhered on same category products in a group, and in accordance with the finding requirement to find out the sample tag in corresponding group; and to find the bestsellers categories tags based on the reply messages from the sample tag. The theoretical analysis and simulation result all indicate the effectiveness of the ETBC protocol. Comparing with the finding protocol for all of the tags, ETBS protocol features lower power consumption, the execution time of protocol is also greatly reduced.

Radio frequency identification(RFID) Active tags Energy Grouping mechanism Wireless communication

国家自然科学基金青年科学基金资助项目(编号：61303207)；

国家自然科学基金面上基金资助项目(编号：61371062)；

教育部2012年高等学校博士学科点专项科研基金联合资助项目(编号：20121402120020)；

山西省科学技术发展项目工业部分基金资助项目(编号：20120321024-01)；

山西省国际合作基金资助项目(编号：2012081031)；

2012年山西省留学回国人员科技活动择优基金资助项目；

2013年山西省留学回国人员科研基金资助项目(编号：2013-032)。

闫丽娟(1989-)，女，现为太原理工学校信息与通信工程专业在读硕士研究生；主要从事RFID技术、无线传感器网络技术的研究。

TN911

A

10.16086/j.cnki.issn1000-0380.201505012

修改稿收到日期：2014-10-14。