莫 磊，陳 偉，任 菊

(成都航空職業(yè)技術(shù)學(xué)院 信息工程學(xué)院，成都 610100)

(*通信作者電子郵箱nqnt@163.com)

計數(shù)型雙時隙射頻識別防碰撞算法

莫 磊*，陳 偉，任 菊

(成都航空職業(yè)技術(shù)學(xué)院 信息工程學(xué)院，成都 610100)

(*通信作者電子郵箱nqnt@163.com)

針對射頻識別(RFID)二進(jìn)制搜索防碰撞算法搜索次數(shù)多、通信數(shù)據(jù)量大等問題，在后退式搜索樹算法和時隙算法的基礎(chǔ)上，提出一種新的計數(shù)型雙時隙RFID防碰撞算法CBS。CBS算法根據(jù)標(biāo)簽中的時隙計數(shù)器和閱讀器收到的碰撞位信息對標(biāo)簽進(jìn)行逐級分類搜索，并將應(yīng)答標(biāo)簽分為兩組，分別在兩個時隙向閱讀器返回數(shù)據(jù)信息；且閱讀器僅發(fā)送最高碰撞位位置信息，而標(biāo)簽僅返回最高碰撞位以后的數(shù)據(jù)位。理論分析和仿真結(jié)果表明：和傳統(tǒng)的后退式二進(jìn)制搜索(RBS)算法相比，CBS算法搜索次數(shù)減少了51%以上，數(shù)據(jù)通信量減少了65%以上。CBS算法性能優(yōu)于其他常用防碰撞算法，能大幅度減少搜索次數(shù)和數(shù)據(jù)通信量，提高搜索效率。

射頻識別；雙時隙；搜索樹；防碰撞；時隙計數(shù)器

0 引言

射頻識別(Radio Frequency IDentification, RFID)是一種非接觸式自動識別技術(shù)，在一個多標(biāo)簽的RFID系統(tǒng)中，由于標(biāo)簽和閱讀器共用一個信道，當(dāng)多個標(biāo)簽同時向閱讀器發(fā)送數(shù)據(jù)時，就會發(fā)生數(shù)據(jù)碰撞，導(dǎo)致閱讀器不能正確識別標(biāo)簽[1]。由于標(biāo)簽的能量低、處理能力弱、存儲空間有限、沒有數(shù)據(jù)偵測能力，很多傳統(tǒng)的防碰撞算法都不適用于RFID[2]。現(xiàn)階段的RFID防碰撞算法通常都是基于時分多址的方法，主要有基于ALOHA的不確定性算法和基于搜索樹的確定性算法[3]。

ALOHA算法主要有：時隙ALOHA算法、幀時隙ALOHA算法、動態(tài)幀時隙ALOHA算法等[4]，這些算法相對比較簡單，但隨著標(biāo)簽數(shù)量的增大，其性能迅速惡化。為了改善其性能，有學(xué)者在此基礎(chǔ)上提出了增強(qiáng)型動態(tài)幀時隙ALOHA算法[5]、分組動態(tài)幀時隙ALOHA 算法[6]、分組自適應(yīng)分配時隙ALOHA算法[7]等，其性能有所改善，但仍存在隨機(jī)性大、性能不穩(wěn)定、吞吐率低、效率不高等問題，且存在由于標(biāo)簽在長時間內(nèi)不能被識別而導(dǎo)致的“饑餓”問題。

搜索數(shù)算法是確定性算法，不存在標(biāo)簽“饑餓”問題，主要有：二進(jìn)制搜索樹(Binary Search, BS)算法、后退式二進(jìn)制搜索樹(Regressive Binary Search, RBS)算法、動態(tài)二進(jìn)制搜索樹(Dynamic Binary Search, DBS)算法[8]等。BS算法是最基本的二進(jìn)制搜索算法，RBS算法相對BS算法減少了搜索次數(shù)，DBS算法相對于BS算法則減少了冗余傳輸。在標(biāo)簽較多時，這些算法存在數(shù)據(jù)傳輸量大、搜索次數(shù)多等問題，對此，學(xué)者們又作了進(jìn)一步的改進(jìn)：文獻(xiàn)[9]中提出一種四叉樹搜索算法，根據(jù)碰撞位進(jìn)行四叉樹搜索，減少了搜索次數(shù)，但增加了空閑時隙；文獻(xiàn)[10]中提出一種改進(jìn)的多叉樹搜索算法，根據(jù)碰撞位的不同來動態(tài)選擇二叉樹搜索或四叉樹搜索，但并沒有消除搜索過程中的空閑時隙；文獻(xiàn)[11]對此作了改進(jìn)，提出IAMS(Improved Adaptive Multi-tree Search)算法，通過碰撞因子來動態(tài)選擇二進(jìn)制或四進(jìn)制搜索，同時，在四叉樹時，通過查詢最高兩個碰撞位信息來消除空閑時隙，但卻增加了查詢時隙；文獻(xiàn)[12]中提出一種增強(qiáng)型多叉樹搜索算法——EBST(Enhanced RFID anti-collision algorithm Based on Search Tree)算法，根據(jù)相鄰碰撞位的個數(shù)，通過查詢搜索前綴命令，動態(tài)選擇二叉樹搜索、四叉樹搜索或八叉樹搜索，雖消除了空閑時隙，但還是增加了查詢時隙，仍有較大的系統(tǒng)通信量。這些算法或多或少都存在算法較復(fù)雜、對標(biāo)簽處理能力要求較高、增加了空閑時隙或查詢時隙等問題。

