胡應(yīng)夢，張小紅

(江西理工大學(xué)信息工程學(xué)院,江西贛州 341000)

?

基于信息位編碼的自適應(yīng)搜索RFID防碰撞算法研究

胡應(yīng)夢，張小紅

(江西理工大學(xué)信息工程學(xué)院,江西贛州 341000)

無線射頻識別(RFID)技術(shù)可實現(xiàn)對目標(biāo)物體的自動識別.為了減少對物體標(biāo)簽識別時間，提出一種基于信息位編碼的自適應(yīng)搜索的防碰撞(AS)算法.讀寫器充分利用碰撞位信息，要求標(biāo)簽返回碰撞位編碼信息，進(jìn)而自適應(yīng)地生成有效查詢前綴，對標(biāo)簽進(jìn)行無空閑時隙識別，以減少查詢次數(shù)，提高算法的性能.此外，AS算法也解決了讀寫器與標(biāo)簽通信中傳輸信息冗余等問題.本文通過理論分析證明了該算法的有效性，其中吞吐率的理論值與實驗值的誤差不超過5%，還從時間復(fù)雜度和通信復(fù)雜度對該算法進(jìn)行了詳細(xì)地分析.仿真結(jié)果表明：AS算法不僅提高了系統(tǒng)的性能，而且還降低了標(biāo)簽?zāi)芰康南?特別是當(dāng)標(biāo)簽數(shù)為1000時，該算法的吞吐率仍保持在61%左右，比查詢樹算法和自適應(yīng)多叉樹算法的系統(tǒng)效率分別提高了72%和20.1%左右.

射頻識別；防碰撞；信息位編碼；自適應(yīng)；空閑時隙

電子學(xué)報URL:http://www.ejournal.org.cn DOI:10.3969/j.issn.0372-2112.2016.08.003

1 引言

射頻識別(Radio Frequency Identification，RFID)技術(shù)[1]是一種以電磁波為傳輸媒介的非接觸式自動識別技術(shù)，是物聯(lián)網(wǎng)感知層的關(guān)鍵技術(shù)之一.其基本原理是利用射頻信號的空間耦合(電感或電磁耦合)或反射的傳輸特性來傳遞信息，以實現(xiàn)快速識別目標(biāo)或數(shù)據(jù)交換的目的[2].與傳統(tǒng)的識別技術(shù)相比，RFID技術(shù)具有操作簡單、抗干擾性強、能識別高速運動的物體以及可適應(yīng)于惡劣環(huán)境等多方面的優(yōu)點，在物流、跟蹤、定位、工業(yè)自動化以及交通運輸控制管理等領(lǐng)域已得到廣泛應(yīng)用.因此，被列為21世紀(jì)最有發(fā)展前途的信息技術(shù)之一[3].

通常RFID系統(tǒng)通常由電子標(biāo)簽(Tag)、讀寫器(Reader)和后端數(shù)據(jù)庫(Database)三大部分組成.其中電子標(biāo)簽可分為有源標(biāo)簽和無源標(biāo)簽[4]，由于成本等各因素的限制，大多數(shù)RFID系統(tǒng)均采用無源標(biāo)簽，即被動標(biāo)簽，其所需能量完全由讀寫器發(fā)送的電磁波提供.當(dāng)多個標(biāo)簽在同一時刻響應(yīng)讀寫器的命令時，信號之間就會相互干擾，導(dǎo)致讀寫器無法準(zhǔn)確地讀取數(shù)據(jù)，這種現(xiàn)象成為標(biāo)簽碰撞[5].因此，如何有效快速地識別標(biāo)簽一直都是RFID技術(shù)的主要研究方向，也是物聯(lián)網(wǎng)技術(shù)領(lǐng)域中一個研究的熱點.

RFID系統(tǒng)必須采用一定的策略或算法來避免碰撞現(xiàn)象的發(fā)生，即控制標(biāo)簽的響應(yīng)時序逐個與讀寫器進(jìn)行通信，并在一定時間內(nèi)完成對所有標(biāo)簽的識別.為此，國內(nèi)外的學(xué)者在關(guān)于多標(biāo)簽與讀寫器的碰撞問題方面已經(jīng)做了大量的研究[6～8].這些防碰撞的算法主要分為兩大類：一種是基于時隙隨機分配的ALOHA算法，也稱為不確定性算法；如時隙ALOHA算法[9]、幀時隙ALOHA算法[10]、動態(tài)幀時隙ALOHA算法[11]以及Q算法[12]等，這些算法均采用碰撞則退避重傳的基本思想，所以其實現(xiàn)過程相對比較簡單.但是，隨著標(biāo)簽數(shù)目的增加，其性能急劇惡化，研究者們又相繼提出增強的動態(tài)幀時隙算法[13]、分組動態(tài)幀時隙ALOHA算法[14]等.雖然這些算法使系統(tǒng)的性能有所改善，但該類算法具有一定的隨機性，可能存在單個或多個標(biāo)簽在很長的一段時間內(nèi)均無法被成功識別，即出現(xiàn)標(biāo)簽“饑餓”問題.

