陳鴻俊

（四川水利職業(yè)技術(shù)學(xué)院）

RFID多標(biāo)簽識(shí)別防碰撞算法的研究與分析

陳鴻俊

（四川水利職業(yè)技術(shù)學(xué)院）

無線射頻識(shí)別技術(shù)是一種非接觸的自動(dòng)識(shí)別技術(shù)，具有識(shí)別距離遠(yuǎn)、穿透能力強(qiáng)、多物體識(shí)別等優(yōu)點(diǎn)，現(xiàn)已廣泛應(yīng)用于自動(dòng)化、交通運(yùn)輸、控制管理、產(chǎn)品服務(wù)、證件防偽等領(lǐng)域。RFID 系統(tǒng)由于信號(hào)在無線信道中相互干擾，就會(huì)發(fā)生沖突或碰撞，致使標(biāo)簽識(shí)別或數(shù)據(jù)采集失敗，這就需要建立有效的防碰撞機(jī)制，即防碰撞算法或防碰撞協(xié)議，來協(xié)調(diào)標(biāo)簽與閱讀器間的通信。

RFID;防碰撞算法;二叉樹搜索;ALOHA

1 無線射頻識(shí)別技術(shù)

無線射頻識(shí)別技術(shù) 屬于新近出現(xiàn)的先進(jìn)無線通信技術(shù)，能夠在無線電訊號(hào)下，對(duì)目標(biāo)進(jìn)行特定性識(shí)別，并對(duì)目標(biāo)數(shù)據(jù)進(jìn)行自動(dòng)讀寫。這種技術(shù)在上世紀(jì)末開始興起，技術(shù)最大的特點(diǎn)是非接觸性。這種RFID信號(hào)可以使電磁場(chǎng)中的無線電頻率有效調(diào)節(jié)，因此在擁有此頻率的電磁場(chǎng)中，能夠?qū)⑿畔?shù)據(jù)通過粘貼的標(biāo)簽傳送到相應(yīng)閱讀器，從而實(shí)現(xiàn)對(duì)物品的自動(dòng)識(shí)別及追蹤。某些標(biāo)簽在識(shí)別過程中可以在閱讀器發(fā)出的電磁場(chǎng)中獲得能量，不需要額外的電池支持；還有些標(biāo)簽本身就包含電源，能夠自主進(jìn)行無線電信號(hào)的發(fā)送。一般來說，閱讀器在數(shù)米之內(nèi)所接收到的電子標(biāo)簽存儲(chǔ)信息都能進(jìn)行識(shí)別。

目前常用的自動(dòng)識(shí)別技術(shù)中，條碼技術(shù)和磁卡技術(shù)所涉及設(shè)備成本較低、操作簡單、數(shù)據(jù)采集速度快、可靠性高靈活實(shí)用，只是數(shù)據(jù)存儲(chǔ)量不大，抗磨損性差。IC卡數(shù)據(jù)存儲(chǔ)量大，安全保密性好，每次修改都需要輸入密碼，重量不大，便于攜帶，但是使用壽命也不高。而當(dāng)前的射頻卡操作便捷，能遠(yuǎn)程操作，可以穿透很厚障礙，不會(huì)產(chǎn)生機(jī)械磨損，擁有較長使用壽命。同時(shí)射頻識(shí)別還有良好的抗干擾能力，耐久性強(qiáng)，對(duì)環(huán)境要求不高，在各種環(huán)境下都能夠正常工作，且射頻識(shí)別對(duì)視線范圍沒有局限，在識(shí)別的有效距離上遠(yuǎn)高于當(dāng)前的光學(xué)系統(tǒng)。由于無線射頻識(shí)別技術(shù)能輕松的免除在物體跟蹤過程中由于人為干預(yù)出現(xiàn)的錯(cuò)誤，因此該技術(shù)能大大簡化在物流、運(yùn)輸及商品供應(yīng)鏈中的產(chǎn)品跟蹤管理，能快速、有效地滿足當(dāng)前信息處理量的不斷增長的需求。在物流行業(yè)高速發(fā)展的今天，該項(xiàng)技術(shù)正以其獨(dú)特的優(yōu)勢(shì)，成為大家所關(guān)注的熱點(diǎn)之一。

2 無線射頻識(shí)別技術(shù)的發(fā)展

