劉金艷，馮全源

（西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，四川 成都 610031）

0 引言

無線射頻識別（Radio Frequency IDentification，RFID）是一種非接觸式自動識別技術(shù)，它通過射頻信號自動識別目標對象并獲取相關(guān)數(shù)據(jù)，識別工作無需人工干預(yù)，可工作于各種惡劣環(huán)境，在物聯(lián)網(wǎng)、供應(yīng)鏈、物流等領(lǐng)域中有著廣泛的應(yīng)用［1］。典型的RFID 系統(tǒng)主要由閱讀器、標簽和后臺計算機應(yīng)用系統(tǒng)三部分組成，標簽具有唯一的識別碼（IDentification code，ID），被貼附到待識別的物體上。

在RFID 應(yīng)用系統(tǒng)的一個閱讀器的天線作用范圍內(nèi)，常常同時存在多個標簽，當(dāng)閱讀器發(fā)出查詢命令后，往往會引起多個標簽同時響應(yīng)，這些響應(yīng)信息在共享的無線信道上發(fā)生碰撞，使響應(yīng)信號難以被閱讀器辨認，從而引起多標簽碰撞。閱讀器為完成對所有標簽的識別，應(yīng)將這些發(fā)生碰撞的標簽區(qū)分開來，再與它們逐個通信，閱讀器完成這些工作所使用的算法就是多標簽防碰撞算法［2-3］。

現(xiàn)有的多標簽防碰撞算法主要分為三類［4］：①基于Aloha的算法，又稱為隨機性算法；②基于樹的算法，又稱為確定性算法；③混合算法，將基于Aloha的算法和基于樹的算法相結(jié)合而產(chǎn)生的一種算法。

1 基于Aloha的防碰撞算法

基于Aloha的防碰撞算法的基本思想是：在閱讀器發(fā)現(xiàn)多標簽碰撞時，閱讀器命令其作用范圍內(nèi)的所有標簽隨機延遲一段時間再進行響應(yīng)，延遲時間的長度是以某種概率隨機選擇的。

1.1 基本的Aloha算法

早期的Aloha算法為純Aloha算法，該算法采用“標簽先發(fā)言”的方式，即標簽一進入閱讀器的作用區(qū)域就自動向閱讀器發(fā)送其自身的信息，對同一個標簽來說，其發(fā)送數(shù)據(jù)的時間是隨機的。在標簽發(fā)送信息的過程中，如果有其他標簽也在發(fā)送數(shù)據(jù)，就會發(fā)生信號重疊，導(dǎo)致部分碰撞或者完全碰撞。閱讀器檢測信號并進行判斷，一旦發(fā)現(xiàn)碰撞，閱讀器將發(fā)送命令讓標簽停止發(fā)送數(shù)據(jù)，所有標簽會隨機延遲一段時間再發(fā)送數(shù)據(jù)，由于延遲的隨機時間不同，再次發(fā)生碰撞的概率將明顯降低。如果沒有碰撞，則閱讀器發(fā)送一個應(yīng)答信號給標簽，標簽從此轉(zhuǎn)入休眠狀態(tài)。這種算法簡單，但吞吐率低，最大吞吐率僅能達到18.4%［5］。

該算法效率低的主要原因是碰撞發(fā)生的時間是隨機的，其中包括：當(dāng)一個標簽在與閱讀器通信的過程中，有可能因其他標簽的突然響應(yīng)而被破壞，即存在部分碰撞問題。為此，人們提出時隙Aloha算法（Slotted Aloha，SA）［5］，把時間分成多個離散時隙，標簽只在每個時隙的開始時刻才能發(fā)送數(shù)據(jù)。算法的基本原理是：閱讀器通過發(fā)送命令通知標簽有多少時隙，標簽隨機選擇發(fā)送信息的時隙。如果某個時隙只有一個標簽響應(yīng)，則閱讀器可正確地識別標簽；如果某個時隙有多個標簽響應(yīng)，則會發(fā)生碰撞，閱讀器通知標簽，標簽便在下一輪循環(huán)中重新隨機選擇發(fā)送的時隙，直到所有的標簽都被識別出來。

在SA 算法中，標簽或成功識別或完全碰撞，避免了純Aloha算法中出現(xiàn)的部分碰撞問題。SA 算法的最大吞吐率可達36.8%［5］。

1.2 FSA與DFSA

對于SA 算法，在發(fā)生碰撞時，標簽延遲的隨機性范圍很大，影響了其平均響應(yīng)速度。為此，規(guī)定若干個時隙為一幀，標簽選擇的隨機延遲必須是幀內(nèi)的某個時隙，這就是幀時隙Aloha（Framed Slotted Aloha，F(xiàn)SA）算法。

FSA 算法的缺點是幀長固定，這樣當(dāng)標簽數(shù)量較少時，存在時隙浪費，而當(dāng)標簽數(shù)較多時，碰撞解決的效果又不是很好。因此，可以考慮根據(jù)標簽數(shù)量動態(tài)地調(diào)整幀長，即動態(tài)幀時隙Aloha（Dynamic Framed Slotted Aloha，DFSA）算法［6-7］。

研究結(jié)果表明，最優(yōu)的幀長應(yīng)該等于標簽數(shù)量［7］，因此只要知道了標簽數(shù)量，就可以確定幀長，然而當(dāng)前幀需識別的標簽數(shù)量通常無法預(yù)知，只能對其進行估算。因此在DFSA 算法中，非常重要的一項工作就是標簽數(shù)量的估計，大多數(shù)方法都是根據(jù)上一幀的幀長、標簽個數(shù)、沖突情況來估計當(dāng)前幀中的標簽數(shù)。典型方法包括：

（1）Vogt方法［8］設(shè)碰撞時隙數(shù)為Ck，碰撞時隙內(nèi)至少有2 個以上的標簽存在，則可以預(yù)測發(fā)生碰撞的標簽數(shù)量至少為2×Ck。

（2）標簽估計方法Ⅰ（Tag Estimation MethodⅠ，TEM Ⅰ）［7］將碰撞率Cratio定義為碰撞時隙數(shù)與幀長的比值，L 為幀長，n 為標簽個數(shù)，則它們之間的關(guān)系為

由于上一幀的幀長L 和碰撞率Cratio已知，可以計算出標簽個數(shù)n。

（3）TEMⅡ方法［7］設(shè)nest為估算的標簽數(shù)量，Mcoll為上一幀中的碰撞時隙數(shù)，則

1.3 FSA的各種改進算法

在固定幀長的Aloha算法中，當(dāng)標簽數(shù)量太多時，沖突時隙較多；而當(dāng)標簽數(shù)量太少時，又會有大量的空閑時隙?；谶@一點，各種改進算法被提出。

1.3.1 分群時隙Aloha算法

分群時隙Aloha算法［9］根據(jù)碰撞時隙在所分配時隙中所占的比例，來確定是否分群。如果碰撞時隙的比例（發(fā)生碰撞的時隙數(shù)／分配的時隙數(shù)）大于分群因子γ，則進行分群。分群后，第一個分群內(nèi)的標簽響應(yīng)閱讀器的查詢命令，另一個分群內(nèi)的標簽處于等待狀態(tài)。當(dāng)?shù)谝粋€分群內(nèi)的所有標簽識別完畢后，第二個分群內(nèi)的標簽再進行響應(yīng)，直至所有標簽識別完畢。

仿真結(jié)果表明，分群時隙Aloha算法優(yōu)于固定時隙Aloha算法，且隨著標簽數(shù)量的增加，算法的優(yōu)越性更明顯。同時，分群因子的選擇是影響算法的關(guān)鍵因素，在標簽數(shù)量較多時，分群因子宜選擇較小值。

1.3.2 自適應(yīng)的動態(tài)幀時隙Aloha算法