文獻(xiàn)[13]中提出一種基于轉(zhuǎn)換碼的雙時隙RFID搜索算法，這種算法僅在有連續(xù)三個碰撞位時為雙時隙發(fā)送，其他情況則根據(jù)碰撞位情況采用二叉樹或四叉樹方法搜索，仍為單時隙發(fā)送，這種算法既沒消除空閑時隙，又增加了查詢時隙，系統(tǒng)性能提高有限。

綜合ALOHA算法和搜索樹算法的優(yōu)點(diǎn)，本文提出了一種新的算法：計數(shù)型雙時隙搜索(Counter and Bi-Slot Search, CBS)算法。CBS算法在每一次搜索中進(jìn)行確定性的雙時隙數(shù)據(jù)發(fā)送，不增加查詢時隙，完全避免空閑時隙，能夠大幅度減少標(biāo)簽搜索次數(shù)，提高搜索效率。

1 計數(shù)型雙時隙防碰撞算法

CBS算法在標(biāo)簽中僅設(shè)置一個時隙計數(shù)器，根據(jù)閱讀器命令進(jìn)行加減計數(shù)；同時，在閱讀器中設(shè)置一個堆棧和一個控制寄存器，閱讀器根據(jù)碰撞位信息、控制寄存器和堆棧數(shù)據(jù)信息發(fā)出請求命令，標(biāo)簽收到閱讀器命令后，首先更新時隙計數(shù)器，確定哪些標(biāo)簽需要向閱讀器返回數(shù)據(jù)，在哪個時隙向閱讀器返回數(shù)據(jù)。

時隙計數(shù)器可以通過在標(biāo)簽中改變硬件電路來實(shí)現(xiàn)，也可以通過軟件編程來實(shí)現(xiàn)。

時隙計數(shù)器的作用主要有：1)確定應(yīng)答標(biāo)簽范圍，計數(shù)值為0和1的標(biāo)簽為應(yīng)答標(biāo)簽。在本文中，應(yīng)答標(biāo)簽的含義是指能夠響應(yīng)閱讀器命令并需向閱讀器返回數(shù)據(jù)的標(biāo)簽。2)確定哪些標(biāo)簽在時隙1發(fā)送數(shù)據(jù)，哪些標(biāo)簽在時隙2發(fā)送數(shù)據(jù)：時隙計數(shù)器更新后，計數(shù)值為0的標(biāo)簽在時隙1發(fā)送數(shù)據(jù)，計數(shù)值為1的標(biāo)簽在時隙2發(fā)送數(shù)據(jù)。3)減少閱讀器和標(biāo)簽間收發(fā)數(shù)據(jù)的比特數(shù)。

閱讀器堆棧和控制寄存器可確定閱讀器請求命令參數(shù)，具體方法在下面的命令規(guī)則和算法步驟中進(jìn)行詳細(xì)講解。

在以下論述中，假設(shè)標(biāo)簽ID的長度為L,按位表示為：(L-1,…,1,0)。

1.1 命令規(guī)則

為了便于描述算法，引入以下閱讀器命令。

1)request(null):閱讀器首次搜索請求命令，所有標(biāo)簽分兩步執(zhí)行命令：①時隙計數(shù)器初始化，第L-1位為0的標(biāo)簽計數(shù)值為0，第L-1位為1的標(biāo)簽計數(shù)值為1；②返回數(shù)據(jù)，計數(shù)值為0的標(biāo)簽在時隙1返回數(shù)據(jù)給閱讀器，計數(shù)值為1的標(biāo)簽在時隙2返回數(shù)據(jù)給閱讀器。

