關于RFID技術防碰撞算法的研究

在一般的RFID系統中，RFID讀寫器和RFID電子標簽之間采用的是無線通信，由于讀寫器和標簽數據信息傳輸所使用的信道相同。所以當多標簽同時響應時，信道中會有不止一份數據信號進行傳輸。就可能會形成信道阻塞的情況，造成數據碰撞，致使部分電子標簽不能被正確讀取。RFID系統的碰撞問題可以歸為兩類：電子標簽之前的互相干擾類和RFID讀寫器互相干擾類。

電子標簽之前的互相干擾類

在RFID系統中各個RFID標簽之前不具備相互通信的能力，而大多數RFID應用場景中RFID標簽數量密集，在某一時刻若多個標簽處于RFID讀寫器的讀取范圍內，這些標簽應答時，將會發現信道爭用，數據之間相互干擾和混疊，如下圖。

多標簽碰撞模型圖

RFID讀寫器互相干擾類

傳統的RFID系統中，是采用單一讀寫器方式，但是隨著物聯網技術的不斷發展，單一讀寫器的RFID系統中越來越不能滿足多數場景的需求。因此需要使用多個讀寫器來對目標區域進行監視，這就可能造成多讀寫器碰撞問題。如下圖，在R1和R2的共同有效讀取范圍內存在一個標簽。當R1和R2同時給標簽發送指令信號時，會產生信號干擾，最終此標簽將不能被讀寫器R1和讀寫器R2的任何一個讀取。

讀寫器和讀寫器的碰撞模型圖

另一種讀寫器之間的碰撞情況如下圖，讀寫器R1和讀寫器R2的有效讀取范圍沒有疊加，但是讀寫器R1的干擾范圍和讀寫器R2的有效讀取范圍存在疊加區域。因此處于此疊加區域的RFID標簽，會受讀寫器R1發射的干擾信號影響，導致讀寫器R2可能出現漏讀現象。

讀寫器和讀寫器的碰撞模型圖

因RFID讀寫器自身有能量供應，能夠進行較高復雜度的計算，所以讀寫器能夠檢測到碰撞的產生，并能夠通過與其他讀寫器之間的交流互通來解決讀寫器的碰撞問題，如讀寫器調度算法和功率控制算法都能比較容易地解決讀寫器碰撞問題，因此，一般討論防碰撞都是針對多標簽的碰撞而言的。

為了防止碰撞的發生，RFID系統中需要設計相應的防碰撞技術，在通信中這種技術也稱為多址技術。RFID讀寫器對RFID標簽的讀取過程就是采用的多址存取方式，該方式規范了讀寫器對標簽數據讀取的先后次序的。目前解決無線通信中信息沖突的多址存取方式主要可以分為四種：

1、碼分多址(CDMA)

碼分多址技術是在擴頻通信技術的基礎上，利用擴頻技術在同一時刻同一信道中，完成多路信號的傳輸通信。擴頻的目的是擴展信息帶寬，即把需要發送的具有一定信號帶寬的信息數據， 用一個帶寬遠大于其信號帶寬的偽隨機碼進行調制，這樣使原來的信息數據的帶寬被擴展，最后通過載波調制發送出去。解擴是指在接收端采用完全一致的偽隨機碼，與接收到的寬帶信號作相關處理，把寬帶信號轉換成原來的信息數據。多址是給每個用戶分配一個地址碼，各個碼型互不重疊。碼分多址技術具有抗干擾性好，保密安全性高，信道利用率高等優點。但是該技術也存在諸多缺點，如頻帶利用率低、信道容量小，偽隨機碼的產生和選擇較難，接收時地址碼捕獲時間長等，所以并未得到廣泛使用。

2、空分多址(SDMA)

空分多址是在分離的空間范圍內實現多個目標識別。其實現的方法有兩種：一種方法是將讀寫器和RFID天線之間的作用距離按空間區域進行劃分，把大量的讀寫器和天線安置在一個天線陣列中。當標簽進入這個天線陣列的覆蓋范圍后，與其距離最近的讀寫器對該標簽進行識別。由于每個天線的覆蓋范圍較小，相鄰的讀寫器識別范圍內的標簽同樣可以進行識別而不受相鄰讀寫器的干擾，如果多個標簽根據在天線陣列中的空間位置的不同，可以同時被識別。另外一種方法是，RFID讀寫器利用一個相控陣天線，通過讓天線的方向性圖對準單獨的標簽，這樣標簽根據其在讀寫器作用范圍內的角度位置的不同而區別開來?？辗侄嘀芳夹g的缺點是它對讀寫器天線的要求較高，一個讀寫器可能存在多個天線，系統復雜，成本較大。

3、頻分多址(FDMA)

