基于粗精二次估計(jì)的RFID標(biāo)簽數(shù)目估算方法

丁建立，韓宇超，王家亮

(1.中國(guó)民航大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300； 2.天津市智能信號(hào)與圖像處理重點(diǎn)實(shí)驗(yàn)室(中國(guó)民航大學(xué))，天津 300300)(*通信作者電子郵箱hyccauc2015@163.com)

基于粗精二次估計(jì)的RFID標(biāo)簽數(shù)目估算方法

丁建立1,2，韓宇超1*，王家亮1

(1.中國(guó)民航大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300； 2.天津市智能信號(hào)與圖像處理重點(diǎn)實(shí)驗(yàn)室(中國(guó)民航大學(xué))，天津 300300)(*通信作者電子郵箱hyccauc2015@163.com)

為了解決航空物聯(lián)網(wǎng)信息采集領(lǐng)域RFID標(biāo)簽估算方法存在的估算精度和運(yùn)算量之間的矛盾，以及標(biāo)簽讀取過(guò)程隨機(jī)性所導(dǎo)致的估算方法性能不穩(wěn)定的問(wèn)題,結(jié)合粗估計(jì)的快速、精估計(jì)的準(zhǔn)確和二次估計(jì)算法性能的穩(wěn)定性，提出一種基于粗精二次估計(jì)的RFID標(biāo)簽數(shù)目估算方法。首先,對(duì)幀時(shí)隙ALOHA算法標(biāo)簽讀取過(guò)程進(jìn)行建模，分析得出碰撞時(shí)隙中的平均標(biāo)簽數(shù)目和碰撞時(shí)隙所占比例之間的數(shù)學(xué)模型;然后，基于上述數(shù)學(xué)模型進(jìn)行標(biāo)簽數(shù)目粗估計(jì)，評(píng)估粗估計(jì)值是否需要進(jìn)行二次精估計(jì)。在二次精估計(jì)中，將粗估計(jì)值作為先驗(yàn)知識(shí)，采用基于先驗(yàn)知識(shí)的最大后驗(yàn)概率(MAP)估計(jì)算法提高估算準(zhǔn)確度，相比原始后驗(yàn)概率估計(jì)算法的搜索范圍可減少90%。仿真實(shí)驗(yàn)表明，基于粗精估計(jì)的RFID標(biāo)簽數(shù)目估算平均誤差為3.8%，估算方法性能穩(wěn)定性顯著提高，運(yùn)算量大幅下降，可有效地應(yīng)用于航空物聯(lián)網(wǎng)信息采集過(guò)程。

射頻識(shí)別防碰撞算法；粗精二次估計(jì)；標(biāo)簽數(shù)估計(jì)；最大后驗(yàn)概率估計(jì)；建模分析

國(guó)內(nèi)航空貨運(yùn)過(guò)程中的數(shù)據(jù)采集與關(guān)鍵環(huán)節(jié)的貨物識(shí)別和跟蹤等工作主要是通過(guò)人工方式來(lái)完成，由于在流程上人為因素較多，導(dǎo)致貨物流通時(shí)間長(zhǎng)，貨損率相對(duì)較高。隨著航空物流貨運(yùn)量的快速增加，使得人為因素所造成的貨物處理效率低下問(wèn)題更加突出。因此，航空物流產(chǎn)業(yè)急需信息化建設(shè)。

目前，射頻識(shí)別(Radio Frequency Identification, RFID)技術(shù)[1]被廣泛應(yīng)用于現(xiàn)代物流產(chǎn)業(yè)中，如倉(cāng)庫(kù)管理、資產(chǎn)管理、貨物定位追蹤等。與人工方式相比，RFID技術(shù)在進(jìn)行信息采集與貨物識(shí)別和跟蹤時(shí)更加準(zhǔn)確與快速。但在實(shí)際應(yīng)用場(chǎng)景中大多數(shù)RFID標(biāo)簽無(wú)源且不具有載波監(jiān)聽能力，當(dāng)閱讀器閱讀范圍內(nèi)同時(shí)存在多個(gè)標(biāo)簽時(shí)，若多個(gè)標(biāo)簽同時(shí)響應(yīng)閱讀器指令，會(huì)出現(xiàn)信號(hào)沖突，閱讀器就不能準(zhǔn)確識(shí)別出所有標(biāo)簽，這就是標(biāo)簽碰撞。多標(biāo)簽碰撞是影響RFID系統(tǒng)識(shí)別效率的主要原因之一。解決這個(gè)問(wèn)題的算法稱為標(biāo)簽防碰撞算法，而對(duì)標(biāo)簽數(shù)的準(zhǔn)確估計(jì)是提高標(biāo)簽防碰撞算法效率的重要環(huán)節(jié)。

為了提高RFID標(biāo)簽防碰撞算法的效率，本文提出一種基于粗精二次估計(jì)的RFID標(biāo)簽數(shù)目估算方法。對(duì)多標(biāo)簽碰撞過(guò)程進(jìn)行建模，構(gòu)建了更具適應(yīng)能力的標(biāo)簽估計(jì)解析式，在此基礎(chǔ)上，與基于先驗(yàn)知識(shí)的最大后驗(yàn)概率估計(jì)方法結(jié)合，改善了標(biāo)簽估計(jì)準(zhǔn)確性與復(fù)雜度之間的矛盾，在確保估計(jì)準(zhǔn)確性與估計(jì)穩(wěn)定性的前提下顯著降低了估計(jì)的復(fù)雜度。

1 相關(guān)工作

