射頻識別防碰撞Q算法的分析及改進

韓振偉， 宋克非

(中國科學院長春光學精密機械與物理研究所，吉林長春130033)

0 引 言

射頻識別(RFID)系統中，當讀寫器的天線輻射區域中有多個標簽同時存在時，多個標簽將幾乎同時響應讀寫器的指令，讀寫器不能正確接收標簽返回信號，這樣就產生了碰撞問題。RFID系統若能夠準確識別多個標簽，必需采取相應的防碰撞技術[1]。由于RFID系統的特殊性，標簽無源并且不具有載波監聽能力，防碰撞技術主要考慮如何提高系統效率和降低系統功耗。防碰撞技術設計的優劣很大程度上決定了RFID系統性能的優劣。高識別效率的RFID系統可以適應標簽數量巨大的場合；低功耗的RFID標簽不僅可以擴展標簽的使用距離，還可以延長標簽的使用壽命，進而降低整個RFID系統的成本。

由于時分多址方式(TDMA)應用簡單，并且容易實現大量標簽的讀寫，目前一般的防碰撞技術主要以TDMA方式實現。常用的方法有ALOHA法、時隙ALOHA法、幀時隙ALOHA(FSA)法和動態幀時隙ALOHA(DFSA)法。EPCglobal Class-1 Gen-2(以下簡稱EPC Gen2)標準采用的防碰撞Q算法是基于動態幀時隙ALOHA(DFSA)法。

1 EPC Gen2標準的防碰撞技術分析

EPC Gen2標準[2]中讀寫器采用3個基本操作命令來管理標簽。選擇操作用于讀寫器選擇特定的標簽群，以便于盤存操作和訪問操作。盤存操作用于讀寫器識別標簽。讀寫器發送Query命令，開始一個盤存周期，一個或一個以上的標簽可以響應。讀寫器檢測某個標簽響應，請求該標簽發出PC、EPC和CRC-16。訪問操作用于讀寫器對每個標簽讀取或寫入。

如果讀寫器的天線輻射區域中有多個標簽，當讀寫器發起盤存操作時，會產生碰撞問題。EPC Gen2標準防碰撞算法采用了基于動態幀時隙ALOHA法。在讀寫器開始對標簽群進行盤存時，讀寫器發出Query命令，Query命令含有一個參數Q，Q的取值范圍為1至15，該參數控制標簽往各自的時隙計數器內載入一個隨機數。當標簽接收到讀寫器QueryRep命令時，時隙計數器值減1。僅當標簽內時隙計數器值為0時，標簽才對讀寫器進行響應；當時隙計數器值不為0時，標簽不對讀寫器進行響應，而是根據讀寫器的不同命令，執行時隙計數器值繼續減1操作，或者根據新的Q參數值再次載入新的隨機數。已經閱讀成功的標簽，退出這輪標簽盤存。當有兩個或多個標簽的時隙計數器值同時為0時，這些標簽會同時對讀寫器進行響應，從而造成碰撞。讀寫器檢測到碰撞發生后，發出相關命令，讓碰撞標簽的時隙計數器值從 0變到0xFFFF，繼續留在這輪盤存周期內，以后讀寫器再設置新的Q參數值來分散發生碰撞的標簽。這個識別過程一直繼續下去，直到完成這輪盤存周期。

Query命令可能會出現以下3個結果：

(1)無標簽響應：讀寫器可以另外再發一個Query命令，或者也可以發出QueryAdjust或QueryRep命令。

(2)一個標簽響應：標簽轉換到應答狀態，反向散射一個RN16，讀寫器發送ACK予以確認。若標簽收到的ACK包含的RN16正確，則反向散射其PC、EPC和CRC-16，并轉換到確認狀態。若標簽收到的ACK所包含的RN16錯誤，則轉換到仲裁狀態。假設是RN16正確的ACK，則讀寫器可以訪問所確認的標簽。

(3)多個標簽響應：讀寫器觀察到由多個RN16組成的反向散射的波形，發送QueryAdjust或QueryRep命令，直至識別出每個標簽。圖1為多個標簽對讀寫器響應的時序圖。

2 Q算法性能分析

2.1 系統效率

在RFID系統工作過程中，讀寫器天線輻射區域中的標簽數量通常是未知的。大多數基于ALOHA的防碰撞算法先根據前一幀的反饋值(碰撞時隙數量ck、空閑時隙數量c0和成功時隙數量c1)，使用某一種標簽估算方法來估算出待識別的標簽數量n值，然后根據此數量值選擇一個最佳的幀長度做動態調整[3]。

假設讀寫器使用幀長度大小為L，天線輻射區域中的標簽數量為n，那么在一個給定的時隙內存在r個標簽的概率符合二項分布

因此，在一個盤存周期內期望識別的標簽數量為

式中：1,——在幀長度為L，待識別標簽數量為n的情況下，時隙中存在1個標簽的時隙數量。那么，系統效率可以計算得出

為了得出最大系統效率時標簽數量，對式(2)求導

對式(4)求解，得出當幀長度為L時，最佳標簽數量

