登錄
注冊
一種簡單高效的RFID 防沖突算法
作者：北京郵電大學計算機科學與技術學院 柳本金 丁海健
來源：RFID世界網
日期：2007-12-17 14:55:44
摘要：本文在分析研究以往兩類RFID 防沖突算法的基礎上，結合兩者的優點提出了一種基于時隙的改進算法。通過仿真與其它防沖突算法相比在識別數量穩定的情況下，本文提出的算法具有更好的效果。
1. 引言
射頻識別技術RFID (Radio Frequency Identification)是目前國內外發展很快的一項新技術。該技術是采用先進的射頻技術，實現對各類物體或設備標號的自動識別，從而對其進行管理。射頻識別技術能無源，并快速地識別多個物體或設備，能應用于許多場合。隨著RFID卡片端成本的不斷降低以及體積的不斷變小，其應用必將越來越多。在射頻卡的識別中，需要解決的一個問題是沖突問題。當多個射頻卡同時發送數據時就會產生信道沖突，使得讀寫頭不能讀出射頻卡的信息。故防沖突算法一直是RFID 中重要研究內容之一。
2. 目前進展
目前的防沖突算法分兩大類，一是基于曼切斯特編碼的二進制搜索算法及其改進算法，二是基于隨機數產生器的時隙算法及其改進算法，下面分別介紹。
2.1 二進制搜索算法及其改進算法
在二進制搜索算法中，射頻卡的ID 號必須采用曼切斯特編碼。曼切斯特碼（Mancherster）可在多個射頻卡同時響應時，譯出錯誤位置，可以按位定出發生沖突的位置。根據沖突的位置，搜索射頻卡[1]。二進制搜索算法只能識別ID 號唯一的情況。
改進的算法有動態二進制搜索算法，算法改進的地方是對沒有發生沖突的ID 位只傳送一次。這樣就減少了重傳的數據，提高了效率[1]。文獻[2]中所提的基于動態二進制的二叉樹搜索結構RFID 反碰撞算法是對二進制搜索算法的改進。它的思想是對每次識別的沖突位進行分類，分成0、1 兩部分，從而形成一顆二叉樹[2]，如圖1。
時隙算法規定射頻卡傳送其ID 號所用的時間為一個時隙，如果每個射頻卡在不同的時隙段發送其ID 號，就能避免沖突。算法的關鍵是怎樣為不同的射頻卡確定其所在的時隙，一般是采用隨機數的策略。算法過程如圖2。
3. 改進算法
通過對以前RFID 防沖突算法兩類方法的分析與研究，結合這兩種方法的優點，本文提出了一種新的算法。
3.1 算法介紹與分析
本文提出的算法是在時隙的基礎上利用各個ID 號尾數不同的特點，同時結合隨機數來實現防沖突的目的。對于多個需要識別的射頻卡，考慮它的低N 位ID 號，產生2N 個時隙。各個射頻卡在它的低N 位的ID 值所在時隙發送其ID 號。在一個時隙段，如果有兩個以上的射頻卡（具有相同低N 位ID 值的射頻卡）發送數據，則產生沖突，此時產生隨機數來區分；如果只有一個射頻卡發送其數據，則可讀出其ID；如果沒有射頻卡發送數據，則等待一個較短的時間發現沒有數據，則取消這個時隙。總之算法的思想就是要盡量減少等待和沖突的時間，從而提高防沖突的效率。
算法步驟如下：
1. n 個射頻卡進入讀寫范圍，感應讀寫頭發出的射頻，獲得能量，處于激活狀態。
2. 讀寫頭發送第一個控制命令，這個命令使得各個射頻卡將它的ID 號的低N 位放入寄存器，如這N 位組成的值為零則發送這個射頻卡的ID 號。
3. 如果只有一個射頻卡發送其ID 則讀寫頭讀出此ID。此時讀寫頭判斷總時隙是否滿，是則結束，否則轉6。
4. 如果有多個射頻卡發送其ID 則發生沖突，則要增加a 個時隙，讀寫頭發送沖突控制命令，各個射頻卡如果寄存器值為零則產生N1 個隨機數放入寄存器中（2N1＝a），否則寄存器的值加上a，如寄存器的值為零則發送這個射頻卡的ID 號，轉3。
5. 如果1/b 個時隙后讀寫卡沒有接到任何數據，則此時讀寫頭判斷總時隙是否滿，是則結束，否則轉6
6. 讀寫頭發送減1 控制命令，每個射頻卡接到此命令后，將其寄存器的值減1，如寄存器的值為零則發送這個射頻卡的ID 號，如小于零則此射頻卡不再激活，轉3。
從步驟中可以看出射頻卡需要實現的幾個操作命令是：將卡的ID 號讀入寄存器、產生隨機數壓入寄存器、對寄存器進行加減操作、判斷是否為零，這些都是一些比較簡單的命令可以快速的實現，且消耗小。
信道利用率是衡量一個防沖突算法效率的標準，其值是傳輸數據時總的時間除以整個識別過程所用的時間。如在本算法中產生的沖突次數為c，因沖突而增加的周期數為T，則期信道利用率Y 的計算公式為：
3.2 仿真分析
對上面的算法我們來進行模擬，模擬的過程是先產生一些射頻卡的卡號，卡號是隨機產生的，我們的任務就是識別這些隨機產生的卡號。
假設需要識別的射頻卡個數n 為16 個，射頻卡的ID 號為64 位，需要識別的卡號只有后面15 位不同，前面的49 位相同，故產生的隨機數的范圍為：0～216-1。a 的值取4（即N1＝2），識別的個數n＝15，b＝10，樣本數m＝10000，N 的值我們取2，3、4、5、6、7來進行對比，對產生的隨機數允許重復。完全模擬整個算法過程，并記錄產生的沖突的次數C 和增加的總周期數T，根據式3.1 即可計算出信道利用率的期望值。結果如表1。
從上面的模擬仿真中可以看出信道利用率還是挺高的，達到了60％~74％。與文獻[7]中的基于后退式索引的二進制樹形搜索反碰撞算法的信道利用率在50％左右相比，本文的方法不僅信道利用率比其高，而且不需要曼切斯特編碼故更易于實現，響應更快速[7]。與文獻[5]中提出的新穎的RFID 防沖突算法相比，因為考慮了射頻卡的ID 值和減少了等待的時間，在識別物品個數穩定的情況下具有比其更好的性能。
4. 結論
本文提出了一種盡量減少等待時隙的提高RFID 防沖突效率的方法。這種方法是對以前兩種方法的折中，在識別數量穩定的一些場合（比如機場的物件識別）等情況下具有很好的信道利用率，且能識別重復的ID。使本方法適應更多的場合也是以后研究發展的方向。
參考文獻
[1] 徐麗香, 藍運維. RFID 二進制搜索法防碰撞的實現[J].Microcontrollers &EmbeddedSystems,2006年第5 期
[2] 李興鶴，胡詠梅，王華蓮. 基于動態二進制的二叉樹搜索結構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] 徐松森，詹宜巨，彭衛東，趙振宇. 基于后退式索引的二進制樹形搜索反碰撞算法及其實現［J］. 計算機工程與應用，2004 年16 期
射頻識別技術RFID (Radio Frequency Identification)是目前國內外發展很快的一項新技術。該技術是采用先進的射頻技術，實現對各類物體或設備標號的自動識別，從而對其進行管理。射頻識別技術能無源，并快速地識別多個物體或設備，能應用于許多場合。隨著RFID卡片端成本的不斷降低以及體積的不斷變小，其應用必將越來越多。在射頻卡的識別中，需要解決的一個問題是沖突問題。當多個射頻卡同時發送數據時就會產生信道沖突，使得讀寫頭不能讀出射頻卡的信息。故防沖突算法一直是RFID 中重要研究內容之一。
2. 目前進展
目前的防沖突算法分兩大類，一是基于曼切斯特編碼的二進制搜索算法及其改進算法，二是基于隨機數產生器的時隙算法及其改進算法，下面分別介紹。
2.1 二進制搜索算法及其改進算法
在二進制搜索算法中，射頻卡的ID 號必須采用曼切斯特編碼。曼切斯特碼（Mancherster）可在多個射頻卡同時響應時，譯出錯誤位置，可以按位定出發生沖突的位置。根據沖突的位置，搜索射頻卡[1]。二進制搜索算法只能識別ID 號唯一的情況。
改進的算法有動態二進制搜索算法，算法改進的地方是對沒有發生沖突的ID 位只傳送一次。這樣就減少了重傳的數據，提高了效率[1]。文獻[2]中所提的基于動態二進制的二叉樹搜索結構RFID 反碰撞算法是對二進制搜索算法的改進。它的思想是對每次識別的沖突位進行分類，分成0、1 兩部分，從而形成一顆二叉樹[2]，如圖1。
時隙算法規定射頻卡傳送其ID 號所用的時間為一個時隙，如果每個射頻卡在不同的時隙段發送其ID 號，就能避免沖突。算法的關鍵是怎樣為不同的射頻卡確定其所在的時隙，一般是采用隨機數的策略。算法過程如圖2。
3. 改進算法
通過對以前RFID 防沖突算法兩類方法的分析與研究，結合這兩種方法的優點，本文提出了一種新的算法。
3.1 算法介紹與分析
本文提出的算法是在時隙的基礎上利用各個ID 號尾數不同的特點，同時結合隨機數來實現防沖突的目的。對于多個需要識別的射頻卡，考慮它的低N 位ID 號，產生2N 個時隙。各個射頻卡在它的低N 位的ID 值所在時隙發送其ID 號。在一個時隙段，如果有兩個以上的射頻卡（具有相同低N 位ID 值的射頻卡）發送數據，則產生沖突，此時產生隨機數來區分；如果只有一個射頻卡發送其數據，則可讀出其ID；如果沒有射頻卡發送數據，則等待一個較短的時間發現沒有數據，則取消這個時隙。總之算法的思想就是要盡量減少等待和沖突的時間，從而提高防沖突的效率。
算法步驟如下：
1. n 個射頻卡進入讀寫范圍，感應讀寫頭發出的射頻，獲得能量，處于激活狀態。
2. 讀寫頭發送第一個控制命令，這個命令使得各個射頻卡將它的ID 號的低N 位放入寄存器，如這N 位組成的值為零則發送這個射頻卡的ID 號。
3. 如果只有一個射頻卡發送其ID 則讀寫頭讀出此ID。此時讀寫頭判斷總時隙是否滿，是則結束，否則轉6。
4. 如果有多個射頻卡發送其ID 則發生沖突，則要增加a 個時隙，讀寫頭發送沖突控制命令，各個射頻卡如果寄存器值為零則產生N1 個隨機數放入寄存器中（2N1＝a），否則寄存器的值加上a，如寄存器的值為零則發送這個射頻卡的ID 號，轉3。
5. 如果1/b 個時隙后讀寫卡沒有接到任何數據，則此時讀寫頭判斷總時隙是否滿，是則結束，否則轉6
6. 讀寫頭發送減1 控制命令，每個射頻卡接到此命令后，將其寄存器的值減1，如寄存器的值為零則發送這個射頻卡的ID 號，如小于零則此射頻卡不再激活，轉3。
從步驟中可以看出射頻卡需要實現的幾個操作命令是：將卡的ID 號讀入寄存器、產生隨機數壓入寄存器、對寄存器進行加減操作、判斷是否為零，這些都是一些比較簡單的命令可以快速的實現，且消耗小。
信道利用率是衡量一個防沖突算法效率的標準，其值是傳輸數據時總的時間除以整個識別過程所用的時間。如在本算法中產生的沖突次數為c，因沖突而增加的周期數為T，則期信道利用率Y 的計算公式為：
3.2 仿真分析
對上面的算法我們來進行模擬，模擬的過程是先產生一些射頻卡的卡號，卡號是隨機產生的，我們的任務就是識別這些隨機產生的卡號。
假設需要識別的射頻卡個數n 為16 個，射頻卡的ID 號為64 位，需要識別的卡號只有后面15 位不同，前面的49 位相同，故產生的隨機數的范圍為：0～216-1。a 的值取4（即N1＝2），識別的個數n＝15，b＝10，樣本數m＝10000，N 的值我們取2，3、4、5、6、7來進行對比，對產生的隨機數允許重復。完全模擬整個算法過程，并記錄產生的沖突的次數C 和增加的總周期數T，根據式3.1 即可計算出信道利用率的期望值。結果如表1。
從上面的模擬仿真中可以看出信道利用率還是挺高的，達到了60％~74％。與文獻[7]中的基于后退式索引的二進制樹形搜索反碰撞算法的信道利用率在50％左右相比，本文的方法不僅信道利用率比其高，而且不需要曼切斯特編碼故更易于實現，響應更快速[7]。與文獻[5]中提出的新穎的RFID 防沖突算法相比，因為考慮了射頻卡的ID 值和減少了等待的時間，在識別物品個數穩定的情況下具有比其更好的性能。
4. 結論
本文提出了一種盡量減少等待時隙的提高RFID 防沖突效率的方法。這種方法是對以前兩種方法的折中，在識別數量穩定的一些場合（比如機場的物件識別）等情況下具有很好的信道利用率，且能識別重復的ID。使本方法適應更多的場合也是以后研究發展的方向。
參考文獻
[1] 徐麗香, 藍運維. RFID 二進制搜索法防碰撞的實現[J].Microcontrollers &EmbeddedSystems,2006年第5 期
[2] 李興鶴，胡詠梅，王華蓮. 基于動態二進制的二叉樹搜索結構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] 徐松森，詹宜巨，彭衛東，趙振宇. 基于后退式索引的二進制樹形搜索反碰撞算法及其實現［J］. 計算機工程與應用，2004 年16 期
