白樂強，劉 杰，曹科研

(沈陽建筑大學(xué)信息與控制工程學(xué)院，遼寧 沈陽 110168)

1 引言

智能化科技的點滴進步，都將帶領(lǐng)社會生產(chǎn)力的顯著提升。隨著大數(shù)據(jù)開發(fā)、自然語言處理、圖形圖像處理、“互聯(lián)網(wǎng)+”等一系列尖端技術(shù)的日益成熟，一個萬物相息、互聯(lián)互通的時代即將到來。無線射頻識別(RFID)技術(shù)作為物聯(lián)網(wǎng)產(chǎn)業(yè)的中流砥柱，發(fā)揮著不可替代的作用。RFID系統(tǒng)[1]主要由閱讀器和標(biāo)簽組成，兩者通過無線電波傳遞處理數(shù)據(jù)。標(biāo)簽與閱讀器內(nèi)部各嵌入一個天線，當(dāng)兩天線靠近時會產(chǎn)生電磁場，標(biāo)簽從電磁場中獲得能量，將自身ID等數(shù)據(jù)通過天線發(fā)送給閱讀器。然而，當(dāng)多個標(biāo)簽同時發(fā)送數(shù)據(jù)給閱讀器時，會導(dǎo)致通信信道堵塞，閱讀器無法正常接收標(biāo)簽數(shù)據(jù)并對其執(zhí)行讀寫操作，這就是標(biāo)簽碰撞[2]。

目前主要存在三類RFID標(biāo)簽防碰撞算法：ALOHA非確定性防碰撞算法、樹型確定性防碰撞算法、混合防碰撞算法[3]。經(jīng)典防碰撞算法識別效率不高，國內(nèi)外研究人員在經(jīng)典算法基礎(chǔ)上提出諸多優(yōu)異的防碰撞算法。丁治國等人提出一種自適應(yīng)多叉樹防碰撞(AMS)算法[4]，AMS算法能夠計算碰撞因子，預(yù)測時隙內(nèi)的標(biāo)簽數(shù)量，動態(tài)調(diào)整分裂叉樹，將系統(tǒng)吞吐量提升至0.545。Su Jian等人提出一種基于空閑時隙消除的RFID二叉分裂防碰撞(ISE-BS)算法[5]，該算法通過引進1bit隨機數(shù)Q值和16bit隨機數(shù)序列標(biāo)識符(SID)協(xié)助標(biāo)簽分裂，Q值在數(shù)據(jù)交換之前傳輸，可以提示閱讀器是否發(fā)生標(biāo)簽碰撞，從而減少不必要的數(shù)據(jù)交換。王漢武等人在AMS算法基礎(chǔ)上進行優(yōu)化并提出一種改進的自適應(yīng)多叉樹防碰撞(IACT)算法[6]，算法了將四叉查詢樹中的空閑時隙全部消除，大大降低了通信開銷。李川等人提出一種雙查詢前綴匹配的防碰撞(DPPS)算法[7]來提高RFID系統(tǒng)的識別效率，標(biāo)簽接收指令過后若與第一個查詢前綴匹配則，立即傳輸剩余ID號給閱讀器，否則延遲r個(r為完整ID長度減去查詢前綴長度)比特時間響應(yīng)，以此消除空閑時隙和減少碰撞時隙。

本文針對AMS算法中識別周期長、碰撞時隙多等缺點，提出一種基于前綴分組的改進自適應(yīng)多叉樹防碰撞(PGAMT)算法。在標(biāo)簽識別過程中，曼徹斯特編碼可以準(zhǔn)確判斷標(biāo)簽碰撞位，從而將查詢樹切割成若干分支，標(biāo)簽識別在各分支內(nèi)進行；識別過程中采用改進自適應(yīng)多叉樹防碰撞算法查詢，根據(jù)碰撞因子動態(tài)調(diào)整樹的分裂叉樹，從而有效減少總時隙數(shù)，加快識別速度提高系統(tǒng)吞吐量。

