RFID 防沖突 算法

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

RFID系統一般由電子標簽和讀寫(xiě)器兩個(gè)部分組成，讀寫(xiě)器具有同時(shí)讀取多個(gè)電子標簽的功能。在多標簽對一個(gè)讀寫(xiě)器的RFID系統中，標簽經(jīng)常會(huì )同時(shí)向讀寫(xiě)器傳輸數據，這就要求RFID系統建立一種仲裁機制來(lái)避免數據發(fā)生碰撞?？紤]到電子標簽本身尺寸、能耗的限制，防碰撞機制在保障功能的同時(shí)還要求盡量簡(jiǎn)單易行，這正是RFID系統設計的挑戰之一。

算法A基于隨機避讓、沖突檢測的原理，使用1個(gè)8位寄存器和1個(gè)8位隨機數產(chǎn)生器，最大可以仲裁標簽的數量只有256個(gè)。算法B基于二進(jìn)制數的原理，使用1個(gè)8位寄存器和1個(gè)l位隨機數產(chǎn)生器，理論上最大可以實(shí)現2256個(gè)標簽的仲裁。文獻提出了對該算法的一個(gè)實(shí)現方案，文獻對該算法做了很大改進(jìn)。算法C類(lèi)似于算法A，使用1個(gè)16位寄存器和16個(gè)l位隨機數產(chǎn)生器，最大可以仲裁標簽的數量是65536個(gè)。本文中，作者提出一種分群避讓、群內沖突檢測的算法和其改進(jìn)算法，僅需要1個(gè)8位寄存器和1個(gè)1位隨機數產(chǎn)生器就可以實(shí)現最大1048 576個(gè)標簽的仲裁．而且碰撞次數相對干算法B要大大減少。

1 仲裁機制描述

本方法的核心思想是：首先把電子標簽隨機分群，并將群隨機排序以實(shí)現群?jiǎn)?wèn)的隨機避讓?zhuān)缓笤谌簝冗M(jìn)行沖突檢測和標簽的仲裁。實(shí)現時(shí)標簽僅需一個(gè)寄存器：利用其高位存儲群號，低位存儲沖突檢測時(shí)退避的步數，實(shí)現極為簡(jiǎn)單。下面以8位寄存器為例具體說(shuō)明本算法的仲裁機制。

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

此外依本算法．由于所有標簽隨機選擇群，有可能會(huì )出現某個(gè)群中的標簽數目過(guò)大，使該群中的標簽在仲裁過(guò)程中始終發(fā)生碰撞，標簽寄存器始終加1，導致寄存器低4位向高4位進(jìn)位。進(jìn)位意味著(zhù)所有進(jìn)位的標簽的寄存器低4位清零而高4位加1，這使得這些標簽不再屬于原有的群而歸人到下一個(gè)群中，從而優(yōu)化了因隨機選擇而產(chǎn)生的分布不均勻的群標簽數。

本算法中，標簽最大退讓步數為24=16步，因此每個(gè)群最大能仲裁的標簽數目為216=65536，則本算法能仲裁的標簽數理論上限是16×216=1048576。

2 算法步驟

給出算法步驟，假設使用一個(gè)8位寄存器，則本算法包括以下步驟：

(1)在所述RFID系統的被動(dòng)方一標簽中設計一個(gè)4+4位的寄存器(Rel)和1個(gè)“0”、“l(fā)”隨機數產(chǎn)生器(RGI)，如圖l所示。
(2)在所述RFID系統的主動(dòng)方一讀寫(xiě)器向所有處在等待態(tài)的標簽發(fā)送初始化命令。標簽因此進(jìn)入仲裁態(tài)，用RGI產(chǎn)生4比特隨機數，加載到Rel高4位R7~R4，低4位R3~R0全部清零。
(3)讀寫(xiě)器等待一定時(shí)間后發(fā)送允許回傳命令。
(4)Rel為全零的標簽向讀寫(xiě)器回傳標簽ID。
(5)如果當前只有一個(gè)標簽回傳ID，讀寫(xiě)器正確讀取該ID，則發(fā)送確認命令，附加命令參數“低位減l”?；貍髁薎D的標簽接收到該命令后，進(jìn)入確認態(tài)，其他高4位為全零的標簽Re1低4位減1，回到步驟(4)重復操作。
(6)如果當前有多個(gè)標簽回傳ID，讀寫(xiě)器通過(guò)CRC校驗或碼長(cháng)校驗，檢測到錯誤的ID號，則發(fā)送確認命令，附加命令參數“寄存器加1”。接收到讀寫(xiě)器這個(gè)命令后，所有在仲裁態(tài)且Rel為全零的標簽由RGI產(chǎn)生1比特隨機數和寄存器上的數相加后重新載入到寄存器中；其他仲裁態(tài)且Rel高4位為零而低4位不為零的標簽Rel加1，回到步驟(4)重復操作
(7)如果當前沒(méi)有標簽回傳ID，讀寫(xiě)器等待一定時(shí)間后發(fā)送確認命令，附加命令參數“低位減1”。所有在仲裁態(tài)且高4為全零的標簽Rel低4位減1，回到步驟(4)重復操作。
(8)低4位減1操作重復L次(L是一個(gè)系統參數，由系統設定，經(jīng)驗值為4)后，讀寫(xiě)器認為所有在仲裁態(tài)且寄存器高4位為零的標簽都已經(jīng)被正確讀取，則發(fā)送確認命令，附加命令參數“高4位減l”，回到步驟(4)。
(9)標簽接收到附加“高位減l”參數的確認命令后，所有Rel高4位不為零的標簽高4位減l，回到步驟4重復操作；在被要求高位減1前已為零的標簽則回到等待態(tài)。
(10)重復15次高位減1操作后．讀寫(xiě)器認為所有在仲裁態(tài)的標簽都已經(jīng)被讀取，則仲裁過(guò)程停止，所有還處于仲裁態(tài)的標簽返回等待態(tài)。

