無空閑時(shí)隙并行識(shí)別動(dòng)態(tài)多叉查詢樹算法

白樂強(qiáng)　劉杰　曹科研

摘? 要： 針對無空閑時(shí)隙的動(dòng)態(tài)多叉查詢樹RFID防碰撞算法在標(biāo)簽識(shí)別過程中吞吐量不穩(wěn)定和識(shí)別效率低的問題，提出一種無空閑時(shí)隙并行識(shí)別動(dòng)態(tài)多叉查詢樹算法。該算法利用同步正交碼（WALSH）作為擴(kuò)頻碼的碼分多址技術(shù)，實(shí)現(xiàn)在單一時(shí)隙并行識(shí)別多個(gè)標(biāo)簽的功能;通過跟蹤碰撞標(biāo)簽的碰撞位，預(yù)測標(biāo)簽分布，消除不存在的標(biāo)簽分支;使用后退查詢方式減少數(shù)據(jù)傳輸位數(shù)，提高識(shí)別速度。理論分析和仿真結(jié)果表明該算法具有較少的總時(shí)隙數(shù)和較高的系統(tǒng)吞吐量。

關(guān)鍵詞： 并行識(shí)別; 動(dòng)態(tài)多叉查詢樹算法; 空閑時(shí)隙; 后退查詢; 標(biāo)簽分布預(yù)測; 理論分析

中圖分類號： TN911?34? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼： A? ? ? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2020）20?0092?05

Parallel identification dynamic N?ARY query tree algorithm without idle time slot

BAI Leqiang， LIU Jie， CAO Keyan

（School of Information & Control Engineering， Shenyang Jianzhu University， Shenyang 110168， China）

Abstract： As the dynamic N?ARY query tree RFID anti?collision algorithm without idle time slot has unstable system throughput and low recognition efficiency in the process of tag identification， a parallel identification dynamic N?ARY query tree algorithm without idle time slot is proposed. In this algorithm， the code division multi?address technology using synchronous orthogonal code （WALSH） as spread spectrum code is used to realize the function of the parallel recognition of multiple tags in a single time slot， the label distribution is predicted for elimination of the nonexistent label branches by tracking the collision bits of collision tags， and the backward query mode is used to reduce the number of data transmission bits and improve the recognition speed. The theoretical analysis and simulation results show that the algorithm has less total number of time slots and higher system throughput.

Keywords： parallel identification; dynamic N?ARY query tree algorithm; idle time slot; backward query; tag distribution prediction; theoretical analysis

0? 引? 言

隨著信息化時(shí)代的到來，物聯(lián)網(wǎng)產(chǎn)業(yè)得到蓬勃發(fā)展，現(xiàn)已廣泛應(yīng)用于物流管理、人工智能、自動(dòng)駕駛、智能家居等領(lǐng)域。無線射頻識(shí)別（RFID）技術(shù)、傳感器技術(shù)、嵌入式系統(tǒng)技術(shù)是組成物聯(lián)網(wǎng)的三大關(guān)鍵技術(shù)，其中，RFID技術(shù)作為物聯(lián)網(wǎng)結(jié)構(gòu)中的感知層，受海內(nèi)外研究人員的關(guān)注。通常，RFID系統(tǒng)由閱讀器、標(biāo)簽與天線三部分構(gòu)成[1]。閱讀器用于識(shí)別或讀取標(biāo)簽;標(biāo)簽通過內(nèi)嵌芯片存儲(chǔ)附著物的身份信息，擁有全球唯一的ID;天線用于傳遞兩者之間內(nèi)存數(shù)據(jù)的讀/寫操作[2]。當(dāng)多個(gè)標(biāo)簽同時(shí)向閱讀器發(fā)送處理數(shù)據(jù)時(shí)，導(dǎo)致通信信道堵塞，閱讀器接收數(shù)據(jù)受損，無法執(zhí)行正常讀/寫操作，這就是標(biāo)簽碰撞。所以，減少標(biāo)簽碰撞，保證數(shù)據(jù)傳輸?shù)耐暾院驼_性是提高RFID系統(tǒng)穩(wěn)定性，打破物聯(lián)網(wǎng)產(chǎn)業(yè)技術(shù)壁壘的關(guān)鍵所在。

