賀曉霞 賈小林

(西南科技大學計算機科學與技術(shù)學院 四川 綿陽 621000)

0 引 言

RFID技術(shù)是一種無線自動識別技術(shù)，按照工作頻率的不同，可以分為低頻(LF)、高頻(HF)、超高頻(UHF)和微波等不同種類。其中超高頻RFID系統(tǒng)通常用于遠距離識別和多標簽的場合。為了有效地解決UHF RFID系統(tǒng)中出現(xiàn)的信道爭用的情況[1]，通常有以下兩種解決方案：

(1) 采用并行方式實現(xiàn)多卡識別；(2) 根據(jù)規(guī)定時間，電子標簽挨個發(fā)送數(shù)據(jù)，在此時間內(nèi)只有一個電子標簽在工作。

對于第一種情況，一般采用碼分多址和頻分多址的方式，然而這樣會增加系統(tǒng)的成本和復(fù)雜性。在第二種情況下，可以使用TDMA方法與軟硬件結(jié)合或它們的組合來實現(xiàn)。實現(xiàn)起來并不復(fù)雜，但是如果沒有好的算法，要識別所有的電子標簽將花費很長時間。

在RFID多標簽系統(tǒng)中，主流防碰撞算法可以劃分為：(1) 基于Aloha的算法，如純Aloha(PA)、時隙Aloha(SA)、幀時隙Aloha(FSA)、動態(tài)幀時隙Aloha(DFSA)以及其他的改進算法[2]；(2) 基于樹的算法，主要有查詢樹(QT)[3]、二進制搜索(BS)[4]、增強型搜索樹算法(EBST)[5]、碰撞樹(CT)[6]以及改進的碰撞樹算法(ICT)[7]等；(3) 混合算法，例如樹時隙Aloha(TSA)、混合查詢時隙(HQT)以及哈希樹算法等[8]。然而基于Aloha算法有一個嚴重的問題，稱為“標簽饑餓”[2]，該問題可能導(dǎo)致標簽一直無法被識別。基于二進制樹的算法的核心思想是不斷地將碰撞標簽分為兩個不相交的子集，直到識別詢問區(qū)中的所有標簽[9]，通常需要較長的識別時間。

識別過程通常都是通過標簽的唯一ID進行識別，當標簽被完全識別出來之后，就會被消除，不再參與后續(xù)的應(yīng)答。例如，在文獻[10]中，如果發(fā)生碰撞，閱讀器將通過用0或1來選擇路徑進行答復(fù)。標簽位與查詢位一致的標簽繼續(xù)下一個位仲裁，而產(chǎn)生碰撞的標簽將記錄碰撞位置并同時進入靜默狀態(tài)。在ID-BTS[11]中提出了類似的協(xié)議。這些算法中標簽都需要帶一個計數(shù)器作為指針，每個標簽在沖突仲裁過程中傳輸ID的每一位。文獻[12]提出了一種新的自調(diào)整多叉樹防碰撞算法(new anti-collision algorithm based on adjustive multi-tree，NAM)，該算法是一種基于多叉樹搜索的確定性算法，其引入了異或運算，使得空閑時隙的數(shù)量降低。

上述兩種技術(shù)主要有三個缺點：(1) ID-BTS算法每次識別后發(fā)送最后一個碰撞比特位置的查詢，喚醒非活動標簽，識別過程相對較慢，并且重復(fù)發(fā)送相同的位查詢請求會造成大量的時間開銷；(2) 閱讀器的命令幀相對較長，ID-BTS算法在每次標簽識別之后都會產(chǎn)生一定的時間開銷，是一種慢速算法；(3) 對于NAM算法，隨著標簽數(shù)量以及標簽位數(shù)的增加，空閑時隙也會隨之增加，數(shù)據(jù)傳輸量仍相對較大。

1 算法設(shè)計

本文提出了一種基于鎖位式的并行二進制分割(LPBS)防碰撞算法。該算法利用曼徹斯特編碼方式，按位判斷，確定并提取碰撞位，組成新的標簽序列，使得非碰撞位的信息不再參與傳輸。例如識別標簽為10011100、11000110時，檢測到的碰撞位是D6、D4、D3、D1，因此組成新一輪查詢序列為1X0XX1X0，不需要再重新發(fā)送非碰撞位的信息，而只需要傳送碰撞的那4位，使得信息的傳輸量減少了50%。同時，采用并行二進制分割技術(shù)，使得閱讀器和標簽可以進行一位標簽應(yīng)答。該方法可以動態(tài)修改標簽與標簽之間的相對回復(fù)順序，發(fā)送的比特數(shù)量等于除了葉子節(jié)點之外的二叉樹節(jié)點的數(shù)量的兩倍。該技術(shù)只使用閱讀器的一位來響應(yīng)發(fā)送的數(shù)據(jù)量(1:碰撞，0:無碰撞)。標簽可以通過閱讀器確定上一輪查詢中位傳輸?shù)慕Y(jié)果，從而使得標簽?zāi)軌蛟趹?yīng)答隊列中不斷地修改其識別的順序。因此，標簽可以確定其未來的應(yīng)答順序并設(shè)置自傳輸控制。本文提出的基于鎖位的并行二進制分割防碰撞算法(LPBS)，結(jié)合了上述兩種技術(shù)的優(yōu)點，在減少閱讀器和標簽之間傳送的比特數(shù)量的同時，減少碰撞時隙，時間開銷也比傳統(tǒng)的二叉樹防碰撞算法有一定的改進。圖1顯示了并行二進制分割技術(shù)和深度優(yōu)先搜索(DFS)[13]技術(shù)之間的差異。

