張娜，王志勇*

（浙江理工大學(xué)信息學(xué)院，浙江杭州，310018）

一種自調(diào)整多叉樹RFID 多標(biāo)簽防碰撞算法

張娜，王志勇*

（浙江理工大學(xué)信息學(xué)院，浙江杭州，310018）

隨著RFID技術(shù)應(yīng)用領(lǐng)域的拓寬，有效地解決多標(biāo)簽碰撞問題是提高RFID系統(tǒng)性能的關(guān)鍵。在樹型搜索防碰撞算法分析的基礎(chǔ)上，提出一種自調(diào)整多叉樹防碰撞算法。該算法利用曼徹斯特編碼提取標(biāo)簽碰撞位，組合成新的標(biāo)簽序列號，然后閱讀器選取兩位序列號進(jìn)行異或運(yùn)算，并根據(jù)運(yùn)算結(jié)果自調(diào)整搜索樹的叉數(shù)搜索標(biāo)簽。該算法增加檢測命令，可以減少空時(shí)隙的數(shù)目，仿真實(shí)驗(yàn)表明，自調(diào)整多叉樹算法在閱讀器查詢次數(shù)、系統(tǒng)吞吐率和傳輸比特?cái)?shù)上比QT算法和改進(jìn)的四叉樹算法都有所提升，在多標(biāo)簽識別中更有競爭力。

RFID；防碰撞；多叉樹；自調(diào)整

引言

近年來，自動(dòng)識別方法在貨物銷售、企業(yè)生產(chǎn)和材料流通領(lǐng)域得到了快速的普及和推廣，射頻識別(Radio Frequency Identification，RFID)技術(shù)是一種先進(jìn)的自動(dòng)識別和數(shù)據(jù)采集技術(shù)。RFID技術(shù)具有讀取方便、識別速度快和安全性高等眾多優(yōu)點(diǎn)，對物聯(lián)網(wǎng)領(lǐng)域的進(jìn)步具有重要意義[1]。RFID系統(tǒng)一般有閱讀器、電子標(biāo)簽和天線組成。在RFID系統(tǒng)數(shù)據(jù)通信的過程中，經(jīng)常會(huì)有多個(gè)閱讀器或多個(gè)標(biāo)簽在同一場合中，就會(huì)造成標(biāo)簽之間或者閱讀器之間相互干擾，這種干擾被稱為碰撞[2],閱讀器自身解決碰撞性能強(qiáng)，多個(gè)閱讀器之間產(chǎn)生的碰撞相對多個(gè)標(biāo)簽之間產(chǎn)生的碰撞要容易解決。本文討論的是多個(gè)標(biāo)簽之間產(chǎn)生碰撞的問題，當(dāng)有多個(gè)標(biāo)簽在同一時(shí)間響應(yīng)閱讀器的信號，就會(huì)導(dǎo)致標(biāo)簽的信號相互干擾，不能被閱讀器成功識別，造成閱讀器和標(biāo)簽通信失敗。

目前解決標(biāo)簽碰撞問題主要采用時(shí)分多路法，該方法分為確定性算法和非確定性算法。ALOHA算法屬于非確定性算法[3]，純 ALOHA算法實(shí)現(xiàn)原理簡單，但是標(biāo)簽獲得處理時(shí)間不能掌控，如果一個(gè)標(biāo)簽連續(xù)發(fā)生碰撞，就會(huì)導(dǎo)致該標(biāo)簽處于一種“休眠”狀態(tài)[4]。王勇等[5]采用動(dòng)態(tài)自適應(yīng)的方式，根據(jù)標(biāo)簽估計(jì)算法得到預(yù)測因子，使幀長和未識別的標(biāo)簽數(shù)量相等，從而提高系統(tǒng)吞吐率，但是每次重新計(jì)算預(yù)測因子的過程比較繁瑣。文獻(xiàn)[6]中閱讀器對時(shí)隙進(jìn)行掃描之后，發(fā)送給每個(gè)標(biāo)簽，略去空時(shí)隙和碰撞時(shí)隙，加快識別標(biāo)簽的速度。二進(jìn)制樹搜索算法屬于典型的確定性算法[7]，閱讀器逐位劃分碰撞標(biāo)簽，縮小識別標(biāo)簽的數(shù)量，該算法識別成功率很高，但應(yīng)用起來比較慢。張學(xué)軍等[8]通過計(jì)算碰撞因子動(dòng)態(tài)的選擇搜索樹的叉數(shù)，從而減少產(chǎn)生空時(shí)隙，提高了標(biāo)簽識別效率。文獻(xiàn)[9]在QT算法的基礎(chǔ)進(jìn)行改進(jìn)，動(dòng)態(tài)地改變查詢前綴，減少碰撞次數(shù)和傳輸位數(shù)。

