蔡曉思,劉桂雄,吳國光

（華南理工大學(xué)機(jī)械與汽車工程學(xué)院，廣東 廣州 510640）

基于CFDSE的RFID標(biāo)簽數(shù)動態(tài)估算方法

蔡曉思,劉桂雄,吳國光

（華南理工大學(xué)機(jī)械與汽車工程學(xué)院，廣東 廣州 510640）

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

RFID技術(shù)；標(biāo)簽數(shù)估算；粗精二次搜索；切比雪夫不等式

0 引 言

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

本文在切比雪夫不等式估算方法基礎(chǔ)上，提出一種粗精二次搜索（coarse-fine double searching-based tag estimation method，CFDSE）的標(biāo)簽數(shù)動態(tài)估算方法，在準(zhǔn)確性、復(fù)雜度等性能指標(biāo)有顯著改進(jìn)。

圖1 CFDSE標(biāo)簽數(shù)估算方法與切比雪夫不等式估算法實(shí)現(xiàn)原理對比示意圖

1 CFDSE標(biāo)簽數(shù)估算方法原理架構(gòu)

圖1為基于CFDSE標(biāo)簽數(shù)估算法與切比雪夫不等式估算法的實(shí)現(xiàn)原理對比示意圖。

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

2 標(biāo)簽數(shù)估算方法工作流程

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

（1）確定標(biāo)簽數(shù)搜索范圍[Nmin～Nmax]。Nmin基于碰撞時(shí)隙至少有兩個(gè)標(biāo)簽應(yīng)答條件有Nmin=NS+2NC，Nmax為實(shí)際應(yīng)用場合最大標(biāo)簽數(shù)。

圖2 基于CFDSE標(biāo)簽數(shù)動態(tài)估算方法流程圖

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

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

（3）CFDSE方法求第一次標(biāo)簽估計(jì)值。在搜索范圍[Nmin～Nmax]內(nèi)，搜索使fCFDSE（）取得最小值的標(biāo)簽數(shù)則為第一次標(biāo)簽估計(jì)值Ntag1，即：

（4）判斷Ntag1是否滿足單調(diào)性檢驗(yàn)。通常Ntag1≠Ntag，必須進(jìn)行單調(diào)性檢驗(yàn)，保持估算準(zhǔn)確性。

若切比雪夫不等式估算法空閑、可讀、碰撞時(shí)隙數(shù)統(tǒng)計(jì)量與對應(yīng)理論期望值平方距離函數(shù)為

則切比雪夫不等式估算法標(biāo)簽數(shù)Ntag估算式為

由于fcheby[N0（Lf，n），N1（Lf，n），Nk（Lf，n）]≥0，故由函數(shù)單調(diào)性得標(biāo)簽數(shù)估算式：

下面將空閑、可讀、碰撞時(shí)隙數(shù)統(tǒng)計(jì)量與對應(yīng)理論期望值大小關(guān)系，討論函數(shù)單調(diào)性檢驗(yàn)。

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（）同為單調(diào)增函數(shù)，故 ΔN=0，標(biāo)簽數(shù)估計(jì)值Ntag=Ntag1；2）N0（Lf，n）＜NE、N1（Lf，n）＜NS、Nk（Lf，n）＜NC，fCFDSE（）與fcheby（）同為單調(diào)減函數(shù)，Ntag=Ntag1；3）|NE-NS|=|NC-NS|=0，在定義域內(nèi)單調(diào)性一致，標(biāo)簽數(shù)估計(jì)值Ntag=Ntag1；4）若上述條件不滿足，則ΔN≠0，為獲得更高估算準(zhǔn)確度，以Ntag1為中心，采用切比雪夫不等式估算法進(jìn)行二次搜索。

（5）采用切比雪夫不等式估算法進(jìn)行二次搜索。由圖 1可以看出，fcheby[N0（Lf，n），N1（Lf，n），Nk（Lf，n）]為凹函數(shù)，Ntag為使該函數(shù)取得最小值的標(biāo)簽值。二次搜索可看作是以Ntag1為中心搜索該凹函數(shù)最小值過程。設(shè)第二次搜索步進(jìn)為Δ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）]，此時(shí)標(biāo)簽數(shù)估算值Ntag=Ntag1+iΔn；若Ntag1≥Ntag，則搜索終止條件相反。

3 仿真實(shí)驗(yàn)與分析

RFID標(biāo)簽數(shù)估算方法必須在保證算法準(zhǔn)確性前提下，具有較小運(yùn)算量，且算法還必須能較快適應(yīng)標(biāo)簽數(shù)變化。下面在Matlab軟件平臺，對基于CFDSE標(biāo)簽數(shù)估算方法進(jìn)行性能仿真。

標(biāo)簽數(shù)估算方法準(zhǔn)確性采用估算誤差為指標(biāo)。若N?tag為估算標(biāo)簽數(shù)，Ntag為實(shí)際標(biāo)簽數(shù)，則估算誤差ε定義為

Ntag[50，1 000]，同一標(biāo)簽數(shù)量情況下，各種算法均進(jìn)行1000次獨(dú)立實(shí)驗(yàn)。圖3為5種算法標(biāo)簽數(shù)估計(jì)值與估算誤差曲線圖。

圖3 標(biāo)簽數(shù)估算方法估算誤差圖

由圖3可以看出：

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

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

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

表1為CFDSE標(biāo)簽數(shù)估算方法與切比雪夫不等式估算方法復(fù)雜度分析比較表。

表1 標(biāo)簽數(shù)估算法與切比雪夫不等式估算法復(fù)雜度分析比較表

由于CFDSE第一次搜索將3（Nmax-NS-2NC+1）個(gè)乘法運(yùn)算轉(zhuǎn)化為絕對值加減運(yùn)算，且一般可使第二次搜索范圍減少約90%，故CFDSE估算法乘法個(gè)數(shù)小于0.3（Nmax-NS-2NC+1），運(yùn)算量顯著降低。若乘法、加法、絕對值加減運(yùn)算時(shí)間分別為tmul、tadd、tabs， 令Nsearch=Nmax-NS-2NC+1，則切比雪夫不等估算法、CFDSE法估算時(shí)間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

廣東省高等學(xué)校高層次人才項(xiàng)目（粵教師函[2010]79號文）

蔡曉思（1989-），女，廣東揭陽市人，碩士研究生，專業(yè)方向?yàn)镽FID技術(shù)、智能傳感及仿真建模。