1、引言

RFID射頻識(shí)別是一種非接觸式的自動(dòng)識(shí)別技術(shù)，它通過(guò)射頻信號(hào)自動(dòng)識(shí)別目標(biāo)對(duì)象并獲取相關(guān)數(shù)據(jù)。典型的RFID系統(tǒng)主要包括兩部分：讀寫器(Reader) 和標(biāo)簽(Tag)。

在射頻識(shí)別系統(tǒng)工作時(shí)，在讀寫器的作用范圍內(nèi)，可能會(huì)有多個(gè)應(yīng)答器（標(biāo)簽）存在，這些應(yīng)答器的數(shù)據(jù)同時(shí)傳送到讀寫器時(shí)出現(xiàn)沖突即數(shù)據(jù)碰撞，導(dǎo)致讀寫器無(wú)法讀出數(shù)據(jù)?，F(xiàn)階段RFID系統(tǒng)應(yīng)用中，基于TDMA的防碰撞算法目前有兩種:基于比特位的二進(jìn)制搜索算法和基于時(shí)隙的ALOHA 算法。二進(jìn)制搜索算法需要閱讀器能夠確定碰撞的準(zhǔn)確的比特位置,這就需要閱讀器對(duì)所有標(biāo)簽的準(zhǔn)確的同步,而這種同步在實(shí)現(xiàn)時(shí)是困難的；ALOHA算法在應(yīng)用中隨著標(biāo)簽數(shù)量的擴(kuò)大,性能將急劇惡化^[2]。因此,本文提出了一種改進(jìn)的基于時(shí)隙ALOHA的防碰撞算法, 通過(guò)限制響應(yīng)標(biāo)簽的數(shù)量，降低了沖突發(fā)生的可能性，提高了標(biāo)簽的識(shí)別效率，有效解決了ALOHA算法的這方面的局限性。

2、現(xiàn)有的ALOHA防碰撞算法^[3]

2.1 純ALOHA（pure-ALOHA）

ALOHA是多路存取中最簡(jiǎn)單的方法，它是一種隨機(jī)接入算法，這種算法多采取“標(biāo)簽先發(fā)言”的方式，即標(biāo)簽進(jìn)入讀寫器的閱讀區(qū)域就自動(dòng)向讀寫器發(fā)送其自身的ID，隨即標(biāo)簽和讀寫器間開(kāi)始通信。在標(biāo)簽發(fā)送數(shù)據(jù)的過(guò)程中，若有其他標(biāo)簽也在發(fā)送數(shù)據(jù)，那么發(fā)生信號(hào)重疊從而導(dǎo)致完全沖突或部分沖突。讀寫器檢測(cè)接收到的信號(hào)來(lái)判斷有無(wú)沖突。一旦發(fā)生沖突，讀寫器就發(fā)送命令讓標(biāo)簽停止發(fā)送，隨機(jī)等待一段時(shí)間后再重新發(fā)送以減少?zèng)_突。

純ALOHA存在的一個(gè)嚴(yán)重問(wèn)題是數(shù)據(jù)幀F(xiàn)的發(fā)送過(guò)程中，沖突發(fā)生的概率很大，其沖突期為2F。理論上，純ALOHA算法的信道最大利用率只有18.4%。此外，RFID系統(tǒng)中標(biāo)簽不具有載波監(jiān)聽(tīng)發(fā)現(xiàn)沖突的能力，只能通過(guò)接收讀寫器的命令來(lái)判斷有無(wú)沖突。

2.2 時(shí)隙ALOHA（Slotted-ALOHA）

Slotted-ALOHA算法是在純ALOHA算法的基礎(chǔ)上把時(shí)間分成多個(gè)離散時(shí)隙，標(biāo)簽只能在每個(gè)時(shí)隙的分界處才能發(fā)送數(shù)據(jù)。這樣標(biāo)簽或成功發(fā)送或完全沖突，避免了純ALOHA算法中的部分沖突，使沖突期減少一半，提高了信道的利用率，達(dá)到36.8%，使純ALOHA算法的兩倍。但是這種方法需要一個(gè)同步時(shí)鐘，使得讀寫器閱讀區(qū)域內(nèi)所有標(biāo)簽的時(shí)隙同步。