2 算法思想

基于前綴分組的自適應(yīng)多叉樹防碰撞算法將標(biāo)簽識別過程抽象成一顆龐大的四-二叉樹，樹的分支節(jié)點為識別過程中的碰撞時隙，樹的葉子節(jié)點為識別時隙。采用標(biāo)簽前綴分組方法，將查詢樹分割成若干分支，各分支互不干擾，以此縮減數(shù)據(jù)發(fā)生碰撞的概率。通過計算碰撞因子動態(tài)選擇樹的分裂叉樹，若標(biāo)簽在四叉樹部分響應(yīng)，則采用消除空閑時隙的動態(tài)四叉樹算法，若標(biāo)簽在二叉樹部分響應(yīng)，則采用碰撞跟蹤樹(CTT)算法[8]。若該分支內(nèi)存在的標(biāo)簽被全部識別，則算法開始識別下一分支，直至標(biāo)簽全部被識別。

2.1 前綴分組

閱讀器需要使用一個查詢周期確定范圍內(nèi)標(biāo)簽的前綴，并把查詢前綴壓入棧中。具體操作流程為：閱讀器選擇最優(yōu)的標(biāo)簽分組的前綴長度為，設(shè)為K比特，之后發(fā)送分組指令REQUEST(1…10…0)，其中比特1的個數(shù)為K，剩余比特為0，總位數(shù)為標(biāo)簽ID長度。標(biāo)簽接收到分組指令后將自身ID中的前K位轉(zhuǎn)換成十進制數(shù)S，并回送給閱讀器一個長度為2K比特的數(shù)據(jù)，其中從右往左第S位為1，剩余位均為0。閱讀器接收到標(biāo)簽的回送信息后，利用曼徹斯特編碼判斷標(biāo)簽的碰撞位置，再將十進制數(shù)表示的碰撞位置轉(zhuǎn)換成對應(yīng)的二進制數(shù)，通過此操作可以得到區(qū)域內(nèi)所有標(biāo)簽的前K位查詢前綴，并把查詢前綴壓入堆棧。

假設(shè)閱讀器工作區(qū)域有6個標(biāo)簽待識別，其ID分別為：Tag1(00011111)、Tag2(00100011)、Tag3(00101010)、Tag4(10010000)、Tag5(10001111)、Tag6(11001100)。假設(shè)分組前綴長度為K，前綴分組階段標(biāo)簽回復(fù)閱讀器的比特位要少于標(biāo)簽ID長度，即需要2K≤8，K≤3，為使防碰撞算發(fā)性能達到最大化，K取3，前綴確定表1如下。

表1 前綴確定表

根據(jù)閱讀器接收到的數(shù)據(jù)可知標(biāo)簽ID第0、1、4、6位碰撞，將其轉(zhuǎn)換成二進制000、001、100、110并壓入堆棧，之后的標(biāo)簽查詢操作都是在這四個分支下進行。

2.2 改進自適應(yīng)多叉樹防碰撞算法

曼徹斯特編碼是控制數(shù)據(jù)流傳輸?shù)囊环N編碼方式，每位編碼都會發(fā)生跳變。當(dāng)標(biāo)簽傳輸給閱讀器的數(shù)據(jù)既包含比特1又包含比特0時，此位編碼相互抵消，數(shù)據(jù)流不會發(fā)生跳變，能夠推斷出此位發(fā)生了碰撞。丁治國等人利用此特性提出了一種自適應(yīng)多叉樹防碰撞算法，該算法通過計算碰撞因子μ

(1)

