一种基于中间件的RFID阅读器去冗余高效算法

何 涛，刘 畅，徐 鹤，周 凯

(1.南京邮电大学 电子科学与工程学院，江苏 南京 210003; 2.南京邮电大学 计算机学院，江苏 南京 210003)

一种基于中间件的RFID阅读器去冗余高效算法

何 涛1，刘 畅1，徐 鹤2，周 凯1

(1.南京邮电大学 电子科学与工程学院，江苏 南京 210003; 2.南京邮电大学 计算机学院，江苏 南京 210003)

射频识别(RFID)技术近年来变得越来越复杂，同时应用领域也更加广泛。冗余阅读器是影响系统性能指标的基本问题之一，其存在给RFID系统造成了极大的负担，并降低了获取信息的准确度。消除冗余阅读器是优化多阅读器RFID系统性能的重要途径。在现有的去除冗余阅读器算法的基础上，分析已有多种算法的优缺点，并结合其优点提出了新的算法思想，再将新算法与RFID中间件技术相结合，提出了基于中间件的改进算法，通过中间件处理计算数据而无需阅读器对标签有过多的读写操作和计算能力。从不同阅读器数量、不同标签数量、不同读取半径三个方面对提出算法进行了仿真验证实验。仿真实验结果表明，提出算法在找出的冗余阅读器的数量上具有较明显的优势，其去冗余性能较现有的其他算法更优。

射频识别；中间件；冗余阅读器；标签

0 引 言

RFID(Radio FrequencyIDentification)技术，又称无线射频识别，是一种通信技术，可通过无线电讯号识

别特定目标并读写相关数据而无需识别系统与特定目标之间建立机械或光学接触。目前，RFID应用的大部分实际需求中，各式各样的应用软件要实现跨平台应用,又或是一个平台要管理和支持多种系统或应用软件,这需要应用系统和软、硬件平台间有可供数据传送的稳定高效的枢纽,以保证系统的有效性[1]。因此，对于RFID中间件的研究必不可少。同时，在RFID系统中，冗余阅读器的存在极大地降低了系统的性能，增加了能源消耗[2]。

在分析研究现有去除冗余阅读器算法的基础上，在CBA算法找出的冗余阅读器一定是冗余阅读器的前提下，运用RRE算法的思想对剩余阅读器进行排序选择，同时，根据NCD算法的优点改进RRE算法对选择排序的具体实现，再运用中间件技术，将运算排序等步骤的实施均移至中间件操作，以减轻系统负担，降低能耗。并且该算法无需系统拓扑信息，也无需阅读器对标签进行写入操作，且排除冗余阅读器的性能更优。

1 相关工作

冗余阅读器是影响RFID系统性能的基础问题之一。在RFID系统中，需要解决一个最基本的问题：信号碰撞。其可分为两种：阅读器信号碰撞和标签信号碰撞。一般可以使用SDMA、FDMA、TDMA解决碰撞问题[3-5]，而减少碰撞的另一个方案就是减少阅读器的数量，即去除冗余阅读器。寻求去除冗余阅读器的最佳方案已被证明是NP-hard问题[6]。阅读器去冗余算法的目的是使区域内工作阅读器的数量降至最低,以改善系统性能。

定义：在RFID系统中，当某个RFID阅读器覆盖一组RFID标签，而此组内的标签同时被其他阅读器所覆盖，则此阅读器是冗余的，称为冗余阅读器[7]。

如图1所示，R1、R2、R3、R4是RFID网络中的四个阅读器的读取范围，T1、T2、T3、T4是其中的4个标签，其后示例图以此类推。

图1 冗余阅读器示意图

从图1可以看出，即使将R1、R3、R4暂时关闭，4个标签依然能被R2全部读取，此时R1、R3、R4即为冗余阅读器。

1.1 RRE(Redundant Reader Elimination)

在RFID领域，Carbunar等提出RRE算法[6]去除冗余阅读器。其步骤如下：将阅读器读取范围内的标签数量作为权重，让具有较大权重的阅读器优先将读取范围的标签锁定，并写入锁定信息，迭代运行直至所有标签都被锁定，一个标签都未锁定的阅读器即为冗余阅读器。

以图1为例，T1(1，R1)(4，R2)表示标签T1被R1、R2读取且R1读取范围内只有1个标签，R2读取范围有4个标签，那么：T2(4，R2)(1，R3),T3(4，R2)(2，R4),T4(4，R2)(2，R4),根据RRE算法，优先选择具有最大权重的阅读器，因此被锁定的有：T1(4，R2)、T2(4，R2)、T3(4，R2)、T4(4，R2)，即R1、R3、R4为冗余阅读器。

1.2 LEO(Layered Elimination Optimization)

