姚金玲 劉 婕 閆雪鋒

(1.天津職業(yè)大學(xué)，天津 300410；2.天津理工大學(xué)天津市先進(jìn)機(jī)電系統(tǒng)設(shè)計(jì)與智能控制重點(diǎn)實(shí)驗(yàn)室，天津 300384；3.天津職業(yè)技術(shù)師范大學(xué)，天津 300110)

隨著信息技術(shù)的快速發(fā)展，射頻識(shí)別(Radio Frequency Identification，RFID)技術(shù)由于其非接觸式信息交互、安全可靠信息傳輸、靈活快捷標(biāo)識(shí)追溯等優(yōu)點(diǎn)而被廣泛用于工業(yè)、農(nóng)業(yè)和商業(yè)等領(lǐng)域[1]。在食品質(zhì)量追溯過(guò)程中，尤其是在運(yùn)輸和倉(cāng)儲(chǔ)中，需要對(duì)整車(chē)貨品標(biāo)簽進(jìn)行批量識(shí)別。多標(biāo)簽識(shí)別是RFID最為明顯的優(yōu)勢(shì)，但當(dāng)多個(gè)標(biāo)簽同時(shí)發(fā)送標(biāo)識(shí)信息時(shí)，其發(fā)送信號(hào)會(huì)在數(shù)據(jù)傳輸?shù)阶x取器時(shí)發(fā)生干擾形成碰撞[2]。碰撞不僅會(huì)降低系統(tǒng)的識(shí)別效率，還會(huì)導(dǎo)致識(shí)別時(shí)間變長(zhǎng)，一定程度上限制了RFID技術(shù)的應(yīng)用。

國(guó)內(nèi)外學(xué)者對(duì)基于RFID標(biāo)簽沖突檢測(cè)的防碰撞算法進(jìn)行了大量研究，并取得了一定的成果，大部分防碰撞算法研究集中在ALOHA算法和二叉樹(shù)算法。王祖良等[3]提出了一種用于農(nóng)產(chǎn)品可追溯性的標(biāo)簽防碰撞自適應(yīng)動(dòng)態(tài)幀時(shí)隙ALOHA算法，該方法適用于設(shè)計(jì)的農(nóng)產(chǎn)品追溯系統(tǒng)，大大提高了識(shí)別效率。與廣泛采用的國(guó)際標(biāo)準(zhǔn)相比，吞吐量提升了30%。潘雪峰等[4]提出了一種結(jié)合動(dòng)態(tài)幀時(shí)隙ALOHA算法和生日悖論概率理論的RFID系統(tǒng)防碰撞算法，該方法可以有效提高標(biāo)簽識(shí)別的準(zhǔn)確性，減少識(shí)別過(guò)程的時(shí)間，提高射頻系統(tǒng)信道的利用率及系統(tǒng)性能。尚弘[5]提出了一種基于搜索樹(shù)的輕量級(jí)防碰撞方法，并設(shè)計(jì)了一種新的查詢(xún)響應(yīng)模式(單查詢(xún)—雙響應(yīng))，可以提高標(biāo)簽識(shí)別的效率。結(jié)果表明，采用雙響應(yīng)模式和計(jì)數(shù)器觸發(fā)的單查詢(xún)模式可將整體通信開(kāi)銷(xiāo)減少42%。賀曉霞等[6]提出了一種基于鎖定位的并行二進(jìn)制分區(qū)(LPBS)防碰撞算法，該算法減少了讀取器和標(biāo)簽之間發(fā)送的位數(shù)，同時(shí)降低了競(jìng)爭(zhēng)時(shí)隙。仿真結(jié)果表明，大多數(shù)情況下，該算法在吞吐量和延遲方面均優(yōu)于傳統(tǒng)的防碰撞算法。但是，上述研究并沒(méi)有全完消除空閑時(shí)隙，造成一部分時(shí)間和資源浪費(fèi)，具有一定的局限性。

在食品質(zhì)量追溯過(guò)程中，多標(biāo)簽識(shí)別是追溯的關(guān)鍵，而多標(biāo)簽識(shí)別不可避免地會(huì)產(chǎn)生碰撞。針對(duì)目前防碰撞算法查詢(xún)時(shí)間過(guò)程會(huì)產(chǎn)生大量的沉余，增加通信開(kāi)銷(xiāo)，文章擬結(jié)合幀時(shí)隙ALOHA(Frame Slotted ALOHA, FSA)算法和最小均方誤差(Minimum Mean Square Error, MMSE)預(yù)編碼技術(shù)，提出一種RFID多標(biāo)簽識(shí)別防碰撞算法，即預(yù)編碼幀時(shí)隙ALOHA算法，旨在為RFID多標(biāo)簽技術(shù)的發(fā)展提供依據(jù)。

