一种RFID网络系统中消除冗余阅读器的高效算法

徐伟，杨智应

（上海海事大学信息工程学院，上海　201306）

一种RFID网络系统中消除冗余阅读器的高效算法

徐伟，杨智应

（上海海事大学信息工程学院，上海201306）

0　引言

RFID是射频识别技术 （Radio Frequency Identification）的英文缩写。射频识别技术是一种自动识别技术，最早盛行于20世纪90年代。目前该技术在世界范围内正被广泛应用，成为21世纪全球自动识别技术发展的主要方向。它主要包括两大块，RFID收发器（阅读器）和RFID应答器（标签）。事实上，RFID系统已经被应用于门禁系统、视频溯源、产品防伪等领域。例如2006年的德国世界杯以及2010年的上海世博会就采用了RFID技术用于门票的防伪。所以RFID系统的便利性使其被广泛应用于不同领域中［3，7］。

在密集部署的RFID网络中，密集的阅读器容易造成相互干扰。因为两个或更多的相邻的阅读器的射频信号可能会重叠和干扰。因此，过多的不必要的阅读器消耗了有限的功率。所以如何使用最少数量的阅读器有效地覆盖每一个标签，这就是冗余阅读器消除问题，冗余阅读器消除问题是一个RFID系统中的基本问题。冗余阅读器消除问题已经被证明是NP-hard问题［1］。

冗余阅读器消除问题一直在被广泛的研究。在本文中，我们利用RRE算法优先选择覆盖标签数多的阅读器为非冗余阅读器的原理，对CBA算法进行了改进，提出了一种高效的冗余阅读器消除算法SCBA。在算法SCBA中，一个拥有最少标签且该阅读器范围［2］内的标签都与相邻阅读器共享的阅读器被判定为冗余阅读器。为了证实所提出的方法的性能，我们还对RRE、LEO和CBA等方法进行了模拟实验。实验证实了算法SCBA能比算法RRE、LEO和CBA能消除更多的冗余阅读器。

1　相关工作

在RFID的碰撞中最重要的问题是信号冲突，它可以分为两种：标签信号的冲突和阅读器信号冲突。RFID系统通常使用CDMA、FDMA和TDMA解决冲突问题，如改进的ALOHA［2，6］算法就是用来避免RFID碰撞［10］。Colorwave则是基于应用理论TDMA来避免冲突。基于TDMA，还有一些学者提出利用标签的识别码来避免标签冲突，他们的算法基于曼彻斯特编码，类似于一个二进制搜索。

为了避免冲突，另一种解决方案则聚焦于减少阅读器的数量。因为冗余的阅读器不仅增加RFID系统负载，而且也导致了有限能源的浪费。

在RFID网络中，如果一个阅读器内的所有标签都被涵盖在至少一个其他的阅读器中，该阅读器就是多余的。如图1所示的一个冗余阅读器在RFID网络中的典型例子。它由三个阅读器R1到R3和五个标签T1 到T5组成。标签T2，T3，T4被R2覆盖的同时又被R1和R3分别覆盖。因此，R2是一个冗余阅读器，它可以在不违反完全覆盖标签的同时被消除，同时又提高了RFID网络质量。

图1　RFID系统冗余阅读器举例

在解决冗余阅读器问题上，RRE［1］和LEO［7］是最有代表性的算法。

（1）RRE

RRE（冗余阅读器消除算法）［1］算法是第一个分布式算法，是由美国普渡大学Bogdan Carbunar等人在2005年提出的。RRE是基于贪心算法设计的。RRE算法的目的是运用最少的阅读器去读取所有的标签。

算法RRE描述如下：

①每个阅读器尝试把他的标签计数count（覆盖的标签数）写到它覆盖的所有标签里。每个阅读器发出一个包含它的阅读器标识符和标签计数的写命令。每个RFID标签仅存储所知的标签计数最高值和相应阅读器的标识。每个阅读器问询区里的标签正确接收其发的写命令。RFID系统里的标签就会在存储单元中存储覆盖该标签同时又覆盖有最大标签数的阅读器ID，并将这个阅读器ID标记为标签的持有者（holder）。

