梅佳偉，李 暉

（沈陽工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 沈陽110870）

0 引 言

射頻識別（Radio Frequency Identifcation，RFID）技術(shù)起始于1973年。作為自動識別和數(shù)據(jù)獲取的一部分，RFID系統(tǒng)通過無線網(wǎng)與網(wǎng)絡(luò)系統(tǒng)進行互交，能夠單獨識別追蹤并捕獲包裝中貨物、動物甚至人的標(biāo)簽狀態(tài)或信息[1]。因此，RFID將會取代現(xiàn)在普遍使用的條形碼廣泛應(yīng)用于物流、零售和存儲管理等領(lǐng)域[2]。

由于標(biāo)簽的體積和造價等原因限制，一個閱讀器讀取范圍內(nèi)同時出現(xiàn)多個標(biāo)簽時，它們會同時響應(yīng)閱讀器的查詢信息，而標(biāo)簽本身無法感知到周圍標(biāo)簽的存在，此時就會出現(xiàn)標(biāo)簽信息的碰撞[3]，導(dǎo)致閱讀器無法順利獲取標(biāo)簽信息。因此，射頻標(biāo)簽的防碰撞成為射頻識別過程中的一個關(guān)鍵技術(shù)[4]。

受現(xiàn)有標(biāo)簽技術(shù)和成本制約，目前的標(biāo)簽防碰撞算法主要分為兩類：一種是以ALOHA算法為主的非確定性算法[5-8]，一種是以二進制搜索算法為基礎(chǔ)的確定性算法。其中，ALOHA算法容易出現(xiàn)有一些標(biāo)簽可能長時間與其他標(biāo)簽發(fā)生碰撞而不能被識別的現(xiàn)象，即標(biāo)簽餓死現(xiàn)象。二進制樹搜索的防碰撞算法主要包括動態(tài)的二分支搜索DBS算法、查詢樹QT算法[9]和碰撞樹CT算法[10]等。這些算法主要通過不斷對標(biāo)簽池查詢的方式，達到完全識別未讀取的標(biāo)簽的目的。它不存在標(biāo)簽餓死現(xiàn)象，但是造成了通信量的大量增加和識別時間長的問題。

在此基礎(chǔ)上出現(xiàn)了一些多叉樹的防碰撞算法，識別過程中通過降低查詢輪數(shù)或者提高查詢碼的準(zhǔn)確程度來降低通信量和空閑時隙。但是，由于二進制查詢方式的逐位查詢特點，遇到新的碰撞位標(biāo)簽就會向閱讀器發(fā)送信息用以形成新的查詢碼，而閱讀器能利用到的信息只有碰撞位信息，這樣在碰撞密集的位置就會造成大量的通信資源浪費。例如，宋建華等人提出的AHT算法[11]，動態(tài)選擇樹形叉數(shù)，通過減少查詢輪數(shù)來降低通信代價，但無法判別多位碰撞的碰撞類型，造成了不可避免的空閑時隙，識別效率不穩(wěn)定。付鈺等人在GBAQT算法[12]中通過增加仲裁位數(shù)，使閱讀器與標(biāo)簽反復(fù)通信對比來確定多位碰撞的類型，使得系統(tǒng)的空閑時隙減少甚至消除來達到提高識別效率的目的，但大大提高了通信成本。Landaluce H等人在CT算法的基礎(chǔ)上提出了CWT算法[13]，通過動態(tài)窗函數(shù)確定下一輪標(biāo)簽向閱讀器的通信量，但在無碰撞時隙會出現(xiàn)閱讀器不能讀取到全部標(biāo)簽信息的情況，降低了整個系統(tǒng)的識別效率，增加了識別成本。本文提出一種自適應(yīng)多位碰撞檢測算法MCDT，通過檢測到的最高2～3位碰撞位的間隔特點，借助于查詢碼，動態(tài)決定下一輪標(biāo)簽向閱讀器傳送的信息量，從而在保持較少空閑時隙維持穩(wěn)定的識別時間的同時，大量降低標(biāo)簽到閱讀器的通信量。

1 MCDT碰撞檢測算法

1.1 碰撞樹算法

