基于中間件的RFID系統(tǒng)冗余閱讀器判別算法

陳陽 陳堅澤 李超

學術(shù)研究

基于中間件的RFID系統(tǒng)冗余閱讀器判別算法

陳陽1,3陳堅澤1李超2

（1.廣東云伴智能科技有限公司，廣東 廣州 510000 2.華南理工大學，廣東 廣州 510000 3.廣東省計算機學會，廣東 廣州 510000）

在大規(guī)模RFID系統(tǒng)中，冗余閱讀器判別是系統(tǒng)性能優(yōu)化的重要途徑。首先，對現(xiàn)有的RFID系統(tǒng)冗余閱讀器判別算法進行分析和比較；然后，結(jié)合各判別算法的特點提出一種基于中間件的RFID系統(tǒng)冗余閱讀器判別算法。仿真實驗結(jié)果表明：本文提出的MNRCBA算法可有效提高冗余閱讀器的檢出率，且具有更好的系統(tǒng)部署合理性。

RFID；中間件；冗余閱讀器；判別算法

0 引言

射頻識別（radio frequency identification, RFID）技術(shù)以非接觸、低成本的特點廣泛應(yīng)用于倉儲管理、物流跟蹤和生產(chǎn)監(jiān)控等領(lǐng)域[1]。通常情況下，為防止RFID標簽漏讀，在工作區(qū)域布設(shè)盡可能多的閱讀器，以實現(xiàn)RFID標簽的全覆蓋。但這會造成大量冗余數(shù)據(jù)，影響RFID系統(tǒng)的整體性能。在RFID系統(tǒng)中，當某個RFID閱讀器覆蓋的所有標簽同時被其他閱讀器覆蓋時，該RFID閱讀器為冗余閱讀器。冗余閱讀器是產(chǎn)生冗余數(shù)據(jù)的重要來源之一[2]。為判別冗余閱讀器，降低RFID系統(tǒng)能耗，國內(nèi)外許多研究人員對RFID冗余閱讀器判別算法進行了研究。

經(jīng)典RFID冗余閱讀器判別算法包括冗余閱讀器消除法（redundant reader elimination, RRE）)[3]、分層消除優(yōu)化法（layered elimination optimization, LEO）[4]、基于計數(shù)的算法（count based algorithm, CBA）[5]。研究人員在經(jīng)典算法基礎(chǔ)上，通過組合或改進使判別結(jié)果更優(yōu)，如改進的冗余閱讀器消除方法（improvable redundant reader elimination, IRRE）[6]，RRE+LEO[7]，RRE+CBA[8]等。其中，呂石磊[9]提出基于中間的RFID系統(tǒng)閱讀器去冗余算法（middle -based redundant reader elimination, MRRE），利用RFID中間件的標簽信息判別冗余閱讀器，不需要系統(tǒng)拓撲信息及頻繁地對標簽寫入信息，有效減少其他判別方法因閱讀器對標簽頻繁寫入而導致的誤判或漏判冗余閱讀器問題，為冗余閱讀器判別方法研究開辟了新路徑。這些算法都以找到更多冗余閱讀器為目的，忽略了RFID閱讀器部署合理性問題，導致有時出現(xiàn)保留的冗余閱讀器干涉區(qū)域較大，產(chǎn)生較多干擾信號，影響RFID系統(tǒng)性能。通過研究相鄰閱讀器的性質(zhì)可解決該問題，如基于鄰近覆蓋密度法（neighboring coverage density, NCD）[10]、鄰近閱讀器競爭消除算法（neighbor-reader competitive elimination algorithm, NRCEA）[11]等。

本文在分析現(xiàn)有RFID冗余閱讀器判別算法的基礎(chǔ)上，總結(jié)各判別算法的特點，并提出一種基于中間件的RFID系統(tǒng)冗余閱讀器判別算法。首先，以CBA算法的啟發(fā)策略找出確定的非冗余閱讀器；然后，運用RRE思想對剩余的RFID閱讀器賦予權(quán)值，并結(jié)合NRCEA思想對賦權(quán)規(guī)則進行改進；最后，采用RFID中間件技術(shù)實現(xiàn)RFID冗余閱讀器的判別。