②阅读器查询其问询区里的每个标签，读覆盖区域内的标签持有者的标识。至少锁定一个标签的阅读器必定非冗余，将保持活动状态。而没有锁定任何标签的阅读器被标记为冗余阅读器，可以被安全关闭。

RRE算法相对来说是一个比较独立的算法，但是当阅读器和标签的通信半径超过一定值时，阅读范围的重叠情况就会非常严重，因为它没考虑相邻阅读器的因素，所以监测冗余阅读器的效率就大大降低了，此时覆盖多的标签的阅读器反而更可能为冗余阅读器。

（2）LEO，LEO+RRE

LEO算法（消除分层优化）［8］是于2007年在Asia-Pacific Service Computing Conference会议上被提出来的。LEO的原则是“先到先得”。所有的阅读器发送请求到在其覆盖区内的标签并得到标签记录。如果标签不属于任何其他阅读器，该阅读器就成为该标签的所有者。如果标签已经有了一个阅读器的ID，则该ID不能被改变。最后，一个标签都没有的阅读器就是冗余阅读器。

LEO算法和其他算法相比可以有效的减少读写操作，但是LEO算法是随机的决定标签的拥有者，因此标签拥有者的选择的质量是不可靠的。

在LEO算法被提出后，有人提出了一个LEO+ RRE构想，即当一个RFID系统由LEO算法执行完毕后，剩余的非冗余阅读器可以再由RRE算法进行过滤。整个的冗余阅读器的总数为LEO和RRE算法所识别的最终结果。这个被称为LEO+RRE算法。

因为LEO的读写操作比RRE小，所以先LEO后RRE，大量冗余阅读器在LEO阶段被去除，RRE在第二阶段才会有较小的读写操作，不过这个算法还是没有解决RRE，LEO算法的根本性缺陷。

（3）FSR

针对算法RRE和算法LEO的缺点，FSR［5］算法于2010年在 Proceedings of the 9th WSEAS International Conference on Software Engineering会议上被Hung J W，Li I H.等人提出。假设每个标签计算覆盖其的阅读器总数为rc。每个阅读器记录其问询区内所有标签数为tc1。如果标签的rc是1，那么把唯一的阅读器的id写进这个标签里面。并把该阅读器内所有的标签holder改为该阅读器。每个阅读器用系统内所有标签总数减去自己的tc1，得到值tc2，tc2值越小的阅读器在系统搜索中优先权越大。

算法FSR首次采用了启发式策略搜索，在算法一开始找出只被一个阅读器覆盖的标签，因为只被一个阅读器覆盖的标签的对应阅读器一定是非冗余阅读器，所以该启发策略是完备的。

算法FSR在启发式策略搜索中找出了RFID网络系统中一定是非冗余的阅读器，再进行加上优先权级后的算法RRE。启发策略改变了网络拓扑结构，所以算法FSR不一定能比算法RRE找出更多的冗余阅读器。而且由于要在启发式策略中记录覆盖当前标签的阅读器数量，RRE算法中必须要重写标签中记录的覆盖当前标签的阅读器问询区内的标签数，所以大大增加了写操作数多。

2　算法的提出

与以上提到的几种算法相比，算法CBA（Count Based Algorithm）［11］的提出则创造性的采用逆向思维，通过存储在标签里的记录该标签被多少阅读器所覆盖的tagcount的不停加减，可以达到先消除系统里面一定是冗余阅读器的那些阅读器。同时在tagcount的不停变化时，也采用启发策略使得算法CBA可以保证每次选择的非冗余阅读器一定是非冗余的阅读器，因此该算法取得了比较好的检测性能。

算法CBA的运行步骤如下：