文獻［10］考慮某些應(yīng)用場合中閱讀器需要對標簽進行重復(fù)識別的要求，充分利用上一幀已識別標簽的信息，提出自適應(yīng)的動態(tài)幀時隙Aloha算法，該算法每成功識別一個標簽就給標簽分配一個時隙號，該時隙號規(guī)定了標簽被閱讀器識別的順序。如果在下次識別過程中閱讀器要重復(fù)識別這些標簽，則可根據(jù)已分配的時隙號按順序進行，從而避免標簽間的沖突，減少識別時間。當(dāng)離去標簽和新到達標簽數(shù)量較少時，系統(tǒng)效率較高，但是當(dāng)有大量的新到達標簽時，僅采用上述方法將導(dǎo)致沖突急劇增加。為減少沖突，閱讀器應(yīng)估計標簽數(shù)，并根據(jù)標簽數(shù)合理調(diào)整幀長。文獻［10］提出了一種最優(yōu)幀長方案，使系統(tǒng)獲得了較大的吞吐量。

1.4 Q 值算法及其改進算法

DFSA 算法可采用各種方法預(yù)測待識別的標簽數(shù)量，然后動態(tài)調(diào)整最優(yōu)幀長，與FSA 相比，系統(tǒng)效率有明顯改善，接近36.8%。但是，當(dāng)標簽數(shù)量較多（特別是標簽數(shù)量大于500）時，采用由預(yù)測標簽數(shù)量設(shè)置最優(yōu)幀長的方案會使系統(tǒng)效率急劇下降［11］。因此，在標簽數(shù)量較多的情況下，為了使系統(tǒng)效率得到提高，EPC Class1Gen 2標準［12］中采用了Q 值算法，該算法可以實時自適應(yīng)地調(diào)整幀長。

1.4.1 Q 值算法

在Q 值算法中，閱讀器首先發(fā)送Query命令，該命令中含有一個參數(shù)Q（取值范圍0～15），接收到命令的標簽可在［0，2Q-1］范圍內(nèi)（稱為幀長）隨機選擇時隙，并將選擇的值存入標簽的時隙計數(shù)器中，只有計數(shù)器為0的標簽才能響應(yīng)，其余標簽保持沉默狀態(tài)。當(dāng)標簽接收到閱讀器發(fā)送的QueryRep命令時，將其時隙計數(shù)器減1，若減為0，則給閱讀器發(fā)送一個應(yīng)答信號。標簽被成功識別后，退出這輪盤存。當(dāng)有兩個以上標簽的計數(shù)器都為0時，它們會同時對閱讀器進行應(yīng)答，造成碰撞。閱讀器檢測到碰撞后，發(fā)出指令將產(chǎn)生碰撞的標簽時隙計數(shù)器設(shè)為最大值（2Q-1），繼續(xù)留在這一輪盤存周期中，系統(tǒng)繼續(xù)盤存直到所有標簽都被查詢過，然后閱讀器發(fā)送重置命令，使碰撞過的標簽生成新的隨機數(shù)。

根據(jù)上一輪識別的情況，閱讀器發(fā)送Query-Adjust命令來調(diào)整Q 的值，當(dāng)標簽接收到Query-Adjust命令時，先更新Q 值，然后在［0，2Q-1］范圍內(nèi)選擇隨機值。

EPC Class1Gen 2標準［12］中提供了一種參考算法來確定Q 值的范圍，如圖1所示。其中：Qfp為浮點數(shù)，其初值一般設(shè)為4.0，對Qfp四舍五入取整后得到的值即為Q；C 為調(diào)整步長，其典型取值范圍是0.1＜C ＜0.5，通常當(dāng)Q 值較大時，C 取較小的值，而當(dāng)Q 值較小時，C 取較大的值。

當(dāng)閱讀器發(fā)送Query命令進行查詢時，若應(yīng)答標簽數(shù)等于1，則Q 值不變；若應(yīng)答標簽數(shù)等于0（空閑時隙），則減小Q 值；若應(yīng)答標簽數(shù)大于1（沖突時隙），則增大Q 值。

該算法在參數(shù)C 的輔助下對Q 值進行動態(tài)調(diào)整，但是C 太大會造成Q 值變化過于頻繁，導(dǎo)致幀長調(diào)整過于頻繁，C 太小又不能快速地實現(xiàn)最優(yōu)幀長的選擇。因此，研究者們對Q 值的調(diào)整進行了各種優(yōu)化。

1.4.2 基于最大吞吐量調(diào)整Q 值的算法

文獻［13］提出一種基于最大吞吐量對Q 值進行調(diào)整的算法，其中定義了以下變量：

Nt為已識別的標簽個數(shù)；

N 為識別標簽所需的總時隙數(shù)；

NC為沖突時隙的個數(shù)；

nu為上一輪未識別的標簽個數(shù)；

e為沖突時隙中的平均標簽個數(shù)；

PC為沖突時隙所占的比例。

這些參數(shù)之間的關(guān)系為PC=NC／N，e=nu／Nc，吞吐量=Nt／N。

由于Aloha 類算法的最大吞吐量為0.368（e-1）［5］，該算法以此作為調(diào)整Q 值的依據(jù)。當(dāng)系統(tǒng)吞吐量達到或接近0.368時，閱讀器僅需調(diào)用2Q-1次QueryRep 命令，而不需要在接下來的盤存周期中調(diào)整Q 值。當(dāng)吞吐量小于0.368時，根據(jù)未識別的標簽個數(shù)nu來調(diào)整Q 值，具體方法如下：

（1）統(tǒng)計上一個盤存周期中的沖突時隙個數(shù)NC和總時隙數(shù)N，并計算出PC。

（2）根據(jù)e和PC的關(guān)系（式（3））［14］計算出e，

從而計算出nu=e×NC。

（3）根據(jù)“最優(yōu)幀長等于待識別的標簽個數(shù)”，可知2Q-1=nu，由此得出Q=［log2（nu+1）］。

該算法減少了對Q 值的調(diào)整次數(shù)，避免了標簽頻繁地在［0，2Q-1］范圍內(nèi)選擇隨機值，減少了標簽的能量消耗。該算法的吞吐量基本可以達到最大值0.368，且識別標簽所需的總時隙數(shù)和吞吐量均優(yōu)于原Q 值算法。

1.4.3 基于分組的位隙Aloha算法

文獻［15］提出一種基于分組的位隙Aloha算法，該算法采用位隙Aloha算法中的128位預(yù)定序列，代表128個位隙。若某個標簽選擇了第i個位隙，則將第i位置1，其余各位都置0。當(dāng)標簽數(shù)量為15 時，位隙Aloha 算法可獲得最大吞吐率88.38%［15］，但隨著標簽數(shù)量的增加，算法性能急劇下降。

因此，基于分組的位隙Aloha算法通過對標簽進行分組來提高算法的性能。該算法在查詢命令中設(shè)置了一個位隙計數(shù)器的參數(shù)Q（Q 為整數(shù)，且0≤Q≤15）［12］，當(dāng)標簽收到閱讀器發(fā)送的查詢命令后，在［0，2Q-1］范圍內(nèi)生成一個隨機數(shù)，即代表選擇了相應(yīng)的位隙，只有選擇了0的標簽才會立即響應(yīng)。同時，該算法根據(jù)沖突位隙數(shù)動態(tài)地對Q 值進行調(diào)整：當(dāng)沖突位隙數(shù)小于11時，Q 減1且最小為0；當(dāng)沖突位隙數(shù)在11～20之間時，Q 保持不變；當(dāng)沖突位隙數(shù)大于20時，Q 加1且最大不超過15。

綜上所述，基于Aloha 的防碰撞算法原理簡單、容易實現(xiàn)，對新到達的標簽具有較好的適應(yīng)性，尤其對于標簽持續(xù)到達的情況有較好的解決方案［16］，但該類算法存在幾個明顯的缺點：①響應(yīng)時間不確定，即同一批標簽在不同時刻進行識別所需要消耗的時間相差很大；②個別標簽可能永遠無法被識別；③Aloha算法達到最佳吞吐率的條件是其幀長等于標簽數(shù)量，當(dāng)需要識別的標簽數(shù)量較多或選擇的幀長與實際待識別標簽數(shù)量不符時，系統(tǒng)性能將明顯下降。而基于樹的算法則很好地解決了這些問題。

