RFID防碰撞算法的研究

秦連芃， 王 喆

（蘭州交通大學(xué)電子與信息工程學(xué)院 蘭州 730070）

0 引言

射頻識(shí)別技術(shù)（Radio Frequency Identification,RFID）是一種非接觸式的自動(dòng)識(shí)別技術(shù)，它通過射頻信號(hào)自動(dòng)識(shí)別目標(biāo)對(duì)象并獲取相關(guān)數(shù)據(jù)，識(shí)別過程無須人工干預(yù)，可工作于各種惡劣的環(huán)境。RFID領(lǐng)域處于物聯(lián)網(wǎng)發(fā)展的最前端，也是實(shí)現(xiàn)物聯(lián)網(wǎng)的基礎(chǔ)技術(shù)之一[1]。

RFID系統(tǒng)主要包括標(biāo)簽（Tag）和讀寫器（Reader）兩部分。標(biāo)簽適用于對(duì)象身份識(shí)別，它的主要模塊集成在一個(gè)芯片中，芯片內(nèi)存用來存儲(chǔ)ID或其他數(shù)據(jù)。讀寫器主要由一個(gè)RF模塊和控制單元組成，通常有內(nèi)置天線，通過射頻信號(hào)與標(biāo)簽通信，標(biāo)簽將自身ID號(hào)發(fā)送給讀寫器，達(dá)到身份識(shí)別的目的。閱讀器作用范圍內(nèi)存在多個(gè)標(biāo)簽，同一時(shí)刻有兩個(gè)或以上的標(biāo)簽向讀寫器返回信息時(shí)，將產(chǎn)生沖突，稱為標(biāo)簽沖突。這個(gè)沖突被稱為碰撞（collision），其結(jié)果將會(huì)導(dǎo)致一次傳輸?shù)氖?。為了解決上述問題而產(chǎn)生了防碰撞算法。

1 防碰撞算法

RFID防碰撞算法在廣義上可分為碼分多址（Code Domain Multiple Access，CDMA）、頻分多址（Frequency Domain Multiple Access，F(xiàn)DMA）、時(shí)分多址（Time Domain Multiple Access，TDMA），以及空分多址（Space Domain Multiple Access，SDMA）4大類。目前在RFID系統(tǒng)中應(yīng)用最多、種類最廣的算法是基于TDMA的防碰撞算法。RFID防碰撞算法又可以分為確定性算法和非確定性算法2大類[2]。如圖1所示。

表1對(duì)非確定性防碰撞算法與確定性防碰撞算法進(jìn)行了比較，列出各自的優(yōu)缺點(diǎn)。

圖1 RFID防碰撞算法分類

表1 非確定性防碰撞算法與確定性防碰撞算法比較

2 非確定性防碰撞算法分析與仿真

非確定性防碰撞算法主要是在Aloha算法基礎(chǔ)上的研究與改進(jìn)，其基本原理是不同標(biāo)簽在不同的時(shí)隙發(fā)送識(shí)別編碼，達(dá)到防碰撞的目的。其中包括純ALOHA算法（Pure ALOHA，PA），時(shí)隙ALOHA算法（Slotted Aloha，SA），幀時(shí)隙ALOHA算法（Frame Slotted Aloha，F(xiàn)SA）及動(dòng)態(tài)幀時(shí)隙ALOHA算法（Dynamic Frame Slotted Aloha，DFSA）。

PA算法是所有多路存取中最簡(jiǎn)單的一種方法，在閱讀器作用范圍內(nèi)的標(biāo)簽隨機(jī)產(chǎn)生應(yīng)答時(shí)間。

SA算法是在PA算法的基礎(chǔ)上，將信道分成若干時(shí)隙，標(biāo)簽只在規(guī)定的同步時(shí)隙內(nèi)傳輸數(shù)據(jù)包，因此沖突只在時(shí)隙邊界處才會(huì)發(fā)生。

FSA算法是在SA算法的基礎(chǔ)上，將多個(gè)時(shí)隙組成一幀，標(biāo)簽在每一幀內(nèi)隨機(jī)選擇一個(gè)時(shí)隙發(fā)送自己的數(shù)據(jù)信息。

DFSA算法通過估算閱讀器作用范圍內(nèi)的標(biāo)簽數(shù)目動(dòng)態(tài)地調(diào)整幀的長(zhǎng)度，以求在減少?zèng)_突標(biāo)簽和避免空閑時(shí)隙之間尋找平衡點(diǎn)。

表2為非確定性防碰撞算法吞吐率計(jì)算公式及最大吞吐率的比較。

表2 非確定性防碰撞算法比較

表2中S為吞吐率，G為輸入負(fù)載即系統(tǒng)交換的數(shù)據(jù)包量，n為讀寫器識(shí)別范圍內(nèi)的標(biāo)簽數(shù)，N為時(shí)隙數(shù)。其中動(dòng)態(tài)幀時(shí)隙ALOHA算法的N是根據(jù)讀寫器識(shí)別范圍內(nèi)的標(biāo)簽數(shù)n不同而變化的。圖2為非確定性防碰撞算法的仿真。

圖2 非確定性防碰撞算法仿真

從圖2中可以看出非確定性防碰撞算法對(duì)系統(tǒng)的利用率不高，理想狀態(tài)下也只能達(dá)到36.8%。

3 確定性防碰撞算法分析與仿真

