基于CFDSE的RFID標簽數動態估算方法

蔡曉思,劉桂雄,吳國光

（華南理工大學機械與汽車工程學院，廣東 廣州 510640）

基于CFDSE的RFID標簽數動態估算方法

蔡曉思,劉桂雄,吳國光

（華南理工大學機械與汽車工程學院，廣東 廣州 510640）

針對切比雪夫不等式標簽數估算方法運算量較大的問題，提出粗精二次搜索RFID標簽數動態估算方法（CFDSE），基于由粗至精搜索思想，第一次搜索用加減運算消除平方、開方運算，同時減少第二次搜索范圍，可使第二次搜索范圍減少約90%。第二次搜索采用切比雪夫不等式估算方法，提高估算準確度。仿真實驗表明：CFDSE估算誤差小于5%，估算時間比切比雪夫不等式法減少約54%。

RFID技術；標簽數估算；粗精二次搜索；切比雪夫不等式

0 引 言

RFID是物聯網關鍵技術之一，在工業自動化、物流管理、定位等領域有廣闊的應用潛力[1-3]。多標簽碰撞是影響RFID信息快速獲取的主要問題之一，為有效降低碰撞概率，需根據標簽數設置讀寫器參數，但通常識別區域標簽數未知，故首先準確估算標簽數，有助于提高標簽防碰撞算法效率。目前RFID標簽數估算方法主要有：（1）基于碰撞最小值、泊松分布、空閑時隙數估算法等條件假設，建立標簽數與時隙統計量解析式，估算標簽數，但該方法關系式固定，估算誤差隨標簽數增加迅速增大，不適用于標簽數較多場合[4-6]；（2）利用空閑、可讀、碰撞時隙數統計信息，在標簽數搜索區間，尋找使評定指標滿足最小或最大條件的標簽數，如基于切比雪夫不等式、最大似然、貝葉斯估計等估算法等[7-9]。基于區間搜索的標簽數估算方法準確度較高，是標簽數估算的發展方向，但算法復雜、計算量大，不適用于計算能力較差的嵌入式讀寫系統開發。若能在保證準確度前提下，降低算法運算量，則該方法將更具應用價值。

本文在切比雪夫不等式估算方法基礎上，提出一種粗精二次搜索（coarse-fine double searching-based tag estimation method，CFDSE）的標簽數動態估算方法，在準確性、復雜度等性能指標有顯著改進。

圖1 CFDSE標簽數估算方法與切比雪夫不等式估算法實現原理對比示意圖

1 CFDSE標簽數估算方法原理架構

圖1為基于CFDSE標簽數估算法與切比雪夫不等式估算法的實現原理對比示意圖。

粗精二次搜索標簽數動態估算方法首先以空閑、可讀、碰撞時隙數統計量與理論期望值的絕對值距離函數fCFDSE（）=|ΔE|+|ΔS|+|ΔC|為指標，在標簽數取值區間，搜索使該函數取得最小值的標簽數為第一次搜索結果，實現粗搜索。若fCFDSE（）與切比雪夫不等式函數fcheby（）=ΔE2（Lf，n）+ΔS2（Lf，n）+ΔC2（Lf，n）單調性相同，則Ntag=Ntag1，這樣就實現以另外一種評價指標代替，用加減運算代替平方、開方運算；若fCFDSE（）與fcheby（）單調性不同，再以Ntag1為中心搜索，用切比雪夫不等式估算法進行第二次精搜索，在Ntag1附近將得到Ntag，由于搜索區間減小，整個搜索范圍平方、開方運算減少，運算量也可減小。

2 標簽數估算方法工作流程

圖2為基于CFDSE標簽數估算方法流程圖。具體包括：確定標簽數搜索范圍[Nmin～Nmax]；計算NE、NS、NC與理論期望值的絕對值距離fCFDSE（）；CFDSE方法求第一次標簽估計值Ntag1；Ntag1單調性檢驗判斷；采用切比雪夫不等式估算法進行二次搜索求Ntag等，下面簡單對算法進行說明。

（1）確定標簽數搜索范圍[Nmin～Nmax]。Nmin基于碰撞時隙至少有兩個標簽應答條件有Nmin=NS+2NC，Nmax為實際應用場合最大標簽數。

圖2 基于CFDSE標簽數動態估算方法流程圖

（2）計算NE、NS、NC與理論期望值的絕對值距離fCFDSE（）。若空閑、可讀、碰撞時隙數的理論期望值分別為

可得CFDSE法搜索的絕對值距離公式為

（3）CFDSE方法求第一次標簽估計值。在搜索范圍[Nmin～Nmax]內，搜索使fCFDSE（）取得最小值的標簽數則為第一次標簽估計值Ntag1，即：

（4）判斷Ntag1是否滿足單調性檢驗。通常Ntag1≠Ntag，必須進行單調性檢驗，保持估算準確性。

若切比雪夫不等式估算法空閑、可讀、碰撞時隙數統計量與對應理論期望值平方距離函數為

則切比雪夫不等式估算法標簽數Ntag估算式為

由于fcheby[N0（Lf，n），N1（Lf，n），Nk（Lf，n）]≥0，故由函數單調性得標簽數估算式：