另外一種則是基于二進(jìn)制搜索的確定型算法，其代表算法有二進(jìn)制搜索(Binary Search,BS)算法[15]、動態(tài)二進(jìn)制搜索(Dynamic Binary Search,DBS)算法[16]以及跳躍式動態(tài)樹(Jumping and Dynamic Searching,JDS)算法[17]，查詢樹(Query Tree,QT)算法[18]，四叉樹(4-ary Query Tree,4QT)算法[19]以及自適應(yīng)多叉樹防碰撞(Adaptive Multi-tree Search,AMS)算法[20]等.其中，BS算法是通過多次比較，不斷減少響應(yīng)標(biāo)簽的數(shù)目，直至對剩下唯一的標(biāo)簽進(jìn)行識別；DBS算法則可以動態(tài)的調(diào)整讀寫器查詢命令和標(biāo)簽反饋信息的ID長度；而JDS算法是基于以上兩種算法的改進(jìn)，不是從根節(jié)點開始重新查詢，而是退到它的上一層節(jié)點即父節(jié)點繼續(xù)查詢，以減少算法的時間復(fù)雜度.QT算法則對標(biāo)簽的要求相對比較簡單，標(biāo)簽不需要具有任何記憶功能，從而降低了標(biāo)簽的制作成本.其缺點就是識別的時間較長，吞吐率很低.4QT算法雖然減少了碰撞時隙，同時也增加了空閑時隙.而AMS算法則是這兩種算法的結(jié)合，通過引入碰撞因子，讓讀寫器調(diào)整分叉數(shù)以提高系統(tǒng)的性能.但是這些算法識別時間相對比較長，讀寫器與標(biāo)簽之間的數(shù)據(jù)通信量比較大，其吞吐率只有50%左右.

現(xiàn)有的RFID防碰撞算法或多或少存在一些如算法操作復(fù)雜、對標(biāo)簽計算能力要求高、發(fā)送數(shù)據(jù)冗余等缺點，本文在總結(jié)前人許多經(jīng)典算法的基礎(chǔ)上，提出一種基于信息位編碼的自適應(yīng)搜索RFID防碰撞算法(Adaptive Searching,AS).AS算法利用Manchester特性，可以獲得所有標(biāo)簽碰撞位的信息，并要求標(biāo)簽返回碰撞位編碼信息，讀寫器收到消息后，從而生成有效查詢前綴，對標(biāo)簽直接進(jìn)行查詢；標(biāo)簽則只需發(fā)送序列號中與前綴互補的部分.這樣不僅減少了碰撞時隙，而且還將空閑時隙減少至零，同時也降低了系統(tǒng)的通信量，減少了對標(biāo)簽?zāi)芰康南?，更適合低成本的RFID系統(tǒng).

2 AS算法設(shè)計

2.1 基本思想

無論是Q算法，四叉樹搜索算法還是AMS算法，其基本思想都是一旦檢測到最高碰撞位，則按照固定的模式生成前綴，然后依次發(fā)送這些前綴對標(biāo)簽進(jìn)行查詢.由于讀寫器不知道標(biāo)簽碰撞位的具體信息，只能不斷地從堆棧中取出查詢前綴，盲目地對標(biāo)簽進(jìn)行查詢，就會不可避免地產(chǎn)生大量的空閑時隙，最終影響系統(tǒng)的性能.

為了讓讀寫器獲得碰撞位信息，標(biāo)簽需將前4bit(后文會解釋其原因)碰撞位信息進(jìn)行相應(yīng)的編碼，如表1所示.讀寫器利用Manchester的特性，檢測出碰撞位的信息.如果僅有1bit發(fā)生碰撞，則將該碰撞位分別置0,1，生成兩個新前綴，并將其壓入讀寫器Stack堆棧中；反之，則將最高碰撞位之前的信息發(fā)給標(biāo)簽，標(biāo)簽收到消息后，與自身的ID進(jìn)行對比.如果相同，則將后續(xù)4bit(從最高碰撞位開始)進(jìn)行編碼，并將編碼信息返回給讀寫器.否則，標(biāo)簽不應(yīng)答.由于編碼之后的16bit中只有1bit是1，其他均為0，所以無論是哪幾種情況發(fā)生碰撞，讀寫器均能準(zhǔn)確無誤的將原碰撞信息解碼出來，最后生成相應(yīng)的前綴，壓入堆棧中.