目前主要存在兩類防碰撞算法：基于ALOHA防碰撞算法和基于樹防碰撞算法[3]?；贏LOHA防碰撞算法采用回避原則，射頻場內(nèi)的所有標(biāo)簽可隨時(shí)傳遞信息給閱讀器，閱讀器判斷是成功接收還是碰撞，若為碰撞，則閱讀器要求標(biāo)簽概率性延遲幾個(gè)時(shí)隙再發(fā)送。然而，當(dāng)大量標(biāo)簽涌入射頻場，存在標(biāo)簽持續(xù)被延遲，最終無法被識(shí)別，這就是“標(biāo)簽餓死”現(xiàn)象。目前，研究人員主要通過事先預(yù)測待識(shí)別標(biāo)簽數(shù)量，采用某種算法調(diào)整幀內(nèi)時(shí)隙數(shù)，最大限度減少碰撞來提高識(shí)別效率?；跇浞琅鲎菜惴╗4]分為查詢樹（QT）算法和搜索樹（BT）算法，是一種非概率性算法，能夠達(dá)到百分百識(shí)別。閱讀器發(fā)送查詢前綴給射頻場內(nèi)的標(biāo)簽，包含該前綴的標(biāo)簽響應(yīng)。閱讀器判斷是成功接收還是碰撞，若為碰撞，則閱讀器擴(kuò)充查詢前綴再發(fā)送，直到識(shí)別所有標(biāo)簽。然而，當(dāng)待識(shí)別標(biāo)簽數(shù)量較多時(shí)，碰撞時(shí)隙和空閑時(shí)隙占總時(shí)隙比例較大，導(dǎo)致識(shí)別時(shí)間延長，系統(tǒng)吞吐量降低。

基本防碰撞算法閱讀器每次識(shí)別過程只能識(shí)別一個(gè)標(biāo)簽，系統(tǒng)吞吐量較低。牛愛民提出無空閑時(shí)隙動(dòng)態(tài)多叉查詢樹RFID防碰撞（DMQT）算法[5]，當(dāng)多標(biāo)簽響應(yīng)時(shí)，該算法利用曼徹斯特編碼精確判斷標(biāo)簽碰撞位，根據(jù)連續(xù)碰撞位的數(shù)量，動(dòng)態(tài)調(diào)整樹的分裂;通過跟蹤查詢碰撞位，預(yù)測碰撞標(biāo)簽分布，剪去標(biāo)簽不存在的分支。

本文在無空閑時(shí)隙的動(dòng)態(tài)多叉查詢樹RFID防碰撞算法的基礎(chǔ)上，結(jié)合WALSH碼的同步正交特性，提出無空閑時(shí)隙并行識(shí)別動(dòng)態(tài)多叉查詢樹算法（DIPQT）。該算法將標(biāo)簽ID與WALSH擴(kuò)頻碼進(jìn)行擴(kuò)頻，擴(kuò)頻后的標(biāo)簽會(huì)以不同的碼道與閱讀器通信，以此減少碰撞發(fā)生的概率。

1? DMQT算法

曼徹斯特編碼常用于RFID系統(tǒng)中檢測碰撞位的位置，如果多個(gè)標(biāo)簽同步傳輸?shù)臄?shù)據(jù)流中，存在0和1兩種不同的比特，該位的曼徹斯特編碼不會(huì)出現(xiàn)跳變，即此位為碰撞位。DMQT對自適應(yīng)多叉樹防碰撞算法進(jìn)行優(yōu)化，其主要改進(jìn)是閱讀器通過兩類查詢方式識(shí)別標(biāo)簽，一類是識(shí)別查詢，另一類是當(dāng)標(biāo)簽發(fā)生ID碰撞時(shí)的位跟蹤查詢。閱讀器通過在查詢前綴q1q2…qk后附加標(biāo)志位（flag）來識(shí)別兩類查詢。每次標(biāo)簽接收到閱讀器發(fā)送的請求指令時(shí)，首先判斷flag，若flag=0，則表示識(shí)別查詢，匹配查詢前綴的標(biāo)簽將除前綴外的剩余ID號傳輸給閱讀器;若flag=1，則表示位跟蹤查詢，位跟蹤查詢的響應(yīng)方式如下：

1） 利用曼徹斯特編碼判斷標(biāo)簽最高連續(xù)碰撞位n的個(gè)數(shù)，確定分裂叉樹為2n，最高不超過64叉;