頻分多址是把若干個使用不同載波頻率的調制信號在同時供通信用戶使用的信道上進行傳輸的技術。通常情況下，RFID系統的上行鏈路(從讀寫器到標簽)頻率是固定的，用于能量的供應和數據的傳輸。對于下行鏈路(從標簽到讀寫器)，不同的標簽采用不同頻率的載波對數據進行調制，這些信號之間不會產生干擾，RFID讀寫器對接收到的不同頻率的信號進行分離，從而實現對不同標簽的識別。頻分多址的RFID系統對RFID讀寫器的硬件要求很高，因此此類系統未得到廣泛應用。

4、時分多址（TDMA）

時分多址具有簡單易實現的優點，它是把整個可供使用的通路容量按時間分配給多個用戶的技術。時分多路復用是按傳輸信號的時間進行分割的，它使不同的信號在不同的時間內傳輸，將整個傳輸時間分為許多時間間隔，每個時間片被一路信號占用。時分多址就是通過在時間上交叉發送每一路信號的一部分來實現一條電路傳輸多路信號的。電路上的每一短暫時刻只有一路信號存在。因為數字信號是有限個離散值，所以時分多路復用技術廣泛應用于包括計算機網絡在內的數字通信系統。目前RFID系統的標簽防碰撞算法大多采用時分多址技術。

TDMA是把整個可供使用的通路容量按時間分配給多個用戶的技術，可分為電子標簽控制法和讀寫器控制法。電子標簽控制法主要有ALOHA算法；而讀寫器控制法有輪詢法和二進制搜索法。目前，RFID系統中最常見的兩大類標簽防碰撞算法是二進制搜索法和ALOHA算法。

二進制樹算法

二進制樹算法的基本思想是將處于沖撞狀態的標簽分成左右兩個子集0和1，先查詢子集0，若沒有沖突，則正確識別標簽；若仍有沖突，則再分裂，把子集0分為00和01兩個子集，依次類推，直到識別出子集0中的所有標簽，再按此步驟查詢子集1。使用基本的二進制樹形算法的標簽能夠記憶以前的查詢結果從而減少平均查詢時間，但對功率要求很高。

二進制樹搜索算法是一種無記憶的算法，即標簽不必儲存以前的查詢情況，這樣可以降低成。在這種算法中讀寫器查詢的不是一個比特，而是一個比特前綴，只有序列號與這個查詢前綴相符的標簽才響應讀寫器的命令而發送其序列號。當只有一個標簽響應的時候讀寫器可以成功識別標簽，但是當有多個標簽響應的時候，下一次循環中讀寫器就把查詢前綴增加一個比特0，通過不斷增加前綴讀寫器就能識別所有的標簽。二進制樹搜索的前提是要辨認出讀寫器中數據碰撞的準確位置，選用曼徹斯特編碼可以檢測出碰撞位。采用二進制樹搜索算法的RFID系統特點是：具有較高的穩定性，易于用軟件實現，吞吐率最高可達36.4%，但ID不能太長，ID越長所需要的時間就越長，當時間超過一定限度時，這種算法將不再適用。

二進制搜索樹的程序流程

ALOHA算法

ALOHA系統采用無規則的時分多址，或叫隨機多址。ALOHA算法采取“標簽先發言”的方式，即RFID標簽一進入讀寫器的作用區域就自動向讀寫器發送其自身的信息。在標簽發送數據的過程中，若有其它標簽也在發送數據，那么將會導致沖突。RFID讀寫器檢測接收到的信號有無沖突，一旦檢測到沖突，RFID讀寫器就發送命令讓標簽先停止發送，隨機等待一段時間后再重新發送以減少沖突。

ALOHA算法的主要特點是各個標簽發射時間是完全隨機的，當工作范圍內標簽的數量不多時ALOHA算法可以很好的工作。缺點就是數據幀發送過程中沖突發生的概率很大，沖突周期是，而且標簽不能自己檢測沖突，只能通過接收讀寫器的命令判斷有無沖突。

當工作范圍內的標簽數增加時，發生碰撞的概率增加，性能急劇下降，信道利用率只有18.4%。針對以上問題，提出了時隙ALOHA算法和幀時隙ALOHA算法等來改善ALOHA算法。采用時隙ALOHA算法的RFID系統因為有讀寫器控制在同步時隙內傳送數據，可能發生碰撞的時間區就縮短了一半，吞吐率最大可達36.8%，相對于純ALOHA算法增加了一倍，但仍局限于只讀型電子標簽。采用幀時隙ALOHA算法的RFID系統適用于傳輸信息量較大的場合，但當標簽數量遠大于時隙個數時，讀取標簽的時間將會大大增加，在標簽數遠小于時隙個數時，就會造成時隙的浪費。

（圖文來源于網絡，侵刪）

審核編輯 黃宇