王 帥, 楊曉東

(河南理工大學(xué) 電氣工程與自動化學(xué)院，河南 焦作 454000)(*通信作者電子郵箱wangs2680@163.com)

0 引言

射頻識別(Radio Frequency IDentification, RFID)技術(shù)是構(gòu)建物聯(lián)網(wǎng)應(yīng)用的基礎(chǔ)，與傳統(tǒng)條形碼技術(shù)相比，具有應(yīng)用靈活、通信距離遠(yuǎn)、穿透性強(qiáng)和存儲容量大等優(yōu)點(diǎn)，目前已廣泛用于物流、工農(nóng)業(yè)生產(chǎn)和自動控制領(lǐng)域，在物體識別、產(chǎn)品管理和過程控制等方面發(fā)揮了巨大作用。RFID系統(tǒng)由讀寫器和標(biāo)簽構(gòu)成，由讀寫器發(fā)出查詢命令，處于讀寫器識別范圍內(nèi)的標(biāo)簽響應(yīng)該命令并返回相應(yīng)信息。目前應(yīng)用的大多數(shù)標(biāo)簽為低成本的無源標(biāo)簽。無源標(biāo)簽從接收的讀寫器信號中獲取能量，結(jié)構(gòu)簡單，但不具備信道監(jiān)聽能力，因此當(dāng)多個標(biāo)簽同時處于讀寫器識別范圍內(nèi)時，讀寫器發(fā)出查詢命令后，可能會有兩個或兩個以上的標(biāo)簽同時作出應(yīng)答，這種情況稱之為碰撞，產(chǎn)生碰撞后讀寫器將無法獲取正確的標(biāo)簽信息。如果待識別的標(biāo)簽數(shù)量較多，頻繁的碰撞將大幅降低標(biāo)簽讀取成功率，需要設(shè)計(jì)有效的防碰撞算法提高識別效率[1-2]。在標(biāo)簽識別過程中防碰撞算法要根據(jù)待識別標(biāo)簽數(shù)量的變化進(jìn)行參數(shù)調(diào)整和優(yōu)化，因此標(biāo)簽數(shù)量估計(jì)是防碰撞算法設(shè)計(jì)的重要內(nèi)容[3-6]。

本文針對目前標(biāo)簽數(shù)量估計(jì)算法中高精度算法復(fù)雜度較高，而低復(fù)雜度算法精度又難以滿足實(shí)際要求的現(xiàn)狀，提出了一種基于序貫線性貝葉斯的標(biāo)簽數(shù)量估計(jì)方法。該方法利用線性貝葉斯理論，將標(biāo)簽數(shù)量估計(jì)問題轉(zhuǎn)化為線性模型，在充分利用觀測信息保證估計(jì)精度的同時，通過線性擬合顯著降低了算法復(fù)雜度，提高了估計(jì)方法的實(shí)用性。

1 相關(guān)工作

目前基于ALOHA的防碰撞算法廣泛用于UHF(Ultra High Frequency)頻段的標(biāo)簽，其中以動態(tài)幀時隙ALOHA(Dynamic Frame Slotted-ALOHA，DFSA)應(yīng)用較為普及。在DFSA算法中，多個時隙組成一幀，讀寫器通過Query命令啟動一幀的開始，標(biāo)簽在一幀內(nèi)隨機(jī)選擇一個時隙發(fā)送數(shù)據(jù)。當(dāng)前幀被成功識別的標(biāo)簽不參與下一幀的競爭，直至收到新的Query命令。采用這種方式，隨著識別過程的進(jìn)行，標(biāo)簽數(shù)量越來越少，直至所有標(biāo)簽被識別為止。在DFSA算法中，標(biāo)簽數(shù)量估計(jì)是決定算法性能的重要環(huán)節(jié)，DFSA算法需要根據(jù)估計(jì)的標(biāo)簽數(shù)量決定每一幀的長度。幀長和標(biāo)簽數(shù)量的差異對識別效率有著直接的影響:當(dāng)幀長大于標(biāo)簽數(shù)量時，會產(chǎn)生過多的空閑時隙; 反之，當(dāng)幀長小于標(biāo)簽數(shù)量時，碰撞時隙數(shù)會增多。理論上已經(jīng)證明，當(dāng)幀長與標(biāo)簽數(shù)量相等時，吞吐率可以達(dá)到最大[7]，因此標(biāo)簽數(shù)量估計(jì)的準(zhǔn)確性是影響DFSA算法性能的重要因素。