RFID技術(shù)最早使用在第二次世界大戰(zhàn)中，在這場(chǎng)戰(zhàn)役中，各國的空軍就是用此技術(shù)來實(shí)現(xiàn)彼此間的相互識(shí)別的。1948年奠定了RFID技術(shù)的理論基礎(chǔ)；1950年以后各國對(duì)RFID技術(shù)開始通過實(shí)驗(yàn)室研究進(jìn)行有效探索；1960年之后，在各種研究基礎(chǔ)上，RFID技術(shù)已經(jīng)得到進(jìn)一步發(fā)展，人們通過設(shè)計(jì)一些諸如電子商品監(jiān)視設(shè)備這樣的簡單商用RFID系統(tǒng)，將此技術(shù)做了程序上的應(yīng)用嘗試；1980年后，RFID技術(shù)在各種應(yīng)用系統(tǒng)中嘗試應(yīng)用，使RFID技術(shù)在各個(gè)行業(yè)得到了開發(fā)及應(yīng)用；過去十年中，人們對(duì)產(chǎn)品標(biāo)準(zhǔn)化不斷關(guān)注，并且伴隨科技經(jīng)濟(jì)的飛速發(fā)展，RFID產(chǎn)品的種類更為豐富齊全，各種類型的標(biāo)簽技術(shù)應(yīng)運(yùn)而生，有效地降低了電子標(biāo)簽的成本。

RFID系統(tǒng)有三部分組成，分別為：閱讀器（ Reader）、標(biāo)簽（ Tag）及數(shù)據(jù)處理系統(tǒng)。標(biāo)簽可以對(duì)所標(biāo)識(shí)物品的身份和屬性信息進(jìn)行有效存儲(chǔ)，閱讀器作為信息采集終端，利用射頻信號(hào)對(duì)標(biāo)簽進(jìn)行識(shí)別，并與數(shù)據(jù)處理系統(tǒng)進(jìn)行通信。鑒于閱讀器同所有待識(shí)別的標(biāo)簽間的溝通是通過無線信道所進(jìn)行的，當(dāng)多個(gè)待識(shí)別標(biāo)簽共同與閱讀器通信，此時(shí)信號(hào)之間會(huì)互相碰撞，標(biāo)簽間信號(hào)出現(xiàn)沖突，不能被準(zhǔn)確識(shí)別，通信數(shù)據(jù)傳送失敗，這就形成了標(biāo)簽沖突( tag collision)。這時(shí)就需要我們采用適當(dāng)方法對(duì)多標(biāo)簽識(shí)別沖突有效解決，一般我們是通過防碰撞算法來解決這類問題的。而這種防碰撞算法當(dāng)前已經(jīng)成為多標(biāo)簽識(shí)別中最主要的一個(gè)研究熱點(diǎn)。在應(yīng)用中我們多通過防碰撞速度，識(shí)別準(zhǔn)確率，信道利用率高低，技術(shù)成本及安全性，還有技術(shù)應(yīng)用中的穩(wěn)定性幾個(gè)指標(biāo)來判斷防碰撞算法的優(yōu)劣。

3 國內(nèi)外關(guān)于防碰撞算法的研究

RFID系統(tǒng)中所使用的防碰撞方法主要有4種，分別是：TDMA（時(shí)分多路法）、FDMA（頻分多路法）、SDMA（空分多路法）、及CDMA（碼分多路法）。其中時(shí)分多路方法在RFID系統(tǒng)中應(yīng)用最為廣泛，而二進(jìn)制樹搜索算法(Binary Tree-Scanning)還有ALOHA算法則是RFID系統(tǒng)中使用頻率最多的算法。

近年來，我國國內(nèi)關(guān)于RFID 技術(shù)及防碰撞算法的研究也如雨后春筍般展開。很多學(xué)者專家對(duì)防碰撞算法依據(jù)使用環(huán)境進(jìn)行了改良，讓RFID系統(tǒng)在實(shí)際環(huán)境中的應(yīng)用效率大大提高。在文獻(xiàn)[5]中，研究者將矩陣搜索算法應(yīng)用于生產(chǎn)領(lǐng)域，這是防碰撞算法在生產(chǎn)領(lǐng)域的有效改良。這種算法可以對(duì)多種標(biāo)簽的數(shù)據(jù)請(qǐng)求信息所形成的信息數(shù)據(jù)進(jìn)行同時(shí)響應(yīng)，避免信息碰撞矩陣的出現(xiàn)，使二叉樹搜索算法中逐位搜索的方法得到了改善，有效提高了工作效率。并且這種算法下，依據(jù)碰撞堆棧理念，能夠?qū)λ阉魍緩阶园l(fā)動(dòng)態(tài)調(diào)整，這樣就能夠使標(biāo)簽碰撞次數(shù)還有傳輸中空閑時(shí)隙數(shù)有效減少，使搜索效率大大提高[5]。在文獻(xiàn)[6]中，研究者在防碰撞算應(yīng)用中提出要降低空時(shí)隙的開銷，并據(jù)此制定出專門算法。這種算法可以對(duì)命令幀中空時(shí)隙的位置在識(shí)別前先行掃描，對(duì)標(biāo)簽數(shù)量進(jìn)行估算，并據(jù)此動(dòng)態(tài)調(diào)整命令幀的長度，以減少空時(shí)隙的時(shí)間浪費(fèi)，達(dá)到提高系統(tǒng)讀取效率的目的。