1 RFID多標(biāo)簽識(shí)別技術(shù)基礎(chǔ)

1.1 RFID系統(tǒng)構(gòu)成及工作原理

RFID系統(tǒng)由標(biāo)簽、天線(xiàn)、讀取器和后臺(tái)數(shù)據(jù)庫(kù)系統(tǒng)4部分組成(圖1)。每個(gè)標(biāo)簽都有一個(gè)唯一的ID號(hào)，該ID號(hào)使用電磁波和天線(xiàn)進(jìn)行數(shù)據(jù)交換和能量傳輸[7]。天線(xiàn)是位于RFID系統(tǒng)標(biāo)簽和讀取器之間的數(shù)據(jù)收發(fā)器。讀取器是RFID系統(tǒng)的信息傳輸站，負(fù)責(zé)讀取和寫(xiě)入標(biāo)簽信息。后端數(shù)據(jù)庫(kù)系統(tǒng)由中間件和信息處理等內(nèi)部組件組成，對(duì)信息進(jìn)行采集、分類(lèi)、分析等[8]，還可以控制閱讀器和電子標(biāo)簽之間的雙向標(biāo)識(shí)。

1.后臺(tái)數(shù)據(jù)庫(kù) 2.讀取器 3.天線(xiàn) 4.RFID標(biāo)簽 5.待識(shí)別食品

RFID的基本工作原理：在后臺(tái)數(shù)據(jù)庫(kù)系統(tǒng)的控制下，讀取器通過(guò)天線(xiàn)將特定頻率的電磁信號(hào)發(fā)送到標(biāo)簽，標(biāo)簽接收到該信號(hào)后，便會(huì)通過(guò)改變自身的阻抗來(lái)存儲(chǔ)ID，信息被調(diào)制并反射回來(lái)。閱讀器通過(guò)天線(xiàn)接收反射信號(hào)，對(duì)標(biāo)簽信息進(jìn)行解調(diào)和解碼，然后將其發(fā)送到數(shù)據(jù)庫(kù)系統(tǒng)。后臺(tái)數(shù)據(jù)庫(kù)系統(tǒng)將根據(jù)接收到的信息執(zhí)行相應(yīng)的動(dòng)作。

由于電子標(biāo)簽和讀取器通過(guò)非接觸進(jìn)行信號(hào)傳輸，因此在進(jìn)行多數(shù)據(jù)傳輸時(shí)有干擾的可能，嚴(yán)重時(shí)會(huì)導(dǎo)致傳輸失敗[9]。RFID系統(tǒng)碰撞可分為標(biāo)簽—標(biāo)簽碰撞、標(biāo)簽—讀取器碰撞、讀取器—讀取器碰撞3類(lèi)。文章主要針對(duì)標(biāo)簽—標(biāo)簽碰撞問(wèn)題進(jìn)行相關(guān)算法和RFID多標(biāo)簽識(shí)別防碰撞算法改進(jìn)。

1.2 幀時(shí)隙ALOHA算法

RFID多標(biāo)簽識(shí)別防碰撞算法包括基于樹(shù)搜索的算法系列和基于ALOHA的算法系列。幀時(shí)隙ALOHA(FSA)算法與時(shí)隙ALOHA算法的最大區(qū)別為時(shí)隙ALOHA算法將識(shí)別周期劃分為不同的時(shí)隙間隔[10]。FSA是一個(gè)由多個(gè)時(shí)隙組成的幀，并且該時(shí)隙由多個(gè)時(shí)間段組成。在數(shù)據(jù)傳輸過(guò)程中，每個(gè)幀的大小由系統(tǒng)確定。如果標(biāo)簽需要發(fā)送數(shù)據(jù)，讀取器將隨機(jī)生成一些時(shí)隙發(fā)送給標(biāo)簽[11]。整個(gè)過(guò)程的時(shí)隙數(shù)據(jù)就是唯一的標(biāo)識(shí)號(hào)。標(biāo)簽還具有一個(gè)時(shí)隙計(jì)數(shù)器，一段時(shí)間后，時(shí)隙計(jì)數(shù)器增加1。如果時(shí)隙計(jì)數(shù)器的值等于幀中時(shí)隙的隨機(jī)數(shù)，則標(biāo)簽可以發(fā)送數(shù)據(jù)，并且在數(shù)據(jù)發(fā)送過(guò)程中不會(huì)產(chǎn)生沖突。圖2為幀時(shí)隙ALOHA算法。

