1. 引言 

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

2. 目前進展 

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

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

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

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

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

3. 改進算法 

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

3.1 算法介紹與分析 
本文提出的算法是在時隙的基礎上利用各個ID 號尾數(shù)不同的特點，同時結合隨機數(shù)來實現(xiàn)防沖突的目的。對于多個需要識別的射頻卡，考慮它的低N 位ID 號，產(chǎn)生2N 個時隙。各個射頻卡在它的低N 位的ID 值所在時隙發(fā)送其ID 號。在一個時隙段，如果有兩個以上的射頻卡（具有相同低N 位ID 值的射頻卡）發(fā)送數(shù)據(jù)，則產(chǎn)生沖突，此時產(chǎn)生隨機數(shù)來區(qū)分；如果只有一個射頻卡發(fā)送其數(shù)據(jù)，則可讀出其ID；如果沒有射頻卡發(fā)送數(shù)據(jù)，則等待一個較短的時間發(fā)現(xiàn)沒有數(shù)據(jù)，則取消這個時隙?？傊惴ǖ乃枷刖褪且M量減少等待和沖突的時間，從而提高防沖突的效率。 

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

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

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

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

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

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

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

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

4. 結論 

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

參考文獻 
[1] 徐麗香, 藍運維. RFID 二進制搜索法防碰撞的實現(xiàn)[J].Microcontrollers &EmbeddedSystems,2006年第5 期 
[2] 李興鶴，胡詠梅，王華蓮. 基于動態(tài)二進制的二叉樹搜索結構RFID 反碰撞算法［J］. 山東科技,第19 卷第二期 
[3] ISO18000-6A 標準: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 標準: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］. 《電子技術應用》2006年第6期 
[6] ISO18000-6C 標準:Information technology-Radio-frequency identification for item management-Part 6C:Parameters for air interface communications at 860 MHz to 960MHz. ［S］ 
[7] 徐松森，詹宜巨，彭衛(wèi)東，趙振宇. 基于后退式索引的二進制樹形搜索反碰撞算法及其實現(xiàn)［J］. 計算機工程與應用，2004 年16 期