RFID防碰撞算法應用研究

高增貊，路 勇

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

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

在單一讀寫器和多個應答器存在的系統(tǒng)下，很容易出現(xiàn)多個應答器同時響應讀寫器的情況，這會影響讀寫器的正常工作，所以選擇適當?shù)姆琅鲎菜惴▽τ趹肦FID系統(tǒng)具有重大意義。

1 防碰撞經(jīng)典算法

1.1 隨機思想算法

1.1.1 幀時隙ALOHA（SFA）算法

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

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

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

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

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

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

1.1.2 動態(tài)幀時隙ALOHA（DFSA）算法

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

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

1.1.3 動態(tài)隨機數(shù)算法

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

圖1 隨機數(shù)Q值變化示意圖

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

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

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

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

1.2.1 二分搜索算法

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

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

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

圖3 曼徹斯特碼

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

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

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

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

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

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

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

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

圖5 二分搜索算法流程

1.2.2 動態(tài)二分搜索算法

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

2 算法仿真分析

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

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

圖6 序列長度和尋呼次數(shù)

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

3 結束語

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

本文介紹了RFID經(jīng)典的防碰撞算法，并對其中經(jīng)典的動態(tài)幀時隙ALOHA算法和動態(tài)二分搜索算法進行了仿真分析，從尋呼次數(shù)的角度分析了兩者在性能上的優(yōu)缺點?？梢钥闯觯瑒討B(tài)幀時隙ALOHA算法實現(xiàn)簡單，尋呼次數(shù)和應答器個數(shù)存在穩(wěn)定的線性關系；動態(tài)二分搜索算法需要編碼解碼幫助識別碰撞位。能夠在應答器較少的情況下產(chǎn)生優(yōu)秀的識別性能，但是性能會隨著應答器數(shù)量的增加而惡化。

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

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

[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].通信與網(wǎng)絡，2007（5）：95-96.

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

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

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

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