動態(tài)調(diào)整樹的分裂叉樹，當(dāng)μ≥0.75，標(biāo)簽數(shù)目較多選擇動態(tài)四叉查詢樹識別，反之選擇動態(tài)二叉查詢樹識別，其中，nc代表碰撞比特，n代表響應(yīng)比特。自適應(yīng)多叉樹防碰撞算法在一定程度上減少了空閑時隙產(chǎn)生，提高了識別效率，但是并沒有完全消除空閑時隙，并存在較多的碰撞時隙，導(dǎo)致系統(tǒng)吞吐量在0.5～0.6左右。

基于前綴分組的改進自適應(yīng)多叉樹防碰撞算法對自適應(yīng)多叉樹防碰撞算法中的動態(tài)查詢部分進行了改進。閱讀器給周邊標(biāo)簽發(fā)送查詢指令REQUEST(q1，q2，…，qu)，只有查詢前綴完全匹配的標(biāo)簽作出回應(yīng)并將自身除查詢前綴之外的剩余位傳輸，閱讀器接收到標(biāo)簽傳送的剩余位信息后判斷μ值：

1) 若μ≥0.75時，采用無空閑時隙動態(tài)四叉查詢樹算法，響應(yīng)標(biāo)簽接收到閱讀器查詢指令后檢測自己的ID最高兩位碰撞位是否連續(xù)，若連續(xù)，則根據(jù)二-十進制代碼發(fā)送信號，閱讀器接收信號后利用曼徹斯特編碼解碼并將查詢前綴進棧；若不連續(xù)，則采用碰撞跟蹤樹算法查詢，首先利用曼徹斯特編碼的特性，得到所有回復(fù)標(biāo)簽中的正確位和碰撞位位置，閱讀器將首位碰撞位設(shè)置為0和1，之后將首碰位撞位之前的正確位同首碰撞位壓入堆棧中。

表2 二-十進制代碼

例如，對于查詢前綴q1q2…qu，如果收到的響應(yīng)為r1r2…rc-1rc，其中，qi，ri∈{0，1}，rc是首位碰撞位，之后閱讀器擴展新的查詢前綴，即：q1q2…qur1r2…rc-10和q1q2…qur1r2…rc-11。

2) 若μ<0.75，表明此分支中存在較少數(shù)目的標(biāo)簽，則采用碰撞跟蹤樹算法查詢。

2.3 算法流程

步驟1：閱讀器向范圍內(nèi)的標(biāo)簽發(fā)送一個長度等于標(biāo)簽ID長度的前綴分組指令，指令格式為REQUEST(1…10…0)，其中比特1的個數(shù)為K，剩余比特均為0。

步驟2：若閱讀器工作區(qū)域內(nèi)沒有標(biāo)簽待識別則轉(zhuǎn)至步驟1，否則待識別標(biāo)簽回送給閱讀器一個長度為2K比特的數(shù)據(jù)，其具體比特位按照前綴分組原則設(shè)置。

步驟3：閱讀器利用曼徹斯特編碼可以準(zhǔn)確檢測碰撞位的特性，對標(biāo)簽回送的數(shù)據(jù)進行處理，即將十進制代表的碰撞位置轉(zhuǎn)換成二進制序列并壓入堆棧S。

步驟4：從堆棧S中彈出棧頂元素，閱讀器廣播查詢指令REQUEST(q1q2…qu)，與查詢前綴q1q2…qu匹配的標(biāo)簽將除查詢前綴外的剩余ID發(fā)送。

步驟5：閱讀器利用曼徹斯特編碼判斷響應(yīng)標(biāo)簽的數(shù)目：

步驟5.1：如果有唯一標(biāo)簽響應(yīng)，該時隙為識別時隙，與該標(biāo)簽進行數(shù)據(jù)交換。

步驟5.2：如果有多個標(biāo)簽同時響應(yīng)，該時隙為碰撞時隙，閱讀器判斷碰撞位個數(shù)，如果碰撞位只有一位，則在標(biāo)簽中該位非0即1，閱讀器無需發(fā)送信息即可同時識別這兩個標(biāo)簽；如果碰撞位個數(shù)大于1，則通過計算碰撞因子μ，按照改進自適應(yīng)多叉樹防碰撞算法查詢標(biāo)簽。

