基于比特估計(jì)的RFID標(biāo)簽數(shù)量估計(jì)算法*

楊 帆,任守綱,徐煥良,孫元昊,楊 星

(1．江蘇師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,江蘇 徐州 221116；2.南京農(nóng)業(yè)大學(xué)工學(xué)院,江蘇 南京 210031； 3.南京農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院，江蘇 南京 210095)

1 引言

物聯(lián)網(wǎng)是新一代信息技術(shù)的重要組成部分，也是信息化時代的重要發(fā)展階段。無線射頻識別RFID(Radio Frequency IDentification)作為物聯(lián)網(wǎng)感知層關(guān)鍵技術(shù)之一，對物聯(lián)網(wǎng)的發(fā)展起著至關(guān)重要的作用[1]。標(biāo)簽防碰撞算法主要用于解決RFID系統(tǒng)中多標(biāo)簽碰撞問題[2 - 6]，而準(zhǔn)確估計(jì)標(biāo)簽數(shù)量作為提高標(biāo)簽防碰撞算法效率的重要環(huán)節(jié)，吸引了大量研究人員的關(guān)注。目前，標(biāo)簽數(shù)量估計(jì)算法[7 - 22]主要分為2大類，分別為基于幀時隙的標(biāo)簽估計(jì)算法[7 - 18]和基于比特估計(jì)的標(biāo)簽估計(jì)算法[19 - 22]。

基于幀時隙的標(biāo)簽估計(jì)算法又分為2類：1類是固定系數(shù)或經(jīng)驗(yàn)系數(shù)的估計(jì)算法，如Low Bound估計(jì)算法[9]、Schoute 估計(jì)算法[10]和基于空閑時隙估計(jì)算法[11]等。該類算法具有時間復(fù)雜度低的優(yōu)點(diǎn)，但其估計(jì)誤差較大。另1類是根據(jù)區(qū)間最優(yōu)值搜索的估計(jì)算法，如Vgot算法[12]、貝葉斯算法[13,14]和最大后驗(yàn)概率估計(jì)算法[15,16]等。該類算法雖然具有較高的標(biāo)簽估計(jì)精度，但由于其在標(biāo)簽的取值范圍內(nèi)多次求極值，使得算法的計(jì)算復(fù)雜度高。

基于比特的標(biāo)簽估計(jì)算法也可分為2類：1類是基于比特時隙的估計(jì)算法[19,20]，如ART(Average Run based Tag estimation)估計(jì)算法[20]。該類算法將單個時隙內(nèi)的標(biāo)簽回復(fù)量設(shè)定為1個比特，即當(dāng)前時隙有標(biāo)簽選擇，則標(biāo)簽回復(fù)1，否則回復(fù)0，這大大降低了讀寫器和標(biāo)簽之間的通信開銷，但其仍然需要較多時隙來完成標(biāo)簽數(shù)量的估計(jì)。另1類是基于比特字符串的估計(jì)算法[21,22]，如OBTT(Optimal Binary Tracking Tree protocol)算法[22]。該類算法以比特字符串代替時隙，并設(shè)定標(biāo)簽從讀寫器發(fā)布的比特字符串中任意選擇1個比特位設(shè)定為1，其余位設(shè)定為0，然后返回產(chǎn)生的比特字符串。利用曼徹斯特編碼技術(shù)，讀寫器聚合接收到的比特字符串，并統(tǒng)計(jì)聚合后比特字符串中未被標(biāo)簽選擇的比特位個數(shù)，進(jìn)而計(jì)算出比特字符串中的空閑比特率IBR(Idle Bit Rate)，若有IBR≠0,則進(jìn)行標(biāo)簽數(shù)量估計(jì)。

無論是基于幀時隙的標(biāo)簽估計(jì)還是基于比特的標(biāo)簽估計(jì)，從統(tǒng)計(jì)意義上看每個幀時隙狀態(tài)(空閑、成功和碰撞)或字符串的比特位狀態(tài)(選擇和未選擇)都符合二項(xiàng)分布定理。對于文獻(xiàn)[22]中提出的標(biāo)簽估計(jì)算法，盡管在IBR值較大時具有較高的準(zhǔn)確性，但在IBR近似為0時，面臨如下2個問題：