目前的標(biāo)簽數(shù)量估計(jì)算法主要有兩大類: 一種是采用固定因子或經(jīng)驗(yàn)系數(shù)的估計(jì)方法[8-9]，該類算法具有復(fù)雜度小的優(yōu)點(diǎn)，但估計(jì)誤差較大; 另一種是根據(jù)設(shè)定的目標(biāo)函數(shù)進(jìn)行最優(yōu)值搜索[10-11]，這類方法估計(jì)精度較高，但大范圍的搜索也導(dǎo)致計(jì)算復(fù)雜度大，實(shí)用中受到很大局限。

(1)

其中:Si為成功時隙數(shù)量，Ci為碰撞時隙數(shù)量，L為幀長，k為固定系數(shù)，文中根據(jù)碰撞時隙所含的平均標(biāo)簽數(shù)量將其設(shè)為2.39。該算法的不足是以標(biāo)簽選擇時隙概率服從泊松分布為假設(shè)條件，但實(shí)際中該假設(shè)并不嚴(yán)格成立，且當(dāng)標(biāo)簽數(shù)量較多時算法誤差較大。

文獻(xiàn)[9]提出基于累計(jì)因子的標(biāo)簽數(shù)量估計(jì)算法，讀寫器接收第i幀后，根據(jù)上一幀估計(jì)的標(biāo)簽數(shù)量ni和累計(jì)因子d計(jì)算當(dāng)前幀的標(biāo)簽數(shù)量ni+1：

ni+1=ni+d(2m+1-2m)

(2)

(3)

其中:m=「lbni?，d為累計(jì)因子，E、S和C分別為成功時隙、空閑時隙和碰撞時隙的數(shù)量，E0、S0和C0分別為相應(yīng)時隙數(shù)量的期望值。該方法的局限是對標(biāo)簽數(shù)量初始值敏感，如果標(biāo)簽數(shù)量初始值與真實(shí)值差距較大，則需要多個幀的識別才能使標(biāo)簽數(shù)量估計(jì)值接近真實(shí)值，降低了識別效率。

基于最大后驗(yàn)概率的估計(jì)算法由文獻(xiàn)[10]提出。該方法利用E、S和C計(jì)算后驗(yàn)概率：

(4)

其中:NS(n,S)為n個標(biāo)簽分配到S個時隙的分法數(shù)量，NC(n,S,C)為n-S個標(biāo)簽分配到C個時隙的分法數(shù)量。該算法通過搜索找出能使式(4)最大的n作為估計(jì)值。該方法雖然充分利用成功時隙、空閑時隙和碰撞時隙數(shù)量的信息，提高了估計(jì)精度，但估計(jì)值需要在較大范圍內(nèi)搜索才能求出，計(jì)算復(fù)雜度較高。

文獻(xiàn)[11]提出了基于馬氏距離的估計(jì)算法，首先計(jì)算成功時隙數(shù)量X1、空閑時隙數(shù)量X2和碰撞時隙數(shù)量X3與對應(yīng)期望值間的馬氏距離，然后選擇使該距離D最短的標(biāo)簽數(shù)量作為估計(jì)值：

(5)

其中:X=(X1,X2,X3)，E[X]和C分別為X的期望值向量和相關(guān)矩陣。該方法將各類型時隙數(shù)量間的相關(guān)性考慮在內(nèi)，當(dāng)標(biāo)簽數(shù)量較大時估計(jì)值仍能保持較高的準(zhǔn)確性，其缺點(diǎn)仍然是需要較大范圍的窮舉搜索，所需計(jì)算量較大，對硬件資源有較高的要求。

