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

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

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

0 引言

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

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

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

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

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

1 系統(tǒng)模型

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

2 貝葉斯推斷

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

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

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

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

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

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

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

3 改進的貝葉斯算法

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

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

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

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

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

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

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

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

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

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

4 算法仿真

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

圖2 性能仿真結果

5 結語

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