一種減少通信復雜度的RFID搜索樹防碰撞算法*

莫 磊，唐 斌，房夢旭

(1.成都航空職業技術學院 信息工程學院，成都 610100；2.四川省高校校企聯合“航空電子技術”應用技術創新基地，成都 610100)

0 引 言

典型的射頻識別(Radio Frequency Identification,RFID)系統一般由電子標簽和閱讀器組成[1]，其防碰撞問題主要有三種情況，分別是一個閱讀器作用范圍內有多個標簽、多個閱讀器作用范圍內有一個標簽和多個閱讀器作用范圍內有多個標簽，涉及的問題主要有多標簽碰撞問題和多閱讀器碰撞問題。由于標簽的成本低、能量少、內存小、計算處理能力弱，RFID防碰撞問題的難點主要集中在多標簽防碰撞方面。本文針對第一種情況進行研究。在這種情況下，由于所有的電子標簽與閱讀器共用一個信道，當有多個標簽處于同一閱讀器的作用范圍內，在同一時刻向閱讀器發送數據時就會發生碰撞，導致閱讀器不能讀取標簽數據[2]。

現階段多標簽防碰撞算法一般是基于時分多路的方法，主要有基于二進制搜索樹的防碰撞算法和基于ALOHA的防碰撞算法[3]。ALOHA算法是一種基于概率統計的防碰撞算法，讀取量大，速度快，但很多情況下讀取率達不到100%，存在由于多次讀不到某一標簽而出現“饑餓”問題[4]。二進制樹算法是一種確定性算法，不存在“饑餓”問題，讀取率可以達到100%，但通信量大，讀取時間長[5]。本文重點研究二進制樹算法。

在搜索樹算法中，除了總時隙指標以外，通信復雜度也是非常重要的指標，它是識別所有標簽所需傳送的總比特數[6]，在查詢時隙相同的情況下，單位時隙通信數據量越少，則通信復雜度越低。本文以二叉樹搜索為載體，重點討論單位時隙的通信復雜度問題。首先介紹現有的典型二叉樹搜索算法，接著提出了一種減少通信復雜度(Reducing Communication Complexity，RCC)的防碰撞算法，最后對幾種算法進行了比較和仿真，結果表明本文算法明顯優于現有的二叉樹搜索算法。

1 傳統搜索樹防碰撞算法

基本二進制搜索(Binary Search,BS)算法[7]的主要思想是，把處于碰撞狀態的標簽分成子集0和子集1，先查詢子集0，若無碰撞，則識別出一個標簽；若有碰撞，再把子集0分成00子集和01子集，先查詢子集00，這樣不斷查詢下去，最終可識別出一個標簽；接著再從頭開始搜索，循環往復，直到識別出所有標簽[8]。

基本二進制搜索算法在識別出一個標簽后，再從頭開始搜索，識別效率低下。后退式二進制搜索(Regressive Binary Search,RBS)防碰撞算法[9]對此作了改進，當識別出一個標簽后，不是從頭開始搜索，而是回到上一節點開始搜索，這樣，搜索次數大大減少，搜索效率得到較大提高。

在基本二進制搜索算法中，每一次搜索，標簽的數據總是被完整地傳給閱讀器，數據傳送時間長、耗能多。動態二進制搜索(Dynamic Binary Search,DBS)防碰撞算法[10]對此作了改進，閱讀器只發送部分數據給標簽，另一部分標簽已知的數據則不予發送；標簽只返回部分數據給閱讀器，另一部分閱讀器已知的數據則不予發送，閱讀器發送的數據和標簽返回的數據都是動態變化的。通過動態搜索，閱讀器和標簽每個時隙發送的數據比特數減少，提高了搜索速率。

碰撞樹(Collision Tree,CT)算法[11]是一個優秀的二叉樹算法，它根據閱讀器檢測到的碰撞位信息直接生成兩個新的前綴，根據前綴對標簽進行搜索，ID和前綴相符合的標簽響應命令并反饋前綴以后的ID數據給閱讀器。CT算法大幅度提高了RFID多標簽識別的性能，開啟了基于碰撞樹的防碰撞算法系列，并成為該算法系列的代表算法[12]。

