基于鎖位的并行二進制分割防碰撞算法研究

賀曉霞 賈小林

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

0 引 言

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

(1) 采用并行方式實現多卡識別；(2) 根據規定時間，電子標簽挨個發送數據，在此時間內只有一個電子標簽在工作。

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

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

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

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

1 算法設計

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

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

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

1.1 相關定義

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

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

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

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

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

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

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

1.2 閱讀器操作

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

1.3 標簽操作

標簽操作具體描述如下：

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

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

3) 一位標簽響應其回復順序，一個比特閱讀器緊跟著報告結果。

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

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

6) 每個節點的閱讀器通知標簽沖突狀態。

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

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

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

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

2 算法性能分析

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

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

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

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

續表1

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

通過閱讀器發送的比特數量和通過標簽發送的比特數量相同，均為9比特。因此，閱讀器和標簽之間傳輸的總比特數等于兩項之和，為18比特。而文獻[14]為了標識與本文例子中相同數量的樹節點，使用了30個比特位。

(2) 總時隙數分析。總時隙數也稱為時間復雜度，可以分為空閑時隙和碰撞時隙兩種狀態進行分析。

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

T=Tem+Tc+m

(1)

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

T=2m-1

(2)

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

S=m/T

(3)

3 算法仿真及分析

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

如圖3所示，比較LPBS算法與動態按位仲裁算法(DBS)[16]在標簽數與總的傳輸比特數量之間的關系，可以看出LPBS算法中閱讀器與標簽之間傳輸的總的比特數量比DBS算法少。

圖3 標簽數與傳輸比特數的關系

圖4為ID長度為16比特的情況下，識別標簽所用的時間與標簽數量之間的關系。可以看出，BIBD[15]算法識別300個標簽需要花費480 ms，傳統的查詢樹算法需要花費2 550 ms。動態查詢樹算法需要1 500 ms識別所有的標簽，而本文提出的LPBS算法則只需要143 ms。

圖4 40 KB/s速率下標簽數量與識別時間的關系

圖5為LPBS算法和QT[3]算法、DBS算法、BIBD算法在總時隙數方面的比較。可以看出，隨著標簽數量的增多，本文提出的LPBS算法與其余兩種算法相比，所需的總時隙數明顯更少。

圖5 標簽數量與總時隙數的關系

4 結 語

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