引言

RFID系統(tǒng)主要由讀寫器和射頻卡兩部分組成，它們之間可以通過無線方式進行通信。其中，射頻卡中存儲了需要識別、交互的數(shù)據(jù)，并且可以實時寫入或擦除。RFID系統(tǒng)工作時,若有多個電子標(biāo)簽同時在同一個閱讀器的作用范圍內(nèi)向閱讀器發(fā)送數(shù)據(jù)，則往往會出現(xiàn)信號的干擾，這個干擾就被稱為碰撞,其結(jié)果將會導(dǎo)致此次數(shù)據(jù)傳輸?shù)氖?，因而必須采用適當(dāng)?shù)募夹g(shù)防止碰撞。最近，有人提出了動態(tài)二進制捜索法、跳躍式類二進制搜索法等二進制防碰撞算法的改進算法。國際上廣泛應(yīng)用的防碰撞算法是ALOHO法和二進制捜索法及對這兩種算法的改進方法，如時隙ALOHO法、動態(tài)二進制搜索法、后退式二進制法搜索等。其中，動態(tài)二進制法是國際標(biāo)準(zhǔn)所推薦的防碰撞方法。就此，本文提出了一種二進制搜索法的改進型算法。

1二進制搜索算法

1.1二進制搜索算法(BS)原理

二進制捜索算法又稱為二叉樹捜索算法叫由于它要求能夠在閱讀器中確定數(shù)據(jù)碰撞位的準(zhǔn)確位置，因此，必須要有合適的位編碼法叫曼徹斯特碼用上升沿表示0,用下降沿表示1，在數(shù)據(jù)傳輸過程中不允許“沒有改變”的狀態(tài)。如果采用ASK調(diào)制方式，當(dāng)多個電子標(biāo)簽同時發(fā)送的數(shù)據(jù)位值不同時，則収對應(yīng)的曼徹斯特碼的上升沿和下降沿相互抵消，造成一種錯誤的狀態(tài)，從而可以確定碰撞位置。假設(shè)有兩個編碼為8位的電子標(biāo)簽，利用曼徹斯特編碼識別碰撞位的原理如圖1所示。閱讀器檢出的碰撞位為D6位和D5位。

一般情況下，二進制搜索算法必須先能辨認(rèn)出閱讀器中數(shù)據(jù)沖突的確切位置，這一點是下面算法的基礎(chǔ)。這里主要對以下幾個命令以及原理流程進行簡述：

REQUEST(某序列號Q)：如果標(biāo)簽序列號小于或等于Q,

則該標(biāo)簽進入識別狀態(tài)，將發(fā)自己的序列號給閱讀器，否則處于等待狀態(tài):

SELECT(某序列號Q):如果標(biāo)簽序列號等于Q,則該標(biāo)簽進入選中狀態(tài)，否則繼續(xù)等待識別；

READ:選中的標(biāo)簽與閱讀器進行數(shù)據(jù)通信；

UNSELECT:取消前選中標(biāo)簽，該標(biāo)簽進入靜默狀態(tài),待所有標(biāo)簽完成通信或者該標(biāo)簽重新入場后，才能進入等待狀態(tài)。

1.2二進制搜索算法的深入分析

閱讀器和標(biāo)簽之間的通信次數(shù)決定了識別速度。從眾多標(biāo)簽中識別出一個標(biāo)簽的平均通信次數(shù)為L在二進制捜索算法中，我們知道：

L=log2N+1(1)

由于二進制搜索算法的識別獨立性，N個標(biāo)簽的全部識別平均通信次數(shù)為：

L(total)=/log2n+1

n=1

當(dāng)標(biāo)簽數(shù)目很多的時候，由于每次獨立識別浪費了大量通信次數(shù)，算法總的通信次數(shù)必然會增長很快。二進制搜索算法還有一個很明顯的弱點：閱讀器發(fā)送給每個標(biāo)簽的比較序列，其實有用的信息只包含在高于上次碰撞位X的高位之中,低于碰撞位的通信產(chǎn)生冗余。

2動態(tài)二進制搜索算法