4 防碰撞算法存在問題分析

目前RFID 防碰撞算法主要還存在如下一些問題：

（1）基于ALOHA 的防碰撞算法采用隨機(jī)申請(qǐng)時(shí)隙的方法，不能保證標(biāo)簽的完全識(shí)別，不能避免標(biāo)簽饑餓（tag starvation）現(xiàn)象，即存在標(biāo)簽長期或一直不能被成功識(shí)別的現(xiàn)象，而且隨著待識(shí)別標(biāo)簽數(shù)量的增加，算法性能急劇下降。

（2）這些算法不能消除識(shí)別過程中的空閑周期或時(shí)隙（idle cycle），即這些周期或時(shí)隙中沒有任何標(biāo)簽響應(yīng)閱讀器的質(zhì)詢（Query）,造成不必要的時(shí)空開銷和能量消耗，影響標(biāo)簽的識(shí)別速度。

（3）算法識(shí)別效率較低，ISO/IEC 18000 系列標(biāo)準(zhǔn)推薦使用的QT、BS、S-ALOHA 和DS-ALOHA 等算法的識(shí)別效率一般情況下在34%左右，眾多新算法或改進(jìn)算法性能也低于50%，且算法較為復(fù)雜，難以付諸實(shí)際應(yīng)用，因此，不能滿足現(xiàn)實(shí)應(yīng)用的需求。

（4）算法穩(wěn)定性較差，隨著待識(shí)別標(biāo)簽的數(shù)量和標(biāo)簽編號(hào)的分布情況不同，算法的識(shí)別性能差異很多大，不便于計(jì)算完成一批標(biāo)簽識(shí)別的準(zhǔn)確時(shí)間，這給RFID 在流水生產(chǎn)或?qū)崟r(shí)數(shù)據(jù)采集等方面的應(yīng)用造成困難。

（5）算法僅考慮或假設(shè)標(biāo)簽編號(hào)成均勻分布狀態(tài)，而在實(shí)際應(yīng)用中其它分布狀況也大量存在，如集裝箱碼頭、大型貨艙等場(chǎng)合，均需要對(duì)同一廠家或類型的批量商品進(jìn)行快速準(zhǔn)確的識(shí)別檢測(cè)，而這時(shí)的標(biāo)簽編號(hào)通常為連續(xù)分布方式。

5 防碰撞算法的發(fā)展趨勢(shì)和展望

標(biāo)簽沖突是RFID 應(yīng)用系統(tǒng)中的關(guān)鍵問題之一。通過對(duì)ALOHA 法和二進(jìn)制樹搜索算法以及在此基礎(chǔ)上發(fā)展起來的其他一些比較重要的防碰撞算法的分析比較, 可以看出:

(1) ALOHA 算法實(shí)現(xiàn)較簡單, 但是存在錯(cuò)誤判決問題, 其信道利用率最大為36%, 在標(biāo)簽數(shù)目不大的場(chǎng)合, 可以用到時(shí)隙ALOHA 法和DFSA 算法。

(2) 二進(jìn)制樹算法識(shí)別率高, 信道利用率可達(dá)43%, 不存在錯(cuò)誤判別問題, 適用于標(biāo)簽數(shù)目較大的場(chǎng)合。

(3) ALOHA 法只適于中低頻被動(dòng)式只讀電子標(biāo)簽, 如校園一卡通; 而高頻和微波系統(tǒng)則多用二進(jìn)制搜索。但是采用二進(jìn)制樹算法時(shí)延長, 泄露的信息較多, 安全性較差。在設(shè)計(jì)系統(tǒng)時(shí)要根據(jù)系統(tǒng)的應(yīng)用場(chǎng)合選擇合適的防沖突算法。

