一種基于貝葉斯推理的多標簽數(shù)量估計方法*

劉 婷，陳慶榮，楊弘峰，宋金圣，韋 濤

（1.中國人民解放軍93114 部隊，北京 100085；2.電子科技大學，四川 成都 611731；3.中國電子科技集團公司第三十研究所，四川 成都 610041）

0 引言

在射頻識別（Radio Frequency Identification，RFID）系統(tǒng)中，同一時間內(nèi)多個標簽向讀寫器發(fā)送數(shù)據(jù)會發(fā)生沖突，這會嚴重影響通信的系統(tǒng)效率。RFID 系統(tǒng)一般都使用時分的接入方式，即節(jié)點競爭時間來發(fā)送，常見的接入方式可以歸類為純ALOHA、時隙ALOHA、幀時隙ALOHA 和動態(tài)幀時隙ALOHA（Dynamic Framed Slotted ALOHA，DFSA）。

DFSA 算法將信道分為多個時隙，標簽隨機選擇一個時隙接入信道。根據(jù)每個時隙中活躍標簽的數(shù)量不同，可以把時隙分為3 類，空時隙（0 個標簽）、成功時隙（1 個標簽）和碰撞時隙（多于1個標簽）[1-3]。其中，只有成功時隙完成了信息的有效傳輸，系統(tǒng)效率為成功時隙占總時隙數(shù)量的比例。

當標簽數(shù)量和時隙數(shù)量相等時，系統(tǒng)效率達到最優(yōu)性能，為36.8%[4]。DFSA 算法性能除了受到標簽數(shù)量估計精度的影響外，還受到初始時隙數(shù)量選擇的影響。當初始時隙數(shù)量選擇不合適時，會顯著降低系統(tǒng)性能[5]。DFSA 提前停止算法在盤存過程中不斷地估計標簽數(shù)量，并實時地判斷時隙數(shù)量和標簽數(shù)量組合是否符合最優(yōu)組合。如果不符合，則提前停止該幀并立即更新時隙數(shù)量[6]。

提前停止算法降低了初始時隙數(shù)量選擇不合理帶來的影響，但是仍然存在一個觀察時隙的問題。傳統(tǒng)的標簽數(shù)量估計算法需要觀察多個時隙中標簽是否成功傳輸或碰撞。一般說來，觀察的時隙數(shù)量越多，標簽數(shù)量估計的準確性越高，不同的觀察時隙的數(shù)量會影響算法的性能[7]。Robithoh Annur 等提出了一種貝葉斯估計的算法，可以只觀察一個時隙來估計標簽數(shù)量，并在連續(xù)的幀迭代過程中不停地更新標簽數(shù)量估計的值，既可以達到優(yōu)秀的標簽數(shù)量估計精度，又可以減少觀察時隙的數(shù)量，其系統(tǒng)性能在標簽數(shù)量較多時（N＞200）可以達到DFSA的理論極限，但是其計算復雜度較高[8]。

本文在貝葉斯估計算法的基礎上進行了改進，擬降低其計算復雜度，并提高算法在標簽數(shù)量較小時的性能。該算法采用貝葉斯推理的方式，根據(jù)先驗概率和似然函數(shù)計算后驗概率，在貝葉斯推理的基礎上，進行了兩個改進。第一，在計算先驗概率和后驗概率時，采用了動態(tài)調(diào)整計算區(qū)間的方法，降低了初始計算區(qū)間對算法復雜度的影響；第二，采用正態(tài)分布對先驗概率進行擬合，降低了計算復雜度。仿真結果顯示，該算法性能與原始算法相當。

1 系統(tǒng)模型

在DFSA 系統(tǒng)中，讀寫器開啟一個包含若干時隙的幀，標簽會隨機選擇其中的一個時隙來傳輸。在本論文中，將時隙ALOHA 接入方式看作是特殊的DFSA 接入方式，每一幀只有第一個時隙被實現(xiàn)，即每一幀在其第一個時隙后就提前結束。如圖1 所示，讀寫器首先開啟了長度為4 的幀，在第一個時隙結束后重新開啟了長度是16的幀，后面的幀以此類推。每個幀實質(zhì)上只有第一個時隙，其余時隙都沒有實現(xiàn)。每個幀只有選擇了第一個時隙的標簽才會發(fā)送。在DFSA 系統(tǒng)中，節(jié)點數(shù)目的估計算法和幀長的調(diào)整策略是兩個重點，嚴重影響著系統(tǒng)的性能。為了最大化系統(tǒng)效率，讀寫器可以在每個時隙都估計標簽數(shù)目，并且據(jù)此更新幀長度和接入概率。

2 貝葉斯推斷

在一個幀內(nèi)，每個時隙內(nèi)只有3 種情況，即空時隙、成功識別的時隙、沖突的時隙。3 種時隙的數(shù)目分別表示為E、S、C。讀寫器可以根據(jù)這3 種時隙的數(shù)目來估計節(jié)點的數(shù)目。

圖1 系統(tǒng)模型結構

貝葉斯推斷利用貝葉斯定理，根據(jù)先驗條件來估計后驗概率。在DFSA 系統(tǒng)中，可以使用貝葉斯推斷來逐時隙地估計標簽數(shù)目。將當前時隙中發(fā)送的標簽數(shù)目作為先驗信息，讀寫器工作范圍內(nèi)要識別的標簽數(shù)量作為參數(shù)N，則先驗概率表示為P(N)，N的范圍是[0,∞]。在每個時隙內(nèi)，假定標簽接入的概率是p，則似然函數(shù)可以表示為式（1），其服從二項分布，其中F是當前時隙中的標簽數(shù)量。

根據(jù)貝葉斯公式，可以將后驗概率表示為：

