一種RFID網(wǎng)絡(luò)系統(tǒng)中消除冗余閱讀器的高效算法

徐偉，楊智應(yīng)

（上海海事大學(xué)信息工程學(xué)院，上海　201306）

一種RFID網(wǎng)絡(luò)系統(tǒng)中消除冗余閱讀器的高效算法

徐偉，楊智應(yīng)

（上海海事大學(xué)信息工程學(xué)院，上海201306）

0　引言

RFID是射頻識別技術(shù) （Radio Frequency Identification）的英文縮寫。射頻識別技術(shù)是一種自動識別技術(shù)，最早盛行于20世紀(jì)90年代。目前該技術(shù)在世界范圍內(nèi)正被廣泛應(yīng)用，成為21世紀(jì)全球自動識別技術(shù)發(fā)展的主要方向。它主要包括兩大塊，RFID收發(fā)器（閱讀器）和RFID應(yīng)答器（標(biāo)簽）。事實上，RFID系統(tǒng)已經(jīng)被應(yīng)用于門禁系統(tǒng)、視頻溯源、產(chǎn)品防偽等領(lǐng)域。例如2006年的德國世界杯以及2010年的上海世博會就采用了RFID技術(shù)用于門票的防偽。所以RFID系統(tǒng)的便利性使其被廣泛應(yīng)用于不同領(lǐng)域中［3，7］。

在密集部署的RFID網(wǎng)絡(luò)中，密集的閱讀器容易造成相互干擾。因為兩個或更多的相鄰的閱讀器的射頻信號可能會重疊和干擾。因此，過多的不必要的閱讀器消耗了有限的功率。所以如何使用最少數(shù)量的閱讀器有效地覆蓋每一個標(biāo)簽，這就是冗余閱讀器消除問題，冗余閱讀器消除問題是一個RFID系統(tǒng)中的基本問題。冗余閱讀器消除問題已經(jīng)被證明是NP-hard問題［1］。

冗余閱讀器消除問題一直在被廣泛的研究。在本文中，我們利用RRE算法優(yōu)先選擇覆蓋標(biāo)簽數(shù)多的閱讀器為非冗余閱讀器的原理，對CBA算法進(jìn)行了改進(jìn)，提出了一種高效的冗余閱讀器消除算法SCBA。在算法SCBA中，一個擁有最少標(biāo)簽且該閱讀器范圍［2］內(nèi)的標(biāo)簽都與相鄰閱讀器共享的閱讀器被判定為冗余閱讀器。為了證實所提出的方法的性能，我們還對RRE、LEO和CBA等方法進(jìn)行了模擬實驗。實驗證實了算法SCBA能比算法RRE、LEO和CBA能消除更多的冗余閱讀器。

1　相關(guān)工作

在RFID的碰撞中最重要的問題是信號沖突，它可以分為兩種：標(biāo)簽信號的沖突和閱讀器信號沖突。RFID系統(tǒng)通常使用CDMA、FDMA和TDMA解決沖突問題，如改進(jìn)的ALOHA［2，6］算法就是用來避免RFID碰撞［10］。Colorwave則是基于應(yīng)用理論TDMA來避免沖突。基于TDMA，還有一些學(xué)者提出利用標(biāo)簽的識別碼來避免標(biāo)簽沖突，他們的算法基于曼徹斯特編碼，類似于一個二進(jìn)制搜索。

為了避免沖突，另一種解決方案則聚焦于減少閱讀器的數(shù)量。因為冗余的閱讀器不僅增加RFID系統(tǒng)負(fù)載，而且也導(dǎo)致了有限能源的浪費。

在RFID網(wǎng)絡(luò)中，如果一個閱讀器內(nèi)的所有標(biāo)簽都被涵蓋在至少一個其他的閱讀器中，該閱讀器就是多余的。如圖1所示的一個冗余閱讀器在RFID網(wǎng)絡(luò)中的典型例子。它由三個閱讀器R1到R3和五個標(biāo)簽T1 到T5組成。標(biāo)簽T2，T3，T4被R2覆蓋的同時又被R1和R3分別覆蓋。因此，R2是一個冗余閱讀器，它可以在不違反完全覆蓋標(biāo)簽的同時被消除，同時又提高了RFID網(wǎng)絡(luò)質(zhì)量。

圖1　RFID系統(tǒng)冗余閱讀器舉例

在解決冗余閱讀器問題上，RRE［1］和LEO［7］是最有代表性的算法。