2.2 AS算法約定

為了實現(xiàn)這個算法，定義以下三個命令來描述該算法，假設(shè)參數(shù)M為查詢前綴，n為檢測到的最高沖突位.

(1)請求命令Request(M)：從讀寫器Stack堆棧中取出一個查詢前綴M，以廣播的形式發(fā)送給標(biāo)簽，標(biāo)簽接收到該命令后，與自身的序列號進(jìn)行對比，若相同，則返回應(yīng)答信息；否則，不應(yīng)答.

(2)返回碰撞信息命令Call(M,n)：標(biāo)簽接收到該命令，將自身的序列號ID與讀寫器發(fā)送的信息M進(jìn)行比較，若標(biāo)簽自身ID前綴部分與M一致，則該標(biāo)簽將碰撞位前四位的信息(第n位至第n-3位)進(jìn)行編碼后返回給讀寫器.

(3)休眠命令Sleep()：標(biāo)簽接收到該指令后，將自身的序列號ID與接收到的信息進(jìn)行比較，若兩者相同，則該標(biāo)簽進(jìn)入休眠狀態(tài)，并且以后都不再應(yīng)答Request(M)指令.

表1 AS信息位編碼規(guī)則

2.3 AS算法流程

AS算法是一種基于編碼技術(shù)的防碰撞算法，首先通過Manchester獲得碰撞位的相關(guān)信息，然后標(biāo)簽利用編碼的原理，將編碼后的碰撞位信息返回給讀寫器，讀寫器經(jīng)過反編碼即可獲得有效查詢前綴，對標(biāo)簽進(jìn)行有效的識別，以減少查詢次數(shù)，提高算法的性能.其協(xié)議流程如圖1所示，具體步驟如下：

步驟1 初始化，將讀寫器Stack堆棧清空，并把空字符串NULL壓入堆棧中，要求在其作用范圍內(nèi)的標(biāo)簽處于待命狀態(tài).

步驟2 讀寫器從堆棧中取出棧首元素，并以廣播的方式發(fā)送給標(biāo)簽，與查詢前綴相匹配的標(biāo)簽響應(yīng)，并且返回各自ID中與查詢前綴互補的部分.如果讀寫器是首次查詢，則發(fā)送Request(NULL)命令，要求標(biāo)簽返回其自身完整的ID；如果堆棧為空，則跳轉(zhuǎn)至步驟7.

步驟3 讀寫器收到標(biāo)簽返回的信息后，首先利用Manchester原理定位到最高碰撞位n的位置，然后對n進(jìn)行判斷：

(1)如果n<4，則將第n位分別置0,1，生成兩個新的查詢前綴并壓入堆棧中，返回步驟2；

(2)否則，轉(zhuǎn)入步驟4.

步驟4 讀寫器根據(jù)響應(yīng)標(biāo)簽的數(shù)量進(jìn)行如下處理：

(1)如果只有一個標(biāo)簽響應(yīng)，則直接讀出該標(biāo)簽的數(shù)據(jù)，并發(fā)送Sleep()命令，讓其進(jìn)入休眠狀態(tài)，不再參與后面的查詢；

(2)如果有兩個或兩個以上的標(biāo)簽，則需進(jìn)一步判斷：

(a)如果僅有1bit發(fā)生碰撞，則將相應(yīng)的碰撞位分別置0,1，生成兩個前綴并壓入堆棧中，返回步驟2；

(b)如果碰撞位是2bit或2bit以上，則讀寫器以廣播的方式發(fā)送Call(M,n)命令，要求條件符合的標(biāo)簽返回其碰撞位信息，轉(zhuǎn)入步驟5；

步驟5 標(biāo)簽收到M消息后，與自身的ID前綴進(jìn)行對比，如果一致，則將第n位至第n-3位的信息進(jìn)行相應(yīng)的編碼，并返回給讀寫器；否則，標(biāo)簽不應(yīng)答，等待下一次查詢；

步驟6 讀寫器收到編碼信息后，通過解碼即可獲得標(biāo)簽產(chǎn)生碰撞的具體信息，進(jìn)而生成有效查詢前綴并且壓入堆棧中；

