基于分組策略的RFID自適應(yīng)防碰撞算法的研究

李 云，謝 剛，鄭 重，楊江波

(太原理工大學(xué)信息工程學(xué)院，山西 太原 030024)

責(zé)任編輯:薛 京

射頻識別(Radio Frequency Identification，RFID)系統(tǒng)運行時，當(dāng)讀寫器作用區(qū)域內(nèi)多個標(biāo)簽同時向讀寫器發(fā)送信號，會產(chǎn)生信號相互干擾的現(xiàn)象，這種現(xiàn)象稱為標(biāo)簽的碰撞，而解決此類碰撞的算法則稱為標(biāo)簽防碰撞算法。目前，現(xiàn)有的時分多路(TDMA)標(biāo)簽防碰撞算法可以分為基于ALOHA機制的隨機性算法和基于二進制樹的確定性算法兩種類型［1］?；贏LOHA機制的算法操作簡單、易于實現(xiàn)，但當(dāng)標(biāo)簽數(shù)目較大時，部分標(biāo)簽可能會在相當(dāng)長的一段時間內(nèi)得不到識別，出現(xiàn)“餓死”現(xiàn)象［2］。目前研究較多的是幀時隙ALOHA算法［3-4］，主要是通過估計標(biāo)簽數(shù)量來確定幀長從而減少碰撞，但仍未解決標(biāo)簽“餓死”問題?；诙M制樹的算法［5-9］識別率高，避免了標(biāo)簽“餓死”現(xiàn)象，適應(yīng)標(biāo)簽數(shù)目較大的場合，但通信量大，且有相當(dāng)長的延時。文獻［5-6］通過后退策略降低了通信量，但是碰撞時隙較多，仍有相當(dāng)長的延時。文獻［7］是通過啟發(fā)式函數(shù)h(x)的大小來估計節(jié)點內(nèi)待識別的標(biāo)簽數(shù)量，由于每次搜索都要計算h(x)，雖然減少了搜索次數(shù)，但通信量仍然很大。文獻［8］規(guī)定只有1位碰撞位時直接識別2個標(biāo)簽，文獻［9］規(guī)定只有2位碰撞位時直接識別，兩種改進都減少了搜索次數(shù)，但當(dāng)標(biāo)簽較少時出現(xiàn)符合規(guī)定的概率較小。

本文針對以上算法存在的不足，提出了一種新的基于分組策略的RFID自適應(yīng)防碰撞算法(AGS)，該算法在二叉樹搜索算法的基礎(chǔ)上引入分組策略、后退策略和自適應(yīng)地選擇四叉樹搜索策略，大幅度地降低了讀寫器的搜索次數(shù)，減少了標(biāo)簽與讀寫器間的通信量與延時，提高了識別效率。

1 AGS算法原理

根據(jù)標(biāo)簽內(nèi)部的計數(shù)器R的值將標(biāo)簽分為兩組:A組(R=0)標(biāo)簽ID中“1”的個數(shù)為偶數(shù);B組(R=1)標(biāo)簽ID中“1”的個數(shù)為奇數(shù)。讀寫器首先對A組標(biāo)簽發(fā)出搜索命令，符合條件的標(biāo)簽將自身的ID值傳送給讀寫器，讀寫器根據(jù)曼切斯特解碼檢測本次響應(yīng)標(biāo)簽的碰撞情況。若無碰撞，直接識別，讀寫器再對B組標(biāo)簽發(fā)出搜索命令;若有碰撞，則根據(jù)連續(xù)碰撞位的信息將該組標(biāo)簽分為不同的子集，即如果檢測到有3位連續(xù)的比特位發(fā)生碰撞，則立刻停止對ID進行編解碼，將該組標(biāo)簽分為“00”，“01”，“10”，“11”共4 個子集，并將已識別的比特位壓棧;如果檢測到3個非連續(xù)的比特位發(fā)生碰撞，則根據(jù)最高碰撞位的位置將該組標(biāo)簽分為“0”，“1”共2個子集。讀寫器繼續(xù)發(fā)出命令，直到標(biāo)簽信息不再發(fā)生碰撞，標(biāo)簽被成功識別，讀寫器采用后退策略，繼續(xù)發(fā)出前一條搜索命令，直到該組標(biāo)簽全部識別成功。具體算法流程如圖1所示。

圖1 AGS算法流程圖

2 算法協(xié)議

為便于實現(xiàn)和描述該算法，提出如下算法協(xié)議對算法進行約束。

1)請求命令Request。命令有3種形式:Request(null，p)，Request(x，q)和 Request(x，y，q)。

Request(null，p)中p為0或1，讀寫器第一次搜索時發(fā)送，要求讀寫器作用區(qū)域內(nèi)所有計數(shù)器R的值與p的值相同的標(biāo)簽響應(yīng);Request(x，q)中x為0或1，q為上一次搜索過程檢測到的最高碰撞位;Request(x，y，q)中x，y分別為0或1，q為最高碰撞位，當(dāng)上一次搜索過程檢測到連續(xù)的3位碰撞位時使用此命令。

