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

徐偉，楊智應

（上海海事大學信息工程學院，上?！?01306）

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

徐偉，楊智應

（上海海事大學信息工程學院，上海201306）

0　引言

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

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

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

1　相關工作

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

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

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

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

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

（1）RRE

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

算法RRE描述如下：

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

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

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

（2）LEO，LEO+RRE

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

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

在LEO算法被提出后，有人提出了一個LEO+ RRE構想，即當一個RFID系統(tǒng)由LEO算法執(zhí)行完畢后，剩余的非冗余閱讀器可以再由RRE算法進行過濾。整個的冗余閱讀器的總數(shù)為LEO和RRE算法所識別的最終結果。這個被稱為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ù)為rc。每個閱讀器記錄其問詢區(qū)內所有標簽數(shù)為tc1。如果標簽的rc是1，那么把唯一的閱讀器的id寫進這個標簽里面。并把該閱讀器內所有的標簽holder改為該閱讀器。每個閱讀器用系統(tǒng)內所有標簽總數(shù)減去自己的tc1，得到值tc2，tc2值越小的閱讀器在系統(tǒng)搜索中優(yōu)先權越大。

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

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

2　算法的提出

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

算法CBA的運行步驟如下：

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

圖2　RFID冗余閱讀器舉例

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

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

表1　CBA算法結果（R_Reader中R即Redundant）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3　算法的實驗與分析

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

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

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

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

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

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

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

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

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

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

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

4　結語

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

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

2015-04-14

2015-05-14

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

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

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

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.