改進(jìn)型RFID自適應(yīng)標(biāo)簽識(shí)別算法

孫　宇，王玉皞，李　唯，鄧　晟

(南昌大學(xué) 信息工程學(xué)院，江西 南昌　330031)

?

改進(jìn)型RFID自適應(yīng)標(biāo)簽識(shí)別算法

孫宇，王玉皞，李唯，鄧晟

(南昌大學(xué) 信息工程學(xué)院，江西 南昌330031)

基于碰撞識(shí)別算法系列，提出改進(jìn)型自適應(yīng)標(biāo)簽識(shí)別算法(Improved Adaptive Collision Tree Algorithm，IACT)。算法通過(guò)優(yōu)化查詢前綴，消除了自適應(yīng)碰撞標(biāo)簽識(shí)別算法在四叉樹(shù)搜索產(chǎn)生的空時(shí)隙查詢，從而減少了算法的時(shí)間復(fù)雜度，提高識(shí)別效率。通過(guò)理論推導(dǎo)和計(jì)算機(jī)仿真可知，該算法比自適應(yīng)標(biāo)簽識(shí)別算法(Adaptive Collision Tree Algorithm，ACT)有著明顯的優(yōu)化。

RFID；標(biāo)簽識(shí)別；防碰撞

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

射頻識(shí)別(Radio Frequency Identification，RFID)技術(shù)是一項(xiàng)利用射頻進(jìn)行非接觸式雙向通信的自動(dòng)識(shí)別技術(shù)[1-2]。它作為物聯(lián)網(wǎng)的核心技術(shù)，在國(guó)家行業(yè)發(fā)展中發(fā)揮著越來(lái)越重要的戰(zhàn)略作用，并影響社會(huì)的各領(lǐng)域，其發(fā)展顯現(xiàn)出高速化、規(guī)模化、泛在化等特點(diǎn)。當(dāng)多個(gè)標(biāo)簽(tags)在同一信道與閱讀器通信時(shí)，就會(huì)引發(fā)標(biāo)簽碰撞，為實(shí)現(xiàn)多標(biāo)簽識(shí)別，就必須解決多標(biāo)簽信號(hào)碰撞沖突的問(wèn)題。尤其在大規(guī)模的RFID標(biāo)簽場(chǎng)景下[3]，RFID系統(tǒng)的標(biāo)簽防碰撞能力直接決定RFID系統(tǒng)的識(shí)別效率。

目前，解決RFID系統(tǒng)中的標(biāo)簽碰撞問(wèn)題主要采用兩大類(lèi)標(biāo)簽防碰撞算法(anti-collision algorithm)[4]，一類(lèi)是基于時(shí)隙隨機(jī)分配的Aloha算法[4-6](隨機(jī)性防碰撞協(xié)議)，主要包括純Aloha(PA)、時(shí)隙Aloha(SA)、幀時(shí)隙Aloha(FSA)、動(dòng)態(tài)幀時(shí)隙Aloha(DFSA)等，適用于數(shù)量較少的標(biāo)簽識(shí)別。另一類(lèi)是基于樹(shù)形搜索的防碰撞算法(確定性防碰撞協(xié)議)，包括分裂樹(shù)(BTS)[7]、二進(jìn)制搜索(BS)[8]、查詢樹(shù)算法(QT)[9]，以及各種改進(jìn)算法和混合協(xié)議[10-11]。這類(lèi)算法比較復(fù)雜，但是適用于RFID標(biāo)簽較多的場(chǎng)景。文獻(xiàn)[12-14]就提出了一系列碰撞識(shí)別算法，這類(lèi)算法可以利用標(biāo)簽之間的比特位碰撞，消除了傳統(tǒng)樹(shù)形算法中閱讀器必須對(duì)接受序列進(jìn)行逐比特識(shí)別的限制，尤其在標(biāo)簽數(shù)量較多的情況，很好的減少了RFID系統(tǒng)的查詢時(shí)隙，由此也減少了系統(tǒng)通信復(fù)雜度。

文本在基于自適應(yīng)標(biāo)簽識(shí)別算法(Adaptive Collision Tree Algorithm，ACT)[14]算法的基礎(chǔ)上，提出了一種改進(jìn)型標(biāo)簽識(shí)別算法(IACT)，本文的算法對(duì)ACT算法中的四叉樹(shù)搜索進(jìn)行了前綴優(yōu)化，消除了ACT算法中四叉樹(shù)搜索產(chǎn)生的空時(shí)隙，同時(shí)也提高了算法識(shí)別效率。