由于非確定性防碰撞算法無法保證在規(guī)定時(shí)間內(nèi)完成閱讀器作用范圍里所有的標(biāo)簽的辯識(shí)，且信道利用率也較低，因此，對(duì)于希望識(shí)別率達(dá)到100%應(yīng)用，尤其是在超高頻段環(huán)境下，往往采用確定性的防碰撞算法。確定性防碰撞算法主要是基于樹形的算法，包括樹形分裂（Tree splitting，TS）算法、詢問樹（Query Tree，QT）算法、二進(jìn)制搜索（Binary search，BS）算法及按位仲裁（Bit wise arbitration，BTA）算法。

TS算法基本思想是當(dāng)碰撞發(fā)生時(shí)，采用隨機(jī)方式將標(biāo)簽分成若干子組，分組數(shù)目會(huì)不斷增加直到每組內(nèi)僅包含一個(gè)標(biāo)簽。TS算法中的每個(gè)標(biāo)簽都要一個(gè)隨機(jī)數(shù)產(chǎn)生器和一個(gè)計(jì)數(shù)器以追蹤其在樹上的位置，這增加了標(biāo)簽成本及計(jì)算復(fù)雜度。

QT算法則是將所有復(fù)雜運(yùn)算交由閱讀器處理，標(biāo)簽始終處于“無記憶”狀態(tài)，僅需包含一個(gè)前綴匹配電路。該協(xié)議無需時(shí)隙劃分，無須內(nèi)存且能耗很小，但在標(biāo)簽位數(shù)較長(zhǎng)時(shí)搜索范圍很大，因此其應(yīng)用受到一定限制。

在BS算法中，標(biāo)簽的序列號(hào)必須采用曼徹斯特編碼。閱讀器根據(jù)已接收到的來自標(biāo)簽的應(yīng)答，找到碰撞位，并據(jù)此向它們發(fā)送不同的請(qǐng)求信號(hào)或命令，采用二叉樹查找的方法，從作用范圍內(nèi)的標(biāo)簽中篩選出唯一一個(gè)標(biāo)簽進(jìn)行通信。

BTA算法是按位對(duì)標(biāo)簽編碼進(jìn)行詢問，其關(guān)鍵是所有標(biāo)簽同步發(fā)送位信息，當(dāng)閱讀器發(fā)現(xiàn)某一位有多個(gè)標(biāo)簽發(fā)生碰撞，則將從該位入手，對(duì)標(biāo)簽編碼進(jìn)行進(jìn)一步分析。

表3為確定性防碰撞算法的比較。

表3 確定性防碰撞算法比較

表3中mi為第i組的標(biāo)簽數(shù)，n為總標(biāo)簽數(shù)，k為標(biāo)簽長(zhǎng)度。圖3為確定性防碰撞算法的仿真。

圖3 確定性防碰撞算法仿真

從圖3中可以看出確定性防碰撞算法隨著標(biāo)簽數(shù)量的增加，閱讀器對(duì)標(biāo)簽的搜索次數(shù)將急劇增加，這嚴(yán)重影響了讀取速度。

4 結(jié)束語

非確定性防碰撞算法識(shí)別速度快，缺點(diǎn)是識(shí)別率低；確定性防碰撞算法識(shí)別率高，但當(dāng)標(biāo)簽數(shù)量比較大時(shí)識(shí)別速度慢。在實(shí)際應(yīng)用中，RFID系統(tǒng)必須在高誤碼率環(huán)境下，以最快的速度無漏讀地識(shí)別大量標(biāo)簽。這就需要結(jié)合兩種算法的優(yōu)點(diǎn)設(shè)計(jì)一種新的算法，提高RFID系統(tǒng)識(shí)別速度和標(biāo)簽讀取率。

[1]周曉光,王曉華.射頻識(shí)別(RFID)技術(shù)原理與應(yīng)用實(shí)例[M].北京:人民郵電出版社,2006.

[2]譚民,劉禹,曾雋芳,等.RFID技術(shù)系統(tǒng)工程及應(yīng)用指南[M].北京:機(jī)械工業(yè)出版社,2007.

[3]于潔瀟.基于RFID的情境感知關(guān)鍵技術(shù)研究[D].天津:天津大學(xué),2010.

[4]崔沂峰,陳平.RFID電子標(biāo)簽防碰撞算法的研究[J].微計(jì)算機(jī)信息,2007(27):233-244.

[5]張剛建,鄒傳云.RFID系統(tǒng)防碰撞協(xié)議的研究[J].電子技術(shù)應(yīng)用,2010(12).

[6]李寶山,羅春青.RFID防碰撞算法計(jì)算機(jī)仿真模型的研究[J].自動(dòng)化與儀器儀表,2010(05).

[7]中華人民共和國科學(xué)技術(shù)部等十五部委.中國射頻識(shí)別(RFID)技術(shù)政策白皮書[R].北京:中華人民共和國科學(xué)技術(shù)部等十五部委,2006.

[8]EPC global.Electronic product code [OL].http://www.epcglobalinc.org/home/.

[9]ISO.RFID Standards [OL].http://www.iso.org/iso/search.htm?qt=RFID&published=on&active tab=standards.

[10]Dheeraj K.Klair, Kwan-Wu Chin, Raad.A Survey and Tutorial of RFID Anti-Collision Protocols[J].IEEE Communications Surveys&Tutorials,Third Quarter,2010,12(3):400-420.

[11]J.Myung, W.Lee, J.Srivastava.Adaptive binary splitting for efficient RFIDtag anti-collision[J].IEEE Personal Commun.Mag,2006,10(3):144-146.