2 基于樹的防碰撞算法

基于樹的防碰撞算法又可進一步分為樹分裂（Tree Splitting，TS）算法和查詢樹（Query Tree，QT）算法兩類。

2.1 樹分裂算法及其改進算法

在TS算法中，將發(fā)生沖突的標簽分成兩個子集，第一個子集的標簽在下一個時隙響應(yīng)，若其內(nèi)部又發(fā)生沖突，則再次進行分裂，如此遞歸地進行分裂操作，直到子集中只有1個標簽為止，此時標簽即可被唯一識別。待第一個子集的沖突全部解決后，再對第二個子集執(zhí)行類似操作［3］。該算法要求標簽具有隨機數(shù)生成器，當(dāng)發(fā)生沖突時，標簽隨機地生成二進制數(shù)0或1，從而將標簽分成兩個子集。

2.1.1 基本的樹分裂算法

在TS算法中，最基本的是Hush［17］提出的基本樹分裂（Basic Tree Splitting，BTS）算法。閱讀器首先與其作用范圍內(nèi)的所有標簽通信，標簽對閱讀器的查詢作出響應(yīng)，顯然在當(dāng)前時隙會產(chǎn)生沖突。每個沖突的標簽都會生成一個二進制隨機數(shù)0 或1，因此可以將沖突的標簽集合分成兩個子集L（生成的隨機數(shù)為0的標簽）和R（生成的隨機數(shù)為1的標簽），在下一個時隙，子集L 中的標簽傳輸數(shù)據(jù)。如果子集L 中仍然存在沖突，則其中的標簽又會生成一個隨機數(shù)，對子集L 進行再次分裂。如此循環(huán)操作，直至子集中只有1個標簽。

該算法實現(xiàn)簡單，但由于沖突和空閑時隙較多，識別標簽所需的總時隙數(shù)較多。

2.1.2 自適應(yīng)二進制分裂算法

Myung等［18-19］提出一種自適應(yīng)二進制分裂（Adaptive Binary Splitting，ABS）算法，該算法設(shè)置了兩種時隙計數(shù)器：①進展時隙計數(shù)器PC，表示閱讀器已經(jīng)識別的標簽數(shù)，其初始值為0；②分配時隙計數(shù)器AC（i），表示標簽ti傳送數(shù)據(jù)的時隙，即當(dāng)PC=AC（i）時，允許標簽ti在當(dāng)前時隙發(fā)送數(shù)據(jù)。具有相同AC值的標簽形成了一個集合，若一個集合中包含了多個標簽，就會產(chǎn)生標簽沖突。

根據(jù)閱讀器反饋信息的不同，標簽的識別過程如下：

（1）若成功讀取一個標簽，則PC加1。

（2）若為空閑時隙，則AC（i）減1。

（3）若為沖突時隙，則產(chǎn)生沖突的標簽的AC（i）=PC，為將其分成兩個子集，標簽ti生成一個隨機的二進制數(shù)并將它加到AC（i）上。因為PC不變，所以生成的隨機數(shù)為0的標簽構(gòu)成第1個子集，它在下一個時隙重新發(fā)送數(shù)據(jù)；生成的隨機數(shù)為1的標簽構(gòu)成第2個子集，它在第1個子集被識別后再發(fā)送數(shù)據(jù)。處于等待狀態(tài)（即AC（i）＞PC）的標簽的AC（i）都加1。

識別過程結(jié)束后，所有標簽都具有唯一的AC值。

為了在識別出所有標簽后能立即終止識別過程，將閱讀器看成是具有最大分配時隙數(shù)的一個標簽，用RC（r）表示閱讀器r的分配時隙數(shù)。當(dāng)PC=RC（r）時，閱讀器r認為所有標簽已識別完畢，結(jié)束識別過程。

ABS算法比BTS算法有效地降低了沖突和空閑時隙數(shù)，因此效率有所提高。但是ABS算法對標簽集合進行分裂時主要依靠標簽產(chǎn)生的二進制隨機數(shù)，并不能保證產(chǎn)生隨機數(shù)0和1的概率總是等于50%（尤其當(dāng)二進制序列較短時，如001，000，其中0和1出現(xiàn)的概率都不是50%），因此ABS算法不能獲得最好的分裂結(jié)果。

2.1.3 增強型防碰撞算法

文獻［20］對ABS算法進行了改進，提出增強型防碰撞算法（Enhanced Anti-collision Algorithm，EAA），該算法采用曼徹斯特編碼，可以準確地判斷產(chǎn)生沖突的位，因此當(dāng)有沖突發(fā)生時，閱讀器只接收到第2個沖突位，之后的數(shù)據(jù)不再接收。

EAA 算法仍然采用ABS算法中提出的PC和AC，并將時隙劃分為：

（1）可讀時隙 只有一個標簽響應(yīng)。

（2）沖突時隙 有多個標簽的AC（i）=PC，且產(chǎn)生沖突的位大于等于2位。

（3）只有1位沖突的時隙（One Bit Collided Timeslot，OBCT）有多個標簽的AC（i）=PC，并且產(chǎn)生沖突的只有1位。

對于OBCT，根據(jù)二進制數(shù)非0即1的特性，可以一次識別2個標簽，從而大大提高算法性能。該算法不僅減少了識別標簽所需的時隙數(shù)量，而且減少了時隙長度。

在文獻［20］的基礎(chǔ)上，文獻［21］做了進一步改進，其主要內(nèi)容為：①根據(jù)產(chǎn)生沖突的最高位是0還是1，決定對AC（i）加0還是1，從而對標簽集合進行分裂，避免了ABS算法中根據(jù)隨機產(chǎn)生的二進制數(shù)對標簽集合進行分裂所產(chǎn)生的缺點（如所有標簽產(chǎn)生的隨機數(shù)都為1，將導(dǎo)致下一個時隙為空閑時隙）；②利用棧和Tstring存放閱讀器已接收到的響應(yīng)信息。改進后的算法識別N 個標簽所需的總時隙數(shù)為2 N-1-2k（k為OBCT 的個數(shù)）。

2.1.4 新增強型防碰撞算法

由于EAA 算法在一個時隙中最多只能識別2個標簽，針對這一缺點，文獻［22］做了進一步改進，提出新型增強型防碰撞算法（New Enhanced Anticollision Algorithm，NEAA），其主要思想如下：

（1）根據(jù)標簽ID 中含1的位數(shù)，將標簽分成n+1個子集set＿i（0≤i≤n，n為標簽ID 的長度），子集set＿i中每個標簽的ID 都有i個數(shù)位為1。例如，0000，0001，1111分別屬于子集set＿0，set＿1和set＿4。閱讀器依次識別每個子集中的標簽。

（2）在一個時隙中識別多個標簽。子集set＿1（或set＿（n-1））中的標簽的ID 只有一位為1（或為0），假設(shè)set＿1 中有3 個標簽，其ID 分別為0001，0010，1000，當(dāng)3個標簽同時響應(yīng)時，閱讀器接收到的響應(yīng)為X0XX（X 表示產(chǎn)生了沖突的位），因為標簽的ID 中只有一位為1，所以閱讀器可以很容易地確定接收到的X0XX 是由3個標簽產(chǎn)生的，只需依次將三個X 置1，就可以分別得到3個標簽的ID，從而可以在一個時隙識別3個標簽。

（3）仍然采用ABS算法中提出的PC和AC（i），并將時隙分為四種類型：

1）可讀 只有1個標簽的AC（i）=PC。

2）有多個標簽可讀 有多個標簽的AC（i）=PC，并且這些標簽屬于集合set＿1或set＿（n-1）。

3）沖突 有多個標簽的AC（i）=PC，并且這些標簽不屬于集合set＿1或set＿（n-1）。

4）空閑 沒有標簽的AC（i）=PC。

NEAA 算法可以在一個時隙中識別多個標簽，從而減少了識別標簽所需的時隙數(shù)量。另一方面，NEAA 算法也減少了標簽與閱讀器的信息傳輸量，從而減少了時隙的長度。