步驟7 判斷堆棧是否為空，如果為空，則識別過程結(jié)束；否則，返回步驟2，取出棧首元素，重復(fù)上述過程直至將所有標(biāo)簽識別完.

下面通過一個例子來說明AS算法識別的過程，假設(shè)有5個標(biāo)簽，其ID分別為a：11110010，b：11110000，c：11010111，d：11001101，e：11001110.識別過程如表2所示，讀寫器首先發(fā)送Request(NULL)命令，所有標(biāo)簽返回其ID，此時讀寫器收到的信息為11××××××，即可得知最高碰撞位n=6>4，并且是多比特發(fā)生碰撞，所以讀寫器發(fā)送Call(11，6)命令，要求前綴為11的標(biāo)簽將其ID上的第6至第3位的數(shù)據(jù)進(jìn)行編碼并返回給讀寫器.然后讀寫器收到的碰撞反饋信息為000×000000×0×000，由表1，即可通過反編碼獲得產(chǎn)生碰撞的具體信息分別為1100，0101，0011，將它們添加在前一次查詢的前綴后面，形成新的查詢前綴110011，110101，111100，并將它們壓入堆棧中.在下一個時隙，讀寫器首先提取棧首元素110011發(fā)送給標(biāo)簽，標(biāo)簽的d，e響應(yīng)，將剩余的第1,2位數(shù)據(jù)信息作為應(yīng)答信號返回給讀寫器.讀寫器收到信息后，即可定位到此次最高碰撞位為n=2<4，將第2位分別置0,1，生成兩個前綴1100110，1100111壓入堆棧中，在下一次查詢中可將d，e分別識別出來.同理從堆棧中取出查詢前綴110101可直接識別出標(biāo)簽c，雖然取出前綴為111100時，標(biāo)簽a，b產(chǎn)生了碰撞，但由于只有1bit發(fā)生碰撞，因此只需要將最高碰撞位n=2分別置0,1即可識別出標(biāo)簽a，b.

表2 AS算法舉例識別過程

注：其中“×”表示碰撞，“/”表示沒有，“?”表示堆棧是空的.

3 AS算法性能分析

AS算法繼承了QT算法和AMS算法的優(yōu)點，即標(biāo)簽不需要存儲以前的查詢情況，同時在它們的基礎(chǔ)上還加以改進(jìn).AS算法不僅僅只有二、四兩種固定分支的選擇，它會隨著標(biāo)簽ID的分布情況，自適應(yīng)地分配多叉樹，生成有效查詢前綴，從而提高算法的性能.下面，對AS算法的時隙情況進(jìn)行分析.

3.1 多叉樹的各時隙數(shù)分析

假設(shè)標(biāo)簽的數(shù)目為m，L表示是在的層數(shù)，B為多叉樹使用的叉樹(B=2,4,8,…).對于一棵滿B叉樹，有k個標(biāo)簽同時在第L層選擇相同的節(jié)點響應(yīng)，其概率服從二項分布：

(1)

由此可得m個標(biāo)簽在第L層出現(xiàn)空閑的概率為：

(2)

標(biāo)簽成功識別的概率為：

(3)

標(biāo)簽出現(xiàn)碰撞的概率為：

p(k>1/m,L) =1-p(0/m,L)-p(1/m,L)

=1-(1-B-L)m-mB-L(1-B-L)m-1

(4)

各標(biāo)簽ID上的取值是相互獨立且符合二項分布，兩標(biāo)簽中任意一位不發(fā)生碰撞的概率為：

(5)

兩標(biāo)簽中任意一位發(fā)生碰撞的概率為：

(6)

假設(shè)標(biāo)簽ID的長度為D，則兩標(biāo)簽中只有1bit發(fā)生碰撞的概率為[21]：

(7)

令qL,i/m表示在第L層中第i個節(jié)點被訪問的概率，則q0,i/m=1，這是因為算法每次開始搜索均是從根節(jié)點出發(fā).除根節(jié)點外，如果要訪問某個節(jié)點，其前提條件是該節(jié)點的父節(jié)點必須產(chǎn)生碰撞.為了便于敘述，又設(shè)變量ξL,i/m為在第L層中第i個節(jié)點發(fā)生碰撞的概率.其中，

ξL,i/m=ξL/m=p(k>1/m,L)

(8)

(9)

因此，滿B叉樹的時隙總數(shù)應(yīng)該為所有被訪問節(jié)點之和，結(jié)合式(4)、(8)、(9)可得：

(10)

碰撞時隙數(shù)為：

(11)

空閑時隙數(shù)為：

(12)

