一種新穎的RFID防沖突算法

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

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

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

1 仲裁機(jī)制描述

本方法的核心思想是：首先把電子標(biāo)簽隨機(jī)分群，并將群隨機(jī)排序以實(shí)現(xiàn)群問的隨機(jī)避讓，然后在群內(nèi)進(jìn)行沖突檢測(cè)和標(biāo)簽的仲裁。實(shí)現(xiàn)時(shí)標(biāo)簽僅需一個(gè)寄存器：利用其高位存儲(chǔ)群號(hào)，低位存儲(chǔ)沖突檢測(cè)時(shí)退避的步數(shù)，實(shí)現(xiàn)極為簡單。下面以8位寄存器為例具體說明本算法的仲裁機(jī)制。

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

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

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