(a) 深度優(yōu)先搜索(DFS)路徑

(b) 并行二進制分割路徑圖1 兩種方法的路徑示意圖

1.1 相關(guān)定義

(1) Lock-request(ID,1)：該指令表示鎖位指令。閱讀器發(fā)送位查詢請求，檢測發(fā)生碰撞的位置，如果沖突置為1，反之無沖突為0。當標簽接到鎖位的指令時，比較自身與閱讀器的序列，提取出置為1的比特位，組成新的一輪查詢序列號，而沒有產(chǎn)生碰撞的位置信息可以忽略，下一輪查詢也無需再次發(fā)送。

(2) request(x,p)：查詢指令。閱讀器的查詢前綴為第一個參數(shù)，碰撞位置的最高位作為第二個參數(shù)。

標簽采用簡單的邏輯運算，基于兩個計數(shù)器和兩個寄存器，實現(xiàn)自傳輸控制和動態(tài)更新回復(fù)命令。寄存器和計數(shù)器的定義如下：

(1) 當前路徑寄存器(CPR):用于存儲當前該位級別的路徑數(shù)(二進制分支數(shù)量)。

(2) 下一條路徑計數(shù)器(NPC)：用于存儲連續(xù)發(fā)現(xiàn)路徑的總數(shù)。當碰撞的標簽回復(fù)閱讀器時，該計數(shù)器增加，任何碰撞都會增加二進制分支的數(shù)量。CPR的值將在每輪二進制分割結(jié)束后由該計數(shù)器中的內(nèi)容加載。

(3) 當前順序寄存器(COR)：用于在CPR中存儲相對于當前路徑數(shù)目的標簽回復(fù)順序。

(4) 下一個順序計數(shù)器(NOC)：用于跟蹤記錄標簽回復(fù)順序的變化，當二叉樹中出現(xiàn)一個新的子樹時，它會增加。在每層子樹分裂結(jié)束時，COR將被NOC內(nèi)容加載。

1.2 閱讀器操作

初始化閱讀器堆棧，發(fā)出查詢請求，閱讀器根據(jù)標簽的應(yīng)答不斷更新現(xiàn)有的偽二叉樹。閱讀器通過掃描之前二進制分割級(上一層子樹)發(fā)現(xiàn)的路徑，來探索潛在的分支路徑節(jié)點信息。檢測到碰撞發(fā)送1，沒有碰撞發(fā)送0。每個標簽都知道當前的回復(fù)順序，閱讀器通過標簽的回答報告標簽的傳輸狀態(tài)(碰撞或無碰撞)來更新該順序。

1.3 標簽操作

標簽操作具體描述如下：

1) 標簽接收閱讀器啟動命令。

2) 標簽重置計數(shù)器和寄存器的值。

3) 一位標簽響應(yīng)其回復(fù)順序，一個比特閱讀器緊跟著報告結(jié)果。

4) 在之前的二進制分割級別(即上一層子樹)中，掃描之前發(fā)現(xiàn)的路徑(節(jié)點)。

5) 每個子樹發(fā)送當前層中的當前標記位。

6) 每個節(jié)點的閱讀器通知標簽沖突狀態(tài)。

7) 標簽修改各自控制計數(shù)器如下：如果“沒有碰撞”，那么它的順序和路徑總數(shù)沒有變化；如果“碰撞”，那么增加總數(shù)路徑(NPC++)。

8) 標簽接到鎖位指令Lock-request(ID,1)，比較自身與閱讀器的序列，提取出置為1的比特位，生成新的一輪查詢序列號，忽略沒有產(chǎn)生碰撞的位置信息，下一輪查詢也無需再次發(fā)送。如果在當前級別中沒有掃描標簽，或者如果標簽通過發(fā)送它的標記位1來參與當前的標簽沖突，那么在下一個分割級別中增加其應(yīng)答順序(增加NOC的值)。

9) 寄存器(COR,CPR)由相應(yīng)計數(shù)器的內(nèi)容更新(NOC,NPC)，標簽接收request(x,p)查詢指令，將上一輪產(chǎn)生碰撞的標簽位組成新的查詢前綴。

