基于分組機制的位仲裁查詢樹防碰撞算法

付鈺，錢志鴻，程超，劉曉慧

?

基于分組機制的位仲裁查詢樹防碰撞算法

付鈺1，錢志鴻1，程超2，劉曉慧1

（1. 吉林大學(xué)通信工程學(xué)院，吉林長春 130012；2. 長春工業(yè)大學(xué)計算機科學(xué)與工程學(xué)院，吉林長春 130012）

提出了一種基于分組機制的位仲裁查詢樹(GBAQT, bit arbitration query tree based on grouping mechanism)算法。該算法根據(jù)標(biāo)簽ID自身特征分組，采用3位仲裁位來取代傳統(tǒng)1位仲裁識別標(biāo)簽的方式，通過碰撞位信息得到傳輸數(shù)據(jù)，從而能避免一些空閑時隙。算法的性能分析和仿真結(jié)果表明，GBAQT防碰撞算法具有較少的總時隙數(shù)，系統(tǒng)效率和時隙利用率也明顯優(yōu)于其他算法。

RFID；標(biāo)簽防碰撞；查詢樹；分組機制

1 引言

物聯(lián)網(wǎng)已經(jīng)成為當(dāng)下最具潛力的產(chǎn)業(yè)之一，其概念最初是在1999年被提出，通過射頻識別技術(shù)和傳感器等信息傳感設(shè)備，把任何物品與互聯(lián)網(wǎng)連接起來，實現(xiàn)監(jiān)控、定位功能的智能化網(wǎng)絡(luò)。現(xiàn)如今，盡管“物聯(lián)網(wǎng)”的概念得到了進(jìn)一步的完善，但RFID技術(shù)作為物聯(lián)網(wǎng)的感知層，在物聯(lián)網(wǎng)的核心技術(shù)中仍起著至關(guān)重要的作用。RFID是一種非接觸式自動識別技術(shù)，利用空間的射頻信號實現(xiàn)雙向數(shù)據(jù)的無線通信。在《中國物聯(lián)網(wǎng)RFID2013年度報告》中顯示，2013年中國物聯(lián)網(wǎng)市場規(guī)模達(dá)到4896億元，RFID市場規(guī)模達(dá)到318.4億元，比上一年增長了34.6%。RFID技術(shù)的應(yīng)用領(lǐng)域更加廣泛，如軍事、航空、醫(yī)療、制造業(yè)和零售業(yè)等[1]。通常，RFID系統(tǒng)主要由閱讀器、電子標(biāo)簽以及后臺服務(wù)器構(gòu)成[2]。閱讀器主要負(fù)責(zé)控制和標(biāo)簽的雙向通信；每個電子標(biāo)簽都具有能被識別的、全球唯一的電子編碼；后臺服務(wù)器是提供服務(wù)和管理的控制中心。

由于標(biāo)簽本身無法知道其他標(biāo)簽的存在，各標(biāo)簽只能按照閱讀器的命令發(fā)送信息。單個閱讀器只有一個通信信道，當(dāng)2個或更多的標(biāo)簽同時向閱讀器發(fā)送它們的ID信息時，就會產(chǎn)生信號干擾，即發(fā)生標(biāo)簽碰撞問題，碰撞問題會嚴(yán)重地影響標(biāo)簽數(shù)據(jù)的完整性，使標(biāo)簽無法被正確識別。標(biāo)簽碰撞問題是RFID系統(tǒng)中重要的難題之一，極大地制約了RFID技術(shù)的發(fā)展。

目前，有很多優(yōu)秀的協(xié)議來解決標(biāo)簽碰撞問題，這些算法主要分為2大類：一類是基于ALOHA的不確定性算法[3~5]；另一類是基于樹的確定性算法[6,7]。前者包括純ALOHA算法[8]、時隙ALOHA算法、幀時隙ALOHA算法、動態(tài)幀時隙ALOHA算法及其改進(jìn)算法等。后者包括了二進(jìn)制搜索樹算法、查詢樹（QT, query tree）算法[9]、碰撞樹算法[10]等多種基于圖的樹型算法。