2） 閱讀器發(fā)送REQUEST（0…0+1…1，1）指令，其中0的比特?cái)?shù)為n個(gè)，剩余比特均為1;

3） 標(biāo)簽接收到位跟蹤查詢指令后，將標(biāo)簽ID中與1…1對應(yīng)位換算為十進(jìn)制數(shù)字s，然后回送一個(gè)長度為2n比特?cái)?shù)據(jù)，其中第s mod 2n位設(shè)成1，剩余位設(shè)成0。

2? 改進(jìn)算法

通常，在基于樹的防碰撞算法中，用時(shí)隙來表示閱讀器識(shí)別標(biāo)簽所消耗的時(shí)間，該算法在識(shí)別標(biāo)簽的過程中可能會(huì)碰到以下3種時(shí)隙狀態(tài)。

1） 碰撞時(shí)隙。有2個(gè)以上標(biāo)簽響應(yīng)，并且標(biāo)簽與閱讀器用相同的碼道通信，此時(shí)標(biāo)簽ID及擴(kuò)頻碼均碰撞，閱讀器無法解碼。

2） 偽碰撞時(shí)隙。有2個(gè)以上標(biāo)簽響應(yīng)，但是存在標(biāo)簽具有唯一的擴(kuò)頻碼，這些標(biāo)簽獨(dú)占1條碼道，解碼后閱讀器能夠成功識(shí)別，剩余的碰撞標(biāo)簽等待下次查詢。

3） 成功時(shí)隙。只有1個(gè)標(biāo)簽響應(yīng)，閱讀器與之建立通信并讀取標(biāo)簽中的信息。

2.1? 算法思想

Don R. Hush在RFID仲裁樹算法[6]中分析，完全分裂的多叉樹總時(shí)隙數(shù)[t（m）]為：

[t（m）=c（m）+z（m）+m? ? ? ? ? =1+BL=0∞BL[1-（1-B-L）m-mBL（1-B-L）m-1]] （1）

式中：[c（m）]為碰撞時(shí)隙;[z（m）]為空閑時(shí)隙;m為射頻場內(nèi)標(biāo)簽數(shù)目;B為完全多叉樹的分裂叉樹;L為完全多叉樹的深度。

碰撞時(shí)隙[c（m）]為：

[c（m）=1B（t（m）-1）] （2）

空閑時(shí)隙[z（m）]為：

[z（m）=B-1Bt（m）-m+1B] （3）

經(jīng)上述公式得到完全多叉樹的時(shí)隙占比如表1所示。

從表1分析隨著分裂叉樹B的增大，碰撞時(shí)隙占比減少，空閑時(shí)隙占比增大，如果能夠完全消除空閑時(shí)隙或者用碰撞時(shí)隙代替空閑時(shí)隙，勢必會(huì)提高系統(tǒng)吞吐量。

WALSH序列碼[7]是一種同步正交碼，是一個(gè)實(shí)現(xiàn)碼分多址（CDMA）信號傳輸?shù)拇a，它們互相之間完全正交。WALSH碼可以用來區(qū)分一個(gè)時(shí)隙里面的多個(gè)碼道，擴(kuò)頻碼長度為m時(shí)，可以產(chǎn)生m個(gè)互相關(guān)特性為0的擴(kuò)頻碼。當(dāng)標(biāo)簽接收到閱讀器發(fā)送的擴(kuò)頻指令后，從碼表中隨機(jī)選擇擴(kuò)頻碼與自己的ID結(jié)合，之后閱讀器與標(biāo)簽會(huì)通過不同的碼道通信。

閱讀器通過REQUEST指令查詢標(biāo)簽，其格式如下：REQUEST（q1q2…qk，flag），q1q2…qk為查詢前綴，flag表示查詢標(biāo)志符，flag∈{0，1}，flag=0時(shí)，代表識(shí)別查詢，flag=1時(shí)，代表位跟蹤查詢。閱讀器發(fā)送REQUEST（q1q2…qk，flag）命令，符合查詢前綴的標(biāo)簽響應(yīng)。

2.2? 算法流程

閱讀器操作步驟如下：

步驟1：閱讀器在內(nèi)部存儲(chǔ)器開辟空間，新建一個(gè)用來存儲(chǔ)查詢前綴的空棧S，發(fā)送REQUEST（ε）指令。

