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

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

（1.中國(guó)人民解放軍93114 部隊(duì)，北京 100085；2.電子科技大學(xué)，四川 成都 611731；3.中國(guó)電子科技集團(tuán)公司第三十研究所，四川 成都 610041）

0 引言

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

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

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

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

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

1 系統(tǒng)模型

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

2 貝葉斯推斷

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

圖1 系統(tǒng)模型結(jié)構(gòu)

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

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

由于在每個(gè)時(shí)隙中F是獨(dú)立同分布的，結(jié)合Bernstein-von Mises 定理可知，后驗(yàn)概率會(huì)收斂于正態(tài)分布，對(duì)式（2）求期望可得到式（3），可以用來(lái)估計(jì)N。

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

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

3 改進(jìn)的貝葉斯算法

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

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

明顯可以看出后驗(yàn)概率仍然是高斯函數(shù)，根據(jù)當(dāng)前時(shí)隙的期望和標(biāo)準(zhǔn)差可以估計(jì)下一時(shí)隙的期望值：

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

對(duì)于成功的時(shí)隙，期望和標(biāo)準(zhǔn)差分別由式（6）和（7）得出：

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

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

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

根據(jù)后驗(yàn)概率的期望、標(biāo)準(zhǔn)差和分布區(qū)間來(lái)估計(jì)未識(shí)別的標(biāo)簽數(shù)目，其中erf(x)是高斯誤差函數(shù)。

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

4 算法仿真

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

圖2 性能仿真結(jié)果

5 結(jié)語(yǔ)

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