基于中間件的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