2　碰撞識(shí)別算法以及相關(guān)改進(jìn)

2.1曼徹斯特碼

RFID系統(tǒng)中，標(biāo)簽ID為“0”和“1”的二進(jìn)制。標(biāo)簽編碼方式有多種，在二進(jìn)制搜索算法(Binary Search，BS)中，采用的編碼方式是曼徹斯特碼。曼徹斯特碼[15]是利用相位進(jìn)行編碼。其編碼方式為數(shù)據(jù)采集的時(shí)鐘信號(hào)(每個(gè)碼元時(shí)間的中間位置)處必有跳變，編碼值1為前半部分高電位，后半部分為低電位，即從高電平跳變到低電平(下降沿)，編碼值0為前半部分低電位，后半部分高電位，即從低電平跳變到高電平(上升沿)。這樣的好處是可以檢測(cè)到發(fā)生標(biāo)簽ID碰撞時(shí)，其碰撞比特的精確位置和標(biāo)示。本文提出的算法就是采用曼徹斯特碼，在發(fā)生碰撞時(shí)就能夠準(zhǔn)確地知道標(biāo)簽ID碰撞比特位。利用此特點(diǎn)，改善樹(shù)形算法。根據(jù)每個(gè)前綴下的匹配標(biāo)簽比特位。可以快速更新前綴，有效減少查詢時(shí)隙和通信復(fù)雜度。

2.2CT算法以及改進(jìn)型ICT算法

在文獻(xiàn)[12]，提出碰撞識(shí)別算法(Collision Protocol，CT)，其主要是基于查詢樹(shù)算法(QT)，在算法中采用了曼徹斯特編碼，標(biāo)簽在每次的最高碰撞位進(jìn)行分裂和疊加前綴。所以每一次查詢的查詢碼可能長(zhǎng)度都不一定一樣，有效的減少了在RFID標(biāo)簽識(shí)別過(guò)程中出現(xiàn)的空時(shí)隙。而ICT算法[13]是在CT算法基礎(chǔ)上，根據(jù)標(biāo)簽ID編碼的“二元性”，即每個(gè)標(biāo)簽ID編碼只能是“0”或者“1”，提出了單次查詢，兩次響應(yīng)。通過(guò)兩個(gè)標(biāo)示位“0”和“1”，進(jìn)行不同子周期的響應(yīng)，所以一次查詢就可以得到兩個(gè)標(biāo)識(shí)位下面的不同標(biāo)簽。

2.3自適應(yīng)標(biāo)簽識(shí)別算法

(1)

假設(shè)RFID系統(tǒng)中有X個(gè)待識(shí)別的標(biāo)簽ID，系統(tǒng)分配的分叉樹(shù)是L，那么在深度為1的搜索深度下，標(biāo)簽ID的識(shí)別概率是p(1)=(1-1/L)X-1，那么在搜索深度為m時(shí)，那么其識(shí)別概率為

p(m)=p(1)[1-p(1)]m-1

(2)

搜索深度均值就為

(3)

將式(2)帶入式(3)得到

(4)

因?yàn)?-p(1)必然是小于1的，最后根據(jù)等比數(shù)列算出搜索深度均值

(5)

已知時(shí)隙表達(dá)式為

(6)

式中：Tf表示系統(tǒng)識(shí)別均時(shí)隙。當(dāng)分叉樹(shù)分別是2和4時(shí)，系統(tǒng)識(shí)別均時(shí)隙則為

(7)

(8)

最后將式(7)公式(8)進(jìn)行比較?？梢杂?jì)算出，當(dāng)X<3時(shí)，T2用時(shí)更少。當(dāng)X≥3時(shí)，T4用時(shí)更少。通過(guò)和碰撞因子的轉(zhuǎn)換，可以知道η=1-(1/2)3-1=0.75是其臨界。每次檢測(cè)碰撞因子時(shí)，當(dāng)碰撞因子η<0.75選擇二叉樹(shù)搜索，當(dāng)η≥0.75，采用四叉樹(shù)。

3　改進(jìn)型自適應(yīng)標(biāo)簽識(shí)別算法

