張繼榮, 江 馳, 劉亞麗

(西安郵電大學(xué) 通信與信息工程學(xué)院， 陜西 西安 710121)

射頻識別系統(tǒng)多標(biāo)簽防碰撞算法

張繼榮, 江 馳, 劉亞麗

(西安郵電大學(xué) 通信與信息工程學(xué)院， 陜西 西安 710121)

為提升射頻識別(RFID)系統(tǒng)中單閱讀器多標(biāo)簽環(huán)境的識別效率，給出一種在標(biāo)簽編碼前綴相同條件下使用的混合算法。先通過Q算法調(diào)整幀長，使之與待識別標(biāo)簽總數(shù)近似相等，以達(dá)到最大識別效率，并給未識別的碰撞標(biāo)簽標(biāo)記分組號，再對已分組的碰撞標(biāo)簽使用反向查詢樹算法(QTR)一一識別。根據(jù)EPCC1G1標(biāo)準(zhǔn)，在單閱讀器多標(biāo)簽的系統(tǒng)環(huán)境下，選取標(biāo)簽編碼長度為96位，分別在標(biāo)簽編碼完全隨機(jī)與標(biāo)簽編碼前60位相同兩種情況下進(jìn)行仿真，結(jié)果表明在標(biāo)簽編碼前綴相同時，較之QT算法、Q算法，混合算法可提高系統(tǒng)吞吐率，降低閱讀器發(fā)送總時隙數(shù)。

多標(biāo)簽防碰撞；混合算法；反向查詢樹；吞吐率

射頻識別技術(shù)(radio frequency identification, RFID)是一種非接觸式的識別技術(shù)，也被稱為電子標(biāo)簽技術(shù)[1]。RFID系統(tǒng)包括識別目標(biāo)對象的閱讀器以及附著在識別對象上的電子標(biāo)簽。

當(dāng)多個標(biāo)簽在同一時間向閱讀器發(fā)送數(shù)據(jù)時，信號在閱讀器接收端發(fā)生干擾，引起數(shù)據(jù)的碰撞(collison)，這樣就會導(dǎo)致標(biāo)簽識別和數(shù)據(jù)傳送失敗[2]。協(xié)調(diào)標(biāo)簽和閱讀器之間的通信，建立能夠準(zhǔn)確識別多個標(biāo)簽的防碰撞算法是RFID系統(tǒng)付諸于應(yīng)用的關(guān)鍵技術(shù)。

防碰撞算法可以被分為兩大類：基于Aloha協(xié)議的概率性防碰撞算法和基于樹協(xié)議的確定性防碰撞算法。概率性算法有純Aloha算法，時隙Aloha算法、幀時隙Aloha算法(FSA)和動態(tài)幀時隙Aloha算法(DFSA)等[3-5]。確定性算法有查詢樹算法(QT)、二叉樹搜索(BT)和二進(jìn)制搜索算法(BS)等[4-5]。

在實(shí)際應(yīng)用中，概率性算法會出現(xiàn)“標(biāo)簽饑餓”問題，即標(biāo)簽的相互碰撞可能導(dǎo)致某個標(biāo)簽永遠(yuǎn)無法被識別，確定性算法雖然能夠準(zhǔn)確識別出每一個標(biāo)簽，但當(dāng)待識別標(biāo)簽過多時會造成識別時間較長。

在EPC C1G2標(biāo)準(zhǔn)[6]中使用Q算法(Adaptive Slot-Count(Q) algorithm)[7]作為防碰撞算法，該算法通過參數(shù)Q及調(diào)整步長C來自適應(yīng)地調(diào)整幀長以達(dá)到最優(yōu),但該算法對于碰撞的解決機(jī)制不夠完好，頻繁的調(diào)整Q值也增加了系統(tǒng)的通信時間，并且因為屬于概率性算法也會出現(xiàn)“標(biāo)簽饑餓”的問題。

反向查詢樹算法(QTR)是對查詢樹算法(QT)的變型[8],此算法使用閱讀器廣播查詢前綴，標(biāo)簽判斷查詢前綴和自身標(biāo)簽碼的匹配與否來選擇是否發(fā)送自己的數(shù)據(jù)。QTR算法屬于確定性算法實(shí)現(xiàn)簡單，可以排除“標(biāo)簽饑餓”現(xiàn)象，但當(dāng)標(biāo)簽數(shù)量過大時，閱讀器向標(biāo)簽的發(fā)送查詢前綴的次數(shù)過多，會造成樹的深度過大，這樣就延長了識別時間，使得系統(tǒng)效率無法穩(wěn)定維持在較高水平。

