RFID防碰撞算法應用研究

高增貊，路 勇

（北京交通大學 電子信息工程學院，北京 100044）

射頻識別技術（RFID, Radio Frequency Identification），又稱無線射頻識別，是一種基于應答器與讀寫器間無線通信的自動識別技術。RFID通過無線信號實現識別目標，讀取目標數據和修改目標數據。射頻識別系統主要包括兩部分，讀寫器和應答器。

在單一讀寫器和多個應答器存在的系統下，很容易出現多個應答器同時響應讀寫器的情況，這會影響讀寫器的正常工作，所以選擇適當的防碰撞算法對于應用RFID系統具有重大意義。

1 防碰撞經典算法

1.1 隨機思想算法

1.1.1 幀時隙ALOHA（SFA）算法

時隙ALOHA算法[1]首先定義一個統一的幀長度，這個幀由若干個時隙組成，時隙的長度就是應答器接收到讀寫器廣播信號后發送應答的時間。

當應答器首次接受到讀寫器的廣播信號的時候，應答器會隨機選擇一個時隙，當到時間到此時隙時，應答器返回應答信息。此時的各個時隙內存在的應答器數量可分為3類，因此操作也分為3類。

（1）第1類是沒有應答器，那么就直接到下一個時隙。

（2）第2類是有兩個或以上應答器，此時多個應答器發送應答信號，那么讀寫器就不能夠完成識別，因此也會繼續下一個時隙。

（3）第3類是有一個應答器，此時讀寫器成功識別應答信息，之后會發送選擇信號，對此應答器進行讀寫，完成后會進入下一個廣播周期。

只有之前選擇應答器被操作完后，其他在讀寫器范圍內的應答器才能進行一個新的尋呼過程。

1.1.2 動態幀時隙ALOHA（DFSA）算法

動態幀時隙ALOHA算法[1]是對幀時隙算法的改進，由于幀時隙算法的吞吐率不穩定，只有在時隙數和應答器數相等的情況下才能夠有比較良好的表現，所以動態幀時隙ALOHA算法針對這種情況進行改進。

當每個時隙內都存在兩個或者兩個以上的應答器時，讀寫器此幀內沒有讀取到任何應答信息，所以下一次會調整每幀內時隙數量（1, 2, 8, …），即幀長度，直到唯一的應答器被識別。此種情況使得讀寫器產生幀的時隙數會隨著應答器數量變化，因此使得效率一直保持比較好的狀態。

1.1.3 動態隨機數算法

動態隨機算法[2]的原理和動態幀時隙ALOHA算法類似。每次的讀寫器尋呼都會發送一個Q值，每個應答器會在1～2(q-1)范圍內隨機選取一個計數。如果應答器的計數為0，則返回應答信息。讀寫器會對接收到的應答信息進行如圖1所示。

圖1 隨機數Q值變化示意圖

（1）如果有一個應答，則發送命令領每個應答器內計數都做減1處理，然后進入下一個接收周期。

（2）如果有多個應答，則增加Q值，并且從新分配應答器計數，然后進入下一個接收周期。

（3）如果沒有應答，則減小Q值（保持大于0），并且從新分配應答器計數，然后進入下一個接收周期。

1.2 基于二分搜索的確定算法

1.2.1 二分搜索算法

二分搜索算法（Binary Search）[1]的整個尋呼機制不同于上述的所有隨機方法。首先，二分搜索算法需要確定具體的碰撞的位置，如果用常規的0和1代替高低電平，即不歸零碼表示信號，那么當出現多個應答器碰撞的時候，接收的信息也能夠讀出，但是此時接收到的信號是多個應答器信號疊加結果，接收器接收到的信號是錯誤的，如圖2所示。

圖2 無基帶編碼導致接收錯誤

對于此問題的解決方法就是對信號進行編碼，通常采用曼徹斯特碼。曼徹斯特碼的0和1表示如圖3所示。

圖3 曼徹斯特碼

如果對于信號進行曼徹斯特編碼，那么對于存在碰撞的情況就會很容易的檢測出來，因為產生碰撞的地方會無法解碼，具體情況如圖4所示。

圖4 采用曼徹斯特碼檢測碰撞位

對于二分搜索算法實現，首先應答器都有唯一的二進制序列作為自身的ID，之后讀寫器會用同樣長度的發送序列以及如下指令配合進行篩選：

（1）REQUEST指令：發送一個二進制序列給應答器，如果應答器的數字序列小于讀寫器發送過來的序列，則應答器把自己的序列返回給讀寫器。

（2）SELECT指令：發送一個通過算法決定的序列給應答器，如果應答器的序列與發送過來的序列相等，此應答器被選中。

（3）READ指令：對選中的應答器內的數據進行操作。

（4）UNSELECT指令：取消之前被選擇的應答器的被選擇狀態和使應答器滅活，此時應答器不會響應REQUEST指令。

