基于RFID防碰撞算法綜述

劉曉崗　宋高俊

摘要：無線射頻識別（Radio Frequency Identification，RFID）技術作為當下最重要的科技之一，以其廣泛的應用性將有越來越大的發展前景，RFID技術也由于其非接觸的特性，遇到了多目標識別過程中的信息碰撞問題。現對Aloha類防碰撞算法、二進制樹防碰撞算法以及改進算法進行分析。

關鍵詞：RFID；防碰撞算法；Aloha；二進制樹

RFID系統在識別過程中會有一個普遍的問題，那就是對象沖突，當在同一時間內有若干個電子標簽同時請求識別是，閱讀器不能正確區別出來，這樣當多個電子標簽同時發送數據的時候，就會出現數據的干擾導致數據傳輸失敗，這就是文章要研究的防碰撞問題。為了解決這一問題，提高系統的性能，需要制定有效的防碰撞算法，所以防碰撞算法是RFID系統的研究核心。

現有的防碰撞算法包括：Aloha類防碰撞算法，又稱為隨機性算法；二進制樹防碰撞算法，又稱為確定性算法；改進算法，在原有的基礎上設計出性能更優的算法。

1基于Aloha類防碰撞算法

ALOHA（Additive Link On line Hawaii）算法算是出現比較早的防碰撞算法，它是采取隨機多址方式。作為無線通信協議，ALOHA算法研究取得成功后被廣泛利用。在理想狀態下，利用ALOHA類防碰撞算法，系統最高吞吐率是36.8%。但是在實際應用中，由于各種因素的干擾，系統的識別效率很難達到理想的狀態。

1.1純Aloha算法

純ALOHA算法也叫基本ALOHA算法，是一種比較容易的時分多址算法。當標簽進入閱讀器的工作范圍內，標簽獲取能量被激活，向閱讀器發送儲存在標簽內部的數據信息。在這個過程中，假如有兩個標簽一同向閱讀器發送信息，就會產生信息沖突，造成完全碰撞；而當一個標簽正在向閱讀器發送過程中，另一個標簽開始信息傳送，這種情況下就會出現標簽部分碰撞。只有標簽單獨在一個時間內進行信息傳輸時才能讓閱讀器正常識別，不會出現碰撞情況。使用純ALOHA算法，系統最大吞吐率只有18.4%，標簽發生碰撞概率比能夠正確識別概率要大得多。

1.2時隙Aloha算法與幀時隙Aloha算法

由于ALOHA算法中，標簽發送數據時間是隨機性的，導致完全碰撞或者部分碰撞。于是將純ALOHA算法進行優化，得到了時隙ALOHA算法。這種算法是把時間劃分成若干等長時隙（每個時隙長度滿足一個標簽成功發送完數據），標簽通過不同時隙向閱讀器發送數據，如此一來，就能避免部分碰撞的產生，從而總體上縮減了產生碰撞的次數。時隙Aloha算法采用分割時隙思想，避免了標簽的部分碰撞，只有成功識別和完全碰撞情況，成倍地提高了信道利用率。但要劃分時隙就要解決一個同步問題，在系統中要有同步時鐘，使閱讀器作用范圍內的所有標簽達到時隙同步。該算法的系統吞吐率可達到36.8%，比純Aloha算法效果提高了一倍。

盡管時隙ALOHA算法在信道利用率上比純ALOHA算法得到一定改進，可是標簽發生碰撞的概率依然很大，發生碰撞后的標簽會隨機接著發送數據，進而影響其他標簽的讀取，為了避免這種情況，于是研究出了幀時隙ALOHA算法。這種方法是把多個時隙組成一個幀，在每一個幀內，標簽任意選擇其中一個時隙發送數據，但只可以發送一次。在某一個時隙內，當標簽發生了完全碰撞，將會處于休眠狀態，等到下一幀進行讀取，這樣不會影響本幀內其他標簽的正常讀取。算法中每一幀的時隙數都是固定的，并且時隙長會大于一個標簽成功發送完信息的時間。這樣，閱讀器發送讀取指令后，假如一個時隙內僅有一個標簽響應，則成功讀取標簽數據；如果時隙內沒有一個標簽，就會掠過此時隙；如果存在許多標簽的話，產生了碰撞后自動等到下一幀的到來，再選擇其他時隙。