圖1 多個標簽響應時序

由此，當標簽數量為n時，最佳幀長度

當n很大時，利用Taylor級數近似得出

由以上可得出，當幀長度L與標簽數量n值近似相等時，系統效率達到最大[4]，接近于時隙ALOHA算法的最大系統效率36.8%，如圖2所示。

圖2 各種幀長度下的系統效率

從圖2中可以看出，幀長度取不同值時，對于幀時隙ALOHA算法，系統效率在標簽數量等于幀長度時達到最大。讀寫器天線輻射區域中的標簽數量是動態變化的，若要使系統效率始終保持在35%以上，則必須使幀長度最大限度地適應現場標簽的數量n，即若能始終保持標簽數量n值在合適的幀長度范圍內，則可達到最優系統效率。

2.2 幀長度調整

若能準確估算出讀寫器天線輻射區域中標簽數量 n值，就可以實時地對幀長度值最優化。通?？梢酝ㄟ^以下幾種預測算法來估算標簽數量n值：

(1)LowerBound算法[5]：碰撞時隙數量為ck，碰撞時隙至少有2個以上的標簽存在，則可以預測發生碰撞的標簽數量至少為2*ck。

(2)Schoute算法[6]：在同一幀中，若每個標簽選擇的時隙符合 =1的泊松分布，則該幀中各碰撞時隙平均響應的標簽個數約為2.39，這樣可以預測未識別的標簽數量為2.39*ck。

(3)Vogt算法[7]：通過比較前一幀成功、空閑、碰撞時隙數量與理論的成功、空閑、碰撞時隙數量得出誤差最小的結果來預測未知標簽數量，即

其中，c1、ck、c0為實際測得的成功、空閑、碰撞時隙數值。在標簽數量N取值范圍[c1+2*ck，……，2*(c1+2*ck)]內找到最小的 值，所對應的N值就是預測的標簽數量。

圖3給出了采用Lowbound、Schout、Vogt這3種不同的標簽預測算法的系統效率仿真結果，它們均先預測確定現場可能的標簽數量后，然后動態調整最優幀長度。與幀時隙ALOHA算法(幀長度固定為256)相比，可以看出基于標簽數量預測的系統的效率有明顯改善，最高系統效率達到了36%。

圖3 系統效率比較

但從圖4看出，當現場標簽數量比較大(特別是標簽數量大于500)時，采用由預測標簽數量算法來設置最優幀長度的方案是不合適的，系統效率急劇下降，從32%下降至18%左右。

圖4 大量標簽情況下標簽預測方案比較

所以，為了使現場存在標簽數量大于500時系統效率得到提高，EPC Gen2標準中采用了Q算法的實時自適應幀時隙設置方案。當一個幀中出現過多的碰撞時隙時，讀寫器提前結束該幀然后發送一個新的更長的幀；當一個幀中出現過多的空閑時隙時，此幀也不是最優長度的幀，讀寫器提前結束該幀然后發送一個新的更短的幀。Q算法如圖5所示。

圖5中參數Q為正整數，取值范圍為0到15。幀長度為L=(2^Q)-1，Q值是動態變化的，初值取round(Qfp)。一個時隙之后，若該時隙是碰撞時隙，則將Qfp加上參數c；若是空閑時隙，則將Qfp減去參數c；若是成功時隙，則Qfp保持不變。讀寫器根據新的Q=round(Qfp)來決定是繼續發送下一個時隙還是重新開啟一個新的幀。

圖5 Q算法

圖6給出Vogt算法和Q算法兩種方案的系統效率仿真結果[8]。與Vogt算法相比，在讀寫器范圍內存在大量標簽時，Q算法系統效率明顯提高，接近于幀時隙ALOHA算法的最大系統效率38.6%。

圖6 Vogt算法和Q算法性能比較

3 Q算法改進

Q算法能夠在標簽數量變化很大的范圍內實現高系統效率主要取決于參數c的取值情況。c太大會造成幀長度調整過于頻繁，太小又不能快速的實現最優幀的選擇。在Q算法中，幀長度調整過于頻繁，即Q值變化過于頻繁，導致標簽頻繁地重新選擇時隙，這將帶來很大功耗負擔；同時，若幀長度不能實時調整到最優幀長度，則識別標簽速率迅速下降，系統效率也大大降低。因此，系統效率和功耗問題是相互矛盾的。僅僅依靠參數c的取值調整，并不能使幀長度最優地適應標簽數量，不能完全解決Q算法這一矛盾。

Q算法在參數c的輔助下對幀長度進行動態調整，從圖7中可看出在讀取500個標簽過程中動態調整幀長度的過程[9]。識別500個標簽需要讀寫器與標簽通信交互次數約1500多次。Q值在通信100次左右之后可以迅速調整到最佳幀長范圍內，但從200到1400之間，Q值不斷的做出調整，在7、8和9之間波動，即幀長度在128、256和512之間調整。在總的識別過程中，Q值跳動次數為280次。這樣非常密集的調整Q值，直接導致標簽內部頻繁地啟動隨機數發生器，從而選擇新的時隙。而標簽動態功耗量主要來自于標簽內部模擬電路和數字電路電平變化和翻轉，Q值調整次數每增加一次，意味著標簽動態功耗量增加一個固定值0.8uw(芯片電路設計和工藝不同，功耗略有差別)，從而如何減少Q值調整次數成為重點。