每個周期，讀寫器首先發送REQUEST指令，一般發送同樣長度的最大二進制序列，即全1序列。此時所有的應答器都會把自己的序列返回給讀寫器，根據譯碼，能夠檢測出碰撞位，根據最高碰撞位，改變下一次命令REQUEST發送的序列，改變規則是：首先，基序列是上一次的發送序列，把此序列的最高的碰撞位置定位為0，此序列的最高碰撞位之前的各位值和發生碰撞的應答器ID對應位保持一致，新的發送序列因此會變小，因此每次改變序列會減少選中的應答器，直到選中一個應答器完成一次識別。然后，識別出的應答器會被SELECT，READ和UNSELECT操作，因此之后這個應答器不會再響應REQUEST命令。重復此流程直到所有的應答器都被識別，整個流程如圖5所示。

圖5 二分搜索算法流程

1.2.2 動態二分搜索算法

動態二分搜索算法[1]是對上述的二分搜索算法的裁剪，區別在于讀寫器每次發送的REQUEST命令發送的二進制序列和應答器回復的二進制序列。此算法中，每次REQUEST發送的二進制序列是上一次碰撞最高位和其前面位的處理部分，而應答器返回的是上一次碰撞最高位之后后面的部分，這樣能夠大量減少冗余序列的發送。

2 算法仿真分析

本文對于上述的兩個經典算法，動態幀時隙ALOHA和動態二分搜索算法，進行了MATLAB仿真，所得的結果主要是針對不同應答器個數的情況下，讀寫器的尋呼次數比較。

對二分搜索算法在不同長度序列下，同時識別1～100個應答器的模擬仿真，比較序列長度和尋呼次數是否存在關系，如圖6所示。圖中表明序列長度和尋呼性能在此數量應答器情況下無明顯關系，但是按照二分搜索算法原理可知道序列長度決定了識別范圍。假設初始的序列長度為L，那么二分搜索算法的防碰撞范圍是1-2(L-1)。

圖6 序列長度和尋呼次數

之后對于動態幀時隙ALOHA（DFSA）算法和動態二叉樹搜索（DBS）算法進行了仿真比較，如圖7所示。DFS算法初始幀時隙是24個，之后指數4會根據碰撞結果增加或減小；DBS初始的序列長度為8位。如圖7所示，在應答器數目較少的情況下，DBS算法表現出了良好的搜索性能，隨著應答器數量的增加，DFS的曲線追了上來，到100之后已經優于了DBS算法。當兩個算法的復雜度是不一樣的，由第二部分介紹原理時可以了解到，DBS的設計難度要高于DFS，因為DBS實現中需要添加曼徹斯特碼的編碼解碼模塊，而DFS只需要分配隨機的時隙即可。因此在實際應用中，DFS會比較容易實現。

3 結束語

圖7 動態幀時隙ALOHA算法和動態二叉樹搜索算法進行了仿真比較

本文介紹了RFID經典的防碰撞算法，并對其中經典的動態幀時隙ALOHA算法和動態二分搜索算法進行了仿真分析，從尋呼次數的角度分析了兩者在性能上的優缺點。可以看出，動態幀時隙ALOHA算法實現簡單，尋呼次數和應答器個數存在穩定的線性關系；動態二分搜索算法需要編碼解碼幫助識別碰撞位。能夠在應答器較少的情況下產生優秀的識別性能，但是性能會隨著應答器數量的增加而惡化。

除了經典算法外，可以根據需要選擇改進算法。對于隨機類算法，都是基于動態幀時隙ALOHA算法的改進算法，可以從分組[3]，預估標簽[4]等角度去改進；對于確定性的二分搜索算法可以通過編碼方式變化[5]，記錄碰撞位[6]操作等減弱動態二分搜索算法大量應答器情況下的惡化效果。

在RFID應用于各類產品的時候，防碰撞算法的選擇不可避免，針對應用環境的不同，選擇適應的防碰撞算法能夠更有效地完成識別。

[1]Klaus Finkenzeller . RFID HANDBOOK FUNDAMENTALS AND APPLICATIONS IN CONTACTLESS SMART CARDS,RADIO FREQUENCY IDENTIFICATION AND NEARFIELD COMMUNICATION (3nd Edition)[M], John Wiley& Sons Ltd, 2010.

[2]劉 佳，張有光.基于時隙的RFID防碰撞算法分析[J].通信與網絡，2007（5）：95-96.

[3]尹 君，何怡剛，李 兵，鄧 曉，譚陽紅，肖迎群.基于分組動態幀時隙的RFID防碰撞算法[J].計算機工程，2009，20（35）：267-269.

[4]陳春明，馮玉田，付良成. RFID動態幀時隙防沖突改進算法研究[J].電子技術應用，2013（1）：86-89.

[5]李世煜，馮全源，魯 飛.基于BIBD(4,2,1)的防碰撞算法[J].計算機工程，2009，3（35）：279-281.

[6]王 雪，錢志鴻，胡正超，李奕男.基于二叉樹的RFID防碰撞算法的研究[J].通信學報，2010，6（31）：49-57.