ACT算法可以合理的在ICT算法基礎(chǔ)上進(jìn)一步減少碰撞時(shí)隙，其通過(guò)碰撞因子和待識(shí)別標(biāo)簽數(shù)量X之間的轉(zhuǎn)換，但是還存在一些誤差。因?yàn)?，在?biāo)簽識(shí)別的過(guò)程中，雖然可以利用曼特斯特編碼知道碰撞位從而得到定義的碰撞因子，但是實(shí)際上當(dāng)前節(jié)點(diǎn)的碰撞因子并不是每次都是能夠?qū)?yīng)準(zhǔn)確的待識(shí)別標(biāo)簽ID數(shù)X。比如，碰撞比特是0011和1100這兩個(gè)。那么就可以知道其碰撞位為全4位碰撞。那么可見(jiàn)，碰撞因子為η=1滿足了之前的理論η≥0.75，應(yīng)該采用四叉樹(shù)搜索，這樣在選擇四叉樹(shù)搜索下就會(huì)多產(chǎn)生兩個(gè)空時(shí)隙。

ACT算法在處理ICT多叉樹(shù)自適應(yīng)問(wèn)題的選擇上還有改進(jìn)。為了減少自適應(yīng)多叉ICT算法可能產(chǎn)生的查詢空時(shí)隙，可以通過(guò)對(duì)閱讀器的前綴進(jìn)行優(yōu)化，也就是本文提出的改進(jìn)型自適應(yīng)碰撞識(shí)別算法(Improved adaptive collision tree algorithm，IACT)。在二叉樹(shù)的情況下，不會(huì)產(chǎn)生多余空時(shí)隙。那么在碰撞因子η<7.5這個(gè)判決條件下，還是采用二叉樹(shù)ICT算法。而在碰撞因子η≥0.75時(shí)，采用四叉樹(shù)。但是在發(fā)送查詢之前，先要對(duì)當(dāng)前節(jié)點(diǎn)碰撞位進(jìn)行一個(gè)判斷處理。

就如上面的標(biāo)簽，若碰撞的標(biāo)簽ID是0011和1100?？芍渑鲎脖忍匚粸閄XXX，碰撞因子為4/4=1，采用四叉樹(shù)。本文將4個(gè)碰撞比特位分別從高位到低位標(biāo)為X3，X2，X1，X0。閱讀器先發(fā)送一個(gè)最高兩位碰撞位即為11，其他比特位全為0的指令給標(biāo)簽。標(biāo)簽將接收到的指令與自己標(biāo)簽ID相“與”，即“0”與“0”得0、“0”與“1”得0、“1”與“0”得0、“1”與“1”得1。那么得到ID碼為1100，0000。所以標(biāo)簽ID的X3，X2位分別是11和00。為了讓閱讀器能夠識(shí)別出高兩位的實(shí)際標(biāo)簽ID碼。將得出的高兩位11和00轉(zhuǎn)換10進(jìn)制然后返回其對(duì)應(yīng)10進(jìn)制位置，即返回一個(gè)分別是X3和X0位置為1，其他位置為0的ID碼，閱讀器再次收到就可以根據(jù)碰撞位判斷出當(dāng)前存在的高兩位ID碼。通過(guò)在發(fā)送查詢之前進(jìn)行判斷處理就可以有效的檢測(cè)出當(dāng)前標(biāo)簽ID的高兩位，從而減少了發(fā)送無(wú)用查詢的空時(shí)隙情況。圖1是IACT算法的算法流程。

圖1　IACT算法流程

和查詢樹(shù)算法一樣，在初始時(shí)，前綴堆棧為空。開(kāi)始時(shí)，閱讀器從前綴池里取出空前綴，發(fā)送問(wèn)詢指令，等待標(biāo)簽響應(yīng)。所以本文的算法步驟如下：

1)閱讀器向前綴放入空串，將標(biāo)簽ID置空。

2)閱讀器發(fā)送前綴，標(biāo)簽響應(yīng)。標(biāo)簽根據(jù)自己標(biāo)志位在不同響應(yīng)子周期發(fā)送自己的標(biāo)簽ID。

3)判斷前綴是否為空，為空則識(shí)別完成。否則繼續(xù)。在有兩個(gè)響應(yīng)周期的閱讀器情況，回復(fù)標(biāo)簽中的剩余ID的最高碰撞位作為標(biāo)志位。前綴的更新為當(dāng)前前綴+剩余碰撞ID位的標(biāo)志位前沒(méi)有發(fā)生碰撞的比特。在響應(yīng)周期為S1的周期，標(biāo)簽發(fā)送標(biāo)志位為“0”的標(biāo)簽。在響應(yīng)周期S2，標(biāo)簽發(fā)送標(biāo)志位為“1”的標(biāo)簽。來(lái)響應(yīng)閱讀器的請(qǐng)求。