步驟2：閱讀器探察有無標(biāo)簽回送的完整ID號，若無，表示閱讀器周圍無電子標(biāo)簽，轉(zhuǎn)至步驟1;若有，執(zhí)行PUSH（QUERY）進(jìn)棧指令，將前綴1和前綴0入棧，同時(shí)向標(biāo)簽發(fā)送碼長參數(shù)為m的WALSH擴(kuò)頻指令。

步驟3：若閱讀器接收到標(biāo)簽ID和擴(kuò)頻碼正交調(diào)制信號，發(fā)送REQUEST（q1q2…qk，0）指令，其中最后的0表示識(shí)別查詢。

步驟4：若閱讀器接收到標(biāo)簽傳輸?shù)牟话ú樵兦熬Y剩余ID數(shù)據(jù)，閱讀器內(nèi)部解碼模塊對標(biāo)簽數(shù)據(jù)解碼，根據(jù)解碼結(jié)果判斷時(shí)隙的狀態(tài)。

1） 如果時(shí)隙內(nèi)只有1個(gè)標(biāo)簽響應(yīng)，該時(shí)隙為識(shí)別時(shí)隙，閱讀器可直接與該標(biāo)簽通信，識(shí)別后將標(biāo)簽置為沉默狀態(tài)，轉(zhuǎn)至步驟6。

2） 如果時(shí)隙內(nèi)有2個(gè)以上標(biāo)簽響應(yīng)，并且具有相同的WALSH擴(kuò)頻碼，該時(shí)隙為碰撞時(shí)隙，此時(shí)標(biāo)簽ID及擴(kuò)頻碼均碰撞，無法識(shí)別信息，轉(zhuǎn)至步驟③。

3） 如果時(shí)隙內(nèi)有2個(gè)以上標(biāo)簽響應(yīng)，但是存在標(biāo)簽具有唯一的WALSH擴(kuò)頻碼，該時(shí)隙為偽碰撞時(shí)隙，這些具有唯一擴(kuò)頻碼的標(biāo)簽獨(dú)占一條碼道通信，可以被閱讀器成功識(shí)別，識(shí)別后將標(biāo)簽置為沉默狀態(tài)。

① 如果偽碰撞時(shí)隙內(nèi)除去有唯一擴(kuò)頻碼的標(biāo)簽后沒有剩余標(biāo)簽待識(shí)別，轉(zhuǎn)至步驟6;如果偽碰撞時(shí)隙內(nèi)除去有唯一擴(kuò)頻碼的標(biāo)簽后還有剩余標(biāo)簽待識(shí)別，在剩余標(biāo)簽中，判斷連續(xù)最高碰撞位數(shù)目n。若n=1，轉(zhuǎn)至步驟②;若n>1，轉(zhuǎn)至步驟③。

② 閱讀器產(chǎn)生兩個(gè)新查詢前綴，執(zhí)行PUSH（QUERY）指令，QUERY_1=原查詢前綴，QUERY_2=首碰撞位之前的位串+1。

③閱讀器發(fā)送位跟蹤查詢指令REQUEST（0…0+1…1，1），其中0的比特?cái)?shù)為n，剩余比特均為1。

步驟5：若閱讀器接收到標(biāo)簽發(fā)送的位跟蹤查詢的計(jì)算結(jié)果信息，用曼徹斯特編碼判斷哪些分支存在標(biāo)簽，剪去標(biāo)簽不存在的分支，執(zhí)行PUSH（QUERY）指令，QUERY=原前綴+標(biāo)簽存在分支。

步驟6：判斷棧S狀態(tài)，如果棧S不為空，則讀取棧首位，作為查詢前綴繼續(xù)查詢，轉(zhuǎn)至步驟3;如果棧S為空，則查詢結(jié)束。

DIPQT算法閱讀器流程如圖1所示。

標(biāo)簽操作步驟如下：

步驟1：若標(biāo)簽接收到REQUEST（ε）指令，將自己的ID號發(fā)送給閱讀器。

步驟2：若標(biāo)簽接收到碼長參數(shù)為m的WALSH擴(kuò)頻指令，標(biāo)簽隨機(jī)選擇擴(kuò)頻碼與ID進(jìn)行擴(kuò)頻，將標(biāo)簽ID和擴(kuò)頻碼正交調(diào)制信號回送給閱讀器。

步驟3：若標(biāo)簽接收到REQUEST（q1q2…qk，flag）指令，根據(jù)flag判斷閱讀器的查詢類型，若flag=0，轉(zhuǎn)至步驟1）;若flag=1，轉(zhuǎn)至步驟2）。