除以上算法外，研究者們還對一些特定場景的標(biāo)簽數(shù)量估計(jì)問題作了相關(guān)研究。如文獻(xiàn)[12]研究了針對多個標(biāo)簽集合的組合數(shù)量估計(jì)問題，由分布于不同區(qū)域的多個讀寫器協(xié)同工作，通過數(shù)據(jù)融合算法統(tǒng)計(jì)滿足指定條件的標(biāo)簽數(shù)量。該方法可以滿足不同限定條件下的標(biāo)簽數(shù)量估計(jì)需求，但需要多讀寫器間的通信聯(lián)絡(luò)，且算法需要計(jì)算量較大的最優(yōu)值搜索，對硬件要求較高；文獻(xiàn)[13]給出一種ART (Average Run-based Tag estimation)算法，該算法通過分析連續(xù)非空時隙個數(shù)與標(biāo)簽數(shù)量的關(guān)系，推導(dǎo)出標(biāo)簽數(shù)量估計(jì)的解析表達(dá)式,利用較少的觀測信息獲得較高精度的估計(jì)值，提高了估計(jì)效率，但估計(jì)式需要復(fù)雜的數(shù)值求解，仍存在運(yùn)算量大的問題。

以上所列算法中，基于固定因子的解析式算法復(fù)雜度較小，但對標(biāo)簽數(shù)量變化的適應(yīng)能力較弱，當(dāng)標(biāo)簽數(shù)量較多時估計(jì)精度難以滿足要求?；谧顑?yōu)值搜索的算法精度較高，在標(biāo)簽數(shù)量較寬的變化范圍內(nèi)均能達(dá)到較高的精度，但運(yùn)算律較大，在應(yīng)用中受到硬件條件的制約。針對現(xiàn)有算法存在的問題，本文利用線性貝葉斯理論推導(dǎo)出標(biāo)簽數(shù)量的線性估計(jì)式，估計(jì)式中的待定系數(shù)通過計(jì)算量較低的序貫方式求出。該方法以解析形式給出標(biāo)簽數(shù)量估計(jì)的最優(yōu)解，避免了消耗大量資源的窮舉搜索，同時通過待定系數(shù)的實(shí)時更新提高了對標(biāo)簽數(shù)量變化的適應(yīng)能力，提高了算法的實(shí)用價值。

2 標(biāo)簽數(shù)量估計(jì)問題建模

(6)

設(shè)每個時隙為空閑、成功和碰撞的概率為p1、p2和p3，根據(jù)式(6)可得:

p1=B(0)=(1-1/L)n

(7)

(8)

p3=1-p1-p2

(9)

(10)

式中:a1、a2、a3和a4是待定系數(shù)。為了降低算法復(fù)雜度，可根據(jù)待求問題的特點(diǎn)作進(jìn)一步簡化。首先，由于M1為空閑時隙個數(shù)，空閑時隙不含標(biāo)簽，因此可忽略其對標(biāo)簽數(shù)量的貢獻(xiàn)，將a1設(shè)為0。其次，由于每個成功時隙僅含一個標(biāo)簽，可以將a2設(shè)為1。綜合以上，由于M3=Lob-M2-M1，令a=a3，a0=a4+a3Lob，可以將式(10)簡化為以下形式：

(11)

這樣經(jīng)過簡化后，標(biāo)簽數(shù)量估計(jì)值只與M1、M2有關(guān)，且僅有2個待定系數(shù)a和a0。

問題1 對于式(11)的線性估計(jì)模型，問題的目標(biāo)是選擇a和a0以最小化下面的MMSE函數(shù)：

(12)

式中E[·]是求數(shù)學(xué)期望的運(yùn)算。

一般來說，標(biāo)簽數(shù)量與觀測的M1、M2和M3呈非線性關(guān)系，采用線性模型會產(chǎn)生估計(jì)精度上的損失，但收益則是運(yùn)算復(fù)雜度上的大幅降低。當(dāng)一個幀中的碰撞時隙數(shù)量比例不是很大時，線性模型可以實(shí)現(xiàn)較好的近似。

綜合式(11)、(12)，可以得到計(jì)算標(biāo)簽估計(jì)值的定理1。

定理1 對于由式(11)給出的標(biāo)簽估計(jì)值與空閑、成功和碰撞時隙個數(shù)的線性模型，通過求解問題1可獲得該式中的待定系數(shù)a和a0為：

