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

莫 磊，唐 斌，房夢旭

(1.成都航空職業(yè)技術(shù)學(xué)院 信息工程學(xué)院，成都 610100；2.四川省高校校企聯(lián)合“航空電子技術(shù)”應(yīng)用技術(shù)創(chuàng)新基地，成都 610100)

0 引 言

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

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

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

1 傳統(tǒng)搜索樹防碰撞算法

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

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

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

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

2 RCC算法

2.1 算法原理

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

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

在標簽中設(shè)置前綴長度寄存器Q和響應(yīng)標志寄存器R。在Q中存儲前綴長度信息，R的取值為0或1，以區(qū)分和搜索當前0子集和1子集，實現(xiàn)返回式搜索。

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

2.2 算法命令

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

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

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

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

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

2.3 算法流程

算法實現(xiàn)步驟如下：

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

Step2 所有收到請求命令標簽同時發(fā)送序列號數(shù)據(jù)給閱讀器。

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

Step4 標志寄存器R為0的標簽響應(yīng)命令，更新前綴長度寄存器Q為P，設(shè)K=N-P-1，第K位為‘0’的標簽返回第K-1～0位數(shù)據(jù)給閱讀器，第K位為‘1’的標簽更新標志寄存器R為1，轉(zhuǎn)至Step 3。

Step5 閱讀器識別出標簽序列號，對標簽數(shù)據(jù)進行讀寫，讓標簽處于“無聲”狀態(tài)。

Step6 閱讀器彈出堆棧存儲區(qū)數(shù)據(jù)，若堆棧為空，則搜索結(jié)束；若堆棧不為空，設(shè)數(shù)據(jù)為P，閱讀器發(fā)送request(1,P)請求命令。

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

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

算法流程如圖1所示。

圖1 RCC算法流程

2.4 算法舉例

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

表1 標簽及其序列號

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

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

表2(續(xù))

2.5 算法分析

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

2.5.1 搜索次數(shù)

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

2.5.2 通信復(fù)雜度

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

2.6 算法仿真

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

2.6.1 總時隙數(shù)

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

圖2 總時隙數(shù)對比

2.6.2 單位時隙通信復(fù)雜度

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

圖3 單位時隙通信復(fù)雜度對比

2.6.3 總通信復(fù)雜度

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

圖4 總通信復(fù)雜度對比

由仿真結(jié)果可以看出，本文算法和傳統(tǒng)二叉樹搜索算法相比，閱讀器和標簽間的數(shù)據(jù)通信量更少，閱讀器識別時間更快，因此，本文算法優(yōu)于傳統(tǒng)的二叉樹搜索算法。

3 結(jié) 論

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