莫 磊，陳 偉，任 菊

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

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

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

莫 磊*，陳 偉，任 菊

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

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

針對(duì)射頻識(shí)別(RFID)二進(jìn)制搜索防碰撞算法搜索次數(shù)多、通信數(shù)據(jù)量大等問(wèn)題，在后退式搜索樹(shù)算法和時(shí)隙算法的基礎(chǔ)上，提出一種新的計(jì)數(shù)型雙時(shí)隙RFID防碰撞算法CBS。CBS算法根據(jù)標(biāo)簽中的時(shí)隙計(jì)數(shù)器和閱讀器收到的碰撞位信息對(duì)標(biāo)簽進(jìn)行逐級(jí)分類搜索，并將應(yīng)答標(biāo)簽分為兩組，分別在兩個(gè)時(shí)隙向閱讀器返回?cái)?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í)別；雙時(shí)隙；搜索樹(shù)；防碰撞；時(shí)隙計(jì)數(shù)器

0 引言

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

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

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

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

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

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

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

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

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

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

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

1.1 命令規(guī)則

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

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

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

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

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

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

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

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

1.2 算法原理

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3 算法舉例

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

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

表1 CBS算法搜索過(guò)程Tab. 1 Searching process of CBS algorithm

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

圖1 CBS算法搜索樹(shù)Fig. 1 Search tree of CBS algorithm

2 算法對(duì)比

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

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

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

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

表2 IAMS算法搜索過(guò)程Tab. 2 Searching process of IAMS algorithm

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

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

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

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

表3 EBST算法搜索過(guò)程Tab. 3 Searching process of EBST algorithm

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

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

3 算法分析

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

3.1 搜索次數(shù)分析

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

C′(N)=N-1

(1)

再考慮只有一個(gè)碰撞位的情況，假設(shè)只有一個(gè)碰撞位的情況出現(xiàn)了P次，由于這種情況下直接識(shí)別兩個(gè)標(biāo)簽，對(duì)應(yīng)一個(gè)節(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)所有識(shí)別節(jié)點(diǎn)都僅一個(gè)碰撞位時(shí)，P最大，由于兩個(gè)識(shí)別標(biāo)簽對(duì)應(yīng)一個(gè)識(shí)別節(jié)點(diǎn)，則P的最大值為N/2,這種極端情況下，總搜索次數(shù)最少：

(3)

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

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

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

TK1=「lbHK?

(4)

其中「?表示向上取整。

TK2=HK

(5)

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

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

(6)

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

(7)

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

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

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

4 算法仿真與分析

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

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

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

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

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

5 結(jié)語(yǔ)

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

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

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

References)

[1] 王心妍,楊博.基于多進(jìn)制查詢樹(shù)的多標(biāo)簽識(shí)別方法[J].計(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] 王勇,唐小虎,張莉涓,等.基于魯棒估計(jì)的最大前綴RFID防碰撞算法[J].計(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] 付鈺,錢(qián)志鴻,孟婕,等.基于連續(xù)時(shí)隙預(yù)測(cè)的幀時(shí)隙Aloha防碰撞算法[J].電子學(xué)報(bào),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] 張小紅,張留洋.無(wú)源RIFD自適應(yīng)幀時(shí)隙防碰撞算法研究[J].電子學(xué)報(bào).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)夢(mèng).分組自適應(yīng)分配時(shí)隙的RFID防碰撞算法研究[J].電子學(xué)報(bào),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] 薛建彬,王文華,張婷,等,基于計(jì)數(shù)機(jī)制的多狀態(tài)二進(jìn)制搜索防碰撞算法[J].計(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ì)算機(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] 林偉,李景霞,葉林鋒.基于多叉樹(shù)搜索算法改進(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)多叉樹(shù)防碰撞算法研究[J].電子學(xué)報(bào),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] 韋冬雪,鄭嘉利,黃慶歡,等.基于搜索樹(shù)的增強(qiáng)型RFID防碰撞算法[J].計(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)換碼的雙時(shí)隙RFID防碰撞算法[J].自動(dòng)化與儀器儀表,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—)，男，四川成都人，副教授，碩士，主要研究方向:射頻識(shí)別、物聯(lián)網(wǎng)； 陳偉(1978—)，男，四川成都人，講師，博士，主要研究方向：物聯(lián)網(wǎng)、應(yīng)用電子； 任菊(1974—)，女，四川成都人，講師，碩士，主要研究方向：信號(hào)與信息處理。

1001- 9081(2017)08- 2168- 05

10.11772/j.issn.1001- 9081.2017.08.2168