將B=16代入式(10)，(11)，(12)，標(biāo)簽的數(shù)目由0增至1000，通過Matlab軟件仿真，如圖2所示.

由圖2可知t(m)，c(m)，i(m)與標(biāo)簽數(shù)目m呈線性增長的關(guān)系，為了計算更為精確，本文將其擬合為二次函數(shù)曲線：

t(m)=-0.001m2+6.9m-120

(13)

i(m)=-0.00093m2+5.5m-110

(14)

c(m)=-6.2×10-5m2+0.43m-7.4

(15)

3.2 AS算法的各時隙數(shù)分析

由于AS算法是采用4bit編碼，故可認(rèn)為是在16叉樹算法上的優(yōu)化.當(dāng)讀寫器檢測到只有1bit發(fā)生碰撞時，讀寫器不需要標(biāo)簽返回碰撞位信息，直接將碰撞位分別置0,1，在下一個時隙即可直接識別這兩個標(biāo)簽.設(shè)在識別過程中只有1比特發(fā)生碰撞的標(biāo)簽數(shù)為G(m).

(16)

AS算法雖然避免了空閑時隙的產(chǎn)生，然而，當(dāng)碰撞位n>4且為多位發(fā)生碰撞時，讀寫器需要發(fā)送Call命令以獲得標(biāo)簽碰撞位的具體信息，進(jìn)而確定存在標(biāo)簽之中有效前綴.令F(m)表示讀寫器發(fā)送Call命令的次數(shù)，則

-D×2-D]

(17)

當(dāng)讀寫器檢測到碰撞位n<4時，不足以進(jìn)行四位編碼，為了減少標(biāo)簽的計算復(fù)雜度，協(xié)議規(guī)定將最高碰撞位分別置0,1，生成兩個新的查詢前綴.令H(m)為檢測到碰撞位n<4時出現(xiàn)的次數(shù)，由于H(m)的情況比較復(fù)雜，本文從實驗的角度對它進(jìn)行分析，如圖3所示.可以得知H(m)隨著標(biāo)簽數(shù)目的增加而變化得非常緩慢，近似線性關(guān)系且所占時隙的比例很少，本文仍將其擬合為二次函數(shù)曲線：

H(m)=3.6×10-5m2+0.0027m-0.17

(18)

因此，AS算法成功識別m個標(biāo)簽需要的時隙總數(shù)為：

T(m)=t(m)-i(m)+F(m)+H(m)

(19)

將B=16，以及式(13)，(14)，(17)代入式(19)中，即

T(m)=-0.001m2+6.9m-120

-(-0.00093m2+5.5m-110)

-D×2-D]+3.6×10-5m2+0.0027m-0.17

=-3.4×10-5m2+1.4027m-10.17

-D×2-D]

(20)

所以吞吐率為：

(21)

4 實驗仿真與分析

為了驗證本算法的有效性，在Windows 7操作系統(tǒng)平臺下，其中PC機的硬件參數(shù)為：CPU為i3處理器，主頻為2.53GHZ，內(nèi)存為4G.利用Matlab2010a軟件作為仿真實驗工具對BS算法，JDS算法，QT算法和AMS算法以及本文的AS算法進(jìn)行仿真實驗.假設(shè)標(biāo)簽的ID為16bit，并且是隨機均勻分布的，標(biāo)簽的數(shù)目由100增加至1000，仿真的結(jié)果是在相同條件下取100次實驗的平均值.

4.1 誤差分析

在第3.2節(jié)中本文已經(jīng)對各時隙情況進(jìn)行理論分析，通過實驗仿真和理論計算，其分析結(jié)果如圖4所示.從圖中可以看出吞吐率的實驗值與理論計算值非常逼近，且曲線相對比較平穩(wěn).兩者的最大誤差為0.043<5%，所以在誤差允許范圍內(nèi)實驗結(jié)果與理論分析的結(jié)果是一致的，同時也從實驗的角度驗證了理論的正確性.出現(xiàn)誤差的原因主要有以下幾個原因：

(1)標(biāo)簽的序列號是隨機產(chǎn)生的，并不是理論上均勻分布，而吞吐率與序列號密切相關(guān).

(2)在計算的過程中，有取整的運算，即有一定精度的損失.

(3)H(m)是通過實驗統(tǒng)計而獲得，因此也有一定的誤差.

4.2 信息位編碼長度的選擇