步驟6：判斷棧S是否為空，若棧S不為空，則轉(zhuǎn)至步驟4，繼續(xù)識別標(biāo)簽；若棧S為空，則表明閱讀器范圍內(nèi)的所有標(biāo)簽已被成功識別，算法結(jié)束。

3 理論分析

在RFID系統(tǒng)中，評價一個防碰撞算法好壞的重要指標(biāo)有2個：總時隙數(shù)和系統(tǒng)吞吐量。

3.1 總時隙數(shù)

PGAMT算法將標(biāo)簽查詢過程劃分為前綴分組和標(biāo)簽識別這兩個階段。假設(shè)標(biāo)簽ID編碼長度為96位，前綴分組長度為K比特，最多產(chǎn)生2K種查詢前綴，由于前綴分組階段標(biāo)簽回復(fù)閱讀器的比特位要少于標(biāo)簽ID長度，即2K≤96，K≤6。在前綴分組階段，閱讀器可以使用一次查詢確定通信范圍內(nèi)標(biāo)簽前K比特的查詢前綴，在標(biāo)簽識別階段，閱讀器需要對組內(nèi)標(biāo)簽逐一識別。

假設(shè)待識別標(biāo)簽數(shù)量為N，標(biāo)簽ID均勻分布，理想狀況下，前綴分組能將標(biāo)簽平均分為t組(1≤t≤2K)，每組內(nèi)約有n=(N/t)個標(biāo)簽。對其中一個分組分析，當(dāng)碰撞因子μ<0.75時，采用二叉碰撞跟蹤樹查詢標(biāo)簽，反之采用消除空閑時隙的動態(tài)四叉樹查詢標(biāo)簽。閱讀器查詢標(biāo)簽的結(jié)果僅有碰撞時隙(分支節(jié)點)和識別時隙(葉子節(jié)點)兩種，當(dāng)閱讀器對標(biāo)簽查詢時可以抽象為對一棵二-四叉樹執(zhí)行遍歷操作，由于本算法消除了空閑時隙，則分支節(jié)點僅有度為2和4兩種節(jié)點。

根據(jù)自適應(yīng)多叉樹防碰撞算法分析，若樹的搜索深度為h，樹的平均子節(jié)點為3，當(dāng)搜索深度小于h時，采用四叉樹查詢，反之采用二叉樹查詢，搜索深度h=?log4(n/3)」。因此，自適應(yīng)多叉樹防碰撞算法的總時隙數(shù)TAMS為兩部分時隙數(shù)相加

TAMS=T2-ary+T4-ary

(2)

當(dāng)搜索深度小于h層，沒有消除空閑時隙的四叉查詢時隙數(shù)T4-ary為

(3)

當(dāng)搜索深度大于h層，二叉查詢時隙數(shù)T2-ary為

(4)

為了計算消除空閑時隙的四叉查詢總時隙數(shù)，接下來計算四叉查詢樹的空閑時隙概率。根據(jù)數(shù)據(jù)結(jié)構(gòu)中完全多叉樹的性質(zhì)：一棵完全四叉樹，第L層中有4L個節(jié)點(層數(shù)L等同于深度h)。假設(shè)待識別標(biāo)簽有n個，其中有m個標(biāo)簽相應(yīng)在同一個節(jié)點的概率服從二項分布[9]

(5)

空閑時隙出現(xiàn)的概率為

P(0/m，L)=(1-4-L)n

(6)

四叉樹中可能產(chǎn)生的空閑時隙數(shù)目為四叉查詢總時隙數(shù)T4-ary與空閑時隙出現(xiàn)的概率之積[10]：

(7)

