何 濤，劉 暢，徐 鶴，周 凱

(1.南京郵電大學 電子科學與工程學院，江蘇 南京 210003; 2.南京郵電大學 計算機學院，江蘇 南京 210003)

一種基于中間件的RFID閱讀器去冗余高效算法

何 濤1，劉 暢1，徐 鶴2，周 凱1

(1.南京郵電大學 電子科學與工程學院，江蘇 南京 210003; 2.南京郵電大學 計算機學院，江蘇 南京 210003)

射頻識別(RFID)技術近年來變得越來越復雜，同時應用領域也更加廣泛。冗余閱讀器是影響系統(tǒng)性能指標的基本問題之一，其存在給RFID系統(tǒng)造成了極大的負擔，并降低了獲取信息的準確度。消除冗余閱讀器是優(yōu)化多閱讀器RFID系統(tǒng)性能的重要途徑。在現(xiàn)有的去除冗余閱讀器算法的基礎上，分析已有多種算法的優(yōu)缺點，并結合其優(yōu)點提出了新的算法思想，再將新算法與RFID中間件技術相結合，提出了基于中間件的改進算法，通過中間件處理計算數(shù)據(jù)而無需閱讀器對標簽有過多的讀寫操作和計算能力。從不同閱讀器數(shù)量、不同標簽數(shù)量、不同讀取半徑三個方面對提出算法進行了仿真驗證實驗。仿真實驗結果表明，提出算法在找出的冗余閱讀器的數(shù)量上具有較明顯的優(yōu)勢，其去冗余性能較現(xiàn)有的其他算法更優(yōu)。

射頻識別；中間件；冗余閱讀器；標簽

0 引 言

RFID(Radio FrequencyIDentification)技術，又稱無線射頻識別，是一種通信技術，可通過無線電訊號識

別特定目標并讀寫相關數(shù)據(jù)而無需識別系統(tǒng)與特定目標之間建立機械或光學接觸。目前，RFID應用的大部分實際需求中，各式各樣的應用軟件要實現(xiàn)跨平臺應用,又或是一個平臺要管理和支持多種系統(tǒng)或應用軟件,這需要應用系統(tǒng)和軟、硬件平臺間有可供數(shù)據(jù)傳送的穩(wěn)定高效的樞紐,以保證系統(tǒng)的有效性[1]。因此，對于RFID中間件的研究必不可少。同時，在RFID系統(tǒng)中，冗余閱讀器的存在極大地降低了系統(tǒng)的性能，增加了能源消耗[2]。

在分析研究現(xiàn)有去除冗余閱讀器算法的基礎上，在CBA算法找出的冗余閱讀器一定是冗余閱讀器的前提下，運用RRE算法的思想對剩余閱讀器進行排序選擇，同時，根據(jù)NCD算法的優(yōu)點改進RRE算法對選擇排序的具體實現(xiàn)，再運用中間件技術，將運算排序等步驟的實施均移至中間件操作，以減輕系統(tǒng)負擔，降低能耗。并且該算法無需系統(tǒng)拓撲信息，也無需閱讀器對標簽進行寫入操作，且排除冗余閱讀器的性能更優(yōu)。

1 相關工作

冗余閱讀器是影響RFID系統(tǒng)性能的基礎問題之一。在RFID系統(tǒng)中，需要解決一個最基本的問題：信號碰撞。其可分為兩種：閱讀器信號碰撞和標簽信號碰撞。一般可以使用SDMA、FDMA、TDMA解決碰撞問題[3-5]，而減少碰撞的另一個方案就是減少閱讀器的數(shù)量，即去除冗余閱讀器。尋求去除冗余閱讀器的最佳方案已被證明是NP-hard問題[6]。閱讀器去冗余算法的目的是使區(qū)域內(nèi)工作閱讀器的數(shù)量降至最低,以改善系統(tǒng)性能。

定義：在RFID系統(tǒng)中，當某個RFID閱讀器覆蓋一組RFID標簽，而此組內(nèi)的標簽同時被其他閱讀器所覆蓋，則此閱讀器是冗余的，稱為冗余閱讀器[7]。