讀寫器為了獲得有效查詢前綴，需要標(biāo)簽返回碰撞信息.如果不將碰撞信息進(jìn)行編碼，則讀寫器很難判斷各標(biāo)簽返回的具體信息.本文取信息位編碼長度V分別為2,3,4,5bit進(jìn)行實驗仿真，如圖5所示，雖然V越長，吞吐率越高，但其代價成本也會隨之增加.考慮到標(biāo)簽成本及各方面的因素，AS算法選擇V=4bit.從圖5中可以看出，當(dāng)V=2時，其吞吐率僅為0.46左右.當(dāng)V=3時，其性能有所提高，但仍不理想.這是由于每次標(biāo)簽發(fā)生多比特碰撞時，讀寫器為了獲得碰撞位的具體信息，需要額外的發(fā)送一次Call命令.當(dāng)V=2,3bit時，每次查詢的步長較少，碰撞較為劇烈，因此，其時隙總數(shù)也必定會增加，最終導(dǎo)致吞吐率較低.

4.3 通信復(fù)雜度分析

通信復(fù)雜度分析是評估一個算法性能的重要方法，其包括讀寫器通信復(fù)雜度和標(biāo)簽通信復(fù)雜度分析兩個部分.本文分別對AS算法、AMS算法、JDS算法以及QT算法在識別過程中標(biāo)簽和讀寫器的通信量進(jìn)行仿真，仿真中用到的AS算法命令和參數(shù)長度如表3所示.

表3 AS算法中涉及的命令和參數(shù)長度

(1)讀寫器的通信復(fù)雜度

讀寫器通信復(fù)雜度是指讀寫器識別全部標(biāo)簽所發(fā)送的總比特數(shù)，即讀寫器的通信量.從圖6可以看出，各算法中讀寫器的通信量都是隨著標(biāo)簽數(shù)目的增加，呈線性增長，其中QT算法增長最快，AMS算法和JDS算法增長速度接近，而AS算法增長較為緩慢.這是因為AS算法能夠自適應(yīng)的生成有效查詢前綴，大幅度地減少了讀寫器發(fā)送詢問指令的次數(shù).當(dāng)標(biāo)簽數(shù)目為1000時，QT算法中讀寫器的通信量為79681bit，JDS、AMS算法分別為61978bit和61098bit，而AS算法僅為52697bit，比QT算法中讀寫器的通信量下降了約33.9%，比JDS、AMS算法分別下降了約15%和13.8%.

(2)標(biāo)簽的通信復(fù)雜度

在識別的過程中，標(biāo)簽對于讀寫器的不同命令，需進(jìn)行相應(yīng)的響應(yīng)，而所有標(biāo)簽發(fā)送的比特數(shù)之和稱為標(biāo)簽的通信量.標(biāo)簽的通信量與功耗密切相關(guān)，通信量越大，標(biāo)簽的功耗也隨之增大，而對于普通的標(biāo)簽而言，功耗是有限的.此外，減少標(biāo)簽返回的數(shù)據(jù)量，也就降低了信息泄露的危險，提高了系統(tǒng)的安全性.因此，應(yīng)盡可能的減少標(biāo)簽的通信量.AS算法繼承了QT算法的優(yōu)點，這不僅簡化了標(biāo)簽的設(shè)計，也降低了標(biāo)簽的通信量.如圖7所示，在這四種算法中，AS算法中標(biāo)簽的通信量增長最為緩慢，明顯低于其他三種算法.當(dāng)標(biāo)簽的數(shù)目1000時，QT算法中標(biāo)簽的比特數(shù)為120700bit，JDS算法和AMS算法分別為104942bit和108213bit，而AS算法僅為59266bit，比QT算法標(biāo)簽的通信量大約下降了51%，比JDS、AMS算法分別下降了43.5%和45.2%.4.4 時間復(fù)雜度分析

讀寫器成功識別所有標(biāo)簽而需要的查詢次數(shù)為時間復(fù)雜度，即總時隙數(shù)，是衡量一個算法性能的重要參數(shù).AS算法是一種無空閑時隙的防碰撞算法，能將碰撞標(biāo)簽準(zhǔn)確無誤地識別，并且還能自適應(yīng)分配有效查詢前綴，降低樹的深度，有利于減少總時隙數(shù).如圖8所示，四種算法的總時隙數(shù)隨著標(biāo)簽數(shù)目的增加而不斷增加，且呈線性增長的趨勢，其中QT算法的總時隙數(shù)增長最快，AS算法增長最慢.隨著標(biāo)簽數(shù)目的不斷增大，AS算法的優(yōu)勢更加明顯.當(dāng)標(biāo)簽數(shù)目為1000時，AS算法的總時隙數(shù)為1630，比QT算法減少約1174個，比JDS算法減少約369個，比AMS算法減少約327個，其時間復(fù)雜度分別下降了41.87%，18.46%和16.71%.

