1. 引言 

射頻識(shí)別技術(shù)RFID (Radio Frequency Identification)是目前國內(nèi)外發(fā)展很快的一項(xiàng)新技術(shù)。該技術(shù)是采用先進(jìn)的射頻技術(shù)，實(shí)現(xiàn)對(duì)各類物體或設(shè)備標(biāo)號(hào)的自動(dòng)識(shí)別，從而對(duì)其進(jìn)行管理。射頻識(shí)別技術(shù)能無源，并快速地識(shí)別多個(gè)物體或設(shè)備，能應(yīng)用于許多場(chǎng)合。隨著RFID卡片端成本的不斷降低以及體積的不斷變小，其應(yīng)用必將越來越多。在射頻卡的識(shí)別中，需要解決的一個(gè)問題是沖突問題。當(dāng)多個(gè)射頻卡同時(shí)發(fā)送數(shù)據(jù)時(shí)就會(huì)產(chǎn)生信道沖突，使得讀寫頭不能讀出射頻卡的信息。故防沖突算法一直是RFID 中重要研究?jī)?nèi)容之一。 

2. 目前進(jìn)展 

目前的防沖突算法分兩大類，一是基于曼切斯特編碼的二進(jìn)制搜索算法及其改進(jìn)算法，二是基于隨機(jī)數(shù)產(chǎn)生器的時(shí)隙算法及其改進(jìn)算法，下面分別介紹。 

2.1 二進(jìn)制搜索算法及其改進(jìn)算法 
在二進(jìn)制搜索算法中，射頻卡的ID 號(hào)必須采用曼切斯特編碼。曼切斯特碼（Mancherster）可在多個(gè)射頻卡同時(shí)響應(yīng)時(shí)，譯出錯(cuò)誤位置，可以按位定出發(fā)生沖突的位置。根據(jù)沖突的位置，搜索射頻卡[1]。二進(jìn)制搜索算法只能識(shí)別ID 號(hào)唯一的情況。 

改進(jìn)的算法有動(dòng)態(tài)二進(jìn)制搜索算法，算法改進(jìn)的地方是對(duì)沒有發(fā)生沖突的ID 位只傳送一次。這樣就減少了重傳的數(shù)據(jù)，提高了效率[1]。文獻(xiàn)[2]中所提的基于動(dòng)態(tài)二進(jìn)制的二叉樹搜索結(jié)構(gòu)RFID 反碰撞算法是對(duì)二進(jìn)制搜索算法的改進(jìn)。它的思想是對(duì)每次識(shí)別的沖突位進(jìn)行分類，分成0、1 兩部分，從而形成一顆二叉樹[2]，如圖1。 

2.2 時(shí)隙算法及其改進(jìn)算法 
時(shí)隙算法規(guī)定射頻卡傳送其ID 號(hào)所用的時(shí)間為一個(gè)時(shí)隙，如果每個(gè)射頻卡在不同的時(shí)隙段發(fā)送其ID 號(hào)，就能避免沖突。算法的關(guān)鍵是怎樣為不同的射頻卡確定其所在的時(shí)隙，一般是采用隨機(jī)數(shù)的策略。算法過程如圖2。 

ISO 18000-6A[3] 和18000-6B[4]規(guī)定了這種時(shí)隙的標(biāo)準(zhǔn)算法。目前國內(nèi)比較好的算法是文獻(xiàn)[5]提出的一種新穎的RFID 防沖突算法，算法基于隨機(jī)數(shù)產(chǎn)生時(shí)隙，并分群快速識(shí)別多個(gè)射頻卡[5]。國外比較好的算法是文獻(xiàn)[6]中一種改進(jìn)的算法，已在歐美得到實(shí)用。 

3. 改進(jìn)算法 

通過對(duì)以前RFID 防沖突算法兩類方法的分析與研究，結(jié)合這兩種方法的優(yōu)點(diǎn)，本文提出了一種新的算法。 