如圖1所示，R1、R2、R3、R4是RFID網(wǎng)絡中的四個閱讀器的讀取范圍，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]去除冗余閱讀器。其步驟如下：將閱讀器讀取范圍內(nèi)的標簽數(shù)量作為權重，讓具有較大權重的閱讀器優(yōu)先將讀取范圍的標簽鎖定，并寫入鎖定信息，迭代運行直至所有標簽都被鎖定，一個標簽都未鎖定的閱讀器即為冗余閱讀器。

以圖1為例，T1(1，R1)(4，R2)表示標簽T1被R1、R2讀取且R1讀取范圍內(nèi)只有1個標簽，R2讀取范圍有4個標簽，那么：T2(4，R2)(1，R3),T3(4，R2)(2，R4),T4(4，R2)(2，R4),根據(jù)RRE算法，優(yōu)先選擇具有最大權重的閱讀器，因此被鎖定的有：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上提出的。其原則是“先到先得”，即所有閱讀器發(fā)送請求到在其覆蓋區(qū)內(nèi)的標簽并取得標簽記錄。如果有標簽不屬于其他任何閱讀器，那么該閱讀器就成為這個標簽的所有者。如果標簽已經(jīng)有了一個閱讀器的身份信息，則該身份信息不能被改變。最后，一個身份信息都沒有被記錄的閱讀器就是冗余閱讀器。

仍以圖1為例，T1首先被R1讀取并記錄，T2被R3讀取并記錄，T3、T4被R4讀取并記錄，此時R2發(fā)送的請求無法記錄任何一個標簽，因為所有標簽均已記錄其他閱讀器ID,此時R2為冗余閱讀器。

上述RRE、LEO算法提出后，又有人提出RRE+LEO算法，即執(zhí)行完LEO算法后，對判定后的非冗余閱讀器再進行RRE算法過濾，最后LEO和RRE算法找出冗余閱讀器的并集就是總的冗余閱讀器數(shù)量[9-11]。

1.3 CBA(Count Based Algorithm)

CBA[12]算法創(chuàng)造性地采用了先找出的一定是冗余閱讀器的思想，通過逐步關閉冗余閱讀器同時減少標簽計數(shù)，得到最終結果。其步驟如下：

(1)所有閱讀器向讀取范圍內(nèi)的所有標簽發(fā)送查詢信息包，每個標簽記錄一共有多少閱讀器可讀取到它們，記為count。

(2)閱讀器發(fā)送查詢信號，標簽返回自身count,如果一個閱讀器收到的標簽信號中有count=1，則該閱讀器鎖定其讀取范圍所有標簽。

(3)如果一個閱讀器收到各個標簽返回的信號的所有count都大于1，則表示沒有標簽一定要被該閱讀器鎖定，此閱讀器被判定為冗余閱讀器，并且此閱讀器讀取范圍的所有標簽的count值減1，可暫時關閉此閱讀器。

(4)另一個閱讀器繼續(xù)發(fā)送查詢信號，重復步驟直到所有閱讀器均查詢完畢。

2 新算法的提出

若RFID系統(tǒng)中閱讀器部署比較密集，多個閱讀器之間交叉發(fā)生沖突，并且閱讀器射頻范圍的標簽數(shù)目相同時，使用RRE算法無法得到最優(yōu)的冗余閱讀器，如圖2所示。

圖2 RRE算法缺點分析圖

通過分析圖2，得到表1。

表1 RRE算法分析結果

表1中結果面前的數(shù)字代表這一行的閱讀器能讀取到的標簽數(shù)量。

由圖2可以看出，在理想情況下，僅使得R2、R4工作即可，但使用RRE算法時，如表1所示，由于R2、R3、R4覆蓋4個不同集合的標簽，算法認為這并不冗余，因此不得不讓3個閱讀器都工作。

