一種新穎的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