RFID防碰撞算法主要分為基于ALOHA(Aloha protocol)的防碰撞算法[2-4]和基于樹的防碰撞算法[5-6]兩大類?；贏LOHA的防碰撞算法當(dāng)前研究熱點(diǎn)為動(dòng)態(tài)幀時(shí)隙ALOHA算法，在原幀時(shí)隙ALOHA算法的基礎(chǔ)上，通過(guò)利用標(biāo)簽數(shù)估計(jì)值動(dòng)態(tài)調(diào)整幀長(zhǎng)，提高了標(biāo)簽識(shí)別效率?；跇涞姆琅鲎菜惴ㄖ?，根節(jié)點(diǎn)表示最先發(fā)生碰撞的標(biāo)簽集合，隨后閱讀器不斷分裂碰撞標(biāo)簽集合，構(gòu)成一系列子集，直到每個(gè)子集中只有一個(gè)電子標(biāo)簽，閱讀器完成對(duì)標(biāo)簽的識(shí)別。此類算法中由未識(shí)別的標(biāo)簽數(shù)量來(lái)確定碰撞標(biāo)簽集合分裂的數(shù)量，估計(jì)標(biāo)簽數(shù)量可以使集合分裂數(shù)量更合理，提高算法的時(shí)隙利用率。但閱讀器識(shí)別區(qū)域標(biāo)簽數(shù)量通常是未知的，所以準(zhǔn)確估計(jì)標(biāo)簽數(shù)量，有利于提高標(biāo)簽防碰撞算法的效率。

現(xiàn)有的標(biāo)簽估計(jì)算法主要分為解析式估計(jì)算法[7-9]和區(qū)間搜索估計(jì)算法[10-12]兩類。解析式估計(jì)算法包括Low Bound估計(jì)算法、Schoute估計(jì)算法、基于空閑時(shí)隙估計(jì)算法等；區(qū)間搜索估計(jì)算法包括基于切比雪夫不等式估計(jì)算法和最大后驗(yàn)概率估計(jì)算法等。

Low Bound估計(jì)算法基于每個(gè)碰撞時(shí)隙中至少存在2個(gè)標(biāo)簽的原理，得出待估計(jì)標(biāo)簽數(shù)目的最低估計(jì)值Ntag：

Ntag=S+2C

(1)

其中：S為識(shí)別時(shí)隙數(shù)量，C為碰撞時(shí)隙數(shù)量。在標(biāo)簽規(guī)模小于50時(shí)，Low Bound算法估計(jì)效率很高。但隨著標(biāo)簽規(guī)模的增大，算法誤差增長(zhǎng)率也隨之增大，所以Low Bound算法不能適應(yīng)大規(guī)模標(biāo)簽估計(jì)。Schoute估計(jì)算法假設(shè)閱讀過(guò)程中標(biāo)簽選擇某一時(shí)隙的概率服從泊松分布，基于此假設(shè)得出每個(gè)碰撞時(shí)隙中平均包含的標(biāo)簽數(shù)目為2.39個(gè)，進(jìn)而可以得出未識(shí)別標(biāo)簽的數(shù)目為2.39C，其中C為碰撞時(shí)隙的數(shù)量。此算法的估計(jì)準(zhǔn)確率優(yōu)于Low Bound算法，但標(biāo)簽選擇時(shí)隙的概率并不嚴(yán)格服從泊松分布，這就造成算法效率的不穩(wěn)定，同時(shí)在標(biāo)簽規(guī)模過(guò)大的情況下也不適用。基于空閑時(shí)隙估計(jì)算法主要思想是根據(jù)一幀中空閑時(shí)隙的理論期望值與實(shí)驗(yàn)中統(tǒng)計(jì)得出的空閑時(shí)隙數(shù)值的關(guān)系進(jìn)行標(biāo)簽數(shù)量的估計(jì)。文獻(xiàn)[7]中提出的Adaptive Slotted ALOHA Protocol標(biāo)簽估計(jì)算法與文獻(xiàn)[8]中提出的Fast Zero Estimation算法都是基于空閑時(shí)隙的標(biāo)簽估計(jì)算法。但隨著標(biāo)簽規(guī)模的增大，幀長(zhǎng)度卻不能一直增大，一個(gè)時(shí)隙為空閑時(shí)隙的概率會(huì)越來(lái)越小，因此基于空閑時(shí)隙的估計(jì)算法準(zhǔn)確度也會(huì)下降。

基于切比雪夫不等式的估計(jì)算法由H．Vogt提出，利用空閑時(shí)隙、識(shí)別時(shí)隙、碰撞時(shí)隙的統(tǒng)計(jì)量與理論期望值的距離進(jìn)行標(biāo)簽數(shù)量估計(jì)。搜索使得該距離取得最小值的理論期望值并確定其所對(duì)應(yīng)的標(biāo)簽數(shù)量Ntag。定義兩個(gè)空間向量(NE,NS,NC)、(N0(L,n),N1(L,n),Nx(L,n))分別代表時(shí)隙統(tǒng)計(jì)值與時(shí)隙理論期望值。其中NE、NS、NC分別為空閑時(shí)隙、識(shí)別時(shí)隙、碰撞時(shí)隙的統(tǒng)計(jì)量；N0(L,n),N1(L,n),Nx(L,n)分別代表幀長(zhǎng)為L(zhǎng)，標(biāo)簽數(shù)量為n時(shí)空閑時(shí)隙、識(shí)別時(shí)隙、碰撞時(shí)隙的理論期望值，則Ntag為：

(2)