1.1 曼徹斯特編碼

基于樹的算法中常常使用曼徹斯特編碼作為檢測碰撞位的方法[11~13]。曼徹斯特編碼將數(shù)據(jù)包含在數(shù)據(jù)流中，每位編碼有一跳變，用下降沿表示比特“1”，上升沿表示比特“0”。在RFID系統(tǒng)中，如果有多個標(biāo)簽同時傳輸不同比特，那么上升沿和下降沿將被抵消。然而在數(shù)據(jù)傳輸過程中曼徹斯特編碼不允許出現(xiàn)這種情況，因此使用曼徹斯特編碼能判斷該位為碰撞位。本文亦采用曼徹斯特編碼，已達(dá)到閱讀器能在接收數(shù)據(jù)中準(zhǔn)確檢測出碰撞位的目的。例如，假設(shè)系統(tǒng)中存在2個標(biāo)簽，分別為Tag A(0101)和Tag B(0011)。當(dāng)Tag A和Tag B同時傳送ID的數(shù)據(jù)信息時，閱讀器通過曼徹斯特編碼接收到的信號為“0XX1”(X表示碰撞位），即第1位和第2位均為碰撞位。圖1所示為標(biāo)簽使用曼徹斯特編碼的響應(yīng)過程。

1.2 查詢樹算法

查詢樹算法主要由輪詢和響應(yīng)2個部分構(gòu)成。在每一輪中，閱讀器要發(fā)送一個字符串（即查詢前綴），查詢標(biāo)簽ID是否含有特定的前綴。只有ID與查詢前綴相匹配的標(biāo)簽才能響應(yīng)輪詢命令。如果只有一個標(biāo)簽響應(yīng)，那么該標(biāo)簽可以被成功識別，并將自己的ID發(fā)送給閱讀器。如果有多個標(biāo)簽響應(yīng)，那么就會發(fā)生標(biāo)簽碰撞，然后閱讀器在該查詢前綴后分別添加0和1構(gòu)成了新的查詢前綴。通過擴展前綴，直到只有一個標(biāo)簽的ID匹配。因此該算法可以識別所有的標(biāo)簽。

然而，在基本的查詢樹算法中如果沒有標(biāo)簽的ID和查詢前綴匹配，那么將會產(chǎn)生多余的空閑時隙。例如2個標(biāo)簽，它們的ID只有最后一位不同，其余各位均一致。那么為了識別這2個標(biāo)簽，將會產(chǎn)生許多的碰撞時隙和空閑時隙。同樣，也會增加查詢時間，使系統(tǒng)的查詢效率下降。

1.3 基于查詢樹算法最近的研究成果

鑒于查詢樹算法的不足，研究學(xué)者們提出了許多基于查詢樹的改進(jìn)算法。其中，Zhang等[14]提出了自適應(yīng)四叉修剪查詢樹(A4PQT, adaptive 4-ary pruning query tree)算法。根據(jù)碰撞位的特點對四叉查詢樹進(jìn)行改善，以減少不必要的空閑時隙。閱讀器向讀取范圍內(nèi)的標(biāo)簽發(fā)送查詢前綴，匹配前綴的標(biāo)簽將除前綴外余下的ID發(fā)送給閱讀器。當(dāng)標(biāo)簽發(fā)生碰撞時，假設(shè)標(biāo)簽ID長度為bit，閱讀器接收數(shù)據(jù)信息為12…p?1pp1…p，p為首碰撞位，那么可以分成3種情況。

1) 如果p1=0，那么閱讀器將產(chǎn)生2個新的查詢前綴，分別為12…p?100和12…p?110，并將原四叉樹的“01”和“11”分支剔除。

2) 如果p1=1，那么閱讀器將產(chǎn)生2個新的查詢前綴，分別為12…p?101和12…p?111，并將原四叉樹的“00”和“10”分支剔除。