下面將空閑、可讀、碰撞時隙數統計量與對應理論期望值大小關系，討論函數單調性檢驗。

1）N0（Lf，n）＞NE、N1（Lf，n）＞NS、Nk（Lf，n）＞NC，則ΔE（Lf，n）、ΔS（Lf，n）、ΔC（Lf，n）均大于 0，fCFDSE（）與fcheby（）同為單調增函數，故 ΔN=0，標簽數估計值Ntag=Ntag1；2）N0（Lf，n）＜NE、N1（Lf，n）＜NS、Nk（Lf，n）＜NC，fCFDSE（）與fcheby（）同為單調減函數，Ntag=Ntag1；3）|NE-NS|=|NC-NS|=0，在定義域內單調性一致，標簽數估計值Ntag=Ntag1；4）若上述條件不滿足，則ΔN≠0，為獲得更高估算準確度，以Ntag1為中心，采用切比雪夫不等式估算法進行二次搜索。

（5）采用切比雪夫不等式估算法進行二次搜索。由圖 1可以看出，fcheby[N0（Lf，n），N1（Lf，n），Nk（Lf，n）]為凹函數，Ntag為使該函數取得最小值的標簽值。二次搜索可看作是以Ntag1為中心搜索該凹函數最小值過程。設第二次搜索步進為Δn，若Ntag1＜Ntag，則搜索終止條件為：fcheby[N0（Lf，Ntag1+iΔn），N1（Lf，Ntag1+iΔn），Nk（Lf，Ntag1+iΔn）]≤fcheby[N0（Lf，Ntag1+iΔn+Δn），N1（Lf，Ntag1+iΔn+Δn），Nk（Lf，Ntag1+iΔn+Δn）]，此時標簽數估算值Ntag=Ntag1+iΔn；若Ntag1≥Ntag，則搜索終止條件相反。

3 仿真實驗與分析

RFID標簽數估算方法必須在保證算法準確性前提下，具有較小運算量，且算法還必須能較快適應標簽數變化。下面在Matlab軟件平臺，對基于CFDSE標簽數估算方法進行性能仿真。

標簽數估算方法準確性采用估算誤差為指標。若N?tag為估算標簽數，Ntag為實際標簽數，則估算誤差ε定義為

Ntag[50，1 000]，同一標簽數量情況下，各種算法均進行1000次獨立實驗。圖3為5種算法標簽數估計值與估算誤差曲線圖。

圖3 標簽數估算方法估算誤差圖

由圖3可以看出：

（1）Ntag/Lf＜5，此情況在實際中較為常見，CFDSE標簽數估算法第一次搜索結果與切比雪夫不等式法準確度性能接近，誤差隨標簽數增加不明顯且小于5%，優于碰撞最小值估算法、泊松分布法與空閑時隙法。

（2）5≤Ntag/Lf≤8時，CFDSE估算法第一次搜索結果誤差小于9%，切比雪夫不等式法估算結果誤差小于7%，但CFDSE估算法第一次搜索算法無須平方運算，復雜度較低。

（3）Ntag/Lf＞8時，由于誤差增大，需在第一次搜索基礎上，結合切比雪夫不等式法進行二次搜索，保證估算方法準確度。

表1為CFDSE標簽數估算方法與切比雪夫不等式估算方法復雜度分析比較表。

表1 標簽數估算法與切比雪夫不等式估算法復雜度分析比較表

由于CFDSE第一次搜索將3（Nmax-NS-2NC+1）個乘法運算轉化為絕對值加減運算，且一般可使第二次搜索范圍減少約90%，故CFDSE估算法乘法個數小于0.3（Nmax-NS-2NC+1），運算量顯著降低。若乘法、加法、絕對值加減運算時間分別為tmul、tadd、tabs， 令Nsearch=Nmax-NS-2NC+1，則切比雪夫不等估算法、CFDSE法估算時間Tcheby、TCFDSE分別為

Dynamic estimation method for RFID tag based on CFDSE

CAI Xiao-si，LIU Gui-xiong，WU Guo-guang
（School of Mechanical and Automotive Engineering，South China University of Technology，Guangzhou 510640，China）

According to the large computation of Chebyshev inequality-based tag estimation method，the dynamic coarse-fine double searching-based tag estimation method （CFDSE）was proposed.Based on the idea of coarse-to-fine search，the first search eliminates square，square root with addition and subtraction，while reducing the second search range.The second search range can be reduced by about 90%.The second search estimation method using Chebyshev inequality to improve the estimation accuracy.Simulation results show that the CFDSE estimation error is less than 5%，the estimation time of about 54% less than the Chebyshev inequality method.

RFID；tag estimation；CFDSE；Chebyshev inequality

TP391.45；TP391.9；TP18；O242

：A

：1674-5124（2014)03-0098-03

10.11857/j.issn.1674-5124.2014.03.026

2013-06-13；

：2013-07-30

廣東省高等學校高層次人才項目（粵教師函[2010]79號文）

蔡曉思（1989-），女，廣東揭陽市人，碩士研究生，專業方向為RFID技術、智能傳感及仿真建模。