切比雪夫估計(jì)算法相比于Low Bound和Schoute具有更高的估計(jì)準(zhǔn)確率，但是估計(jì)過(guò)程中運(yùn)算量過(guò)大，不適合性能有限的嵌入式系統(tǒng)。文獻(xiàn)[11]提出的基于最大后驗(yàn)概率的估計(jì)算法，不同于其他基于各時(shí)隙分布期望值的估計(jì)算法，此算法將最大后驗(yàn)概率準(zhǔn)則應(yīng)用到標(biāo)簽數(shù)量估計(jì)中，提高了估計(jì)的精度。但因?yàn)楣烙?jì)過(guò)程中搜索范圍太大需要進(jìn)行多次的運(yùn)算，同樣存在估計(jì)運(yùn)算量過(guò)大的問(wèn)題。

上述的估計(jì)算法雖然有各自的優(yōu)勢(shì)，但都存在一定的問(wèn)題。解析式估計(jì)算法由于方法關(guān)系式固定，難以適應(yīng)標(biāo)簽數(shù)動(dòng)態(tài)變化較大、標(biāo)簽數(shù)量較多等場(chǎng)景。區(qū)間搜索估計(jì)算法實(shí)現(xiàn)復(fù)雜、計(jì)算量大，難以在性能較差的嵌入式設(shè)備中使用。

2 粗精標(biāo)簽估計(jì)算法

2.1 粗精標(biāo)簽估計(jì)算法流程

粗精標(biāo)簽估計(jì)算法結(jié)合粗估計(jì)的快速、精估計(jì)的準(zhǔn)確和二次估計(jì)算法性能的穩(wěn)定性，使得估計(jì)算法效率更高，適應(yīng)場(chǎng)景更廣。圖1為算法的流程。

圖1 粗精二次標(biāo)簽估計(jì)流程

基于粗精二次估計(jì)的RFID標(biāo)簽估計(jì)算法主要分為三部分：標(biāo)簽的粗估計(jì)、評(píng)估粗估計(jì)值的可信度、標(biāo)簽的精估計(jì)。首先初始幀長(zhǎng)為L(zhǎng)，進(jìn)行一次讀取后統(tǒng)計(jì)該讀取周期內(nèi)的反饋信息：空閑時(shí)隙數(shù)E、識(shí)別時(shí)隙數(shù)S、碰撞時(shí)隙數(shù)C。利用這些反饋信息計(jì)算碰撞時(shí)隙所占總時(shí)隙的比例Bc=C/L。根據(jù)建模分析得出的Bc與每個(gè)碰撞時(shí)隙中平均標(biāo)簽數(shù)nu的關(guān)系構(gòu)建出的解析式粗估計(jì)算法的表達(dá)式來(lái)計(jì)算第一次標(biāo)簽估計(jì)值Nr。粗估計(jì)之后需要對(duì)估計(jì)值Nr進(jìn)行評(píng)估，評(píng)估標(biāo)準(zhǔn)由統(tǒng)計(jì)分析大量實(shí)驗(yàn)中讀取周期內(nèi)空閑時(shí)隙的比例范圍得出，可隨應(yīng)用場(chǎng)景調(diào)整。若粗估計(jì)值滿足評(píng)估要求，則對(duì)標(biāo)簽的估計(jì)完成。反之，需要進(jìn)行二次精估計(jì)。精估計(jì)采用基于先驗(yàn)知識(shí)的最大后驗(yàn)概率估計(jì)算法。設(shè)定粗估計(jì)值Nr為二次精估計(jì)搜索的起點(diǎn)，通過(guò)一次后驗(yàn)概率的計(jì)算來(lái)確定搜索的方向，然后按照確定的起點(diǎn)與方向進(jìn)行最大后驗(yàn)概率搜索，當(dāng)滿足搜索停止條件時(shí)停止搜索，并輸出當(dāng)前的標(biāo)簽估計(jì)值。

2.2 解析式粗估計(jì)

解析式粗估計(jì)的數(shù)學(xué)模型定義如下：設(shè)閱讀器使用幀長(zhǎng)度L，對(duì)N個(gè)標(biāo)簽進(jìn)行讀取，則選擇同一時(shí)隙的標(biāo)簽數(shù)量為r，概率為P=1/L的二項(xiàng)分布。

(3)

可以得出空閑時(shí)隙概率Pe、碰撞時(shí)隙概率Pc、識(shí)別時(shí)隙概率Ps。

Pe=B(r=0)=(1-p)N

(4)

Ps=B(r=1)=Np(1-p)N-1

(5)

Pc=B(r=x)=1-Pe-Ps

(6)

一次讀取后統(tǒng)計(jì)出一幀中空閑時(shí)隙數(shù)為E、碰撞時(shí)隙數(shù)為C、識(shí)別時(shí)隙數(shù)為S，且E+S+C=L。

以此數(shù)學(xué)模型為基礎(chǔ)有幾種解析式估計(jì)方法。Low Bound估計(jì)算法與Schoute估計(jì)算法都是在假設(shè)每個(gè)碰撞時(shí)隙中的標(biāo)簽數(shù)量的基礎(chǔ)上進(jìn)行標(biāo)簽的估計(jì)，而每個(gè)碰撞時(shí)隙中標(biāo)簽的數(shù)量為固定的值，并不能隨標(biāo)簽規(guī)模的增大而變化，所以隨著標(biāo)簽規(guī)模增大估計(jì)誤差也會(huì)大幅增加?？臻e時(shí)隙標(biāo)簽估計(jì)算法優(yōu)于以上兩種估計(jì)算法的原因是可以根據(jù)空閑時(shí)隙所占比例的變化動(dòng)態(tài)地估計(jì)標(biāo)簽的數(shù)量。如圖2所示空閑時(shí)隙的比例在N/L大于2.5時(shí)變化趨于平緩，標(biāo)簽數(shù)量的增加已經(jīng)不能通過(guò)空閑時(shí)隙的比例得到體現(xiàn)，所以空閑時(shí)隙標(biāo)簽估計(jì)算法已經(jīng)不再適用。根據(jù)這個(gè)思路觀察圖2可以看出。