2.1動態(tài)二進制搜索算法原理

前面所述的二進制搜索算法，每次搜索都需要完整的傳輸標(biāo)簽的序列號ID。但在實際應(yīng)用中，標(biāo)簽的序列號長度不再像前所述那樣為8位，而可能是長達(dá)10個字節(jié)甚至更大的規(guī)模。這樣采用BS算法，RFID系統(tǒng)標(biāo)簽的傳輸量將大增，為此動態(tài)二進制捜索(DBS)算法應(yīng)運而生。DBS算法是IS014443A這一國際標(biāo)準(zhǔn)所推薦的防碰撞算法。序列號ID中的全部信息對于成功識別出標(biāo)簽不是不可或缺的。根據(jù)編碼規(guī)律可以去掉序列號中的冗余信息，留下有用的信息傳輸。通過觀察上面BS算法實例中標(biāo)簽的識別過程可知：命令中的碰撞位及其低位因為總是被置位為1，不包含有用的信息，這樣就不要傳輸；標(biāo)簽應(yīng)答的序列號最高位至碰撞位是已知的前綴信息，不包括補充信息，也不需要傳輸。由上面的分析可知，序列號ID中的冗余部分是不需要傳輸?shù)??？梢詫BS算法由雙向的完整傳輸加以改進，只傳輸部分有用信息。Request命令中，讀寫器只需以要捜索的序列號ID的碰撞位至最高位部分為參數(shù)。所有相應(yīng)位與此命令中參數(shù)相符的標(biāo)簽，則傳輸序列號的碰撞位以下部分作為應(yīng)答。

DBS算法的命令

與BS算法的命令相比，DBS算法的命令做了一些改進：主要是DBS算法把第一個命令改成RequestQDg,X)。讀寫器發(fā)送參數(shù)ID"t(ID的N~X位)給作用范圍內(nèi)的所有標(biāo)簽,相應(yīng)位與ID**符合的標(biāo)簽做出響應(yīng)，返回剩余的位信息。其余三條命令與前面所述BS算法一致。

DBS算法的，性能分析

DBS算法與BS算法的規(guī)則相同，所以兩者重復(fù)操作的過程也相同。因此，DBS算法的總捜索次數(shù)為：

I-BS=(log2N+1)+［log2(N-1)+1］+…+

(log,2+1)+(log21+1)=(3)

N+log2(N!)

DBS算法在識別過程開始時，即算法的第一步，工作范圍內(nèi)的標(biāo)簽是需要傳輸整個序列號的；在這之后的識別過程中，標(biāo)簽只需要傳輸ID的有用部分位。整個識別過程平均下來,DBS的信息量只有BS算法的一半。DBS算法中，標(biāo)簽要傳輸?shù)臄?shù)據(jù)量和所需時間比起B(yǎng)S算法減少了近50%。

3查詢樹算法(QT)

“QT(QueryTree)查詢樹算法基于標(biāo)簽ID號來分裂一組發(fā)生碰撞的標(biāo)簽?！痹诿恳惠唫鬏斨?，讀寫器向標(biāo)簽發(fā)送一個比特串的查詢信息。讀寫器的一系列查詢比特串記錄在隊列Q中。初始化隊列Q為兩個1位比特比特串0和1,讀寫器從Q中取出一個比特串，用以查詢信息。若此查詢信息與某標(biāo)簽的序列號ID的前綴信息相同，則此標(biāo)簽響應(yīng)讀寫器的命令，傳輸自己的ID給讀寫器。如果讀寫器發(fā)送的查詢比特串XXX3-X,(Xie{0,1},,小于標(biāo)簽序列號ID的長度),有多個標(biāo)簽同時響應(yīng)讀寫器的查詢信息，即發(fā)生了碰撞，則在此查詢比特串后面增加一位，將XXX3-X,0和XXX3-X,1壓入隊列Q中。讀寫器下次將分別用這兩個比特串作為查詢信息，前面發(fā)生碰撞的標(biāo)簽將分為兩個部分。一部分將響應(yīng)查詢比特串XjXzXs-X0,另一部分將響應(yīng)查詢比特串X1X2X3…X,1。依此方法不斷地增加比特串位數(shù)，直至收到響應(yīng)但沒有