針對目前大部分防碰撞算法識別周期過長，存在過多的空時(shí)隙的問題，本文提出一種自調(diào)整多叉樹防碰撞方法，根據(jù)標(biāo)簽序列號異或運(yùn)算結(jié)果動(dòng)態(tài)地選擇二叉或四叉搜索樹識別標(biāo)簽，增加檢測指令，可以減少空時(shí)隙的數(shù)量和縮減閱讀器平均查詢次數(shù)，從而提高了系統(tǒng)的效率。

1 自調(diào)整多叉樹防碰撞算法

實(shí)現(xiàn)該算法需要能準(zhǔn)確地定位到發(fā)生碰撞位的位置,本文選用曼徹斯特編碼法，此編碼法時(shí)通過半個(gè)周期的電平變化來得到的，在半個(gè)位周期時(shí)的負(fù)跳變(即電平由1變?yōu)?)表示二進(jìn)制“1”，正跳變(即電平由0變?yōu)?)表示二進(jìn)制“0”。當(dāng)兩個(gè)標(biāo)簽同時(shí)發(fā)送的比特位不相同時(shí)，上升沿和下降沿會(huì)相互抵消，造成電平未發(fā)生變化，會(huì)被系統(tǒng)當(dāng)作錯(cuò)誤處理，所以閱讀器利用該錯(cuò)誤就可以判斷發(fā)生的具體位置。閱讀器利用曼徹斯特編碼檢測標(biāo)簽1和標(biāo)簽2碰撞位的示意圖如圖1所示，檢測出位置3和4為碰撞位。

圖1 曼徹斯特編碼檢測沖突示意圖

1.1 算法約定指令

為了便于描述算法，引入以下指令：

Request(prefix)請求指令，查詢前綴prefix由多個(gè)x組成，x∈{0,1}，滿足條件的標(biāo)簽響應(yīng)閱讀器的請求。

XOR(S)異或運(yùn)算指令，S為進(jìn)行異或運(yùn)算比特的位置，閱讀器發(fā)送XOR(S)命令，同一個(gè)標(biāo)簽的S和S+1位上的比特進(jìn)行異或運(yùn)算。

Push(prefix)入棧命令，將查詢前綴prefix放入堆棧中。

Pop出棧命令，將查詢前綴prefix從棧中取出。

Check(S)檢測命令，選取標(biāo)簽的S和S+1位的比特分別進(jìn)行異或運(yùn)算。

Choose(S)選擇指令，選取兩個(gè)查詢前綴。Verify(V)確認(rèn)指令，查看值為V的位置。

Read_Data讀取數(shù)據(jù)指令，讀取標(biāo)簽內(nèi)存儲(chǔ)的信息。

Select(UID)選擇指令，UID為每個(gè)標(biāo)簽擁有唯一的序列號，閱讀器發(fā)送選擇指令，序列號為SNR的標(biāo)簽將被選中。

Unselect(UID)取消指令，將序列號為 UID的標(biāo)簽舍去，讓標(biāo)簽進(jìn)入“休眠”狀態(tài)。

1.2 算法設(shè)計(jì)