3.1 算法介紹與分析 
本文提出的算法是在時(shí)隙的基礎(chǔ)上利用各個(gè)ID 號(hào)尾數(shù)不同的特點(diǎn)，同時(shí)結(jié)合隨機(jī)數(shù)來實(shí)現(xiàn)防沖突的目的。對(duì)于多個(gè)需要識(shí)別的射頻卡，考慮它的低N 位ID 號(hào)，產(chǎn)生2N 個(gè)時(shí)隙。各個(gè)射頻卡在它的低N 位的ID 值所在時(shí)隙發(fā)送其ID 號(hào)。在一個(gè)時(shí)隙段，如果有兩個(gè)以上的射頻卡（具有相同低N 位ID 值的射頻卡）發(fā)送數(shù)據(jù)，則產(chǎn)生沖突，此時(shí)產(chǎn)生隨機(jī)數(shù)來區(qū)分；如果只有一個(gè)射頻卡發(fā)送其數(shù)據(jù)，則可讀出其ID；如果沒有射頻卡發(fā)送數(shù)據(jù)，則等待一個(gè)較短的時(shí)間發(fā)現(xiàn)沒有數(shù)據(jù)，則取消這個(gè)時(shí)隙。總之算法的思想就是要盡量減少等待和沖突的時(shí)間，從而提高防沖突的效率。 

算法步驟如下： 
1. n 個(gè)射頻卡進(jìn)入讀寫范圍，感應(yīng)讀寫頭發(fā)出的射頻，獲得能量，處于激活狀態(tài)。 
2. 讀寫頭發(fā)送第一個(gè)控制命令，這個(gè)命令使得各個(gè)射頻卡將它的ID 號(hào)的低N 位放入寄存器，如這N 位組成的值為零則發(fā)送這個(gè)射頻卡的ID 號(hào)。 
3. 如果只有一個(gè)射頻卡發(fā)送其ID 則讀寫頭讀出此ID。此時(shí)讀寫頭判斷總時(shí)隙是否滿，是則結(jié)束，否則轉(zhuǎn)6。 
4. 如果有多個(gè)射頻卡發(fā)送其ID 則發(fā)生沖突，則要增加a 個(gè)時(shí)隙，讀寫頭發(fā)送沖突控制命令，各個(gè)射頻卡如果寄存器值為零則產(chǎn)生N1 個(gè)隨機(jī)數(shù)放入寄存器中（2N1＝a），否則寄存器的值加上a，如寄存器的值為零則發(fā)送這個(gè)射頻卡的ID 號(hào)，轉(zhuǎn)3。 
5. 如果1/b 個(gè)時(shí)隙后讀寫卡沒有接到任何數(shù)據(jù)，則此時(shí)讀寫頭判斷總時(shí)隙是否滿，是則結(jié)束，否則轉(zhuǎn)6 
6. 讀寫頭發(fā)送減1 控制命令，每個(gè)射頻卡接到此命令后，將其寄存器的值減1，如寄存器的值為零則發(fā)送這個(gè)射頻卡的ID 號(hào)，如小于零則此射頻卡不再激活，轉(zhuǎn)3。 

從步驟中可以看出射頻卡需要實(shí)現(xiàn)的幾個(gè)操作命令是：將卡的ID 號(hào)讀入寄存器、產(chǎn)生隨機(jī)數(shù)壓入寄存器、對(duì)寄存器進(jìn)行加減操作、判斷是否為零，這些都是一些比較簡(jiǎn)單的命令可以快速的實(shí)現(xiàn)，且消耗小。 

信道利用率是衡量一個(gè)防沖突算法效率的標(biāo)準(zhǔn)，其值是傳輸數(shù)據(jù)時(shí)總的時(shí)間除以整個(gè)識(shí)別過程所用的時(shí)間。如在本算法中產(chǎn)生的沖突次數(shù)為c，因沖突而增加的周期數(shù)為T，則期信道利用率Y 的計(jì)算公式為： 

在式3.1 中，需要權(quán)衡的是N 的值。怎樣對(duì)N 取值才能更大的發(fā)揮算法的優(yōu)點(diǎn)？下面對(duì)其進(jìn)行仿真并分析。 

3.2 仿真分析 
對(duì)上面的算法我們來進(jìn)行模擬，模擬的過程是先產(chǎn)生一些射頻卡的卡號(hào)，卡號(hào)是隨機(jī)產(chǎn)生的，我們的任務(wù)就是識(shí)別這些隨機(jī)產(chǎn)生的卡號(hào)。 