2.1.5 二進制矩陣搜索算法

文獻［23］提出二進制矩陣搜索算法，該算法保持了后退式二進制樹形搜索算法［24］的后退機理，當(dāng)有碰撞發(fā)生時，根據(jù)碰撞的最高位跳躍式向前搜索；無碰撞時，采取后退策略實現(xiàn)標簽的有序讀取。與后退式二進制樹形搜索算法相比，該算法主要在以下方面進行了改進：

（1）因為后退式二進制樹形搜索算法發(fā)送的指令中，沖突位之后的低位部分全為1并沒有任何實際意義，反而加大了閱讀器和標簽之間的通信量，所以本算法中的指令長度可以動態(tài)調(diào)整，只發(fā)送位數(shù)高于或等于沖突位的指令位。

（2）基于一位沖突直接識別，當(dāng)只探測到一位碰撞位時，根據(jù)二進制數(shù)非0即1的特性，可直接識別出2個標簽的ID 數(shù)據(jù)。

該算法所需的查詢次數(shù)和通信量均優(yōu)于后退式二進制樹形搜索算法。

2.1.6 自適應(yīng)分裂樹算法

文獻［25］提出自適應(yīng)分裂樹防碰撞算法，其核心思想是：在碰撞發(fā)生的時隙內(nèi)，結(jié)合碰撞集規(guī)模估計（對標簽反饋的脈沖信號進行強度疊加，然后閱讀器根據(jù)信號幅值來判定碰撞集內(nèi)的標簽規(guī)模）的結(jié)果，確定碰撞標簽的分裂規(guī)模SBC，并由閱讀器將SBC 作為碰撞指令的參數(shù)反饋給標簽。

該算法的具體實現(xiàn)流程為：在所有標簽內(nèi)實現(xiàn)一個計數(shù)器，將其初始化為0；閱讀器發(fā)出查詢指令后，僅計數(shù)器等于0的標簽可以應(yīng)答。若出現(xiàn)碰撞，則閱讀器估計出當(dāng)前碰撞標簽規(guī)模N，根據(jù)線性模型SBC=factor×N（其中factor為分裂因子）計算出SBC 的值，并將其反饋給標簽；所有計數(shù)器為0的標簽（即上輪應(yīng)答標簽）都生成一個隨機數(shù)，并對SBC 取余（結(jié)果用m 表示），然后將計數(shù)器值加上m，而其他標簽的計數(shù)器值加上SBC-1。反復(fù)進行這一過程，直至出現(xiàn)唯一的應(yīng)答標簽。在成功識別標簽或本輪沒有標簽應(yīng)答時，所有標簽計數(shù)器均減1。與此同時，已被成功識別的標簽需置靜默態(tài)，在本輪識別過程中不再響應(yīng)閱讀器。循環(huán)執(zhí)行，即可以完成所有標簽的識別。

當(dāng)factor取值為0.8時［25］，系統(tǒng)效率最高。該算法可根據(jù)產(chǎn)生碰撞的標簽的數(shù)量來選擇SBC 值，從而動態(tài)地調(diào)整分裂規(guī)模，加快標簽分裂的過程，減少碰撞時隙。

2.1.7 自適應(yīng)多叉樹防碰撞算法

文獻［26］提出一種自適應(yīng)多叉樹防碰撞算法，該算法通過統(tǒng)計碰撞比特出現(xiàn)的概率估計分支內(nèi)標簽的數(shù)量，根據(jù)搜索深度和分支內(nèi)的標簽數(shù)靈活地選擇分叉數(shù)量。該算法中提出了碰撞因子μ 的概念，將其定義為：在碰撞時隙內(nèi)碰撞比特占標簽響應(yīng)比特位的比值。通過理論分析確定了當(dāng)μ≥0.75時，選擇四叉樹進行下一層搜素；當(dāng)μ＜0.75時，選擇二叉樹進行下一層搜素。仿真結(jié)果表明，從識別標簽所需的總時隙數(shù)和吞吐率來看，該算法的性能優(yōu)于其他算法。

2.2 查詢樹算法及其改進算法

在TS及其改進算法中，要求標簽具備隨機數(shù)生成器和計數(shù)器，增加了標簽的設(shè)計復(fù)雜度，從而提高了設(shè)計成本［2］。為此，人們研究出了QT 算法，該算法僅要求標簽具有前綴匹配電路即可，大大降低了標簽的設(shè)計復(fù)雜度。

2.2.1 基本的查詢樹算法

在基本的QT 算法［27］中，閱讀器首先向所有標簽廣播一個前綴，標簽將接收到的前綴與自己的ID進行比較，若匹配，則進行響應(yīng)，將自己的ID 號的未匹配部分發(fā)送給閱讀器。如果有多個標簽響應(yīng)，就會出現(xiàn)沖突，此時閱讀器在前綴后面增加一位（0或1），生成新的前綴，再用新前綴進行查詢。如此重復(fù)，直到只有一個標簽響應(yīng)為止。

由于基本的QT 算法每次只對前綴擴展一位，沖突時隙較多，算法運行時間較長；而在每一次產(chǎn)生沖突時，標簽都要將其ID 傳送給閱讀器，但實際上，此時傳輸?shù)男畔⒉]有意義，導(dǎo)致傳輸?shù)男畔⒘看?。為此，人們對QT 算法進行了各種改進，主要集中在兩方面：①如何一次使前綴擴展的位數(shù)盡量多，從而減少識別標簽所需的總時隙數(shù)；②如何使標簽和閱讀器間傳輸?shù)男畔⒘勘M量少。

2.2.2 shortcutting QT，QT-sl和QT-im

為了縮短QT 算法的運行時間，文獻［27］提出shortcutting QT 算法。若閱讀器在查詢前綴q 時發(fā)現(xiàn)了沖突，則將在q后面加上0或1后，繼續(xù)查詢新的前綴。如果閱讀器先查詢q0，沒有標簽響應(yīng)，則前綴為q1的標簽就至少有2 個，肯定會產(chǎn)生沖突，因此可以跳過前綴q1，直接查詢前綴q10和q11，由此形成了shortcutting QT 算法。

為了減少傳輸?shù)男畔⒘?，文獻［27］提出短長QT（QT short-long，QT-sl）算法和增量匹配QT（QT incremental-matching，QT-im）算法。在QTsl算法中，閱讀器的查詢分為短查詢和長查詢兩種，對于短查詢，標簽只需以一位進行響應(yīng)；而對于長查詢，標簽以其完整ID 號進行響應(yīng)。閱讀器確定只有一個標簽與前綴匹配時，才會進行長查詢。在QTim 算法中，要求標簽記住閱讀器上一輪發(fā)送的前綴，而在當(dāng)前查詢中，閱讀器只發(fā)送前綴中新增加的部分。例如：假設(shè)上一輪的查詢前綴為q，則在接下來的查詢中，閱讀器只發(fā)送0或1，而不是發(fā)送q0或q1，從而減少了傳輸?shù)男畔⒘俊?/p>

2.2.3 跳躍式動態(tài)樹形防碰撞算法

在跳躍式動態(tài)樹形防碰撞算法［28］中，標簽ID采用曼徹斯特編碼，并以標簽ID 發(fā)生碰撞的最高位作為下一次查詢的依據(jù)。假設(shè)標簽ID 的長度為m，第1位為最高位，第m 位為最低位，并假設(shè)發(fā)生碰撞的最高位是第x 位。

閱讀器首先發(fā)送一個查詢前綴ID1～x（標簽ID值的第1～x 位）給所有標簽，與之匹配的標簽應(yīng)答，返回剩余的m-x 位信息（第x+1～m 位），將這一操作用命令request（ID1～x，x）表示。

算法的基本思想是：

（1）閱讀器首先發(fā)送request（NUL，0）命令，要求區(qū)域內(nèi)所有標簽響應(yīng)。

（2）檢測有無碰撞發(fā)生，若有，則確定碰撞的最高位。