4.5 吞吐率分析

吞吐率也是衡量一個算法性能的一個重要指標(biāo)，與總時隙數(shù)密切相關(guān).本文通過與QT算法，JDS算法以及AMS算法這三種經(jīng)典防碰撞算法進(jìn)行比較，如圖9所示.這四種算法的吞吐率均保持相對比較平穩(wěn)，隨著標(biāo)簽數(shù)目的增加，QT算法的吞吐率為0.35左右，JDS、AMS算法則分別保持0.5和0.51左右，而AS算法的吞吐率最高，維持在0.6左右.當(dāng)標(biāo)簽的數(shù)目為1000時，與QT、JDS以及AMS算法相比，AS算法的吞吐率分別提高了72%，22.7%和20.1%.

5 結(jié)論

本文提出一種基于信息位編碼的自適應(yīng)搜索RFID防碰撞(AS)算法，同QT算法一樣，標(biāo)簽不需要記憶以前的查詢情況，只需要與讀寫器發(fā)出的前綴作比較.若匹配成功，則僅需發(fā)送前綴后面的序列以減少標(biāo)簽的數(shù)據(jù)傳輸.

本文雖然是在選取標(biāo)簽數(shù)目為1000以內(nèi)，對AS算法進(jìn)行的實驗仿真和理論分析，但通過實驗表明和數(shù)據(jù)分析，當(dāng)標(biāo)簽數(shù)目為1200，1500時，除了誤差有稍微的增加外，上述大部分結(jié)論也依然成立.此外，還從時間復(fù)雜度和通信復(fù)雜度對該算法進(jìn)行了詳細(xì)地分析.其仿真結(jié)果表明，隨著標(biāo)簽數(shù)目的增加，AS算法同QT、JDS以及AMS算法一樣，標(biāo)簽、讀寫器的通信量以及時隙總數(shù)幾乎都保持了線性增加.其中，AS算法增長最為緩慢，通信量和時隙總數(shù)最少，而吞吐率最高，維持在60%左右.因此，本文提出的AS算法能有效地提高RFID系統(tǒng)的工作效率，減少識別時間，降低標(biāo)簽的能量消耗.針對于大量的標(biāo)簽的識別，AS算法的優(yōu)勢尤為顯著，在物聯(lián)網(wǎng)工程中具有廣泛的應(yīng)用前景.

[1]Atzori L,Iera A,Morabito G.The internet of things:A survey[J].Computer Networks,2010,54(15):2787-2805.

[2]Want R.An introduction to RFID technology[J].IEEE Pervasive Computing,2006,5(1):25-33.

[3]Weinstein R.RFID:A technical overview and its application to the enterprise[J].IT Professional,2005,7(3):27-33.

[4]Yang L,Rida A,Vyas R,et al.RFID tag and RF structures on a paper substrate using inkjet-printing technology[J].IEEE Transactions on Microwave Theory and Techniques,2007,55(12):2894-2901.

[5]Hwang K,Yeo S S,Park J H.Distributed tag access with collision-avoidance among mobile RFID readers[A].Proceedings of the 2009 International Conference on Computational Science and Engineering[C].Vancouver:IEEE,2009.621-626.

[6]Qian C,Ngan H,Liu Y,et al.Cardinality estimation for large-scale RFID systems[J].IEEE Transactions on Parallel and Distributed Systems,2011,22(9):1441-1454.

[7]Wu H,Zeng Y,Feng J,et al.Binary tree slotted ALOHA for passive RFID tag anti-collision[J].IEEE Transactions on Parallel and Distributed Systems,2013,24(1):19-31.

[8]Li Z,He C,Li J,et al.RFID reader anti-collision algorithm using adaptive hierarchical artificial immune system[J].Expert Systems with Applications,2014,41(5):2126-2133.

[9]Liu L,Lai S.ALOHA-based anti-collision algorithms used in RFID system[A].Proceedings of the 2006 International Conference on Wireless Communications,Networking and Mobile Computing[C].Wuhan:IEEE,2006.1-4.

[10]Eom J B,Lee T J.Accurate tag estimation for dynamic framed-slotted ALOHA in RFID systems[J].IEEE Communications Letters,2010,14(1):60-62.

[11]Deng D J,Tsao H W.Optimal dynamic framed slotted ALOHA based anti-collision algorithm for RFID systems[J].Wireless Personal Communications,2011,59(1):109-122.