LEO算法的缺點：由于LEO算法只依賴于閱讀器的識別順序，因此會將R2視作冗余閱讀器而讓R1、R3、R4工作，顯然這是不合理的。

CBA算法的缺點：在所有標簽count均大于1時，若先判定R1為冗余閱讀器，剩余閱讀器選擇的順序具有隨機性，不同的選擇順序直接導致最后的冗余閱讀器的判定結果不同。

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

(1)閱讀器與標簽一對一的寫入方式。

(2)閱讀器對標簽進行讀寫操作來交互信息的通信方式。

(3)閱讀器對標簽的讀寫距離不等的特性，都會導致算法誤判、漏判冗余閱讀器并使系統(tǒng)功率消耗過大。

因此，在CBA算法的基礎上，借鑒了呂石磊等提出的利用中間件存儲分析標簽閱讀器信息的思想[13]，并根據(jù)RRE算法的思想改進CBA算法在選擇閱讀器時的隨機性，運用RRE算法的同時，舍棄RRE以最大值為權重的方法，結合NCD(Neighboring Coverage Density)算法[14]提出一種更精確的加權算法，即MCBA(Middleware Count Based Algorithm)。

該算法對系統(tǒng)有如下要求：

(1)閱讀器可讀取到其射頻范圍內(nèi)所有標簽。

(2)RFID中間件可儲存并處理閱讀器本身信息及其發(fā)送的標簽信息。

MCBA步驟如下：

(1)閱讀器讀取其范圍內(nèi)的標簽信息傳給中間件，中間件接收并存儲閱讀器發(fā)送的標簽信息。

(2)建立“閱讀器-標簽”矩陣M，定義為：

其中，Tj∈Ri表示閱讀器Ri可讀取標簽Tj，反之Tj?Ri表示標簽Tj不在閱讀器Ri的讀取范圍內(nèi)。

(3)計算矩陣M各行及各列的和，可得出一個閱讀器能讀取的標簽個數(shù)(readercount)及一個標簽被多少閱讀器覆蓋(tagcount)。

(4)找出tagcount=1的標簽j，此列在M矩陣中值為1的標簽被對應的閱讀器i鎖定，i為非冗余閱讀器。

(5)定義相鄰覆蓋密度為：

(6)重復步驟(4)和(5),直到系統(tǒng)內(nèi)所有閱讀器都發(fā)送過查詢信號。

通過分析圖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?？梢钥闯鯳R2大于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算法的性能，設計實驗以驗證各算法的去冗余效果。實驗環(huán)境基于Matlab7，在1 000*1 000的固定區(qū)域里，隨機生成閱讀器和標簽節(jié)點的位置。通過比較算法得出的冗余閱讀器的數(shù)量來分析判斷算法RRE、LEO、CBA、MCBA的優(yōu)劣。每次結果均取100次仿真實驗結果的均值。算法實驗見圖3。

圖3 算法比較

(1)分析閱讀器數(shù)量的變化對四種算法找出的冗余閱讀器數(shù)量的影響。標簽數(shù)量取定為2 500，閱讀器讀取半徑為30，閱讀器數(shù)量由100依次以100為基數(shù)遞增到600，結果見圖3(a)。

從圖3(a)中可以看出,在閱讀器讀取半徑和標簽數(shù)量不變的情況下，閱讀器數(shù)量增加，各算法找出的冗余閱讀器數(shù)量均增加。分析可知，當閱讀器總數(shù)增多而標簽個數(shù)不變時，新增的閱讀器或是冗余，或是覆蓋已記錄的標簽，使原本非冗余閱讀器被判定為冗余，所以冗余閱讀器數(shù)量一定增加。其中，MCBA算法去冗余的性能優(yōu)于其他三種算法。

(2)在閱讀器讀取半徑和閱讀器數(shù)量不變的情況下，分析研究標簽數(shù)量的增加對不同算法去冗余效率的影響。選定閱讀器讀取半徑為30，閱讀器數(shù)量為400，標簽數(shù)量由1 000以1 000為基數(shù)依次遞增為6 000。圖3(b)為不同算法在不同標簽數(shù)目下找出的冗余閱讀器的個數(shù)。

