一種新穎的RFID防沖突算法

1、一種新穎的RFID防沖突算法    無線射頻識別(RFID)是一種非接觸式的自動識別技術，其基本原理是刺用射頻信號和空間耦合(電感或電磁耦合)的傳輸特性，實現(xiàn)對特定物體的自動識別。RFID技術可以追溯至第二次世界大戰(zhàn)期間。后來發(fā)展應用到鐵路、軍隊的貨物跟蹤甚至寵物識別上。在過去的半個多世紀里，RFID的發(fā)展經(jīng)歷了從技術探索、試驗研究、商業(yè)應用和標準化建立等幾個重要階段。從現(xiàn)有發(fā)展趨勢看，RHD將構建虛擬世界與物理世界的橋梁。可以預見在不久的將來，RFID技術不僅會在各行各業(yè)被廣泛采用，最終RFID技術還將會與普適計算技術相融合，對人類社會產(chǎn)生深遠影響。

2、RFID系統(tǒng)一般由電子標簽和讀寫器兩個部分組成，讀寫器具有同時讀取多個電子標簽的功能。在多標簽對一個讀寫器的RFID系統(tǒng)中，標簽經(jīng)常會同時向讀寫器傳輸數(shù)據(jù)，這就要求RFID系統(tǒng)建立一種仲裁機制來避免數(shù)據(jù)發(fā)生碰撞?？紤]到電子標簽本身尺寸、能耗的限制，防碰撞機制在保障功能的同時還要求盡量簡單易行，這正是RFID系統(tǒng)設計的挑戰(zhàn)之一。 算法A基于隨機避讓、沖突檢測的原理，使用1個8位寄存器和1個8位隨機數(shù)產(chǎn)生器，最大可以仲裁標簽的數(shù)量只有256個。算法B基于二進制數(shù)的原理，使用1個8位寄存器和1個l位隨機數(shù)產(chǎn)生器，理論上最大可以實現(xiàn)2256個標簽的仲裁。文獻提出了對該算法的一個實現(xiàn)方案，文獻對該算法做

3、了很大改進。算法C類似于算法A，使用1個16位寄存器和16個l位隨機數(shù)產(chǎn)生器，最大可以仲裁標簽的數(shù)量是65536個。本文中，作者提出一種分群避讓、群內沖突檢測的算法和其改進算法，僅需要1個8位寄存器和1個1位隨機數(shù)產(chǎn)生器就可以實現(xiàn)最大1048 576個標簽的仲裁而且碰撞次數(shù)相對干算法B要大大減少。 1 仲裁機制描述 本方法的核心思想是：首先把電子標簽隨機分群，并將群隨機排序以實現(xiàn)群問的隨機避讓，然后在群內進行沖突檢測和標簽的仲裁。實現(xiàn)時標簽僅需一個寄存器：利用其高位存儲群號，低位存儲沖突檢測時退避的步數(shù)，實現(xiàn)極為簡單。下面以8位寄存器為例具體說明本算法的仲裁機制。 當讀寫器初始化標簽時，所有標

4、簽在015之間任選一個整數(shù)存人寄存器高4位(相當于隨機選擇一個群)并把寄存器低4位設為全O，同時產(chǎn)生一個O或l的隨機數(shù)加到寄存器中。如果此時寄存器中的8比特數(shù)為全0則圓傳該標簽的ID(ID是指電子標簽的惟一標識，在不同的編碼系統(tǒng)中有不同的含義)。如果多個標簽同時回傳數(shù)據(jù)，則沖突發(fā)生。發(fā)生沖突后，其他寄存器高4位為O的標簽寄存器中的數(shù)加l，而寄存器中的8比特數(shù)為全0的標簽則再產(chǎn)生一個0或1的隨機數(shù)加到寄存器中。如果寄存器作加法后仍為全零。則繼續(xù)回傳該標簽的ID；如果回傳時不發(fā)生碰撞，則其他寄存器高4位為O的標簽僅把寄存器低4位減1后重復前面的回傳操作。當寄存器高4位全為0的標簽全部回傳完ID，則