(1)根據(jù)二項(xiàng)分布理論，對于具有不同數(shù)量標(biāo)簽的2組標(biāo)簽群，當(dāng)2者的標(biāo)簽實(shí)際數(shù)量都遠(yuǎn)大于用于標(biāo)簽估計(jì)的比特字符串長度時，比特字符串的空閑比特率仍會出現(xiàn)IBR=1/S的情況，其中S為比特字符串的長度。此時，如何根據(jù)IBR的值精準(zhǔn)估計(jì)這2組標(biāo)簽群內(nèi)標(biāo)簽的實(shí)際數(shù)量？

(2)由于IBR的值與標(biāo)簽實(shí)際數(shù)量n和S的比值密切相關(guān)，在S/n→0的過程中，標(biāo)簽的估計(jì)誤差會出現(xiàn)較大波動，那么是否存在1個非零且非1/S的IBR閾值TIBR(Threshold of Idle Bit Rate),當(dāng)有IBR≥TIBR時，使得標(biāo)簽估計(jì)的誤差率e(2.3節(jié)將給出定義)在任意標(biāo)簽實(shí)際數(shù)量下有e|TIBR,n≤e|1/S,n,且e值的波動較小。

通過對上述2點(diǎn)的分析，本文在文獻(xiàn)[22]的基礎(chǔ)上提出了基于比特估計(jì)的優(yōu)化算法OBE(Optimization of Bit Estimation)。該算法通過引入TIBR取代S-1作為開啟標(biāo)簽估計(jì)的判斷條件，使得標(biāo)簽的估計(jì)誤差大大降低。同時，通過分析不同TIBR在不同標(biāo)簽實(shí)際數(shù)量下的誤差率和時隙消耗的均值和方差，尋找面向不同標(biāo)簽規(guī)模的最優(yōu)TIBR。仿真結(jié)果顯示，OBE算法相比現(xiàn)有的標(biāo)簽估計(jì)算法具有更高的精度，且在不同規(guī)模的標(biāo)簽群上具有更加穩(wěn)定的標(biāo)簽估計(jì)性能。

綜上所述，本文的貢獻(xiàn)總結(jié)如下：

(1)提出了基于比特估計(jì)的優(yōu)化算法。該算法通過引入TIBR解決了文獻(xiàn)[22]中未考慮在IBR近似為0時的問題，在不同稠密度的標(biāo)簽環(huán)境中進(jìn)行仿真實(shí)驗(yàn)，得出了獨(dú)立于標(biāo)簽稠密度的最優(yōu)TIBR值。最終仿真結(jié)果顯示，OBE算法具有更高的標(biāo)簽估計(jì)準(zhǔn)確度。

(2)利用二項(xiàng)分布和容斥原理等理論，對OBE算法中用于標(biāo)簽估計(jì)的時隙消耗進(jìn)行了分析，并給出了OBE算法時隙消耗的數(shù)學(xué)表達(dá)式。

2 OBE算法

相比基于時隙的標(biāo)簽估計(jì)算法，基于比特字符串的估計(jì)算法利用曼徹斯特編碼技術(shù)，通過在1個時隙內(nèi)檢測每個比特位的狀態(tài)而不是在1個識別幀內(nèi)檢測時隙的狀態(tài)來估計(jì)標(biāo)簽的數(shù)量。因此，基于比特字符串的估計(jì)算法可以使用較少的時隙開銷完成對標(biāo)簽數(shù)量的估計(jì)。OBE算法分為2個階段，分別是比特字符串長度調(diào)整和標(biāo)簽數(shù)量估計(jì)。表1給出了本文常用的數(shù)學(xué)符號及說明。

Table 1 Mathematic symbols表1 常用的數(shù)學(xué)符號

2.1 比特字符串長度調(diào)整

利用曼徹斯特編碼技術(shù)，讀寫器分別合并1～L個時隙內(nèi)標(biāo)簽回復(fù)的字符串，以獲得該幀內(nèi)聚合字符串Q={q0,q1,…,qS-1},其中qi={0,1,X}，qi=0表示字符串的第i個比特位未被選擇;qi=1表示第i個比特位只被1個標(biāo)簽選擇，否則表示該比特位被多個標(biāo)簽選擇。如果用qbi表示Q中第i個比特位的選擇狀況，則有：

(1)

Table 2 Adjusting process of bit sequence length in OBE algorithm表 2 OBE算法比特字符串長度的調(diào)整過程

2.2 標(biāo)簽估計(jì)

對于Q中任意比特位被標(biāo)簽選擇和未被選擇的概率分別記為PSB和PNB，則有：

(2)

PSB(n,S)=1-PNB(n,S)

(3)

根據(jù)文獻(xiàn)[3]可知，基于時隙的標(biāo)簽估計(jì)，在任意1個幀中出現(xiàn)空閑時隙的數(shù)量其均值滿足：

