防碰撞算法

無線射頻識別（RadioFrequencyIDentifica－tion，RFID）是一種非接觸式自動識別技術，它通過射頻信號自動識別目標對象並獲取相關數據，識別工作無需人工干預，可工作於各種惡劣環境，在物聯網、供應鏈、物流等領域中有着廣泛的應用。典型的RFID系統主要由閲讀器、標籤和後台計算機應用系統三部分組成，標籤具有唯一的識別碼（IDen－tificationcode，ID），被貼附到待識別的物體上。在RFID應用系統的一個閲讀器的天線作用範圍內，常常同時存在多個標籤，當閲讀器發出查詢命令後，往往會引起多個標籤同時響應，這些響應信息在共享的無線信道上發生碰撞，使響應信號難以被閲讀器辨認，從而引起多標籤碰撞。閲讀器為完成對所有標籤的識別，應將這些發生碰撞的標籤區分開來，再與它們逐個通信，閲讀器完成這些工作所使用的算法就是多標籤防碰撞算法。

現有的多標籤防碰撞算法主要分為三類：①基於Aloha的算法，又稱為隨機性算法；②基於樹的算法，又稱為確定性算法；③混合算法，將基於Aloha的算法和基於樹的算法相結合而產生的一種算法。

基於Aloha的防碰撞算法的基本思想是：在閲讀器發現多標籤碰撞時，閲讀器命令其作用範圍內的所有標籤隨機延遲一段時間再進行響應，延遲時間的長度是以某種概率隨機選擇的 ^[1]  。

早期的Aloha算法為純Aloha算法，該算法採用“標籤先發言”的方式，即標籤一進入閲讀器的作用區域就自動向閲讀器發送其自身的信息，對同一個標籤來説，其發送數據的時間是隨機的。在標籤發送信息的過程中，如果有其他標籤也在發送數據，就會發生信號重疊，導致部分碰撞或者完全碰撞 ^[1]  。

閲讀器檢測信號並進行判斷，一旦發現碰撞，閲讀器將發送命令讓標籤停止發送數據，所有標籤會隨機延遲一段時間再發送數據，由於延遲的隨機時間不同，再次發生碰撞的概率將明顯降低。如果沒有碰撞，則閲讀器發送一個應答信號給標籤，標籤從此轉入休眠狀態。這種算法簡單，但吞吐率低，最大吞吐率僅能達到18．4% ^[1]  。

該算法效率低的主要原因是碰撞發生的時間是隨機的，其中包括：當一個標籤在與閲讀器通信的過程中，有可能因其他標籤的突然響應而被破壞，即存在部分碰撞問題。為此，人們提出時隙Aloha算法（SlottedAloha，SA），把時間分成多個離散時隙，標籤只在每個時隙的開始時刻才能發送數據。算法的基本原理是：閲讀器通過發送命令通知標籤有多少時隙，標籤隨機選擇發送信息的時隙。如果某個時隙只有一個標籤響應，則閲讀器可正確地識別標籤；如果某個時隙有多個標籤響應，則會發生碰撞，閲讀器通知標籤，標籤便在下一輪循環中重新隨機選擇發送的時隙，直到所有的標籤都被識別出來。在SA算法中，標籤或成功識別或完全碰撞，避免了純Aloha算法中出現的部分碰撞問題。SA算法的最大吞吐率可達36．8% ^[1]  。

對於SA算法，在發生碰撞時，標籤延遲的隨機性範圍很大，影響了其平均響應速度。為此，規定若干個時隙為一幀，標籤選擇的隨機延遲必須是幀內的某個時隙，這就是幀時隙Aloha（FramedSlottedAloha，FSA）算法 ^[1]  。

FSA算法的缺點是幀長固定，這樣當標籤數量較少時，存在時隙浪費，而當標籤數較多時，碰撞解決的效果又不是很好。因此，可以考慮根據標籤數量動態地調整幀長，即動態幀時隙Aloha（DynamicFramedSlottedAloha，DFSA）算法。研究結果表明，最優的幀長應該等於標籤數量，因此只要知道了標籤數量，就可以確定幀長，然而當前幀需識別的標籤數量通常無法預知，只能對其進行估算。因此在DFSA算法中，非常重要的一項工作就是標籤數量的估計，大多數方法都是根據上一幀的幀長、標籤個數、衝突情況來估計當前幀中的標籤數 ^[1]  。典型方法包括：

（1）Vogt方法設碰撞時隙數為Ck，碰撞時隙內至少有2個以上的標籤存在，則可以預測發生碰撞的標籤數量至少為2×Ck ^[1]  。

（2）標籤估計方法Ⅰ（TagEstimationMethodⅠ，TEMⅠ）將碰撞率Cratio定義為碰撞時隙數與幀長的比值，L為幀長，n為標籤個數，則它們之間的關係為Cratio=1－（1-1/L）(1+n/(L-1))（1）由於上一幀的幀長L和碰撞率Cratio已知，可以計算出標籤個數n ^[1]  。

（3）TEMⅡ方法設nest為估算的標籤數量，Mcoll為上一幀中的碰撞時隙數，則nest=2．3922×Mcoll ^[1]  。

在固定幀長的Aloha算法中，當標籤數量太多時，衝突時隙較多；而當標籤數量太少時，又會有大量的空閒時隙。基於這一點，各種改進算法被提出 ^[1]  。

分羣時隙Aloha算法根據碰撞時隙在所分配時隙中所佔的比例，來確定是否分羣。如果碰撞時隙的比例（發生碰撞的時隙數/分配的時隙數）大於分羣因子γ，則進行分羣。分羣后，第一個分羣內的標籤響應閲讀器的查詢命令，另一個分羣內的標籤處於等待狀態。當第一個分羣內的所有標籤識別完畢後，第二個分羣內的標籤再進行響應，直至所有標籤識別完畢 ^[1]  。