4)判斷是否發(fā)生碰撞，計(jì)算碰撞因子η，若η<0.75，則采用二叉樹(shù)，發(fā)送前綴；若η≥0.75，則采用四叉樹(shù)，根據(jù)判斷處理得出高兩位前綴，發(fā)送前綴。

5)將發(fā)生碰撞的最高位前的比特與前綴合并，形成新的前綴，放入堆棧。

6)再次看前綴是否為空，直到前綴為空為止。識(shí)別完成。

下面為一個(gè)識(shí)別實(shí)例，假設(shè)有7個(gè)長(zhǎng)度為4的ID標(biāo)簽，分別是A：0001，B：0010，C：0011，D：0100，E：0101，F(xiàn)：1100，G：1110。使用本算法進(jìn)行識(shí)別。識(shí)別過(guò)程如圖2所示。

圖2　IACT算法識(shí)別實(shí)例圖

通過(guò)圖2可知，本次識(shí)別7個(gè)標(biāo)簽使用6次查詢。其中陰影表示識(shí)別標(biāo)簽，虛線表示不需要發(fā)送查詢碼。

4　IACT算法分析

(9)

當(dāng)搜索深度大于m時(shí)，采用二叉樹(shù)。因?yàn)椴捎米又芷诘慕Y(jié)構(gòu)，在搜索的過(guò)程中二叉樹(shù)的查詢次數(shù)需要去掉子周期的次數(shù)。那么可得采用二叉樹(shù)搜索的識(shí)別時(shí)隙

(10)

式中：T子的個(gè)數(shù)根據(jù)標(biāo)簽碰撞的情況在0到X/2之間。本文改進(jìn)了完全四叉樹(shù)的查詢，優(yōu)化查詢前綴，所以這部分的時(shí)間復(fù)雜度需要加上閱讀器在檢測(cè)到碰撞二次發(fā)送查詢的時(shí)隙和減去空閑的時(shí)隙。二次查詢的時(shí)隙正好與碰撞時(shí)隙相等。假設(shè)，在四叉樹(shù)的m搜索層，X待識(shí)別標(biāo)簽。那么就有4m個(gè)節(jié)點(diǎn)，在m層n個(gè)標(biāo)簽響應(yīng)同一節(jié)點(diǎn)的概率服從二項(xiàng)分布

(11)

那么，空時(shí)隙即為0個(gè)標(biāo)簽響應(yīng)，識(shí)別時(shí)隙即為1個(gè)標(biāo)簽響應(yīng)，碰撞時(shí)隙即為多個(gè)標(biāo)簽響應(yīng)。概率表達(dá)式分別如下

(12)

(13)

P(1/X,m)

(14)

式中：n>1，p=1/4m表示為在4m節(jié)點(diǎn)里選擇一個(gè)節(jié)點(diǎn)的概率，那么可知

P(0/X,m)=(1-1/4m)X

(15)

P(1/X,m)=X·4-m(1-1/4m)X-1

(16)

P(n/X,m)=1-(1-1/4m)X-X·4-m(1-1/4m)X-1

(17)

設(shè)αmi/X和δmi/X分別表示在m層第i節(jié)點(diǎn)被搜索的概率和在m層第i節(jié)點(diǎn)發(fā)生碰撞的概率，節(jié)點(diǎn)在同一層的搜索和碰撞的概率相同，可知δmi/X=P(k/X,m)，當(dāng)父節(jié)點(diǎn)發(fā)生碰撞時(shí)，下一節(jié)點(diǎn)才能被訪問(wèn)到，所以當(dāng)深度大于1時(shí)，αmi/X=δ(m-1)i/X。平均查詢總時(shí)隙為

(18)

最后得到

(19)

把δmi/X=P(k/X,m)代入得到

X·4-m(1-1/4m)X-1]

(20)

碰撞時(shí)隙為

(21)

空閑時(shí)隙為總時(shí)隙減去碰撞時(shí)隙和識(shí)別時(shí)隙得到

(22)

根據(jù)文獻(xiàn)[16]可得大概關(guān)系為

(23)

那么，IACT算法的總時(shí)隙是

(24)

所以吞吐率為

(25)

根據(jù)文獻(xiàn)[13]中對(duì)于ICT算法通信復(fù)雜度的計(jì)算，可以推導(dǎo)IACT算法的通信復(fù)雜度為只是在二次查詢時(shí)增加一次查詢碼，但是減少了空閑時(shí)隙的查詢碼。所以算法的通信復(fù)雜度為