（1）RRE

RRE（冗余閱讀器消除算法）［1］算法是第一個分布式算法，是由美國普渡大學(xué)Bogdan Carbunar等人在2005年提出的。RRE是基于貪心算法設(shè)計的。RRE算法的目的是運用最少的閱讀器去讀取所有的標(biāo)簽。

算法RRE描述如下：

①每個閱讀器嘗試把他的標(biāo)簽計數(shù)count（覆蓋的標(biāo)簽數(shù)）寫到它覆蓋的所有標(biāo)簽里。每個閱讀器發(fā)出一個包含它的閱讀器標(biāo)識符和標(biāo)簽計數(shù)的寫命令。每個RFID標(biāo)簽僅存儲所知的標(biāo)簽計數(shù)最高值和相應(yīng)閱讀器的標(biāo)識。每個閱讀器問詢區(qū)里的標(biāo)簽正確接收其發(fā)的寫命令。RFID系統(tǒng)里的標(biāo)簽就會在存儲單元中存儲覆蓋該標(biāo)簽同時又覆蓋有最大標(biāo)簽數(shù)的閱讀器ID，并將這個閱讀器ID標(biāo)記為標(biāo)簽的持有者（holder）。

②閱讀器查詢其問詢區(qū)里的每個標(biāo)簽，讀覆蓋區(qū)域內(nèi)的標(biāo)簽持有者的標(biāo)識。至少鎖定一個標(biāo)簽的閱讀器必定非冗余，將保持活動狀態(tài)。而沒有鎖定任何標(biāo)簽的閱讀器被標(biāo)記為冗余閱讀器，可以被安全關(guān)閉。

RRE算法相對來說是一個比較獨立的算法，但是當(dāng)閱讀器和標(biāo)簽的通信半徑超過一定值時，閱讀范圍的重疊情況就會非常嚴(yán)重，因為它沒考慮相鄰閱讀器的因素，所以監(jiān)測冗余閱讀器的效率就大大降低了，此時覆蓋多的標(biāo)簽的閱讀器反而更可能為冗余閱讀器。

（2）LEO，LEO+RRE

LEO算法（消除分層優(yōu)化）［8］是于2007年在Asia-Pacific Service Computing Conference會議上被提出來的。LEO的原則是“先到先得”。所有的閱讀器發(fā)送請求到在其覆蓋區(qū)內(nèi)的標(biāo)簽并得到標(biāo)簽記錄。如果標(biāo)簽不屬于任何其他閱讀器，該閱讀器就成為該標(biāo)簽的所有者。如果標(biāo)簽已經(jīng)有了一個閱讀器的ID，則該ID不能被改變。最后，一個標(biāo)簽都沒有的閱讀器就是冗余閱讀器。

LEO算法和其他算法相比可以有效的減少讀寫操作，但是LEO算法是隨機(jī)的決定標(biāo)簽的擁有者，因此標(biāo)簽擁有者的選擇的質(zhì)量是不可靠的。

在LEO算法被提出后，有人提出了一個LEO+ RRE構(gòu)想，即當(dāng)一個RFID系統(tǒng)由LEO算法執(zhí)行完畢后，剩余的非冗余閱讀器可以再由RRE算法進(jìn)行過濾。整個的冗余閱讀器的總數(shù)為LEO和RRE算法所識別的最終結(jié)果。這個被稱為LEO+RRE算法。

因為LEO的讀寫操作比RRE小，所以先LEO后RRE，大量冗余閱讀器在LEO階段被去除，RRE在第二階段才會有較小的讀寫操作，不過這個算法還是沒有解決RRE，LEO算法的根本性缺陷。

（3）FSR

針對算法RRE和算法LEO的缺點，F(xiàn)SR［5］算法于2010年在 Proceedings of the 9th WSEAS International Conference on Software Engineering會議上被Hung J W，Li I H.等人提出。假設(shè)每個標(biāo)簽計算覆蓋其的閱讀器總數(shù)為rc。每個閱讀器記錄其問詢區(qū)內(nèi)所有標(biāo)簽數(shù)為tc1。如果標(biāo)簽的rc是1，那么把唯一的閱讀器的id寫進(jìn)這個標(biāo)簽里面。并把該閱讀器內(nèi)所有的標(biāo)簽holder改為該閱讀器。每個閱讀器用系統(tǒng)內(nèi)所有標(biāo)簽總數(shù)減去自己的tc1，得到值tc2，tc2值越小的閱讀器在系統(tǒng)搜索中優(yōu)先權(quán)越大。

