基于分組策略的RFID自適應防碰撞算法的研究

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

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

責任編輯:薛 京

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

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

1 AGS算法原理

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

圖1 AGS算法流程圖

2 算法協議

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

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

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

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

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

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

3 算法步驟

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

圖2 算法的搜索識別過程

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

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

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

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

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

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

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

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

4 算法仿真分析

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

圖3 四叉樹代替二叉樹可能出現的3種情況

策略1:后退策略

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

策略2:自適應策略

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

策略3:分組策略

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

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

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

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

本算法的吞吐率可表示為

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

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

圖7 n=16時吞吐率比較

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

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

5 結束語

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

［1］劉云浩.物聯網導論［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］郭志濤，程林林，周艷聰，等.動態幀時隙 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］丁治國，朱學永，雷迎科，等.基于啟發式函數的多叉樹防碰撞算法［J］. 計算機應用，2012，32(3):665-668.

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

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