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

陳鴻俊

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

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

陳鴻俊

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

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

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

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

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

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

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

RFID技術(shù)最早使用在第二次世界大戰(zhàn)中，在這場戰(zhàn)役中，各國的空軍就是用此技術(shù)來實現(xiàn)彼此間的相互識別的。1948年奠定了RFID技術(shù)的理論基礎(chǔ)；1950年以后各國對RFID技術(shù)開始通過實驗室研究進(jìn)行有效探索；1960年之后，在各種研究基礎(chǔ)上，RFID技術(shù)已經(jīng)得到進(jìn)一步發(fā)展，人們通過設(shè)計一些諸如電子商品監(jiān)視設(shè)備這樣的簡單商用RFID系統(tǒng)，將此技術(shù)做了程序上的應(yīng)用嘗試；1980年后，RFID技術(shù)在各種應(yīng)用系統(tǒng)中嘗試應(yīng)用，使RFID技術(shù)在各個行業(yè)得到了開發(fā)及應(yīng)用；過去十年中，人們對產(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)簽可以對所標(biāo)識物品的身份和屬性信息進(jìn)行有效存儲，閱讀器作為信息采集終端，利用射頻信號對標(biāo)簽進(jìn)行識別，并與數(shù)據(jù)處理系統(tǒng)進(jìn)行通信。鑒于閱讀器同所有待識別的標(biāo)簽間的溝通是通過無線信道所進(jìn)行的，當(dāng)多個待識別標(biāo)簽共同與閱讀器通信，此時信號之間會互相碰撞，標(biāo)簽間信號出現(xiàn)沖突，不能被準(zhǔn)確識別，通信數(shù)據(jù)傳送失敗，這就形成了標(biāo)簽沖突( tag collision)。這時就需要我們采用適當(dāng)方法對多標(biāo)簽識別沖突有效解決，一般我們是通過防碰撞算法來解決這類問題的。而這種防碰撞算法當(dāng)前已經(jīng)成為多標(biāo)簽識別中最主要的一個研究熱點。在應(yīng)用中我們多通過防碰撞速度，識別準(zhǔn)確率，信道利用率高低，技術(shù)成本及安全性，還有技術(shù)應(yīng)用中的穩(wěn)定性幾個指標(biāo)來判斷防碰撞算法的優(yōu)劣。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

從RFID 應(yīng)用的角度來看, 目前的防碰撞算法的識別率、識別速度、信道利用率都有待提高, 識別過程較復(fù)雜, 對安全和個人隱私等問題考慮不周, 這些問題都有待進(jìn)一步研究和改進(jìn), 以適應(yīng)高速運(yùn)動、多目標(biāo)識別復(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] 陳飛宇. 基于動態(tài)二進(jìn)制RFID防碰撞算法的改進(jìn)[D]. 上海:上海交通大學(xué), 2011.6.

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

[6] 王中祥,王俊宇,劉丹,閔昊. 一種降低空時隙開銷的RFID防碰撞算法[J]. 通信學(xué)報,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ù)與方法,2008.3

陳鴻?。?981-），四川成都人，四川水利職業(yè)技術(shù)學(xué)院，講師，主要從事計算機(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

項目編號是:四川科技廳項目編號2012GZ0112。

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