2)request(X，H):閱讀器請求命令，其中X為兩位二進(jìn)制數(shù)。標(biāo)簽分兩步執(zhí)行命令：①更新時隙計數(shù)器；②返回數(shù)據(jù)，計數(shù)值為0的標(biāo)簽在時隙1返回數(shù)據(jù)給閱讀器，計數(shù)值為1的標(biāo)簽在時隙2返回數(shù)據(jù)給閱讀器。

更新時隙計數(shù)器的方法：

若X=00：計數(shù)值為0第H位為0的標(biāo)簽計數(shù)值不變，其余標(biāo)簽(計數(shù)值為0第H位為1的標(biāo)簽,計數(shù)值大于0的標(biāo)簽)計數(shù)值加1；

若X=01：計數(shù)值為0第H位為1的標(biāo)簽計數(shù)值更新為1，其余標(biāo)簽計數(shù)值不變；

若X=10：計數(shù)值為1第H位為0的標(biāo)簽計數(shù)值更新為0，其余標(biāo)簽計數(shù)值不變；

若X=11：首先，所有標(biāo)簽計數(shù)值減1，然后計數(shù)值為1第H位為0的標(biāo)簽計數(shù)值更新為0。

1.2 算法原理

每個標(biāo)簽都有兩個時隙，閱讀器根據(jù)碰撞位信息進(jìn)行分類搜索，應(yīng)答標(biāo)簽分為兩組，計數(shù)值為0的一組在時隙1返回數(shù)據(jù)，計數(shù)值為1的一組在時隙2返回數(shù)據(jù)。

時隙按碰撞位情況可以分為識別時隙和沖突時隙。識別時隙分兩種情況：一種情況是無碰撞位，則識別一個標(biāo)簽；一種情況是只有一個碰撞位，則直接識別兩個標(biāo)簽。有兩個或兩個以上碰撞位的時隙為沖突時隙。

閱讀器設(shè)堆棧，按先入后出的規(guī)則存取數(shù)據(jù)。

閱讀器設(shè)置控制寄存器X，X是長度為兩位的二進(jìn)制數(shù)，初始值為00。當(dāng)時隙1為沖突時隙，則X高位為0；當(dāng)時隙1為識別時隙，則X高位為1。當(dāng)時隙2為沖突時隙，則X低位為0；當(dāng)時隙2為識別時隙，則X低位為1。

1)閱讀器初始化堆棧為空,閱讀器發(fā)送請求命令request(null)。

2)所有標(biāo)簽響應(yīng)命令，首先，初始化標(biāo)簽時隙計數(shù)器；接著，標(biāo)簽返回數(shù)據(jù)，計數(shù)值為0的標(biāo)簽在時隙1發(fā)送ID的L-2～0位數(shù)據(jù)給閱讀器；計數(shù)值為1的標(biāo)簽在時隙2發(fā)送ID的L-2～0位數(shù)據(jù)給閱讀器。

3)閱讀器在兩個時隙接收數(shù)據(jù)，分以下四種情況：

①兩個時隙都為識別時隙：更新控制寄存器，X=11，轉(zhuǎn)至步驟5)。

②時隙1為識別時隙，時隙2為沖突時隙：更新控制寄存器，X=10；設(shè)時隙2最高碰撞位為H,把H壓入堆棧，轉(zhuǎn)至步驟5)。

③時隙1為沖突時隙，時隙2為識別時隙：更新控制寄存器，X=01；設(shè)時隙1最高碰撞位為H,把H壓入堆棧。轉(zhuǎn)至步驟5)。

④兩個時隙都為沖突時隙：更新控制寄存器，X=00；設(shè)時隙1最高碰撞位為H,閱讀器發(fā)出請求命令request(00，H)；設(shè)時隙2最高碰撞位為H′,把H′壓入堆棧。

4)所有標(biāo)簽更新計數(shù)值后，計數(shù)值為0的標(biāo)簽在時隙1返回ID的H-1～0位數(shù)據(jù)給閱讀器，計數(shù)值為1的標(biāo)簽在時隙2返回ID的H-1～0位數(shù)據(jù)給閱讀器，轉(zhuǎn)至步驟3)。

