基于偽ID碼的樹型防碰撞算法

王 帥,楊恒新,楊 華

(南京郵電大學(xué) 電子與光學(xué)工程學(xué)院,南京 210023)

0 概述

無線射頻識(shí)別(Radio Frequency Identification,RFID)是一種遠(yuǎn)距離識(shí)別技術(shù)[1],它主要通過空間耦合技術(shù)使閱讀器和標(biāo)簽進(jìn)行遠(yuǎn)程通信[2-4]。隨著5G時(shí)代的到來,物聯(lián)網(wǎng)的應(yīng)用將更加廣泛,而作為物聯(lián)網(wǎng)核心技術(shù)之一的RFID技術(shù)也引起了人們更多的關(guān)注[5]。

RFID系統(tǒng)主要由閱讀器、標(biāo)簽、計(jì)算機(jī)組成[6]。計(jì)算機(jī)通過控制閱讀器與標(biāo)簽進(jìn)行通信。在RFID系統(tǒng)中最主要的問題就是標(biāo)簽碰撞問題。當(dāng)閱讀器的識(shí)別區(qū)域內(nèi)同時(shí)出現(xiàn)大量未識(shí)別標(biāo)簽時(shí),閱讀器發(fā)出查詢指令,所有未識(shí)別標(biāo)簽同時(shí)回應(yīng),此時(shí)會(huì)發(fā)生數(shù)據(jù)碰撞,導(dǎo)致閱讀器無法對(duì)標(biāo)簽進(jìn)行正常識(shí)別[7]。針對(duì)這一問題,人們提出基于時(shí)分多路(Time Division Multiple Access,TDMA)、頻分多路(Frequency Division Multiple Access,FDMA)、空分多路(Space Division Multiple Access,SDMA)和碼分多路(Code Division Multiple Access,CDMA)等4種方式的防碰撞算法[8-9],其中應(yīng)用最多的是時(shí)分多路的防碰撞算法。

時(shí)分多路(TDMA)防碰撞算法中的典型算法主要分為基于ALOHA的概率型算法和基于樹的概率型算法。基于ALOHA的概率型算法主要有幀時(shí)隙(FSA)算法和動(dòng)態(tài)幀時(shí)隙(DFSA)算法等[10-11],ALOHA算法簡(jiǎn)單,但吞吐率都不高?；跇涞母怕市退惴ㄖ饕袆?dòng)態(tài)二進(jìn)制搜索(DBST)算法[12-13]和碰撞跟蹤樹(CTT)算法等[14-15]。樹型算法雖然比較復(fù)雜,但吞吐率較ALOHA型算法高。文獻(xiàn)[16]提出一種基于查詢樹(QT)算法的混合查詢樹(IHQT)算法,在查詢標(biāo)簽碰撞時(shí),增加一個(gè)分支預(yù)測(cè)階段,雖然可以有效避免空閑時(shí)隙,但大大增加了系統(tǒng)的復(fù)雜度。文獻(xiàn)[2]提出一種位屏蔽多叉樹搜索的防碰撞算法,主要通過屏蔽寄存器將標(biāo)簽ID中的非碰撞位進(jìn)行屏蔽,用碰撞位生成新的ID號(hào),從而避免空閑時(shí)隙,減少數(shù)據(jù)通信量,但在大規(guī)模標(biāo)簽識(shí)別時(shí),同樣會(huì)有樹的深度過深導(dǎo)致吞吐率下降的問題。文獻(xiàn)[17]提出一種改進(jìn)的搜索樹防碰撞算法,在標(biāo)簽數(shù)量多時(shí)使用多叉樹進(jìn)行識(shí)別,標(biāo)簽數(shù)量少時(shí)使用二叉樹進(jìn)行識(shí)別。該方法雖然可以減少部分空閑時(shí)隙,但不能完全避免。

在樹類算法中,CTT算法[18]雖然避免了空閑時(shí)隙,但由于在標(biāo)簽數(shù)量多的情況下查詢樹的深度過深,導(dǎo)致算法吞吐率下降。針對(duì)這一問題,本文提出一種基于偽ID碼的樹型防碰撞算法,主要通過偽ID碼對(duì)標(biāo)簽進(jìn)行劃分,從而降低樹的深度,提高算法的識(shí)別效率。

1 碰撞跟蹤樹算法