（3）將碰撞的最高位置0，高于該位的數(shù)值位不變，可得ID1～x值，得到下一次request命令所需的兩個參數(shù)。

（4）若無碰撞發(fā)生，則可識別出一個標簽。標簽ID 值為原ID1～x和應(yīng)答時返回的IDx+1～m的組合，處理完后，將該標簽設(shè)為啞狀態(tài)。同時，采用回跳策略從其父節(jié)點獲得下一次request命令所需的兩個參數(shù)。

（5）重復(fù)以上過程，直到執(zhí)行request（NUL，0）時無碰撞發(fā)生為止。

與傳統(tǒng)的QT 算法相比，該算法識別標簽所需的詢問次數(shù)明顯減少，閱讀器識別N 個標簽所需的詢問次數(shù)為2 N-1［28］。

2.2.4 碰撞樹算法

文獻［29］中提出碰撞樹（Collision Tree，CT）算法，其基本思想與跳躍式動態(tài)樹形防碰撞算法［28］有一定相似之處，都是以標簽ID 發(fā)生碰撞的最高位作為下一次查詢的依據(jù)。但CT 算法在檢測到碰撞發(fā)生的最高位（假設(shè)為第x 位）時，不是簡單地將碰撞的最高位置0，而是將其分別設(shè)為0和1，由此產(chǎn)生兩個新的查詢前綴ID1～（x-1）0和ID1～（x-1）1，對之后的查詢過程進行分裂。以前綴ID1～（x-1）0進行查詢時，其過程與文獻［28］相同，但在進行下一次查詢時，所需的前綴已確定為ID1～（x-1）1，并不需要采用回跳策略從父節(jié)點獲取。

與QT 算法相比，該算法在性能上有了很大的提升，其性能僅依賴于待識別的標簽數(shù)量，與標簽ID 的分布無關(guān)，并且當(dāng)標簽數(shù)量較多時，平均時間復(fù)雜度、平均通信復(fù)雜度、吞吐率都接近常數(shù)［30］。

但是，該算法也存在一定的缺點，即檢測到碰撞發(fā)生的最高位時，會產(chǎn)生兩個新的查詢前綴ID1～（x-1）0和ID1～（x-1）1，這兩個前綴的前x-1位都相同，只有最后一位不同，在接下來進行的兩次查詢中，傳輸?shù)男畔⒋嬖诤艽蟮闹貜?fù)，因此閱讀器可以將兩次查詢合并為一次，只發(fā)送查詢前綴的前x-1位，與之匹配的標簽，第x 位為0則在第一個時隙響應(yīng)，第x 位為1則在第二個時隙響應(yīng)。

2.2.5 自適應(yīng)的查詢分裂算法

與QT 算法相似，自適應(yīng)的查詢分裂（Adaptive Query Splitting，AQS）算法［19，31］也是由閱讀器廣播一個前綴，標簽將接收到的前綴與自己的ID 進行比較，若匹配，則進行響應(yīng)。但是，AQS算法從上一幀建立的查詢樹的葉節(jié)點開始查詢，而不是從根節(jié)點開始查詢。其中，“幀”由若干個詢問周期構(gòu)成，在一個幀中，閱讀器可識別出其作用范圍內(nèi)的所有標簽。

AQS考慮了標簽的移動，將標簽分為駐留標簽（在上一幀中已被識別的標簽）、新到標簽和離開標簽三類。若能消除由駐留標簽引起的沖突，則將大大縮短在當(dāng)前幀中識別標簽所需的時間。因此，AQS算法跳過上一幀建立的查詢樹的中間節(jié)點（對應(yīng)的都是引起沖突的查詢前綴），直接從葉節(jié)點（對應(yīng)的是空閑周期或可識別單個標簽的周期）開始查詢。為此，閱讀器需要維護兩個隊列：

（1）葉節(jié)點隊列（Leaf node Queue，LQ）存放閱讀器在當(dāng)前幀中進行查詢所需要的前綴，其初始值是上一幀建立的查詢樹中所有葉節(jié)點對應(yīng)的前綴。

（2）候補隊列（Candidate Queue，CQ）存放當(dāng)前幀中的空閑周期和可識別周期（即只有一個標簽響應(yīng)）對應(yīng)的前綴，為下一幀的查詢做準備。

當(dāng)一個新的幀開始時，用CQ 初始化Q，并將CQ 清空。若CQ 為空（如：閱讀器被復(fù)位后），則用前綴0和1來初始化Q。

由于CQ 中存放的是上一幀中沒有引起沖突的前綴，在新的幀中，閱讀器可以跳過沖突周期。

當(dāng)有新標簽到達時執(zhí)行插入操作，將新標簽加入查詢樹；當(dāng)有標簽離開后，其對應(yīng)的葉節(jié)點就會變成空閑周期，因此用刪除操作來刪除該節(jié)點，以便減少下一幀中不必要的查詢。

從產(chǎn)生沖突的次數(shù)和通信開銷方面來看，AQS都明顯低于QT，當(dāng)駐留標簽數(shù)量較多時，優(yōu)勢更為明顯。但在查詢周期方面，AQS的優(yōu)勢并沒有那么明顯，尤其是當(dāng)駐留標簽數(shù)量較少（即有大量標簽離開）時，AQS的查詢周期反而多于QT，其原因是大量的標簽離開從而形成了大量的空閑周期。

2.2.6 BSQTA 和BSCTTA 算 法

在QT 算法中，若查詢前綴q時發(fā)現(xiàn)了沖突，則下一次的查詢前綴為q0和q1，這兩個前綴的前n-1位都相同，只有最后一位不同。為了減少傳輸信息量，閱讀器可以將兩次查詢合并為一次，只發(fā)送查詢前綴的前n-1位（即前綴q）與其匹配的標簽，若第n位為0，則在第一個時隙響應(yīng)；若第n位為1，則在第二個時隙響應(yīng)。因此，時隙的編號就代表了第n位的值?；谶@一思想，文獻［32］提出基于位隙的QT 算法（Bi-Slotted Query Tree Algorithm，BSQTA）和基于位隙的碰撞跟蹤樹算法（Bi-Slotted Collision Tracking Tree Algorithm，BSCTTA）。

對于BSQTA，標簽將其ID 號的第n+1 位至最后一位作為響應(yīng)發(fā)送給閱讀器；對于BSCTTA，標簽也是從ID 號的第n+1位開始響應(yīng)，但當(dāng)閱讀器檢測到?jīng)_突后，會給標簽發(fā)送一個ACK 命令，標簽收到ACK 命令后，停止發(fā)送其ID 號。因此，在有沖突的情況下，BSCTTA 比BSQTA 發(fā)送的標簽ID號的位數(shù)要少一些，從而減少了傳輸信息量。

2.2.7 基于16位隨機數(shù)的查詢樹算法

文獻［33］提出基于16 位隨機數(shù)的QT 算法（16-bit Random Number aided Query Tree Algorithm，RN16QTA），在該算法中，每個標簽都會產(chǎn)生一個16 位的隨機數(shù)（16-bit Random Number，RN16），閱讀器采用基本的QT 算法對這個RN16進行識別。當(dāng)某個標簽產(chǎn)生的RN16被識別后，閱讀器給該標簽發(fā)送一個ACK 命令，標簽將其電子產(chǎn)品碼（Electronic Product Code，EPC）作為響應(yīng)發(fā)送給閱讀器，完成一個標簽的識別過程。

由于基于樹的防碰撞算法的性能主要取決于樹的高度，而標簽的EPC一般都比較長（大于16位），采用基本 QT 算法時，樹的高度都較大，而RN16QTA 采用的是16位隨機數(shù)，可以大大減少查詢樹的高度，提高了算法的性能。但是該算法也存在明顯的缺點：①通過RN16識別出標簽后，還需要再傳輸一次標簽的EPC，這無疑增加了閱讀器與標簽之間的通信負載；②16位二進制數(shù)能表示的數(shù)據(jù)范圍有限，當(dāng)標簽數(shù)量較多時，多個標簽可能會產(chǎn)生相同的隨機數(shù)，導(dǎo)致標簽無法被識別。

