嚴軍榮 葉仁杰 鐘 華 姜顯揚

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

1 引言

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

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

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

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

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

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

2 TLNEGC算法

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

2.1 高斯擬合模型

文獻[9]證明了碰撞時隙的比例、碰撞因子之間的關系不受幀長影響。為獲得碰撞時隙比例F與碰撞因子B的關系，參照文獻[14]采用蒙特卡羅方法[18]對閱讀器的讀取過程進行模擬。

模擬中的參數(shù)設置如下：初始幀長取值128,256, 512，標簽數(shù)量范圍設置為[100, 1000]，實驗次數(shù)為3000次。

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

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

圖1 碰撞時隙比例與碰撞因子之間的關系

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

圖2 高斯擬合曲線

2.2 初次估計解析方程

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

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

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

2.3 2次估計

標簽在響應閱讀器的過程中隨機選擇一個時隙應答，根據(jù)數(shù)理統(tǒng)計知識可知，r張標簽選擇同一時隙的概率應滿足多項分布。空閑時隙概率Pe、成功時隙概率Ps、碰撞時隙概率Pc可通過式(8)所示的公式計算得到。

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

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

2.4 TLNEGC算法流程

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

表1 TLNEGC的算法流程

3 算法仿真與分析

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

3.1 估計誤差

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

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

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

圖3 誤差對比

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

3.2 時間復雜度

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

圖4 運行時間對比

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

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

3.3 總時隙數(shù)消耗

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

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

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

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

3.4 總時間消耗

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

圖6 完成識別所需總時間消耗比較

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

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

3.5 穩(wěn)定性

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

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

圖7 捕獲效應下的估計誤差

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

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

4 結(jié)論

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