從圖3(b)可以看出，在閱讀器讀取半徑和閱讀器數(shù)量不變的情況下，隨著標簽數(shù)量的增加，四種算法找出的冗余閱讀器數(shù)量均呈下降趨勢。因為在標簽越來越密集的情況下，之前的冗余閱讀器因為覆蓋了新增的標簽而成為非冗余閱讀器。從仿真結果可以看出，MCBA優(yōu)于CBA及另外兩種算法。

(3)分析在標簽數(shù)量和閱讀器數(shù)量恒定的情況下，閱讀器半徑大小對四種算法去冗余性能的影響。結果如圖3(c)所示。

由圖3(c)分析可知，在標簽數(shù)量和閱讀器數(shù)量不變的前提下，閱讀器讀取半徑逐步增大，找出的冗余閱讀器先減少，當半徑增加到一定值時，冗余閱讀器數(shù)量開始增加。當閱讀器讀取半徑增加時，原來未被某閱讀器覆蓋的標簽會因此進入該閱讀器射頻范圍，即用較少的閱讀器即可讀取相同數(shù)量的標簽，因此找出的冗余閱讀器必然增加。其中，MCBA在半徑增加時去冗余性能比CBA有明顯優(yōu)勢，就是因為選擇了合適的權重對剩余閱讀器進行排序，讓系統(tǒng)優(yōu)先選擇更可能是冗余閱讀器的閱讀器進行計算。所以MCBA算法的性能比另外三種都要好。

(4)通過實驗對比觀察RFID系統(tǒng)應用MCBA算法后的效果。取定閱讀器數(shù)量為400，標簽數(shù)量為2 500，閱讀器讀取半徑為50。實驗對比結果如圖4所示，其中圓圈代表閱讀器讀取范圍，點代表標簽。

圖4 應用MCBA算法前后系統(tǒng)網(wǎng)絡圖

通過對比很容易看出，在運用MCBA算法后，RFID系統(tǒng)的標簽-閱讀器網(wǎng)絡拓撲簡潔了很多，由此降低了能耗，同時避免過多的碰撞問題。

另外，采用的是閱讀器對標簽的讀距離和寫距離1∶1進行實驗，而實際中閱讀器對標簽的寫距離是小于讀距離的[15]，這又會使RRE、LEO和CBA算法的去冗余性能有所下降，而MCBA不需要閱讀器對標簽進行寫操作，因此不會受到影響。

4 結束語

為高效地解決RFID網(wǎng)絡冗余閱讀器問題，提出了基于中間件技術的MCBA算法。該算法運用相鄰覆蓋密度的概念給閱讀器加上權重來選擇閱讀器，屏蔽了CBA算法選擇閱讀器的隨機性，并引入中間件減輕了閱讀器和標簽的負擔。實驗結果表明，與RRE、LEO及CBA算法相比，MCBA算法在找出的冗余閱讀器的數(shù)量上，具有明顯優(yōu)勢，且其去冗余性能更優(yōu)。

[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系統(tǒng)的冗余閱讀器消除改進算法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網(wǎng)絡系統(tǒng)中消除冗余閱讀器的高效算法[J].現(xiàn)代計算機,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系統(tǒng)閱讀器去冗余算法[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 網(wǎng)絡出版時間：2017-04-28

國家自然科學基金資助項目(61602261)；中國博士后科學基金(2014M561696)；江蘇省自然科學基金(BK20140886)；江蘇省高校自然科學研究面上項目(14KJB520030)；江蘇省博士后科研資助計劃項目(1401005B)；江蘇省研究生科研創(chuàng)新計劃(SJLX15_0381)；南京郵電大學引進人才科研啟動基金(NY213034)；南京郵電大學自然科學基金(NY214060，NY214061)

何 濤(1972-)，男，講師，研究方向為無線傳感器網(wǎng)絡及大數(shù)據(jù)；劉 暢(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