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

王 帥,楊恒新,楊 華

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

0 概述

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

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

時分多路(TDMA)防碰撞算法中的典型算法主要分為基于ALOHA的概率型算法和基于樹的概率型算法。基于ALOHA的概率型算法主要有幀時隙(FSA)算法和動態幀時隙(DFSA)算法等[10-11],ALOHA算法簡單,但吞吐率都不高。基于樹的概率型算法主要有動態二進制搜索(DBST)算法[12-13]和碰撞跟蹤樹(CTT)算法等[14-15]。樹型算法雖然比較復雜,但吞吐率較ALOHA型算法高。文獻[16]提出一種基于查詢樹(QT)算法的混合查詢樹(IHQT)算法,在查詢標簽碰撞時,增加一個分支預測階段,雖然可以有效避免空閑時隙,但大大增加了系統的復雜度。文獻[2]提出一種位屏蔽多叉樹搜索的防碰撞算法,主要通過屏蔽寄存器將標簽ID中的非碰撞位進行屏蔽,用碰撞位生成新的ID號,從而避免空閑時隙,減少數據通信量,但在大規模標簽識別時,同樣會有樹的深度過深導致吞吐率下降的問題。文獻[17]提出一種改進的搜索樹防碰撞算法,在標簽數量多時使用多叉樹進行識別,標簽數量少時使用二叉樹進行識別。該方法雖然可以減少部分空閑時隙,但不能完全避免。

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

1 碰撞跟蹤樹算法

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

以標簽0110、0101、0111、1010、1000為例,其識別過程如圖1所示。

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

從圖1可以看出,CTT算法在查詢上述5個標簽時,沒有產生空閑時隙。

假設識別區域內未識別標簽數為n,內部結點數為tc,葉結點數為ts,總時隙數為N,則:

N=2(tc+1)+1

(1)

N=ts+tc+1

(2)

由于CTT算法不會產生空閑時隙,因此:

n=ts

(3)

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

N=2n-1

(4)

因此,算法的吞吐率為:

(5)

從吞吐率公式可以看出,當標簽數量越來越多時,算法的吞吐率越低,則標簽的識別速度越慢。

2 樹型防碰撞算法

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

2.1 偽ID碼

每個標簽在偽ID碼的范圍內進行隨機選取,令偽ID碼的個數為L,識別范圍內未識別標簽的數量為n,則在單個偽ID碼中,有t個標簽同時選中的概率為:

(6)

當t=0時,即單個偽ID碼沒有標簽選中,稱為空ID碼,其概率為:

(7)

當t=1時,即單個偽ID碼只有1個標簽選中,稱為成功ID碼,其概率為:

(8)

當t≥2時,即單個偽ID碼有多個標簽選中,稱為碰撞ID碼,其概率為:

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

(9)

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

(10)

成功偽ID碼的期望為:

(11)

碰撞偽ID碼的期望為:

e≥2=L-e0-e1

(12)

令:

(13)

對式(1)求導,取極值后得:

L≈n+1

(14)

即當上式成立時,偽ID碼中成功ID碼的數量最多,識別成功ID碼,無需CTT算法,可以直接進行識別。

為計算方便,令L≈n,此時在碰撞位ID碼中:

(15)

(16)

(17)

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

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

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

2.2 標簽數量預測

目前研究人員已經提出了多種標簽數量預測方法,如Vogt算法、Chen’s算法、Vahedi’s算法、Q算法等[19-20]。上述算法計算都比較復雜,本文采取一種簡單的基于泊松分布的標簽數量預測方法為[21]:

n′=S+2.39×C

(18)

假設未識別標簽數n′應用成功數S與碰撞數C的2.39倍之和來加以預測。

標簽預測的具體步驟如下:

步驟1閱讀器向識別區域內的所有標簽發送Q,Q的初始值設為8。

步驟2標簽在接收到Q值后,利用隨機數生成器,在1～2Q中隨機選擇一個數,進行相應的短暫延時,然后向閱讀器發送一個非常短的長度為2 bit的預約幀。

步驟4根據n′=S+2.39×C,計算出識別范圍內標簽的大概數量。

2.3 算法主體流程

算法首先由標簽預測算法識別出識別范圍內標簽的大概數量,然后由偽ID碼進行劃分,如果識別過程中發生碰撞,就通過CTT算法進行識別,直到識別范圍內的所有標簽都識別完畢。

步驟1閱讀器通過標簽預測算法,得到識別區域內未識別標簽的大概數量n。

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

步驟3若i≤n,則轉到步驟4;否則,結束算法,所有標簽識別完畢。

步驟4閱讀器向標簽發送i。標簽在接收到i后,判斷自己的偽ID碼是否與i相等,如果相等則進行回應。

步驟5閱讀器在相應的時間內判斷是否有標簽進行回應。若沒有,則i=i+1,轉到步驟3;否則繼續執行步驟6。

步驟6閱讀器判斷標簽回應的數據是否發送碰撞。若有則利用CTT算法進行識別,并向識別完成的標簽發送靜默指令;否則直接識別回應的標簽,識別完成后,向其發送靜默指令。最后執行i=i+1,轉到步驟3。

算法流程如圖3所示。

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

3 性能分析

3.1 閱讀器查詢次數分析

在算法實現過程中,閱讀器主要通過偽ID碼和碰撞時的CTT算法進行查詢,則閱讀器總查詢次數Q的表達式為:

Q=QID+QCTT

(19)

若ID碼的個數為L,則:

QID=L

(20)

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

本文算法中CTT算法的總查詢次數為:

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

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

(21)

在式(21)中,本應計算P(t=5)、P(t=6)等,但因為其值太小,同時為了書寫方便,將其省略。

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

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

(22)

同時,每個標簽的平均查詢次數為:

(23)

3.2 吞吐率分析

算法的吞吐率S的表達式為:

(24)

4 仿真結果與分析

本文將改進算法、CTT算法、QT算法在吞吐率、閱讀器總查詢次數、標簽平均查詢次數3個方面進行比較,算法仿真在Matlab平臺上進行運行。采用蒙特卡洛仿真方法進行仿真,仿真參數如表1所示。算法仿真結果如圖4～圖6所示。

表1 仿真參數設置Table 1 Simulation parameter settings

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

圖5 3種算法標簽平均查詢次數比較Fig.5 Comparison of average query number of tagsof three algorithms

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

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

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

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

5 結束語

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