首先，將閱讀器中的堆棧初始化為空，閱讀器發(fā)送查詢請求Request(111…111)，范圍內(nèi)標(biāo)簽響應(yīng)請求，如果沒有響應(yīng)，算法運(yùn)行結(jié)束，否則，標(biāo)簽將返回自身的序列號作為回應(yīng)。閱讀器根據(jù)曼徹斯特編碼將碰撞位置1，其他位置0，形成查詢序列號ID，并發(fā)送給標(biāo)簽，例如，a標(biāo)簽(10110101)、b標(biāo)簽(11010111)、c標(biāo)簽(10100111)、d標(biāo)簽(11000011)，閱讀器譯碼結(jié)果為1XXX0XX1，得到的查詢序列號ID為01110110，將查詢序列號發(fā)送給標(biāo)簽，標(biāo)簽接收到ID，與自身序列號進(jìn)行比對，提取出1對應(yīng)位的值，組合成標(biāo)簽新的 UID號。如上例，閱讀器發(fā)送ID(01110110)后，a、b、c和d標(biāo)簽分別得到新的序列號a(01110)、b(10111)、c(01011)、d(10001)。

得到新的標(biāo)簽后，閱讀器發(fā)送異或指令 XOR(S),標(biāo)簽的序列號S和S+1位上的比特進(jìn)行異或運(yùn)算，運(yùn)算結(jié)果如下：

a）如果只有0，閱讀器發(fā)送Push(00)和Push(11)命令。

b）如果只有1，閱讀器發(fā)送Push(01)和Push(10)命令。

c）如果即有1又有0，閱讀器發(fā)送Check(S)指令。

對于 a和 b種情況，閱讀器從堆棧中取出查詢前綴，發(fā)送Request(prefix)，如果只有一個(gè)標(biāo)簽響應(yīng)，說明在傳輸中沒有發(fā)生標(biāo)簽碰撞，則閱讀器選擇該標(biāo)簽，讀取標(biāo)簽內(nèi)的信息之后，發(fā)送Unselect命令，讓標(biāo)簽“睡眠”，不再響應(yīng)閱讀器的請求。如果發(fā)生碰撞，異或運(yùn)算位S后移兩位，閱讀器先判斷S和S+1位是否相等，如果相等，繼續(xù)后移兩位，如果不相等，讓其繼續(xù)進(jìn)行異或運(yùn)算，一直循環(huán)，直到堆棧為空，標(biāo)簽識別完成。

對于c種情況，算法增加了檢測機(jī)制，因?yàn)槌霈F(xiàn)既有1和0的有很多種組合，例如11、10、01的組合，00、01、11的組合，11、01的組合等等，經(jīng)過異或運(yùn)算得到的值既有0又有1。為了避免此種情況的發(fā)生，閱讀器先發(fā)送Check(S)命令，讓標(biāo)簽的S和S+1位上的比特分別進(jìn)行異或運(yùn)算。如果運(yùn)算結(jié)果都為1，則將查詢前綴 00、01、10、11全部壓入堆棧。如果運(yùn)算結(jié)果兩個(gè)值不相等，則發(fā)送Choose(S)確認(rèn)指令，查看Check(S)運(yùn)算結(jié)果為0位上的值等于多少，

a）如果為0，發(fā)送Push(00)命令。

b）如果為1，發(fā)送Push(11)命令。發(fā)送 Verify(V)確認(rèn)指令，查看 Check(S)運(yùn)算得到的值為 1的位置，

a）如果在S位，發(fā)送Push(10)命令。

b）如果在S+1位，發(fā)送Push(01)命令。

例如a(01110)和c(01011)在查詢前綴01節(jié)點(diǎn)發(fā)生了碰撞，S和 S + 1(S=2)位的數(shù)值為11和01，異或運(yùn)算得到的結(jié)果既有0又有1，執(zhí)行Check(S)指令之后，發(fā)現(xiàn)S和S+1位上的值不相等，則繼續(xù)發(fā)送Choose (S)指令和Verify(V)指令，發(fā)現(xiàn)0位上的值為1且在S+1位上，則只將查詢前綴11和10壓入堆棧中，舍棄00和 01，這樣可以避免多產(chǎn)生兩個(gè)空時(shí)隙，提高了系統(tǒng)識別準(zhǔn)確率。算法流程如圖2所示。