LEO算法[8]是于2007年在AsiaPacific Service Computing Conference上提出的。其原则是“先到先得”，即所有阅读器发送请求到在其覆盖区内的标签并取得标签记录。如果有标签不属于其他任何阅读器，那么该阅读器就成为这个标签的所有者。如果标签已经有了一个阅读器的身份信息，则该身份信息不能被改变。最后，一个身份信息都没有被记录的阅读器就是冗余阅读器。

仍以图1为例，T1首先被R1读取并记录，T2被R3读取并记录，T3、T4被R4读取并记录，此时R2发送的请求无法记录任何一个标签，因为所有标签均已记录其他阅读器ID,此时R2为冗余阅读器。

上述RRE、LEO算法提出后，又有人提出RRE+LEO算法，即执行完LEO算法后，对判定后的非冗余阅读器再进行RRE算法过滤，最后LEO和RRE算法找出冗余阅读器的并集就是总的冗余阅读器数量[9-11]。

1.3 CBA(Count Based Algorithm)

CBA[12]算法创造性地采用了先找出的一定是冗余阅读器的思想，通过逐步关闭冗余阅读器同时减少标签计数，得到最终结果。其步骤如下：

(1)所有阅读器向读取范围内的所有标签发送查询信息包，每个标签记录一共有多少阅读器可读取到它们，记为count。

(2)阅读器发送查询信号，标签返回自身count,如果一个阅读器收到的标签信号中有count=1，则该阅读器锁定其读取范围所有标签。

(3)如果一个阅读器收到各个标签返回的信号的所有count都大于1，则表示没有标签一定要被该阅读器锁定，此阅读器被判定为冗余阅读器，并且此阅读器读取范围的所有标签的count值减1，可暂时关闭此阅读器。

(4)另一个阅读器继续发送查询信号，重复步骤直到所有阅读器均查询完毕。

2 新算法的提出

若RFID系统中阅读器部署比较密集，多个阅读器之间交叉发生冲突，并且阅读器射频范围的标签数目相同时，使用RRE算法无法得到最优的冗余阅读器，如图2所示。

图2 RRE算法缺点分析图

通过分析图2，得到表1。

表1 RRE算法分析结果

表1中结果面前的数字代表这一行的阅读器能读取到的标签数量。

由图2可以看出，在理想情况下，仅使得R2、R4工作即可，但使用RRE算法时，如表1所示，由于R2、R3、R4覆盖4个不同集合的标签，算法认为这并不冗余，因此不得不让3个阅读器都工作。

LEO算法的缺点：由于LEO算法只依赖于阅读器的识别顺序，因此会将R2视作冗余阅读器而让R1、R3、R4工作，显然这是不合理的。

CBA算法的缺点：在所有标签count均大于1时，若先判定R1为冗余阅读器，剩余阅读器选择的顺序具有随机性，不同的选择顺序直接导致最后的冗余阅读器的判定结果不同。

这些算法除了上述分析的缺点之外，其共性包括：

(1)阅读器与标签一对一的写入方式。

(2)阅读器对标签进行读写操作来交互信息的通信方式。

(3)阅读器对标签的读写距离不等的特性，都会导致算法误判、漏判冗余阅读器并使系统功率消耗过大。

因此，在CBA算法的基础上，借鉴了吕石磊等提出的利用中间件存储分析标签阅读器信息的思想[13]，并根据RRE算法的思想改进CBA算法在选择阅读器时的随机性，运用RRE算法的同时，舍弃RRE以最大值为权重的方法，结合NCD(Neighboring Coverage Density)算法[14]提出一种更精确的加权算法，即MCBA(Middleware Count Based Algorithm)。

该算法对系统有如下要求：

(1)阅读器可读取到其射频范围内所有标签。

(2)RFID中间件可储存并处理阅读器本身信息及其发送的标签信息。

MCBA步骤如下：

(1)阅读器读取其范围内的标签信息传给中间件，中间件接收并存储阅读器发送的标签信息。

(2)建立“阅读器-标签”矩阵M，定义为：

其中，Tj∈Ri表示阅读器Ri可读取标签Tj，反之Tj∉Ri表示标签Tj不在阅读器Ri的读取范围内。

(3)计算矩阵M各行及各列的和，可得出一个阅读器能读取的标签个数(readercount)及一个标签被多少阅读器覆盖(tagcount)。

(4)找出tagcount=1的标签j，此列在M矩阵中值为1的标签被对应的阅读器i锁定，i为非冗余阅读器。

(5)定义相邻覆盖密度为：

(6)重复步骤(4)和(5),直到系统内所有阅读器都发送过查询信号。