10) 掃描下一個分割級別，并重復(fù)從步驟4)開始的過程，直到完成ID長度的“n”級別。

2 算法性能分析

本節(jié)將從多個角度分析LPBS算法的時間復(fù)雜度、吞吐率以及標簽通信的復(fù)雜度。時間復(fù)雜度可以通過分析總時隙數(shù)驗證，而標簽通信復(fù)雜度可以通過標簽發(fā)送的位數(shù)驗證。

閱讀器通過圖2所示的順序掃描樹節(jié)點來重建二叉樹，并在每個節(jié)點接收標簽響應(yīng)。表1詳細描述了基于LPBS算法下分支節(jié)點探測的過程。

圖2 并行分裂掃描用于探索路徑

表1 LPBS算法的防碰撞過程(---:靜默)

續(xù)表1

(1) 傳輸總比特數(shù)(標簽與閱讀器之間)。如圖1(b)所示，除葉子節(jié)點外，樹節(jié)點的數(shù)量等于9個節(jié)點。每個節(jié)點消耗1位用于標簽響應(yīng)，閱讀器消耗1位用于報告每個節(jié)點的類型(碰撞或無碰撞)。

通過閱讀器發(fā)送的比特數(shù)量和通過標簽發(fā)送的比特數(shù)量相同，均為9比特。因此，閱讀器和標簽之間傳輸?shù)目偙忍財?shù)等于兩項之和，為18比特。而文獻[14]為了標識與本文例子中相同數(shù)量的樹節(jié)點，使用了30個比特位。

(2) 總時隙數(shù)分析?？倳r隙數(shù)也稱為時間復(fù)雜度，可以分為空閑時隙和碰撞時隙兩種狀態(tài)進行分析。

無空閑時隙狀態(tài)，在本文中只討論二叉樹情況，因此不存在四叉樹、多叉樹混合查詢的情況。當查詢過程中沒有空閑時隙時，可以看成是完全二叉樹查詢，Tem代表空閑時隙的數(shù)量，則此時Tem等于0。假設(shè)總時隙數(shù)為T，碰撞時隙為Tc，閱讀器詢問區(qū)中的標簽數(shù)量為m，則有：

T=Tem+Tc+m

(1)

當進行完全二叉樹查詢時：

T=2m-1

(2)

(3) 吞吐率。單位時間內(nèi)某信道成功交付數(shù)據(jù)的平均速率為：

S=m/T

(3)

3 算法仿真及分析

本文通過MATLAB平臺進行該算法的仿真實驗，假設(shè)：(1) 閱讀器具有豐富的記憶和較強的計算能力；(2) 標簽的內(nèi)存和計算能力有限；(3) 閱讀器和標簽之間有一個共享的通信信道；(4) 標簽不能相互交換信息。

如圖3所示，比較LPBS算法與動態(tài)按位仲裁算法(DBS)[16]在標簽數(shù)與總的傳輸比特數(shù)量之間的關(guān)系，可以看出LPBS算法中閱讀器與標簽之間傳輸?shù)目偟谋忍財?shù)量比DBS算法少。

圖3 標簽數(shù)與傳輸比特數(shù)的關(guān)系

圖4為ID長度為16比特的情況下，識別標簽所用的時間與標簽數(shù)量之間的關(guān)系?？梢钥闯?，BIBD[15]算法識別300個標簽需要花費480 ms，傳統(tǒng)的查詢樹算法需要花費2 550 ms。動態(tài)查詢樹算法需要1 500 ms識別所有的標簽，而本文提出的LPBS算法則只需要143 ms。

圖4 40 KB/s速率下標簽數(shù)量與識別時間的關(guān)系

圖5為LPBS算法和QT[3]算法、DBS算法、BIBD算法在總時隙數(shù)方面的比較?？梢钥闯觯S著標簽數(shù)量的增多，本文提出的LPBS算法與其余兩種算法相比，所需的總時隙數(shù)明顯更少。

圖5 標簽數(shù)量與總時隙數(shù)的關(guān)系

4 結(jié) 語

本文提出了一種新的基于鎖位的并行二進制分割防碰撞算法(LPBS)，可以應(yīng)用于UHF RFID多標簽識別防碰撞系統(tǒng)中。LPBS算法利用曼徹斯特編碼按位判斷，確定并提取碰撞位，使得非碰撞位的信息無需再次傳輸。同時，采用并行二進制分割技術(shù)，使得閱讀器和標簽可以進行一位標簽應(yīng)答。該方法可以動態(tài)修改標簽與標簽之間的相對回復(fù)順序，將閱讀器傳輸?shù)男畔⒆钚』癁閮H一位反饋。該算法在減少閱讀器和標簽之間傳送的比特數(shù)量的同時，減少碰撞時隙，時間開銷也比傳統(tǒng)的二叉樹防碰撞算法有一定的改進。通過性能分析和仿真實驗表明，本文算法在大多數(shù)情況下優(yōu)于已有的防碰撞算法。