基于高斯擬合與切比雪夫不等式的標(biāo)簽數(shù)量二次估計(jì)算法

嚴(yán)軍榮 葉仁杰 鐘 華 姜顯揚(yáng)

(杭州電子科技大學(xué)通信工程學(xué)院 杭州 310018)

1 引言

射頻識(shí)別技術(shù)(Radio Frequency Identification,RFID)是一種通過(guò)閱讀器在短時(shí)間內(nèi)快速識(shí)別標(biāo)簽的非接觸性識(shí)別技術(shù)[1]，當(dāng)多個(gè)標(biāo)簽處于同一個(gè)閱讀器的工作范圍時(shí)，多個(gè)標(biāo)簽的應(yīng)答信號(hào)會(huì)相互干擾導(dǎo)致閱讀器無(wú)法正常讀取標(biāo)簽內(nèi)信息，這稱為標(biāo)簽碰撞[2]。標(biāo)簽防碰撞問(wèn)題是RFID系統(tǒng)中多標(biāo)簽識(shí)別的關(guān)鍵問(wèn)題[3]。RFID系統(tǒng)中最常使用的防碰撞算法是ALOHA算法[4]，基于ALOHA的算法包括時(shí)隙ALOHA(Slotted Aloha, SA)算法[5]、幀時(shí)隙ALOHA(Frame Slotted Aloha, FSA)算法[6]、動(dòng)態(tài)幀時(shí)隙ALOHA(Dynamic Frame Slot Aloha, DFSA)算法[7]以及其他改進(jìn)算法[8,9]。

DFSA算法是目前比較主流的防碰撞算法，已經(jīng)被一些RFID標(biāo)準(zhǔn)(ISO 14443-3, ISO 18000-6C和EPC Class1 Gen2)采用[10]。DFSA 算法的性能主要從標(biāo)簽數(shù)量估計(jì)和幀長(zhǎng)度設(shè)定兩個(gè)維度進(jìn)行分析。文獻(xiàn)[11]證明當(dāng)幀長(zhǎng)等于RFID系統(tǒng)中待識(shí)別標(biāo)簽的數(shù)量時(shí)，RFID系統(tǒng)達(dá)到最高吞吐率。準(zhǔn)確地估算待識(shí)別標(biāo)簽的數(shù)量，尤其是在大規(guī)模應(yīng)用場(chǎng)景下快速估算標(biāo)簽數(shù)量，是提高防碰撞算法性能的關(guān)鍵。

目前的標(biāo)簽數(shù)量估計(jì)算法主要分為兩類，一類是基于系數(shù)的解析式估計(jì)算法[12–14]，另一類是根據(jù)目標(biāo)函數(shù)進(jìn)行最優(yōu)值搜索的區(qū)間估計(jì)算法[15–17]。

文獻(xiàn)[12]提出Low Bound估計(jì)算法，假定碰撞時(shí)隙中的平均標(biāo)簽量為2，文獻(xiàn)[13]提出Schoute算法，假定碰撞時(shí)隙中的平均標(biāo)簽量為2.39。文獻(xiàn)[14]證明當(dāng)RFID系統(tǒng)中待識(shí)別標(biāo)簽數(shù)量是幀長(zhǎng)3倍以上時(shí)，碰撞時(shí)隙內(nèi)的平均標(biāo)簽數(shù)遠(yuǎn)多二者假定的標(biāo)簽量，因此Low Bound算法和Schoute算法在待識(shí)別標(biāo)簽數(shù)遠(yuǎn)大于幀長(zhǎng)時(shí)估計(jì)誤差相對(duì)較大。為此文獻(xiàn)[14]提出一種基于分段解析式的標(biāo)簽數(shù)量估計(jì)算法，根據(jù)碰撞時(shí)隙比例的不同分段地調(diào)整平均標(biāo)簽數(shù)量的數(shù)值，該算法相對(duì)于Low Bound算法、Schoute算法能更好地適應(yīng)標(biāo)簽數(shù)量的動(dòng)態(tài)變化，但是分段處的跳躍間斷點(diǎn)會(huì)導(dǎo)致估計(jì)值出現(xiàn)大波動(dòng)，而且當(dāng)碰撞時(shí)隙比例較大時(shí)不能及時(shí)調(diào)整碰撞因子值會(huì)導(dǎo)致大的估計(jì)誤差。