圖2 三種時(shí)隙的比例與N/L的關(guān)系

碰撞時(shí)隙所占比例Bc隨N/L增加呈現(xiàn)單調(diào)變化，同時(shí)更加接近線性變化。所以用Bc來(lái)估計(jì)標(biāo)簽數(shù)量效果會(huì)更好。由于估計(jì)算法初始幀長(zhǎng)固定，所以估計(jì)算法應(yīng)不受不同幀長(zhǎng)的影響。經(jīng)過(guò)建模分析得出每個(gè)碰撞時(shí)隙中平均標(biāo)簽數(shù)nu與碰撞時(shí)隙的比例Bc的關(guān)系不受幀長(zhǎng)度影響。

圖3是幀長(zhǎng)L分別為128、256、512，標(biāo)簽數(shù)從100～1 000的條件下，進(jìn)行10 000次實(shí)驗(yàn)統(tǒng)計(jì)所得。由圖2可知，N/L小于2時(shí)，Bc小于0.6，N/L小于4時(shí)，Bc小于0.9。圖3中點(diǎn)的分布與此一致，可以看出：同等標(biāo)簽數(shù)量在不同幀長(zhǎng)條件下nu與Bc的關(guān)系穩(wěn)定；當(dāng)Bc變化時(shí)，nu的變化呈現(xiàn)一定的規(guī)律性。按照nu的變化率可劃分成三個(gè)階段，對(duì)三個(gè)階段分別進(jìn)行函數(shù)擬合。

圖3 不同幀長(zhǎng)下nu與Bc關(guān)系

圖4為nu與Bc的分段擬合圖，獲得三段擬合曲線的數(shù)學(xué)表達(dá)式：

(7)

根據(jù)擬合曲線的數(shù)學(xué)表達(dá)式，閱讀器在一次搜索后依據(jù)反饋信息可以簡(jiǎn)單地獲取nu的值，進(jìn)而得出標(biāo)簽數(shù)粗估計(jì)的結(jié)果Nr。

Nr=nu×C+S

(8)

2.3 標(biāo)簽估計(jì)值評(píng)價(jià)過(guò)程與標(biāo)準(zhǔn)

設(shè)定評(píng)價(jià)標(biāo)準(zhǔn)來(lái)評(píng)價(jià)粗估計(jì)得到結(jié)果的準(zhǔn)確性，決定是否需要進(jìn)行第二次估計(jì)。

圖5是不同實(shí)驗(yàn)條件下，一個(gè)讀取周期后空閑時(shí)隙占總時(shí)隙比例分布圖。圖中理論值隨著標(biāo)簽數(shù)量的變化穩(wěn)定在0.367；實(shí)驗(yàn)數(shù)據(jù)是在最優(yōu)幀長(zhǎng)條件下(即L=N)，空閑時(shí)隙所占比例的分布；誤差1(模擬標(biāo)簽估計(jì)值大于實(shí)際值)為在標(biāo)簽數(shù)量大于幀長(zhǎng)5%的條件下，空閑時(shí)隙所占比例的分布；誤差2(模擬標(biāo)簽估計(jì)值小于估計(jì)值)為在標(biāo)簽數(shù)量小于幀長(zhǎng)5%的條件下，空閑時(shí)隙所占比例的分布。

圖4 Bc與nu分段擬合圖

圖5 空閑時(shí)隙所占比例分布

分析圖5可知，當(dāng)標(biāo)簽估計(jì)誤差超過(guò)5%時(shí)，空閑時(shí)隙所占比例分布與估計(jì)準(zhǔn)確的情況下的分布有很大不同。在標(biāo)簽數(shù)量小于200時(shí)分布有10%的重合，因?yàn)闃?biāo)簽數(shù)量小于200時(shí)粗估計(jì)的準(zhǔn)確度高，所以重合部分影響很小。根據(jù)上述規(guī)律，可以設(shè)計(jì)基于空閑時(shí)隙比例的標(biāo)簽估計(jì)值評(píng)價(jià)標(biāo)準(zhǔn)。如表1所示，不同的標(biāo)簽數(shù)量對(duì)應(yīng)著不同的空閑時(shí)隙比例范圍。進(jìn)行標(biāo)簽估計(jì)值評(píng)估的過(guò)程為：

1)根據(jù)粗估計(jì)的標(biāo)簽數(shù)量初始化閱讀器評(píng)估指標(biāo)。

2)設(shè)置幀長(zhǎng)L為當(dāng)前估計(jì)值的最優(yōu)幀長(zhǎng)。

3)閱讀器進(jìn)行一次讀取并統(tǒng)計(jì)這次讀取周期內(nèi)的空閑時(shí)隙個(gè)數(shù)。

4)根據(jù)L計(jì)算空閑時(shí)隙所占的比例并判斷是否符合評(píng)估的標(biāo)準(zhǔn)。

5)若空閑時(shí)隙所占比例符合評(píng)估標(biāo)準(zhǔn)，粗估計(jì)的標(biāo)簽數(shù)量為可信值；反之，粗估計(jì)的標(biāo)簽數(shù)量不可信，需進(jìn)行二次精估計(jì)。

表1 標(biāo)簽估計(jì)值評(píng)價(jià)標(biāo)準(zhǔn)