圖2 幀時(shí)隙 ALOHA算法通信原理

為系統(tǒng)設(shè)置特定的幀長(zhǎng)L，待識(shí)別標(biāo)簽個(gè)數(shù)n，當(dāng)讀取器與標(biāo)簽進(jìn)行通信時(shí)，標(biāo)簽隨機(jī)選擇時(shí)隙返回序列碼信息的概率p=1/L。由于該算法基于二項(xiàng)式分布，m個(gè)標(biāo)簽在同一時(shí)隙中響應(yīng)讀取器的查詢(xún)命令的概率如式(1)所示[12]。

(1)

如果該時(shí)隙沒(méi)有標(biāo)簽響應(yīng)讀取器的查詢(xún)命令時(shí)，則該時(shí)隙為空閑時(shí)隙I，即m=0，概率如式(2)所示。

(2)

如果時(shí)隙中對(duì)查詢(xún)命令的響應(yīng)僅一個(gè)標(biāo)簽，則該時(shí)隙為成功的時(shí)隙S，即m=1，概率如式(3)所示[13]。

(3)

如果時(shí)隙中對(duì)多個(gè)同時(shí)標(biāo)記響應(yīng)閱讀器的查詢(xún)命令，則該時(shí)隙為碰撞時(shí)隙C，即m>1，該概率如式(4)所示。

Pc=1-Pi-Ps。

(4)

一個(gè)幀長(zhǎng)時(shí)間內(nèi)，成功識(shí)別標(biāo)簽的時(shí)隙數(shù)目如式(5)所示[14]。

(5)

算法系統(tǒng)的吞吐量如式(6)所示[15]。

(6)

對(duì)式(6)進(jìn)行求導(dǎo)，則

(7)

整理可得：

(8)

當(dāng)n為無(wú)窮大時(shí)，將式(8)按泰勒級(jí)數(shù)展開(kāi)，得到最優(yōu)幀長(zhǎng)[16]：

(9)

當(dāng)幀長(zhǎng)L=n時(shí)，系統(tǒng)的最大吞吐率S如式(10)所示[17]。

(10)

因此，在處理大量標(biāo)簽識(shí)別問(wèn)題時(shí)，幀長(zhǎng)等于標(biāo)簽數(shù)時(shí)，識(shí)別效率最高，識(shí)別時(shí)間最短。但是，幀時(shí)隙也有其缺點(diǎn)。如果標(biāo)簽數(shù)量較多，則不能將幀長(zhǎng)度增加到任意長(zhǎng)度值，即幀時(shí)隙是有限的。當(dāng)幀長(zhǎng)達(dá)到最大時(shí)，隨著標(biāo)簽的增加，效率逐漸下降。如果標(biāo)簽數(shù)遠(yuǎn)小于幀長(zhǎng)度，則空閑時(shí)隙較多，造成大量的時(shí)隙浪費(fèi)。

2 改進(jìn)幀時(shí)隙ALOHA算法

2.1 預(yù)編碼技術(shù)

考慮到噪聲在信息傳輸過(guò)程中的影響，采用最小均方誤差預(yù)編碼技術(shù)對(duì)幀時(shí)隙ALOHA算法進(jìn)行改進(jìn)，以最小化實(shí)際傳輸符號(hào)與接收器估計(jì)輸出值之間的差異，從而找到最優(yōu)的預(yù)編碼矩陣[18]。

argminE‖s-β-1s‖2，

(11)

(12)

式中：

β——功率影響系數(shù)；

Pt——系統(tǒng)的總發(fā)射功率，W。

當(dāng)式(12)成立時(shí)，實(shí)際傳輸信號(hào)與接收機(jī)估計(jì)輸出信號(hào)的差異最小。

根據(jù)式(12)建立拉格朗日函數(shù)，得到該函數(shù)的解：

FMMSE=HH(HHH+δI)-1，

(13)

式中：

H——信道矩陣；

δ、I——功率控制因子和單位矩陣。

(14)

式中：

(·)H——共軛轉(zhuǎn)置運(yùn)算；

(·)-1——求逆運(yùn)算；

功率歸一化因子β為[19]：

(15)

式中：

Tr(·)——跡運(yùn)算。

此時(shí)預(yù)編碼矩陣為：

(16)

預(yù)編碼模型方框圖如圖3所示。

圖3 預(yù)編碼模型

信道矩陣H由Nt根發(fā)射天線(xiàn)和Nr根接收天線(xiàn)組成Nt×Nr，通過(guò)天線(xiàn)優(yōu)化算法對(duì)信道矩陣進(jìn)行選取。