由于在每個時隙中F是獨立同分布的，結合Bernstein-von Mises 定理可知，后驗概率會收斂于正態(tài)分布，對式（2）求期望可得到式（3），可以用來估計N。

盡管貝葉斯推斷具有較好的估計性能，但是在DFSA 應用中會存在一些限制。一方面，讀寫器無法確定N的大小，在計算時假定N分布于[0，∞]是不切實際的，如果假定其分布于0 到Nmax，在實際標簽數(shù)目大于Nmax時該算法將不適用。另一方面，讀寫器需要記錄所有后驗概率的值，并且在每個時隙根據(jù)似然函數(shù)和觀測數(shù)據(jù)來計算后驗概率，每個時隙中至少要進行2Nmax次乘積運算，運算量較大并且與標簽數(shù)目相關。為此，本文基于貝葉斯推斷提出改進算法，使用高斯函數(shù)來估計后驗概率，每次計算只有兩個主要參數(shù)進行更新，明顯降低了計算量。

讀寫器在每個時隙都計算最優(yōu)幀長。最優(yōu)幀長可以根據(jù)標簽數(shù)目的估計值來確定。如果最優(yōu)幀長與當前幀長度相同，讀寫器會發(fā)送QuerryRep 命令繼續(xù)執(zhí)行當前幀，否則發(fā)送QuerryAdjust 命令調(diào)整幀長度。在服從EPCglobal C1G2 標準的情況下，幀長只能是2 的指數(shù)，即2Q，否則幀長可以是任意的自然數(shù)。在一次盤存過程中，讀寫器重復執(zhí)行上述命令，如果讀寫器開啟了一個長度為1 的幀并且沒有標簽發(fā)送，則表示所有標簽都識別完，盤存過程結束。

3 改進的貝葉斯算法

高斯分布僅僅由期望μ和標準差σ決定。使用高斯分布來近似模擬后驗概率曲線可以簡化計算，不用記錄后驗概率的所有值，每次只需要關注更新μ和σ兩個變量及分布區(qū)間[0，Nmax]。假定先驗概率服從高斯分布，對似然函數(shù)進行選擇，可以保證后驗概率曲線保持高斯函數(shù)的形狀。需要注意的是，使用高斯函數(shù)來近似分布區(qū)間里的后驗概率曲線，并不意味著標簽數(shù)目服從高斯分布。考慮到分布區(qū)間的變化，在分布區(qū)間內(nèi)，對概率進行了歸一化以確保在每個時隙中其和為1。

使用μc和σc表示在當前時隙中對未識別節(jié)點數(shù)目估計的期望和標準差，μn和σn表示下一時隙中的期望和標準差，F(xiàn)表示當前時隙中的標簽數(shù)目。由于讀寫器不能區(qū)分沖突時隙中的節(jié)點數(shù)目，時隙為空、成功、沖突3 種狀態(tài)分別對應為F=0、F=1、F＞1。對于空時隙，似然函數(shù)是關于N的指數(shù)函數(shù)，后驗概率可以表示為：

明顯可以看出后驗概率仍然是高斯函數(shù)，根據(jù)當前時隙的期望和標準差可以估計下一時隙的期望值：

假定了p足夠小，使-ln(1-p)≈1/p。

對于成功的時隙，期望和標準差分別由式（6）和（7）得出：

當時隙中F＞3 時似然函數(shù)是類似log 函數(shù)的曲線，1 ≤F≤3 時似然函數(shù)是∩形曲線，此時期望和標準差可以表示為：

和空時隙的情況類似，后驗概率仍是高斯函數(shù)，結合貝葉斯公式，后驗概率表示為：

對于成功時隙，即F=1 的情況，由于只對未識別的標簽數(shù)目進行估計，要在后驗概率的期望值上減1，由此得到更新的后驗概率的期望和標準差：

根據(jù)后驗概率的期望、標準差和分布區(qū)間來估計未識別的標簽數(shù)目，其中erf(x)是高斯誤差函數(shù)。

為了保證算法適應不同標簽數(shù)目，每次估計需要對分布區(qū)間做出調(diào)整，Nmax的更新公式為：

4 算法仿真

首先評估提出的算法對初始Q值的敏感性。作為對比，采用文獻[1]中的標簽數(shù)量估計算法，并對標準DFSA和DFSA幀提前停止算法進行了對比。仿真結果如圖2 所示。從圖2 中可以看出，當讀寫器不采用幀提前停止算法時，即使讀寫器準確地知道標簽數(shù)量，也無法達到最優(yōu)性能，系統(tǒng)性能在初始Q值和標簽數(shù)量匹配時才達到最優(yōu)。而當采用了幀提前停止算法時，則算法對初始幀長和標簽數(shù)量的敏感性明顯下降，對于不同的初始Q值，系統(tǒng)的性能也存在一定的波動性。而本文提出的算法則能很好地應對初始幀長和標簽數(shù)量不匹配的問題。

圖2 性能仿真結果

5 結語

本文提出了一種改進的基于貝葉斯推理的RFID 標簽數(shù)量估計算法，該算法利用高斯函數(shù)來擬合先驗概率，在每個時隙結束時根據(jù)時隙的類型，利用式（8）、式（9）、式（11）、式（12）和式（13）來更新μ和σ，及估計標簽數(shù)目。算法收斂快，估計精度高，可以應用于DFSA 幀提前停止算法中。仿真結果表明，該算法系統(tǒng)性能穩(wěn)定，對標簽數(shù)量和初始Q值不敏感，大大增強了RFID 系統(tǒng)的穩(wěn)定性。此外，該算法與傳統(tǒng)貝葉斯估計算法相比，復雜度大大降低，僅需要進行固定數(shù)量的基礎運算。本算法適用于大容量倉儲物流中多標簽高效快速識別應用場景。