基于前綴分組的改進(jìn)自適應(yīng)多叉樹防碰撞算法

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

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

1 引言

智能化科技的點(diǎn)滴進(jìn)步，都將帶領(lǐng)社會(huì)生產(chǎn)力的顯著提升。隨著大數(shù)據(jù)開發(fā)、自然語言處理、圖形圖像處理、“互聯(lián)網(wǎng)+”等一系列尖端技術(shù)的日益成熟，一個(gè)萬物相息、互聯(lián)互通的時(shí)代即將到來。無線射頻識別(RFID)技術(shù)作為物聯(lián)網(wǎng)產(chǎn)業(yè)的中流砥柱，發(fā)揮著不可替代的作用。RFID系統(tǒng)[1]主要由閱讀器和標(biāo)簽組成，兩者通過無線電波傳遞處理數(shù)據(jù)。標(biāo)簽與閱讀器內(nèi)部各嵌入一個(gè)天線，當(dāng)兩天線靠近時(shí)會(huì)產(chǎn)生電磁場，標(biāo)簽從電磁場中獲得能量，將自身ID等數(shù)據(jù)通過天線發(fā)送給閱讀器。然而，當(dāng)多個(gè)標(biāo)簽同時(shí)發(fā)送數(shù)據(jù)給閱讀器時(shí)，會(huì)導(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算法能夠計(jì)算碰撞因子，預(yù)測時(shí)隙內(nèi)的標(biāo)簽數(shù)量，動(dòng)態(tài)調(diào)整分裂叉樹，將系統(tǒng)吞吐量提升至0.545。Su Jian等人提出一種基于空閑時(shí)隙消除的RFID二叉分裂防碰撞(ISE-BS)算法[5]，該算法通過引進(jìn)1bit隨機(jī)數(shù)Q值和16bit隨機(jī)數(shù)序列標(biāo)識符(SID)協(xié)助標(biāo)簽分裂，Q值在數(shù)據(jù)交換之前傳輸，可以提示閱讀器是否發(fā)生標(biāo)簽碰撞，從而減少不必要的數(shù)據(jù)交換。王漢武等人在AMS算法基礎(chǔ)上進(jìn)行優(yōu)化并提出一種改進(jìn)的自適應(yīng)多叉樹防碰撞(IACT)算法[6]，算法了將四叉查詢樹中的空閑時(shí)隙全部消除，大大降低了通信開銷。李川等人提出一種雙查詢前綴匹配的防碰撞(DPPS)算法[7]來提高RFID系統(tǒng)的識別效率，標(biāo)簽接收指令過后若與第一個(gè)查詢前綴匹配則，立即傳輸剩余ID號給閱讀器，否則延遲r個(gè)(r為完整ID長度減去查詢前綴長度)比特時(shí)間響應(yīng)，以此消除空閑時(shí)隙和減少碰撞時(shí)隙。

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

2 算法思想

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

2.1 前綴分組

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

假設(shè)閱讀器工作區(qū)域有6個(gè)標(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ā)性能達(dá)到最大化，K取3，前綴確定表1如下。

表1 前綴確定表

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

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

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

(1)

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

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

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

表2 二-十進(jìn)制代碼

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

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

2.3 算法流程

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

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

步驟3：閱讀器利用曼徹斯特編碼可以準(zhǔn)確檢測碰撞位的特性，對標(biāo)簽回送的數(shù)據(jù)進(jìn)行處理，即將十進(jìn)制代表的碰撞位置轉(zhuǎn)換成二進(jì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)，該時(shí)隙為識別時(shí)隙，與該標(biāo)簽進(jìn)行數(shù)據(jù)交換。

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

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

3 理論分析

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

3.1 總時(shí)隙數(shù)

PGAMT算法將標(biāo)簽查詢過程劃分為前綴分組和標(biāo)簽識別這兩個(gè)階段。假設(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)個(gè)標(biāo)簽。對其中一個(gè)分組分析，當(dāng)碰撞因子μ<0.75時(shí)，采用二叉碰撞跟蹤樹查詢標(biāo)簽，反之采用消除空閑時(shí)隙的動(dòng)態(tài)四叉樹查詢標(biāo)簽。閱讀器查詢標(biāo)簽的結(jié)果僅有碰撞時(shí)隙(分支節(jié)點(diǎn))和識別時(shí)隙(葉子節(jié)點(diǎn))兩種，當(dāng)閱讀器對標(biāo)簽查詢時(shí)可以抽象為對一棵二-四叉樹執(zhí)行遍歷操作，由于本算法消除了空閑時(shí)隙，則分支節(jié)點(diǎn)僅有度為2和4兩種節(jié)點(diǎn)。

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

TAMS=T2-ary+T4-ary

(2)

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

(3)

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

(4)

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

(5)

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

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

(6)

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

(7)

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

(8)

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

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

(9)

3.2 系統(tǒng)吞吐量

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

(10)

4 仿真研究

本文以MATLAB2018a為仿真平臺對PGAMT算法進(jìn)行仿真分析，遵循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ù)、總時(shí)隙數(shù)和系統(tǒng)吞吐量三個(gè)方面的比較。

圖1 四種算法的性能比較

圖2 吞吐量

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

圖2表示PGAMT算法與其它三種算法系統(tǒng)吞吐量之間的比較。從圖中可以看出，PGAMT算法吞吐量明顯高于其它三種算法，最高達(dá)到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算法雖然波動(dòng)幅度較大，但吞吐量明顯高于其它防碰撞算法。

5 總結(jié)

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