①先计算RFID系统中每个标签有多少阅读器覆盖它，将结果记为count，存储在标签的存储器中。第二步：启发式策略，每个阅读器给它的覆盖区域里所有标签发送查询信号，如果其中有某个标签的count=1，那么当前阅读器锁定它覆盖区域里的所有标签。第三步，如果阅读器覆盖区域里面的所有标签的count＞1，意味着该阅读器不一定是这些标签的holder。则该阅读器被标记为冗余阅读器，该冗余阅读器发送写信号到它问询区里所有标签，将覆盖区域内标签的count值都减1，然后关闭此阅读器。第四步，RFID系统里另一个阅读器发送查询信号到它覆盖的区域里面，探测是否有count=1的标签，重复第二步和第三步直至系统里所有阅读器都发送过查询信号。

图2　RFID冗余阅读器举例

按照上述步骤对图2进行冗余阅读器的消除可得：

表1中的数据X1，X2，X3，X4，X5，X6没有给出确切的答案的原因是，通过CBA算法我们其实是无法准确的判断其余标签应该属于哪个阅读器的。

表1　CBA算法结果（R_Reader中R即Redundant）

假设图2中的RFID系统执行了CBA算法的第一、二步处理，因为T3的count为1所以R2必不为冗余阅读器，所以T1和T4也被锁定，那么接下来在执行第三步的时候我们该从哪个阅读器开始呢？

图3　图2执行完CBA第一、二步后结果

从图3中我们看到R1，R4，R3中的标签它们的count都大于1，那么这三个阅读器的读取顺序的不同将导致得出的冗余阅读器的数量有很大的差异。

假设我们从R4阅读器开始执行第三步，我们发现T2，T5，T6，T7的count都为2（大于1），则R4被判断为冗余阅读器，关闭此阅读器。T2，T5，T6，T7的count都减1，变为了1，然后又回归到第二步开始重新执行，因为T2，T5，T6，T7的count都为1，所以R1，R3不为冗余阅读器。

可是假设我们从R1开始执行第三步，因为T2的count为2所以R1为冗余阅读器，R1被关闭。此时T2 的count变成了1，所以R4不是冗余阅读器所以T5，T6，T7被锁定，所以R3也是冗余阅读器。所以如果从R1开始，R1和R3则变成了冗余阅读器。

两个不一样的执行顺序则导致了两个截然相反的结果。很明显从结果看来第二个假设得出的结果才是我们想要的。

其实原理很简单，从图3我们可以看到，如果我们不用CBA来判断，而用最简单的RRE就可以得出结果，我们在判断一个阅读器是否是冗余阅读器的时候，我们希望那些非冗余阅读器能尽量覆盖更多的标签，也就是一个有效的阅读器尽量读更多的标签，这样才能使RFID系统更高效。

只是RRE算法是先确定非冗余阅读器为先决条件的算法，而CBA算法是先确定冗余阅读器为先决条件的算法，所以只要在CBA算法中嵌入RRE算法的判断准则，在进行完基于启发式策略的第二步后，加入一个类RRE算法判决，那么该算法将比原有的算法得出更好的结果。我将此算法命名为SCBA算法。

算法SCBA的基本操作步骤如下：

①RFID系统中每个标签计算有多少阅读器覆盖它，即可以和它通信阅读器的数量，将结果记为tagcount，存储在标签的存储器中。

②每个阅读器的覆盖信息即每个阅读器读到了多少标签结果记为readercount，则被发送到中心主站。

③阅读器给它的覆盖区域里所有标签发送查询信号，如果有某个标签的count=1，那么当前阅读器锁定它覆盖区域里的所有标签，该阅读器为非冗余阅读器。

④将已经确定了的阅读器排除，从剩余的阅读器中，按readercount从小到大开始选择阅读器，如果阅读器覆盖区域里面的所有标签的tagcount＞1，意味着没有标签一定要被当前阅读器hold。则当前阅读器被标记为冗余阅读器，该冗余阅读器发送写信号到它问询区里所有标签，将标签的count值减1，然后关闭此阅读器。