E[I]=F×P(n,F)(0)

(4)

其中,I表示空閑時隙的數(shù)量，F(xiàn)表示幀長，P(n,F)(0)表示空閑時隙的概率。

對于Q中未被選擇的比特位數(shù)NNB，結(jié)合式(2)和式(4)有：

(5)

(6)

2.3 參數(shù)的選擇

TIBR是OBE算法的關(guān)鍵參數(shù)，最優(yōu)的TIBR取值不僅可以降低標(biāo)簽估計(jì)的誤差率，還能夠保證在不同規(guī)模的標(biāo)簽群上具有相對穩(wěn)定的標(biāo)簽估計(jì)性能。

為了描述TIBT的取值對于誤差估計(jì)準(zhǔn)確性的影響，本文使用文獻(xiàn)[9]中提到的歸一化估計(jì)誤差函數(shù)δ作為評判標(biāo)準(zhǔn)，其表示如下：

(7)

由于文獻(xiàn)[23]給出了空閑率的最大上限值，本文以此為基礎(chǔ)，設(shè)定TIBR的參數(shù)集TS={0.05,0.1,…,0.35,0.4}，其集合大小u=8,標(biāo)簽實(shí)際數(shù)量的參數(shù)集nS={100,120,140,…,1 980,2 000},其集合大小v=96。同時，定義誤差矩陣EM(Error Matrix)來觀察不同TIBR和n對δ的影響，EM表示如下：

(8)

其中,evu為誤差率，其值為：

evu=δ|TIBT=TS(u),n=nS(v)

(9)

利用OBE算法，以Matlab為仿真工具，在b=96的條件下，分別對不同TS和nS的取值組合進(jìn)行仿真，每種組合迭代200次取均值得到其對應(yīng)的e值和時隙消耗，仿真結(jié)果如圖1所示。從圖1中可發(fā)現(xiàn)，誤差率e與標(biāo)簽實(shí)際數(shù)量n和TIBT均成反比關(guān)系，而時隙消耗數(shù)量o與標(biāo)簽實(shí)際數(shù)量n和TIBT成正比關(guān)系。

Figure 1 Error rate e and slot consumption o under different n and TIBT圖1 不同組合下的誤差率e和時隙消耗數(shù)量o

EM呈現(xiàn)了不同取值組合與誤差率之間的關(guān)系，在相同的標(biāo)簽實(shí)際數(shù)量n下，較大的TIBR具有較小的誤差率，但仍無法確定最優(yōu)的TIBR取值。因此,本文引入誤差率e的均值集合we={we1,we2,…,weu}和標(biāo)準(zhǔn)差集合σe={σe1,σe2,…,σeu}，以及時隙消耗數(shù)量o的均值集合wo={wo1,wo2,…,wou}和標(biāo)準(zhǔn)差集合σo={σo1,σo2,…,σou}，來分析不同TIBR值下標(biāo)簽估計(jì)的誤差率及誤差波動情況，以尋找最優(yōu)TIBR值。該4類參數(shù)計(jì)算方法如式(10)和式(11)所示，結(jié)合圖1中的數(shù)據(jù)集合，其計(jì)算結(jié)果如表3所示。

(10)

(11)

從表3中可清晰地看出，we與TIBT成反比關(guān)系，即TIBT越大，OBE算法的估計(jì)性能越好，這與前面分析的結(jié)果相同。在不同TIBT下，σe的取值出現(xiàn)上下浮動，當(dāng)TIBR=0.35時，σe的值最小，即表明此時OBE算法受標(biāo)簽數(shù)量n的影響最小。wo與TIBT成正比關(guān)系，即TIBT越大，OBE算法所消耗的時隙數(shù)量越多。當(dāng)TIBR=0.35時，σo的值最大，這表明OBE算法可以根據(jù)標(biāo)簽實(shí)際數(shù)量自動調(diào)整時隙消耗數(shù)量。綜上考慮，本文設(shè)定最優(yōu)的TIBT為0.35。

3 OBE算法性能分析

相比基于時隙的標(biāo)簽估計(jì)算法，OBE算法利用比特跟蹤技術(shù)可減少因標(biāo)簽估計(jì)而產(chǎn)生的時隙數(shù)量，故本節(jié)主要分析標(biāo)簽估計(jì)所消耗的時隙數(shù)量。

假設(shè)T表示在標(biāo)簽實(shí)際數(shù)量為n的條件下第i次調(diào)整L時，Q中被選擇比特位的個數(shù)，則有：