3) 如果p1也是碰撞位，那么閱讀器將產(chǎn)生4個新的查詢前綴，分別為12…p?100、12…p?101、12…p?110和12…p?111，不剔除掉四叉樹任何分支。

因此，A4PQT算法可以減少一些空閑時隙，所需要的總時隙為至2?3之間。然而，如果2個標(biāo)簽的ID分別為“01”和“10”，那么閱讀器通過曼徹斯特編碼得到的數(shù)據(jù)為“XX”，根據(jù)A4PQT算法將要產(chǎn)生4個查詢前綴，由此將產(chǎn)生2個額外的空閑時隙。

針對上述研究所存在的問題，本文基于分組機制和查詢樹識別，提出一種基于分組機制的位仲裁查詢樹(GBAQT, bit arbitration query tree based on grouping mechanism)防碰撞算法。在GBAQT算法中標(biāo)簽根據(jù)ID自身特征，通過3位仲裁的方式將未識別標(biāo)簽分成2組，閱讀器根據(jù)各組標(biāo)簽特點和接收數(shù)據(jù)的碰撞位信息能得到傳輸數(shù)據(jù)，減少了大量空閑時隙。仿真結(jié)果顯示，與其他標(biāo)簽防碰撞算法相比，GBAQT算法具有較高的系統(tǒng)效率和時隙利用率，并且在較多標(biāo)簽存在的環(huán)境下具有明顯的優(yōu)勢。

2 算法描述

目前，基于樹的確定性算法中通常使用前綴來識別標(biāo)簽，在識別樹中一般包括3個時隙。

碰撞時隙：在該時隙中，多個標(biāo)簽同時響應(yīng)閱讀器的查詢，閱讀器將不能識別任何標(biāo)簽，稱該時隙為碰撞時隙。

成功時隙：在該時隙中只有1個標(biāo)簽響應(yīng)閱讀器，則標(biāo)簽?zāi)鼙怀晒ψR別，稱該時隙為成功時隙。

空閑時隙：在該時隙中沒有標(biāo)簽響應(yīng)，則為空閑時隙。

2.1 基本思想

本文采用3位仲裁的方式來代替?zhèn)鹘y(tǒng)的1位仲裁，盡管采用多叉查詢樹能有效地減少碰撞時隙，但會帶來大量的空閑時隙。因此，GBAQT算法對空閑時隙數(shù)進(jìn)行了優(yōu)化，通過標(biāo)簽ID的自身特征分組，由碰撞信息盡量準(zhǔn)確地推斷出傳輸數(shù)據(jù)的組合形式。

分組機制描述如下。假設(shè)標(biāo)簽ID長度為，標(biāo)簽的第位開始相鄰3位為pp+1p+2，定義為異或運算符，如果pp+1=p+2，則pp+1p+2為第0組，表示為=0; 如果pp+1≠p+2，則pp+1p+2為第1組，表示為=1。例如標(biāo)簽的ID中3位連續(xù)數(shù)據(jù)為140516，符合1405=16，那么=0。另外，還發(fā)現(xiàn)以下規(guī)則：對于=0組的標(biāo)簽，pp1p23位數(shù)據(jù)符合其中任意2位異或都等于其余一位，由此定義=0組標(biāo)簽具有異或特征；而=1組標(biāo)簽，pp1p23位數(shù)據(jù)符合其中任意2位同或等于其余一位，由此定義=1組標(biāo)簽具有同或特征。

例如，在RFID系統(tǒng)中存在2個標(biāo)簽，分別為Tag A(101)和Tag B(110)，標(biāo)簽發(fā)送ID與組號信息，閱讀器得到“1XX”和=0。根據(jù)=0組標(biāo)簽的異或特征，可得到傳輸數(shù)據(jù)的組合形式為：101和110，能準(zhǔn)確地判斷標(biāo)簽ID。相比A4PQT算法，可以減少2個空閑時隙。

2.2 算法相關(guān)指令

REQUEST(12…q,)請求命令，12…q為查詢前綴，其中，{0,1},。表示組號，∈{0,1}。閱讀器發(fā)送REQUEST(12…q,)命令，符合查詢前綴為12…q且組號為的標(biāo)簽響應(yīng)，處于激活狀態(tài)。