2 RCC算法

2.1 算法原理

算法的核心思想有兩個：一是減少閱讀器搜索的次數；二是減少搜索時閱讀器和標簽間通信的數據比特數。

在傳統的二進制搜索法中，通過前綴對標簽進行搜索，存在閱讀器反復發送標簽已知數據的問題。在本文算法中，閱讀器不再發送標簽搜索前綴，而是通過發送前綴長度信息，結合標簽是否為當前響應子集對標簽進行分類搜索，可有效避免閱讀器重復發送數據。

在標簽中設置前綴長度寄存器Q和響應標志寄存器R。在Q中存儲前綴長度信息，R的取值為0或1，以區分和搜索當前0子集和1子集，實現返回式搜索。

當發現只有一個碰撞位時，可直接識別出兩個標簽，減少了標簽搜索的次數，進一步提高了標簽搜索的速率。

2.2 算法命令

設標簽ID長度為N，按位表示為[N-1，N-2，…，1，0]。前綴長度寄存器Q的初始值為0，響應標志寄存器R的初始值為0。在閱讀器設置堆棧存儲區，存儲1子集前綴長度信息，并按后進先出的原則對數據進行存取。

為了便于理解，先介紹幾個閱讀器命令。

(1)request(ε)：初始搜索命令。收到此命令的標簽發送序列號給閱讀器。

(2)request(0,P)：0子集搜索命令。標志寄存器R為0的標簽響應命令，更新前綴長度寄存器Q為P，設K=N-P-1，第K位為‘0’的標簽返回第K-1～0位數據給閱讀器，第K位為‘1’的標簽更新標志寄存器R為1。

(3)request(1,P)：1子集搜索命令。標志寄存器R為1，前綴長度寄存器Q為P的標簽響應命令，設K=N-P-1，返回第K-1～0位數據給閱讀器，同時更新標志寄存器R為0。

2.3 算法流程

算法實現步驟如下：

Step1 閱讀器發送request(ε)請求命令。

Step2 所有收到請求命令標簽同時發送序列號數據給閱讀器。

Step3 閱讀器檢測數據并根據數據位碰撞情況作出相應的處理。若沒有接收到任何數據，則說明在閱讀器附近沒有標簽，轉至Step 6；若接收到數據，但沒有任何碰撞，則可識別一個標簽，轉至Step 5；若檢測到只有一個序列號數據位發生碰撞，則可直接識別兩個標簽，轉至Step 5；若檢測到有兩個或兩個以上的序列號數據位發生碰撞，設最高序列號碰撞位為標簽的第K位，則P=N-K-1，閱讀器把P值存儲到閱讀器堆棧區；閱讀器發送request(0，P)請求命令。

Step4 標志寄存器R為0的標簽響應命令，更新前綴長度寄存器Q為P，設K=N-P-1，第K位為‘0’的標簽返回第K-1～0位數據給閱讀器，第K位為‘1’的標簽更新標志寄存器R為1，轉至Step 3。

Step5 閱讀器識別出標簽序列號，對標簽數據進行讀寫，讓標簽處于“無聲”狀態。

Step6 閱讀器彈出堆棧存儲區數據，若堆棧為空，則搜索結束；若堆棧不為空，設數據為P，閱讀器發送request(1,P)請求命令。

Step7 前綴長度寄存器Q為P的標簽響應命令，設K=N-P-1，返回第K-1～0位數據給閱讀器，同時更新標志寄存器R為0。

Step8 跳至Step 3。依此循環，直到堆棧為空，識別出所有標簽。

算法流程如圖1所示。

圖1 RCC算法流程

2.4 算法舉例

假設閱讀器作用范圍內有4個標簽，序列號為10位，即N=10，如表1所示。

表1 標簽及其序列號

RCC防碰撞算法識別標簽過程見表2。識別4個標簽，總共用了7個時隙，在總時隙數上小于BS算法和DBS算法，與CT算法相同；在通信復雜度上，由于通信時閱讀器只發送前綴長度信息和標簽只返回碰撞位以后信息，通信數據比特數少于CT算法，更少于BS算法和DBS算法。