文獻(xiàn)[15]提出了基于切比雪夫不等式的區(qū)間估計(jì)算法，利用切比雪夫不等式進(jìn)行標(biāo)簽估計(jì)。文獻(xiàn)[16]提出了基于最大后驗(yàn)概率的區(qū)間估計(jì)算法，將估計(jì)區(qū)間內(nèi)最大后驗(yàn)概率對(duì)應(yīng)的標(biāo)簽量作為待識(shí)別標(biāo)簽數(shù)量的估計(jì)值。上述兩種算法相對(duì)基于系數(shù)的解析式估計(jì)算法大幅提高了估計(jì)精度。但是算法分析復(fù)雜，且估計(jì)穩(wěn)定性差。文獻(xiàn)[17]提出基于粗精2次估計(jì)的RFID標(biāo)簽數(shù)目估計(jì)算法，該算法對(duì)待識(shí)別標(biāo)簽量進(jìn)行粗精兩次估計(jì)，在降低一定時(shí)間復(fù)雜度的同時(shí)提升了估計(jì)精度，但是增加了額外的時(shí)隙消耗；同時(shí)該算法在精估計(jì)時(shí)存在局部最優(yōu)解的問(wèn)題。

由上述分析可知，基于系數(shù)的解析式算法的性能取決于碰撞時(shí)隙中的平均標(biāo)簽數(shù)量，具有計(jì)算量小、估計(jì)精度低的特點(diǎn)；基于區(qū)間的估計(jì)算法在估計(jì)區(qū)間內(nèi)逐一搜索尋找最優(yōu)估計(jì)量，具有計(jì)算量大、估計(jì)精度高的特點(diǎn)。因此本文將上述兩類算法的優(yōu)點(diǎn)進(jìn)行結(jié)合，提出一種基于高斯擬合與切比雪夫不等式的標(biāo)簽數(shù)量2次估計(jì)算法(Twice Labels Number Estimation algorithm based on Gaussian fitting and Chebyshev inequality, TLNEGC)。

2 TLNEGC算法

TLNEGC算法首先根據(jù)碰撞因子與碰撞時(shí)隙比例的關(guān)系建立碰撞模型，采用高斯函數(shù)對(duì)碰撞模型中的離散數(shù)據(jù)點(diǎn)進(jìn)行擬合逼近獲得高斯估計(jì)模型；然后利用高斯估計(jì)模型初次估計(jì)標(biāo)簽的數(shù)量，根據(jù)初次估計(jì)的結(jié)果判斷是否需要進(jìn)行2次估計(jì)，2次估計(jì)是利用切比雪夫不等式對(duì)估計(jì)區(qū)間進(jìn)行2次搜索以獲得最佳估計(jì)值。

2.1 高斯擬合模型

文獻(xiàn)[9]證明了碰撞時(shí)隙的比例、碰撞因子之間的關(guān)系不受幀長(zhǎng)影響。為獲得碰撞時(shí)隙比例F與碰撞因子B的關(guān)系，參照文獻(xiàn)[14]采用蒙特卡羅方法[18]對(duì)閱讀器的讀取過(guò)程進(jìn)行模擬。

模擬中的參數(shù)設(shè)置如下：初始幀長(zhǎng)取值128,256, 512，標(biāo)簽數(shù)量范圍設(shè)置為[100, 1000]，實(shí)驗(yàn)次數(shù)為3000次。