PUSH()讀寫指令，將作為新的查詢前綴壓入棧的底部。

SELECT()選擇指令，選擇符合此ID的標(biāo)簽。

READ-DATA讀取指令，讀出標(biāo)簽ID的數(shù)據(jù)信息。

SILENCE靜默指令，將標(biāo)簽置于靜默狀態(tài)，不再參與識別過程。

“”表示連接符，將2組數(shù)據(jù)連接組合成一組，如“0001”，表示將“00”和“01”連接成“0001”。

2.3 算法流程

GBAQT算法流程如圖2所示。

第1步 初始化，閱讀器置查詢前綴堆棧和組號存儲器為空。

第2步 閱讀器發(fā)送REQUEST(12…q)。首次發(fā)送該命令時置查詢前綴為，即讀取范圍內(nèi)的標(biāo)簽全部響應(yīng)。

第3步 與查詢前綴12…q相匹配的標(biāo)簽響應(yīng)。如果沒有標(biāo)簽響應(yīng)，則為空閑時隙，轉(zhuǎn)到第6步；否則轉(zhuǎn)到第4步。

第4步 閱讀器查詢標(biāo)簽是否發(fā)生碰撞。如果未發(fā)生碰撞，則該標(biāo)簽可以被成功識別，閱讀器發(fā)送SELECT和READ-DATA指令，對標(biāo)簽讀寫操作后閱讀器發(fā)送SILENCE指令，將標(biāo)簽置為靜默狀態(tài)，轉(zhuǎn)到第6步；如果發(fā)生碰撞，則轉(zhuǎn)到第5步。

第5步 假設(shè)閱讀器接收的數(shù)據(jù)為12…p?1pp+1p+2，其中{0,1}，p表示最高碰撞位。從標(biāo)簽ID的p位開始的連續(xù)3位pp+1p+2為一組，執(zhí)行分組指令，相應(yīng)的置標(biāo)簽內(nèi)部組號存儲器為0或1。標(biāo)簽發(fā)送數(shù)據(jù)“pp+1p+2”。根據(jù)閱讀器中組號存儲器接收數(shù)據(jù)是否碰撞可分為以下2種情況討論。

1) 如果閱讀器的組號存儲器發(fā)生碰撞，則先查詢=0的標(biāo)簽，然后再查詢=1的標(biāo)簽。若該組中沒有標(biāo)簽響應(yīng)，則為空閑時隙；若該組中只有一個標(biāo)簽響應(yīng)，則可以直接識別，閱讀器發(fā)送SELECT和READ-DATA指令，對標(biāo)簽讀寫操作后閱讀器發(fā)送SILENCE指令，將標(biāo)簽置為靜默狀態(tài)；若該組發(fā)生碰撞，那么通過碰撞位信息，遵循其異或（或同或）特征可推斷傳輸數(shù)據(jù)的組合形式，將“查詢前綴傳輸數(shù)據(jù)”壓入棧底，轉(zhuǎn)到第6步。

2) 如果閱讀器的組號存儲器未發(fā)生碰撞，即為單一組號時，只查詢符合該組的標(biāo)簽即可，轉(zhuǎn)到第6步。

第6步 查詢堆棧是否為空。若棧不為空，則從棧頂彈出數(shù)據(jù)作為新的查詢前綴，轉(zhuǎn)到第2步；若棧為空，則查詢過程結(jié)束。