5、所有其他標簽把寄存器高4位減1后重復前面的操作。此外依本算法由于所有標簽隨機選擇群，有可能會出現(xiàn)某個群中的標簽數(shù)目過大，使該群中的標簽在仲裁過程中始終發(fā)生碰撞，標簽寄存器始終加1，導致寄存器低4位向高4位進位。進位意味著所有進位的標簽的寄存器低4位清零而高4位加1，這使得這些標簽不再屬于原有的群而歸人到下一個群中，從而優(yōu)化了因隨機選擇而產(chǎn)生的分布不均勻的群標簽數(shù)。 本算法中，標簽最大退讓步數(shù)為24=16步，因此每個群最大能仲裁的標簽數(shù)目為216=65536，則本算法能仲裁的標簽數(shù)理論上限是16×216=1048576。 2 算法步驟 給出算法步驟，假設使用一個8位寄存器，則本算法包括

6、以下步驟： (1)在所述RFID系統(tǒng)的被動方一標簽中設計一個4+4位的寄存器(Rel)和1個“0”、“l(fā)”隨機數(shù)產(chǎn)生器(RGI)，如圖l所示。 (2)在所述RFID系統(tǒng)的主動方一讀寫器向所有處在等待態(tài)的標簽發(fā)送初始化命令。標簽因此進入仲裁態(tài)，用RGI產(chǎn)生4比特隨機數(shù)，加載到Rel高4位R7R4，低4位R3R0全部清零。 (3)讀寫器等待一定時間后發(fā)送允許回傳命令。 (4)Rel為全零的標簽向讀寫器回傳標簽ID。 (5)如果當前只有一個標簽回傳ID，讀寫器正確讀取該ID，則發(fā)送確認命令，附加命令參數(shù)“低位減l”。回傳了ID的標簽接收到該命令后，進入確認態(tài)，其他高4位為全零的標簽Re1低4位減1，

7、回到步驟(4)重復操作。 (6)如果當前有多個標簽回傳ID，讀寫器通過CRC校驗或碼長校驗，檢測到錯誤的ID號，則發(fā)送確認命令，附加命令參數(shù)“寄存器加1”。接收到讀寫器這個命令后，所有在仲裁態(tài)且Rel為全零的標簽由RGI產(chǎn)生1比特隨機數(shù)和寄存器上的數(shù)相加后重新載入到寄存器中；其他仲裁態(tài)且Rel高4位為零而低4位不為零的標簽Rel加1，回到步驟(4)重復操作 (7)如果當前沒有標簽回傳ID，讀寫器等待一定時間后發(fā)送確認命令，附加命令參數(shù)“低位減1”。所有在仲裁態(tài)且高4為全零的標簽Rel低4位減1，回到步驟(4)重復操作。 (8)低4位減1操作重復L次(L是一個系統(tǒng)參數(shù)，由系統(tǒng)設定，經(jīng)驗值為4)后，讀寫器認為所有在仲裁態(tài)且寄存器高4位為零的標簽都已經(jīng)被正確讀取，則發(fā)送確認命令，附加命令參數(shù)“高4位減l”，回到步驟(4)。 (9)標簽接收到附加“高位減l”參數(shù)的確認命令后，所有Rel高4位不為零的標簽高4位減l，回到步驟4重復操作；在被要求高位減1前已為零的標簽則回到等待態(tài)。 (10)重復15次高位減1操作后讀寫器認為所有在仲裁態(tài)的標簽都已經(jīng)被讀取，則仲裁過程停止，所有還處于仲裁態(tài)的標簽返回等待態(tài)。 算法步驟中所述等待態(tài)是指電子標簽上電后的初始狀態(tài)；仲裁態(tài)是指未被讀寫器鑒別的電子標簽開始響應讀寫器鑒別命令時進入的狀態(tài)；確認態(tài)是指已被讀寫器鑒別