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

胡應夢，張小紅

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

?

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

胡應夢，張小紅

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

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

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

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

1 引言

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

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

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

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

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

2 AS算法設計

2.1 基本思想

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

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

2.2 AS算法約定

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

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

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

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

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

2.3 AS算法流程

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

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

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

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

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

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

步驟4 讀寫器根據(jù)響應標簽的數(shù)量進行如下處理：

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

(2)如果有兩個或兩個以上的標簽，則需進一步判斷：

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

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

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

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

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

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

表2 AS算法舉例識別過程

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

3 AS算法性能分析

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

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

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

(1)

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

(2)

標簽成功識別的概率為：

(3)

標簽出現(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)

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

(5)

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

(6)

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

(7)

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

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

(8)

(9)

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

(10)

碰撞時隙數(shù)為：

(11)

空閑時隙數(shù)為：

(12)

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

由圖2可知t(m)，c(m)，i(m)與標簽數(shù)目m呈線性增長的關系，為了計算更為精確，本文將其擬合為二次函數(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編碼，故可認為是在16叉樹算法上的優(yōu)化.當讀寫器檢測到只有1bit發(fā)生碰撞時，讀寫器不需要標簽返回碰撞位信息，直接將碰撞位分別置0,1，在下一個時隙即可直接識別這兩個標簽.設在識別過程中只有1比特發(fā)生碰撞的標簽數(shù)為G(m).

(16)

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

-D×2-D]

(17)

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

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

(18)

因此，AS算法成功識別m個標簽需要的時隙總數(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，內存為4G.利用Matlab2010a軟件作為仿真實驗工具對BS算法，JDS算法，QT算法和AMS算法以及本文的AS算法進行仿真實驗.假設標簽的ID為16bit，并且是隨機均勻分布的，標簽的數(shù)目由100增加至1000，仿真的結果是在相同條件下取100次實驗的平均值.

4.1 誤差分析

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

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

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

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

4.2 信息位編碼長度的選擇

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

4.3 通信復雜度分析

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

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

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

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

(2)標簽的通信復雜度

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

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

4.5 吞吐率分析

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

5 結論

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

本文雖然是在選取標簽數(shù)目為1000以內，對AS算法進行的實驗仿真和理論分析，但通過實驗表明和數(shù)據(jù)分析，當標簽數(shù)目為1200，1500時，除了誤差有稍微的增加外，上述大部分結論也依然成立.此外，還從時間復雜度和通信復雜度對該算法進行了詳細地分析.其仿真結果表明，隨著標簽數(shù)目的增加，AS算法同QT、JDS以及AMS算法一樣，標簽、讀寫器的通信量以及時隙總數(shù)幾乎都保持了線性增加.其中，AS算法增長最為緩慢，通信量和時隙總數(shù)最少，而吞吐率最高，維持在60%左右.因此，本文提出的AS算法能有效地提高RFID系統(tǒng)的工作效率，減少識別時間，降低標簽的能量消耗.針對于大量的標簽的識別，AS算法的優(yōu)勢尤為顯著，在物聯(lián)網(wǎ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]丁治國,朱學永,郭立,等.自適應多叉樹防碰撞算法研究[J].自動化學報,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]劉子龍,紀金水,劉彩虹,等.基于連續(xù)碰撞位探測的防碰撞算法研究[J].電子學報,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)

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

E-mail:huyingmeng89@163.com

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

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；責任編輯：藍紅杰

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

TN92

A

0372-2112 (2016)08-1791-08