1） 標(biāo)簽檢測自己的ID是否與查詢前綴匹配，如果不匹配，不作響應(yīng);如果匹配，發(fā)送除查詢前綴外的剩余ID號。

2） 標(biāo)簽根據(jù)位跟蹤查詢REQUEST（0…0+1…1，1），將ID中與1…1對應(yīng)位換算為十進(jìn)制數(shù)字s，然后回送一個(gè)長度為2n比特?cái)?shù)據(jù)，其中第s mod 2n位設(shè)成1，其他位設(shè)置為0，將位跟蹤查詢的計(jì)算結(jié)果信息回送給閱讀器。

DIPQT算法標(biāo)簽響應(yīng)的流程如圖2所示。

3? 算法理論分析

在RFID系統(tǒng)中，評價(jià)防碰撞算法好壞的重要指標(biāo)有總時(shí)隙數(shù)和系統(tǒng)吞吐量。DIPQT算法利用自適應(yīng)多叉樹的動(dòng)態(tài)分裂特性，樹的分裂叉數(shù)可隨碰撞標(biāo)簽數(shù)目變化。假設(shè)標(biāo)簽ID長度為96 bit，最高連續(xù)碰撞位為h位，此時(shí)采用2h叉樹分裂，分裂叉樹必須小于標(biāo)簽ID長度，即DIPQT算法最高分裂64叉，此時(shí)得到最少總時(shí)隙數(shù)。

完全64叉樹DIPQT算法的總時(shí)隙數(shù)為：識(shí)別時(shí)隙+碰撞時(shí)隙+位跟蹤查詢時(shí)隙（位跟蹤時(shí)隙數(shù)等于碰撞時(shí)隙數(shù)）。若射頻場內(nèi)中有N個(gè)標(biāo)簽等待識(shí)別，則完全64叉樹的總時(shí)隙數(shù)[5]T64為：

[T64=65N-263] （4）

若擴(kuò)頻碼隨機(jī)分布，且擴(kuò)頻碼碼長為m，理想狀況下擴(kuò)頻后的最小總時(shí)隙Tmin為：

[Tmin=T64m=65N-263m] （5）

當(dāng)最高連續(xù)碰撞位僅有1個(gè)，此時(shí)碰撞時(shí)隙最多，得到最多總時(shí)隙數(shù)，完全2叉樹的總時(shí)隙數(shù)T2為[8]：

[T2=2N-1] （6）

理想狀況下擴(kuò)頻后的最大總時(shí)隙Tmax為：

[Tmax=T2m=2N-1m] （7）

由式（5）和式（7）得到理想狀況下DIPQT算法所需的總時(shí)隙數(shù)T為：

[T∈65N-263m，2N-1m] （8）

通過上述分析可知，若標(biāo)簽數(shù)量一定，隨著擴(kuò)頻碼碼長m的增加，總時(shí)隙數(shù)會(huì)大幅度下降，但系統(tǒng)的設(shè)計(jì)復(fù)雜度會(huì)變大，閱讀器利用碼表擴(kuò)頻占用較多時(shí)間，使得算法的整體工作效率變低。

系統(tǒng)吞吐量表示閱讀器在一個(gè)時(shí)隙內(nèi)平均識(shí)別標(biāo)簽的數(shù)量，是評價(jià)RFID防碰撞算法性能的重要指標(biāo)之一。假設(shè)系統(tǒng)中有N個(gè)標(biāo)簽待識(shí)別，在一個(gè)時(shí)隙內(nèi)，有n個(gè)標(biāo)簽響應(yīng)且WALSH擴(kuò)頻碼碼長為[m]的期望吞吐量ESlot為：

[ESlot=mnm1-1mn-1] （9）

設(shè)L為樹分裂的叉數(shù)，則樹搜索的層數(shù)k為：

[k=logLNn] （10）

根據(jù)查詢樹的基本原理，在一個(gè)時(shí)隙內(nèi)有n個(gè)標(biāo)簽響應(yīng)的概率[P（T）]服從二項(xiàng)分布[9]：

[P（T）=CnN（L-k）n（1-L-k）N-n] （11）

基于樹查詢算法的吞吐量為一個(gè)時(shí)隙內(nèi)有n個(gè)標(biāo)簽響應(yīng)的期望吞吐量與概率乘積的加和，即DIPQT算法的吞吐量S為：