a0=E[n]-(-aE[M1]+(1-a)E[M2])

(13)

(14)

其中:M=(M1,M2)，Τ1=-(1,1)，Τ2=(0,1)，CMM是M的2×2協(xié)方差矩陣，CnM是n和M的1×2互協(xié)方差矢量。

證明

根據(jù)問題1的定義推導(dǎo)式(11)中的最佳待定系數(shù)。把式(11)代入式(12)，可得:

(15)

(16)

由式(16)可解出a0為:

a0=E[n]-(-aE[M1]+(1-a)E[M2])

(17)

將式(17)代入式(15)，可得:

(-aE[M1]+(1-a)E[M2])]2}=

E{[(aΤ1′+Τ2′)(M-E[M])-(n-E[n])]2}=

(18)

(19)

將式(13)和式(14)代入式(11)即可求出標(biāo)簽數(shù)量估計(jì)值。注意到式(13)和(14)是閉式解，只需求出n和M1、M2的統(tǒng)計(jì)量即可代入直接計(jì)算，避免了傳統(tǒng)估計(jì)算法中常見的極值搜索操作，可以大幅簡化算法的運(yùn)算量。

3 M1、M2和n的序貫統(tǒng)計(jì)量計(jì)算

為了求出a0和a的值，首先需要求出n和M1、M2的一階和二階統(tǒng)計(jì)量E[n]、E[M1]、E[M2]、CMM和CnM。這些統(tǒng)計(jì)量可以在標(biāo)簽識別過程中以序貫的方式求出，以減少運(yùn)算量。具體做法是，讀寫器在識別標(biāo)簽的過程中，每接收到一個新時隙，根據(jù)上一次求出的統(tǒng)計(jì)值和本次時隙狀態(tài)的觀測值更新各個統(tǒng)計(jì)量。下面詳細(xì)介紹各統(tǒng)計(jì)量的序貫式求解方法。

因n的分布一般很難精確確定，實(shí)際中往往只能給出n的大致范圍，因此本文假定n服從均勻分布，即n～U(nmin,nmax)，nmin和nmax分別為標(biāo)簽數(shù)量的下限和上限。

為了后續(xù)推導(dǎo)的方便起見，將推導(dǎo)中用到的變量和自定義函數(shù)定義如下：

δ=1-1/L

(20)

γ=1-2/L

(21)

Θ=nmax-nmin+1

(22)

Π=nmax+nmin

(23)

(24)

(25)

(26)

假定n服從均勻分布U(nmin,nmax),其中nmin和nmax分別為標(biāo)簽數(shù)量的下限和上限。對于幀長為L的一幀，將其中的時隙順序編號為1～L。對于第l個時隙，定義兩個二值隨機(jī)變量il和sl：

在n已知的前提下，il和sl的條件期望如(27)和(28)所示:

E[il|n]=0+1×P(il=1|n)=(1-1/L)n

(27)

E[sl|n]=0+1×P(sl=1|n)=(n/L)(1-1/L)n-1

(28)

由于n服從均勻分布U(nmin,nmax)，其期望值容易求出：

E[n]=(nmax+nmin)/2=Π/2

(29)

使用記號X(k)表示接收到第k個時隙時統(tǒng)計(jì)量X的值。為簡化起見，令A(yù)～H替代推導(dǎo)過程中的一些常值表達(dá)式。已知第k個時隙的統(tǒng)計(jì)量，接收到第k+1個時隙時各統(tǒng)計(jì)量的更新表達(dá)式推導(dǎo)如下：

M1的期望值為：

(k+1)A=Ek[M1]+A

(30)

同樣可得M2的期望值：

(k+1)C=E(k)[M2]+C

(31)

對CnM=(CnM1,CnM2)，可以求出

(32)

(33)

kB+k(k-1)F-(k+1)2A2=

(34)

采用同樣方式，可以得到:

(k+1)C/L+k(k+1)G/L2-(k+1)2C2=

(35)

對于CM1M2，可以求出:

(36)

4 算法復(fù)雜度分析