1 RFID冗余閱讀器相關(guān)研究

早在2009年，CARBUNAR等[3]首次提出冗余閱讀器是影響RFID系統(tǒng)性能的基礎(chǔ)問題之一，并指出即使在知道RFID系統(tǒng)拓撲的前提下，判別冗余閱讀器也是一個非確定多項式（non-deterministic polynomial, NP）問題。RFID冗余閱讀器判別算法的目的是使工作區(qū)域內(nèi)的RFID閱讀器，在實現(xiàn)區(qū)域標簽全覆蓋的同時數(shù)量最少、布局更合理、閱讀器間信號干擾更小，從而降低系統(tǒng)能耗，改善系統(tǒng)性能。

RFID系統(tǒng)示意圖如圖1所示，其中R1，R2，R3，R4是4個閱讀器，圓形表示RFID閱讀器的讀取范圍；T1，T2，T3，T4，T5是5個標簽。

圖1 RFID系統(tǒng)示意圖

由圖1可以看出：關(guān)閉閱讀器R3和R4，5個標簽仍然能被全部讀取，即R3和R4為冗余閱讀器。但R1和R2存在干涉區(qū)域，會產(chǎn)生干擾信號。如果關(guān)閉R2，保留R1，R3，R4，此時RFID系統(tǒng)實現(xiàn)5個標簽全覆蓋，且不存在干涉區(qū)域，避免干擾信號。

1.1 RRE算法

RRE算法[3]基于貪心算法設(shè)計，其關(guān)鍵思想是根據(jù)RFID閱讀器讀取的標簽數(shù)目對閱讀器進行賦權(quán)。該算法能夠較直觀和簡單地判別冗余閱讀器。但當RFID系統(tǒng)中閱讀器布設(shè)密度較高時，讀取范圍嚴重重疊，RRE算法的判別能力可能失效。

1.2 CBA算法

CBA算法[5]采用的啟發(fā)策略使該算法能夠保證每次判別的非冗余閱讀器一定是非冗余的。該算法在判別非冗余閱讀器上有明顯優(yōu)勢，有效避免了誤判而導致的標簽漏讀情況。然而，該算法受判別順序影響較大，不同判別順序?qū)ε袆e結(jié)果影響較大。

1.3 NRCEA算法

NRCEA算法[11]的主要思想是比較相鄰閱讀器的共享標簽數(shù)，從而量化各個RFID閱讀器間的匯聚度，并認為匯聚度越高的閱讀器能夠識別的標簽越多，在網(wǎng)絡(luò)中發(fā)揮的作用也越大。該算法取消了迭代運算，具有計算量小、效率高的特點。該算法將可讀取更多標簽且具有更多共享標簽的閱讀器優(yōu)先保留。但具有更多共享標簽的閱讀器，往往與其他閱讀器的重疊區(qū)域較多，也意味著這些閱讀器可能具有更的多干擾信號，不利于RFID系統(tǒng)性能提升。

2 MNRCBA算法

由于以下3種原因，上述算法可能存在對冗余閱讀器誤判和漏判的情況：1）閱讀器與標簽一對一的寫入方式；2）閱讀器與標簽通過讀寫操作實現(xiàn)交互的通信方式；3）閱讀器對標簽的讀寫距離不等的特性。因此，本文借鑒文獻[9]提出的利用中間件存儲分析RFID閱讀器讀入標簽信息的方法，提出一種基于中間件的RFID系統(tǒng)冗余閱讀器判別改進算法（middleware-neighbor reader-count based algorithm, MNRCBA）。首先，運用CBA找出確定的非冗余閱讀器；然后，改進NRCEA算法，即將讀取標簽數(shù)最多且共享標簽數(shù)最多為優(yōu)先保留閱讀器的原則，變成讀取標簽數(shù)最多且相鄰閱讀器最少為優(yōu)先保留閱讀器原則；最后，根據(jù)計算的優(yōu)先權(quán)，運用RRE思想進行冗余閱讀器判別。

MNRCBA算法步驟：

