基于序貫線性貝葉斯的RFID標簽數量估計算法

王 帥, 楊曉東

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

0 引言

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

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

1 相關工作

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

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

(1)

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

文獻[9]提出基于累計因子的標簽數量估計算法，讀寫器接收第i幀后，根據上一幀估計的標簽數量ni和累計因子d計算當前幀的標簽數量ni+1：

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

(2)

(3)

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

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

(4)

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

文獻[11]提出了基于馬氏距離的估計算法，首先計算成功時隙數量X1、空閑時隙數量X2和碰撞時隙數量X3與對應期望值間的馬氏距離，然后選擇使該距離D最短的標簽數量作為估計值：

(5)

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

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

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

2 標簽數量估計問題建模

(6)

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

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

(7)

(8)

p3=1-p1-p2

(9)

(10)

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

(11)

這樣經過簡化后，標簽數量估計值只與M1、M2有關，且僅有2個待定系數a和a0。

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

(12)

式中E[·]是求數學期望的運算。

一般來說，標簽數量與觀測的M1、M2和M3呈非線性關系，采用線性模型會產生估計精度上的損失，但收益則是運算復雜度上的大幅降低。當一個幀中的碰撞時隙數量比例不是很大時，線性模型可以實現較好的近似。

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

定理1 對于由式(11)給出的標簽估計值與空閑、成功和碰撞時隙個數的線性模型，通過求解問題1可獲得該式中的待定系數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é)方差矢量。

證明

根據問題1的定義推導式(11)中的最佳待定系數。把式(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)即可求出標簽數量估計值。注意到式(13)和(14)是閉式解，只需求出n和M1、M2的統(tǒng)計量即可代入直接計算，避免了傳統(tǒng)估計算法中常見的極值搜索操作，可以大幅簡化算法的運算量。

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

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

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

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

δ=1-1/L

(20)

γ=1-2/L

(21)

Θ=nmax-nmin+1

(22)

Π=nmax+nmin

(23)

(24)

(25)

(26)

假定n服從均勻分布U(nmin,nmax),其中nmin和nmax分別為標簽數量的下限和上限。對于幀長為L的一幀，將其中的時隙順序編號為1～L。對于第l個時隙，定義兩個二值隨機變量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)計量X的值。為簡化起見，令A～H替代推導過程中的一些常值表達式。已知第k個時隙的統(tǒng)計量，接收到第k+1個時隙時各統(tǒng)計量的更新表達式推導如下：

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 算法復雜度分析

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

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

5 性能仿真

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

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

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

圖1 標簽數量估計精度比較

圖2 識別所有標簽所需的時隙總數

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

圖3 識別標簽所需的總幀數

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

圖4 不同標簽數下算法復雜度比較

表1列出了不同標簽數量估計算法的性能對比。基于序貫線性貝葉斯的估計算法由于使用線性模型并充分利用了時隙狀態(tài)信息，能夠在保證高精度的同時減少計算復雜度，使其在計算資源有限的條件下仍能實現準確的估計。

表1 不同標簽數量估計算法性能比較

6 結語

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