碰撞情況發(fā)生或無響應(yīng)的情況，這樣讀寫器就能夠識別出所有的標(biāo)簽。

查詢樹算法用隊列Q存儲查詢信息標(biāo)簽不必存儲序列號ID以外的無關(guān)信息，這樣，標(biāo)簽就具有更簡單的功能，可降低標(biāo)簽成本，因此，QT算法是無記憶的算法。圖2所示是QT算法的一個示意圖。系統(tǒng)中的標(biāo)簽ID號為0010,1110和1101。

圖2QT算法實例

4改進型算法

4.1改進型算法思想

讀寫器引入一個堆棧S來存儲二叉樹發(fā)生碰撞時右子樹節(jié)點信息，一個隊列Q來存儲無碰撞發(fā)生時的查詢前綴。

設(shè)標(biāo)簽序列號ID是長為L的二進制數(shù)，讀寫器查詢前綴是長度不大于L的二進制數(shù)。那么，讀寫器發(fā)送查詢前綴,使其作用范圍內(nèi)標(biāo)簽將自己的序列號ID與查詢前綴相比較。如果查詢前綴與標(biāo)簽自最高位開始的部分比特串相同，則標(biāo)簽回復(fù)序列號ID剩余的部分比特串給讀寫器。初始時，二叉樹只有根節(jié)點，讀寫器的堆棧為空，隊列Q為空。

4.2改進型算法流程

第一步，由讀寫器在初始時發(fā)送查詢前綴（1位的二進制數(shù)“0”），此時有以下幾種情況：

（1）如果只有一個標(biāo)簽響應(yīng)，即無碰撞發(fā)生，此時可為根節(jié)點添加左子節(jié)點（表示二進制數(shù)0），將此查詢前綴“0”送入隊列Q，跳轉(zhuǎn)到第四步。

（2）如果有多于一個的標(biāo)簽響應(yīng)，即發(fā)生了碰撞，此時可為根節(jié)點添加左子節(jié)點（表示二進制數(shù)0），并把0送入堆棧S；然后為節(jié)點0添加左子節(jié)點00和右子節(jié)點01。將01送入堆棧S，再跳轉(zhuǎn)到第三步，以00為查詢前綴。

（3）如果無標(biāo)簽響應(yīng)，跳轉(zhuǎn)到第二步。

第二步，讀寫器發(fā)送查詢前綴（1位的二進制數(shù)“1”），此時也有如下幾種情況：

（1）若有標(biāo)簽響應(yīng)且無碰撞發(fā)生，則為根節(jié)點添加右子節(jié)點（表示二進制數(shù)1），將查詢前綴“1”送入隊列Q中，跳轉(zhuǎn)到第四步。

（2）若有碰撞發(fā)生，則為根節(jié)點添加右子節(jié)點（表示二進制數(shù)1），并把1送入堆棧S；然后為節(jié)點1添加左子節(jié)點10和右子節(jié)點11。將11送入堆棧S，以10為查詢前綴。

（3）若無標(biāo)簽響應(yīng)，說明讀寫器作用范圍內(nèi)無標(biāo)簽存在或者系統(tǒng)可能出現(xiàn)故障，識別流程結(jié)束。

第三步，讀寫器發(fā)送查詢前綴。若收到響應(yīng)且無碰撞發(fā)生,則將此查詢前綴送入Q；若有碰撞發(fā)生，則分別添加左子樹和右子樹，右子樹壓入堆棧S，左子樹作為新的查詢前綴，重復(fù)步驟第三步；如無標(biāo)簽響應(yīng)，則從堆棧S中彈出一個元素作為查詢前綴，重復(fù)第三步。

第四步，當(dāng)讀寫器成功識別某標(biāo)簽，先與讀寫器進行通信，然后使標(biāo)簽進入“無聲”狀態(tài)，即此標(biāo)簽不再響應(yīng)讀寫器的查詢。從堆棧S中彈出一個元素作為查詢前綴,重復(fù)第三步,直至所有的標(biāo)簽被識別出來。

