基于中间件的RFID系统冗余阅读器判别算法

陈阳 陈坚泽 李超

学术研究

基于中间件的RFID系统冗余阅读器判别算法

陈阳1,3陈坚泽1李超2

（1.广东云伴智能科技有限公司，广东 广州 510000 2.华南理工大学，广东 广州 510000 3.广东省计算机学会，广东 广州 510000）

在大规模RFID系统中，冗余阅读器判别是系统性能优化的重要途径。首先，对现有的RFID系统冗余阅读器判别算法进行分析和比较；然后，结合各判别算法的特点提出一种基于中间件的RFID系统冗余阅读器判别算法。仿真实验结果表明：本文提出的MNRCBA算法可有效提高冗余阅读器的检出率，且具有更好的系统部署合理性。

RFID；中间件；冗余阅读器；判别算法

0 引言

射频识别（radio frequency identification, RFID）技术以非接触、低成本的特点广泛应用于仓储管理、物流跟踪和生产监控等领域[1]。通常情况下，为防止RFID标签漏读，在工作区域布设尽可能多的阅读器，以实现RFID标签的全覆盖。但这会造成大量冗余数据，影响RFID系统的整体性能。在RFID系统中，当某个RFID阅读器覆盖的所有标签同时被其他阅读器覆盖时，该RFID阅读器为冗余阅读器。冗余阅读器是产生冗余数据的重要来源之一[2]。为判别冗余阅读器，降低RFID系统能耗，国内外许多研究人员对RFID冗余阅读器判别算法进行了研究。

经典RFID冗余阅读器判别算法包括冗余阅读器消除法（redundant reader elimination, RRE）)[3]、分层消除优化法（layered elimination optimization, LEO）[4]、基于计数的算法（count based algorithm, CBA）[5]。研究人员在经典算法基础上，通过组合或改进使判别结果更优，如改进的冗余阅读器消除方法（improvable redundant reader elimination, IRRE）[6]，RRE+LEO[7]，RRE+CBA[8]等。其中，吕石磊[9]提出基于中间的RFID系统阅读器去冗余算法（middle -based redundant reader elimination, MRRE），利用RFID中间件的标签信息判别冗余阅读器，不需要系统拓扑信息及频繁地对标签写入信息，有效减少其他判别方法因阅读器对标签频繁写入而导致的误判或漏判冗余阅读器问题，为冗余阅读器判别方法研究开辟了新路径。这些算法都以找到更多冗余阅读器为目的，忽略了RFID阅读器部署合理性问题，导致有时出现保留的冗余阅读器干涉区域较大，产生较多干扰信号，影响RFID系统性能。通过研究相邻阅读器的性质可解决该问题，如基于邻近覆盖密度法（neighboring coverage density, NCD）[10]、邻近阅读器竞争消除算法（neighbor-reader competitive elimination algorithm, NRCEA）[11]等。

本文在分析现有RFID冗余阅读器判别算法的基础上，总结各判别算法的特点，并提出一种基于中间件的RFID系统冗余阅读器判别算法。首先，以CBA算法的启发策略找出确定的非冗余阅读器；然后，运用RRE思想对剩余的RFID阅读器赋予权值，并结合NRCEA思想对赋权规则进行改进；最后，采用RFID中间件技术实现RFID冗余阅读器的判别。

1 RFID冗余阅读器相关研究

早在2009年，CARBUNAR等[3]首次提出冗余阅读器是影响RFID系统性能的基础问题之一，并指出即使在知道RFID系统拓扑的前提下，判别冗余阅读器也是一个非确定多项式（non-deterministic polynomial, NP）问题。RFID冗余阅读器判别算法的目的是使工作区域内的RFID阅读器，在实现区域标签全覆盖的同时数量最少、布局更合理、阅读器间信号干扰更小，从而降低系统能耗，改善系统性能。

RFID系统示意图如图1所示，其中R1，R2，R3，R4是4个阅读器，圆形表示RFID阅读器的读取范围；T1，T2，T3，T4，T5是5个标签。