假設(shè)需要識(shí)別的射頻卡個(gè)數(shù)n 為16 個(gè)，射頻卡的ID 號(hào)為64 位，需要識(shí)別的卡號(hào)只有后面15 位不同，前面的49 位相同，故產(chǎn)生的隨機(jī)數(shù)的范圍為：0～216-1。a 的值取4（即N1＝2），識(shí)別的個(gè)數(shù)n＝15，b＝10，樣本數(shù)m＝10000，N 的值我們?nèi)?，3、4、5、6、7來進(jìn)行對(duì)比，對(duì)產(chǎn)生的隨機(jī)數(shù)允許重復(fù)。完全模擬整個(gè)算法過程，并記錄產(chǎn)生的沖突的次數(shù)C 和增加的總周期數(shù)T，根據(jù)式3.1 即可計(jì)算出信道利用率的期望值。結(jié)果如表1。 

算法中N 的取值是關(guān)鍵，直接影響到算法的效率。從圖3 中我們可以看出N 的值取得使之2N 于識(shí)別的個(gè)數(shù)附近。當(dāng)然N 的值可以變換以適應(yīng)不同的場(chǎng)合，但是一般讀寫頭讀取射頻卡的時(shí)間固定，故N 的值一般也是固定，這樣也簡(jiǎn)化了射頻卡的邏輯處理，從而降低了功耗。 

從上面的模擬仿真中可以看出信道利用率還是挺高的，達(dá)到了60％~74％。與文獻(xiàn)[7]中的基于后退式索引的二進(jìn)制樹形搜索反碰撞算法的信道利用率在50％左右相比，本文的方法不僅信道利用率比其高，而且不需要曼切斯特編碼故更易于實(shí)現(xiàn)，響應(yīng)更快速[7]。與文獻(xiàn)[5]中提出的新穎的RFID 防沖突算法相比，因?yàn)榭紤]了射頻卡的ID 值和減少了等待的時(shí)間，在識(shí)別物品個(gè)數(shù)穩(wěn)定的情況下具有比其更好的性能。 

4. 結(jié)論 

本文提出了一種盡量減少等待時(shí)隙的提高RFID 防沖突效率的方法。這種方法是對(duì)以前兩種方法的折中，在識(shí)別數(shù)量穩(wěn)定的一些場(chǎng)合（比如機(jī)場(chǎng)的物件識(shí)別）等情況下具有很好的信道利用率，且能識(shí)別重復(fù)的ID。使本方法適應(yīng)更多的場(chǎng)合也是以后研究發(fā)展的方向。 

參考文獻(xiàn) 
[1] 徐麗香, 藍(lán)運(yùn)維. RFID 二進(jìn)制搜索法防碰撞的實(shí)現(xiàn)[J].Microcontrollers &EmbeddedSystems,2006年第5 期 
[2] 李興鶴，胡詠梅，王華蓮. 基于動(dòng)態(tài)二進(jìn)制的二叉樹搜索結(jié)構(gòu)RFID 反碰撞算法［J］. 山東科技,第19 卷第二期 
[3] ISO18000-6A 標(biāo)準(zhǔn):Information technology automatic identification and data capture techniques-Radio frequency identification for item management air interface-Part6:Parameters for air interface communications at 860-960MHz［S］ 
[4] ISO18000-6B 標(biāo)準(zhǔn):Information technology automatic identification and data capture techniques-Radio frequency identification for item management air interface-Part 6:Parameters for air interface 
communications at 860-960MHz［S］ 
[5] 張明，張建華, 徐國鑫, 張 平. 一種新穎的 RFID 防沖突算法［J］. 《電子技術(shù)應(yīng)用》2006年第6期 
[6] ISO18000-6C 標(biāo)準(zhǔn):Information technology-Radio-frequency identification for item management-Part 6C:Parameters for air interface communications at 860 MHz to 960MHz. ［S］ 
[7] 徐松森，詹宜巨，彭衛(wèi)東，趙振宇. 基于后退式索引的二進(jìn)制樹形搜索反碰撞算法及其實(shí)現(xiàn)［J］. 計(jì)算機(jī)工程與應(yīng)用，2004 年16 期