[S=n=0NP（T）?ESlot] （12）

由DIPQT算法可知，當(dāng)擴(kuò)頻碼長度m確定，連續(xù)最高碰撞位h=6時(shí)，最高分裂叉樹等于2h=64叉，DIPQT算法的系統(tǒng)吞吐量S為：

[S=n=02CnN（2-k）n（1-2-k）N-n?mnm1-1mn-1+? ? ? n=363CnN（n-k）n（1-n-k）N-n?mnm1-1mn-1+? ? ?n=64NCnN（64-k）n（1-64-k）N-nmnm1-1mn-1] （13）

通過以上對DIPQT算法性能的理論分析可知，DIPQT算法的防碰撞性能得到了較大提升，系統(tǒng)吞吐量高于DMQT算法。

4? 算法仿真及分析

以Matlab 2018a為仿真平臺(tái)對算法進(jìn)行仿真，閱讀器射頻場內(nèi)的標(biāo)簽數(shù)量取值為100～1 000，標(biāo)簽ID均勻分布，固定為96 bit長度，仿真20次取平均值。下面將DIPQT算法和GBAQT算法[10]、A4PQT算法[11]、DMQT算法進(jìn)行仿真分析，從總時(shí)隙數(shù)和系統(tǒng)吞吐量兩個(gè)方面進(jìn)行比較。

在RFID系統(tǒng)中，當(dāng)標(biāo)簽數(shù)量一定的情況下，隨著擴(kuò)頻碼碼長m的增加，標(biāo)簽在同一個(gè)時(shí)隙內(nèi)出現(xiàn)“碼碰撞”的概率就越小，系統(tǒng)期望的吞吐量隨之增大，防碰撞的性能越好。但是，m值的增加就意味著系統(tǒng)運(yùn)行占用的資源增加，系統(tǒng)的硬件設(shè)計(jì)復(fù)雜度會(huì)大大增加[12]。經(jīng)驗(yàn)證，取值m∈{2i，i=0，1，…，7}可滿足實(shí)際生活需要。

圖3表示DIPQT算法與其他三種算法總時(shí)隙數(shù)的比較?；谒牟鏄湫薷牡腁4PQT算法在標(biāo)簽數(shù)量變多時(shí)總時(shí)隙數(shù)變得非常大，識(shí)別1 000個(gè)標(biāo)簽大約需要2 000個(gè)時(shí)隙。

GBAQT算法采用標(biāo)簽分組的方法消除了部分空閑時(shí)隙，標(biāo)簽數(shù)量小于500時(shí)，總時(shí)隙數(shù)與A4PQT算法和DMQT算法相差不大;標(biāo)簽數(shù)量大于500時(shí)，GBAQT算法明顯遜色于DMQT算法。DMQT算法雖然完全消除了空閑時(shí)隙，但是會(huì)增加少許的位跟蹤時(shí)隙，DMQT算法大幅度減少了總時(shí)隙數(shù)，識(shí)別1 000個(gè)標(biāo)簽約需要1 400個(gè)時(shí)隙。前三個(gè)算法由于沒有使用并行識(shí)別技術(shù)，總時(shí)隙數(shù)都在1 000以上，而DIPQT算法（m=8）識(shí)別1 000個(gè)標(biāo)簽所需時(shí)隙數(shù)約為700個(gè)，DIPQT算法（m=128）所需總時(shí)隙數(shù)更少，最大不超過200個(gè)時(shí)隙。通過對以上對比發(fā)現(xiàn)DIPQT算法更適用于標(biāo)簽數(shù)量較多的場景。

圖4表示DIPQT算法與其他三種算法的系統(tǒng)吞吐量的比較。通過圖4a）可看出，DIPQT算法（m=8）的吞吐量要明顯高于GBAQT算法和A4PQT算法。GBAQT算法的吞吐量在0.54上下波動(dòng)，趨于穩(wěn)定;A4PQT算法的吞吐量一直在0.50以下，這是因?yàn)殡S著標(biāo)簽數(shù)量的增加，A4PQT算法會(huì)增加許多空閑時(shí)隙，從而導(dǎo)致吞吐量較低;DMQT算法消除了空閑時(shí)隙，使DMQT算法系統(tǒng)吞吐量提升幅度較大，在0.59和0.71之間波動(dòng)，上下波動(dòng)明顯。DIPQT算法（m=8）的系統(tǒng)吞吐量隨標(biāo)簽數(shù)量變化的曲線軌跡比較平穩(wěn)，較DMQT算法平均提高約8.6%。圖4b）中DIPQT算法（m=128）的吞吐量較DMQT算法平均提高約38.4%，當(dāng)標(biāo)簽數(shù)量達(dá)到500后，DIPQT算法的吞吐量在0.89趨于穩(wěn)定。