图1 RFID系统示意图

由图1可以看出：关闭阅读器R3和R4，5个标签仍然能被全部读取，即R3和R4为冗余阅读器。但R1和R2存在干涉区域，会产生干扰信号。如果关闭R2，保留R1，R3，R4，此时RFID系统实现5个标签全覆盖，且不存在干涉区域，避免干扰信号。

1.1 RRE算法

RRE算法[3]基于贪心算法设计，其关键思想是根据RFID阅读器读取的标签数目对阅读器进行赋权。该算法能够较直观和简单地判别冗余阅读器。但当RFID系统中阅读器布设密度较高时，读取范围严重重叠，RRE算法的判别能力可能失效。

1.2 CBA算法

CBA算法[5]采用的启发策略使该算法能够保证每次判别的非冗余阅读器一定是非冗余的。该算法在判别非冗余阅读器上有明显优势，有效避免了误判而导致的标签漏读情况。然而，该算法受判别顺序影响较大，不同判别顺序对判别结果影响较大。

1.3 NRCEA算法

NRCEA算法[11]的主要思想是比较相邻阅读器的共享标签数，从而量化各个RFID阅读器间的汇聚度，并认为汇聚度越高的阅读器能够识别的标签越多，在网络中发挥的作用也越大。该算法取消了迭代运算，具有计算量小、效率高的特点。该算法将可读取更多标签且具有更多共享标签的阅读器优先保留。但具有更多共享标签的阅读器，往往与其他阅读器的重叠区域较多，也意味着这些阅读器可能具有更的多干扰信号，不利于RFID系统性能提升。

2 MNRCBA算法

由于以下3种原因，上述算法可能存在对冗余阅读器误判和漏判的情况：1）阅读器与标签一对一的写入方式；2）阅读器与标签通过读写操作实现交互的通信方式；3）阅读器对标签的读写距离不等的特性。因此，本文借鉴文献[9]提出的利用中间件存储分析RFID阅读器读入标签信息的方法，提出一种基于中间件的RFID系统冗余阅读器判别改进算法（middleware-neighbor reader-count based algorithm, MNRCBA）。首先，运用CBA找出确定的非冗余阅读器；然后，改进NRCEA算法，即将读取标签数最多且共享标签数最多为优先保留阅读器的原则，变成读取标签数最多且相邻阅读器最少为优先保留阅读器原则；最后，根据计算的优先权，运用RRE思想进行冗余阅读器判别。

MNRCBA算法步骤：

1）工作区域内，RFID阅读器读入其识别范围内的标签信息，并传送到RFID中间件，建立“阅读器——标签”矩阵，其元素()定义为

2）将矩阵各行相加，得到列向量，列向量的数值表示各阅读器所能读取的标签数量的总和；将矩阵各列相加，得到行向量，行向量的数值表示能读取该标签的阅读器个数；

3）根据CBA算法思想，将行向量中元素等于1的标签所对应的阅读器设定为非冗余阅读器，并锁定这些阅读器对应的标签；

4）令步骤3）中被锁定的标签在矩阵中置0，得到更新后的矩阵’；

5）对矩阵’重复步骤2）和步骤3），迭代运算至“阅读器——标签”矩阵中各列相加得到的行向量中所有元素均大于1；

6）设步骤5）中得到的“阅读器——标签”矩阵为，则对矩阵中仍然需要判别的阅读器逐一查询，获得这些阅读器相邻阅读器；其规则为：获得所查询阅读器的标签集合，根据标签集合中每个标签对应的阅读器，获得相邻阅读器集合，得到相邻阅读器个数；

7）计算各阅读器查询权重因子，其原则是读取标签数最多且相邻阅读器最少的阅读器权重因子越大，反之越小，其运算公式为

8）按各阅读器的权重因子大小顺序逐个选择阅读器，锁定所选择阅读器的标签，更新“阅读器——标签”矩阵，直到矩阵中所有元素为0，此时未被选择的阅读器即判别为冗余阅读器。