PGAMT算法在識別過程中若遇到碰撞位只有一個的情況只需一次查詢就能同時識別兩個標(biāo)簽，假設(shè)在組內(nèi)四叉樹部分這樣的節(jié)點數(shù)為u個，二叉樹部分這樣的節(jié)點數(shù)為v個，則此算法識別一個小分支內(nèi)需要閱讀器的查詢次數(shù)為

(8)

PGAMT算法總時隙數(shù)為前綴分組階段的一次查詢加上各小組內(nèi)時隙數(shù)之和

TPGAMT=t(T2-ary+T4-ary-T4-idel-u-v)+1

(9)

3.2 系統(tǒng)吞吐量

系統(tǒng)吞吐量即識別時隙與總時隙之比[11]，對于待識別標(biāo)簽N，識別時隙為N，其系統(tǒng)吞吐量SPGAMT為

(10)

4 仿真研究

本文以MATLAB2018a為仿真平臺對PGAMT算法進行仿真分析，遵循EPCglobal編碼標(biāo)準(zhǔn)，閱讀器工作區(qū)域內(nèi)的標(biāo)簽數(shù)量取值為100～1000，標(biāo)簽ID均勻分布，固定為96bit長度，仿真50次取平均值。圖1、圖2表示PGAMT算法與AMS算法、ISE-BS算法、IACT算法在碰撞時隙數(shù)、總時隙數(shù)和系統(tǒng)吞吐量三個方面的比較。

圖1 四種算法的性能比較

圖2 吞吐量

圖1表示PGAMT算法與其它三種算法碰撞時隙和總時隙之間的比較。PGAMT算法消除了AMS算法中存在較多空閑時隙的問題，當(dāng)識別過程中只有一位碰撞位，則閱讀器不用繼續(xù)搜索即可同時識別兩個標(biāo)簽，以此消減了部分碰撞時隙。從圖1可以看出，PGAMT算法性能明顯優(yōu)于ISE-BS算法和AMS算法，隨著標(biāo)簽數(shù)量增多，PGAMT算法與IACT算法的差距也在逐漸拉大。在標(biāo)簽數(shù)量達到1000時，ISE-BS算法識別所有標(biāo)簽需要2463個時隙，AMS算法需要1877個時隙，IACT算法要1636個時隙，而PGAMT算法需要1568個時隙。結(jié)果表明，在標(biāo)簽數(shù)量較多時，PGAMT算法優(yōu)勢明顯。

圖2表示PGAMT算法與其它三種算法系統(tǒng)吞吐量之間的比較。從圖中可以看出，PGAMT算法吞吐量明顯高于其它三種算法，最高達到0.709，隨著標(biāo)簽數(shù)量的增加，PGAMT算法吞吐量穩(wěn)定于0.641。IACT算法最高只有0.618，穩(wěn)定于0.613，AMS算法和ISE-BS算法吞吐量僅有0.535和0.405。結(jié)果表明，PGAMT算法雖然波動幅度較大，但吞吐量明顯高于其它防碰撞算法。

5 總結(jié)

本文針對自適應(yīng)多叉樹防碰撞算法存在查詢周期長，系統(tǒng)識別效率低等缺點，提出一種基于前綴分組的改進自適應(yīng)多叉樹防碰撞算法。在前綴分組階段，將一棵復(fù)雜的多叉查詢樹切割，以此減少碰撞時隙的產(chǎn)生，提高系統(tǒng)吞吐量。在標(biāo)簽識別階段，通過計算碰撞因子，預(yù)測標(biāo)簽數(shù)量，動態(tài)選擇分裂叉樹，在標(biāo)簽數(shù)量較少的分支采用跟蹤碰撞樹算法，在標(biāo)簽數(shù)量較多的分支采用無空閑時隙的動態(tài)四叉樹算法。理論分析和仿真證明該算法標(biāo)簽識別全程沒有產(chǎn)生空閑時隙，大幅度提高了系統(tǒng)吞吐量和查詢速度，在龐大的物聯(lián)網(wǎng)產(chǎn)業(yè)中，具有一定的實用價值。