4.3改進型算法實例

假設(shè)系統(tǒng)內(nèi)有四個待識別的標(biāo)簽，其序列號ID分別為0010、0100、1010、1101。其首次識別過程如表1所列。

首先，讀寫器發(fā)送查詢前綴0，標(biāo)簽0010和0100響應(yīng)，發(fā)生碰撞，將0送入堆棧S；添加左子節(jié)點00和右子節(jié)點01，將01送入堆棧S，以00作為新的查詢前綴。讀寫器發(fā)送查詢前綴00，此時只有標(biāo)簽0010響應(yīng)，將查詢前綴00送入隊列Q；此標(biāo)簽被成功識別，與讀寫器通信完畢后，進入“無聲”狀態(tài)。從堆棧S中彈出01，作為新的查詢前綴，此時只有標(biāo)簽0100響應(yīng)，將查詢前綴01送入隊列Q；此標(biāo)簽被成功識別。

然后再從堆棧S中彈出0，作為新的查詢前綴，此時無標(biāo)簽響應(yīng)，因此讀寫器以1為查詢前綴。標(biāo)簽1010和1101響應(yīng)，發(fā)生了碰撞，將1送入堆棧S；添加左子節(jié)點10和右子節(jié)點11，將11送入堆棧S，以10作為新的查詢前綴。讀寫器發(fā)送查詢前綴10，此時只有標(biāo)簽1010響應(yīng)，將查詢前綴10送入隊列Q；此標(biāo)簽被成功識別。從堆棧S中彈出11，作為新的查詢前綴，此時只有標(biāo)簽1101響應(yīng)，將查詢前綴11送入隊列Q；此標(biāo)簽被成功識別。

最后從標(biāo)簽中彈出1，作為新的查詢前綴，無標(biāo)簽響應(yīng)，結(jié)束識別流程。

如上所述，通過表1中所列的首輪識別后，隊列Q中的查詢前綴為[00，01，10，11]。當(dāng)讀寫器再次需要識別其作用范圍內(nèi)的標(biāo)簽時，就可直接發(fā)送隊列Q中的查詢前綴，這樣，標(biāo)簽?zāi)軌虮豢焖俚刈R別出來。

5各種算法的Matlab仿真

下面采用Matlab下仿真系統(tǒng)通信量的方法來比較各個算法的效率。在識別相同標(biāo)簽屬的前提下占用的比特數(shù)越高，則說明其通信量越大，對系統(tǒng)要求越高。

圖3和圖4均是在標(biāo)簽長度L=8的情況下所進行的仿真結(jié)果，其中圖3在識別100個標(biāo)簽時，二進制搜索算法通信量約為7500b，動態(tài)二進制搜索算法通信量約為4300b；圖4則在識別100個標(biāo)簽時，查詢樹算法在通信量約為13600b，改進型算法通信量約為2100b情況下的仿真結(jié)果。

依據(jù)在標(biāo)簽長度為8b時所仿真出的圖3和圖4所示的通信量數(shù)據(jù)，可以采用相同的仿真方法較容易地得出各種防碰撞方法在不同標(biāo)簽長度下的通信量數(shù)據(jù),綜合總結(jié)如表2所列。

6結(jié)語

本文通過對RFID中各種主流防碰撞方法的思想、實現(xiàn)及算法的研究，提出了相應(yīng)的改進型算法，并對算法進行了詳細(xì)的說明。之后，對所有算法的實現(xiàn)進行了Matlab仿真，證實了改進型算法相較其他算法的優(yōu)越性。仿真證明，在標(biāo)簽長度較短的情況下，該算法可以表現(xiàn)出極其優(yōu)越的性能。但是，該算法亦有它的不足，在單個標(biāo)簽長度較長的情況下，該算法的通信量急劇上升。所以，在算法的通信冗余度方面還有進一步優(yōu)化的必要。

20211018_616c57196bf54__RFID中解決無線信道爭用問題的防碰撞算法研究