分析MNRCBA算法可知：经过步骤1）~5）后，剩下的阅读器基本上与其相邻阅读器具有重叠区域，而重叠区域以NRCEA算法将读取标签数最多且共享标签数最多为优先保留阅读器的原则时，阅读器更容易存在干涉区域而使干扰信号增大。而以相邻阅读器更少原则进行改进，则可避免这些干涉区域的出现，得到布局更完善的RFID系统。

MNRCBA算法伪代码如下：

forj=1 to Tmaxfori=1 to Rmaxif（A(i, j)=1 and Am(j)=1）thenNonRReader(j)←readerID(i)end ifif(Ri(j)=intersect(ones(i,j),A'[(i,j)|a(i,j)=1]))then A[(i,j)|a(t,j)=1]←0；end ifTR(i)←An(i)RN(i)←length(RNi)forl=1 to Rmax by sorted(WR(i))if (ReaderID(l) unlocked)fork=1 to Tmaxif (A’(l,k)=1 and A’m(k)=1)then NonRReader(k)←readerID(l)else then RedReader(l)←readerID(l)end ifend forforh=1 to Tmaxif (A’(l,h)=1 and RedReader(l)=1)then A’[(i,j)|a(t,j)=1]←0；end ifend forend ifend forend for end for

3 实验与分析

图2 RFID系统阅读器与标签仿真拓扑图

3.1 冗余阅读器判别效果分析

1）将标签数量设为2000个，然后阅读器数量从100个开始依次增加100个，直增至600个，考察4种算法能够找出的冗余阅读器数量，实验结果如图3所示。

图3 各算法判别效果（2000个标签）

由图3可知：在标签数量不变且阅读器较少时，4种算法找到的冗余阅读器数量相当，RFID性能相当。但随着RFID阅读器数量增加，MNRCBA算法找出的冗余阅读器相对较多，RFID性能提升明显；而CBA算法、NRCEA算法性能相当，RRE算法性能相对较差。

2）将阅读器数量设定为500个，然后标签数量从1000个开始依次增加1000个，直增至6000个，考察4种算法能够找出的冗余阅读器数量，实验结果如图4所示。

图4 各算法判别效果（500个阅读器）

由图4可知：MNRCBA算法相对于其他3个算法找出的冗余阅读器数量更多，且在标签数量较少时具有较高性能，而CBA算法和RRE算法在标签数量较大时（约3000个）才具有较好的判别效果。

3.2 RFID系统标签信息量分析

RFID系统标签信息量分析主要衡量判别算法对冗余阅读器判别消除后，剩余阅读器共享标签的数量，共享标签的数量越少表示RFID系统读入的标签重复率越少，后续数据处理更容易。一般采用标签总量溢出率（rate of overflow, RoF）进行量化，其公式为

式中，为RFID系统消除冗余阅读器后阅读器集合；(R)为阅读器R的可读标签集合；max为RFID系统标签总数；R为对标签的平均读取率。

将阅读器数量设定为500个，然后标签数量从1000个开始依次增加1000个，直增至6000个，考察4种算法的系统标签信息量，实验结果如图5所示。

图5 各算法RoF值比较

由图5可知：MNRCBA算法和NRCEA算法的值远远小于CBA算法和RRE算法的值，表示MNRCBA算法和NRCEA算法在消除冗余阅读器的同时能够保证共享标签的数量在较小范围内，且MNRCBA算法比NRCEA算法稍有优势。

3.3 RFID系统部署性能合理性分析

系统标签信息量分析主要衡量判别算法对冗余阅读器判别消除后，剩余阅读器对标签的读写冲突发生概率。理想情况是在满足所有标签全覆盖的同时实现各阅读器独立工作而互不干涉，即RFID系统没有相邻阅读器。一般采用平均相邻阅读器数量（average quantity of neighbor readers, ANR）来进行量化评估，其公式为

将阅读器数量设定为500个，然后标签数量从1000个开始依次增加1000个，直增至6000个，考察4种算法的系统部署性能合理性，实验结果如图6所示。

图6 各算法ANR值比较

由图6可知：经MNRCBA算法和NRCEA算法判别后的RFID系统部署性能明显优于CBA算法和RRE算法，且MNRCBA算法比NRCEA算法有较明显优势，这是因为MNRCBA算法的原则是尽可能少的相邻阅读器，与系统部署性能合理性要求相符合。

4 结论

针对大型RFID系统在布设阅读器时，为达到标签全覆盖而导致的冗余阅读器问题，提出一种基于中间件的RFID系统冗余阅读器判别算法——MNRCBA算法。该算法结合RRE算法、CBA算法和NRCEA算法的优点，并以读取标签数最多且相邻阅读器最少的阅读器作为优先保留原则，有效提高消除冗余阅读器后RFID系统的部署性能。实验仿真结果表明：本文提出的MNRCBA算法在冗余阅读器判别效果、RFID系统标签信息量以及RFID系统部署合理性3方面均取得较好性能。

[1] 刘畅.RFID中间件数据处理方法研究[D].南京:南京邮电大学,2017.

[2] 何涛,刘畅,徐鹤,等.一种基于中间件的RFID阅读器去冗余高效算法[J].计算机技术与发展,2017,27(6):27-31.

[3] CARBUNAR B, RAMANATHAN M-K, KOYUTÜRK Mehmet, et al. Efficient tag detection in RFID systems[J]. Parallel and Distributed Computing, 2009, 69(2): 180-196.

[4] HSU C-H, CHEN Y-M, KANG H-J. Performance-effective and low complexity redundant reader detection in wireless RFID networks[J]. EURASIP Journal on Wireless Communication and Networking, 2008, 22: 138-145.

[5] PAN S-Y, YANG Z-Y. A count based algorithm for redundant reader elimination inf RFID application system[C]. intelligent system design and engineering applications(ISDEA), 3rd international conference on intelligent system design and engineering application, 2013: 30-33.

[6] 姜跃.RFID系统的冗余阅读器消除改进算法I-RRE[J].计算机工程与应用,2011,47(5):101-103.

[7] IRFAN N, YAGOUB M-C. Efficient algorithm for redundant reader elimination in wireless RFID networks[J]. International Journal of Computer Science Issues, 2010, 7(3): 1-8.

[8] 徐伟,杨智应.一种RFID网络系统中消除冗余阅读器的高效算法[J].现代计算机(专业版),2015(17):36-41.

[9] 吕石磊,余顺争.一种基于中间件的RFID系统阅读器去冗余算法[J].电子学报,2012,40(5):965-970.

[10] MA M, WANG P, CHU C-H. A novel distributed algorithm for redundant reader elimination in RFID network[C]. 2013 IEEE International Conference on RFID-Technologies and Application (RFID-TA), 2013: 1-6.

[11] 郭稳涛,郑剑,李兵.一种高效的RFID系统冗余阅读器消除算法[J].东北师大学报(自然科学版),2018,50(3):72-78.

Identification Algorithm for Redundant Reader of RFID System Based on Middleware

Chen Yang1,3Chen Jianze1Li Chao2

(1.Guangdong Yunban Intelligent Technology Co., Ltd, Guangzhou 510000, China 2.South China University of Technology, Guangzhou 510000, China 3. Guangdong Computer Academy, Guangzhou 510000, China)

In large-scale RFID system, redundant reader identification is an important way to optimize system performance. Firstly, the existing RFID system redundant reader identification algorithms are analyzed and compared; then, combined with the characteristics of each identification algorithm, a middleware based RFID system redundant reader identification algorithm is proposed. Simulation results show that the proposed MNRCBA algorithm can effectively improve the detection rate of redundant readers, and has better system deployment rationality.

RFID; middleware; redundant reader; identification algorithm

TP391.44

A

1674-2605(2021)02-0004-06

10.3969/j.issn.1674-2605.2021.02.004

陈阳，男，1984年生，高级工程师，主要研究方向：计算机、电子信息技术应用等。E-mail: gdcc_chenyang@foxmail.com