⑤RFID系统里另一个阅读器发送查询信号到它覆盖的区域里面，以探测count=1的标签，重复②至④直至系统里所有阅读器都发送过查询信号。

3　算法的实验与分析

为了评估所提出的冗余阅读器消除算法性能，我们用MATLAB 2012b仿真了RFID网络环境并随机部署RFID阅读器和标签节点。我们评估的指标是冗余阅读器的数量，较高的冗余阅读器数量预示着算法的高效性。

（1）标签数量变化对冗余阅读器的影响：针对标签数的不同对RRE，LEO，CBA，SCBA的性能进行测试。该1000×1000平方米的实验区采取400随机阅读器，标签数量分别为从1000提高到5000。阅读器的读写半径设置为30。如下图为各算法条件下的去冗余结果。

从图4中可以看出，在阅读半径和阅读器数量不变的前提下，随着标签数的增加，各个算法消除的冗余阅读器数量都呈下降趋势。同时SCBA和CBA的差距也趋于减小，因为当RFID系统变成高密度的网络环境时，本来是冗余的阅读器覆盖到了新的标签，使其变为了非冗余阅读器。从图上可以看出SCBA的性能明显的高于RRE，LEO算法，和CBA相比消除冗余阅读器的性能也有了明显提升，所以SCBA算法还是最优的。

图4　标签数量变化情况下各算法性能比较

（2）阅读器数量变化对冗余阅读器的影响：针对阅读器数量的不同对RRE，LEO，CBA，SCBA的性能进行测试。该1000×1000平方米的实验区采取2500个随机标签，阅读器数量分别为从100提高到600。阅读器的读写半径设置为30。如下图为各算法条件下的去冗余结果。

图5　阅读器数量变化情况下各算法性能比较

从图5中可以看出在阅读半径和标签数量不变的前提下，随着阅读器数量的增加，所有的算法消除冗余阅读器的数量都在增加，呈上升趋势。这是因为阅读器数量增多，标签数量不改变的情况下，冗余的阅读器数量必然增多。同时从图中我们可以看出SCBA算法的性能同样要优于RRE，LEO和CBA算法。

（3）阅读半径的变化对冗余阅读器的影响：

针对阅读器阅读半径的不同对RRE，LEO，CBA，SCBA的性能进行测试。在1000×1000平方米的实验区内部署了2500个随机标签和400个随机阅读器，阅读器的有效读取半径为从为10，20，30，40，50。如下图为各算法条件下的去冗余结果。

图6　阅读半径变化情况下各算法性能比较

由图6可知，随着阅读半径的增长，冗余阅读器数量逐渐减少。当阅读半径增加到一定值时，所有算法检测出的冗余阅读器数量都增大。这是因为随着阅读半径的增大，用更少的阅读器就可以覆盖当前网络中的所有标签。本文提出的算法SCBA的性能之所以在阅读半径增大时比CBA算法有明显的提升，就是因为SCBA算法优先选择覆盖标签数多的阅读器为非冗余阅读器。所以SCBA算法的性能比RRE，LEO，CBA算法都要好。

4　结语

本文提出的算法SCBA继承了CBA原有的优点，确保每次选择的冗余阅读器一定是冗余阅读器，又融入了类RRE算法的优点。和RRE，LEO，CBA等算法相比提升了RFID冗余阅读器消除的性能。但是在读写操作方面，由于需要不间断改写标签的tagcount信息，因此写操作数偏多，同时需要对阅读器进行排序也增加了系统的负担，但是综合起来，比起当前的其他算法SCBA应用前景还是比较广泛的。

［1］B.Carbunar，M.K.Ramanathan，M.Koyuturk，C.Hoffmann，A.Grama，“Redundant Reader Elimination in RFID Systems，”SecondAnnual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks，2005，Page（s）：176-184.

