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

郭穩(wěn)濤，鄭 劍，2，李 兵，，何怡剛

(1.湖南機電職業(yè)技術學院，湖南 長沙 410151；2.湖南大學電氣與信息工程學院，湖南 長沙 410082；3.合肥工業(yè)大學電氣與自動化工程學院，安徽 合肥 230009)

0 引言

射頻識別技術(Radio Frequency Identification，RFID)作為物聯(lián)網(wǎng)代表性核心技術，已經(jīng)廣泛應用于物流、交通運輸、醫(yī)療、定位導航等各領域.[1]一個完整的RFID系統(tǒng)通常包含標簽、閱讀器、中間件[2]和后臺應用系統(tǒng).為保證區(qū)域標簽能夠完全被識別，RFID系統(tǒng)往往會部署過多的閱讀器，這可能帶來相鄰閱讀器的射頻信號重疊產(chǎn)生相互干擾，同時，同一標簽會多次被不同的閱讀器讀取，產(chǎn)生大量冗余數(shù)據(jù).如何消除冗余閱讀器是RFID系統(tǒng)領域中數(shù)據(jù)清洗重大研究問題.冗余閱讀器的消除問題已被證明是NP(Non-deterministic Polynomial)問題[3].

冗余閱讀器消除問題一直是國內(nèi)外研究學者關注的熱點.具有代表性的研究工作包括RRE(Redundant Reader Elimination)算法[4]、LEO(Layered Elimination Optimization)算法[5]和MRRE (Middleware-Base Redundant Reader Elimination)算法[6].RRE 算法使用閱讀器內(nèi)可讀取標簽數(shù)量為權重，保證權重大的閱讀器對標簽具有更大地寫入鎖定優(yōu)先級，迭代直至所有標簽被鎖定，未鎖定標簽的閱讀器即為冗余閱讀器.LEO算法思想是RRE算法針對某些系統(tǒng)拓撲結構失效而進行的進一步改進，保證標簽首次被閱讀器讀取時即被寫入鎖定，未鎖定標簽的閱讀器即判為冗余閱讀器.這兩個算法需要標簽具有寫鎖定存儲功能，同時要求閱讀器對標簽寫距離與讀距離相等，頻繁寫操作浪費時間，增加系統(tǒng)的負擔，影響系統(tǒng)性能.MRRE算法在RFID中間件建立閱讀器和標簽二維數(shù)組，對該數(shù)組進行迭代計算.根據(jù)閱讀器之間重疊標簽的數(shù)量判斷是否為冗余閱讀器，該算法避免了對標簽的寫鎖定操作，從全局上建立閱讀器與標簽間的對應關系.在系統(tǒng)的冗余檢測率、系統(tǒng)標簽信息量和覆蓋率等方面具有一定的優(yōu)勢，但是該算法需要建立全局的閱讀器與標簽對應數(shù)組和在該數(shù)組的迭代操作，尤其迭代終止條件(需要迭代矩陣的元素全為0)極為苛刻，對系統(tǒng)中部署大量的閱讀器和標簽時，需要較大的存儲容量，使算法的復雜性急劇上升，算法的可擴展性差.[7-8]

由于完成消除冗余閱讀器是一個NP問題，因此，如何在冗余閱讀器的消除率和算法額外開銷取得較好的平衡是判斷一個冗余閱讀器消除算法優(yōu)劣的重要指標.本文提出了友鄰閱讀器競爭冗余消除算法NRCEA (Neighbor-Reader Competitive Elimination Algorithm).該算法主要思想是比較相鄰閱讀器的共同標簽數(shù)，用來量化閱讀器間的信息匯聚度，匯聚度越高的閱讀器表明能夠識別的標簽越多，在網(wǎng)絡中發(fā)揮作用越大；匯聚度低的閱讀器表明可能分布在系統(tǒng)的邊緣地帶(可讀標簽數(shù)為0的閱讀器除外).這兩種閱讀器在消除算法中最應該保留，這樣分別從信息匯聚度低和高的兩種情況出發(fā)，消除網(wǎng)絡中重疊標簽，直至最后閱讀器可讀標簽集不再變化為止，可讀標簽集為空的閱讀器即為冗余閱讀器.為了驗證所提出算法的性能，將NRCEA消除算法與典型的RRE算法和LEO算法進行比較，NRCEA消除算法具有閱讀器檢測率高和系統(tǒng)部署更合理的優(yōu)點，同時，與MRRE算法相比具有更低的復雜性.[9-10]

1 冗余閱讀器消除算法