2.2 預(yù)編碼幀時(shí)隙ALOHA算法

基于預(yù)編碼技術(shù)提出了預(yù)編碼幀時(shí)隙ALOHA(MMSE-FSA算法)，該算法將一些預(yù)設(shè)時(shí)隙組合為一幀fs，并將讀取器工作輻射區(qū)的標(biāo)簽數(shù)設(shè)置為N。當(dāng)識(shí)別認(rèn)證標(biāo)簽時(shí)，標(biāo)簽隨機(jī)且獨(dú)立選擇1-fs個(gè)時(shí)隙發(fā)送響應(yīng)信號(hào)。

時(shí)隙中標(biāo)簽數(shù)量k的概率為：

(17)

時(shí)隙中標(biāo)簽數(shù)為1的概率為：

(18)

如果標(biāo)簽數(shù)量為1，此時(shí)隙中沒(méi)有碰撞，可以成功完成標(biāo)簽標(biāo)識(shí)。因此，根據(jù)式(19)可以正確識(shí)別幀中的標(biāo)簽時(shí)隙數(shù)。

(19)

則碰撞時(shí)隙數(shù)為：

fcollosion=fs-fsuccess。

(20)

2.3 MMSE-FSA算法工作流程

假設(shè)讀取器在工作輻射區(qū)有天線(xiàn)，則工作輻射區(qū)可以識(shí)別很多標(biāo)簽，標(biāo)簽數(shù)量為N，MMSE-FSA算法步驟如下：

① 當(dāng)讀取器的工作輻射區(qū)中有標(biāo)簽進(jìn)入，就會(huì)廣播一個(gè)請(qǐng)求命令，RFID系統(tǒng)開(kāi)始識(shí)別認(rèn)證。

② 識(shí)別前對(duì)所有未識(shí)別的標(biāo)簽進(jìn)行分組，并通過(guò)預(yù)編碼技術(shù)進(jìn)行預(yù)處理。通過(guò)式(14)建立預(yù)編碼矩陣，發(fā)射機(jī)發(fā)送信號(hào)為：

x=smPek，

(21)

式中：

sm——發(fā)射信號(hào)映射；

ek——信號(hào)映射的調(diào)制符號(hào)；

接收信號(hào)為：

(22)

③ 使用FSA算法對(duì)接收信號(hào)進(jìn)行識(shí)別。

④ 檢查是否識(shí)別了堆棧中的所有標(biāo)簽。如果未識(shí)別完，執(zhí)行③，否則繼續(xù)執(zhí)行下一步。

⑤ 確定所有標(biāo)簽后，算法完成。

改進(jìn)算法的流程圖如圖4所示。

圖4 改進(jìn)算法流程

3 仿真試驗(yàn)及結(jié)果分析

3.1 仿真試驗(yàn)設(shè)置

仿真設(shè)備為聯(lián)想PC機(jī)，操作系統(tǒng)為Windows 7 64位旗艦版，Intel i5 2450m CPU，2.5 GHz頻率，8 GB內(nèi)存和Matlab r2018a作為仿真平臺(tái)。將MMSE-FSA算法(幀時(shí)隙ALOHA算法和最小均方誤差預(yù)編碼技術(shù)相結(jié)合)與幀時(shí)隙ALOHA算法、后退二進(jìn)制搜索樹(shù)算法(Regressive-style Binary Search Tree，RBST)[20]進(jìn)行時(shí)隙總數(shù)、吞吐量、沖突時(shí)隙和識(shí)別時(shí)間分析。RBST算法引入標(biāo)簽狀態(tài)計(jì)數(shù)器進(jìn)行分組，利用前、后向搜索方法來(lái)減少標(biāo)簽的搜索范圍。標(biāo)簽數(shù)量N在[0,1 000]變化，50為一個(gè)間隔。

3.2 仿真結(jié)果分析

MMSE-FSA算法、幀時(shí)隙ALOHA算法和RBST算法所需總時(shí)隙數(shù)比較結(jié)果見(jiàn)圖5。由圖5可知，MMSE-FSA算法的總時(shí)隙數(shù)隨標(biāo)簽數(shù)量的增加呈線(xiàn)性增加，但是與幀時(shí)隙ALOHA算法和RBST算法相比，具有明顯的優(yōu)勢(shì)。當(dāng)標(biāo)簽總數(shù)從0～1 000變化時(shí)，幀時(shí)隙ALOHA算法生成的時(shí)隙曲線(xiàn)總數(shù)呈指數(shù)增長(zhǎng)。RBST算法生成的時(shí)隙曲線(xiàn)總數(shù)呈線(xiàn)性增長(zhǎng)。當(dāng)標(biāo)簽數(shù)為1 000時(shí)，改進(jìn)算法所需的時(shí)隙總數(shù)約為800，比幀時(shí)隙ALOHA算法少4 000，比RBST算法少1 000。因此，MMSE-FSA算法總時(shí)隙數(shù)變化最為緩慢，符合預(yù)期效果。