2.3 幀-時(shí)隙ALOHA（Framed-Slotted ALOHA）

Frame-Slotted ALOHA算法是在時(shí)隙ALOHA算法的基礎(chǔ)上把N個(gè)時(shí)隙組成一幀，標(biāo)簽在每個(gè)幀內(nèi)隨機(jī)選擇一個(gè)時(shí)隙發(fā)送數(shù)據(jù)。

3、改進(jìn)算法

胡建赟等人^[4]在分析RFID系統(tǒng)識(shí)別過(guò)程后，在固定時(shí)隙數(shù)量，不同數(shù)量應(yīng)答器的情況下，將時(shí)隙的數(shù)量固定在25個(gè)，應(yīng)答器的最大數(shù)量設(shè)為30個(gè)，得到了在25個(gè)時(shí)隙數(shù)時(shí)，系統(tǒng)中標(biāo)簽數(shù)量大于一幀所含的時(shí)隙數(shù)時(shí)，識(shí)別成功率急速下降的結(jié)果。因此，本文提出的算法，通過(guò)制定一定的規(guī)則來(lái)限制響應(yīng)閱讀器請(qǐng)求命令的標(biāo)簽數(shù)量，以達(dá)到提高閱讀器的識(shí)別效率，降低識(shí)別所有標(biāo)簽所使用的時(shí)隙數(shù)的目的。

本文算法通過(guò)比較標(biāo)簽序列號(hào)的一部分比特位，以限制響應(yīng)請(qǐng)求命令的標(biāo)簽數(shù)。閱讀器向標(biāo)簽發(fā)送比較的開(kāi)始位、比較位的長(zhǎng)度和比較的基準(zhǔn)值。標(biāo)簽收到這些數(shù)據(jù)后，將自己的部分序列號(hào)與規(guī)定的比較基準(zhǔn)值相比較，若小于基準(zhǔn)值，則該標(biāo)簽響應(yīng)閱讀器。例如，假設(shè)標(biāo)簽的序列號(hào)為8位二進(jìn)制數(shù)，比較的開(kāi)始位是比特位5，比較位的長(zhǎng)度是3，比較的基準(zhǔn)值是100₂。如有一標(biāo)簽A的序列號(hào)為10011101₂，根據(jù)以上的比較信息，可知該標(biāo)簽用來(lái)比較的序列號(hào)部分為“011₂”，小于比較基準(zhǔn)值100₂，則標(biāo)簽A響應(yīng)閱讀器。若另有一標(biāo)簽B的序列號(hào)為01101001₂，易知，該標(biāo)簽將不響應(yīng)閱讀器。

閱讀器的識(shí)別成功率在標(biāo)簽數(shù)大于一幀所含時(shí)隙數(shù)時(shí)，大幅降低，所以，本文提出的算法并不是在任何時(shí)候都需要使用的。限制該算法使用的條件是發(fā)生沖突的標(biāo)簽數(shù)與發(fā)送的標(biāo)簽數(shù)的比率。如果，該比率大于參考值，則采用本文提出的算法，否則，所有的標(biāo)簽都響應(yīng)閱讀器。Tae-Wook Hwang等人^[5]提出過(guò)以上類似的算法，他采用的比率概念是發(fā)生沖突的時(shí)隙數(shù)與一幀所含時(shí)隙數(shù)的比值，但本算法采用了完全不一樣的比率概念。仿真結(jié)果顯示，采用本文的比率概念后，所使用的時(shí)隙數(shù)比Tae-Wook Hwang等人的時(shí)隙數(shù)降低了將近20%。