[12]Maguire Y,Pappu R.An optimal Q-algorithm for the ISO 18000-6C RFID protocol[J].IEEE Transactions on Automation Science and Engineering,2009,6(1):16-24.

[13]Chen W T.An accurate tag estimate method for improving the performance of an RFID anti-collision algorithm based on dynamic frame length ALOHA[J].IEEE Transactions on Automation Science and Engineering,2009,6(1):9-15.

[14]Wang C Y,Lee CC.A grouping-based dynamic framed slotted ALOHA anti-collision method with fine groups in RFID systems[A].Proceedings of the 2010 5th International Conference on Future Information Technology[C].Busan:IEEE,2010.1-5.

[15]Bentley J L.Multidimensional binary search trees used for associative searching[J].Communications of the ACM,1975,18(9):509-517.

[16]Yu Z,Liu X.Improvement of Dynamic Binary Search Algorithm Used in RFID System[A].Proceedings of the 2011 International Conference on Cross Strait Quad-Regional Radio Science and Wireless Technology[C].Harbin:IEEE,2011.1046-1049.

[17]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.

[18]Choi J H,Lee D,Lee H.Query tree-based reservation for efficient RFID tag anti-collision[J].IEEE Communications Letters,2007,11(1):85-87.

[19]Shih B Y,Lo T W,Chen C Y.The research of quadtree search algorithms for anti-collision in radio frequency identification systems[J].Scientific Research and Essays,2011,6(25):5342-5350.

[20]丁治國,朱學(xué)永,郭立,等.自適應(yīng)多叉樹防碰撞算法研究[J].自動化學(xué)報,2010,36(2):237-241.

Ding Zhi-guo,Zhu Xue-yong,Guo Li,et al.An adaptive anti-collision algorithm based on multi-tree search[J].Acta Automatica Sinica,2010,36(2):237-241.(in Chinese)

[21]劉子龍,紀(jì)金水,劉彩虹,等.基于連續(xù)碰撞位探測的防碰撞算法研究[J].電子學(xué)報,2013,41(11):2156-2160.

Liu Zi-long,Ji Jin-shui,Liu Cai-hong,et al.An anti-collision algorithm based on continuous collision bit detection[J].Acta Electronica Sinica,2013,41(11):2156-2160.(in Chinese)

胡應(yīng)夢 男,1989年11月出生,湖南婁底人， 現(xiàn)為江西理工大學(xué)信息工程學(xué)院碩士研究生，研究方向為 RFID防碰撞算法、可信認(rèn)證協(xié)議.

E-mail:huyingmeng89@163.com

張小紅 女,1966年8月出生,河北昌黎人，現(xiàn)為江西理工大學(xué)信息工程學(xué)院教授、博士生導(dǎo)師，研究方向為無線傳感器網(wǎng)絡(luò)、非線性動力學(xué)理論、混沌保密通信.

E-mail:xiaohongzh@263.net

Research of an Adaptive Searching Anti-collision Algorithm for RFID Based on Information-Bit Encoding

HU Ying-meng,ZHANG Xiao-hong

(SchoolofInformationEngineering,JiangxiUniversityofScienceandTechnology,Ganzhou,Jiangxi341000,China)

Radio frequency identification(RFID) technology has the ability to automatically identify the target object.An adaptive searching prefix(AS) anti-collision algorithm for RFID based on encoding is proposed to reduce the identified time of the object tag.The reader makes full use of the collision information to adaptively generate a valid query prefix by asking the tags return the collision coded information.With no idle slots for tags to identify,AS reduces the number of queries and consumedly enhances the system efficiency.Besides,it has solved the problems of redundant data in the communication between the reader and the tags and other related issues.The effectiveness of the algorithm has been proved by the theoretical analysis in detail,and the error of the throughput between the values of the theory and the experiment does not exceed 5%.Simulation results show that AS not only achieves much better performance of the system,but also reduces the energy consumption of the tags.It improves the system efficiency by 72% and 20.1% respectively compared with Query Tree algorithm and Adaptive Multi-tree Search algorithm when the number of tags is over 1000，the throughput still maintains at about 61%.

radio frequency identification(RFID);anti-collision;encoding information bit;adaptive;idle slots

2015-02-03；

2015-04-15；責(zé)任編輯：藍(lán)紅杰

國家自然科學(xué)基金(No.61363076,No.11062002);江西省自然科學(xué)基金(No.20142BAB207020);江西省教育廳科技項目((No.GJJ14465);江西省研究生創(chuàng)新專項資金(No.YC2014-S370)

TN92

A

0372-2112 (2016)08-1791-08