(26)

式中：Creader(X)表示為閱讀器通信復(fù)雜度；Ctags(X)表示為標(biāo)簽通信復(fù)雜度；lq,i是在i周期發(fā)送查詢前綴長(zhǎng)；lr,i是在i識(shí)別周期發(fā)送響應(yīng)的長(zhǎng)度。標(biāo)簽ID長(zhǎng)度lID=lq,i+lr,i，所以得到

(27)

5　IACT仿真以及性能分析

通過(guò)以上分析，本文主要仿真RFID標(biāo)簽識(shí)別最重要的兩個(gè)性能對(duì)比：查詢總時(shí)隙和算法吞吐率。將IACT算法與CT，ICT，ACT算法比較。仿真場(chǎng)景設(shè)置為標(biāo)簽ID長(zhǎng)度96，標(biāo)簽數(shù)量從0～10 000個(gè)，假設(shè)所有標(biāo)簽空間分布均勻，沒(méi)有丟失標(biāo)簽ID。通過(guò)仿真如圖3所示。

圖3　IACT算法與QT，CT，ICT，ACT算法的查詢次數(shù)仿真對(duì)比圖

從仿真結(jié)果看得出，IACT優(yōu)化了ACT在四叉樹(shù)時(shí)的前綴搜索。極大的減少了空時(shí)隙，進(jìn)而極大的減少了總查詢次數(shù)，減少了系統(tǒng)的識(shí)別時(shí)間復(fù)雜度。

圖4　IACT算法與QT，CT，ICT，ACT算法的吞吐率仿真對(duì)比圖

由圖4可以看出，新的改進(jìn)算法吞吐率有了很大的提高。然而，采用了四叉樹(shù)的算法在幾個(gè)節(jié)點(diǎn)上會(huì)出現(xiàn)一些跳變，這是因?yàn)榕c算法的搜索深度有關(guān)，深度m=?log4(X/3)」表示向下取整，不是一個(gè)連續(xù)的整數(shù)會(huì)導(dǎo)致標(biāo)簽數(shù)量在到達(dá)一定數(shù)量會(huì)出現(xiàn)搜索深度的跳變，所以算法查詢次數(shù)和吞吐率都會(huì)出現(xiàn)一個(gè)階段的上升然后有一個(gè)跳變。從圖中可以看出QT算法一直維持在0.4左右的吞吐率，CT和ICT分別維持在0.5和1.0的吞吐率左右。ACT的吞吐率也是高于ICT的。由于總查詢時(shí)隙的極大的減少，IACT吞吐率也是極大的提高，高于其他算法。

6　結(jié)論

本文提出一種新的改進(jìn)型碰撞識(shí)別算法，在自適應(yīng)碰撞識(shí)別算法上有效去除在選擇四叉樹(shù)搜索時(shí)產(chǎn)生的空時(shí)隙。有效減少系統(tǒng)總查詢時(shí)隙。在識(shí)別性能上也是極大地優(yōu)化了ACT算法，通過(guò)理論和仿真驗(yàn)證了提出的IACT算法優(yōu)于ACT，進(jìn)一步提升了算法的適用性。表明IACT算法可以應(yīng)用于標(biāo)簽識(shí)別，能高效地解決標(biāo)簽碰撞問(wèn)題。

[1]FINKENZELLER K. RFID-handbook fundamengtals and applications in contact less smart cards and identification [M]. 2nd ed. New York：Wiley and Sons，2003.

[2]WANT R. An introduction to RFID technology[J]. Pervasive computing，2006(1)：25-33.

[3]SHAO C，KIM T，YU J，et al. ProTaR： probabilistic tag retardation for missing tag identification in large-scale RFID systems[J]. IEEE transactions on industrial informatics，2015，11(2)：513-522.

[4]KLAIR D K，CHIN K W，RAAD R. A survey and tutorial of RFID anti-collision protocols[J]. Communications surveys & tutorials，2010，12(3)：400-421.

[5]SU W，ALCHAZIDIS N V，HA T T. Multiple RFID tags access algorithm[J]. IEEE transactions on mobile computing，2010，9(2)：174-187.

[6]KAITOVIC J，IMKO M， LANGWIESER R，et al. Channel estimation in tag collision scenarios[C]// 2012 IEEE International Conference on RFID. Orlando，F(xiàn)L：IEEE，2012： 74-80.

[7]HUSH D R，WOOD C. Analysis of tree algorithms for RFID arbitration[C]//IEEE International Symposium on Information Theory. Cambridge， MA：IEEE，1998：107-110.