算法步驟中所述等待態(tài)是指電子標簽上電后的初始狀態(tài)；仲裁態(tài)是指未被讀寫(xiě)器鑒別的電子標簽開(kāi)始響應讀寫(xiě)器鑒別命令時(shí)進(jìn)入的狀態(tài)；確認態(tài)是指已被讀寫(xiě)器鑒別的電子標簽進(jìn)入的狀態(tài)。電子標簽狀態(tài)轉移規則如下：上電后電子標簽進(jìn)入等待態(tài)；處于等待態(tài)的電子標簽可以進(jìn)入仲裁態(tài)；處于仲裁態(tài)的電子標簽可以返回等待態(tài)；處于仲裁態(tài)的電子標簽可以進(jìn)入確認態(tài)；處于確認態(tài)的電子標簽不能返回仲裁態(tài)；確認態(tài)與等待態(tài)之間不能直接轉移。

針對上述算法步驟，在以下幾個(gè)地方加以改進(jìn)，形成本算法的改進(jìn)算法。
A、步驟(1)中，隨機數產(chǎn)生器產(chǎn)生兩組隨機數，分別加載到寄存器高位和低4位。其中高位加載的位數M可以動(dòng)態(tài)設為1、2、3或4。

B、步驟(10)中的重復操作次數為2M次。因為改進(jìn)算法在寄存器低4位也加載了隨機數，使得標簽在群間轉移的概率(即低4位向高位進(jìn)位的概率)大大增加，特別如果最后一個(gè)群中標簽的寄存器低4位在退讓步驟中進(jìn)位，則會(huì )產(chǎn)生一個(gè)新群，因此需要額外增加一次高位減l操作。

3 電路實(shí)現

算法實(shí)現的參考電路框圖見(jiàn)圖l，其中RGI是一個(gè)“0”“1”隨機數產(chǎn)生器；Rel是一個(gè)8位寄存器。加法器ADDl和ADD2的加減功能根據讀寫(xiě)器命令來(lái)設定：當執行加法操作時(shí)，低4位的ADD2需向高4位的ADDl進(jìn)位；當執行減法操作時(shí)，兩個(gè)器件ADDl和ADD2相互獨立。加法器可以工作在同步狀態(tài)或異步狀態(tài)，工作在同步狀態(tài)時(shí)可以使用電子標簽的最大時(shí)鐘。

4 仿真結果

仿真l：為了評估本算法的優(yōu)劣，特設計以下仿真：標簽使用8位寄存器，高4位為高位。定義0個(gè)、2個(gè)和2個(gè)以上的標簽同時(shí)發(fā)送數據時(shí)為傳輸沖突；只有一個(gè)標簽發(fā)送數據時(shí)為傳輸成功，平均沖突次數定義為傳輸沖突總次數和傳輸成功總次數的比；空傳率定義O個(gè)標簽發(fā)送數據的次數與傳輸成功總次數的比。觀(guān)察標簽數為20~10000時(shí)的平均沖突次數。

仿真結果如圖2所示，本文提出的算法與二進(jìn)制算法性能接近，平均每成功傳輸1次都要伴隨2次傳輸沖突；而改進(jìn)算法則在標簽數為50~5000個(gè)時(shí)明顯減少了碰撞次數。同時(shí)也注意到當標簽個(gè)數少于50時(shí)，改進(jìn)算法性能下降，這是因為此時(shí)標簽數接近分群的群數導致空傳率上升所致，解決的辦法是減少分群的群數。針對該問(wèn)題，特設計仿真2來(lái)分析。

仿真2：為了分析低標簽密度時(shí)改進(jìn)算法的性能，特設計以下仿真：采用改進(jìn)算法，分別使用5~8位寄存器。高l~4位為高位，即分群群數分別為2、4、8和16。仿真結果如圖3所示，可以看到當標簽總數為20時(shí)，如果把高位寄存器的位數從4降到l，則平均碰撞次數從5 5回落到1．4。而當標簽總數為200和2000時(shí)，高位寄存器位數的改變對平均碰撞次數的影響不大。因此如果在某次仲裁中出現多次空傳，根據這個(gè)先驗知識，讀寫(xiě)器可以在下一次仲裁時(shí)指示標簽改變寄存器高位個(gè)數，以此降低空傳率，進(jìn)而可以降低平均碰撞次數。

本文提出的防碰撞算法僅需在電子標簽中配置1個(gè)8位寄存器、1個(gè)l位“O”