［2］Jae-Ryong Cha，Jae-Hyun Kim.Dynamic Framed Slotted ALOHA Algorithms Using Fast Tag Estimation Method for RFID System. Consumer Communications and Networking Conference，2006，Page（s）：768～772

［3］C.Floerkemeier，C.Roduner，M.Lampe.RFID Application Development With the Accada Middleware Platform，”IEEE Systems Journal，2007，Page（s）：82～94

［4］Ziming Guo，Binjie Hu.A Dynamic Bit Arbitration Anti-Collision Algorithm for RFID System.IEEE International Workshop on Anticounterfeiting，Security，Identification，2007，Page（s）：457～460

［5］Hung J W，Li I H，Lin H H，et al.The First Search Right Algorithm for Redundant Reader Elimination in RFID Network［C］.Proceedings of the 9th WSEAS International Conference on Software Engineering，Parallel and Distributed Systems（SEPADS）.2010：177～183

［6］Xu Huang，Son Le.Efficient Dynamic Framed Slotted ALOHA for RFID Passive Tags.The 9th International Conference on Advanced Communication Technology，2007，Page（s）：94～97

［7］Tatsuya Inaba.Impact Analysis of RFID on Financial Supply Chain Management.IEEE International Conference on Service Operations and Logistics，and Informatics，2007，Page（s）：1～6

［8］Ching-Hsien Hsu，Yi-Min Chen，Chao-Tung Yang.A Layered Optimization Approach for Redundant Reader Elimination in Wireless RFID Networks.IEEE Asia-Pacific Services Computing Conference，2007，Page（s）：138～145

［9］Leian Liu，Zhenhua Xie，Jingtian Xi，Shengli Lai.An Improved Anti-Collision Algorithm in RFID System.2nd International Conference on Mobile Technology，Applications and Systems，2005

［10］J.Waldrop，D.W.Engels，S.E.Sarma.Colorwave：an Anticollision Algorithm for the Reader Collision Problem.IEEE International Conference on Communications，2003，Page（s）：1206～1210

［11］Shuyuan Pan，Zhiying Yang.A Count Based Algorithm for Redundant Reader Elimination in RFID Application System，Intelligent System Design and Engineering Applications（ISDEA），2013 Third International Conference on，vol.，no.，pp.30，33，16-18 Jan.2013

Redundant Reader Elimination；RRE；LEO；CBA；SCBA

Efficient Algorithm for Redundant Reader Elimination in RFID Networks

XU Wei，YANG Zhi-ying
（College of Information Engineering，Shanghai Maritime University，Shanghai 201306，China）

1007-1423（2015）17-0036-06

10.3969/j.issn.1007-1423.2015.17.008

徐伟（1991-），男，江苏南通人，硕士研究生，研究方向为算法设计与分析、并行与分布式计算、移动自组网、RFID传感器网络与物联网

2015-04-14

2015-05-14

在多阅读器RFID网络系统中，冗余阅读器消除问题已被人们所关注，有许多算法和优化技术用来消除RFID系统中的冗余阅读器。在深入分析算法CBA的基础上提出新的算法SCBA以克服其不足之处。仿真实验表明，该算法SCBA比算法CBA、LEO、RRE能消除更多的冗余阅读器。

冗余阅读器消除；RRE；LEO；CBA；SCBA

杨智应（1964-），男，博士，教授，研究方向为算法设计与分析、并行与分布式计算、移动自组网、RFID传感器网络与物联网

In multi-reader RFID network systems，the problem of eliminating redundant readers attracted the attention of many researchers.There are many algorithms and optimization techniques to eliminate redundant readers in RFID system.Proposes SCBA algorithm to overcome the disadvantages of CBA algorithm.Simulation experiments show that algorithm CBA has better performance than other algorithms such as CBA，LEO and RRE.