5)閱讀器選中已識別標(biāo)簽，讀取標(biāo)簽數(shù)據(jù)，令標(biāo)簽為休眠態(tài)，休眠態(tài)標(biāo)簽不再響應(yīng)閱讀器命令。閱讀器判定堆棧是否為空，若堆棧為空，搜索結(jié)束；若堆棧不為空，彈出堆棧數(shù)據(jù)，設(shè)為H,若控制寄存器為X，則閱讀器發(fā)出請求命令request(X，H)。

1.3 算法舉例

下面通過具體例子來說明RFID雙時隙防碰撞算法搜索過程，假設(shè)閱讀器作用范圍內(nèi)有8個標(biāo)簽，它們的ID號長度都為10 bit，分別為：A：0010110001，B：1010101010，C：0001110110，D：0001101011，E：0001100011，F(xiàn)：1101110001，G：1101010001, H：1010001010。搜索過程如表1所示。其中的閱讀器請求命令比特數(shù)是指閱讀器請求命令參數(shù)的數(shù)據(jù)比特數(shù)，閱讀器接收數(shù)據(jù)比特數(shù)即標(biāo)簽發(fā)送數(shù)據(jù)比特數(shù)。

第1次搜索：標(biāo)簽A、C、D、E時隙計數(shù)器計數(shù)值初始化為0，并在時隙1響應(yīng)，標(biāo)簽B、F、G、H時隙計數(shù)器計數(shù)值初始化為1，并在時隙2響應(yīng)，兩個時隙都為沖突時隙；第2次搜索：標(biāo)簽C、D、E時隙計數(shù)器計數(shù)值仍為0，并在時隙1響應(yīng)，標(biāo)簽A時隙計數(shù)器計數(shù)值更新為1，并在時隙2響應(yīng)，時隙1為沖突時隙，時隙2無碰撞位，識別標(biāo)簽A；第3次搜索：標(biāo)簽D、E時隙計數(shù)器計數(shù)值仍為0，并在時隙1響應(yīng)，標(biāo)簽C時隙計數(shù)器計數(shù)值更新為1，并在時隙2響應(yīng)，時隙1只有1個碰撞位，識別標(biāo)簽D、E，時隙2無碰撞位，識別標(biāo)簽C；第4次搜索：標(biāo)簽B、H時隙計數(shù)器計數(shù)值更新為0，并在時隙1響應(yīng)，標(biāo)簽F、G時隙計數(shù)器計數(shù)值更新為1，并在時隙2響應(yīng)，時隙1只有一個碰撞位，識別標(biāo)簽B、H, 時隙2也只有一個碰撞位，識別標(biāo)簽F、G。

表1 CBS算法搜索過程Tab. 1 Searching process of CBS algorithm

CBS算法搜索樹如圖1所示。由圖1可見，每次搜索都有兩個時隙，提高了搜索效率，搜索順序是先搜索子集0標(biāo)簽，再返回搜索子集1標(biāo)簽。

圖1 CBS算法搜索樹Fig. 1 Search tree of CBS algorithm

2 算法對比

CBS算法具有較小的搜索次數(shù)和通信數(shù)據(jù)比特數(shù)，以上述的8個標(biāo)簽為例，對IAMS算法、EBST算法和本文的CBS算法進(jìn)行對比分析。

CBS算法的搜索次數(shù)為4，時隙1標(biāo)簽發(fā)送數(shù)據(jù)比特數(shù)為：9+7+4+8=28, 時隙2標(biāo)簽發(fā)送數(shù)據(jù)比特數(shù)也為28,閱讀器發(fā)送數(shù)據(jù)比特數(shù)為：5+4+5=14,通信總比特數(shù)為：28+28+14=70。

IAMS算法是比較新的一種防碰撞方法，表2是IAMS算法的搜索過程，其中“比特數(shù)”這一列的數(shù)據(jù)中“|”前面的數(shù)字表示閱讀器發(fā)送數(shù)據(jù)比特數(shù)，后面的數(shù)字表示標(biāo)簽發(fā)送數(shù)據(jù)比特數(shù)。

IAMS算法根據(jù)碰撞因子來決定叉樹，碰撞因子小于0.75用二叉樹搜索，碰撞因子大于或等于0.75用四叉樹搜索，由表2可見，只有第1次搜索碰撞因子大于0.75，整個搜索過程只有一次四叉樹搜索，其他都是二叉樹搜索，其搜索次數(shù)為15，遠(yuǎn)大于CBS算法。

表2 IAMS算法搜索過程Tab. 2 Searching process of IAMS algorithm