2.2.8 基于變長ID 的防碰撞算法

對于2.2.7 節(jié)提到的RN16QTA 算法的第一個缺點，文獻［34］提出了基于變長ID 的防碰撞算法，該算法采用EPC global定義的RFID 標簽EPC長度（96位），如圖2所示。

該算法利用標簽EPC 中的縮短ID（Shortened ID，SID）（共36 位），將SID 最右邊的位作為第1位，讓其向左擴展，并根據(jù)未被識別的標簽數(shù)量自適應(yīng)地調(diào)整SID 的長度（假設(shè)為N 位，其初始值設(shè)為4）。采用QT 算法進行識別，閱讀器首先生成一個n位的前綴（第一個前綴只有1位，其值為0）進行查詢，若標簽SID 的前n位與之匹配，則標簽將其SID的剩余部分（共N-n 位）作為響應(yīng)發(fā)送給閱讀器，閱讀器進行判斷：

（1）若產(chǎn)生沖突，則閱讀器采用QT 算法重新生成新的前綴，再次查詢。

（2）若未產(chǎn)生沖突，說明可能只有一個標簽，也可能有多個具有相同SID 的標簽，則閱讀器給標簽發(fā)送一個ACK 命令，接收到該命令的標簽將余下的96-N 位（即除了SID 部分以外的EPC 號）發(fā)送給閱讀器。如果有多個標簽具有相同的SID，則閱讀器收到的96-N 位信息必然有沖突，此時需將SID 再擴展D 位，然后閱讀器生成新的前綴再次進行查詢。

（3）若沒有標簽響應(yīng)，則說明未被識別的標簽數(shù)量已經(jīng)很少（例如當(dāng)查詢前綴為010時，無標簽響應(yīng)，可推測前綴為011的標簽數(shù)量也不多），此時可以進一步減小查詢樹的高度，故將SID 減少D 位，但須滿足條件N-D＞n。

仿真結(jié)果表明，D=4 時算法的性能最好［34］。通過D 值的設(shè)置，該算法可以根據(jù)未被識別的標簽數(shù)量自適應(yīng)地調(diào)整SID 的長度，因此降低了標簽識別過程中總的信息傳輸量。

2.2.9 增強型的RN16QTA 算法

對于2.2.7節(jié)提到的RN16QTA 算法的第二個缺點，經(jīng)證明，當(dāng)標簽數(shù)大于300時，多個標簽可能會產(chǎn)生相同的RN16［35］，此時RN16QTA 算法將失效。雖然未被識別的標簽可以再次生成RN16，并再次采用QT 算法進行識別，但是這種方法需要多次生成隨機數(shù)，而且標簽被成功識別后，還要再一次發(fā)送其EPC，這無疑增加了識別標簽的時延及信息傳輸量。因此，文獻［35］提出增強型的RN16QTA 算法，在該算法中，標簽只需產(chǎn)生一次RN16；同時將標簽的96位EPC 分為6段，即EPCi（1≤i≤6，其中EPC1為高位部分，EPC6為低位部分）；通過與RN16進行異或操作產(chǎn)生RXEi（1≤i≤6），并將其作為臨時ID 用于標簽的識別過程。考慮在某些應(yīng)用場合標簽EPC的高位部分相同，在進行異或操作時，采用反向的EPC，即RXE1=RN16⊕EPC6，RXE2=RN16⊕EPC6⊕EPC5，…。

若采用RXEi能成功識別標簽，則閱讀器給標簽發(fā)送一個ACK 信號，然后標簽將RN16，EPC1～EPC6-i發(fā)送給閱讀器，閱讀器收到后，根據(jù)EPC6=RXE1⊕RN16，EPC5=RXE2⊕RXE1，…重新計算出EPC6，EPC5，…，最終得出標簽的完整EPC。

該算法減少了標簽識別過程中的信息傳輸量。

3 混合算法

基于Aloha算法和基于樹的算法各有優(yōu)缺點?；贏loha算法的優(yōu)缺點已在第1章進行了論述；基于樹的算法雖然可以100%地識別標簽、不會發(fā)生標簽饑餓，但閱讀器與標簽之間交互次數(shù)多、通信數(shù)據(jù)量大。因此，可以將這兩類算法的優(yōu)點相結(jié)合，由此產(chǎn)生了混合算法。

3.1 基于魯棒估計和二叉選擇的FSA 算法

文獻［36］對DFSA 算法中的標簽數(shù)量估計方法進行了改進，提出基于魯棒估計和二叉選擇的FSA 算法（FSA with robust Estimation and Binary selection，EB-FSA），該算法由兩個階段構(gòu)成：

（1）估算階段 閱讀器準確地估計標簽數(shù)量，從而確定最佳幀長。EB-FSA 首先使用固定幀長Lest，如果發(fā)生沖突的概率大于閾值Pcoll＿th，則閱讀器按照因子fd減少響應(yīng)的標簽數(shù)量。重復(fù)這一過程，直至沖突的概率Pcoll≤Pcoll＿th，然后根據(jù)Pcoll和Lc=Lest以及式（4）估算出標簽數(shù)量n。

（2）識別階段 閱讀器根據(jù)估算的標簽數(shù)量n確定最優(yōu)幀長L。每個標簽都有一個計數(shù)器，其初值為一個隨機值，每個時隙、標簽都遞減自己的計數(shù)器，當(dāng)計數(shù)器為0時，標簽發(fā)送其ID 號。當(dāng)有沖突發(fā)生時進行二叉選擇，沖突的標簽隨機選擇0或1作為其計數(shù)器值，其余標簽的計數(shù)器值加1。

EB-FSA 算法在第一階段通過對標簽數(shù)量的準確估算來確定最佳幀長，從而降低了標簽沖突的可能性。當(dāng)有沖突發(fā)生時，在當(dāng)前幀中通過二叉選擇（而不是通過增加額外的幀）來解決沖突，從而快速識別標簽。因此，EB-FSA 算法在性能上有了較大的提高，但其缺點是仍然需要額外的幀，以便對標簽數(shù)量進行估計。

3.2 基于引導(dǎo)幀和二叉選擇的FSA算法

基于引導(dǎo)幀和二叉選擇的FSA 算法（FSA with Pilot frame and Binary selection，F(xiàn)SAPB）［37］通過使用位掩碼將響應(yīng)的標簽分成M 個分組，用一個引導(dǎo)幀（長度為Lp）估計識別第一個分組內(nèi)的標簽所需的幀長。將標簽分成更小的分組可以有效降低Lp的值，從而節(jié)約估計標簽所需時隙。

第一分組中的標簽在Lp內(nèi)隨機選擇時隙發(fā)送其ID，同時閱讀器記錄沖突時隙的個數(shù)c，估算沖突的概率Pcoll=Lp-1max（0，c-1／2），并與沖突概率的閾值Pth比較。

若Pcoll＞Pth，則只需要一個單一的識別幀。根據(jù)Pcoll和Lp估算出標簽個數(shù)n1，其方法可參考式（4）。當(dāng)Pcoll較大時，用“n1-Lp中識別出的標簽個數(shù)”來估計識別幀L1的長度。在幀L1中，閱讀器采用二叉樹選擇的方法對Lp中沖突的標簽進行識別。

若Pcoll≤Pth，則表明只有少量的沖突，不需要增加額外的幀，可以在引導(dǎo)幀結(jié)束后增加額外的時隙Ladd，并直接應(yīng)用二叉樹選擇法，此時在Lp中沖突的標簽重新選擇新的隨機計數(shù)器值（根據(jù)在Lp沖突的順序和Lp中的剩余時隙數(shù)進行選擇）。

假設(shè)標簽為均勻分布，則用位掩碼分組后的每個分組也為均勻分布，因此對于第2～M 個分組，不再需要引導(dǎo)幀來估算標簽個數(shù)。第k 組的幀長Lk=γ·nk-1，其中：γ為一個常數(shù)，文獻［37］中確定的γ值為0.87；nk-1為第k-1個分組的標簽個數(shù)。在Lk中，當(dāng)產(chǎn)生沖突時，采用二叉樹選擇法解決沖突。

