陳陽(yáng) 陳堅(jiān)澤 李超

學(xué)術(shù)研究

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

陳陽(yáng)1,3陳堅(jiān)澤1李超2

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

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

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

0 引言

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

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

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

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

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

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

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

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

1.1 RRE算法

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

1.2 CBA算法

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

1.3 NRCEA算法

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

2 MNRCBA算法

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

MNRCBA算法步驟：

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

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

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

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

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

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

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

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

分析MNRCBA算法可知：經(jīng)過步驟1）~5）后，剩下的閱讀器基本上與其相鄰閱讀器具有重疊區(qū)域，而重疊區(qū)域以NRCEA算法將讀取標(biāo)簽數(shù)最多且共享標(biāo)簽數(shù)最多為優(yōu)先保留閱讀器的原則時(shí)，閱讀器更容易存在干涉區(qū)域而使干擾信號(hào)增大。而以相鄰閱讀器更少原則進(jìn)行改進(jìn)，則可避免這些干涉區(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 實(shí)驗(yàn)與分析

圖2 RFID系統(tǒng)閱讀器與標(biāo)簽仿真拓?fù)鋱D

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

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

圖3 各算法判別效果（2000個(gè)標(biāo)簽）

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

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

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

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

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

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

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

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

圖5 各算法RoF值比較

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

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

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

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

圖6 各算法ANR值比較

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

4 結(jié)論

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

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

[2] 何濤,劉暢,徐鶴,等.一種基于中間件的RFID閱讀器去冗余高效算法[J].計(jì)算機(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)的冗余閱讀器消除改進(jìn)算法I-RRE[J].計(jì)算機(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)代計(jì)算機(jī)(專業(yè)版),2015(17):36-41.

[9] 呂石磊,余順爭(zhēng).一種基于中間件的RFID系統(tǒng)閱讀器去冗余算法[J].電子學(xué)報(bào),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].東北師大學(xué)報(bào)(自然科學(xué)版),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

陳陽(yáng)，男，1984年生，高級(jí)工程師，主要研究方向：計(jì)算機(jī)、電子信息技術(shù)應(yīng)用等。E-mail: gdcc_chenyang@foxmail.com