1 000次最優(yōu)幀長(zhǎng)條件下的實(shí)驗(yàn)中有大約95%空閑時(shí)隙比例在標(biāo)準(zhǔn)比例范圍中，標(biāo)簽估計(jì)值準(zhǔn)確的情況下評(píng)估準(zhǔn)確率為95%。標(biāo)簽估計(jì)值誤差為5%時(shí)，2 000次實(shí)驗(yàn)中有9%在標(biāo)準(zhǔn)比例范圍內(nèi)，且大多都集中在標(biāo)簽數(shù)量小于200的區(qū)間，若標(biāo)簽估計(jì)誤差合格范圍設(shè)為5%，則標(biāo)簽估計(jì)值錯(cuò)誤的情況下評(píng)估的準(zhǔn)確率最小為91%。綜上，基于空閑時(shí)隙的標(biāo)簽估計(jì)值評(píng)估標(biāo)準(zhǔn)對(duì)標(biāo)簽粗估計(jì)值的評(píng)估準(zhǔn)確率可以達(dá)到92%。

2.4 基于先驗(yàn)知識(shí)的后驗(yàn)概率分布標(biāo)簽精估計(jì)

將幀時(shí)隙ALOHA防碰撞算法對(duì)標(biāo)簽的一次讀取過(guò)程建?？醋骶哂兄貜?fù)獨(dú)立實(shí)驗(yàn)的多項(xiàng)分布(每個(gè)實(shí)驗(yàn)為幀中的一個(gè)時(shí)隙)，其中每個(gè)實(shí)驗(yàn)有三個(gè)結(jié)果：空時(shí)隙、識(shí)別時(shí)隙、碰撞時(shí)隙；且每個(gè)時(shí)隙是空時(shí)隙的概率為Pe，是識(shí)別時(shí)隙的概率為Ps，是碰撞時(shí)隙的概率為Pc，約束條件為Pe+Ps+Pc=1。

在幀長(zhǎng)L的讀取過(guò)程中，空時(shí)隙數(shù)量為E，識(shí)別時(shí)隙數(shù)量為S，碰撞時(shí)隙數(shù)量為C，這種情況發(fā)生的概率為P(E,S,C)。

(9)

P(E,S,C)為(Pe+Ps+Pc)L多項(xiàng)式展開的一般項(xiàng)。因此，對(duì)于具有幀長(zhǎng)度L的讀取周期，當(dāng)幀中時(shí)隙的分布為E個(gè)空時(shí)隙、S個(gè)識(shí)別時(shí)隙和C個(gè)碰撞時(shí)隙時(shí)，對(duì)于標(biāo)簽數(shù)量n具有后驗(yàn)概率，如下：

[(1-1/L)n]E[(n/L)(1-1/L)(n-1)]S×

[1-(1-1/L)n-(n/L)(1-1/L)(n-1)]C

(10)

基于后驗(yàn)概率分布，確定使得概率最大化的標(biāo)簽數(shù)量n。因此，利用后驗(yàn)概率估計(jì)標(biāo)簽數(shù)量的決策規(guī)則為：搜索標(biāo)簽數(shù)量ng=n使得P(n|E,S,C)取得最大值。

在一次讀取周期中，若沒(méi)有先驗(yàn)知識(shí)進(jìn)行標(biāo)簽數(shù)量ng的搜索則不能確定大致的搜索范圍，而每次搜索計(jì)算P(n|E,S,C)的運(yùn)算量很大。這就導(dǎo)致標(biāo)簽估計(jì)算法的效率很差，甚至在一些計(jì)算性能有限的系統(tǒng)中無(wú)法應(yīng)用。

針對(duì)這一問(wèn)題，提出基于解析式粗估計(jì)值的后驗(yàn)概率標(biāo)簽估計(jì)方法。該方法利用解析式估計(jì)的結(jié)果作為先驗(yàn)知識(shí)，根據(jù)粗估計(jì)的值Nr確定搜索的大致范圍，通過(guò)結(jié)合Nr的大小和解析式估計(jì)的特點(diǎn)，決定搜索方向。

根據(jù)圖6所示，后驗(yàn)概率隨標(biāo)簽數(shù)量的變化呈正態(tài)分布。在進(jìn)行后驗(yàn)概率最優(yōu)搜索時(shí)，以粗估計(jì)標(biāo)簽數(shù)量值Nr為開始，根據(jù)解析式估計(jì)在不同Nr大小時(shí)估計(jì)誤差分布情況選擇向前或向后搜索。

圖6 不同標(biāo)簽數(shù)量下的后驗(yàn)概率分布

確定搜索結(jié)束的不同情況：第一次搜索利用Nr計(jì)算出后驗(yàn)概率P1。根據(jù)確定的方向進(jìn)行第二次搜索，會(huì)出現(xiàn)兩種情況。

1)若第二次搜索的后驗(yàn)概率P2>P1，繼續(xù)按照此方向搜索，當(dāng)后驗(yàn)概率值不再增加時(shí)，停止搜索，前一次搜索的n值即為標(biāo)簽的估計(jì)數(shù)。

2)若第二次搜索的后驗(yàn)概率P2

基于先驗(yàn)知識(shí)的最大后驗(yàn)概率標(biāo)簽估計(jì)算法工作流程如圖7所示。

圖7 基于先驗(yàn)知識(shí)的最大后驗(yàn)概率估計(jì)算法流程

基于解析式粗估計(jì)值的后驗(yàn)概率標(biāo)簽估計(jì)方法相較于基于后驗(yàn)概率的標(biāo)簽估計(jì)方法能減少大約90%的搜索范圍，極大地降低了估計(jì)算法的運(yùn)算量，提高了算法的運(yùn)行效率。

3 算法仿真與分析