(12)

其中,Li=2i-1×L。

以Rx表示在標(biāo)簽實(shí)際數(shù)量為n的條件下第i次調(diào)整L時，Q中第x位未被選擇的所有排列組合形式的集合，則其所有排列組合的數(shù)量為：

(13)

以Rx∩Ry表示在標(biāo)簽數(shù)量為n的條件下第i次調(diào)整L時，Q中第x位和第y位未被選擇的所有排列組合形式，則有：

(14)

根據(jù)容斥原理，并結(jié)合式(12)和式(14)，則對于Q中有T個比特位都被選擇的所有排列組合數(shù)量為：

(15)

在標(biāo)簽實(shí)際數(shù)量為n的條件下第i次調(diào)整L的概率PA(i,n)為：

Table 3 Mean values and standard deviations of error rate and slot consumption under different TIBR表3 不同TIBR下的誤差率和時隙消耗的平均值和方差

(16)

由于當(dāng)n

(17)

以PS(i,n)表示在標(biāo)簽實(shí)際數(shù)量為n的條件,第i-1次調(diào)整L后滿足IBR≥TIBR的概率，則有：

(18)

以H(i)表示第i次調(diào)整L需要的時隙數(shù)量，則有：

(19)

因此，前i次標(biāo)簽估計(jì)消耗時隙的數(shù)量為：

(20)

根據(jù)等式(17)、式(18)和式(20)，則對n個標(biāo)簽估計(jì)所消耗的平均時隙A(n)為：

(21)

4 仿真實(shí)驗(yàn)

本節(jié)利用計(jì)算機(jī)仿真實(shí)驗(yàn)驗(yàn)證所提出的估計(jì)算法的性能。在仿真實(shí)驗(yàn)中，假設(shè)該RFID系統(tǒng)僅有1個讀寫器，標(biāo)簽ID服從均勻分布，所有標(biāo)簽被讀寫器識別的過程中一直處于讀寫器的工作范圍，且在整個識別過程中標(biāo)簽實(shí)際數(shù)量不會發(fā)生改變。同時，假定系統(tǒng)中的信號在信道傳輸和接收的過程中不存在誤碼問題且無捕獲效應(yīng)。標(biāo)簽數(shù)目n設(shè)定為50,55,60,…,2 000。每設(shè)置1次n，實(shí)驗(yàn)重復(fù)200次取平均值。

4.1 標(biāo)簽估計(jì)的誤差率

本節(jié)給出了在不同標(biāo)簽ID長度b下，OBTT算法和OBE算法的估計(jì)誤差率隨標(biāo)簽實(shí)際數(shù)量n的變化曲線圖，如圖2所示。從圖2中可以很明顯地看出，OBE算法的估計(jì)性能明顯優(yōu)于OBTT算法的，且基本不受標(biāo)簽ID長度和標(biāo)簽實(shí)際數(shù)量的影響。在b=64,n≤65和b=96,n≤95時，OBE算法和OBTT算法具有相同的估計(jì)誤差，這是由于此時2者具有相同的IBR值，且都滿足IBR≥TIBR，如圖3a所示。

Figure 2 Error rate of each algorithm under different n圖2 不同標(biāo)簽實(shí)際數(shù)量n下各算法的誤差率

Figure 3 Adjusting process of IBR under different n圖3 不同規(guī)模標(biāo)簽群上IBR的調(diào)整過程

對于不同b值下的OBTT算法誤差率曲線，其每個波峰的出現(xiàn)即代表此時的IBR趨近于0，需要增加時隙調(diào)整S值重新估計(jì)標(biāo)簽數(shù)量，如b=96，n=950時，此時時隙消耗數(shù)量與標(biāo)簽實(shí)際數(shù)量在正無窮方向的某個區(qū)間上一定是單調(diào)遞增的。

隨著標(biāo)簽實(shí)際數(shù)量的不斷增大，OBTT算法的IBR值不斷減小直至IBR=0時才增加時隙調(diào)整S值，而OBE算法根據(jù)TIBR不斷調(diào)整S，使其IBR值始終維持在TIBR以上，如圖3b所示。因此,從仿真結(jié)果中能夠看出，OBTT算法的估計(jì)性能隨著標(biāo)簽實(shí)際數(shù)量的增大而出現(xiàn)下降，而OBE算法的誤差率，基本維持在0.12%左右。

4.2 標(biāo)簽估計(jì)算法的穩(wěn)定性