在實(shí)際應(yīng)用中，受硬件計(jì)算資源的限制，算法復(fù)雜度是衡量算法實(shí)用性的重要指標(biāo)。首先分析本文算法的復(fù)雜度。不失一般性，假設(shè)n服從均勻分布U(0,nmax)。由于乘法計(jì)算量要遠(yuǎn)大于加法，因此本文只以乘法運(yùn)算次數(shù)作為評估計(jì)算復(fù)雜度的指標(biāo)。在計(jì)算第1個時隙時，要首先計(jì)算出δ和γ，因?yàn)檫@兩個量是其他函數(shù)和表達(dá)式的基本因子。很明顯，計(jì)算這兩個量所需的乘法數(shù)為2nmax。經(jīng)過簡單計(jì)算，可以依次得到Γ1(x)、Γ2(x)、Γ3(x)的乘法次數(shù)分別為4、7、20，每個時隙計(jì)算統(tǒng)計(jì)量所需總乘法次數(shù)為14，計(jì)算a0和a需乘法次數(shù)為2和16，計(jì)算式(11)需乘法次數(shù)為2。綜合以上各項(xiàng)，總乘法數(shù)可以求出為2nmax+65。當(dāng)計(jì)算后續(xù)時隙時，各統(tǒng)計(jì)量在原有統(tǒng)計(jì)量的基礎(chǔ)上更新，只需計(jì)算增量部分的乘法次數(shù)，每個時隙總計(jì)需乘法次數(shù)為34，與nmax無關(guān)，即計(jì)算復(fù)雜度都為O(1)。另外，逐時隙估計(jì)[1]和累計(jì)因子[2]的標(biāo)簽估計(jì)式都為解析形式，計(jì)算式(1)和式(2)的乘法次數(shù)分別為4次和5次，因此計(jì)算復(fù)雜度都為O(1)。

另一個高精度標(biāo)簽估計(jì)算法是文獻(xiàn)[11]提出的馬氏距離估計(jì)算法。該算法采用與最大后驗(yàn)概率估計(jì)方法類似的窮舉搜索方式尋找最優(yōu)估計(jì)值。每次計(jì)算式(5)需要36次乘法，整個搜索過程共需要36nmax次乘法，復(fù)雜度為O(n)。雖然該算法的復(fù)雜度與nmax呈線性關(guān)系，但當(dāng)nmax較大時序貫線性貝葉斯算法與之相比仍具有明顯優(yōu)勢。另外，序貫線性貝葉斯算法在估計(jì)精度方面要優(yōu)于該算法，具體的性能比較可見后面的仿真結(jié)果。

5 性能仿真

為驗(yàn)證算法的有效性，將本文提出的序貫線性貝葉斯算法與現(xiàn)有四種算法逐時隙估計(jì)[8]、累計(jì)因子[9]、最大后驗(yàn)概率[10]和馬氏距離[11]進(jìn)行性能比較。首先比較標(biāo)簽數(shù)量估計(jì)精度，幀長為64，標(biāo)簽數(shù)量設(shè)為50。

如圖1所示，隨著觀測時隙數(shù)的增加，各算法的估計(jì)精度都逐漸提高，說明樣本數(shù)的增加可以使估計(jì)更加準(zhǔn)確。同時還可看出，隨著觀測時隙數(shù)的增加，各算法的估計(jì)值都逐漸趨向于穩(wěn)定，在觀測過程中序貫線性貝葉斯方法的誤差始終小于其他算法，且具有更快的收斂速度，當(dāng)觀測時隙數(shù)為16時估計(jì)誤差已小于10%，觀測時隙數(shù)為幀長一半時誤差近似為4%。這說明序貫線性貝葉斯算法可以在觀測時隙數(shù)較少的情況下給出更精確的估計(jì)，使系統(tǒng)可以更早地作出正確的幀長調(diào)整，這將減少整個識別過程的時間消耗。