仿真結(jié)果如圖1所示。其中橫軸是碰撞時(shí)隙比例F，縱軸是碰撞因子B。

圖1中的蒙特卡羅數(shù)據(jù)點(diǎn)集分布滿足高斯分布在X負(fù)半軸的分布特征，因此采用1維高斯函數(shù)對(duì)圖1中的蒙特卡羅數(shù)據(jù)點(diǎn)集 (Bi,Fi), i＝1, 2, 3, ···,3000進(jìn)行擬合。擬合形式如式(1)所示

圖1 碰撞時(shí)隙比例與碰撞因子之間的關(guān)系

根據(jù)高斯函數(shù)對(duì)圖1進(jìn)行擬合得到的高斯擬合曲線如圖2所示。從圖2可以看出式(6)給出的擬合曲線具有很好的擬合度。

圖2 高斯擬合曲線

2.2 初次估計(jì)解析方程

根據(jù)式(6)的擬合曲線，閱讀器在一次讀取后根據(jù)反饋信息獲取B的值，從而估計(jì)出標(biāo)簽數(shù)量Ne(此時(shí)為初次估計(jì)值)可由式(7)所示

其中，C為碰撞時(shí)隙數(shù)，S為成功時(shí)隙數(shù)。

當(dāng)初次估計(jì)值Ne小于幀長(zhǎng)L時(shí)，幀長(zhǎng)大于實(shí)際標(biāo)簽量，由多項(xiàng)分布可知，此時(shí)碰撞時(shí)隙數(shù)較少，成功時(shí)隙數(shù)較多，此時(shí)式(7)給出的解析式具有非常好的擬合度的估計(jì)精度，可直接將估計(jì)值輸出為最佳估計(jì)值。當(dāng)初次估計(jì)值Ne大于幀長(zhǎng)L時(shí)，幀長(zhǎng)小于實(shí)際標(biāo)簽量，由多項(xiàng)分布可知，此時(shí)碰撞時(shí)隙數(shù)較多，成功時(shí)隙數(shù)較少，Ne的精確度很大程度受到B的影響，那么需要對(duì)Ne進(jìn)行2次估計(jì)。

2.3 2次估計(jì)

標(biāo)簽在響應(yīng)閱讀器的過(guò)程中隨機(jī)選擇一個(gè)時(shí)隙應(yīng)答，根據(jù)數(shù)理統(tǒng)計(jì)知識(shí)可知，r張標(biāo)簽選擇同一時(shí)隙的概率應(yīng)滿足多項(xiàng)分布?？臻e時(shí)隙概率Pe、成功時(shí)隙概率Ps、碰撞時(shí)隙概率Pc可通過(guò)式(8)所示的公式計(jì)算得到。

其中，P＝1/L，N為待識(shí)別標(biāo)簽數(shù)量。r＝0表示空閑時(shí)隙，r＝1表示成功時(shí)隙，r ＞1表示碰撞時(shí)隙。閱讀器對(duì)標(biāo)簽的每一幀讀取過(guò)程是獨(dú)立的多次實(shí)驗(yàn)(每一幀的每一時(shí)隙為一次獨(dú)立實(shí)驗(yàn)，每次實(shí)驗(yàn)的結(jié)果為空閑時(shí)隙、成功時(shí)隙、碰撞時(shí)隙的一種)，此碰撞場(chǎng)景適用于采用切比雪夫不等式進(jìn)行估計(jì)。

利用切比雪夫不等式對(duì)Ne的初次估計(jì)結(jié)果進(jìn)行估計(jì)，該方法的基礎(chǔ)是隨機(jī)試驗(yàn)的結(jié)果應(yīng)接近于期望值。為此，設(shè)定的一個(gè)估計(jì)區(qū)間Δ，在Δ內(nèi)計(jì)算每一個(gè)標(biāo)簽量n對(duì)應(yīng)的每個(gè)時(shí)隙的期望，計(jì)算每個(gè)時(shí)隙期望與實(shí)際值之間的切比雪夫距離D，在Δ內(nèi)搜索出一個(gè)標(biāo)簽量n使得切比雪夫距離D最小，該標(biāo)簽量n即最佳估計(jì)值。切比雪夫距離D由式(9)所示