標(biāo)簽數(shù)量的估計(jì)本質(zhì)上是對1個隨機(jī)過程進(jìn)行估計(jì)，由于其不可避免地會出現(xiàn)隨機(jī)性誤差，所以要求標(biāo)簽估計(jì)算法應(yīng)該具備一定抵抗隨機(jī)性誤差的能力。在不同規(guī)模的標(biāo)簽環(huán)境中，其仍具有準(zhǔn)確的標(biāo)簽估計(jì)性能，這種能力被稱為標(biāo)簽估計(jì)的穩(wěn)定性。本節(jié)通過分析在不同b值下，OBTT算法和OBE算法在標(biāo)簽數(shù)量為50～2 000時估計(jì)誤差率的標(biāo)準(zhǔn)差來分析2種算法的穩(wěn)定性。

從圖4中可以看出，OBE算法的穩(wěn)定性明顯高于OBTT算法的。隨著b值的不斷增大，2種算法的估計(jì)性能趨穩(wěn)定，這是因?yàn)閎值越大，標(biāo)簽可選的比特位置越多，根據(jù)二項(xiàng)分布特性，其出現(xiàn)的空閑比特率也將越大，因此估計(jì)更加準(zhǔn)確。雖然較大的b值可以提高標(biāo)簽估計(jì)精度，同時也會帶來標(biāo)簽成本增加，標(biāo)簽與讀寫器之間的通信開銷增大等問題。

Figure 4 Stability of OBE and OBTT algorithms under different ID lengths圖4 不同ID長度下OBE和OBTT算法的穩(wěn)定性

4.3 標(biāo)簽估計(jì)的時隙消耗

本節(jié)給出了在不同標(biāo)簽ID長度下，OBTT算法和OBE算法的時隙消耗在標(biāo)簽實(shí)際數(shù)量為50～ 2 000時的變化曲線圖，如圖5所示。

Figure 5 Slot consumption of tag number estimation圖5 標(biāo)簽估計(jì)的時隙消耗

從圖5中可以看出，2種算法的時隙消耗數(shù)量均與標(biāo)簽實(shí)際數(shù)量成正比，且OBE算法的時隙消耗量要大于OBTT算法的。這是因?yàn)镺BE算法需要不斷調(diào)整S值的大小，使得IBR≥TIBR。每1次S值的調(diào)整都需要消耗1個時隙，因此OBE算法相比OBTT算法的時隙消耗較高，即OBE算法的標(biāo)簽估計(jì)時間要長于OBTT算法的。

5 結(jié)束語

本文在研究OBTT算法的基礎(chǔ)上，提出了基于比特估計(jì)的OBE算法，該算法針對OBTT算法中使用單個空閑比特位作為開啟標(biāo)簽估計(jì)準(zhǔn)則的缺陷，給出了1種新的開啟標(biāo)簽估計(jì)的準(zhǔn)則，通過引入TIBR參數(shù)用于判定當(dāng)前比特字符串中的空閑比特率情況而決定是否進(jìn)行標(biāo)簽估計(jì)。通過計(jì)算機(jī)數(shù)據(jù)模擬，確定了適用于稠密標(biāo)簽環(huán)境中的最優(yōu)TIBR取值。仿真結(jié)果顯示，與OBTT算法相比，OBE算法的估計(jì)性能要優(yōu)于OBTT算法的，估計(jì)誤差率維持在0.12%，且標(biāo)簽估計(jì)的精度基本不受標(biāo)簽實(shí)際數(shù)量和標(biāo)簽ID長度的影響。

盡管OBE算法具有較高的標(biāo)簽估計(jì)準(zhǔn)確性，對標(biāo)簽進(jìn)行估計(jì)時，由于可選的字符串比特位數(shù)S遠(yuǎn)小于標(biāo)簽實(shí)際數(shù)量n,因此存在IBR遠(yuǎn)小于TIBR的情況，使得讀寫器需要多次發(fā)布調(diào)整L值指令才能準(zhǔn)確估計(jì)出標(biāo)簽的數(shù)量，但這在稠密的標(biāo)簽環(huán)境中，將大大增加標(biāo)簽和讀寫器之間的時隙消耗以及通信開銷，造成相對較長的標(biāo)簽估計(jì)時間。因此，下一步將優(yōu)化OBE算法中標(biāo)簽與讀寫器之間的數(shù)據(jù)交換機(jī)制，降低2者之間的通信開銷，使之能夠應(yīng)用于實(shí)際的RFID系統(tǒng)當(dāng)中。