圖2比較了序貫線性貝葉斯與其他算法在識別效率上的性能差異。一個完整的RFID識別過程包括初始幀和其后的若干個幀，設(shè)初始幀的幀長為128，用識別標(biāo)簽所需的全部時隙數(shù)目評價算法的識別效率。由圖2可見，在5種算法中，使用序貫貝葉斯方法識別全部標(biāo)簽耗時最少，識別效率最高，當(dāng)標(biāo)簽數(shù)量為100和200時所需時隙數(shù)分別為260和540。序貫貝葉斯識別效率高的主要原因有: 一是標(biāo)簽數(shù)量估計(jì)精度高，可使每個識別幀的長度接近最優(yōu)值；二是由于采用序貫式估計(jì)方式，當(dāng)標(biāo)簽數(shù)量與幀長不匹配時，可以及時結(jié)束當(dāng)前幀，使用最優(yōu)幀長啟動下一幀，從而進(jìn)一步縮短了識別時間。

圖1 標(biāo)簽數(shù)量估計(jì)精度比較

圖2 識別所有標(biāo)簽所需的時隙總數(shù)

讀寫器與標(biāo)簽通信過程需要的總幀數(shù)也是影響識別效率的重要因素，總幀數(shù)越多，用于握手過程的通信開銷就越大。圖3比較了幾種算法需要的總幀數(shù)。逐時隙估計(jì)算法由于估計(jì)精度最低，所需總幀數(shù)最多，而累計(jì)因子、最大后驗(yàn)概率和馬氏距離的估計(jì)精度依次提高，所需總幀數(shù)也相應(yīng)減少。本文提出的序貫貝葉斯由于具有較高的標(biāo)簽數(shù)量估計(jì)精度，每幀長度接近最優(yōu)幀長，標(biāo)簽成功讀取率高，在5種算法中所需總幀數(shù)最少，當(dāng)標(biāo)簽數(shù)量為100和200時所需幀數(shù)分別為8和10，可以有效減少通信開銷，提高識別效率。

圖3 識別標(biāo)簽所需的總幀數(shù)

圖4比較了幾種算法的計(jì)算復(fù)雜度，為便于觀察，采用自然對數(shù)坐標(biāo)表示。如圖4所示，最大后驗(yàn)概率算法算法由于所需乘法數(shù)與標(biāo)簽數(shù)量的平方成正比，復(fù)雜度在三種算法中最高，隨標(biāo)簽數(shù)量的增加上升速度最快。馬氏距離的復(fù)雜度與標(biāo)簽數(shù)量呈線性關(guān)系，增長幅度較為緩慢。累計(jì)因子、逐時隙估計(jì)和序貫線性貝葉斯算法復(fù)雜度為O(1)，算法復(fù)雜度受標(biāo)簽數(shù)量影響最小。當(dāng)待識別的標(biāo)簽數(shù)量較多時，序貫線性貝葉斯算法的這種特性具有很大的優(yōu)勢，可以大幅降低計(jì)算復(fù)雜度，節(jié)省計(jì)算資源和能量消耗，尤其適用于移動讀寫器這種資源受限的設(shè)備。

圖4 不同標(biāo)簽數(shù)下算法復(fù)雜度比較

表1列出了不同標(biāo)簽數(shù)量估計(jì)算法的性能對比?；谛蜇灳€性貝葉斯的估計(jì)算法由于使用線性模型并充分利用了時隙狀態(tài)信息，能夠在保證高精度的同時減少計(jì)算復(fù)雜度，使其在計(jì)算資源有限的條件下仍能實(shí)現(xiàn)準(zhǔn)確的估計(jì)。

表1 不同標(biāo)簽數(shù)量估計(jì)算法性能比較

6 結(jié)語

本文在分析比較現(xiàn)有標(biāo)簽數(shù)量估計(jì)算法的基礎(chǔ)上，將序貫線性貝葉斯理論應(yīng)用于標(biāo)簽數(shù)量估計(jì)，提出了隨時隙更新的標(biāo)簽數(shù)量估計(jì)算法，推導(dǎo)了估計(jì)式和各階統(tǒng)計(jì)量的閉式表達(dá)式。該算法可與DFSA協(xié)議有效結(jié)合，每接收到一個時隙后及時計(jì)算標(biāo)簽數(shù)量并調(diào)整幀長，大幅提高標(biāo)簽識別效率。所提的算法在保證高精度估計(jì)的同時，通過序貫式更新統(tǒng)計(jì)量的方式，顯著降低了計(jì)算復(fù)雜度，提高了算法的實(shí)用性。