圖5 不同算法總時(shí)隙數(shù)變化曲線(xiàn)

MMSE-FSA算法、幀時(shí)隙ALOHA算法和RBST算法的吞吐率比較結(jié)果見(jiàn)圖6。由圖6可知，當(dāng)讀取器輻射區(qū)域內(nèi)標(biāo)簽數(shù)相同時(shí)，MMSE-FSA算法的吞吐量高于幀時(shí)隙ALOHA算法和RBST算法的。當(dāng)標(biāo)簽數(shù)為1 000時(shí)，MMSE-FSA算法的吞吐率為0.8，比幀時(shí)隙ALOHA算法和RBST算法的分別提高了340%，58%。在輻射范圍內(nèi)，MMSE-FSA算法的吞吐量可以保持在0.8左右，識(shí)別效率有了較大提升。

圖6 不同算法吞吐率變化曲線(xiàn)

圖7為MMSE-FSA算法、幀時(shí)隙ALOHA算法和RBST算法碰撞時(shí)隙數(shù)的比較結(jié)果。由圖7可知，如果標(biāo)簽總數(shù)相同，MMSE-FSA算法產(chǎn)生的碰撞時(shí)隙數(shù)最少，當(dāng)標(biāo)簽總數(shù)從0～1 000變化時(shí)，MMSE-FSA算法碰撞時(shí)隙數(shù)變化最為緩慢。當(dāng)標(biāo)簽數(shù)為1 000時(shí)，MMSE-FSA算法相比于RBST算法碰撞時(shí)隙數(shù)減少了830個(gè)，比幀時(shí)隙ALOHA算法少3 200個(gè)。

圖7 不同算法碰撞時(shí)隙數(shù)變化曲線(xiàn)

圖8為MMSE-FSA算法與幀時(shí)隙ALOHA算法和RBST算法的識(shí)別時(shí)間比較結(jié)果。由圖8可知，當(dāng)標(biāo)簽總數(shù)從0～1 000變化時(shí)，MMSE-FSA算法識(shí)別時(shí)間變化最為緩慢，比幀時(shí)隙ALOHA算法和RBST算法花費(fèi)的時(shí)間短。當(dāng)標(biāo)簽數(shù)為1 000時(shí)，MMSE-FSA算法的識(shí)別時(shí)間相比于RBST算法的降低了3.7 s，比幀時(shí)隙ALOHA算法的降低了8.2 s。MMSE-FSA算法有效降低了識(shí)別時(shí)間，相對(duì)于幀時(shí)隙ALOHA算法和RBST算法，其識(shí)別速度有了較大提升。

圖8 不同算法識(shí)別時(shí)間變化曲線(xiàn)

綜上，MMSE-FSA算法完成了對(duì)大量標(biāo)簽識(shí)別認(rèn)證過(guò)程，采用最小均方誤差預(yù)編碼技術(shù)對(duì)幀時(shí)隙ALOHA算法進(jìn)行了改進(jìn)，不僅降低了時(shí)隙總數(shù)、碰撞數(shù)，而且識(shí)別時(shí)間也得到了一定的改善，穩(wěn)定性較好，具有一定的實(shí)際意義。

4 結(jié)論

文中提出了一種結(jié)合幀時(shí)隙ALOHA算法和最小均方誤差預(yù)編碼技術(shù)的RFID系統(tǒng)防碰撞算法。當(dāng)標(biāo)簽總數(shù)為1 000時(shí)，改進(jìn)幀時(shí)隙ALOHA算法顯著提升了系統(tǒng)吞吐量，降低了標(biāo)簽識(shí)別時(shí)間，減少了碰撞時(shí)隙數(shù)量?？紤]到當(dāng)前的試驗(yàn)設(shè)備和數(shù)據(jù)規(guī)模，文中提出的食品RFID標(biāo)簽沖突檢測(cè)的防碰撞算法仍處于起步階段，僅對(duì)[0，1 000]內(nèi)標(biāo)簽進(jìn)行了仿真分析，后續(xù)應(yīng)對(duì)大規(guī)模識(shí)別數(shù)據(jù)進(jìn)行研究，以適應(yīng)未來(lái)不斷變化的應(yīng)用環(huán)境。