2)如果讀寫器檢測到只有2個比特位發(fā)生碰撞時，讀寫器直接識別這2個標(biāo)簽。

3)當(dāng)讀寫器檢測到有3個比特位發(fā)生碰撞時，則立刻停止對ID進行編解碼。

4)根據(jù)檢測最高碰撞位連續(xù)個數(shù)自適應(yīng)地確定搜索樹的分叉數(shù)，即在某分支下檢測出最高碰撞位連續(xù)的個數(shù)大于等于3時，則選擇四叉樹搜索，否則選擇二叉樹搜索。

3 算法步驟

假設(shè)讀寫器作用區(qū)域內(nèi)有8個標(biāo)簽，各個標(biāo)簽的編碼及其識別過程如圖2所示。

圖2 算法的搜索識別過程

1)讀寫器發(fā)送命令Request(null，0)，讀寫器作用區(qū)域內(nèi)計數(shù)器R=0的所有標(biāo)簽均作出響應(yīng)。本例中，D7D6D5均發(fā)生碰撞，則q=7。

2)讀寫器發(fā)送命令Request(0，0，7)，即選擇D7D6為“00”的待命態(tài)標(biāo)簽，只有Tag4滿足條件，不存在沖突問題而直接識別。

3) 讀寫器發(fā)送命令 Request(0，1，7)，Tag3，Tag5 滿足條件并作出響應(yīng)。此時，讀寫器解碼得:1000??，只有2位碰撞位，由算法協(xié)議2)可知:讀寫器不必發(fā)送請求命令而直接識別 Tag3，Tag5。

4) 讀寫器發(fā)送命令 Request(1，0，7)，Tag1，Tag6，Tag7滿足條件并作出響應(yīng)。此時讀寫器解碼得:1?0??，最高碰撞位為D4。

5) 讀寫器發(fā)送命令Request(0，4)，Tag6，Tag7 滿足條件，并作出響應(yīng)。此時，讀寫器解碼得:000??，只有2位碰撞位，從而直接識別Tag6，Tag7。

6)讀寫器發(fā)送命令Request(1，4)，此時只有Tag1滿足條件，不存在沖突問題直接識別。

7)讀寫器發(fā)送命令Request(1，1，7)，此時只有Tag2滿足條件，直接識別。

8)讀寫器發(fā)送命令Request(null，1)，讀寫器作用區(qū)域內(nèi)計數(shù)器R=1的所有標(biāo)簽均作出響應(yīng)，此時只有Tag8滿足條件，不存在沖突問題而直接識別。

4 算法仿真分析

設(shè)讀寫器作用區(qū)域內(nèi)存在N個標(biāo)簽，標(biāo)簽ID為n位，由標(biāo)簽計數(shù)器R的值將N個標(biāo)簽分為兩組:R值為0的標(biāo)簽個數(shù)為N1個;R值為1的標(biāo)簽個數(shù)為N2個。讀寫器識別兩組標(biāo)簽的過程中，檢測到只有2個碰撞位的情況分別為M1，M2次，使用四叉樹時出現(xiàn)如圖3a的情況分別為 P1，P2次，出現(xiàn)如圖3c的情況分別為Q1，Q2次。

圖3 四叉樹代替二叉樹可能出現(xiàn)的3種情況

策略1:后退策略

基于后退策略的二進制搜索算法識別N個標(biāo)簽所需搜索次數(shù)為

策略2:自適應(yīng)策略

出現(xiàn)連續(xù)3位碰撞位時，采用四叉樹代替二叉樹有如圖3所示的3種情況。假如讀寫器作用區(qū)域內(nèi)存在00011101和00000001兩個標(biāo)簽時，產(chǎn)生如圖3a所示的情況，此時采用四叉樹比二叉樹增加了2次搜索;假如讀寫器作用區(qū)域內(nèi)存在00011101，00000001和00001001這3個標(biāo)簽時，產(chǎn)生如圖3b所示左邊的情況，此時采用四叉樹的搜索次數(shù)與二叉樹的搜索次數(shù)相同;假如讀寫器作用區(qū)域內(nèi)存在00011101，000110001，00000001和00001101這4個標(biāo)簽時，產(chǎn)生如圖3c所示的情況，此時采用四叉樹，比二叉樹減少了2次搜索。

策略3:分組策略

由算法協(xié)議2)可知，在識別A組標(biāo)簽的過程中檢測到M1次只有2個比特位發(fā)生碰撞時，采用本算法相當(dāng)于在二叉樹上減少了M1個葉子節(jié)點，即搜索次數(shù)減少2×M1次。