2基于二進制樹防碰撞算法

二進制樹防碰撞算法通過電子標簽具有唯一的二進制編碼來查詢區別。此算法工作原理是將產生了碰撞的電子標簽分為0、1兩個子集，首先從子集0開始搜尋，要是沒有碰撞產生，說明成功識別。如果產生了碰撞，就將碰撞的標簽再分成00與01兩個子集，再從00子集開始搜尋，重復執行操作。0子集的標簽完全成功識別后，轉向1子集搜尋，直至把全部標簽都識別完，任務結束。

2.1二進制搜索算法與動態二進制搜索算法

與ALOHA類算法不同的是，使用二進制搜索算法需要用到標簽自身的序列號和閱讀器的查詢指令號。當標簽序列號與閱讀器查詢指令相同時，標簽產生響應。要是僅有一個標簽做出響應，那么成功識別。如果存在若干個標簽一同做出響應，閱讀器會根據碰撞位情況修正查詢指令，經過不斷修正查詢命令來識別出所有標簽。

動態二進制搜索（DBS，Dynamic Binary Search）算法是對二進制搜索算法進行優化的。使用二進制搜索算法，整個標簽序列號需要多次被傳輸，并且閱讀器發送的REQUEST指令數據位也多，從而會造成查詢時間增加，出錯頻率也跟著提高。動態二進制搜索算法能很好減少數據位冗余，但是它的運行流程與二進制搜索算法基本相同，只是修改了REQUEST指令。

2.2鎖位后退二進制搜索算法與跳躍式動態二進制搜算算法

鎖位后退二進制搜索算法也是在二進制搜索算法基礎上得到優化的，雖然動態二進制搜索算法能減少數據傳輸量，但是并不能減少搜索次數。鎖位后退二進制搜索算法的工作原理是當閱讀器成功識別出一個標簽后，閱讀器不需要重新發送REQUEST指令，而是直接根據上一層的鎖位分組退回到上一層，也就是返回根節點，這樣顯然會減少搜索次數。

跳躍式動態二進制搜索算法在動態二進制搜索算法和鎖位后退算法的基礎上結合而成的，涵蓋了兩種算法的優點，既減少了數據冗余位的發送，也減少了搜索次數，同時縮短了查詢時間，也提高了標簽識別效率。

跳躍式搜索算法比二進制搜索以及鎖位后退搜索需要的查詢次數少，比動態搜索算法數據傳輸量又少，整體性能相對來說是最好。

3改進算法

為了使識別效率更好，不少學者在原有的基礎上，提出了新的改進算法，有學者提出了優化幀內時隙長度的策略，并通過馬爾科夫建模實現對標簽的讀取周期數達到減少的目的。同時，基于二進制樹的防碰撞算法也有很多學者在研究，并且在其基礎上提出了不少改進算法，如改進的返回式動態二進制算法、NTA算法、EMBT算法和二叉樹搜算算法等，相比之前的動態二進制搜算算法，在平均比特數上，實現了大大的減少，提高了識別效率。最近，有學者提出GDRA（geometric distribution reader anticollision）拓撲方案，利用篩選幾何概率分布函數來實現閱讀器碰撞問題最小化，它能提供更高的吞吐量，符合EPC國際標準，在不需要額外的硬件條件就可在真實的RFID系統中實現功能。

4結語

相比之下，Aloha類算法操作簡單，識別時間短，但穩定性不足，系統利用率最高也只能達到36.8%，并且當標簽數量增加時，系統的識別效率將下降的很快。二進制算法雖然識別效率高，穩定性也較好，但是操作復雜，識別時間較長。改進算法在原有的基礎上，實現新的突破，在準確度、信道利用率、穩定性等方面尋求改善，是未來的研究方向之一。