算法FSR首次采用了啟發(fā)式策略搜索，在算法一開始找出只被一個閱讀器覆蓋的標(biāo)簽，因為只被一個閱讀器覆蓋的標(biāo)簽的對應(yīng)閱讀器一定是非冗余閱讀器，所以該啟發(fā)策略是完備的。

算法FSR在啟發(fā)式策略搜索中找出了RFID網(wǎng)絡(luò)系統(tǒng)中一定是非冗余的閱讀器，再進(jìn)行加上優(yōu)先權(quán)級后的算法RRE。啟發(fā)策略改變了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，所以算法FSR不一定能比算法RRE找出更多的冗余閱讀器。而且由于要在啟發(fā)式策略中記錄覆蓋當(dāng)前標(biāo)簽的閱讀器數(shù)量，RRE算法中必須要重寫標(biāo)簽中記錄的覆蓋當(dāng)前標(biāo)簽的閱讀器問詢區(qū)內(nèi)的標(biāo)簽數(shù)，所以大大增加了寫操作數(shù)多。

2　算法的提出

與以上提到的幾種算法相比，算法CBA（Count Based Algorithm）［11］的提出則創(chuàng)造性的采用逆向思維，通過存儲在標(biāo)簽里的記錄該標(biāo)簽被多少閱讀器所覆蓋的tagcount的不停加減，可以達(dá)到先消除系統(tǒng)里面一定是冗余閱讀器的那些閱讀器。同時在tagcount的不停變化時，也采用啟發(fā)策略使得算法CBA可以保證每次選擇的非冗余閱讀器一定是非冗余的閱讀器，因此該算法取得了比較好的檢測性能。

算法CBA的運行步驟如下：

①先計算RFID系統(tǒng)中每個標(biāo)簽有多少閱讀器覆蓋它，將結(jié)果記為count，存儲在標(biāo)簽的存儲器中。第二步：啟發(fā)式策略，每個閱讀器給它的覆蓋區(qū)域里所有標(biāo)簽發(fā)送查詢信號，如果其中有某個標(biāo)簽的count=1，那么當(dāng)前閱讀器鎖定它覆蓋區(qū)域里的所有標(biāo)簽。第三步，如果閱讀器覆蓋區(qū)域里面的所有標(biāo)簽的count＞1，意味著該閱讀器不一定是這些標(biāo)簽的holder。則該閱讀器被標(biāo)記為冗余閱讀器，該冗余閱讀器發(fā)送寫信號到它問詢區(qū)里所有標(biāo)簽，將覆蓋區(qū)域內(nèi)標(biāo)簽的count值都減1，然后關(guān)閉此閱讀器。第四步，RFID系統(tǒng)里另一個閱讀器發(fā)送查詢信號到它覆蓋的區(qū)域里面，探測是否有count=1的標(biāo)簽，重復(fù)第二步和第三步直至系統(tǒng)里所有閱讀器都發(fā)送過查詢信號。

圖2　RFID冗余閱讀器舉例

按照上述步驟對圖2進(jìn)行冗余閱讀器的消除可得：

表1中的數(shù)據(jù)X1，X2，X3，X4，X5，X6沒有給出確切的答案的原因是，通過CBA算法我們其實是無法準(zhǔn)確的判斷其余標(biāo)簽應(yīng)該屬于哪個閱讀器的。

表1　CBA算法結(jié)果（R_Reader中R即Redundant）

假設(shè)圖2中的RFID系統(tǒng)執(zhí)行了CBA算法的第一、二步處理，因為T3的count為1所以R2必不為冗余閱讀器，所以T1和T4也被鎖定，那么接下來在執(zhí)行第三步的時候我們該從哪個閱讀器開始呢？

圖3　圖2執(zhí)行完CBA第一、二步后結(jié)果

從圖3中我們看到R1，R4，R3中的標(biāo)簽它們的count都大于1，那么這三個閱讀器的讀取順序的不同將導(dǎo)致得出的冗余閱讀器的數(shù)量有很大的差異。

假設(shè)我們從R4閱讀器開始執(zhí)行第三步，我們發(fā)現(xiàn)T2，T5，T6，T7的count都為2（大于1），則R4被判斷為冗余閱讀器，關(guān)閉此閱讀器。T2，T5，T6，T7的count都減1，變?yōu)榱?，然后又回歸到第二步開始重新執(zhí)行，因為T2，T5，T6，T7的count都為1，所以R1，R3不為冗余閱讀器。