2.4 TLNEGC算法流程

TLNEGC的算法流程如表1所示。

表1 TLNEGC的算法流程

3 算法仿真與分析

使用Matlab軟件進(jìn)行仿真實(shí)驗(yàn)，從估計(jì)誤差、時(shí)間復(fù)雜度、總時(shí)隙數(shù)消耗、總時(shí)間消耗、穩(wěn)定性5個(gè)角度進(jìn)行對(duì)比。

3.1 估計(jì)誤差

設(shè)ε為估計(jì)誤差率，Ne為標(biāo)簽數(shù)量的估計(jì)量，N為RFID系統(tǒng)中實(shí)際存在的標(biāo)簽數(shù)量，那么ε可由式(10)計(jì)算

對(duì)本文提出的TLNEGC算法和現(xiàn)有的Low Bound算法、Schoute算法、最大后驗(yàn)概率算法、粗精2次估計(jì)算法的標(biāo)簽數(shù)量估計(jì)誤差率進(jìn)行仿真，仿真結(jié)果如圖3所示。圖3中的橫坐標(biāo)為標(biāo)簽數(shù)量，取值范圍為[100, 1000]，縱坐標(biāo)為估計(jì)誤差率。

由圖3可知，TLNEGC算法誤差曲線整體平緩，誤差均值為2.2%，最大估計(jì)誤差不超過(guò)4%。Low Bound算法、Schoute算法、算法的估計(jì)誤差率隨著標(biāo)簽數(shù)量的增多迅速上升。最大后驗(yàn)概率算法的估計(jì)誤差比Low Bound算法、Schoute算法更低，但明顯高于TLNEGC算法而且誤差曲線起伏大。粗精2次估計(jì)算法在估計(jì)精度、估計(jì)穩(wěn)定性方面優(yōu)于Low Bound算法、Schoute算法、最大后驗(yàn)概率算法，但估計(jì)誤差仍然高于TLNEGC算法。

圖3 誤差對(duì)比

由此可知，TLNEGC算法相比現(xiàn)有算法的估計(jì)誤差更低、穩(wěn)定性更好。其原因在于TLNEGC算法采用了2次估算，第1次是動(dòng)態(tài)調(diào)整解析式系數(shù)以降低估計(jì)誤差，第2次是利用切比雪夫不等式對(duì)初次估計(jì)的結(jié)果進(jìn)行2次搜索以提高估算精度。

3.2 時(shí)間復(fù)雜度

使用算法的運(yùn)行時(shí)間來(lái)衡量時(shí)間復(fù)雜度。對(duì)本文提出的TLNEGC算法和現(xiàn)有的Low Bound算法、Schoute算法、最大后驗(yàn)概率算法、粗精2次估計(jì)算法的運(yùn)行時(shí)間進(jìn)行仿真，仿真結(jié)果如圖4所示。圖4中的橫坐標(biāo)為標(biāo)簽數(shù)量，取值范圍為[100,1000]，縱坐標(biāo)為運(yùn)行時(shí)間。

圖4 運(yùn)行時(shí)間對(duì)比