式1表達(dá)了本算法中比率概念及比率與參考值之間的關(guān)系。

R=C/T≥γ                           （1）

其中，C是發(fā)生沖突的標(biāo)簽數(shù),T是發(fā)送的標(biāo)簽數(shù)，γ是參考值，它決定了是否采用本文提出的算法來(lái)限制響應(yīng)閱讀器的標(biāo)簽數(shù)量。圖1所示的為算法流程圖。

圖1本文提出的算法的流程圖     

4、仿真結(jié)果分析

在仿真過(guò)程中，設(shè)定了一幀所含的時(shí)隙數(shù)是256，比較位的長(zhǎng)度是3，比較的基準(zhǔn)值是100₂，每次比較的開(kāi)始位隨機(jī)產(chǎn)生。當(dāng)R值大于等于γ時(shí)，采用本文提出的算法，限制響應(yīng)閱讀器的標(biāo)簽數(shù)；R值小于γ時(shí)，所有標(biāo)簽響應(yīng)閱讀器。在以上的條件下，本仿真實(shí)驗(yàn)考察了γ在取不同值時(shí)，標(biāo)簽數(shù)從1逐漸增加到1000，閱讀器識(shí)別所有標(biāo)簽所使用的時(shí)隙數(shù)的情況。表1所示的為仿真實(shí)驗(yàn)中的參數(shù)的取值情況。其中S_0.5 ~ S₁為仿真結(jié)果圖中不同參數(shù)下縱坐標(biāo)對(duì)應(yīng)的值。

表1 仿真試驗(yàn)中的參數(shù)       

在第一個(gè)仿真中，γ（gamma）值分別取了：0.5、0.6、0.7、0.8、0.9、1，由式（1）可知，R的值必定是小于等于1的，當(dāng)R等于1的時(shí)候，說(shuō)明所有標(biāo)簽都發(fā)生沖突，這種概率在實(shí)際情況下是很小的。從圖1的流程圖可知，當(dāng)閱讀器計(jì)算得到R的值大于等于γ（gamma）時(shí)，將采用本文提出的算法，所以當(dāng)γ（gamma）=1的時(shí)候，是永遠(yuǎn)不會(huì)采用到本文提出的算法，也就是說(shuō)，閱讀器在識(shí)別標(biāo)簽的過(guò)程中，沒(méi)有使用本文的算法，即γ（gamma）=1的曲線對(duì)應(yīng)的是普通算法情況下，閱讀器識(shí)別所有標(biāo)簽所使用的時(shí)隙數(shù)。γ（gamma）分別取值0.5、0.6、0.7、0.8、0.9時(shí)的曲線，對(duì)應(yīng)了使用本文提出的算法時(shí)，閱讀器識(shí)別所有標(biāo)簽所使用的時(shí)隙數(shù)情況。從圖2可以看出，當(dāng)標(biāo)簽數(shù)達(dá)到600個(gè)左右的時(shí)候，普通算法所消耗的時(shí)隙數(shù)急速上升，而本文提出的算法的時(shí)隙數(shù)曲線變化斜率基本保持不變，并且當(dāng)標(biāo)簽數(shù)大于600以后，可以明顯地看出本文提出的算法所使用的時(shí)隙數(shù)比普通算法的時(shí)隙數(shù)少使用了很多，充分體現(xiàn)出本文提出的算法比普通算法優(yōu)越。另外，從圖2也可以看到，當(dāng)γ（gamma）=0.8且擁有大量標(biāo)簽時(shí)，閱讀器識(shí)別所有標(biāo)簽所使用的時(shí)隙數(shù)是最少的。從圖3可以非常明顯的看出，當(dāng)標(biāo)簽數(shù)=990時(shí)，γ（gamma）分別取0.5、0.6、0.7、0.8、0.9、1（普通算法）的情況下，γ（gamma）=0.8時(shí)，使用的時(shí)隙數(shù)最少，比采用普通算法少了大約1300個(gè)，降低了約41%左右。