通信復(fù)雜度是指閱讀器和標(biāo)簽間通信的數(shù)據(jù)比特數(shù)，IAMS算法閱讀器發(fā)送數(shù)據(jù)總比特數(shù)為63，標(biāo)簽發(fā)送數(shù)據(jù)總比特數(shù)為144,總的數(shù)據(jù)通信比特數(shù)為207，遠(yuǎn)大于CBS算法。

EBST算法在IAMS算法的基礎(chǔ)上作了改進(jìn)，表3是EBST算法的搜索過程，其中“比特數(shù)”這一列的數(shù)據(jù)中“|”前面的數(shù)字表示閱讀器發(fā)送數(shù)據(jù)比特數(shù)，后面的數(shù)字表示標(biāo)簽發(fā)送數(shù)據(jù)比特數(shù)。

EBST算法根據(jù)連續(xù)碰撞的位數(shù)來確定叉樹，當(dāng)連續(xù)3位或3位以上碰撞時，選擇八叉樹搜索；當(dāng)僅連續(xù)兩位碰撞時，選擇四叉樹搜索；當(dāng)僅單獨(dú)位碰撞時，選擇二叉樹搜索。在八叉樹或四叉樹搜索時，需要先查詢碰撞前綴，其總搜索次數(shù)為14，略小于IAMS算法，遠(yuǎn)大于CBS算法。

EBST算法在3個連續(xù)碰撞位進(jìn)行前綴查詢時，其返回數(shù)據(jù)可能不足4，但閱讀器接收數(shù)據(jù)仍按4 bit數(shù)據(jù)來處理，所以在此仍按4 bit來計算閱讀器接收數(shù)據(jù)比特數(shù)。EBST算法閱讀器發(fā)送數(shù)據(jù)總比特數(shù)為73,標(biāo)簽發(fā)送數(shù)據(jù)總比特數(shù)為128，總的數(shù)據(jù)通信比特數(shù)為201，略小于IAMS算法，遠(yuǎn)大于CBS算法。

表3 EBST算法搜索過程Tab. 3 Searching process of EBST algorithm

需要說明的是，雖是舉例，但并沒有特殊性，任意ID序列號的幾個標(biāo)簽來比較，結(jié)果都大致相同。

CBS算法中涉及到的數(shù)據(jù)比較和標(biāo)簽分組，由于標(biāo)簽內(nèi)有微處理器和存儲器，可以通過軟件編程來實(shí)現(xiàn)。

3 算法分析

本文算法是確定性算法，能確保搜索并識別每一個標(biāo)簽，性能穩(wěn)定可靠；相比傳統(tǒng)的BS算法和RBS等算法，其搜索次數(shù)大大減少，通信復(fù)雜度大大降低；相比新近提出的IAMS算法和EBST算法，其搜索次數(shù)和通信復(fù)雜度也有很大改善。

3.1 搜索次數(shù)分析

搜索次數(shù)是衡量RFID性能優(yōu)劣的一個重要指標(biāo)，本文算法搜索過程為二叉樹搜索，根據(jù)二叉樹搜索法的性質(zhì)，對于任意一個二叉樹，度為2的節(jié)點(diǎn)總比度為0的節(jié)點(diǎn)少一個，本文算法中，每一個度為2的節(jié)點(diǎn)對應(yīng)一次搜索，度為0的節(jié)點(diǎn)對應(yīng)標(biāo)簽的個數(shù)，設(shè)標(biāo)簽的個數(shù)為N,則搜索次數(shù)為C′(N)為：

C′(N)=N-1

(1)

再考慮只有一個碰撞位的情況，假設(shè)只有一個碰撞位的情況出現(xiàn)了P次，由于這種情況下直接識別兩個標(biāo)簽，對應(yīng)一個節(jié)點(diǎn)，所以CBS算法中，總的搜索次數(shù)C(N)為：

C(N)=N-P-1

(2)

RBS算法搜索次數(shù)遠(yuǎn)小于BS算法，搜索次數(shù)為2N-1；但和CBS算法相比，RBS算法搜索次數(shù)又遠(yuǎn)多于CBS算法，相比RBS算法，CBS算法搜索次數(shù)減少了一半以上。

由式(2)可看出，P越大，C(N)越小，當(dāng)所有識別節(jié)點(diǎn)都僅一個碰撞位時，P最大，由于兩個識別標(biāo)簽對應(yīng)一個識別節(jié)點(diǎn)，則P的最大值為N/2,這種極端情況下，總搜索次數(shù)最少：

(3)