[8]YU S， ZHAN Y， WANG Z，et al. Anti-collision algorithm based on jumping and dynamic searching and its analysis[J]. Computer engineering，2005，31(9)：19-20.

[9]LAW C，LEE K，SIU K Y. Efficient memoryless protocol for tag identification[C]//Proc. 4th International Workshop on Discrete Algorithms And Methods For Mobile Computing And Communications. New York：ACM，2000：75-84.

[10]BONUCCELLI M A，LONETTI F，MARTELLI F. Tree slotted ALOHA： a new protocol for tag identification in RFID networks[C]//Proc. 2006 International Symposium on World of Wireless，Mobile and Multimedia Networks. Buffalo-Niagara Falls，NY：IEEE，2006：603-608.

[11]RYU J，LEE H，SEOK Y，et al. A hybrid query tree protocol for tag collision arbitration in RFID systems[C]//IEEE International Conference on Communications，2007. Glasgow：IEEE，2007：5981-5986.

[12]JIA X，F(xiàn)ENG Q，MA C. An efficient anti-collision protocol for RFID tag identification[J]. Communications letters，2010，14(11)：1014-1016.

[13]JIA X L，F(xiàn)ENG Q Y. An improved anti-collision protocol for radio frequency identification tag[J]. International journal of communication systems，2015，28(3)：401-413.

[14]LIU X，QIAN Z，ZHAO Y，et al. An adaptive tag anti-collision protocol in RFID wireless systems[J]. Wireless communication over zigbee for automotive inclination measurement china communications，2014，11(7)：117-127.

[15]FORSTER R. Manchester encoding：opposing definitions resolved[J]. Engineering science & education journal，2000，9(6)：278-280.

[16]張學(xué)軍，蔡文琦，王鎖萍.改進(jìn)型白適應(yīng)多叉樹(shù)防碰撞算法研究[J]. 電子學(xué)報(bào)，2012，40(1)：193-198.

孫宇(1989— )，碩士生，主研通信系統(tǒng)、RFID防碰撞協(xié)議；

王玉皞(1977— )，博士生導(dǎo)師，主要研究方向?yàn)闊o(wú)線協(xié)作、通信系統(tǒng)、雷達(dá)通信一體化、RFID等；

李唯(1991— )，女，碩士生，主研RFID防碰撞協(xié)議；

鄧晟(1991— )，碩士生，主研電波傳播、信道參數(shù)估計(jì)、無(wú)源雷達(dá)。

責(zé)任編輯：時(shí)雯

8月24—27日，第二十五屆北京國(guó)際廣播電影電視展覽會(huì)(BIRTV2016)在北京中國(guó)國(guó)際展覽中心舉行。展會(huì)以“融合媒體 智慧廣電”為主題，匯聚了中外500多家參展商，展覽面積超過(guò)5萬(wàn)平方米。展會(huì)同期舉辦了專業(yè)論壇超10場(chǎng)，全面展示了廣電領(lǐng)域最新的技術(shù)和設(shè)備、傳統(tǒng)主流媒體創(chuàng)新業(yè)務(wù)及融合發(fā)展成果，并展望了廣電領(lǐng)域未來(lái)的發(fā)展方向。

Improved adaptive tag-reading algorithm in RFID system

SUN Yu，WANG Yuhao，LI Wei，DENG Sheng

(CollegeofInformationEngineering，NanchangUniversity，Nanchang330031，China)

A novel improved adaptive collision tree algorithm (IACT) is proposed for RFID tags-reading based on adaptive collision tree algorithm. The improved algorithm reduces idle time slots which occurs in adaptive collision tree algorithm (ACT) by optimizing the prefix-query. So， the proposed algorithm reduces the time complexity and improves the efficiency of recognition in RFID system. By mathematical analysis and simulation， it proves that the improved adaptive collision tree algorithm (IACT) has a better performance than adaptive collision tree algorithm (ACT) for RFID tags-reading.

RFID； tag-reading； anti-collision

TP39

A

10.16280/j.videoe.2016.09.028

2016-01-05

文獻(xiàn)引用格式：孫宇，王玉皞，李唯，等.改進(jìn)型RFID自適應(yīng)標(biāo)簽識(shí)別算法 [J].電視技術(shù)，2016，40(9)：137-142.

SUN Y，WANG Y H，LI W，et al.Improved adaptive tag-reading algorithm in RFID system[J].Video engineering，2016,40(9)：137-142.