本文針對Q算法中Q值改變過多且存在“標(biāo)簽饑餓”的現(xiàn)象,和QTR算法在識別大量標(biāo)簽時效率低下的問題，將Q算法進(jìn)行變型并融合QTR算法提出一種混合算法，即增強(qiáng)型反向查詢樹算法(Enhanced Query tree with Reversed IDs by fast grouping, EQR)，通過設(shè)置邊界條件降低Q值改變次數(shù)，引入QTR算法識別碰撞標(biāo)簽，并使用快速分組的方法將碰撞標(biāo)簽分組，以提高系統(tǒng)效率。

1 增強(qiáng)型反向查詢樹算法

EPC碼是由標(biāo)頭、廠商識別碼、對象分類碼以及序列號所組成[9-10]，當(dāng)廠商申請使用EPC編碼時會獲得全球唯一的廠商識別碼，而對于同類型產(chǎn)品，也具有同樣的對象分類碼,因此，同一廠商物流供應(yīng)鏈上的同類型產(chǎn)品EPC編碼的前綴是相同的。EQR算法僅在編碼前綴相同環(huán)境下使用。

1.1 最佳幀長的判斷

假設(shè)一幀有L個時隙，n個待識別標(biāo)簽。標(biāo)簽在各時隙相互對立地發(fā)送數(shù)據(jù)，即各時隙得到標(biāo)簽的概率相等，故m個標(biāo)簽在某時隙內(nèi)發(fā)送碰撞的概率pm滿足二項分布[11]，即

m個標(biāo)簽在某時隙內(nèi)發(fā)送數(shù)據(jù)的數(shù)學(xué)期望為

在某時隙有且只有一個標(biāo)簽被成功識別的期望是

定義RFID系統(tǒng)的效率公式為

當(dāng)標(biāo)簽數(shù)為n時，為使效率最高，應(yīng)使

由此可以推知，當(dāng)標(biāo)簽數(shù)與時隙數(shù)相同時，系統(tǒng)效率最高。

1.2 邊界條件的設(shè)定

要使得時隙數(shù)L近似等于待識別標(biāo)簽數(shù)n，碰撞時隙數(shù)Nc，空閑時隙數(shù)Ne和識別時隙數(shù)Ni應(yīng)該滿足[12]

通過三種時隙的數(shù)量對比，判斷時隙數(shù)L和待識別標(biāo)簽n之間的關(guān)系。當(dāng)L與n相等時，應(yīng)有

從而可得邊界條件

為避免頻繁調(diào)整Q值，當(dāng)邊界條件得到滿足時，算法不再進(jìn)行幀長調(diào)整，而是直接轉(zhuǎn)入碰撞標(biāo)簽識別。

1.3 快速分組的實(shí)現(xiàn)

各標(biāo)簽隨機(jī)地從區(qū)域(0,2Q-1)內(nèi)選擇一個隨機(jī)數(shù),作為自身發(fā)送數(shù)據(jù)所選擇的時隙號。使用計數(shù)器備份此隨機(jī)數(shù)，作為該標(biāo)簽的分組號。當(dāng)閱讀器偵測到碰撞發(fā)生，即有多個標(biāo)簽選擇了同一時隙號，此時應(yīng)將所備份的分組號存入閱讀器存儲分組號的棧內(nèi)，留待下一階段使用，由此可將發(fā)生碰撞的標(biāo)簽分成若干組。各標(biāo)簽隨機(jī)選擇時隙數(shù)，選擇相同的標(biāo)簽可通過分組的方式被離散開來，所以，算法效率相對穩(wěn)定。

1.4 算法流程

EQR算法中，標(biāo)簽有兩個計數(shù)器C1和C2，閱讀器中有計數(shù)器Cq，存儲分組號的棧S1和存儲查詢前綴的棧S2。

算法流程如圖1所示。

圖1 EQR算法流程

EQR算法的具體步驟可描述如下。

步驟1閱讀器發(fā)送初始化Q值給標(biāo)簽，并在Cq中保存這個值。

步驟2標(biāo)簽隨機(jī)地從(0,2Q-1)中選擇一個值，并且保存于C1和C2中。

步驟3閱讀器發(fā)送查詢命令，C1=0的標(biāo)簽響應(yīng)。若沒有響應(yīng)則為空閑時隙；若有多個標(biāo)簽響應(yīng)則為碰撞時隙，將碰撞標(biāo)簽計數(shù)器C1值設(shè)為最大2Q，C2值不變且入棧做為第二階段的查詢碰撞標(biāo)簽的分組號；若只有一個標(biāo)簽響應(yīng)，則為成功識別并將該標(biāo)簽標(biāo)記為已識別狀態(tài)不再響應(yīng)查詢。

步驟4閱讀器Cq減1，未響應(yīng)標(biāo)簽C1減1。

步驟5判斷Cq是否為零，若為零，則一幀結(jié)束。判斷這一幀中空閑、碰撞、識別時隙的比例關(guān)系，若滿足邊界條件，則清空棧，重新調(diào)整