3.3 交織二進制樹搜索算法

文獻［38］將幀時隙Aloha算法和返回式二進制搜索算法的優(yōu)點相結(jié)合，提出交織二進制樹搜索算法，該算法將所有待識別標簽進行隨機分組，產(chǎn)生多棵由部分標簽組成的子樹，再針對每棵子樹中的標簽，使用返回式二進制樹搜索方法進行識別，提高了多標簽識別的效率和安全性，減少了標簽發(fā)送ID的次數(shù)。算法的基本思想為：閱讀器發(fā)起一個長度為Lint的交織幀，并等待標簽響應(yīng)；標簽生成一個小于等于Lint的隨機數(shù)k，并將其存儲在標簽存儲器中，標簽在當(dāng)前幀的第k個時隙發(fā)送其ID 號。交織幀結(jié)束后，時隙將會被分成空閑時隙、單標簽響應(yīng)時隙、沖突時隙三種。對于沖突時隙，閱讀器將會接收到類似于X01X 的信息（X 為發(fā)生碰撞的比特位），閱讀器據(jù)此建立相應(yīng)的碰撞信息表。發(fā)生碰撞的標簽將其所選擇的時隙編號ki存入碰撞信息表中的對應(yīng)位置，然后閱讀器按照ki從小到大的順序?qū)γ總€碰撞時隙內(nèi)的標簽進行識別，采用的識別方法為返回式二進制搜索算法。仿真結(jié)果表明，該算法的吞吐率達到60%以上。

3.4 動態(tài)時隙沖突跟蹤樹算法

文獻［39］提出動態(tài)時隙沖突跟蹤樹算法（Dynamic Slots Collision Tracking Tree Algorithm，DSCTTA），該算法借用Aloha算法中時隙的概念對BSCTTA 算法［32］進行了改進，算法核心思想是：設(shè)置一個數(shù)值N，表示閱讀器可以接收的響應(yīng)信息中連續(xù)沖突位的長度。若N=2，則表示：若閱讀器已接收到兩個連續(xù)的沖突位（如0010XX），則給標簽發(fā)送一個ACK 命令，標簽停止發(fā)送其ID 號的剩余部分；然后閱讀器將0010作為新的前綴查詢與其匹配的標簽，若其ID 未匹配部分的最高兩位為00，01，10，11，則分別在第1，2，3，4個時隙響應(yīng)，時隙的序號即為其最高兩位的值。若N=1，則DSCTTA退化為BSCTTA 算法。

4 結(jié)束語

RFID 多標簽防碰撞算法大致可分為基于Aloha的算法、基于樹的算法以及前兩者的混合算法三類?；贏loha算法的通信復(fù)雜度低，動態(tài)適應(yīng)性強，但是算法隨機性大，性能不穩(wěn)定，甚至可能出現(xiàn)標簽饑餓的問題；基于樹的算法不存在標簽饑餓問題，但是閱讀器與標簽之間的交互次數(shù)多，通信數(shù)據(jù)量大，標簽識別效率較低；混合算法正好結(jié)合了前兩者的優(yōu)點，是未來的研究方向之一。

本文提出的QT 算法及其改進算法所構(gòu)建的查詢樹的深度與標簽ID 的長度有密切關(guān)系，因此當(dāng)標簽的ID 長度增加時，算法的時延肯定會增加。針對這種情況，少量文獻［33，35］提出了基于隨機數(shù)的方法，降低了查詢樹的深度。因此，對基于隨機數(shù)的QT 改進算法的性能進行詳細分析，并在此基礎(chǔ)上提出更為完善的算法，也是未來的一個研究方向。

除了多標簽碰撞問題以外，在RFID 系統(tǒng)中還存在閱讀器碰撞問題，目前已有部分文獻［40-44］對該問題提出了解決方法。在此基礎(chǔ)上，考慮閱讀器與標簽之間的通信特點，設(shè)計更具針對性的閱讀器防碰撞算法，并盡量降低算法的復(fù)雜度，也是今后的研究方向之一。

［1］LI Minbo，JIN Zuxu，CHEN Chen.Application of RFID on products tracking and tracing system［J］.Computer Integrated Manufacturing Systems，2010，16（1）：202-208（in Chinese）.［李敏波，金祖旭，陳 晨.射頻識別在物品跟蹤與追溯系統(tǒng)中的應(yīng)用［J］.計算機集成制造系統(tǒng)，2010，16（1）：202-208.］

［2］LI Hua.Research and performance analysis of UHF RFID multi-tag anti-collision algorithms［D］.Jinan：Shandong University，2011（in Chinese）.［栗 華.UHF RFID多標簽防碰撞算法的研究與性能分析［D］.濟南：山東大學(xué)，2011.］

［3］SHIH D H，SUN P L，YEN D C，et al.Taxonomy and survey of RFID anti-collision protocols［J］.Computer Communications，2006，29（11）：2150-2166.

［4］KLAIR D K，CHIN K W，RAAD R.A survey and tutorial of RFID anti-collision protocols［J］.IEEE Communications Surveys &Tutorials，2010，12（3）：400-421.

［5］FINKENZELLER K.RFID handbook：fundamentals and applications in contactless smart cards and identification［M］.New York，N.Y.，USA：John Wiley &Sons，2003：200-219.

［6］SCHOUTE F C.Dynamic frame length ALOHA［J］.IEEE Transactions on Communications，1983，31（4）：565-568.

［7］CHA J R，KIM J H.Novel anti-collision algorithms for fast object identification in RFID system［C］／／Proceedings of the 2005 11th International Conference on Parallel and Distributed Systems.Washington，D.C.，USA：IEEE，2005：63-67.

［8］VOGT H.Efficient object identification with passive RFID tags［J］.Lecture Notes in Computer Sciences，2002，2414：98-113.

［9］HWANG T W，LEE B G，KIM Y S，et al.Improved anti-collision scheme for high speed identification in RFID system［C］／／Proceddings of the 1st International Conference on Innovative Computing，Information and Control.Washington，D.C.，USA：IEEE，2006：449-452.

［10］WU Haifeng，ZENG Yu.ADFA protocol for RFID tag collision arbitration［J］.Journal of Computer Research and Development，2011，48（5）：802-810（in Chinese）.［吳海峰，曾玉.自適應(yīng)幀Aloha的RFID標簽防沖突協(xié)議［J］.計算機研究與發(fā)展，2011，48（5）：802-810.］

［11］HAN Zhenwei，SONG Kefei.Improved anti-collision Q-algorithm for RFID system［J］.Computer Engineering and Design，2011，32（7）：2314-2318（in Chinese）.［韓振偉，宋克非.射頻識別防碰撞Q 算法的分析及改進［J］.計算機工程與設(shè)計，2011，32（7）：2314-2318.］

［12］EPC Global Inc.EPCTMradio-frequency identity protocols class-1generation-2UHF RFID protocol for communications at 860 MHz-960MHz，Version 1.0.9［EB／OL］.（2005-01-26）［2012-10-09］.http：／／www.gs1.org／gsmp／kc／epcglobal／uhfc1g2／uhfc1g2＿1＿0＿9-standard-20050126.pdf.

［13］DENG Huifang，LIU Jinqiao，DENG Chunhui，et al.RFID multi-tags anti-collision algorithm with adaptive Q leading to the maximum throughput［C］／／Proceedings of the 3rd Pacific-Asia Conference on Web Mining and Web-based Application.Washington，D.C.，USA：IEEE，2010：166-169.

［14］DENG Xiao，HE Yigang，XIANG Yang，et al.Novel tags quantity estimation method for anti-collision in RFID systems［J］.Computer Engineering and Applications，2008，44（31）：142-144（in Chinese）.［鄧 曉，何怡剛，向 陽，等.一種新的RFID標簽數(shù)目估算方法［J］.計算機工程與應(yīng)用，2008，44（31）：142-144.］