圖2 γ（gamma）取不同值時(shí)所使用的時(shí)隙數(shù)變化曲線

圖3 標(biāo)簽數(shù)=990時(shí)，γ取不同值時(shí)所使用的時(shí)隙數(shù)比較

在第二個(gè)仿真中，一幀所含的時(shí)隙數(shù)（N）分別取256、128和64，并且在這三種情況下，分別使用了普通算法和本文提出的算法。目的是了解一幀所含時(shí)隙數(shù)的取值情況對(duì)閱讀器識(shí)別標(biāo)簽過(guò)程中使用時(shí)隙數(shù)的影響，同時(shí)觀察本文提出的算法是否優(yōu)越。從圖4可以看出，當(dāng)N=256時(shí)，使用的時(shí)隙數(shù)最少。當(dāng)N=128時(shí)，在標(biāo)簽數(shù)大于300的情況下，應(yīng)用本文提出的算法所使用的時(shí)隙數(shù)曲線的斜率約為5，而普通算法的曲線斜率約達(dá)到47，由此可知，后者的曲線增加速率約為前者的10倍，即所使用的時(shí)隙數(shù)隨著標(biāo)簽數(shù)量的增加，其增加的速率在應(yīng)用普通算法時(shí)約為應(yīng)用本文算法時(shí)的10倍。當(dāng)N=64時(shí)，也可以得到相應(yīng)的比較情況。所以，通過(guò)第二個(gè)仿真試驗(yàn)，驗(yàn)證了本文提出的算法較之普通算法其性能是優(yōu)越的。

圖4 在一幀所含時(shí)隙數(shù)不同的情況下，應(yīng)用本文提出的算法和普通算法時(shí)所使用的時(shí)隙數(shù)的比較

5、結(jié)論

本文作者創(chuàng)新點(diǎn)在于提出一種RFID系統(tǒng)防碰撞改進(jìn)算法，該算法針對(duì)在RFID防碰撞算法中，ALOHA算法在應(yīng)用中有隨著標(biāo)簽數(shù)量的增加,性能急劇惡化的缺點(diǎn)，將沖突發(fā)生的比率與參考值γ相比較后，通過(guò)比較部分標(biāo)簽序列號(hào)的方法，限制響應(yīng)閱讀器的標(biāo)簽數(shù)量，從而提高了識(shí)別標(biāo)簽過(guò)程的性能。一系列的仿真結(jié)果顯示了本文所提出的改進(jìn)算法比普通算法識(shí)別標(biāo)簽所使用的時(shí)隙數(shù)少，性能優(yōu)越。

參考文獻(xiàn)(References)：

1、李寶山，射頻識(shí)別系統(tǒng)防碰撞技術(shù)的研究，包頭鋼鐵學(xué)院學(xué)報(bào)，2005.12

2、陳博，一種類二進(jìn)制搜索的RFID系統(tǒng)反碰撞算法及其實(shí)現(xiàn)，電子器件，2006.3

3、陳香，張思東，薛小平，RFID防碰撞技術(shù)的研究，電腦與電信（PCCom），2006.4

4、胡建赟，李強(qiáng)，閔昊，時(shí)隙ALOHA法在RFID系統(tǒng)防碰撞問(wèn)題中的應(yīng)用，應(yīng)用科學(xué)學(xué)報(bào)，2005.9

5、Tae-Wook Hwang,Byong-Gyo Lee, Young Soo Kim, Doug Young Suh and Jin Sang Kim, Improved Anti-collision Scheme FOR High Speed Identification in RFID System, Proceeding of the First International Conference on Innovative Computing, Information and Control,2006

6、胡圣波，鄭志平。一種井下RFID定位系統(tǒng)的讀卡器防碰撞算法[J]。微計(jì)算機(jī)信息，2006，9-2：185-187