可是假設(shè)我們從R1開始執(zhí)行第三步，因為T2的count為2所以R1為冗余閱讀器，R1被關(guān)閉。此時T2 的count變成了1，所以R4不是冗余閱讀器所以T5，T6，T7被鎖定，所以R3也是冗余閱讀器。所以如果從R1開始，R1和R3則變成了冗余閱讀器。

兩個不一樣的執(zhí)行順序則導(dǎo)致了兩個截然相反的結(jié)果。很明顯從結(jié)果看來第二個假設(shè)得出的結(jié)果才是我們想要的。

其實原理很簡單，從圖3我們可以看到，如果我們不用CBA來判斷，而用最簡單的RRE就可以得出結(jié)果，我們在判斷一個閱讀器是否是冗余閱讀器的時候，我們希望那些非冗余閱讀器能盡量覆蓋更多的標(biāo)簽，也就是一個有效的閱讀器盡量讀更多的標(biāo)簽，這樣才能使RFID系統(tǒng)更高效。

只是RRE算法是先確定非冗余閱讀器為先決條件的算法，而CBA算法是先確定冗余閱讀器為先決條件的算法，所以只要在CBA算法中嵌入RRE算法的判斷準(zhǔn)則，在進(jìn)行完基于啟發(fā)式策略的第二步后，加入一個類RRE算法判決，那么該算法將比原有的算法得出更好的結(jié)果。我將此算法命名為SCBA算法。

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

①RFID系統(tǒng)中每個標(biāo)簽計算有多少閱讀器覆蓋它，即可以和它通信閱讀器的數(shù)量，將結(jié)果記為tagcount，存儲在標(biāo)簽的存儲器中。

②每個閱讀器的覆蓋信息即每個閱讀器讀到了多少標(biāo)簽結(jié)果記為readercount，則被發(fā)送到中心主站。

③閱讀器給它的覆蓋區(qū)域里所有標(biāo)簽發(fā)送查詢信號，如果有某個標(biāo)簽的count=1，那么當(dāng)前閱讀器鎖定它覆蓋區(qū)域里的所有標(biāo)簽，該閱讀器為非冗余閱讀器。

④將已經(jīng)確定了的閱讀器排除，從剩余的閱讀器中，按readercount從小到大開始選擇閱讀器，如果閱讀器覆蓋區(qū)域里面的所有標(biāo)簽的tagcount＞1，意味著沒有標(biāo)簽一定要被當(dāng)前閱讀器hold。則當(dāng)前閱讀器被標(biāo)記為冗余閱讀器，該冗余閱讀器發(fā)送寫信號到它問詢區(qū)里所有標(biāo)簽，將標(biāo)簽的count值減1，然后關(guān)閉此閱讀器。

⑤RFID系統(tǒng)里另一個閱讀器發(fā)送查詢信號到它覆蓋的區(qū)域里面，以探測count=1的標(biāo)簽，重復(fù)②至④直至系統(tǒng)里所有閱讀器都發(fā)送過查詢信號。

3　算法的實驗與分析

為了評估所提出的冗余閱讀器消除算法性能，我們用MATLAB 2012b仿真了RFID網(wǎng)絡(luò)環(huán)境并隨機(jī)部署RFID閱讀器和標(biāo)簽節(jié)點。我們評估的指標(biāo)是冗余閱讀器的數(shù)量，較高的冗余閱讀器數(shù)量預(yù)示著算法的高效性。

（1）標(biāo)簽數(shù)量變化對冗余閱讀器的影響：針對標(biāo)簽數(shù)的不同對RRE，LEO，CBA，SCBA的性能進(jìn)行測試。該1000×1000平方米的實驗區(qū)采取400隨機(jī)閱讀器，標(biāo)簽數(shù)量分別為從1000提高到5000。閱讀器的讀寫半徑設(shè)置為30。如下圖為各算法條件下的去冗余結(jié)果。

從圖4中可以看出，在閱讀半徑和閱讀器數(shù)量不變的前提下，隨著標(biāo)簽數(shù)的增加，各個算法消除的冗余閱讀器數(shù)量都呈下降趨勢。同時SCBA和CBA的差距也趨于減小，因為當(dāng)RFID系統(tǒng)變成高密度的網(wǎng)絡(luò)環(huán)境時，本來是冗余的閱讀器覆蓋到了新的標(biāo)簽，使其變?yōu)榱朔侨哂嚅喿x器。從圖上可以看出SCBA的性能明顯的高于RRE，LEO算法，和CBA相比消除冗余閱讀器的性能也有了明顯提升，所以SCBA算法還是最優(yōu)的。