Q= round (Q-0.2)，

轉(zhuǎn)到步驟1；若不滿足邊界條件，則進(jìn)入下一階段，即使用QTR算法識別碰撞標(biāo)簽，此時所有標(biāo)簽初始選擇的時隙數(shù)值保存在標(biāo)簽自己的C2中作為第二階段的分組號，棧S1中存儲了所有的分組號。

步驟6從棧S1中彈出分組號并發(fā)送查詢前綴給所有標(biāo)簽。

步驟7標(biāo)簽中C2值等于S1彈出的分組號的標(biāo)簽進(jìn)行響應(yīng)，使用QTR算法將自身標(biāo)簽碼與查詢前綴匹配并將查詢前綴壓入棧S2。

步驟8判斷匹配前綴棧S2是否為空，若不為空則返回步驟6。

步驟9判斷棧S1是否為空，若不為空則返回步驟6；若為空則表示所有碰撞標(biāo)簽被成功識別。

2 性能分析與仿真

衡量RFID系統(tǒng)防碰撞算法性能的指標(biāo)有兩個，即吞吐率和系統(tǒng)時間復(fù)雜度[13]。吞吐率定義為待識別標(biāo)簽總數(shù)和總時隙數(shù)的比值；系統(tǒng)時間復(fù)雜度即識別過程所需總時隙數(shù)。

2.1 算法性能分析

對于Q算法，根據(jù)二項分布，同一時隙只有一個標(biāo)簽的概率

每幀內(nèi)可識別的標(biāo)簽數(shù)

故Q算法的吞吐率為

當(dāng)L=n時,求得吞吐率的最大值

若N≥25,則

ηQ，max≤0.375，

故總時隙數(shù)

對于QT算法，根據(jù)查詢前綴與標(biāo)簽碼的碰撞位后一位進(jìn)行0和1的分組，當(dāng)待識別標(biāo)簽總數(shù)n?2時，吞吐率可近似為[14]

當(dāng)n≥25時，則

ηQT≤0.41，

故總時隙數(shù)近似為

對于EQR算法,根據(jù)邊界條件要求，若成立比例關(guān)系

據(jù)此，當(dāng)N≥25時，有

η≤0.513，

總時隙數(shù)近似為

2.2 算法仿真

參照EPCC1G2標(biāo)準(zhǔn)，針對多標(biāo)簽單閱讀器識別系統(tǒng)，標(biāo)簽數(shù)量從0到500，標(biāo)簽編碼長度為96位，分別在標(biāo)簽編碼完全隨機(jī)與標(biāo)簽編碼前綴60位相同這兩種情況下進(jìn)行仿真比較，結(jié)果如圖2和圖3所示。

由圖2可見，當(dāng)標(biāo)簽編碼前綴相同時，EQR算法顯著的提高了吞吐率。由于采用了標(biāo)簽分組策略，解決碰撞標(biāo)簽時的吞吐率始終保持在一個較高水平。

閱讀所發(fā)送的總時隙數(shù)可以反應(yīng)出該系統(tǒng)時間復(fù)雜度。由圖3可見，在標(biāo)簽編碼前綴相同這個特定的應(yīng)用環(huán)境下，EQR算法要明顯優(yōu)于Q算法及QT算法，發(fā)送的通信總時隙數(shù)要小于后兩種，這說明EQR算法可縮短標(biāo)簽識別時間，提高系統(tǒng)識別效率。

(a) 編碼隨機(jī)

(b) 編碼前綴相同

(a) 編碼隨機(jī)

(b) 編碼前綴相同

3 結(jié)束語

EQR算法使用設(shè)定邊界條件和融合QTR算法的方法，能克服Q算法“標(biāo)簽饑餓”和幀長調(diào)整頻繁的問題，使用快速分組的策略可彌補(bǔ)QTR算法在識別大量標(biāo)簽時效率較低的缺點(diǎn)。仿真驗證表明，EQR算法可提高系統(tǒng)吞吐率，降低通信總時隙數(shù)。

[1]AtzoriL,IeraA,GiacomoM.Intheinternetofthings:asurver[J].ComputerNetworks, 2010,54(3):2785-2885.

[2]MobahatH.AuthenticationandlighrweigthcyptographyinlowcostRFID[C]//The2ndInternationalConferenceonSoftwareTechnologyandEngineer.SanJuan:IEEE,2010:123-129.

[3]VogtH.EfficientobjectidentificationwithpassiveRFIDtags[C]//ProceedingsofIEEEInternationalConferenceonPervasiveComputing.Zurich:Springer-Verlag, 2002:98-113.

[4]MyungJ,LeeW,SrivastavaJ,etal.Tag-splitting:adaptivecollisionprotocolsforRFIDtagidentification[J].IEEETransactionsonParallelandDistribbutedSystems, 2007,18(6):763-775.