為了衡量基于粗精二次估計(jì)的RFID標(biāo)簽數(shù)目估算方法的性能，進(jìn)行了基于Matlab軟件平臺(tái)的仿真測(cè)試。與之前的算法進(jìn)行比較，從估計(jì)誤差、穩(wěn)定性和運(yùn)算量的大小三方面來(lái)說(shuō)明算法的性能。初始幀長(zhǎng)設(shè)為128，標(biāo)簽量級(jí)為1 000以內(nèi)。

3.1 估算誤差

估計(jì)誤差ε作為評(píng)估標(biāo)簽估計(jì)方法準(zhǔn)確性的指標(biāo)，定義如式(11)所示，其中Ns為實(shí)際標(biāo)簽數(shù)，Ng為標(biāo)簽估計(jì)值。

ε=|Ns-Ng|/Ns

(11)

在標(biāo)簽隨機(jī)分布的情況下不同估計(jì)方法的誤差如圖8所示，隨著標(biāo)簽數(shù)量的增加，不同標(biāo)簽估計(jì)方法的誤差率變化趨勢(shì)各異。Low Bound估計(jì)方法與Schoute估計(jì)方法誤差變化趨勢(shì)相近，Schoute估計(jì)方法在各個(gè)階段均優(yōu)于Low Bound估計(jì)方法。解析式估計(jì)的誤差率隨著標(biāo)簽數(shù)量的增加呈現(xiàn)出不穩(wěn)定狀態(tài)，估算誤差在標(biāo)簽數(shù)量小于400時(shí)保持在5%以下，但在標(biāo)簽數(shù)量為500時(shí)誤差率卻達(dá)到10.33%；之后估算誤差率保持在10%以下，但在標(biāo)簽數(shù)量為800時(shí)誤差率劇增為42.38%。后驗(yàn)概率標(biāo)簽估計(jì)方法的誤差率隨著標(biāo)簽數(shù)量的增加變化比較平緩，誤差率保持在5%～10%?；诖志喂烙?jì)的標(biāo)簽估計(jì)算法的誤差率隨標(biāo)簽數(shù)量增加變化最平緩且誤差率最低，算法的平均誤差率為3.8%。

圖8 不同標(biāo)簽數(shù)下不同估計(jì)方法誤差比較

為了進(jìn)一步評(píng)估不同估計(jì)算法的性能，固定標(biāo)簽數(shù)量，對(duì)各個(gè)估計(jì)算法在不同標(biāo)簽分布情況下的誤差進(jìn)行了比較。設(shè)定標(biāo)簽數(shù)量為500，標(biāo)簽分布分散級(jí)別為從1～10，級(jí)別1表示標(biāo)簽整體隨機(jī)分布，位置沒(méi)有明顯規(guī)律，級(jí)別2表示標(biāo)簽聚集在2個(gè)不同位置上，以此類推級(jí)別10表示標(biāo)簽聚集在10個(gè)不同位置上。各個(gè)估計(jì)算法估計(jì)誤差如圖9所示。

圖9 不同標(biāo)簽分布下各個(gè)估計(jì)方法誤差比較

隨著標(biāo)簽分布分散程度級(jí)別的增加，Low bound估計(jì)算法和Schoute估計(jì)算法誤差率只有小幅的上升，但誤差率都在40%以上。解析式估計(jì)算法的誤差率從級(jí)別1到級(jí)別5表現(xiàn)平穩(wěn)，保持在10%以下，但在級(jí)別5之后有大幅的增加，誤差率在級(jí)別10時(shí)達(dá)到30%。最大后驗(yàn)概率估計(jì)算法的誤差率前期表現(xiàn)與解析式估計(jì)算法相近，在級(jí)別5之下誤差率保持在9%以下，但之后也出現(xiàn)了小幅的上升，最后誤差率穩(wěn)定在15%左右。粗精二次估計(jì)算法的誤差率一直保持在5%以下，在級(jí)別7之后有小幅上升，但誤差率一直保持10%以下。在不同標(biāo)簽分布分散級(jí)別下，粗精估計(jì)算法平均誤差率為6%。

綜上所述，相較于其他幾種估算方法，粗精二次估計(jì)算法在不同標(biāo)簽數(shù)量和不同標(biāo)簽分布情況下的平均誤差率都保持最低，所以粗精二次估計(jì)算法標(biāo)簽估計(jì)的結(jié)果更準(zhǔn)確。

3.2 估計(jì)穩(wěn)定性

標(biāo)簽估計(jì)是對(duì)一個(gè)隨機(jī)過(guò)程進(jìn)行估計(jì)，不可避免地會(huì)出現(xiàn)隨機(jī)性誤差，估計(jì)算法應(yīng)該具備一定抵抗隨機(jī)性誤差的能力，這種能力被稱為估計(jì)穩(wěn)定性。定義估計(jì)穩(wěn)定性的量化指標(biāo)α=Kc/Kz，其中Kz為總的實(shí)驗(yàn)次數(shù)，Kc為估計(jì)成功的實(shí)驗(yàn)次數(shù)。估計(jì)成功定義為誤差率小于5%。量化指標(biāo)α的數(shù)值越大說(shuō)明估計(jì)算法的穩(wěn)定性越高，通過(guò)量化指標(biāo)α來(lái)說(shuō)明估計(jì)算法的穩(wěn)定性。每個(gè)估計(jì)算法進(jìn)行10 000次實(shí)驗(yàn)，次數(shù)在不同的標(biāo)簽數(shù)量下平均分布。