通过分析图2可得新的加权方法具有更高的精确性。对于R2(R4同R2)，其相邻阅读器是R1和R3，因此DR2=2+4=6,WR2=4/6≈0.66。对于R3，它的相邻阅读器是R2和R4，因此DR3=4+4=8，WR3=4/8=0.5。可以看出WR2大于WR3，即R2为冗余阅读器的可能性更小，与实际情况一致。因此，运用新的权重排序，较小权重的阅读器更有可能是冗余阅读器，相比RRE以最大值为权重得到的结果会更加精确。

MCBA算法的伪代码如下：

forj=1 totagnumber

fori=1 to readernumber

if (M(i,j)=1 and tagcount=1)

Tagholder(j)←readerID(i);

end

end

end

while(reader(b)∈neighboring_reader(a)) do

end

form=1 toreadernumber by sorted(Weight)

if (reader(m) unlocked)

forn=1 to tagnumber

if (M(m,n)=1 and tagcount=1)

TagHolder(n)←ReaderID(m)

Tags in Readerradius(m) hold by Reader(m);

end

else Reader(m)∈RedundantReader;

end

forn=1 to tagnumber

if (M(m,n)=1 and reader(m)∈RedundantReader)

Tagcount(n)--;

end

end

end

end

3 算法实验及分析

为了更好地分析MCBA算法的性能，设计实验以验证各算法的去冗余效果。实验环境基于Matlab7，在1 000*1 000的固定区域里，随机生成阅读器和标签节点的位置。通过比较算法得出的冗余阅读器的数量来分析判断算法RRE、LEO、CBA、MCBA的优劣。每次结果均取100次仿真实验结果的均值。算法实验见图3。

图3 算法比较

(1)分析阅读器数量的变化对四种算法找出的冗余阅读器数量的影响。标签数量取定为2 500，阅读器读取半径为30，阅读器数量由100依次以100为基数递增到600，结果见图3(a)。

从图3(a)中可以看出,在阅读器读取半径和标签数量不变的情况下，阅读器数量增加，各算法找出的冗余阅读器数量均增加。分析可知，当阅读器总数增多而标签个数不变时，新增的阅读器或是冗余，或是覆盖已记录的标签，使原本非冗余阅读器被判定为冗余，所以冗余阅读器数量一定增加。其中，MCBA算法去冗余的性能优于其他三种算法。

(2)在阅读器读取半径和阅读器数量不变的情况下，分析研究标签数量的增加对不同算法去冗余效率的影响。选定阅读器读取半径为30，阅读器数量为400，标签数量由1 000以1 000为基数依次递增为6 000。图3(b)为不同算法在不同标签数目下找出的冗余阅读器的个数。

从图3(b)可以看出，在阅读器读取半径和阅读器数量不变的情况下，随着标签数量的增加，四种算法找出的冗余阅读器数量均呈下降趋势。因为在标签越来越密集的情况下，之前的冗余阅读器因为覆盖了新增的标签而成为非冗余阅读器。从仿真结果可以看出，MCBA优于CBA及另外两种算法。

(3)分析在标签数量和阅读器数量恒定的情况下，阅读器半径大小对四种算法去冗余性能的影响。结果如图3(c)所示。

由图3(c)分析可知，在标签数量和阅读器数量不变的前提下，阅读器读取半径逐步增大，找出的冗余阅读器先减少，当半径增加到一定值时，冗余阅读器数量开始增加。当阅读器读取半径增加时，原来未被某阅读器覆盖的标签会因此进入该阅读器射频范围，即用较少的阅读器即可读取相同数量的标签，因此找出的冗余阅读器必然增加。其中，MCBA在半径增加时去冗余性能比CBA有明显优势，就是因为选择了合适的权重对剩余阅读器进行排序，让系统优先选择更可能是冗余阅读器的阅读器进行计算。所以MCBA算法的性能比另外三种都要好。

(4)通过实验对比观察RFID系统应用MCBA算法后的效果。取定阅读器数量为400，标签数量为2 500，阅读器读取半径为50。实验对比结果如图4所示，其中圆圈代表阅读器读取范围，点代表标签。

图4 应用MCBA算法前后系统网络图

通过对比很容易看出，在运用MCBA算法后，RFID系统的标签-阅读器网络拓扑简洁了很多，由此降低了能耗，同时避免过多的碰撞问题。

另外，采用的是阅读器对标签的读距离和写距离1∶1进行实验，而实际中阅读器对标签的写距离是小于读距离的[15]，这又会使RRE、LEO和CBA算法的去冗余性能有所下降，而MCBA不需要阅读器对标签进行写操作，因此不会受到影响。

4 结束语

为高效地解决RFID网络冗余阅读器问题，提出了基于中间件技术的MCBA算法。该算法运用相邻覆盖密度的概念给阅读器加上权重来选择阅读器，屏蔽了CBA算法选择阅读器的随机性，并引入中间件减轻了阅读器和标签的负担。实验结果表明，与RRE、LEO及CBA算法相比，MCBA算法在找出的冗余阅读器的数量上，具有明显优势，且其去冗余性能更优。