CT碰撞樹算法以及目前主要的二進制防碰撞算法都是通過曼切斯特編碼對識別過程中的碰撞位進行追蹤定位[14-16]。CT算法過程中，閱讀器在一輪查詢后接收到了標(biāo)簽發(fā)送來的信息，先判斷信息中是否存在碰撞，如果存在碰撞則判斷第一位碰撞位的具體位置，之后根據(jù)第一位碰撞位的具體位置形成2個新的查詢碼再進行查詢過程。例如：在某輪中查詢碼的內(nèi)容為q1q2…qi（若標(biāo)簽的ID信息總位數(shù)為k位，則i是小于等于k且大于零的整數(shù))。本輪中閱讀器接收到的信息為r1r2…rc-1rc，其中rc為檢測到的第一位碰撞位，則將形成2個新的查詢碼q1q2…qir1r2…rc-10和q1q2…qir1r2…rc-11。重復(fù)上述過程，直到當(dāng)前閱讀器范圍內(nèi)不存在未讀取的標(biāo)簽。

在CT算法和現(xiàn)有的二進制防碰撞算法中，都是通過提高識別效率、減少查詢次數(shù)來簡化系統(tǒng)的通信來降低通信量。不論是二叉樹或者是多叉樹算法，利用的都是檢測到的最高幾位的連續(xù)碰撞位形成新的查詢碼。CT算法主要利用一位碰撞位，而四叉樹的算法會利用第1位和第2位碰撞位形成00、01、10、11這樣4個分支。在一次查詢過程中，最高幾位碰撞位后的信息都是無用信息，如CT算法中閱讀器接收到r1r2…rc-1rcrc+1…，其中rc+1…屬于無用信息。標(biāo)簽在每一輪的查詢過程中都會向閱讀器傳輸大量無用信息，且回復(fù)的標(biāo)簽數(shù)目越多，碰撞位越密集，造成的浪費越多。

1.2 MCDT算法

針對CT算法中通信資源的浪費問題，提出MCDT算法來避免標(biāo)簽向閱讀器傳送大量無用信息。MCDT算法將查詢碼的形式由CT算法的q1q2…qi轉(zhuǎn)變成q1q2…qi||T。新形成的查詢碼比原有的多出一位信息T。T的目的是輔助標(biāo)簽確定查詢過程中需要向閱讀器發(fā)送多少位的標(biāo)簽信息。T的具體數(shù)值利用閱讀器檢測到的最高第2位與第3位碰撞位之間間隔的比特位數(shù)S來控制計算的。圖1演示了在后2位碰撞并不連續(xù)的情況下閱讀器如何形成新的查詢碼的工作過程。若3個碰撞位在接收信息中的編號分別為r_c1、r_c2、r_c3。在檢測到的第1位碰撞位r_c1處，閱讀器會形成2個查詢碼。如圖1所示，原查詢碼q_1q_2…q_i和檢測到不發(fā)生碰撞的信息r_1r_2…r(c-1)、r_(c1+1)…r_(c2-1)不 變，r_c1在 上方查詢碼中轉(zhuǎn)變?yōu)?，在下方查詢碼中為1。形成的兩個新查詢碼為在 下 一 輪 查 詢 的 過程中，得到的回復(fù)信息第一位必然是一個碰撞位。再通過第2、3位之間的間隔S來確定T的值。圖1中S bit為接收到標(biāo)簽信息中從r_c2到r_c3共有S bit的數(shù)據(jù)。因為考慮到在接下來的查詢過程中還需要至少3個碰撞位來輔助確定T的值，這里規(guī)定T必須是大于等于S+4。

實際情況中，并不是每次都是算法理想狀況能出現(xiàn)3位碰撞，或者3個碰撞位是連續(xù)的中間沒有不碰撞的信息位。這些情況在識別過程中總會發(fā)生，那么算法就要自適應(yīng)去調(diào)整識別方式。規(guī)定在一次檢測中只出現(xiàn)了2次或者1次碰撞，則T值就會被設(shè)置為k-i，即在這2種情況下，下一次的查詢過程中標(biāo)簽傳輸除對應(yīng)查詢碼位數(shù)的剩下的所有信息。

圖1 新查詢碼形成過程

1.3 MCDT算法的流程

流程如圖2所示，其中L為當(dāng)前查詢碼長度，K為標(biāo)簽ID信息二進制碼的長度。

圖2 算法流程

步驟1：閱讀器重置，初始化查詢前綴堆棧，向堆棧中依次壓入0|T、1|T；

步驟2：查詢碼存儲單元彈出頂部的數(shù)據(jù)查詢碼。接著閱讀器發(fā)送QUERY(q1q2…qi||T)，在當(dāng)前的閱讀器范圍內(nèi)與查詢內(nèi)容相符合的標(biāo)簽回應(yīng)閱讀器查詢。