不同標(biāo)簽估計(jì)算法的穩(wěn)定性如圖10所示，隨著標(biāo)簽數(shù)量的增加，不同估計(jì)算法穩(wěn)定性變化各異。Low Bound估計(jì)算法和Schoute估計(jì)算法的穩(wěn)定性極差，在標(biāo)簽數(shù)量為100時(shí)取得最大值，分別為0.36、0.79，之后穩(wěn)定性急劇下降。解析式估計(jì)穩(wěn)定性相較于前兩者有了大幅的提高，但隨著標(biāo)簽數(shù)量的增加降低幅度太大，在標(biāo)簽數(shù)大于300時(shí)穩(wěn)定性已經(jīng)在0.6以下，之后穩(wěn)定性總體呈下降趨勢(shì)。后驗(yàn)概率估計(jì)穩(wěn)定性在標(biāo)簽數(shù)量小于400時(shí)可以達(dá)到0.8以上，同時(shí)穩(wěn)定性下降幅度也小于解析式估計(jì)。粗精二次估計(jì)由于結(jié)合了解析式估計(jì)與后驗(yàn)概率估計(jì)，具有更強(qiáng)的抵抗隨機(jī)性誤差的能力，其穩(wěn)定性表現(xiàn)優(yōu)于其余的估計(jì)算法。在標(biāo)簽數(shù)量小于600時(shí)穩(wěn)定性變化幅度平緩保持在0.9以上，之后穩(wěn)定性下降幅度有所增加，但相較于其他估計(jì)算法還是具有明顯優(yōu)勢(shì)。

圖10 不同估計(jì)方法穩(wěn)定性比較

3.3 估計(jì)運(yùn)算量

由于嵌入式設(shè)備的性能限制，標(biāo)簽估計(jì)算法在保持估計(jì)的準(zhǔn)確性與穩(wěn)定性的同時(shí)還需控制算法的運(yùn)算量。

表2所示為不同標(biāo)簽估計(jì)算法的性能指標(biāo)對(duì)比。粗精二次估計(jì)算法通過(guò)結(jié)合解析式估計(jì)與后驗(yàn)概率估計(jì)的優(yōu)點(diǎn)，在保證低誤差與高穩(wěn)定性的同時(shí)降低算法的運(yùn)算量。

表2 不同標(biāo)簽估計(jì)算法比較

圖11為不同標(biāo)簽數(shù)量下各估計(jì)算法運(yùn)算時(shí)間的對(duì)比結(jié)果，Low Bound估計(jì)算法、Schoute估計(jì)算法與解析式估計(jì)算法的計(jì)算復(fù)雜度為O(1)，算法運(yùn)行時(shí)間不受標(biāo)簽數(shù)量的影響，隨著標(biāo)簽數(shù)量的增加，這三種算法的運(yùn)行時(shí)間沒(méi)有太大的變化。最大后驗(yàn)概率估計(jì)算法的計(jì)算復(fù)雜度為O(n2)，隨標(biāo)簽數(shù)量的增加，算法的運(yùn)行時(shí)間急劇增加。粗精二次估計(jì)算法的計(jì)算復(fù)雜度約為O(n)，隨標(biāo)簽數(shù)量增加，算法的運(yùn)算時(shí)間的增加趨勢(shì)大致呈線性。對(duì)比最大后驗(yàn)概率估計(jì)算法，粗精二次估計(jì)算法的運(yùn)行時(shí)間降低約90%。

圖11 不同標(biāo)簽估計(jì)算法的運(yùn)行時(shí)間對(duì)比

4 結(jié)語(yǔ)

通過(guò)對(duì)RFID標(biāo)簽讀寫過(guò)程的建模分析，針對(duì)現(xiàn)有標(biāo)簽估計(jì)算法存在的估計(jì)準(zhǔn)確性與算法復(fù)雜性之間的矛盾，本文提出基于粗精二次估計(jì)的RFID標(biāo)簽數(shù)目估算方法。通過(guò)仿真實(shí)驗(yàn)，該方法比其他幾種標(biāo)簽估計(jì)算法具有較低的平均誤差率，減少了標(biāo)簽識(shí)別過(guò)程中的運(yùn)算量。利用粗精二次估計(jì)使得算法對(duì)標(biāo)簽估計(jì)過(guò)程中的隨機(jī)誤差具有更強(qiáng)的抵抗能力，算法的穩(wěn)定性優(yōu)于其他幾種標(biāo)簽估計(jì)算法。在解決了估計(jì)準(zhǔn)確性與運(yùn)算量之間的矛盾的同時(shí)，其高穩(wěn)定性使得算法適用于計(jì)算性能有限的場(chǎng)景，有利于提高標(biāo)簽防碰撞算法的效率。

References)

[1] WANT R. An introduction to RFID technology [J]. IEEE Pervasive Computing, 2006, 5(1): 25-33.

[2] HE Y, WANG X. An ALOHA-based improved anti-collision algorithm for RFID systems [J]. IEEE Wireless Communications, 2013, 20(5): 152-158.

[3] 王勇,唐小虎,張莉涓.RFID系統(tǒng)中停留標(biāo)簽的組策略防碰撞算法[J].電子與信息學(xué)報(bào),2016,38(3):594-599.(WANG Y, TANG X H, ZHANG L J. Group strategy for remaining tags in anti-collision algorithm for RFID system [J]. Journal of Electronics & Information Technology, 2016, 38(3): 594-599.)

[4] 潘雪峰,曹加恒.一種改進(jìn)的動(dòng)態(tài)幀時(shí)隙ALOHA算法[J].微電子學(xué)與計(jì)算機(jī),2016,33(6):95-99.(PAN X F, CAO J H. An improved dynamic frame slotted ALOHA algorithm [J]. Microelectronics & Computer, 2016, 33(6): 95-99.)