圖2 算法流程圖

2 算法性能分析

本文從閱讀器查詢次數(shù)、吞吐率和通信復(fù)雜度三個(gè)方面分析算法的性能。

2.1 閱讀器查詢次數(shù)

閱讀器查詢次數(shù)的多少可以反映算法識別標(biāo)簽的效率的高低，對閱讀器范圍內(nèi)的n個(gè)標(biāo)簽的查詢過程可以用一棵二叉和四叉組合樹的方式來表示，成功識別的標(biāo)簽對應(yīng)組合樹的葉子節(jié)點(diǎn)，發(fā)生碰撞的標(biāo)簽對應(yīng)組合樹的內(nèi)部節(jié)點(diǎn)(除去葉子節(jié)點(diǎn)的其他節(jié)點(diǎn))，對標(biāo)簽的搜索類似于對組合樹的遍歷過程。閱讀器每次選取標(biāo)簽序列號的兩位進(jìn)行異或運(yùn)算，根據(jù)運(yùn)算結(jié)果選擇二叉樹或者四叉樹搜索標(biāo)簽。

（a）當(dāng)進(jìn)行異或運(yùn)算的比特位為00、01、10、11中的任意三個(gè)組合時(shí)，共有種情況；

（b）當(dāng)異或運(yùn)算為00、01、10、11時(shí)，此時(shí)產(chǎn)生0個(gè)空節(jié)點(diǎn)，共1種情況；

在（a）和（b）種情形下，閱讀器會(huì)選擇四叉樹進(jìn)行搜索標(biāo)簽，但（a）情況會(huì)產(chǎn)生一個(gè)空節(jié)點(diǎn)。

（c） 當(dāng)進(jìn)行異或運(yùn)算的查詢前綴為00和11的組合或者01和10的組合，經(jīng)過閱讀器的異或運(yùn)算之后，選擇二叉樹查詢；

（d）當(dāng)00與10、00與01、11與01、11與10的組合，經(jīng)過閱讀器運(yùn)算之后，會(huì)出現(xiàn)既有0又有1的情況，開始會(huì)選擇四叉樹查詢，但是經(jīng)過檢測命令(check)檢測之后，最終還是選擇二叉樹搜索。

所以（c）和（d）共有六種情況會(huì)選擇二叉樹搜索。所以選擇二叉樹查詢的概率為6/11，選擇四叉樹查詢的概率為5/11，設(shè)總的查詢次數(shù)為N，產(chǎn)生四叉樹的節(jié)點(diǎn)為n4，產(chǎn)生二叉樹的節(jié)點(diǎn)為 n2，葉子節(jié)點(diǎn)(標(biāo)簽被成功識別)為 n0，空節(jié)點(diǎn)為 nk。則N=n4+n2+n0+nk,即得到

2.2 吞吐率

RFID系統(tǒng)的吞吐率為標(biāo)簽的數(shù)量比上閱讀器發(fā)送的查詢命令次數(shù)[10]，即

依照這個(gè)吞吐率的標(biāo)準(zhǔn)，自調(diào)整多叉樹RFID多標(biāo)簽防碰撞算法吞吐率的表達(dá)式為

2.3 通信復(fù)雜度

通信復(fù)雜度是系統(tǒng)執(zhí)行效率的另一個(gè)重要指標(biāo)，是完成所有標(biāo)簽的識別，閱讀器和標(biāo)簽之間傳輸?shù)目偙忍財(cái)?shù)，用C(n)表示，n為標(biāo)簽的個(gè)數(shù)，閱讀器在獲得標(biāo)簽新的序列號之前，信道傳輸?shù)谋忍財(cái)?shù)用 L1表示，閱讀器獲得標(biāo)簽新的序列號之后，信道傳輸?shù)谋忍財(cái)?shù)用L2表示，則