1）工作區(qū)域內(nèi)，RFID閱讀器讀入其識別范圍內(nèi)的標簽信息，并傳送到RFID中間件，建立“閱讀器——標簽”矩陣，其元素()定義為

2）將矩陣各行相加，得到列向量，列向量的數(shù)值表示各閱讀器所能讀取的標簽數(shù)量的總和；將矩陣各列相加，得到行向量，行向量的數(shù)值表示能讀取該標簽的閱讀器個數(shù)；

3）根據(jù)CBA算法思想，將行向量中元素等于1的標簽所對應(yīng)的閱讀器設(shè)定為非冗余閱讀器，并鎖定這些閱讀器對應(yīng)的標簽；

4）令步驟3）中被鎖定的標簽在矩陣中置0，得到更新后的矩陣’；

5）對矩陣’重復步驟2）和步驟3），迭代運算至“閱讀器——標簽”矩陣中各列相加得到的行向量中所有元素均大于1；

6）設(shè)步驟5）中得到的“閱讀器——標簽”矩陣為，則對矩陣中仍然需要判別的閱讀器逐一查詢，獲得這些閱讀器相鄰閱讀器；其規(guī)則為：獲得所查詢閱讀器的標簽集合，根據(jù)標簽集合中每個標簽對應(yīng)的閱讀器，獲得相鄰閱讀器集合，得到相鄰閱讀器個數(shù)；

7）計算各閱讀器查詢權(quán)重因子，其原則是讀取標簽數(shù)最多且相鄰閱讀器最少的閱讀器權(quán)重因子越大，反之越小，其運算公式為

8）按各閱讀器的權(quán)重因子大小順序逐個選擇閱讀器，鎖定所選擇閱讀器的標簽，更新“閱讀器——標簽”矩陣，直到矩陣中所有元素為0，此時未被選擇的閱讀器即判別為冗余閱讀器。

分析MNRCBA算法可知：經(jīng)過步驟1）~5）后，剩下的閱讀器基本上與其相鄰閱讀器具有重疊區(qū)域，而重疊區(qū)域以NRCEA算法將讀取標簽數(shù)最多且共享標簽數(shù)最多為優(yōu)先保留閱讀器的原則時，閱讀器更容易存在干涉區(qū)域而使干擾信號增大。而以相鄰閱讀器更少原則進行改進，則可避免這些干涉區(qū)域的出現(xiàn)，得到布局更完善的RFID系統(tǒng)。

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系統(tǒng)閱讀器與標簽仿真拓撲圖

3.1 冗余閱讀器判別效果分析

1）將標簽數(shù)量設(shè)為2000個，然后閱讀器數(shù)量從100個開始依次增加100個，直增至600個，考察4種算法能夠找出的冗余閱讀器數(shù)量，實驗結(jié)果如圖3所示。

圖3 各算法判別效果（2000個標簽）

由圖3可知：在標簽數(shù)量不變且閱讀器較少時，4種算法找到的冗余閱讀器數(shù)量相當，RFID性能相當。但隨著RFID閱讀器數(shù)量增加，MNRCBA算法找出的冗余閱讀器相對較多，RFID性能提升明顯；而CBA算法、NRCEA算法性能相當，RRE算法性能相對較差。

2）將閱讀器數(shù)量設(shè)定為500個，然后標簽數(shù)量從1000個開始依次增加1000個，直增至6000個，考察4種算法能夠找出的冗余閱讀器數(shù)量，實驗結(jié)果如圖4所示。

圖4 各算法判別效果（500個閱讀器）

由圖4可知：MNRCBA算法相對于其他3個算法找出的冗余閱讀器數(shù)量更多，且在標簽數(shù)量較少時具有較高性能，而CBA算法和RRE算法在標簽數(shù)量較大時（約3000個）才具有較好的判別效果。

3.2 RFID系統(tǒng)標簽信息量分析

RFID系統(tǒng)標簽信息量分析主要衡量判別算法對冗余閱讀器判別消除后，剩余閱讀器共享標簽的數(shù)量，共享標簽的數(shù)量越少表示RFID系統(tǒng)讀入的標簽重復率越少，后續(xù)數(shù)據(jù)處理更容易。一般采用標簽總量溢出率（rate of overflow, RoF）進行量化，其公式為

