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

韓振偉， 宋克非

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

0 引 言

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

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

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

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

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

Query命令可能會出現(xiàn)以下3個結(jié)果：

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

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

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

2 Q算法性能分析

2.1 系統(tǒng)效率

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

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

因此，在一個盤存周期內(nèi)期望識別的標簽數(shù)量為

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

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

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

圖1 多個標簽響應時序

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

當n很大時，利用Taylor級數(shù)近似得出

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

圖2 各種幀長度下的系統(tǒng)效率

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

2.2 幀長度調(diào)整

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

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

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

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

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

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

圖3 系統(tǒng)效率比較

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

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

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

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

圖5 Q算法

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

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

3 Q算法改進

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

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

圖7 Q算法幀長度調(diào)整過程

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

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

當產(chǎn)生新Q值newQ時，立即清除Qfp，恢復成newQ；

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

若產(chǎn)生的新Q值newQ與oldQ不同，則Q值和oldQ同步更新。

這樣，使幀長度穩(wěn)定在最優(yōu)值范圍內(nèi)，相鄰通信次數(shù)間減小Q值調(diào)整頻率。改進后的Q算法讀取500個標簽過程中動態(tài)調(diào)整幀長度的過程如圖8所示。

圖8 改進后Q算法幀長度調(diào)整過程

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

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

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

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

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

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

4 結(jié)束語

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

[1]劉亮,邢煥革,郭金衛(wèi).奇偶區(qū)域搜索反碰撞算法及其仿真分析[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.