圖4　標(biāo)簽數(shù)量變化情況下各算法性能比較

（2）閱讀器數(shù)量變化對冗余閱讀器的影響：針對閱讀器數(shù)量的不同對RRE，LEO，CBA，SCBA的性能進(jìn)行測試。該1000×1000平方米的實驗區(qū)采取2500個隨機(jī)標(biāo)簽，閱讀器數(shù)量分別為從100提高到600。閱讀器的讀寫半徑設(shè)置為30。如下圖為各算法條件下的去冗余結(jié)果。

圖5　閱讀器數(shù)量變化情況下各算法性能比較

從圖5中可以看出在閱讀半徑和標(biāo)簽數(shù)量不變的前提下，隨著閱讀器數(shù)量的增加，所有的算法消除冗余閱讀器的數(shù)量都在增加，呈上升趨勢。這是因為閱讀器數(shù)量增多，標(biāo)簽數(shù)量不改變的情況下，冗余的閱讀器數(shù)量必然增多。同時從圖中我們可以看出SCBA算法的性能同樣要優(yōu)于RRE，LEO和CBA算法。

（3）閱讀半徑的變化對冗余閱讀器的影響：

針對閱讀器閱讀半徑的不同對RRE，LEO，CBA，SCBA的性能進(jìn)行測試。在1000×1000平方米的實驗區(qū)內(nèi)部署了2500個隨機(jī)標(biāo)簽和400個隨機(jī)閱讀器，閱讀器的有效讀取半徑為從為10，20，30，40，50。如下圖為各算法條件下的去冗余結(jié)果。

圖6　閱讀半徑變化情況下各算法性能比較

由圖6可知，隨著閱讀半徑的增長，冗余閱讀器數(shù)量逐漸減少。當(dāng)閱讀半徑增加到一定值時，所有算法檢測出的冗余閱讀器數(shù)量都增大。這是因為隨著閱讀半徑的增大，用更少的閱讀器就可以覆蓋當(dāng)前網(wǎng)絡(luò)中的所有標(biāo)簽。本文提出的算法SCBA的性能之所以在閱讀半徑增大時比CBA算法有明顯的提升，就是因為SCBA算法優(yōu)先選擇覆蓋標(biāo)簽數(shù)多的閱讀器為非冗余閱讀器。所以SCBA算法的性能比RRE，LEO，CBA算法都要好。

4　結(jié)語

本文提出的算法SCBA繼承了CBA原有的優(yōu)點，確保每次選擇的冗余閱讀器一定是冗余閱讀器，又融入了類RRE算法的優(yōu)點。和RRE，LEO，CBA等算法相比提升了RFID冗余閱讀器消除的性能。但是在讀寫操作方面，由于需要不間斷改寫標(biāo)簽的tagcount信息，因此寫操作數(shù)偏多，同時需要對閱讀器進(jìn)行排序也增加了系統(tǒng)的負(fù)擔(dān)，但是綜合起來，比起當(dāng)前的其他算法SCBA應(yīng)用前景還是比較廣泛的。

［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-），男，江蘇南通人，碩士研究生，研究方向為算法設(shè)計與分析、并行與分布式計算、移動自組網(wǎng)、RFID傳感器網(wǎng)絡(luò)與物聯(lián)網(wǎng)

2015-04-14

2015-05-14

在多閱讀器RFID網(wǎng)絡(luò)系統(tǒng)中，冗余閱讀器消除問題已被人們所關(guān)注，有許多算法和優(yōu)化技術(shù)用來消除RFID系統(tǒng)中的冗余閱讀器。在深入分析算法CBA的基礎(chǔ)上提出新的算法SCBA以克服其不足之處。仿真實驗表明，該算法SCBA比算法CBA、LEO、RRE能消除更多的冗余閱讀器。

冗余閱讀器消除；RRE；LEO；CBA；SCBA

楊智應(yīng)（1964-），男，博士，教授，研究方向為算法設(shè)計與分析、并行與分布式計算、移動自組網(wǎng)、RFID傳感器網(wǎng)絡(luò)與物聯(lián)網(wǎng)

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.