3.2 通信復(fù)雜度分析

通信復(fù)雜度是指在完成標(biāo)簽搜索過程中，閱讀器和標(biāo)簽間通信的數(shù)據(jù)比特數(shù)，較小的通信復(fù)雜度能減少標(biāo)簽的耗能，并提高搜索的速率。

CBS算法中，通信復(fù)雜度和最高碰撞位有關(guān)，假設(shè)標(biāo)簽ID長度為L，在第K次搜索中,最高碰撞位為第HK位，很明顯，0≤HK≤L-1,忽略控制命令本身比特數(shù)，第K次搜索通信總比特數(shù)為：閱讀器發(fā)送參數(shù)比特數(shù)+時隙1標(biāo)簽返回數(shù)據(jù)比特數(shù)+時隙2標(biāo)簽返回數(shù)據(jù)比特數(shù)。在CBS算法中，時隙1標(biāo)簽返回數(shù)據(jù)比特數(shù)和時隙2標(biāo)簽返回數(shù)據(jù)比特數(shù)相等，設(shè)為TK2，閱讀器發(fā)送參數(shù)比特數(shù)設(shè)為TK1，則有：

TK1=「lbHK?

(4)

其中「?表示向上取整。

TK2=HK

(5)

則第K次搜索通信數(shù)據(jù)量為：

TK=TK1+2TK2=「lbHK?+2HK

(6)

本文CBS算法總的通信數(shù)據(jù)比特數(shù)為：

(7)

可見，總的搜索次數(shù)一定小于N，通信總數(shù)據(jù)比特數(shù)僅和每次搜索的最高碰撞位位置有關(guān)，每次搜索的數(shù)據(jù)比特數(shù)一般小于2L。

RBS算法通信數(shù)據(jù)比特數(shù)少于BS算法，通信數(shù)據(jù)比特數(shù)為2L(2N-1)；但和CBS算法相比，RBS算法通信數(shù)據(jù)比特數(shù)又大于CBS算法。

實(shí)際的RFID系統(tǒng)中，閱讀器和標(biāo)簽間的通信還包括控制命令的開銷，由于本文算法搜索次數(shù)很少，減少了不少控制命令開銷，實(shí)際應(yīng)用中，更能顯出算法低通信復(fù)雜度的優(yōu)勢。

4 算法仿真與分析

前面通過理論分析得到了CBS算法的搜索次數(shù)和通信數(shù)據(jù)比特數(shù)，下面利用Matlab進(jìn)行仿真，并與BS算法、 RBS算法、IAMS算法和EBST算法進(jìn)行對比。假設(shè)標(biāo)簽ID長度為96 bit,閱讀器和標(biāo)簽控制命令本身長度固定為10 bit。

圖2是幾種算法的搜索次數(shù)比較。由圖2可見，CBS算法搜索次數(shù)遠(yuǎn)小于其他算法，標(biāo)簽數(shù)量越大，優(yōu)勢越明顯，這是由于CBS算法在每次搜索過程中，都有兩個時隙發(fā)送數(shù)據(jù)，一次搜索最多可以識別4個標(biāo)簽，大大提高了搜索的效率；和RBS算法相比，本文CBS算法搜索次數(shù)減少了一半以上；IAMS算法和EBST算法雖減少了空閑時隙，但卻增加了查詢高碰撞位的時隙，搜索次數(shù)仍遠(yuǎn)大于本文CBS算法。

圖2 搜索次數(shù)比較Fig. 2 Comparison of search times

圖3是幾種算法的通信復(fù)雜度比較。由圖3可見，CBS算法通信比特數(shù)小于IAMS算法和EBST算法，更遠(yuǎn)小于DBS算法和RBS算法，IAMS算法和EBST算法都耗費(fèi)了大量的查詢高碰撞位的數(shù)據(jù)比特數(shù)，實(shí)際上，按這類算法的原理，分叉越多，耗費(fèi)的查詢比特數(shù)就越多，所以IAMS算法和EBST算法仍有較高的通信數(shù)據(jù)量。CBS算法在幾個方面減少了通信比特數(shù)：一個是搜索次數(shù)最少，閱讀器和標(biāo)簽控制命令本身耗費(fèi)的數(shù)據(jù)比特數(shù)減少；另一個是采用了時隙計數(shù)器配合進(jìn)行搜索，閱讀器只需發(fā)送最高碰撞位的位置信息，標(biāo)簽只需要返回最高碰撞位以后的信息；再有就是當(dāng)只有一個碰撞位時直接識別兩個標(biāo)簽。正是由于這些措施和方法，使CBS算法通信數(shù)據(jù)比特數(shù)這一指標(biāo)優(yōu)于其他對比算法。

