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

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

責任編輯:薛 京

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

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

1 AGS算法原理

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

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

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

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

3 算法步驟

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

圖2 算法的搜索識別過程

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

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

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

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

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

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

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

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

4 算法仿真分析

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

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

策略1:后退策略

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

策略2:自適應策略

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

策略3:分組策略

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

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

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

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

本算法的吞吐率可表示為

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

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

圖7 n=16時吞吐率比較

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

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

5 結束語

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

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

［2］王春華，許靜，彭關超，等.改進的RFID標簽識別防沖突算法［J］.計算機工程與應用，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］.計算機應用研究，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］丁治國，朱學永，雷迎科，等.基于啟發(fā)式函數(shù)的多叉樹防碰撞算法［J］. 計算機應用，2012，32(3):665-668.

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

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