[5] 周曉光.射頻識別技術(shù)原理與應(yīng)用實(shí)例[M].北京:人民郵電出版社，2006:134-138.

[6] 中國物聯(lián)網(wǎng).詳解全球三大RFID產(chǎn)業(yè)標(biāo)準(zhǔn)體系對比分析[EB/OL].(2010-10-28)[2014-12-19].Http://info.secu.hc360.com/2010/10/281356403021.html.

[7]LeeS,JooSD,LEECW.AnenhanceddynamicframedslottedalohaalogrithmforRFIDtagidentification[C]//Proceedingsofmobiquitous.Orlando:IEEE,2005:166-172.

[8]ChoJ,ShinJD,KimSK.RFIDtaganti-collisionprotocol:querytreewithreversedIDs[C]//InternationalConferenceonAdvancedCommunicationTechnology,KoreaSeoul:IEEE,2008:225-230.

[9] 黃玉蘭.射頻識別(RFID)核心技術(shù)詳解[M].北京:人民郵電出版社,2012:370.

[10] 宋紅波,答軍.一種半有源射頻識別標(biāo)簽設(shè)計[J].西安郵電大學(xué)學(xué)報，2014，19(4):90-93.

[11]ZhangYan,YangLT,ChenJiming.RFID與傳感器網(wǎng)絡(luò):架構(gòu)、協(xié)議、安全與集成[M].謝志軍，譯.北京:機(jī)械工業(yè)出版社,2012:87-95.

[12]JiaXiaolin,FengQuanyuan.Aniprovedanti-collsionprotocolforradiofrequencyidentificationtag[J].InternationalJournalofCommunicationSystems,2013,8(6):78-81.

[13]LaPoratT,MaseliG,PetrioliC.Anti-collsionprotocolsforsingle-readerRFIDsystems:temporalanalysisandoptimization[J].IEEETransactionsonMobileComputing,2011,10(2):201-203.

[14]HushDR,WoodC.AnalysisoftreealgorithmsforRFIDarbitration[C]//ProceedingsofIEEESymposiumonInformationTheory,USAMACambridge:IEEE,1998：107-116.

[責(zé)任編輯:瑞金]

《西安郵電大學(xué)學(xué)報》版權(quán)聲明

為適應(yīng)我國信息化建設(shè)的需要，擴(kuò)大刊物影響，拓寬信息交流渠道，本刊已加入“中國知網(wǎng)CNKI系列期刊數(shù)據(jù)庫”、“中國核心期刊(遴選)數(shù)據(jù)庫”(萬方數(shù)據(jù)——數(shù)字化期刊群)、“中國期刊網(wǎng)”等數(shù)據(jù)庫。本刊已許可以上數(shù)據(jù)庫以數(shù)字化方式復(fù)制、匯編、發(fā)行、信息網(wǎng)絡(luò)傳播本刊所載文章的全文信息。稿件一經(jīng)刊登，將在本刊稿酬中一次性支付著作權(quán)使用報酬(包括印刷版、光盤版和網(wǎng)絡(luò)版等各種使用方式的報酬)。作者向本刊提交文章的行為即視為同意我刊上述聲明。

西安郵電大學(xué)學(xué)報編輯部

Multi-tags anti-colision algorithms in RFID system

ZHANG Jirong, JIANG Chi, LIU Yali

(School of Communication and Information Engineering, Xi’an University of Posts and Telecommunication, Xi’an 710121, China)

In order to improve the effciency of single reader under multi-tags RFID system, a hybrid algorithm is proposed to use in a particular condition which tags number have the same prefix. In the first step of this algorithm, the Adaptive Slot-Count (Q) algorithm is used to adjust the frame size to approach the number of tags to achieve maximum efficiency and divide the collision tags into group. In the second step, the Query Tree with Reversed IDs (QTR) is used to identify collision tags grouop by group. According to EPC C1G1 Standrad, in the single reader and mulit-tags system enviroment, simulation is carried out with the size of tag number of 96 in two cases: complete random and same prefix of tag number. Result show when the tags number has a same prefix, compared to QT and Q algorithm, the hybrid algorithm could improve the throught rate and reduce the number of slots.

multi-tags anti-colision, hybrid algorithm, query tree with reversed IDs, throught rate

2014-12-16

張繼榮(1963-)，女，博士，教授，從事現(xiàn)代通信網(wǎng)研究。E-mail:comnet@xupt.edu.cn江馳(1990-)，男，碩士研究生，研究方向為現(xiàn)代通信網(wǎng)。E-mail:108182061@qq.com

10.13682/j.issn.2095-6533.2015.06.007

TN92

A

2095-6533(2015)06-0028-05