圖3 通信復(fù)雜度比較Fig. 3 Comparison of communication complexity

5 結(jié)語

本文在搜索樹防碰撞算法的基礎(chǔ)上，借鑒ALOHA算法時隙的思想，提出了一種新的防碰撞算法——CBS算法。該算法通過時隙計數(shù)器，對標(biāo)簽進(jìn)行逐級搜索，每次搜索中，應(yīng)答標(biāo)簽分為兩組，分別在兩個時隙返回數(shù)據(jù)給閱讀器，大大減少了搜索次數(shù)；同時，閱讀器只發(fā)送最高碰撞位位置信息，標(biāo)簽只返回最高碰撞位以后的ID號，當(dāng)只有一個碰撞位時，直接識別兩個標(biāo)簽，大大減少了系統(tǒng)通信數(shù)據(jù)量。

由于標(biāo)簽的能量有限，處理能力弱，標(biāo)簽的算法應(yīng)當(dāng)盡量簡單，而閱讀器不存在嚴(yán)苛的能量問題和體積問題，可以適應(yīng)比較復(fù)雜的算法。計數(shù)型雙時隙防碰撞算法對此作了充分考慮，是一個符合標(biāo)簽實(shí)際的實(shí)用的算法。

無論是IAMS算法還是EBST算法，標(biāo)簽處理過程都相對比較復(fù)雜；CBS算法盡量把復(fù)雜算法讓閱讀器來處理，標(biāo)簽處理過程相對簡單，耗能更小，易于實(shí)現(xiàn)，便于RFID系統(tǒng)的實(shí)際應(yīng)用，是一種很有應(yīng)用前景的防碰撞算法。

References)

[1] 王心妍,楊博.基于多進(jìn)制查詢樹的多標(biāo)簽識別方法[J].計算機(jī)工程,2015,41(8):95-99. (WANG X Y, YANG B. Multi-tag identification method based on multi-ary query tree [J]. Computer Engineering, 2015, 41(8): 95-99.)

[2] 王勇,唐小虎,張莉涓,等.基于魯棒估計的最大前綴RFID防碰撞算法[J].計算機(jī)工程,2015,41(2):303-307. (WANG Y, TANG X H, ZHANG L J, et al. Maximized prefix anti-collision algorithm for RFID based on robust estimation [J]. Computer Engineering, 2015, 41(2): 303-307.)

[3] 付鈺,錢志鴻,孟婕,等.基于連續(xù)時隙預(yù)測的幀時隙Aloha防碰撞算法[J].電子學(xué)報,2016,44(9):2081-2086. (FU Y, QIAN Z H, MENG J, et al. FSA anti-collision algorithm based on continuous slot prediction [J]. Acta Electronica Sinica, 2016, 44(9): 2081-2086.)

[4] 張小紅,張留洋.無源RIFD自適應(yīng)幀時隙防碰撞算法研究[J].電子學(xué)報.2016,44(9):2211-2218. (ZHANG X H, ZHANG L Y. Research on passive RFID system adaptive frame slot anti-collision algorithm [J]. Acta Electronica Sinica, 2016, 44(9): 2211-2218.)

[5] WANG C-Y, LEE C-C, LEE M-C. An enhanced dynamic framed slotted ALOHA anti-collision method for mobile RFID tag identification [J]. Journal of Convergence Information Technology, 2011, 6(4): 340-351.

[6] LIN C-F, LIN F Y-S. Efficient estimation and collision-group-based anti-collision algorithms for dynamic framed-slotted ALOHA in RFID networks [J]. IEEE Transactions on Automation Science and Engineering, 2010, 7(4): 840-848.

[7] 張小紅,胡應(yīng)夢.分組自適應(yīng)分配時隙的RFID防碰撞算法研究[J].電子學(xué)報,2016,44(6):1328-1335. (ZHANG X H, HU Y M. Research on a grouped adaptive allocating slot anti-collision algorithm in RFID system [J]. Acta Electronica Sinica, 2016, 44(6): 1328-1335.)

[8] 薛建彬,王文華,張婷,等,基于計數(shù)機(jī)制的多狀態(tài)二進(jìn)制搜索防碰撞算法[J].計算機(jī)工程,2013,39(4):309-313. (XUE J B, WANG W H, ZAHNG T, et al. Multi-state binary search anti-collision algorithm based on counting mechanism [J]. Computer Engineering, 2013, 39(4): 309-313.)