［15］WONG C P，F(xiàn)ENG Q Y.Grouping based bit-slot ALOHA protocol for tag anti-collision in RFID systems［J］.IEEE Communications Letters，2007，11（12）：946-948.

［16］CHEN Yihong，F(xiàn)ENG Quanyuan.RFID anti-collision algorithms for tags continuous arrival in Internet of things［J］.Computer Integrated Manufacturing Systems，2012，18（9）：2076-2081（in Chinese）.［陳毅紅，馮全源.物聯(lián)網(wǎng)中標簽持續(xù)到達的RFID 防碰撞算法研究［J］.計算機集成制造系統(tǒng)，2012，18（9）：2076-2081.］

［17］HUSH D R，WOOD C.Analysis of tree algorithms for RFID arbitration［C］／／Proceedings of IEEE International Symposium on Information Theory.Washington，D.C.，USA：IEEE，1998：107.

［18］MYUNG J，LEE W，SRIVASTAVA J.Adaptive binary splitting for efficient RFID tag anti-collision［J］.IEEE Communications Letters，2006，10（3）：144-146.

［19］MYUNG J，LEE W，SRIVASTAVA J，et al.Tag-splitting：adaptive collision arbitration protocols for RFID tag identification［J］.IEEE Transactions on Parallel and Distributed Systems，2007，18（6）：763-775.

［20］CHEN W C，HORNG S J，F(xiàn)AN Pingzi.An enhanced anticollision algorithm in RFID based on counter and stack［C］／／Proceedings of the 2nd International Conference on Systems and Networks Communications.Washington，D.C.，USA：IEEE，2007：1-4.

［21］HE M X，HORNG S J，F(xiàn)AN P Z，et al.A fast RFID tag identification algorithm based on counter and stack［J］.Expert Systems with Applications，2011，38（6）：6829-6838.

［22］CHEN Y H，HORNG S J，RUN R S，et al.A novel anticollision algorithm in RFID systems for identifying passive tags［J］.IEEE Transactions on Industrial Informatics，2010，6（1）：105-121.

［23］DENG Huifang，LIU Jinqiao.Binary-matrix search in anticollision of RFID system［J］.Microcomputer Information，2009，25（10-2）：4-5，3（in Chinese）.［鄧輝舫，劉金橋.RFID系統(tǒng)防碰撞中的二進制矩陣搜索［J］.微計算機信息，2009，25（10-2）：4-5，3.］

［24］YU Songsen，ZHAN Yiju，PENG Weidong，et al.An anticollision algorithm based on binary-tree searching of regressive index and its practice［J］.Computer Engineering and Application，2004，40（16）：26-28（in Chinese）.［余松森，詹宜巨，彭衛(wèi)東，等.基于后退式索引的二進制樹形搜索反碰撞算法及其實現(xiàn)［J］.計算機工程與應(yīng)用，2004，40（16）：26-28.］

［25］WEN Chao，OU Ruofeng，LING Li.RFID anti-collision algorithm based on adaptive splitting tree［J］.Computer Engineering，2011，37（24）：287-289（in Chinese）.［文 超，歐若風(fēng)，凌 力.基于自適應(yīng)分裂樹的RFID 防碰撞算法［J］.計算機工程，2011，37（24）：287-289.］

［26］DING Zhiguo，ZHU Xueyong，GUO Li，et al.An adaptive anti-collision algorithm based on multi-tree search［J］.Acta Automatica Sinica，2010，36（2）：237-241（in Chinese）.［丁治國，朱學(xué)永，郭 立，等.自適應(yīng)多叉樹防碰撞算法研究［J］.自動化學(xué)報，2010，36（2）：237-241.］

［27］LAW C，LEE K，SIU K Y.Efficient memoryless protocol for tag identification［C］／／Proceedings of the 4th International Workshop on Discrete Algorithms andMethodsfor Mobile Computing and Communications.New York，N.Y.，USA：ACM，2000：75-84.

［28］YU Songsen，ZHAN Yiju，WANG Zhiping，et al.Anti-collision algorithm based on jumping and dynamic searching and its analysis［J］.Computer Engineering，2005，31（9）：19-20，26（in Chinese）.［余松森，詹宜巨，王志平，等.跳躍式動態(tài)樹形反碰撞算法及其分析［J］.計算機工程，2005，31（9）：19-20，26.］

［29］JIA X L，F(xiàn)ENG Q Y，MA C Z.An efficient anti-collision protocol for RFID tag identification［J］.IEEE Communications Letters，2010，14（11）：1014-1016.

［30］JIA X L，F(xiàn)ENG Q Y，YU L S.Stability analysis of an efficient anti-collision protocol for RFID tag identification［J］.IEEE Transactions on Communications，2012，60（8）：2285-2294.

［31］MYUNG J，LEE W，SHIH T K.An adaptive memoryless protocol for RFID tag collision arbitration［J］.IEEE Transactions on Multimedia，2006，8（5）：1096-1101.

［32］CHOI J H，LEE D，LEE H.Bi-slotted tree based anti-collision protocols for fast tag identification in RFID systems［J］.IEEE Communications Letters，2006，10（12）：861-863.

［33］CHOI J H，LEE D，LEE H.Query tree-based reservation for efficient RFID tag anti-collision［J］.IEEE Communications Letters，2007，11（1）：85-87.

［34］YEO W Y，HWANG G H.Efficient anti-collision algorithm using variable length ID in RFID systems［J］.IEICE Electronics Express，2010，7（23）：1735-1740.

［35］YANG C N，HE J Y.An effective 16-bit random number aided query tree algorithm for RFID tag anti-collision［J］.IEEE Communications Letters，2011，15（5）：539-541.

［36］PARK J，CHUNG M Y，LEE T J.Identification of RFID tags in framed-slotted ALOHA with robust estimation and binary selection［J］.IEEE Communications Letters，2007，11（5）：452-454.

［37］EOM J B，LEE T J，RIETMAN R，et al.An efficient framed-slotted ALOHA algorithm with pilot frame and binary selection for anti-collision of RFID tags［J］.IEEE Communications Letters，2008，12（11）：861-863.

［38］HONG Weijun.Research on serveral key technologies on implementation and application of ultra high frequency radio frequency identification［D］.Beijing：Beijing University of Posts and Telecommunications，2009（in Chinese）.［洪衛(wèi)軍.超高頻射頻識別系統(tǒng)實現(xiàn)與應(yīng)用中的若干關(guān)鍵技術(shù)研究［D］.北京：北京郵電大學(xué)，2009.］

［39］LIANG C K，LIN H M.Using Dynamic slots collision tracking tree technique towards an efficient tag anti-collision algorithm in RFID systems［C］／／Proceedings of the 9th International Conference on Ubiquitous Intelligence and Computing and 9th International Conference on Autonomic and Trusted Computing.Washington，D.C.，USA：IEEE，2012：272-277.

［40］YU J，LEE W，DU D Z.Reducing reader collision for mobile RFID［J］.IEEE Transactions on Consumer Electronics，2011，57（2）：574-582.

［41］KONSTANTINOU N.Expowave：an RFID anti-collision algorithm for dense and lively environments［J］.IEEE Transactions on Communications，2012，60（2）：352-356.

［42］DENG H F，HU C Y.Tackling RFID reader collision using a non-color metric minimum graph coloring method and Boltzmann machine model［C］／／Proceedings of the 2nd International Conference on Intellectual Technology in Industrial Practice.Washington，D.C.，USA：IEEE，2010：598-602.

［43］ESSIA H，NATHALIE M，DAVID S R.Reader anti-collision in dense RFID networks with mobile tags［C］／／Proceedings of the IEEE International Conference on RFID-Technologies and Applications.Washington，D.C.，USA：IEEE，2011：327-334.

［44］CHEN B Y，DENG H F，DENG C H.DPC-EDiCa：a RFID reader anti-collision algorithm for dense RFID system［J］.International Journal of Automated Identification Technology，2013，5（1）：21-32.