表2 RCC防碰撞算法識別過程

表2(續)

2.5 算法分析

由2.4節可以看出，RCC算法和CT算法相比，搜索次數和通信復雜度都進一步減少。

2.5.1 搜索次數

CT算法的搜索次數為2N-1次[11]；設閱讀器接收數據中僅出現一個碰撞位的情況為H次，則RCC防碰撞算法的搜索次數為2N-2H-1次，次數少了2H次。

2.5.2 通信復雜度

由于閱讀器僅發送查詢前綴長度信息，標簽僅返回碰撞位以后信息，閱讀器和標簽間的通信數據量大大減少。假設標簽序列號長度為N，搜索前綴長度為L，則每個查詢時隙中，CT算法的通信數據比特數為N，RCC算法的通信數據比特數為(lbL+N-L)，RCC算法相比CT算法每個查詢時隙減少了(L- lbL)比特通信數據量。

2.6 算法仿真

為了檢驗和比較算法的性能，利用Matlab軟件對算法進行了仿真。假設信道是理想的，標簽ID的長度為128 b，標簽數量在0～100之間變化，仿真100次取平均值，不計控制命令前綴、后綴及檢驗冗余等開銷，對查詢時隙和通信復雜度等指標進行仿真和比較。

2.6.1 總時隙數

圖2為總時隙數對比圖，由圖可見，BS算法和DBS算法的總時隙數大致相同，具有最大的總時隙數；CT算法和RBS算法的總時隙數大致相同；所有算法中RCC算法的總時隙數最小。這是由于RCC算法通過標志寄存器和堆棧存取實現了返回式搜索，且在只有一個碰撞位時直接識別兩個標簽。

圖2 總時隙數對比

2.6.2 單位時隙通信復雜度

圖3為單位時隙通信復雜度對比圖，即平均每個查詢時隙閱讀器和標簽間數據通信比特數。由圖可見，在每個查詢時隙中，BS算法和RBS算法具有大致相同的通信復雜度，CT算法和DBS算法具有大致相同的通信復雜度，所有算法中RCC算法具有最小的通信復雜度。這是由于RCC算法中閱讀器僅發送前綴長度信息，標簽僅返回前綴以后比特信息，大大減少了數據通信量。

圖3 單位時隙通信復雜度對比

2.6.3 總通信復雜度

圖4為總通信復雜度即完成所有標簽識別所需要的通信數據比特數對比。由圖可見，BS算法具有最大的總通信復雜度。這是由于BS算法不僅具有最大的總時隙數，還具有最大的單位時隙通信復雜度。在標簽數較大時，DBS算法比RBS算法具有更大的通信復雜度。這是由于DBS算法的總時隙數大于RBS算法，但單位時隙通信復雜度小于RBS算法，且隨著標簽數的增大，DBS算法總時隙數的增長斜率逐漸增大。所有算法中，RCC算法具有最小的總通信復雜度。

圖4 總通信復雜度對比

由仿真結果可以看出，本文算法和傳統二叉樹搜索算法相比，閱讀器和標簽間的數據通信量更少，閱讀器識別時間更快，因此，本文算法優于傳統的二叉樹搜索算法。

3 結 論

本文對現有的二叉樹搜索算法進行了分析和比較，并提出了一個新的解決方案，在標簽中設置前綴長度寄存器以便存儲前綴長度信息，設置標志寄存器以便區分和搜索標簽0子集和1子集，閱讀器僅需發送前綴長度信息即可對標簽進行分類搜索，同時，在閱讀器設置堆棧存儲區，按后進先出的原則存儲標簽前綴序列號長度信息，配合后退式算法進行標簽搜索；在閱讀器接收數據只有一個碰撞位時，直接識別兩個標簽。這些措施有效減少了二叉樹算法中閱讀器搜索標簽的次數，減少了閱讀器和標簽間的數據通信量，減少了標簽的能量消耗，減少了閱讀器識別標簽的時間，提高了閱讀器搜索標簽的效率。