步驟3：標(biāo)簽檢測自己的ID信息前綴與查詢碼q1q2…qi對應(yīng)位置是否相同。檢測結(jié)果相同的標(biāo)簽，響應(yīng)閱讀器的查詢信息，且根據(jù)查詢碼中的T來確定要發(fā)送多少比特的信息給閱讀器，然后執(zhí)行步驟4；若是沒有標(biāo)簽前綴與本次查詢碼相同，那么本輪查詢便無響應(yīng)，系統(tǒng)認定此次閱讀器時隙開銷為無用的空時隙，轉(zhuǎn)到算法步驟6。

步驟4：閱讀根據(jù)標(biāo)簽發(fā)來的標(biāo)簽信息，驗證有無發(fā)生碰撞。如果沒有碰撞發(fā)生，則記錄標(biāo)簽信息成功識別次標(biāo)簽；若是發(fā)生碰撞，則執(zhí)行步驟5。

步驟5：首先判斷碰撞的類型。碰撞位是否大于等于3位，若成立，則在最第1位碰撞位處形成0和1兩個分支，再加上第1位到第2位碰撞位之間的數(shù)據(jù)形成2個新的查詢碼，然后根據(jù)最高第2二位與第2位碰撞位之間的距離更新T的數(shù)值，即一個ST的過程，之后把這2個查詢碼壓入堆棧。若碰撞位低于3位，則在最高位碰撞處形成0和1分支2個查詢碼，再將T設(shè)置為k-i壓入堆棧，進入算法步驟6。

步驟6：檢測當(dāng)前查詢碼儲存單元中是否還有查詢碼數(shù)據(jù)。若為空，則說明查詢結(jié)束，退出算法循環(huán)；如果不為空，則轉(zhuǎn)到算法步驟2，繼續(xù)進行算法循環(huán)。

例如，第一次查詢過程中閱讀器接收到的信息為1XXX0011…XXX（一共是（k-1）比特信息），那么現(xiàn)在就可以判斷S=2，ST之后查詢碼中T的數(shù)值被設(shè)置為T=2+4=6，那么下一次標(biāo)簽傳送給閱讀器的信息為XX0011（一共是6bit信息）?？梢?，一次查詢過程中，標(biāo)簽要傳送給閱讀器的信息量大量減少，同時不影響閱讀器形成新的查詢碼。

2 算法分析

在RFID系統(tǒng)中，主要用閱讀器的識別效率、識別時間復(fù)雜度和閱讀器與標(biāo)簽的通信復(fù)雜度衡量算法的性能[17]。MCDT算法與CT算法在識別效率方面大致相同。下面通過計算分析MCDT算法的性能。

MDCT算法在識別過程中主要采用二叉樹的分支方式。識別過程是由閱讀器查詢到標(biāo)簽回應(yīng)的一個個周期組成。這里設(shè)需要識別的標(biāo)簽數(shù)量為n，由于每次都是在碰撞點進行分支，所以CT算法中不存在空時隙，也就是沒有標(biāo)簽回應(yīng)的時隙，故二叉樹的葉子節(jié)點數(shù)也是n。

碰撞樹中節(jié)點數(shù)目為：

每一個節(jié)點處，閱讀器都要進行一輪查詢，那么二叉樹中的節(jié)點數(shù)目就是完整的識別過程中閱讀器需要查詢的次數(shù)，也就是閱讀器需要開銷的時隙數(shù)。設(shè)第N輪的查詢時間為TN，那么閱讀器查詢過程的時間復(fù)雜度T就可以表示為：

每進行一輪查詢閱讀器就會有一個時隙開銷。在防碰撞算法中，算法效率主要是指要識別的標(biāo)簽數(shù)量與閱讀形成的總的時隙數(shù)量的比值，即識別效率E可表示為：

可知，CT算法的整體效率略大于50%。

標(biāo)簽的通信復(fù)雜度主要是指在識別過程中，標(biāo)簽需要向閱讀器發(fā)送的二進制數(shù)據(jù)的位數(shù)，所需要傳送的數(shù)據(jù)量越大，標(biāo)簽需要的能量就越多，對標(biāo)簽成本的要求就越高。

若設(shè)C為查詢過程的通信量，lc.N、lq.N分別為閱讀器在第N個周期查詢過程中發(fā)出的命令和查詢碼的長度。lr.N是在本周期標(biāo)簽響應(yīng)閱讀器命令回復(fù)的二進制數(shù)據(jù)長度，那么C可以表示為：

在原本的碰撞樹和相關(guān)的改進算法中，若設(shè)每個標(biāo)簽的ID信息二進制數(shù)據(jù)長度為k，那么：