閱讀器根據(jù)碰撞位信息，利用各組的異或（或同或）特征推斷出傳輸數(shù)據(jù)的組合形式，具體描述如下，=0的標(biāo)簽中，若pp+1p+2中有2位碰撞位，利用該組的異或特征，從傳輸數(shù)據(jù)中已知的一位數(shù)據(jù)信息推斷出另2位的組合形式，例如pp+1p+2= 1XX，則發(fā)送PUSH(12…q12…p?1101)和PUSH(12…q12…p?1110)；若pp+1p+2中的各位均為碰撞位，則推斷為PUSH(12…q12…p?1000), PUSH(12…q12…p?1011), PUSH (qq…q12…p?1101), PUSH (12…q12…p?1110)。同樣，的標(biāo)簽中，若pp+1p+2只有2位碰撞位，利用該組的同或特征，亦可以推斷出這2個碰撞位的組合形式，例如pp+1p+2= 1XX，則發(fā)送PUSH(12…12…p?1100)和PUSH(12…12…p?1111)；若3位均為碰撞位則發(fā)送PUSH(12…q12…p?1001), PUSH(12…q12…p?1010), PUSH(12…q12…p?1100), PUSH(12…q12…p?1111)。

下面舉例說明GBAQT算法識別標(biāo)簽的步驟。設(shè)有6個待識別標(biāo)簽，標(biāo)簽ID分別為Tag1(000110)、Tag2(000101)、Tag3(000011)、Tag4(011111)、Tag5(011010)、Tag6(111111)。GBAQT算法閱讀器查詢和標(biāo)簽響應(yīng)過程如表1所示，對應(yīng)的查詢樹結(jié)構(gòu)如圖3所示。

表1 閱讀器查詢和標(biāo)簽響應(yīng)情況

3 算法性能分析

在RFID系統(tǒng)中，衡量防碰撞算法的優(yōu)劣主要有2個指標(biāo)：總時隙數(shù)和系統(tǒng)效率。下面通過計算總時隙數(shù)和系統(tǒng)效率來分析GBAQT算法性能。假設(shè)系統(tǒng)中有個標(biāo)簽，在第層的時候，對于完全八叉樹有8個節(jié)點，由于每個節(jié)點可分為=0組和=1組，那么該層有組。由于每個標(biāo)簽的分配是相互獨立的，其中有個標(biāo)簽在第層分配到同一組內(nèi)的概率服從二項分布

該組為空閑的概率為

該組能被成功識別的概率為

(3)

該組發(fā)生碰撞的概率為

若該組為碰撞時隙，那么可以將樹結(jié)構(gòu)分為以下3種情況。

1) 只有2個子節(jié)點時，則一定沒有空閑時隙；

2) 有3個子節(jié)點時，則必然產(chǎn)生3個非空閑時隙（其狀態(tài)為碰撞還是成功時隙需有+1層進(jìn)行判斷）和一個空閑時隙；

3) 有4個子節(jié)點，則4個都是非空閑時隙。

因此，最佳樹的情況應(yīng)該沒有空閑時隙，最差樹的情況則是每個碰撞組有一個空閑時隙。

有3個節(jié)點的概率為

(6)

有4個節(jié)點的概率為

對于每組都只有2個節(jié)點的樹結(jié)構(gòu)，若只需要1層即可識別所有標(biāo)簽，那么總時隙

(8)

每組都有3個節(jié)點的樹結(jié)構(gòu)，若需要2層即可識別所有標(biāo)簽，那么總時隙

每組都有4個節(jié)點的樹結(jié)構(gòu)，若需要3層即可識別所有標(biāo)簽，那么總時隙

(10)

在GBAQT算法樹結(jié)構(gòu)中是2個節(jié)點、3個節(jié)點和4個節(jié)點混合的情況，為了便于分析，這里按各個情況發(fā)生的概率占總體發(fā)生概率的百分比得到：發(fā)生2個節(jié)點的概率；發(fā)生3個節(jié)點的概率；發(fā)生2個節(jié)點的概率。那么得到總時隙

空閑時隙數(shù)

(12)

系統(tǒng)效率為

4 仿真及分析

以Matlab2012a為仿真平臺對算法進(jìn)行仿真，閱讀器讀取范圍內(nèi)的標(biāo)簽數(shù)量取值范圍為100~1 000，且標(biāo)簽ID隨機產(chǎn)生，ID長度為96 bit進(jìn)行仿真。下列結(jié)果仿真20次取平均值，下面將GBAQT算法與A4PQT算法、QT算法、八叉樹算法進(jìn)行仿真，分別從空閑時隙數(shù)、總時隙數(shù)、系統(tǒng)效率和時隙利用率4個方面的性能進(jìn)行對比。