為了將標(biāo)簽的碰撞位提取出來，組合成新的標(biāo)簽序列號，閱讀器首先發(fā)送一個(gè)和標(biāo)簽序列號長度相等的查詢命令，范圍內(nèi)的n個(gè)標(biāo)簽返回自身的序列號，長度為k，閱讀器收到標(biāo)簽的序列號之后，將碰撞位置“1”，其他位置“0”，形成和標(biāo)簽長度k相等的查詢序列號，標(biāo)簽接收到查詢序列號，提取自身序列號和查詢序列號為“1”對應(yīng)的標(biāo)簽位，并返回給閱讀器，假設(shè)新標(biāo)簽的長度用 knew表示，在最優(yōu)的情況下knew為Integ(lbn)位(n代表標(biāo)簽的個(gè)數(shù))，最差的情況和原來長度 k相等，所以形成新標(biāo)簽位數(shù)的區(qū)間為[Integ(lbn),k][11]，此時(shí)在信道上傳輸?shù)谋忍亻L度為L1，則

提取標(biāo)簽碰撞位完成之后，閱讀器發(fā)送異或運(yùn)算指令，根據(jù)運(yùn)算結(jié)果選擇二叉樹或者四叉樹搜索，閱讀器發(fā)送的查詢前綴和標(biāo)簽返回的序列號之和等于新的標(biāo)簽序列號長度knew，

用Lcom表示閱讀器發(fā)送的平均指令長度，由上文對閱讀器查詢次數(shù)的分析，傳輸?shù)谋忍財(cái)?shù)L2為，

由公式(4)、(5)和(6)可得，

3 實(shí)驗(yàn)仿真與分析

實(shí)驗(yàn)選取自調(diào)整多叉樹算法、查詢樹算法、一種改進(jìn)的四叉樹RFID防碰撞算法[12]在軟件Matlab上進(jìn)行仿真，標(biāo)簽序列號由16位二進(jìn)制數(shù)組成，標(biāo)簽的數(shù)量n從0增加到2000，實(shí)驗(yàn)結(jié)果取 50次的均值。分別取標(biāo)簽序列號長度 k的值為Integ(lbn)、(Integ(lbn)+k)/2和k時(shí)，閱讀器查詢次數(shù)、吞吐率、傳輸?shù)谋忍財(cái)?shù)和標(biāo)簽個(gè)數(shù)的關(guān)系圖。

三種算法的閱讀器查詢次數(shù)隨著標(biāo)簽數(shù)量的變化如圖3所示，從圖中可知，隨著標(biāo)簽數(shù)量從 0增加到2000，三種算法的閱讀器查詢次數(shù)也都相應(yīng)地在增多，QT算法增長的幅度尤為明顯，改進(jìn)的四叉樹算法所需的平均搜索次數(shù)始終多于自調(diào)整多叉樹算法。當(dāng)圖(a)中標(biāo)簽數(shù)量等于400時(shí)，QT算法的搜索次數(shù)約是本算法查詢次數(shù)的三倍，改進(jìn)的四叉樹算法也比本算法多200多次查詢，產(chǎn)生此結(jié)果的原因很可能是由于改進(jìn)的四叉樹RFID算法每次都是通過匹配對比矩陣中的四個(gè)比特?cái)?shù)(00、01、10、11)，來選擇搜索路徑，隨著標(biāo)簽數(shù)目的減少，產(chǎn)生的空時(shí)隙的數(shù)目就會(huì)增多，而本算法通過檢測指令，成功避免了產(chǎn)生2個(gè)及以上的空時(shí)隙，提高了搜索的準(zhǔn)確性。

圖3 本算法與QT算法、改進(jìn)的四叉樹算法閱讀器查詢次數(shù)的比較

