韓振偉， 宋克非

(中國(guó)科學(xué)院長(zhǎng)春光學(xué)精密機(jī)械與物理研究所，吉林長(zhǎng)春130033)

0 引 言

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

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

1 EPC Gen2標(biāo)準(zhǔn)的防碰撞技術(shù)分析

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

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

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

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

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

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

2 Q算法性能分析

2.1 系統(tǒng)效率

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

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

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

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

為了得出最大系統(tǒng)效率時(shí)標(biāo)簽數(shù)量，對(duì)式(2)求導(dǎo)

對(duì)式(4)求解，得出當(dāng)幀長(zhǎng)度為L(zhǎng)時(shí)，最佳標(biāo)簽數(shù)量

圖1 多個(gè)標(biāo)簽響應(yīng)時(shí)序

由此，當(dāng)標(biāo)簽數(shù)量為n時(shí)，最佳幀長(zhǎng)度

當(dāng)n很大時(shí)，利用Taylor級(jí)數(shù)近似得出

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

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

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

2.2 幀長(zhǎng)度調(diào)整

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

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

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

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

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

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

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

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

圖4 大量標(biāo)簽情況下標(biāo)簽預(yù)測(cè)方案比較

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

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

圖5 Q算法

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

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

3 Q算法改進(jìn)

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

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

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

本文對(duì)此提出一種新的解決方案，簡(jiǎn)述如下：

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

當(dāng)產(chǎn)生新Q值newQ時(shí)，立即清除Qfp，恢復(fù)成newQ；

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

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

這樣，使幀長(zhǎng)度穩(wěn)定在最優(yōu)值范圍內(nèi)，相鄰?fù)ㄐ糯螖?shù)間減小Q值調(diào)整頻率。改進(jìn)后的Q算法讀取500個(gè)標(biāo)簽過程中動(dòng)態(tài)調(diào)整幀長(zhǎng)度的過程如圖8所示。

圖8 改進(jìn)后Q算法幀長(zhǎng)度調(diào)整過程

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

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

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

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

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

圖10 改進(jìn)后的Q算法識(shí)別效率

4 結(jié)束語

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

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