由圖4可知，本文提出的TLNEGC算法的運(yùn)行時(shí)間與標(biāo)簽量的增長(zhǎng)呈正相關(guān)，平均運(yùn)行時(shí)間為0.0054 s；時(shí)間復(fù)雜度為O(n)。Low Bound算法、Schoute算法的運(yùn)行時(shí)間與標(biāo)簽數(shù)量的增長(zhǎng)基本無(wú)關(guān)，時(shí)間復(fù)雜度為O(1)，平均運(yùn)行時(shí)間為0.0029 s。最大后驗(yàn)概率算法的運(yùn)行時(shí)間隨著標(biāo)簽的增加呈指數(shù)增長(zhǎng)，算法的時(shí)間復(fù)雜度為O(n2)，平均運(yùn)行時(shí)間為0.346 s。粗精2次估計(jì)算法的運(yùn)算時(shí)間與標(biāo)簽量的增長(zhǎng)呈正相關(guān)，時(shí)間復(fù)雜度也為O(n)，平均運(yùn)行時(shí)間為0.012 s。

由此可知，TLNEGC算法的運(yùn)行時(shí)間略長(zhǎng)于系數(shù)類估計(jì)算法，但是明顯低于其他高精度區(qū)間類估計(jì)算法。其原因在于TLNEGC估計(jì)算法在初次估計(jì)時(shí)只做1次乘法，在利用切比雪夫不等式進(jìn)行2次估計(jì)時(shí)也只做0.12n次乘法，因此總體時(shí)間復(fù)雜度仍能保持在O(n)。

3.3 總時(shí)隙數(shù)消耗

為了驗(yàn)證TLNEGC算法的識(shí)別效率，以識(shí)別全部標(biāo)簽所需的總時(shí)隙數(shù)消耗為衡量指標(biāo)，對(duì)本文提出的TLNEGC算法和現(xiàn)有的Low Bound算法、Schoute算法、最大后驗(yàn)概率算法、粗精2次估計(jì)算法的運(yùn)行時(shí)間進(jìn)行仿真，仿真結(jié)果如圖5所示。圖5中的橫坐標(biāo)為標(biāo)簽數(shù)量，取值范圍為[50, 250]，縱坐標(biāo)為識(shí)別所需總時(shí)隙數(shù)。

由圖5可知，TLNEGC算法的總時(shí)隙數(shù)消耗曲線平直，平均消耗414個(gè)時(shí)隙就能完成識(shí)別。Low Bound算法的總時(shí)隙數(shù)消耗曲線起伏較大，平均消耗602個(gè)時(shí)隙就能完成識(shí)別。Schoute算法的總時(shí)隙數(shù)消耗曲線同樣起伏較大，平均消耗564個(gè)時(shí)隙能完成識(shí)別。最大后驗(yàn)概率算法總時(shí)隙消耗曲線平緩，平均消耗458個(gè)時(shí)隙能完成識(shí)別。粗精2次估計(jì)算法總時(shí)隙消耗曲線總體平緩，平均消耗834個(gè)時(shí)隙完成識(shí)別。

圖5 完成識(shí)別所需總時(shí)隙數(shù)消耗比較

由此可知TLNEGC算法相比現(xiàn)有算法的總時(shí)隙數(shù)消耗更少。這是由于TLNEGC算法估計(jì)精度高，有效地減少了時(shí)隙消耗。

3.4 總時(shí)間消耗

為了分析TLNEGC算法的總時(shí)間消耗，以識(shí)別全部標(biāo)簽所需的總時(shí)間消耗為衡量指標(biāo)，對(duì)本文提出的TLNEGC算法和現(xiàn)有的Low Bound算法、Schoute算法、最大后驗(yàn)概率算法、粗精2次估計(jì)算法的運(yùn)行時(shí)間進(jìn)行仿真，仿真結(jié)果如圖6所示。圖6中的橫坐標(biāo)為標(biāo)簽數(shù)量，取值范圍為[100, 500]，縱坐標(biāo)為識(shí)別所需總時(shí)間。

圖6 完成識(shí)別所需總時(shí)間消耗比較