通過對算法的仿真結(jié)果分析可知，DIPQT算法系統(tǒng)吞吐量高于現(xiàn)有的其他查詢樹算法。

5? 結(jié)? 語

本文基于動(dòng)態(tài)多叉查詢樹和并行識(shí)別技術(shù)，提出一種無空閑時(shí)隙并行識(shí)別動(dòng)態(tài)多叉查詢防碰撞算法。該算法使用跟蹤碰撞時(shí)隙之間碰撞位的方法消除空閑時(shí)隙，利用碼分多址的擴(kuò)頻碼技術(shù)進(jìn)行并行識(shí)別。擴(kuò)頻后的閱讀器與標(biāo)簽會(huì)使用不同的碼道通信，減少了標(biāo)簽碰撞的產(chǎn)生，實(shí)現(xiàn)了在一個(gè)時(shí)隙內(nèi)最多可并行識(shí)別多個(gè)標(biāo)簽的功能，在每次識(shí)別完標(biāo)簽后后退到上一級碰撞節(jié)點(diǎn)，減少了數(shù)據(jù)傳輸。理論分析和仿真結(jié)果證明DIPQT算法大幅度減少了防碰撞算法的總識(shí)別時(shí)隙數(shù)，能有效提高系統(tǒng)識(shí)別速度和系統(tǒng)吞吐量，更適合用標(biāo)簽數(shù)量較多的場景。

參考文獻(xiàn)

[1] 郭振軍，孫應(yīng)飛.基于標(biāo)簽分組的RFID系統(tǒng)防碰撞算法[J].電子與信息學(xué)報(bào)，2017，39（1）：250?254.

[2] 曾實(shí)現(xiàn)，薛蕊，陳江波.基于物聯(lián)網(wǎng)RFID技術(shù)的導(dǎo)引系統(tǒng)設(shè)計(jì)與研究[J].現(xiàn)代電子技術(shù)，2017，40（19）：22?24.

[3] 王雪，錢志鴻，胡正超，等.基于二叉樹的RFID防碰撞算法的研究[J].通信學(xué)報(bào)，2010，31（6）：49?57.

[4] LIU Xiaohui， QIAN Zhihong， ZHAO Yanhong， et al. An adaptive tag anti?collision protocol in RFID wireless systems [J]. China communications， 2014， 11（7）： 117?127.

[5] 牛愛民.無空閑時(shí)隙的動(dòng)態(tài)多叉查詢樹RFID防碰撞算法[J].計(jì)算機(jī)應(yīng)用與軟件，2016，33（6）：277?281.

[6] HUSH D R， WOOD C. Analysis of tree algorithms for RFID arbitration [C]// Proceedings of IEEE International Symposium on Information Theory. Cambridge： IEEE， 1998： 107?116.

[7] 王岳松，孔韜.一種基于同相正交環(huán)的數(shù)字曼徹斯特解碼方法[J].中國電子科學(xué)研究院學(xué)報(bào)，2015，10（3）：317?320.

[8] ZHANG Yin， YANG Fan， WANG Qian， et al. An anti?collision algorithm for RFID?based robots based on dynamic grouping binary trees [J]. Computers and electrical engineering， 2017， 63： 91?98.

[9] YEH M K， JIANG J R. Parallel splitting for RFID tag anti?collision [J]. International journal of ad hoc and ubiquitous computing， 2011， 8（4）： 249?260.

[10] 付鈺，錢志鴻，程超，等.基于分組機(jī)制的位仲裁查詢樹防碰撞算法[J].通信學(xué)報(bào)，2016，37（1）：123?129.

[11] ZHANG W， GUO Y， 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， 2013： 1?7.

[12] 王必勝，張其善.可并行識(shí)別的超高頻RFID系統(tǒng)防碰撞性能研究[J].通信學(xué)報(bào)，2009，30（6）：108?113.