圖7 Q算法幀長度調整過程

本文對此提出一種新的解決方案，簡述如下：

當前Q值記為Q，產生碰撞累積得新Q值記為newQ，上一Q值記為oldQ；

當產生新Q值newQ時，立即清除Qfp，恢復成newQ；

若產生的新Q值newQ與oldQ相同，則保持當前Q值不變，oldQ更新；

若產生的新Q值newQ與oldQ不同，則Q值和oldQ同步更新。

這樣，使幀長度穩定在最優值范圍內，相鄰通信次數間減小Q值調整頻率。改進后的Q算法讀取500個標簽過程中動態調整幀長度的過程如圖8所示。

圖8 改進后Q算法幀長度調整過程

從圖8中可以看出，識別500個標簽需要讀寫器與標簽通信交互次數約1400多次。Q值在通信100次左右之后依然可以迅速調整到最佳幀長范圍內，但從200到1400之間，與改進之前的Q算法相比Q值調整次數明顯減少，即幀長度調整頻率變小，幀長度在128、256和512之間調整。在總的識別過程中，Q值跳動次數為51次。因此，標簽內部防碰撞模塊門電路翻轉頻率變小，隨機數發生器啟動次數也減少。

以識別500個標簽為例，Q算法防碰撞過程中，Q值調整280次，總動態功耗動態為224uw；改進Q算法后防碰撞過程中，Q值調整51次，總動態功耗為40.8uw，總動態功耗下降了81.8%。

從圖7中看出識別過程接近結束時，Q值不能夠迅速減小至盤存結束。并且Q值小于4，對識別標簽提高效率意義不大，故可進一步改進Q算法，使Q取值最小只能為4，幀時隙數最少為16。仿真結果如圖9所示。

圖9 改進后Q算法幀長度最小為16的調整過程

這樣，與原Q算法相比，改進后的Q算法調整幀長度頻率降低，并且盤存開始后，可以迅速進入最佳幀長范圍；盤存接近結束時幀長度保持固定長度，可以降低標簽動態功耗。同時，給出改進后的系統效率，如圖10所示。系統效率與原Q算法相比并未降低，依然維持在30%以上。

圖10 改進后的Q算法識別效率

4 結束語

對EPCGen2防碰撞Q算法進行了深入分析，研究了RFID系統標簽數量的3種不同估算方法，與Q算法比較了系統效率的優劣，并對Q算法提出改進方案。通過比較相鄰或相近的幀長度，使Q算法到達最優幀長度范圍內之后，幀長度調整頻率明顯減小，從而降低了標簽防碰撞過程中總動態功耗81.8%。同時，系統效率并沒有降低，依然保持在30%以上，標簽消耗的硬件資源沒有任何增加，可應用于低功耗遠距離RFID系統。

[1]劉亮,邢煥革,郭金衛.奇偶區域搜索反碰撞算法及其仿真分析[J].計算機工程與設計,2010,31(12):2740-2743.

[2]EPCglobal Inc.EPCTM radio-frequency identity protocols class-1 gen-2 UHF RFID protocol for communications at 860 MHz-960 MHz version 1.2.0[S].Lawrenceville:EPCglobal Inc,2008.

[3]Su-Ryun Lee,Sung-Don Joo,Chae-Woo Lee.An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification[C].Proceedings of the Second Annual International Conference on Mobile and Ubiquitous Systems,2005:166-172.

[4]Wang Jianwei,Wang Dong,Zhao Yuping.A novel anti-collision algorithm with dynamic tag number estimation for RFID systems[C].Proceedings of the IEEE International Conference on Communication Technology,2006:1-4.

[5]Jae-RyongCha,Jae-Hyun Kim.Dynamicframed slotted ALOHA algorithmsusingfast tag estimationmethodfor RFIDsystem[C].Proceedings of the IEEE International Conference on Consumer Communications,2006:768-772.

[6]Inwhee Joe,Juno Lee.A novel anti-collision algorithm with optimal frame size for RFID system[C].5th ACIS International Conference on Software Engineering Research,Management&Applications,2007:424-428.

[7]Tae-Wook Hwang,Byong-Gyo Lee.Improved anti-collision scheme for high speed identification in RFID system[C].First International Conference on Innovative Computing,Information and Control,2006:449-452.

[8]Cheng Jin,Sung Ho Cho.Performance evaluation of RFID EPC Gen2 anti-collision algorithm in AWGN environment[C].Proceeding of the IEEE International Conference on Mechatronics and Automation,2007:2066-2070.

[9]Tao Cheng,Li Jin.Analysis and simulation of RFID anti-collision algorithms[C].Proceedings of the 9th International Conference on Advanced Communication Technology,2007:697-701.