MCDT算法中，由于會根據(jù)碰撞的情況去決定下一次標(biāo)簽向閱讀器傳輸?shù)亩M制數(shù)據(jù)長度lr.N，那么在碰撞符合條件的情況下，回復(fù)的長度為lr.N1，則：

因此，新的通信量C1為：

由此可知，MCDT算法在整個識別過程中的通信復(fù)雜度會低于原有的碰撞樹相關(guān)算法。

3 算法的仿真以及驗證

使用Matlab2014b作為仿真平臺，對碰撞樹算法（CT）、查詢樹算法（QT）、自適應(yīng)的A4PQT四叉樹算法[18]和本文的自適應(yīng)多位碰撞檢測算法（MCDT）進行對比仿真。仿真的內(nèi)容主要是識別效率、識別時間和標(biāo)簽對閱讀器的通信復(fù)雜度。使用現(xiàn)在主流的96bit長度標(biāo)簽進行仿真，而為了數(shù)據(jù)能夠更加清晰，標(biāo)簽的數(shù)量從100到1000，每次增長50個。

圖3是4種算法的識別效率對比圖。

圖3 效率對比

可以看出，在識別效率方面，MCDT算法與碰撞樹CT算法基本一致。由于每次都是在碰撞位置形成新的查詢碼，所以基本沒有無應(yīng)答時隙，效率基本穩(wěn)定在0.5，與標(biāo)簽的數(shù)量無關(guān)聯(lián)。A4PQT算法由于在連續(xù)2位碰撞時會出現(xiàn)4個分支，這樣一次分支就有可能造成最多2個空時隙，故識別相同數(shù)目標(biāo)簽時效率會低于MCDT算法和CT算法。

圖4是4種算法識別時間的對比仿真?？梢钥闯觯捎赒T算法和A4PQT算法中存在較多的空時隙，也就是存在很多輪次的查詢是沒有標(biāo)簽回應(yīng)的，故查詢完成的總時間明顯高于另外2種算法。而從圖4中可以看出，MCDT算法在標(biāo)簽數(shù)目較多時，查詢完成時間略低于CT算法；數(shù)目較低時，查詢時間則基本與CT算法持平。

圖4 識別時間對比

如圖5所示，是4種算法在標(biāo)簽到閱讀器的通信量的對比仿真。可以看出，由于QT算法無論碰撞與否，每次只增加一位查詢碼。在這種情況下，標(biāo)簽發(fā)送給閱讀器的信息量明顯高于在碰撞點形成查詢碼的CT算法。當(dāng)遇到連續(xù)碰撞的情況時，如果存在00、01、10、11這4種情況的碰撞，那么A4PQTMCDT算法與CT算法相比，就會降低查詢次數(shù)。從圖5也可以看出，A4PQT算法的通信量比CT算法有明顯下降。與MCDT算法相較，因為新算法會根據(jù)碰撞信息來調(diào)整標(biāo)簽向閱讀器的通信量，所以每次只發(fā)送有用的碰撞信息，最后才發(fā)送完整的標(biāo)簽信息，故通信量降低的幅度非常明顯，且標(biāo)簽越多碰撞情況越復(fù)雜，所以標(biāo)簽越多時通信量的優(yōu)勢越明顯。

圖5 通信量對比

由以上3個對比仿真可以看出，本文提出的MCDT算法在識別效率和識別時間方面都有較好表現(xiàn)，且大大降低了通信量，優(yōu)勢明顯。

4 結(jié) 語

本文基于二進制防碰撞算法中的碰撞檢測方法，提出了一種利用2～3位碰撞位的自適應(yīng)多位碰撞檢測的防碰撞MCDT算法。該算法通過檢測最高2～3位的碰撞位來輔助判斷標(biāo)簽在下一輪中需要傳遞給閱讀器的標(biāo)簽信息，避免在多次查詢過程中或者是碰撞密集環(huán)境下標(biāo)簽向閱讀器傳輸過多的無用信息而浪費能量。

通過仿真結(jié)果可以看出，MCDT算法能夠減少閱讀器與標(biāo)簽的通信量，降低標(biāo)簽成本，且在維持查詢效率、查詢時間時有較好表現(xiàn)，同時有效降低了標(biāo)簽向閱讀器的通信復(fù)雜度。根據(jù)仿真結(jié)果可以知道，在標(biāo)簽數(shù)量快速增加的同時，通信量降低幅度顯著。因此，MCDT算法適合于同一個閱讀器范圍內(nèi)標(biāo)簽數(shù)目較多或者需要連續(xù)讀取較多標(biāo)簽的場景，符合現(xiàn)代大型倉儲物流、無人超市的應(yīng)用環(huán)境。