考慮到兩類算法各具優(yōu)點(diǎn), 有人考慮將二者結(jié)合起來得出新算法;也有人提出采用碼分多址和空分多址的方法,通過為每個(gè)標(biāo)簽分配不同的PN 碼來避免沖突, 空分多址通常是將標(biāo)簽定位達(dá)到隔離和識(shí)別的目的。這種方法可通過改變讀寫器的閱讀范圍或使用智能天線來實(shí)現(xiàn)。這兩種方法能大大提高RFID 系統(tǒng)的防沖突能力, 但系統(tǒng)設(shè)計(jì)較為復(fù)雜, 標(biāo)簽的成本較高, 其主要適于超高頻和微波等寬帶應(yīng)用場(chǎng)景。以上各種方法都有待進(jìn)一步研究。

從RFID 應(yīng)用的角度來看, 目前的防碰撞算法的識(shí)別率、識(shí)別速度、信道利用率都有待提高, 識(shí)別過程較復(fù)雜, 對(duì)安全和個(gè)人隱私等問題考慮不周, 這些問題都有待進(jìn)一步研究和改進(jìn), 以適應(yīng)高速運(yùn)動(dòng)、多目標(biāo)識(shí)別復(fù)雜系統(tǒng)的應(yīng)用。

[1] Rao,K.V.S. An overview of backscattered radio frequency identification system(RFID)[J]．Microwave Conference,1999,3: 746—749.

[2] K.Finkenzeller. RFID Handbook[M]. 第四版.北京:北京大學(xué)出版社, 2 0 0 3. 206-219.

[3] 高樂. RFID技術(shù)中的防碰撞算法研究[D]. 成都:電子科技大學(xué)，2006.2

[4] 陳飛宇. 基于動(dòng)態(tài)二進(jìn)制RFID防碰撞算法的改進(jìn)[D]. 上海:上海交通大學(xué), 2011.6.

[5] 丁治國,郭立,劉琦. 一種基于搜索矩陣的自適應(yīng)防碰撞算法[J]. 模式識(shí)別與人工智能,2008,21(4): 476-481.

[6] 王中祥,王俊宇,劉丹,閔昊. 一種降低空時(shí)隙開銷的RFID防碰撞算法[J]. 通信學(xué)報(bào),2009,30(9): 1-6.

[7] M.A. Bonuccelli, F. Lonetti and F. Martelli, Instant collision resolution for tagidentification in RFID networks, Elsevier, Ad Hoc Networks, vol.5, no.8, pp.1220-1232,2007.

[8] J.Choi and W.Lee, Comparative evaluation of probabilistic and deterministic taganti-collision protocols for RFID networks, EUC Workshops, pp.538-549, 2007.

[9] D.H.Shih, P.L.Sun, D.C.Yen and S.M.Huang, “Taxonomy and survey of RFID anti-collision protocols,” Computer Communications, vol. 29, no.11, pp.2150-2166,July 2006

[10] 聶賽如,劉有源. RFID 防碰撞算法研究現(xiàn)狀與發(fā)展趨勢(shì)綜述. 技術(shù)與方法,2008.3

陳鴻俊（1981-），四川成都人，四川水利職業(yè)技術(shù)學(xué)院，講師，主要從事計(jì)算機(jī)應(yīng)用技術(shù)研究。

Research and analysis of RFID multi tag identification anti collision algorithm

Chen Hongjun
(Sichuan Water Conservancy vocational College)

Wireless radio frequency identification technology is a non-contact automatic identification technology,which has many advantages,such as high identification distance,penetrating ability,multi object recognition,etc.,has been widely used in the field of automation,transportation, control management,product service,document security and other fields. Because of the interference of the signal in wireless channel,the RFID system has a collision or collision, which leads to the failure of tag identification or data acquisition,which requires the establishment of an effective collision avoidance mechanism,i.e.,anti collision algorithm or anti collision protocol,to coordinate the communication between the tag and the reader.At present,the research of RFID anti collision algorithm is mainly focused on the Aloha slot collision avoidance algorithm and the two fork tree search anti collision algorithm. However, the Aloha time slot collision avoidance algorithm has the phenomenon that a tag is not recognized. Two binary tree search algorithm can avoid this problem, but when the number of tags is large,the identification period is long, which affects the efficiency of RFID reader.

RFID;anti collision algorithm;two fork tree search;ALOHA

項(xiàng)目編號(hào)是:四川科技廳項(xiàng)目編號(hào)2012GZ0112。

目前，RFID防碰撞算法的研究主要集中在Aloha時(shí)隙防碰撞算法和二叉樹搜索防碰撞算法。但Aloha時(shí)隙防碰撞算法存在某個(gè)標(biāo)簽始終無法被識(shí)別的現(xiàn)象；二叉樹搜索算法可以避免這個(gè)問題，但當(dāng)標(biāo)簽數(shù)量比較大時(shí)，識(shí)別周期長，影響了RFID讀寫器的效率。