圖4是自調(diào)整多叉樹算法和QT算法以及改進(jìn)的四叉樹算法吞吐率的比較，從圖中可以看出，本算法在吞吐率上明顯優(yōu)于其他兩種算法，在圖(a)中隨著標(biāo)簽數(shù)目的增多，自調(diào)整多叉樹算法吞吐率維持在0.55左右，而改進(jìn)的四叉樹算法在0.5左右，當(dāng)標(biāo)簽的數(shù)量達(dá)到 1000左右時(shí)候，吞吐率下降較為明顯。其中 QT算法的吞吐率最低，這很可能是由于QT算法中閱讀器每次收到標(biāo)簽碰撞，就將查詢前綴分別加上“0”和“1”，繼續(xù)查詢，直到?jīng)]有發(fā)生碰撞，才成功識別標(biāo)簽。隨標(biāo)簽的數(shù)目增多，逐位的查詢，發(fā)生碰撞的概率很高，導(dǎo)致QT算法的吞吐率較低。

圖4 本算法與FSA、改進(jìn)的四叉樹算法吞吐率的比較

圖5是自調(diào)整多叉樹算法和QT算法以及改進(jìn)四叉樹算法傳輸總比特?cái)?shù)的比較，從圖(a)中可以發(fā)現(xiàn)，當(dāng)標(biāo)簽的序列號長度為Integ(lbn)時(shí)，自調(diào)整多叉樹算法傳輸?shù)谋忍財(cái)?shù)要少于另外兩種算法，這是因?yàn)楸舅惴ㄍㄟ^曼徹斯特編碼提取標(biāo)簽的碰撞位，組合成新的標(biāo)簽序列號，在識別過程中，減少傳輸?shù)谋忍財(cái)?shù)的位數(shù)。當(dāng)標(biāo)簽的序列號長度等于k時(shí)，傳輸?shù)谋忍財(cái)?shù)和改進(jìn)的四叉樹算法相當(dāng)，但在一般情況下，經(jīng)過曼徹斯特編碼之后，得到新的標(biāo)簽序列號長度要少于原標(biāo)簽序列號的長度，所以傳輸?shù)谋忍財(cái)?shù)也會(huì)相應(yīng)的減少。

圖5 本算法與QT算法、改進(jìn)的四叉樹算法傳輸比特?cái)?shù)的比較

通過對實(shí)驗(yàn)結(jié)果進(jìn)行分析比較，自調(diào)整多叉樹防碰撞算法在閱讀器查詢次數(shù)、系統(tǒng)吞吐率和傳輸?shù)谋忍財(cái)?shù)上都要優(yōu)于另外兩種算法，在解決標(biāo)簽防碰撞問題更有優(yōu)勢。

4 結(jié)束語

本文在以多叉樹搜索標(biāo)簽為基礎(chǔ)，通過提取標(biāo)簽序列號中發(fā)生碰撞的比特位，組合成新的標(biāo)簽序列號，舍去多余的比特位，減少了閱讀器和標(biāo)簽通信時(shí)傳輸比特的位數(shù)。執(zhí)行 XOR(S)和Check(S)指令，動(dòng)態(tài)的選擇多叉樹識別標(biāo)簽，減少了空時(shí)隙的數(shù)目，提高系統(tǒng)的識別效率。通過實(shí)驗(yàn)仿真和性能分析，該算法在系統(tǒng)吞吐率、閱讀器比較次數(shù)和傳輸比特?cái)?shù)上更有優(yōu)勢。在后續(xù)的研究中，可以根據(jù)標(biāo)簽序列號的特征進(jìn)行動(dòng)態(tài)地分組，降低發(fā)生標(biāo)簽碰撞的概率，使系統(tǒng)性能更加優(yōu)越。

[1]蘇忠根. 射頻識別天線蝕刻技術(shù)工藝流程及其精益化管理研究[J].科技管理研究,2014,34(1)： 218-223.

[2]康東. 射頻識別 (RFID) 核心技術(shù)與典型應(yīng)用開發(fā)案例[M]. 人民郵電出版社,2008.

