RFID防碰撞算法應(yīng)用研究

高增貊，路 勇

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

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

在單一讀寫器和多個(gè)應(yīng)答器存在的系統(tǒng)下，很容易出現(xiàn)多個(gè)應(yīng)答器同時(shí)響應(yīng)讀寫器的情況，這會(huì)影響讀寫器的正常工作，所以選擇適當(dāng)?shù)姆琅鲎菜惴▽?duì)于應(yīng)用RFID系統(tǒng)具有重大意義。

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

1.1 隨機(jī)思想算法

1.1.1 幀時(shí)隙ALOHA（SFA）算法

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

當(dāng)應(yīng)答器首次接受到讀寫器的廣播信號(hào)的時(shí)候，應(yīng)答器會(huì)隨機(jī)選擇一個(gè)時(shí)隙，當(dāng)?shù)綍r(shí)間到此時(shí)隙時(shí)，應(yīng)答器返回應(yīng)答信息。此時(shí)的各個(gè)時(shí)隙內(nèi)存在的應(yīng)答器數(shù)量可分為3類，因此操作也分為3類。

（1）第1類是沒有應(yīng)答器，那么就直接到下一個(gè)時(shí)隙。

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

（3）第3類是有一個(gè)應(yīng)答器，此時(shí)讀寫器成功識(shí)別應(yīng)答信息，之后會(huì)發(fā)送選擇信號(hào)，對(duì)此應(yīng)答器進(jìn)行讀寫，完成后會(huì)進(jìn)入下一個(gè)廣播周期。

只有之前選擇應(yīng)答器被操作完后，其他在讀寫器范圍內(nèi)的應(yīng)答器才能進(jìn)行一個(gè)新的尋呼過(guò)程。

1.1.2 動(dòng)態(tài)幀時(shí)隙ALOHA（DFSA）算法

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

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

1.1.3 動(dòng)態(tài)隨機(jī)數(shù)算法

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

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

（1）如果有一個(gè)應(yīng)答，則發(fā)送命令領(lǐng)每個(gè)應(yīng)答器內(nèi)計(jì)數(shù)都做減1處理，然后進(jìn)入下一個(gè)接收周期。

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

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

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

1.2.1 二分搜索算法

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

圖2 無(wú)基帶編碼導(dǎo)致接收錯(cuò)誤

對(duì)于此問(wèn)題的解決方法就是對(duì)信號(hào)進(jìn)行編碼，通常采用曼徹斯特碼。曼徹斯特碼的0和1表示如圖3所示。

圖3 曼徹斯特碼

如果對(duì)于信號(hào)進(jìn)行曼徹斯特編碼，那么對(duì)于存在碰撞的情況就會(huì)很容易的檢測(cè)出來(lái)，因?yàn)楫a(chǎn)生碰撞的地方會(huì)無(wú)法解碼，具體情況如圖4所示。

圖4 采用曼徹斯特碼檢測(cè)碰撞位

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

（1）REQUEST指令：發(fā)送一個(gè)二進(jìn)制序列給應(yīng)答器，如果應(yīng)答器的數(shù)字序列小于讀寫器發(fā)送過(guò)來(lái)的序列，則應(yīng)答器把自己的序列返回給讀寫器。

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

（3）READ指令：對(duì)選中的應(yīng)答器內(nèi)的數(shù)據(jù)進(jìn)行操作。

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

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

圖5 二分搜索算法流程

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

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

2 算法仿真分析

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

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

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

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

3 結(jié)束語(yǔ)

圖7 動(dòng)態(tài)幀時(shí)隙ALOHA算法和動(dòng)態(tài)二叉樹搜索算法進(jìn)行了仿真比較

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

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

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

[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]劉 佳，張有光.基于時(shí)隙的RFID防碰撞算法分析[J].通信與網(wǎng)絡(luò)，2007（5）：95-96.

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

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

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

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