仿真結果表明，分羣時隙Aloha算法優於固定時隙Aloha算法，且隨着標籤數量的增加，算法的優越性更明顯。同時，分羣因子的選擇是影響算法的關鍵因素，在標籤數量較多時，分羣因子宜選擇較小值 ^[1]  。

文獻考慮某些應用場合中閲讀器需要對標籤進行重複識別的要求，充分利用上一幀已識別標籤的信息，提出自適應的動態幀時隙Aloha算法，該算法每成功識別一個標籤就給標籤分配一個時隙號，該時隙號規定了標籤被閲讀器識別的順序。如果在下次識別過程中閲讀器要重複識別這些標籤，則可根據已分配的時隙號按順序進行，從而避免標籤間的衝突，減少識別時間。當離去標籤和新到達標籤數量較少時，系統效率較高，但是當有大量的新到達標籤時，僅採用上述方法將導致衝突急劇增加。為減少衝突，閲讀器應估計標籤數，並根據標籤數合理調整幀長。文獻提出了一種最優幀長方案，使系統獲得了較大的吞吐量 ^[1]  。

DFSA算法可採用各種方法預測待識別的標籤數量，然後動態調整最優幀長，與FSA相比，系統效率有明顯改善，接近36．8%。但是，當標籤數量較多（特別是標籤數量大於500）時，採用由預測標籤數量設置最優幀長的方案會使系統效率急劇下降。因此，在標籤數量較多的情況下，為了使系統效率得到提高，EPCClass1Gen2標準中採用了Q值算法，該算法可以實時自適應地調整幀長 ^[1]  。

在Q值算法中，閲讀器首先發送Query命令，該命令中含有一個參數Q（取值範圍0～15），接收到命令的標籤可在[0，2Q－1]範圍內（稱為幀長）隨機選擇時隙，並將選擇的值存入標籤的時隙計數器中，只有計數器為0的標籤才能響應，其餘標籤保持沉默狀態。當標籤接收到閲讀器發送的QueryRep命令時，將其時隙計數器減1，若減為0，則給閲讀器發送一個應答信號。標籤被成功識別後，退出這輪盤存。當有兩個以上標籤的計數器都為0時，它們會同時對閲讀器進行應答，造成碰撞。閲讀器檢測到碰撞後，發出指令將產生碰撞的標籤時隙計數器設為最大值（2Q－1），繼續留在這一輪盤存週期中，系統繼續盤存直到所有標籤都被查詢過，然後閲讀器發送重置命令，使碰撞過的標籤生成新的隨機數 ^[1]  。

根據上一輪識別的情況，閲讀器發送Query－Adjust命令來調整Q的值，當標籤接收到Query－Adjust命令時，先更新Q值，然後在[0，2Q－1]範圍內選擇隨機值。EPCClass1Gen2標準中提供了一種參考算法來確定Q值的範圍.其中：Qfp為浮點數，其初值一般設為4．0，對Qfp四捨五入取整後得到的值即為Q；C為調整步長，其典型取值範圍是0．1<C<0．5，通常當Q值較大時，C取較小的值，而當Q值較小時，C取較大的值 ^[1]  。

當閲讀器發送Query命令進行查詢時，若應答標籤數等於1，則Q值不變；若應答標籤數等於0（空閒時隙），則減小Q值；若應答標籤數大於1（衝突時隙），則增大Q值 ^[1]  。

該算法在參數C的輔助下對Q值進行動態調整，但是C太大會造成Q值變化過於頻繁，導致幀長調整過於頻繁，C太小又不能快速地實現最優幀長的選擇。因此，研究者們對Q值的調整進行了各種優化 ^[1]  。

文獻提出一種基於最大吞吐量對Q值進行調整的算法，其中定義了以下變量：Nt為已識別的標籤個數；N為識別標籤所需的總時隙數；NC為衝突時隙的個數；nu為上一輪未識別的標籤個數；e為衝突時隙中的平均標籤個數；PC為衝突時隙所佔的比例 ^[1]  。

這些參數之間的關係為PC=NC/N，e=nu/Nc，吞吐量=Nt/N。由於Aloha類算法的最大吞吐量為0．368（e－1）[5]，該算法以此作為調整Q值的依據。當系統吞吐量達到或接近0．368時，閲讀器僅需調用2Q－1次QueryRep命令，而不需要在接下來的盤存週期中調整Q值。當吞吐量小於0．368時，根據未識別的標籤個數nu來調整Q值 ^[1]  .

文獻提出一種基於分組的位隙Aloha算法，該算法採用位隙Aloha算法中的128位預定序列，代表128個位隙。若某個標籤選擇了第i個位隙，則將第i位置1，其餘各位都置0。當標籤數量為15時，位隙Aloha算法可獲得最大吞吐率88．38%，但隨着標籤數量的增加，算法性能急劇下降 ^[1]  。

因此，基於分組的位隙Aloha算法通過對標籤進行分組來提高算法的性能。該算法在查詢命令中設置了一個位隙計數器的參數Q（Q為整數，且0≤Q≤15），當標籤收到閲讀器發送的查詢命令後，在[0，2Q－1]範圍內生成一個隨機數，即代表選擇了相應的位隙，只有選擇了0的標籤才會立即響應。同時，該算法根據衝突位隙數動態地對Q值進行調整：當衝突位隙數小於11時，Q減1且最小為0；當衝突位隙數在11～20之間時，Q保持不變；當衝突位隙數大於20時，Q加1且最大不超過15 ^[1]  。

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