[3]邢志鵬,楊恒新,張昀. 分段式位隙分組幀時(shí)隙Aloha算法[J]. 計(jì)算機(jī)技術(shù)與發(fā)展,2016,26(4)： 31-35.

[4]Hwang T W,Lee B G,Kim Y S,et al. Improved Anti-collision Scheme for High Speed Identification in RFID System[C]// International Conference on Innovative Computing,Information and Control. IEEE Computer Society,2006： 449-452.

[5]王勇,李婷. 改進(jìn)的基于ALOHA的RFID防碰撞算法[J]. 電信科學(xué),2016,32(8)： 77-81.

[6]張小紅,胡應(yīng)夢. 分組自適應(yīng)分配時(shí)隙的 RFID防碰撞算法研究[J].電子學(xué)報(bào),2016,44(6)： 1328-1335.

[7]Park J,Min Y C,Lee T J. Identification of RFID Tags in Framed-Slotted ALOHA with Robust Estimation and Binary Selection[J].Communications Letters IEEE,2007,11(5)： 452-454.

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

[9]肖菲,楊恒新,劉蕾蕾. 一種改進(jìn)的二進(jìn)制查詢樹RFID標(biāo)簽防碰撞算法[J]. 計(jì)算機(jī)技術(shù)與發(fā)展,2014(6)： 92-94.

[10]吳楠. 一種樹型結(jié)構(gòu)的RFID防碰撞算法研究[D]. 吉林大學(xué),2014.

[11]Cover T M,Thomas J A. Elements of information theory (2. ed.)[M]//Elements of information theory /. Wiley,2006： 1600-1601.

[12]孫耀磊,吳曉波,陳元文,等. 一種改進(jìn)的四叉樹 RFID 防碰撞算法[J]. 計(jì)算機(jī)工程與應(yīng)用,2014,50(4)： 63-68.

Anti-Collision Algorithm based on Self-adjusting Multi-tree For RFID Multi-Tag

ZHANG Na,WANG Zhiyong*
(School of Information Science and Technology,Zhejiang Sci-Tech University,Hangzhou 310018,China)

With the expansion of RFID technology applications,effectively solve the multi-label collision problem is to improve the performance of RFID system key. Based on the analysis of anti - collision algorithm of tree search,a self - adjusting multi - tree anti - collision algorithm is proposed. The algorithm uses the Manchester code to extract the label collision bits,and then combines the new tag serial number,and then the reader selects the two-bit serial number to XOR and transfers the data according to the result of the operation. By increasing the detection command,the system can achieve the effect of reducing the number of empty slots. The simulation results show that the self -adjusting multi - tree algorithm has improved the number of times of reader query,system throughput and transmission bits than QT algorithm and improved quadtree algorithm,and it is more competitive in multi - tag recognition.

RFID; collision; multi-tree; self-adjusting

TN92

A

1672-9129(2017)06-0004-04

10.19551/j.cnki.issn1672-9129.2017.06.002

張娜,王志勇. 一種自調(diào)整多叉樹RFID多標(biāo)簽防碰撞算法[J]. 數(shù)碼設(shè)計(jì),2017,6(6)： 4-7.

Cite：ZHANG Na,WANG Zhiyong. Anti-Collision Algorithm based on Self-adjusting Multi-tree For RFID Multi-Tag[J]. Peak Data Science,2017,6(6)： 4-7.

2017-02-11；

2017-03-06。

浙江省重大科技專項(xiàng)重點(diǎn)工業(yè)項(xiàng)目： 面向公共安全的智能監(jiān)控平臺(tái)關(guān)鍵技術(shù)研究與示范(2014C01047)；國家自然科學(xué)基金（61502430）；浙江理工大學(xué)“521人才培養(yǎng)計(jì)劃”。

張娜(1977—)，女，浙江杭州人，副教授，碩士，主要從事自適應(yīng)軟件、軟件測試與智能信息處理方面的研究。王志勇(1992—)，男，安徽池州人，碩士研究生，研究的方向?yàn)槲锫?lián)網(wǎng)技術(shù)。

E-mail:wzystxk@163.com