冗余閱讀器收集標簽的功能可以被周圍其他閱讀器替代，不影響RFID系統(tǒng)的功能，因此，判斷系統(tǒng)中標簽的歸屬是去除冗余閱讀器的有效途徑.閱讀器讀取標簽受信號強弱的限制，具有一定地域性，只能讀取周圍一定范圍的標簽，本文提出的冗余閱讀器消除算法基于該思想，比較相鄰閱讀器的可讀標簽，與其他算法相比，可以極大地降低算法的搜索空間.[11-12]

1.1 閱讀器信息匯聚度

RFID系統(tǒng)中部署大量的標簽T和閱讀器R，且存在大量的冗余閱讀器，這些閱讀器射頻信號強弱相同，讀取標簽的范圍相同，讀取的范圍記為d.RFID中間件可接受并存儲閱讀器發(fā)送的標簽信息，并且可以得到閱讀器i在系統(tǒng)部署區(qū)域的坐標，記為〈xi，yi〉.

(1)

在中間件中，通過距離判別函數(shù)得到系統(tǒng)中每個閱讀器的相鄰閱讀器集，使用一個二元組〈TS，RS〉來表示閱讀器的信息，其中TS表示閱讀器可讀標簽集，RS來表示相鄰閱讀器節(jié)點集.根據(jù)相鄰閱讀器節(jié)點集RS可以將可讀標簽集TS中的標簽進行分類，共享標簽集TS1和孤立標簽集TS2，對閱讀器i使用的描述公式為：

?j∈RSi∧?r∈TSj∧?r∈TSi→r∈TSi1；

TSi2=TSi-TSi1.

(2)

為了精確刻畫相鄰閱讀器相似程度，對有多個閱讀器共享的同一標簽，需要重復計算多次，加入到共享標簽集TS1中.孤立標簽集TS2如果不為空，則表示該閱讀器需要獨自讀取某些標簽，標記為非冗余閱讀器.使用max來標記系統(tǒng)中的所有標簽數(shù)，定義相鄰閱讀器相似度用來刻畫閱讀器在系統(tǒng)中間可讀標簽的相似程度.[13-14]

定義1閱讀器相鄰相似度.閱讀器i的相鄰相似度可以表示為

α=|TS1|/max.

(3)

|TS1|表示共享標簽集的數(shù)目，α∈[0，1].

定義2閱讀器信息匯聚度.閱讀器i的信息匯聚度可以表示為

IAi=w*α(1-w)*|TS|/max.

(4)

其中：w∈[0，1]，w取不同值，表示相鄰相似度和可讀標簽數(shù)間的比重.閱讀器信息匯聚度刻畫了當TS2≠?時，閱讀器在系統(tǒng)中承擔讀取共享標簽和總標簽的比重，w值越大，表示閱讀器承擔讀取共享標簽的功能越大，在閱讀器信息匯聚度的量化指標中占據(jù)的比重越大.圖1為一個簡單的RFID冗余閱讀器拓撲.

圖1 RFID冗余閱讀器舉例

根據(jù)上述概念的定義，可以分別得到可讀標簽集、共享標簽集和孤立標簽集：

TSR1={T1，T2}，TSR11={T2}，TSR12={T1}；

TSR2={T2，T3，T4，T7，T8}，

TSR21={T2，T4，T7，T8，T8}，TSR22={T3}；

TSR3={T4，T6，T8}，

TSR31={T4，T6，T8，T8}，TSR32=?；

TSR4={T5，T6，T7，T8}；

TSR41={T6，T7，T8，T8}，TSR41={T5}.

這里，max=9，假設取w=0.7，可以得到信息匯聚度：

首先，TSR32=?可以看出閱讀器R3的可讀孤立標簽集為空，則該閱讀器可能為空，從閱讀器的信息匯聚度值相對大小可知，閱讀器R2在系統(tǒng)中承擔讀取標簽任務的比重較大，從該閱讀器開始進行消減標簽，直至閱讀器可讀標簽為零為止.

1.2 算法描述

友鄰閱讀器競爭冗余消除算法NRCEA的基本思想：首先，RFID系統(tǒng)中各閱讀器發(fā)送讀取標簽廣播，收集可讀范圍內(nèi)所有標簽標志，構成可讀標簽集TS.然后，各閱讀器將自身位置坐標〈xi，yi〉和可讀標簽集TS發(fā)送給系統(tǒng)中間件，根據(jù)中間件公式(1)計算各閱讀器的相鄰閱讀器集RS，并根據(jù)公式(2)將可讀標簽集TS分成共享標簽集TS1和孤立標簽集TS2.最后，按照以下步驟判別冗余閱讀器[15]：