圖4為GBAQT算法、A4PQT算法、QT算法和八叉樹算法空閑時隙數(shù)比較，可以看出GBAQT算法的空閑時隙數(shù)遠(yuǎn)遠(yuǎn)小于A4PQT算法、QT算法和八叉樹算法，并且隨著值的增加，其空閑時隙數(shù)的增加趨勢緩慢而穩(wěn)定。然而八叉樹的空閑時隙數(shù)增加的速度最快，在標(biāo)簽數(shù)量為1 000時，八叉樹的空閑時隙數(shù)幾乎是GBAQT算法的28倍。因此，當(dāng)存在大量標(biāo)簽時，GBAQT算法的優(yōu)勢更加明顯。

圖5為GBAQT算法、A4PQT算法、QT算法和八叉樹算法總時隙數(shù)的比較。識別個標(biāo)簽時，GBAQT算法所需的總時隙數(shù)明顯小于A4PQT算法、QT算法和八叉樹算法，并且在標(biāo)簽數(shù)量較多時，可有效地減少搜索的總時隙數(shù)。

圖6對GBAQT算法、A4PQT算法、QT算法和八叉樹算法的系統(tǒng)效率進(jìn)行了比較，可以看出GBAQT算法的系統(tǒng)效率明顯要優(yōu)于A4PQT算法、QT算法和八叉樹算法，可維持在0.54左右。其次是A4QPT算法效率，不超過0.49。四叉樹算法系統(tǒng)效率次之，保持在0.35左右。八叉樹算法的系統(tǒng)效率最低，在0.25至0.28之間浮動。

圖7表示GBAQT算法、A4PQT算法、QT算法和八叉樹算法的時隙利用率，其中時隙利用率=。由于GBAQT算法可以利用碰撞時隙反演出標(biāo)簽，因此碰撞時隙和成功時隙都是有用時隙。可以看出GBAQT的時隙利用率要優(yōu)于其他3種算法，達(dá)到了0.95。其次是QT算法，時隙利用率維持在0.85左右。A4PQT算法次之，在0.77附近浮動。盡管八叉樹算法能減少碰撞時隙，但同時也伴隨著大量空閑時隙的產(chǎn)生，因此其系統(tǒng)利用率最低，不超過0.4。

5 結(jié)束語

本文基于分組機制和查詢樹識別，提出一種基于分組機制的位仲裁查詢樹防碰撞算法，該算法采用3位仲裁位的方式減少碰撞時隙，并根據(jù)標(biāo)簽ID自身特征分組，通過碰撞位信息得到的傳輸數(shù)據(jù)從而能避免一些空閑時隙。理論和仿真分析表明：GBAQT算法能有效地減少空閑時隙數(shù)，具有較低的總時隙數(shù)，并且能有效地提高系統(tǒng)效率和時隙利用率。在標(biāo)簽數(shù)量較多的情況下，GBAQT性能明顯優(yōu)于其他算法。

[1] BLETSAS A, KIMIONIS J, DIMITRIOUS A G, et al. Single-antenna coherent detection of collided FM0 RFID signals[J]. IEEE Transactions on Communications, 2012, 60(3):756-766.

[2] HSU C H, CHAO H C, PARK J H. Threshold jumping and wrap-around scan techniques toward efficient tag identification in high density RFID systems[J]. Information Systems Frontiers, 2011, 13(4):471-480.

[3] 李萌, 錢志鴻, 張旭, 等. 基于時隙預(yù)測的 RFID 防碰撞 ALOHA 算法[J]. 通信學(xué)報, 2012, 32(12):43-50.

LI M, QIAN Z H, ZHANG X, et alSlot-predicting based ALOHA algorithm for RFID anti-collision[J]. Journal on Communications, 2012, 32(12):43-50.