碰撞跟蹤樹(Collision Tracking Tree,CTT)算法的核心思想是在查詢樹(QT)算法的基礎(chǔ)上,根據(jù)曼徹斯特碼檢測(cè)到的碰撞,將最高碰撞位之前的信息加上最高碰撞位置0或1組成新的查詢前綴,從而可以避免空閑時(shí)隙。

以標(biāo)簽0110、0101、0111、1010、1000為例,其識(shí)別過程如圖1所示。

圖1 CTT算法流程Fig.1 CTT algorithm processdure

從圖1可以看出,CTT算法在查詢上述5個(gè)標(biāo)簽時(shí),沒有產(chǎn)生空閑時(shí)隙。

假設(shè)識(shí)別區(qū)域內(nèi)未識(shí)別標(biāo)簽數(shù)為n,內(nèi)部結(jié)點(diǎn)數(shù)為tc,葉結(jié)點(diǎn)數(shù)為ts,總時(shí)隙數(shù)為N,則:

N=2(tc+1)+1

(1)

N=ts+tc+1

(2)

由于CTT算法不會(huì)產(chǎn)生空閑時(shí)隙,因此:

n=ts

(3)

由式(1)～式(3)可得:

N=2n-1

(4)

因此,算法的吞吐率為:

(5)

從吞吐率公式可以看出,當(dāng)標(biāo)簽數(shù)量越來越多時(shí),算法的吞吐率越低,則標(biāo)簽的識(shí)別速度越慢。

2 樹型防碰撞算法

針對(duì)CTT算法中隨著標(biāo)簽數(shù)量越多,吞吐率越低的問題,本文提出了偽ID碼的概念,其主要是將標(biāo)簽通過偽ID碼進(jìn)行重新劃分,使每個(gè)偽ID碼只有一個(gè)或幾個(gè)標(biāo)簽,然后根據(jù)CTT算法進(jìn)行識(shí)別,從而提高算法的識(shí)別效率。

2.1 偽ID碼

每個(gè)標(biāo)簽在偽ID碼的范圍內(nèi)進(jìn)行隨機(jī)選取,令偽ID碼的個(gè)數(shù)為L(zhǎng),識(shí)別范圍內(nèi)未識(shí)別標(biāo)簽的數(shù)量為n,則在單個(gè)偽ID碼中,有t個(gè)標(biāo)簽同時(shí)選中的概率為:

(6)

當(dāng)t=0時(shí),即單個(gè)偽ID碼沒有標(biāo)簽選中,稱為空ID碼,其概率為:

(7)

當(dāng)t=1時(shí),即單個(gè)偽ID碼只有1個(gè)標(biāo)簽選中,稱為成功ID碼,其概率為:

(8)

當(dāng)t≥2時(shí),即單個(gè)偽ID碼有多個(gè)標(biāo)簽選中,稱為碰撞ID碼,其概率為:

P(t≥2)=1-P(t=0)-P(t=1)

(9)

因此,在L個(gè)偽ID碼中,空偽ID碼的期望為:

(10)

成功偽ID碼的期望為:

(11)

碰撞偽ID碼的期望為:

e≥2=L-e0-e1

(12)

令:

(13)

對(duì)式(1)求導(dǎo),取極值后得:

L≈n+1

(14)

即當(dāng)上式成立時(shí),偽ID碼中成功ID碼的數(shù)量最多,識(shí)別成功ID碼,無需CTT算法,可以直接進(jìn)行識(shí)別。

為計(jì)算方便,令L≈n,此時(shí)在碰撞位ID碼中:

(15)

(16)

(17)

圖2給出了標(biāo)簽數(shù)(n)取不同值時(shí),碰撞位ID碼中不同標(biāo)簽數(shù)量的概率(P)值。

圖2 碰撞位的概率值Fig.2 Probability value of collision position

從圖2可以看出,隨著標(biāo)簽數(shù)量的增加,P(t=2)穩(wěn)定在0.18,P(t=3)穩(wěn)定在0.06,P(t=4)基本為0。因此,當(dāng)L≈n時(shí),每個(gè)偽ID碼中最多包含3個(gè)標(biāo)簽,此時(shí)應(yīng)用CTT算法,算法吞吐率最高。

2.2 標(biāo)簽數(shù)量預(yù)測(cè)

目前研究人員已經(jīng)提出了多種標(biāo)簽數(shù)量預(yù)測(cè)方法,如Vogt算法、Chen’s算法、Vahedi’s算法、Q算法等[19-20]。上述算法計(jì)算都比較復(fù)雜,本文采取一種簡(jiǎn)單的基于泊松分布的標(biāo)簽數(shù)量預(yù)測(cè)方法為[21]:

n′=S+2.39×C

(18)

假設(shè)未識(shí)別標(biāo)簽數(shù)n′應(yīng)用成功數(shù)S與碰撞數(shù)C的2.39倍之和來加以預(yù)測(cè)。

標(biāo)簽預(yù)測(cè)的具體步驟如下:

步驟1閱讀器向識(shí)別區(qū)域內(nèi)的所有標(biāo)簽發(fā)送Q,Q的初始值設(shè)為8。

步驟2標(biāo)簽在接收到Q值后,利用隨機(jī)數(shù)生成器,在1～2Q中隨機(jī)選擇一個(gè)數(shù),進(jìn)行相應(yīng)的短暫延時(shí),然后向閱讀器發(fā)送一個(gè)非常短的長(zhǎng)度為2 bit的預(yù)約幀。

步驟4根據(jù)n′=S+2.39×C,計(jì)算出識(shí)別范圍內(nèi)標(biāo)簽的大概數(shù)量。

2.3 算法主體流程

算法首先由標(biāo)簽預(yù)測(cè)算法識(shí)別出識(shí)別范圍內(nèi)標(biāo)簽的大概數(shù)量,然后由偽ID碼進(jìn)行劃分,如果識(shí)別過程中發(fā)生碰撞,就通過CTT算法進(jìn)行識(shí)別,直到識(shí)別范圍內(nèi)的所有標(biāo)簽都識(shí)別完畢。

步驟1閱讀器通過標(biāo)簽預(yù)測(cè)算法,得到識(shí)別區(qū)域內(nèi)未識(shí)別標(biāo)簽的大概數(shù)量n。

步驟2閱讀器向標(biāo)簽發(fā)送n。標(biāo)簽在接收到n后,利用隨機(jī)數(shù)生成器隨機(jī)產(chǎn)生1～n內(nèi)的任意一個(gè)數(shù)作為自己的偽ID碼,同時(shí),閱讀器設(shè)立初始值為0的變量i,變量i用于判斷是否識(shí)別完所有的偽ID碼。

步驟3若i≤n,則轉(zhuǎn)到步驟4;否則,結(jié)束算法,所有標(biāo)簽識(shí)別完畢。

步驟4閱讀器向標(biāo)簽發(fā)送i。標(biāo)簽在接收到i后,判斷自己的偽ID碼是否與i相等,如果相等則進(jìn)行回應(yīng)。

步驟5閱讀器在相應(yīng)的時(shí)間內(nèi)判斷是否有標(biāo)簽進(jìn)行回應(yīng)。若沒有,則i=i+1,轉(zhuǎn)到步驟3;否則繼續(xù)執(zhí)行步驟6。

步驟6閱讀器判斷標(biāo)簽回應(yīng)的數(shù)據(jù)是否發(fā)送碰撞。若有則利用CTT算法進(jìn)行識(shí)別,并向識(shí)別完成的標(biāo)簽發(fā)送靜默指令;否則直接識(shí)別回應(yīng)的標(biāo)簽,識(shí)別完成后,向其發(fā)送靜默指令。最后執(zhí)行i=i+1,轉(zhuǎn)到步驟3。

算法流程如圖3所示。

圖3 樹型防碰撞算法主體流程Fig.3 Main procedure of the tree auti-collision algorithm

3 性能分析

3.1 閱讀器查詢次數(shù)分析

在算法實(shí)現(xiàn)過程中,閱讀器主要通過偽ID碼和碰撞時(shí)的CTT算法進(jìn)行查詢,則閱讀器總查詢次數(shù)Q的表達(dá)式為:

Q=QID+QCTT

(19)

若ID碼的個(gè)數(shù)為L(zhǎng),則:

QID=L

(20)

由式(4)可知,CTT算法的查詢次數(shù)為N=2n-1。但是在本文算法中,由于在發(fā)送碰撞時(shí),已經(jīng)檢測(cè)出了碰撞位,因此本文算法中CTT算法的實(shí)際查詢次數(shù)為N=2n-2。

本文算法中CTT算法的總查詢次數(shù)為:

QCTT=L×P(t=2)×(2×2-2)+L×P(t=3)×

(2×3-3)+L×P(t=4)×(2×4-3)

(21)

在式(21)中,本應(yīng)計(jì)算P(t=5)、P(t=6)等,但因?yàn)槠渲堤?同時(shí)為了書寫方便,將其省略。