由圖6可知，TLNEGC算法的總時(shí)間隙數(shù)消耗曲線平直，平均消耗0.43s就能完成識(shí)別。Low Bound算法的總時(shí)間隙數(shù)消耗曲線較為平直，平均消耗0.56 s完成識(shí)別。Schoute算法的總時(shí)間隙數(shù)消耗曲線同樣較為平直，平均消耗0.73 s完成識(shí)別。最大后驗(yàn)概率算法的總時(shí)間消耗曲線陡峭，平均消耗0.78 s能完成識(shí)別。粗精2次估計(jì)算法的總時(shí)間隙數(shù)消耗曲線較為平直，平均消耗0.94 s完成識(shí)別。

由此可知TLNEGC算法相比現(xiàn)有算法的總時(shí)間消耗更低。這是由于TLNEGC算法有較高的估計(jì)精度，有效地減少估計(jì)時(shí)隙消耗。同時(shí)TLNEGC算法運(yùn)行時(shí)間短，減少了估計(jì)時(shí)間的消耗。

3.5 穩(wěn)定性

由于存在捕獲效應(yīng)，部分碰撞時(shí)隙會(huì)被閱讀器識(shí)別為成功時(shí)隙，會(huì)引起標(biāo)簽的丟失，導(dǎo)致碰撞時(shí)隙和成功時(shí)隙與實(shí)際情況不符。本節(jié)對(duì)捕獲效應(yīng)下算法的估計(jì)結(jié)果進(jìn)行仿真對(duì)比，其中捕獲效應(yīng)發(fā)生的概率設(shè)置為0.15。

對(duì)捕獲效應(yīng)下TLNEGC算法和現(xiàn)有的Low Bound算法、Schoute算法、最大后驗(yàn)概率算法、粗精2次估計(jì)算法的標(biāo)簽數(shù)量估計(jì)誤差率進(jìn)行仿真，仿真結(jié)果如圖7所示。圖7中的橫坐標(biāo)為標(biāo)簽數(shù)量，取值范圍為[100, 1000]，縱坐標(biāo)為估計(jì)誤差率。

圖7 捕獲效應(yīng)下的估計(jì)誤差

計(jì)算估計(jì)誤差的均方差。TLNEGC算法的均方差為0.0086。Low Bound算法、Schoute算法的均方差分別是0.2376, 0.2304。最大后驗(yàn)概率算法的均方差為0.1550。粗精二次估計(jì)算法的均方差為0.0174。

由此可知在捕獲效應(yīng)的場(chǎng)景下，TLNEGC算法估計(jì)誤差的均方差低于現(xiàn)有估計(jì)算法，穩(wěn)定性更好。其原因在于TLNEGC算法在第1次估算時(shí)動(dòng)態(tài)調(diào)整解析式系數(shù)以降低估計(jì)誤差，在第2次估算時(shí)利用切比雪夫不等式對(duì)初次估計(jì)的結(jié)果進(jìn)行2次搜索保證了估計(jì)的穩(wěn)定性。

4 結(jié)論

針對(duì)RFID系統(tǒng)中標(biāo)簽數(shù)量估計(jì)算法存在的估計(jì)精度不高、識(shí)別時(shí)延長(zhǎng)、時(shí)間復(fù)雜度高的問(wèn)題，本文提出一種基于高斯擬合與切比雪夫不等式的標(biāo)簽數(shù)量二次估計(jì)算法TLNEGC。仿真結(jié)果表明，TLNEGC算法在大規(guī)模標(biāo)簽場(chǎng)景下的平均估計(jì)誤差為2.2%，平均消耗414個(gè)時(shí)隙完成標(biāo)簽數(shù)量識(shí)別，完成識(shí)別平均時(shí)間消耗0.43 s，明顯優(yōu)于現(xiàn)有標(biāo)簽數(shù)量估計(jì)算法且具有較高的穩(wěn)定性。本文所提TLNEGC算法具有估計(jì)精度高、時(shí)間復(fù)雜度低的優(yōu)點(diǎn)，對(duì)于標(biāo)簽數(shù)量識(shí)別具有一定的應(yīng)用價(jià)值。