式中，為RFID系統(tǒng)消除冗余閱讀器后閱讀器集合；(R)為閱讀器R的可讀標簽集合；max為RFID系統(tǒng)標簽總數(shù)；R為對標簽的平均讀取率。

將閱讀器數(shù)量設(shè)定為500個，然后標簽數(shù)量從1000個開始依次增加1000個，直增至6000個，考察4種算法的系統(tǒng)標簽信息量，實驗結(jié)果如圖5所示。

圖5 各算法RoF值比較

由圖5可知：MNRCBA算法和NRCEA算法的值遠遠小于CBA算法和RRE算法的值，表示MNRCBA算法和NRCEA算法在消除冗余閱讀器的同時能夠保證共享標簽的數(shù)量在較小范圍內(nèi)，且MNRCBA算法比NRCEA算法稍有優(yōu)勢。

3.3 RFID系統(tǒng)部署性能合理性分析

系統(tǒng)標簽信息量分析主要衡量判別算法對冗余閱讀器判別消除后，剩余閱讀器對標簽的讀寫沖突發(fā)生概率。理想情況是在滿足所有標簽全覆蓋的同時實現(xiàn)各閱讀器獨立工作而互不干涉，即RFID系統(tǒng)沒有相鄰閱讀器。一般采用平均相鄰閱讀器數(shù)量（average quantity of neighbor readers, ANR）來進行量化評估，其公式為

將閱讀器數(shù)量設(shè)定為500個，然后標簽數(shù)量從1000個開始依次增加1000個，直增至6000個，考察4種算法的系統(tǒng)部署性能合理性，實驗結(jié)果如圖6所示。

圖6 各算法ANR值比較

由圖6可知：經(jīng)MNRCBA算法和NRCEA算法判別后的RFID系統(tǒng)部署性能明顯優(yōu)于CBA算法和RRE算法，且MNRCBA算法比NRCEA算法有較明顯優(yōu)勢，這是因為MNRCBA算法的原則是盡可能少的相鄰閱讀器，與系統(tǒng)部署性能合理性要求相符合。

4 結(jié)論

針對大型RFID系統(tǒng)在布設(shè)閱讀器時，為達到標簽全覆蓋而導致的冗余閱讀器問題，提出一種基于中間件的RFID系統(tǒng)冗余閱讀器判別算法——MNRCBA算法。該算法結(jié)合RRE算法、CBA算法和NRCEA算法的優(yōu)點，并以讀取標簽數(shù)最多且相鄰閱讀器最少的閱讀器作為優(yōu)先保留原則，有效提高消除冗余閱讀器后RFID系統(tǒng)的部署性能。實驗仿真結(jié)果表明：本文提出的MNRCBA算法在冗余閱讀器判別效果、RFID系統(tǒng)標簽信息量以及RFID系統(tǒng)部署合理性3方面均取得較好性能。

[1] 劉暢.RFID中間件數(shù)據(jù)處理方法研究[D].南京:南京郵電大學,2017.

[2] 何濤,劉暢,徐鶴,等.一種基于中間件的RFID閱讀器去冗余高效算法[J].計算機技術(shù)與發(fā)展,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系統(tǒng)的冗余閱讀器消除改進算法I-RRE[J].計算機工程與應(yīng)用,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] 徐偉,楊智應(yīng).一種RFID網(wǎng)絡(luò)系統(tǒng)中消除冗余閱讀器的高效算法[J].現(xiàn)代計算機(專業(yè)版),2015(17):36-41.

[9] 呂石磊,余順爭.一種基于中間件的RFID系統(tǒng)閱讀器去冗余算法[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] 郭穩(wěn)濤,鄭劍,李兵.一種高效的RFID系統(tǒng)冗余閱讀器消除算法[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年生，高級工程師，主要研究方向：計算機、電子信息技術(shù)應(yīng)用等。E-mail: gdcc_chenyang@foxmail.com