[5] 丁治國(guó),朱學(xué)永,雷迎科,等.基于啟發(fā)式函數(shù)的多叉樹防碰撞算法[J].計(jì)算機(jī)應(yīng)用,2012,32(3):665-668.(DING Z G, ZHU X Y, LEI Y K, et al. Multi-tree anti-collision algorithm based on heuristic function [J]. Journal of Computer Applications, 2012, 32(3): 665-668.)

[6] SHAO M, JIN X, JIN L. An improved dynamic adaptive multi-tree search anti-collision algorithm based on RFID [C]// Proceedings of the 2014 International Conference on Data Science and Advanced Analytics. Piscataway, NJ: IEEE, 2014: 72-75.

[7] KHANDELWAL G, YENER A, LEE K, et al. ASAP : a MAC protocol for dense and time constrained RFID systems [C]// Proceedings of the 2006 IEEE International Conference on Communications. Piscataway, NJ: IEEE, 2006: 4028-4033.

[8] CUI Y, ZHAO Y. A fast zero estimation scheme for RFID systems [J]. Computer Communications, 2010, 33(11): 1318-1324.

[9] XU Y, CHEN Y. An improved dynamic framed slotted ALOHA anti-collision algorithm based on estimation method for RFID systems [C]// Proceedings of the 2015 IEEE International Conference on RFID. Piscataway, NJ: IEEE, 2015: 1-8.

[10] 李萌,錢志鴻,張旭,等.基于時(shí)隙預(yù)測(cè)的RFID防碰撞ALOHA算法[J].通信學(xué)報(bào),2011,32(12):43-50.(LI M, QIAN Z H, ZHANG X, et al. Slot-predicting based ALOHA algorithm for RFID anti-collision [J]. Journal on Communications, 2011, 32(12): 43-50.)

[11] CHEN W T. An accurate tag estimate method for improving the performance of an RFID anticollision algorithm based on dynamic frame length ALOHA [J]. IEEE Transactions on Automation Science and Engineering, 2009, 6(1): 9-15.

[12] AHMED H A, SALAH H, ROBERT J, et al. An efficient RFID tag estimation method using biased Chebyshev inequality for dynamic frame slotted ALOHA [C]// Proceedings of the 2014 European Conference on Smart Objects, Systems and Technologies. Piscataway, NJ: IEEE, 2015: 1-4.

[13] VOGT H. Efficient object identification with passive RFID tags [M]// International Conference on Pervasive Computing, LNCS 2414. Berlin: Springer, 2002: 98-113.

EstimationmethodforRFIDtagsbasedonroughandfinedoubleestimation

DING Jianli1,2, HAN Yuchao1*, WANG Jialiang1

(1.CollegeofComputerScienceandTechnology,CivilAviationonUniversityofChina,Tianjin300300,China;2.TianjinKeyLabforAdvancedSignalProcessing(CivilAviationonUniversityofChina),Tianjin300300,China)

To solve the contradiction between the estimation accuracy and the calculation amount of the RFID tag estimation method, and the instability of the estimation method performance caused by the randomness of the tag reading process in the field of aviation logistics networking information gathering. Based on the idea of complementary advantages, a method for estimating the number of RFID tags based on rough and fine estimation was proposed. By modeling and analyzing the tag reading process of framed ALOHA algorithm, the mathematical model between the average number of tags in the collision slot and the proportion of the collision slot was established. Rough number estimation based on the model was made, and then, according to the value of rough estimation, the reliability of rough estimation was evaluated. The Maximum A Posteriori (MAP) estimation algorithm based on the value of rough estimation as priori knowledge was used to improve the estimation accuracy. Compared to the original maximum posteriori probability estimation algorithm, the search range can be reduced up to 90%. The simulation results show that, the average error of the RFID tag number estimation based on rough and fine estimation is 3.8%, the stability of the estimation method is significantly improved, and the computational complexity is greatly reduced. The proposed algorithm can be effectively applied to the information collection process aviation logistics networking.

Radio Frequency Identification (RFID) anti-collision algorithm; rough and fine double estimation; estimation of number of tags; Maximum A Posteriori (MAP) estimation; modeling analysis

2017- 03- 31;

2017- 05- 17。

民航局科技創(chuàng)新重大專項(xiàng)(MHRD20140106, MHRD20150107)；中國(guó)民航大學(xué)中央高?；鹳Y助項(xiàng)目(3122016A001, 3122015C020)。

丁建立(1963—)，男，河南洛陽(yáng)人，教授，博士，CCF會(huì)員，主要研究方向：民航智能信息處理、航空物聯(lián)網(wǎng)； 韓宇超(1992—)，男，陜西扶風(fēng)人，碩士研究生，主要研究方向：航空物聯(lián)網(wǎng); 王家亮(1983—)，男，遼寧遼陽(yáng)人，講師，博士，主要研究方向：民航信息系統(tǒng)。

1001- 9081(2017)09- 2722- 06

10.11772/j.issn.1001- 9081.2017.09.2722

TP391.5

A

This work is partially supported by the Major Projects of Civil Aviation Technology Innovation Funds of China (MHRD20140106, MHRD20150107), the Fundamental Research Funds for the Central Universities of Civil Aviation University of China (3122016A001, 3122015C020).

DINGJianli, born in 1963, Ph. D., professor. His research interests include civil aviation intelligent information processing, aviation logistics networking.

HANYuchao, born in 1992, M. S. candidate. His research interests include aviation logistics networking.

WAGJialiang, born in 1983, Ph. D., lecturer. His research interests include civil aviation information system.