[1] Floerkemeier C,Roduner C,Lampe M.RFID application development with the Accada middleware platform[J].IEEE Systems Journal,2007,1(2):82-94.

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

[3] Waldrop J,Engels D W,Sarma S E.Colorwave:an anticollision algorithm for the reader collision problem[C]//IEEE international conference on communications.[s.l.]:IEEE,2003:1206-1210.

[4] Ferrero R,Gandino F,Montrucchio B,et al.Improving Colorwave with the probabilistic approach for reader-to-reader anti-collision TDMA protocols[J].Wireless Networks,2014,20(3):397-409.

[5] Hsu C H,Yu C H,Chung C Y,et al.An overlap aware technique for redundant reader elimination[C]//9th international conference on ubiquitous intelligence & computing and autonomic & trusted computing.[s.l.]:IEEE,2012:357-360.

[6] Carbunar B,Ramanathan M K,Koyuturk M,et al.Redundant reader elimination in RFID systems[C]//Second annual IEEE communications society conference on sensor and ad hoc communications and networks.[s.l.]:IEEE,2005:176-184.

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

[8] Hsu C H,Chen Y M,Yang C T.A layered optimization approach for redundant reader elimination in wireless RFID networks[C]//2nd IEEE Asia-Pacific service computing conference.[s.l.]:IEEE,2007:138-145.

[9] Zailani S, Iranmanesh M, Nikbin D,et al.Determinants of RFID adoption in malaysia’s healthcare industry:occupational level as a moderator[J].Journal of Medical Systems,2015,39(1):1-11.

[10] Zheng Feng,Kaiser T.Adaptive Aloha anti-collision algorithms for RFID systems[J].EURASIP Journal on Embedded Systems,2016(1):1-14.

[11] Joo Y I,Seo D H,Kim J W.An efficient anti-collision protocol for fast identification of RFID tags[J].Wireless Personal Communications,2014,77(1):767-775.

[12] Pan Shuyuan,Yang Zhiying.A count based algorithm for redundant reader elimination in RFID application system,intelligentsystem design and engineering applications[C]//Third international conference on intelligent system design and engineering applications.[s.l.]:[s.n.],2013:30-33.

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

[14] Ma M,Wang P,Chu C H.A novel distributed algorithm for redundant reader elimination in RFID networks[C]//IEEE international conference on RFID-technologies and applications.[s.l.]:IEEE,2013:1-6.

[15] Nikitin P V,Rao K V S,Martinez R,et al.Sensitivity and impedance measurements of UHF RFID chips[J].IEEE Transactions on Microwave Theory and Techniques,2009,57(5):1297-1302.

An Efficient Middleware-based Algorithm for Redundant Reader in RFID System

HE Tao1,LIU Chang1,XU He2,ZHOU Kai1

(1.College of Electronic Science and Engineering,Nanjing University of Posts and Telecommunications,Nanjing 210003,China; 2.College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

RFID technology has become more and more complex as well as more and more extensive application areas in recent years.Redundant reader is one of the fundamental issues that affect the performance of system,which could bring a great burden to the RFID system and reduce the accuracy of information obtained.It is an important approach to eliminate redundant readers for performance optimization of multi-reader RFID system.According to this consideration,on the analysis of existing algorithms and the advantages and disadvantages of multi algorithms to remove redundant readers,a new algorithm idea has been introduced with the advantages of existing algorithms and thus an improved algorithm with RFID middleware has been presented which has been integrated with RFID middleware technology.All data have been treated with middleware and without more reading/writing operation and computation capacities of reader for the tags.The result of the experiment has verified that the algorithm proposed has a great advantage in finding redundant readers and it has better performance than other existing algorithms.

radio frequency identification;middleware;redundant reader;tag

2016-06-07

2016-10-13 网络出版时间：2017-04-28

国家自然科学基金资助项目(61602261)；中国博士后科学基金(2014M561696)；江苏省自然科学基金(BK20140886)；江苏省高校自然科学研究面上项目(14KJB520030)；江苏省博士后科研资助计划项目(1401005B)；江苏省研究生科研创新计划(SJLX15_0381)；南京邮电大学引进人才科研启动基金(NY213034)；南京邮电大学自然科学基金(NY214060，NY214061)

何 涛(1972-)，男，讲师，研究方向为无线传感器网络及大数据；刘 畅(1991-)，男，硕士研究生，研究方向为射频识别技术。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170428.1702.022.html

TP301.6

A

1673-629X(2017)06-0027-05

10.3969/j.issn.1673-629X.2017.06.006