本算法將以上3種策略結(jié)合在一起，讀寫器識別計數(shù)器R=0的所有標(biāo)簽需要搜索次數(shù)為

同樣，讀寫器識別計數(shù)器R=1的所有標(biāo)簽需要搜索次數(shù)為

因此，采用本算法讀寫器識別其作用區(qū)域內(nèi)的所有標(biāo)簽所需的搜索次數(shù)為

本算法的吞吐率可表示為

在MATLAB仿真平臺上對本算法、四叉樹搜索算法、基于后退策略的二進制搜索算法、動態(tài)調(diào)整二進制搜索算法［8］和PDBS［9］進行仿真。目前 EPC 編碼體系中使用較多的是EPC-64。在仿真實驗中編碼位數(shù)n由標(biāo)簽數(shù)量決定?，F(xiàn)取n=8，n=16兩種情況分別對讀寫器發(fā)出的搜索次數(shù)和系統(tǒng)的吞吐率進行仿真，結(jié)果如圖4～圖7所示。

1)由圖4和圖5可看出:當(dāng)標(biāo)簽數(shù)目大于100時，與其余4種算法相比，本文算法的搜索次數(shù)明顯減少，吞吐率增幅很大。

圖7 n=16時吞吐率比較

2)由圖6和圖7可看出:當(dāng)標(biāo)簽位數(shù)和標(biāo)簽數(shù)目一定時，本文算法和PDBS算法明顯優(yōu)于四叉樹搜索算法、基于后退策略的二進制搜索算法和動態(tài)調(diào)整二進制搜索算法;隨著標(biāo)簽數(shù)目的增加，本文算法的吞吐率較PDBS算法及其他算法越來越高。

3)由圖4～圖7可看出:當(dāng)標(biāo)簽位數(shù)一定時，隨著標(biāo)簽數(shù)目的增加，將后退策略、分組策略和自適應(yīng)策略相結(jié)合的算法所得到的系統(tǒng)吞吐率明顯高于單純地選用四叉樹策略、后退策略或分組策略所得到的系統(tǒng)吞吐率。即當(dāng)標(biāo)簽位數(shù)一定時，隨著讀寫器作用區(qū)域內(nèi)的標(biāo)簽數(shù)量N的增大，檢測出只有2位比特位發(fā)生碰撞的概率越大，發(fā)生圖3c的概率也將遠大于發(fā)生圖3a的概率，即算法的吞吐率越大。

5 結(jié)束語

本文提出了一種基于分組策略的RFID自適應(yīng)防碰撞算法，該算法在二進制搜索算法的基礎(chǔ)上加入了分組策略、后退策略和自適應(yīng)策略。分組策略和自適應(yīng)策略的引入，有效地降低了標(biāo)簽間的碰撞次數(shù)，大幅地提高了讀寫器的吞吐率，再加上后退策略，又更進一步地減少了讀寫器與標(biāo)簽間的通信量。通過對新算法的性能分析及對仿真結(jié)果的比較證明，新算法更高效地解決了標(biāo)簽的碰撞問題，具有良好的應(yīng)用前景。

［1］劉云浩.物聯(lián)網(wǎng)導(dǎo)論［M］.北京:科學(xué)出版社，2011:33-37.

［2］王春華，許靜，彭關(guān)超，等.改進的RFID標(biāo)簽識別防沖突算法［J］.計算機工程與應(yīng)用，2011，47(31):104-107.

［3］FINKENZELLER K.RFID handbook fundamentals and applications in contactless smart cards and identification［M］.2nd ed.West Sussex:John Wiley ＆ Sons Ltd.，2003.

［4］郭志濤，程林林，周艷聰，等.動態(tài)幀時隙 ALOHA算法的改進［J］.計算機應(yīng)用研究，2012，29(3):907-909.

［5］RYU J，LEE H，SEOK Y，et al.A hybrid query tree protocol for tag collision arbitration in RFID systems［C］//Proc.IEEE International Conference on Communications.［S.l.］:IEEE Press，2007:5981-5986.

［6］CHEN Y H，HORNG S J，RUN R S，et al.A novel anti-collision algorithm in RFID systems for identifying passive tags［J］.IEEE Trans.Industrial Information，2010，6(1):105-121.

［7］丁治國，朱學(xué)永，雷迎科，等.基于啟發(fā)式函數(shù)的多叉樹防碰撞算法［J］. 計算機應(yīng)用，2012，32(3):665-668.

［8］謝振華，賴聲禮，陳鵬.RFID技術(shù)和防碰撞算法［J］.計算機工程與應(yīng)用，2007，43(6):223-225.

［9］伍繼雄，江岸，黃生葉，等.RFID系統(tǒng)中二叉樹防碰撞算法性能的提升［J］.湖南大學(xué)學(xué)報:自然科學(xué)版，2010，39(12):82-86.