將式(20)、式(21)代入式(19),得:

Q=L+L×P(t=2)×2+L×P(t=3)×3+L×P(t=4)×5

(22)

同時(shí),每個(gè)標(biāo)簽的平均查詢次數(shù)為:

(23)

3.2 吞吐率分析

算法的吞吐率S的表達(dá)式為:

(24)

4 仿真結(jié)果與分析

本文將改進(jìn)算法、CTT算法、QT算法在吞吐率、閱讀器總查詢次數(shù)、標(biāo)簽平均查詢次數(shù)3個(gè)方面進(jìn)行比較,算法仿真在Matlab平臺(tái)上進(jìn)行運(yùn)行。采用蒙特卡洛仿真方法進(jìn)行仿真,仿真參數(shù)如表1所示。算法仿真結(jié)果如圖4～圖6所示。

表1 仿真參數(shù)設(shè)置Table 1 Simulation parameter settings

圖4 3種算法閱讀器總查詢次數(shù)比較Fig.4 Comparison of total query number of readersof three algorithms

圖5 3種算法標(biāo)簽平均查詢次數(shù)比較Fig.5 Comparison of average query number of tagsof three algorithms

圖6 3種算法吞吐率比較Fig.6 Comparison of throughput rates of three algorithms

圖4是3種算法的閱讀器總查詢次數(shù)的比較結(jié)果。在同樣標(biāo)簽數(shù)的情況下,本文改進(jìn)算法所需的總查詢次數(shù)最少,QT算法的總查詢次數(shù)最多。這是因?yàn)镃TT算法在QT算法的基礎(chǔ)上引入了曼徹斯特碼碰撞檢測(cè),消除了空閑時(shí)隙,而本文改進(jìn)算法則利用偽ID碼機(jī)制,避免了CTT生成樹過深的問題,進(jìn)一步減少了查詢次數(shù)。但標(biāo)簽數(shù)量為1 000時(shí),QT算法的總查詢次數(shù)為3 110,CTT算法的總查詢次數(shù)為2 013,改進(jìn)算法的總查詢次數(shù)為1 684,因此改進(jìn)算法的總查詢次數(shù)相比CTT算法、QT算法分別減少了16%和45%。

圖5是3種算法的標(biāo)簽平均查詢次數(shù)的比較結(jié)果。QT算法隨著標(biāo)簽數(shù)量的增加,其平均查詢次數(shù)逐漸減少,逐漸穩(wěn)定在2.9左右,而CTT算法由于避免了空閑時(shí)隙,一直平穩(wěn)在2.0上,改進(jìn)算法由于減少了樹的深度,其標(biāo)簽的平均查詢次數(shù),隨著標(biāo)簽數(shù)的增多,也一直維持在1.65上。因此,改進(jìn)算法的標(biāo)簽平均查詢次數(shù)相比CTT算法、QT算法分別減少了17%和43%。

圖6是3種算法的吞吐率比較結(jié)果。由圖6可見,改進(jìn)算法的吞吐率比CTT算法、QT算法的吞吐率都要高。改進(jìn)算法的吞吐率主要維持在0.575,CTT算法的吞吐率主要維持在0.5,而QT算法的吞吐率主要維持在0.33左右。因此,改進(jìn)算法的吞吐率相比于CTT算法、QT算法分別提高了15%和74%。

5 結(jié)束語

本文在CTT算法的基礎(chǔ)上提出一種基于偽ID碼的樹型防碰撞算法。利用偽ID劃分未識(shí)別標(biāo)簽,然后運(yùn)用CTT算法進(jìn)行識(shí)別。通過該方法可以將樹型算法查詢標(biāo)簽的數(shù)量控制在3個(gè)以內(nèi),雖然偽ID碼會(huì)產(chǎn)生部分空閑時(shí)隙,但在成功時(shí)隙中可以直接識(shí)別標(biāo)簽,而不需要利用樹型算法進(jìn)行查詢,降低了算法的復(fù)雜度。仿真結(jié)果表明,改進(jìn)算法在總查詢次數(shù)、標(biāo)簽平均查詢次數(shù)和吞吐率方面均優(yōu)于CTT算法和QT算法。在實(shí)際應(yīng)用過程中,可以大致預(yù)測(cè)出閱讀器識(shí)別范圍內(nèi)的未識(shí)別標(biāo)簽數(shù)量,因此本文算法具備實(shí)際的應(yīng)用價(jià)值。