參考文獻：

[1] He M,Horng S J,Fan P,et al.A Fast RFID Tag Identification Algorithm Based on Counter and Stack[J].Expert Systems with Applications An International Journal,2011,38(06):6829-6838.

[2] Safa H,El-Hajj W,Meguerditchian C.A Distributed Multi-Channel Reader Anti-collision Algorithm for RFID Environments[J].Computer Communicatio ns,2015,64(01):44-56.

[3] Hsu C H,Chao H C,Park J H.Threshold Jumping and Wrap-around Scan Techniques Toward Efficient Tag Identification in High Density RFID Systems[J].Information Systems Frontiers,2011,13(04):471-480.

[4] Li T,Wu S S,Chen S,et al.Generalized Energy-efficient Algorithms for the RFID Estimation Problem[J].IEEE/ACM Transactions on Networking,2012,20(06):1978-1990.

[5] He Y,Wang X.An ALOHA-based Improved Anticollision Algorithm for RFID Systems[J].IEEE Wireless Communications,2013,20(05):152-158.

[6] 陳毅紅,馮全源.按需時隙分配RFID防碰撞協(xié)議研究[J].電子學(xué)報,2014,42(02):377-382.CHEN Yi-hong,FENG Quan-yuan.Research on RFID Anti-collision Protocol for on-demand Time Slot Allocation[J].Acta Electronica Sinica,2014,42(02):377-382.

[7] Wang H,Xiao S,Lin F,et al.Group Improved Enhanced Dynamic Frame Slotted ALOHA Anti-collision Algorithm[J].Journal of Supercomputing,2014,69(03):1235-1253.

[8] 丁治國,丁莉,湯紅飛.基于動態(tài)預(yù)約機制的防碰撞算法[J].計算機工程,2017,43(02):317-321.DING Zhi-guo,DING Li,TANG Hong-fei.AnticollisionAlgorithm Based on Dynamic Reservarion Mechanism[J].Computer Engineering,2017,43(02):317-321.

[9] Hush D R,Wood C.Analysis of Tree Algorithms for RFID Arbitration[C].IEEE International Symposium on Information Theory,2002:15-23.

[10] Jia X,Feng Q,Ma C.An Efficient Anti-Collision Protocol for RFID Tag Identification[J].IEEE Communications Letters,2010,14(11):1014-1016.

[11] 宋建華,郭亞軍,韓蘭勝等.自調(diào)整混合樹RFID多標(biāo)簽防碰撞算法[J].電子學(xué)報,2014,42(04):685-689.SONG Jian-hua,GUO Ya-jun,HAN Lan-sheng.An Adjustive Hybrid Tree Anti-CollisionAlgorithm for RFID Multi-Tag Identification[J].Acta Electronica Sinica,2014,42(04):685-689.

[12] 付鈺,錢志鴻,程超等.基于分組機制的位仲裁查詢樹防碰撞算法[J].通信學(xué)報,2016,37(01):123-129.FU Yu,QIAN Zhi-hong,CHENG Chao,et al.Bit Arbitration Query Tree Anti-CollisionAlgorithm Based on Grouping Mechanism[J].Journal on Communicatio ns,2016,37(01):123-129.

[13] Landaluce H,Perallos A,Bengtsson L,et al.Simplified Computation in Memoryless Anti-collision RFID Identification Protocols[J].Electronics Letters,2014,50(17):1250-1252.

[14] Shin J,Jeon B,Yang D.Multiple RFID Tags Identification with M-ary Query Tree Scheme[J].IEEE Communications Letters,2013,17(03):604-607.

[15] Landaluce H,Perallos A,Zuazola I J G.A Fast RFID Identification Protocol with Low Tag Complexity[J].IEEE Communications Letters,2013,17(09):1704-1706.

[16] Lai Y C,Hsiao L Y,Chen H J,et al.A Novel Query Tree Protocol with Bit Tracking in RFID Tag Identification[J].IEEE Transactions on Mobile Computing,2013,12(10):2063-2075.

[17] Jiang Y,Zhang R.An Adaptive Combination Query Tree Protocol for Tag Identification in RFID Systems[J].IEEE Communications Letters,2012,16(08):1192-1195.

[18] Zhang W,Guo Y,Tang X,et al.An Efficient Adaptive Anti Collision Algorithm Based on 4-Ary Pruning Query Tree[J].International Journal of Distributed Sensor Networks,2013(01):1-7.