步驟1中間件根據(jù)公式(3)和(4)計算閱讀器相鄰相似度和信息匯聚度，剔除那些孤立標簽集TS2不為空的閱讀器，判別為非冗余閱讀器，放入非冗余閱讀器集NRR.

步驟2從閱讀器集中任意選擇一個閱讀器Ri，與相鄰閱讀器集TS的閱讀器Rj進行比較，如果存在共同標簽：

(1) 如果閱讀器Ri∈NRR，則從閱讀器Rj的可讀標簽集RS中刪除該標簽；

(2) 如果閱讀器Rj∈NRR，則從閱讀器Ri的可讀標簽集RS中刪除該標簽；

(3) 如果IAi

(4) 如果IAi≥IAj，則從閱讀器Rj的可讀標簽集RS中刪除該標簽.

步驟3不斷迭代遍歷步驟2，直至閱讀器集中所有元素遍歷為止.

步驟4計算判別冗余閱讀器，如果可讀標簽集不為空，則為冗余閱讀器，放入非冗余閱讀器集NRR.

1.2.1 算法偽代碼

第1步：初始化，得到所有閱讀器可讀標簽集和相鄰閱讀器集.

Set NRCEA(Set Rds，Set tags，flaot d；float w，float Thresd){

Set NRR=?，RR=?；

for each(reader rd1 in Rds){

rd1.TS.put(rd.readtargers())；

for each(reader rd2 in Rds $$ rd2!=rd1){

if(rd2.RS.contain(rd1))

rd1.RS.put(rd2)；

elseif(!abs(rd1.x-rd2.x)>2*d&&

!abs(rd1.y-rd2.y)>2*d)

rd1.RS.put(rd2)；

}

}.

第2步：得到共享標簽集TS1和孤立標簽集TS2.

for each(reader rd1 in Rds){

for each (reader rd2 in rd1.RS)

for each (tag t in rd1.RS)

if(t in rd2.TS)

rd1.TS1.put(t)；

rd1.TS2=rd1.TS-rd1.TS1；

}.

第3步：計算每個閱讀器的信息匯聚度.

for each(reader rd1 in Rds)

rd1.ia=w*rd1.TS1.num()/tags.num()+(1-w)*rd1.TS.num/tags.num().

第4步：迭代遍歷閱讀器集，計算非冗余標簽集和冗余標簽集.

for each(reader rd1 in Rds)

for each (reader rd2 in rd1.RS)

for each (tag t in rd1.RS)

if(rd2.TS.contain(t)){

if(NRR.contain(rd1)){

rd2.TS.delete(t)；

break；

}

if(NRR.contain(rd2)){

rd1.TS.delete(t)；

break；

}

if(!rd1.TS2.empty()){

NRR.put(rd1)；

rd2.TS.delete(t)；

break；

}

if(!rd2.TS2.empty()){

NRR.put(rd2)；

rd1.TS.delete(t)；

break；

}

if (rd1.ia

rd1.TS.delete(t)；

break；

}

rd2.TS.delete(t)；

}.

第5步：判斷冗余閱讀器.

for each(reader rd1 in Rds)

if(!NRR.contain(rd1)&&!rd1.TS.empty()){

NRR.put(rd1)；

RR=Rds-NRR；

return RR；

}.

1.2.2 算法流程

在迭代過程中，相鄰閱讀器間具有共同標簽的閱讀器，根據(jù)其信息匯聚度值競爭性刪除相同的標簽，能夠保留可讀標簽數(shù)量和相同標簽數(shù)大的閱讀器，該算法流程如圖2所示.

圖2冗余閱讀器消除算法流程

1.3 算法分析

設系統(tǒng)中存在n個閱讀器，每個閱讀器可讀標簽平均數(shù)量為r，相鄰閱讀器平均數(shù)量為m.系統(tǒng)中標簽數(shù)為n*r.

首先，RRE算法和LEO+RRE算法在消除冗余閱讀器時，需要保存每個標簽的鎖定的閱讀器信息，因此，空間復雜度為系統(tǒng)中標簽的數(shù)量，即O(n*r)；MRRE算法需要保存一個所有閱讀器與所有標簽一一映射的矩陣，其所有空間復雜度為O(n*n*r).而NRCEA算法消除過程中為每個標簽保存一張可讀標簽集合和相鄰閱讀器集合，其空間復雜度為O(n*(w+r)).因此，空間代價要比MRRE算法小得多.

其次，RRE算法和LEO+RRE算法需要對每個標簽執(zhí)行寫鎖定操作，其寫操作復雜度為O(n*r)，因寫操作時間要遠遠大于讀操作時間，因此，該算法的額外寫操作時間開銷比較大.MRRE算法和NRCEA算法不要寫操作，需要遍歷所有的閱讀器和標簽，其最差時間復雜性均為O((n*n*r)2).

因此，NRCEA算法空間復雜度要低于MRRE算法，時間復雜度要優(yōu)于RRE算法和LEO+RRE算法，能夠在時間和空間上均具有明顯的優(yōu)勢.同時，NRCEA算法設置2種閱讀器保留策略：一種是保留讀取孤立標簽集的閱讀器；另一種是通過計算閱讀器信息匯聚度作為相鄰閱讀器競爭讀取標簽的權重，保留信息匯聚度大的閱讀器，從而使算法在系統(tǒng)標簽信息量和覆蓋率、系統(tǒng)部署更合理性.

2 算法實驗與結果分析

實驗環(huán)境基于Matlab 7.0，參數(shù)同文獻[4-6]，實驗區(qū)域為1 000×1 000單位長度，隨機分布500個閱讀器和若干標簽，實驗標簽的數(shù)量范圍為[1 000，8 000]，設定閱讀器讀距離d=50，閱讀器對標簽寫距離與讀距離比例為0.7[7].各種實驗分別進行10次，對實驗數(shù)據(jù)取平均值.

2.1 算法性能分析

由于LEO算法和RRE算法需要對標簽進行寫鎖定操作，因此代價比較大，性能相對較低.MRRE算法和NRCEA算法在中間件上進行，受RFID工作特性影響較少，其性能較優(yōu).

各算法可擴展性性能可以使用系統(tǒng)標簽數(shù)量變化進行描述.4種算法隨標簽數(shù)量變化的冗余消除結果如圖3所示，由圖3可以看出，本文提出的NRCEA算法和MRRE算法明顯優(yōu)于LEO和RRE算法，同時，NRCEA算法的冗余閱讀器檢測率比MRRE算法提高了6%～14%.因為NRCEA算法優(yōu)先考慮處于邊界和孤立閱讀器，其他閱讀器共享標簽消除時依據(jù)閱讀器信息匯聚度，能夠保存讀取更多標簽的閱讀器，將閱讀信息量少的閱讀器盡可能地消除掉.

圖3 各算法去冗余消除結果

2.2 系統(tǒng)標簽信息量分析

系統(tǒng)標簽信息量可以使用標簽總量溢出率(rate of overflow，RoF)來量化，定義為

(5)

其中：NRR表示系統(tǒng)冗余閱讀器消除后非冗余閱讀器集合；TS(Ri)表示閱讀器Ri可讀取的標簽集合；NoT表示系統(tǒng)標簽總數(shù)；Rr表示NRR對標簽的平均讀取率.

各算法隨標簽數(shù)量變化的RoF性能變化如圖4所示.NRCEA算法和MRRE算法的RoF值接近1，遠遠小于RRE算法和LEO算法，表明冗余閱讀器消除后閱讀器間共享的標簽數(shù)量特別少.

圖4 各算法RoF性能比較

2.3 系統(tǒng)部署合理性分析

系統(tǒng)部署合理性是指系統(tǒng)應盡量減少RFID對標簽讀寫沖突發(fā)生的概率.通過減少各標簽周圍覆蓋的閱讀器的數(shù)量，降低閱讀器間沖突的發(fā)生概率.因此，使用閱讀器的平均相鄰閱讀器數(shù)量(average quantity of neighbor readers，ANR)來衡量各算法的系統(tǒng)部署合理性，定義為：

RNS(Ri)={Rj|Rj∈RS(Ri)∧Rj∈NRR}；

(6)

圖5 各算法ANR性能比較

其中：RNS(Ri)表示閱讀器Ri在冗余消除后相鄰閱讀器集；|·|表示對應集合內(nèi)元素數(shù)量.

各算法隨標簽數(shù)量變化的ANR指標曲線如圖5所示.由圖5可以看出，NRCEA算法明顯優(yōu)于RRE算法和LEO算法，取得與MRRE算法相同的效果，但是算法的復雜度明顯低于MRRE算法.

3 結束語

為了解決RFID系統(tǒng)中冗余閱讀器的多讀問題，本文提出了一種基于閱讀器信息匯聚度的高效RFID系統(tǒng)冗余閱讀器消除算法NRCEA.與現(xiàn)有的典型RRE算法和LEO算法相比，該算法不需要對標簽寫鎖定操作，不受RFID工作特性的影響.與MRRE算法相比，該算法在存儲空間上具有更低的復雜度.仿真實驗結果表明，NRCEA算法在算法性能、系統(tǒng)標簽信息量和部署更合理性，具有更高的冗余閱讀器檢測率.