[9] 李寶山,喬聰.改進(jìn)的二進(jìn)制搜索防沖突算法[J].微電子學(xué)與計算機(jī),2014,31(5):94-97. (LI B S, QIAO C. An improved binary search anti-collision algorithm [J]. Microelectronics & Computer, 2014, 31(5): 94-97.)

[10] 林偉,李景霞,葉林鋒.基于多叉樹搜索算法改進(jìn)的RFID防碰撞算法[J].電子技術(shù)應(yīng)用,2013,39(2):130-133. (LIN W, LI J X, YE L F. An improved anti-collision algorithm based on multi-tree search in RFID [J]. Application of Electronic Technique, 2013, 39(2): 130-133.)

[11] 張學(xué)軍,蔡文琦,王鎖萍.改進(jìn)型自適應(yīng)多叉樹防碰撞算法研究[J].電子學(xué)報,2012,40(1):193-198. (ZHANG X J, CAI W Q, WANG S P. One anti-collision algorithm based on improved adaptive multi-tree search [J]. Acta Electronica Sinica, 2012, 40(1): 193-198.)

[12] 韋冬雪,鄭嘉利,黃慶歡,等.基于搜索樹的增強(qiáng)型RFID防碰撞算法[J].計算機(jī)應(yīng)用與軟件,2015,32(11):226-231. (WEI D X, ZHENG J L, HUANG Q H, et al. An enhanced RFID anti-collision algorithm based on search tree [J]. Computer Applications and Software, 2015, 32(11): 226-231.)

[13] 孫耀磊,吳曉波,陳元文,等.基于轉(zhuǎn)換碼的雙時隙RFID防碰撞算法[J].自動化與儀器儀表,2014(2):134-136,139. (SUN Y L,WU X B, CHEN Y W, et al. A bi-slot RFID anti-collision algorithm based on convertion code [J]. Automation and Instrumentation, 2014(2): 134-136, 139.)

This work is partially supported by the Safety Production Science Project in Sichuan Province of China (scaqjgjc_stp_2015004), the Key Scientific Research Project of Sichuan Department of Education (15ZA0341).

MOLei, born in 1969, M. S., associate professor. His research interests include RFID, Internet of things.

CHENWei, born in 1978, Ph. D., lecturer. His research interests include Internet of things, application of electronic.

RENJu, born in 1974, M. S., lecturer. His research interests include signal and information processing.

Anti-collisionalgorithmforRFIDbasedoncounterandbi-slot

MO Lei*, CHEN Wei, REN Ju

(CollegeofElectronicalandInformationEngineering,ChengduAeronauticPolytechnic,ChengduSichuan610100,China)

Focusing on the problem of the binary search anti-collision algorithm in Radio Frequency IDentification (RFID) system such as many search times and large amount of communication data, a new anti-collision algorithm for RFID with counter and bi-slot was proposed based on regressive search tree algorithm and time slot algorithm, namely CBS. The tags were searched step by step according to the slot counter in tag and the collision bit information

by reader. The response tags were divided into two groups, which returned the data information to the reader in two time slots. The reader only sends the information of the highest collision bit position, and the tags only send the bits of data after the highest collision bit. Theoretical analysis and simulation results showed that compared with the traditional Regressive Binary Search (RBS) algorithm, the search times of CBS algorithm was reduced by more than 51%, and the communication data was reduced by more than 65%. CBS algorithm is superior to the commonly used anti-collision algorithms, which greatly reduces the search times and communication data, and improves the search efficiency.

Radio Frequency IDentification (RFID); bi-slot; search tree; anti-collision; slot counter

TP391.45; TN92

A

2017- 02- 22;

2017- 04- 07。

四川省安全生產(chǎn)科技項(xiàng)目(scaqjgjc_stp_2015004)；四川省教育廳重點(diǎn)科研項(xiàng)目(15ZA0341)。

莫磊(1969—)，男，四川成都人，副教授，碩士，主要研究方向:射頻識別、物聯(lián)網(wǎng)； 陳偉(1978—)，男，四川成都人，講師，博士，主要研究方向：物聯(lián)網(wǎng)、應(yīng)用電子； 任菊(1974—)，女，四川成都人，講師，碩士，主要研究方向：信號與信息處理。

1001- 9081(2017)08- 2168- 05

10.11772/j.issn.1001- 9081.2017.08.2168