[4] ZANELLA A. Adaptive batch resolution algorithm with deferred feedback for wireless systems[J]. IEEE Transactions on Wireless Communications, 2012, 11(10):3528-3539.

[5] ZHU L, YUM T P. Optimal framed Aloha based anti-collision algorithms for RFID systems[J]. IEEE Transactions on Communications, 2010, 58(12):3583-3592.

[6] JIANG Y, ZHANG R N. An adaptive combination query tree protocol for tag identification in RFID systems[J]. IEEE Communications Letters, 2012,16(8):1192-1195.

[7] YANG C N, HU L J, LAI J B. Query tree algorithm for RFID tag with binary-coded decimal EPC[J]. I IEEE Communications Letters, 2010, 16(10):1616-1619.

[8] LAW C, LEE K, SIU K Y. Efficient memory-less protocol for tag identification[C]//The 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and CommunicationsBoston. c2000: 75-84.

[9] HUSH D R, WOOD C. Analysis of tree algorithms for RFID arbitration[C]//IEEE International Symposium on Information Theory. Cambridge, c1998: 107.

[10] JIA X L, FENG Q Y, YU L S. Stability analysis of an efficient anti-collision protocol for RFID tag identification[J]. IEEE Transactions on Communications, 2012, 60(8):2285-2294.

[11] LIU X H, QIAN Z H, ZHAO Y H, et al. An adaptive tag anti-collision protocol in RFID wireless systems[J]. China Communications, 2014, 11(7):117-127.

[12] GAO J, WANG J, HE J, et al. QSA: query splitting-based anticollision for mobile RFID-based internet-of-things[J]. International Journal of Distributed Sensor Networks, 2013, DOI:10.1155/2013/674698.

[13] CHEN Y H, HORNG S J, RUN R S, et al. A novel anti-collision algorithm in RFID systems for identifying passive tags[J]. IEEE Transactions on Industrial Informatics, 2010, 6(1):105-121.

[14] ZHANG W, GUO Y J, TANG X M, et al. An efficient adaptive anticollision algorithm based on 4-ary pruning query tree[J]. International Journal of Distributed Sensor Networks, 2013, 14(2): 135-143.

Bit arbitration query tree anti-collision algorithm based on grouping mechanism

FU Yu1, QIAN Zhi-hong1, CHENG Chao2, LIU Xiao-hui1

(1. College of Communication Engineering, Jilin University, Changchun 130012, China; 2. School of Computer Science & Engineering, Changchun University of Technology, Changchun 130012, China)

A bit arbitration query tree anti-collision algorithm based on grouping mechanism was proposed. GBAQT divided tags into two groups according to the tag ID’s feature and used three arbitration bits to identify tags instead of using one bit in traditional methods. The reader can obtain the transmit data based on information of collision bits and thus avoid some idle timeslots. The algorithm performance analysis and simulation results show that GBAQT anti-collision algorithm has fewer total number of timeslots. Timeslot utilization and system efficiency of GBAQT algorithm are significantly better than the other algorithms.

RFID, tag anti-collision, query tree, grouping mechanism

TN92

A

10.11959/j.issn.1000-436x.2016014

2014-11-19；

2015-01-20

國家自然科學(xué)基金資助項目(No.61371092)；吉林省科技廳基金資助項目(No.20140204019GX)

The National Natural Science Foundation of China (No.61371092); Research Project of Science and Technology Department of Jilin Province (No.20140204019GX)

付鈺（1990-），女，吉林省吉林市人，吉林大學(xué)博士生，主要研究方向為RFID和物聯(lián)網(wǎng)。

錢志鴻（1957-），男，吉林長春人，吉林大學(xué)教授、博士生導(dǎo)師，主要研究方向為物聯(lián)網(wǎng)、RFID、Wi-Fi、無線傳感器網(wǎng)絡(luò)和無線定位等。

程超（1984-），男，吉林長春人，博士，長春工業(yè)大學(xué)講師，主要研究方向為短距離無線通信理論。

劉曉慧（1989-），女，吉林長春人，吉林大學(xué)碩士生，主要研究方向為無線通信理論。