智能制造中RFID多標(biāo)簽快速識(shí)別問(wèn)題的研究

(山東建筑大學(xué) 信息與電氣工程學(xué)院，濟(jì)南 250101)

0 引言

所謂RFID，指的是無(wú)線(xiàn)射頻識(shí)別技術(shù)(Radio Frequency IDentification)，它通過(guò)無(wú)線(xiàn)電訊號(hào)識(shí)別特定的目標(biāo)對(duì)象，無(wú)需識(shí)別系統(tǒng)與目標(biāo)對(duì)象之間有接觸，即可實(shí)現(xiàn)兩者的雙向數(shù)據(jù)通信。與以往應(yīng)用在工業(yè)現(xiàn)場(chǎng)的條形碼識(shí)別技術(shù)相比，RFID技術(shù)不受應(yīng)答對(duì)象尺寸大小和形狀限制，不易被污染，適應(yīng)惡劣環(huán)境的能力更強(qiáng)，已逐步成為工程機(jī)械智能制造領(lǐng)域的核心推動(dòng)力[1]。

工程機(jī)械生產(chǎn)線(xiàn)依托RFID 系統(tǒng)，能夠自動(dòng)且準(zhǔn)確地獲取生產(chǎn)過(guò)程中有關(guān)“工序、工件、工人”的信息，實(shí)現(xiàn)全過(guò)程溯源，提高生產(chǎn)安全和質(zhì)量。目前，影響工業(yè)現(xiàn)場(chǎng)RFID技術(shù)應(yīng)用效果的主要問(wèn)題就是多標(biāo)簽快速識(shí)別問(wèn)題，該問(wèn)題直接影響著RFID系統(tǒng)的工作效率，進(jìn)而影響整個(gè)智能制造生產(chǎn)線(xiàn)的工程進(jìn)度。

現(xiàn)有的RFID防碰撞算法主要分為ALOHA 算法和樹(shù)形算法兩類(lèi)。其中ALOHA算法原理簡(jiǎn)單，容易實(shí)現(xiàn)，特別是其中一種動(dòng)態(tài)幀時(shí)隙ALOHA算法已經(jīng)具備比較高的吞吐率，但這種算法具有不可避免的隨機(jī)性，存在標(biāo)簽饑餓現(xiàn)象，即總會(huì)有少量標(biāo)簽不能被識(shí)別[2]。這在準(zhǔn)確性和安全性要求高的工業(yè)現(xiàn)場(chǎng)是不被允許的，因此ALOHA算法僅適用于待識(shí)別標(biāo)簽數(shù)目較少的情景。二進(jìn)制樹(shù)算法不存在隨機(jī)性，解決了標(biāo)簽饑餓問(wèn)題，但這卻以系統(tǒng)的復(fù)雜度為代價(jià)，對(duì)系統(tǒng)識(shí)別總時(shí)長(zhǎng)有顯著影響，這就不符合工業(yè)現(xiàn)場(chǎng)高實(shí)時(shí)性的特點(diǎn)。因此二進(jìn)制樹(shù)類(lèi)算法僅適用于待識(shí)別標(biāo)簽數(shù)目較多，且對(duì)識(shí)別時(shí)間要求不高的情景。查詢(xún)樹(shù)算法解決了標(biāo)簽饑餓問(wèn)題的同時(shí)，系統(tǒng)復(fù)雜度也不高，但系統(tǒng)識(shí)別效率受標(biāo)簽ID的長(zhǎng)度影響較為嚴(yán)重，可見(jiàn)該類(lèi)算法靈活性較低，僅適用于待識(shí)別標(biāo)簽ID長(zhǎng)度較短的情景[3]。

ALOHA 算法和樹(shù)形算法都不可避免空時(shí)隙或空搜索的存在，造成資源浪費(fèi)的同時(shí)，算法的性能和識(shí)別效率都受到很大的影響。這兩類(lèi)算法都無(wú)法在短時(shí)間內(nèi)完成大量標(biāo)簽的識(shí)別，不能滿(mǎn)足工業(yè)現(xiàn)場(chǎng)的生產(chǎn)要求。針對(duì)上述問(wèn)題，本文提出一種更具靈活性的改進(jìn)型算法，該算法建立在查詢(xún)樹(shù)算法的基礎(chǔ)上，保留了查詢(xún)樹(shù)算法的優(yōu)點(diǎn)的同時(shí)，對(duì)查詢(xún)樹(shù)算法的缺點(diǎn)進(jìn)行了針對(duì)性改進(jìn)，能夠?qū)崿F(xiàn)多標(biāo)簽快速識(shí)別，可運(yùn)用于工程機(jī)械智能制造生產(chǎn)線(xiàn)中。

本文提出的新算法對(duì)RFID系統(tǒng)的軟硬件沒(méi)有特殊要求，尤其是不需要電子標(biāo)簽具有歷史記錄功能，只需要與閱讀器傳來(lái)的查詢(xún)前綴進(jìn)行對(duì)比，然后判斷是否響應(yīng)該命令即可。

1 曼徹斯特編碼方式簡(jiǎn)述

本文提出的新算法中標(biāo)簽ID采用曼徹斯特編碼(ManchesterEncoding)方式編碼，也叫做相位編碼方式，它是一種同步時(shí)針編碼方式。該編碼方式能在兩個(gè)或多個(gè)標(biāo)簽同時(shí)響應(yīng)閱讀器的命令時(shí)，精確地識(shí)別出發(fā)生碰撞的數(shù)據(jù)的比特位，從而采取相應(yīng)措施使發(fā)生碰撞的標(biāo)簽?zāi)鼙蛔R(shí)別。

曼徹斯特編碼方式采用半個(gè)周期的電平正負(fù)跳變來(lái)表示1和0，約定由高電平到低電平的跳變?yōu)?，由低電平到高電平跳變?yōu)?[4]。若同時(shí)響應(yīng)的兩個(gè)或多個(gè)標(biāo)簽的編號(hào)中有某一位數(shù)據(jù)是不同值，則閱讀器接收到的上升沿和下降沿之間會(huì)相互抵消，呈現(xiàn)沒(méi)有電平跳變的狀態(tài)，這是不被允許的，此時(shí)閱讀器就可以判定這些數(shù)據(jù)位之間發(fā)生了碰撞，如圖1所示。

圖1 曼徹斯特編碼示意圖

2 改進(jìn)型算法過(guò)程描述

本文提出的新算法延續(xù)了查詢(xún)樹(shù)算法的優(yōu)點(diǎn)，此外，針對(duì)查詢(xún)樹(shù)算法存在的識(shí)別效率受標(biāo)簽編號(hào)長(zhǎng)度影響的問(wèn)題進(jìn)行了改進(jìn)。即當(dāng)多個(gè)標(biāo)簽發(fā)生碰撞時(shí)，根據(jù)首位碰撞位生成兩個(gè)新的搜索前綴，而不是機(jī)械的在之前的搜索前綴后添加1或0。

該算法中，閱讀器自身帶有查詢(xún)前綴棧prefix、數(shù)據(jù)儲(chǔ)存棧string和分組編號(hào)棧group；標(biāo)簽帶有寄存器count。

2.1 待識(shí)別標(biāo)簽分組

本算法主要是實(shí)現(xiàn)短時(shí)間內(nèi)大量標(biāo)簽的識(shí)別，故為減少標(biāo)簽碰撞發(fā)生的可能性，提高系統(tǒng)的識(shí)別效率，閱讀器將標(biāo)簽ID中數(shù)值1的總位數(shù)作為分組編號(hào)，對(duì)場(chǎng)內(nèi)所有待識(shí)別標(biāo)簽進(jìn)行分組識(shí)別。

首先，閱讀器發(fā)送數(shù)值1的總位數(shù)請(qǐng)求命令Quest，場(chǎng)內(nèi)所有標(biāo)簽接收到該命令后，統(tǒng)計(jì)自身ID中數(shù)值1的個(gè)數(shù)，將該統(tǒng)計(jì)值保存在標(biāo)簽的寄存器count中，并將該統(tǒng)計(jì)值編碼后發(fā)送給閱讀器。

為提高數(shù)據(jù)傳輸?shù)姆€(wěn)定性，在信道中傳輸分組編號(hào)時(shí)不采用傳統(tǒng)的二進(jìn)制編碼，而是由標(biāo)簽生成一個(gè)比特串，該比特串中位序號(hào)與該統(tǒng)計(jì)值相同的二進(jìn)制數(shù)位設(shè)置為1，其余二進(jìn)制數(shù)位設(shè)置為0(若標(biāo)簽編碼不包含1，則返回全0比特串)。閱讀器接收到該比特串后，還原為1的總位數(shù)，將其作為分組編號(hào)，壓入分組編號(hào)棧group中。具體示例如表1所示。

表1 統(tǒng)計(jì)值編碼示例圖

2.2 搜索前綴的生成

傳統(tǒng)的查詢(xún)樹(shù)算法中，當(dāng)標(biāo)簽發(fā)生數(shù)據(jù)碰撞時(shí)，閱讀器直接在之前的搜索前綴后增加一位1或者0，生成新的搜索前綴[5]。這種做法不可避免空搜索的存在，降低了系統(tǒng)的識(shí)別效率，同時(shí)又使算法的效率很大程度上受標(biāo)簽ID長(zhǎng)度的影響。

針對(duì)上述問(wèn)題，本文提出算法中采取了一種更具靈活性的搜索前綴生成方式，即根據(jù)首位碰撞位P來(lái)生成兩個(gè)搜索前綴，這就很好地解決了空搜索的問(wèn)題，一定程度上減少了標(biāo)簽ID長(zhǎng)度對(duì)系統(tǒng)效率的影響。此外，當(dāng)前組的待識(shí)別標(biāo)簽與搜索前綴匹配成功后，只將自身ID中與搜索前綴相匹配之后的數(shù)據(jù)發(fā)送給閱讀器，這就減少了標(biāo)簽與閱讀器間的數(shù)據(jù)通信量，進(jìn)一步優(yōu)化了算法的性能[6]。

本算法中生成搜索前綴時(shí)應(yīng)考慮當(dāng)前組標(biāo)簽進(jìn)行首輪識(shí)別和非首輪識(shí)別兩種情況[7]。

當(dāng)前組進(jìn)行首輪識(shí)別時(shí)，閱讀器的搜索前綴棧中只有空字符串。閱讀器接收標(biāo)簽的返回信號(hào)，若檢測(cè)到未發(fā)生碰撞，則進(jìn)入下一組標(biāo)簽的識(shí)別；若檢測(cè)到發(fā)生碰撞，則根據(jù)首位碰撞位P生成兩個(gè)新搜索前綴，兩個(gè)新搜索前綴由標(biāo)簽ID中首位碰撞位P之前的部分與首位碰撞位P組成，且P分別賦值為0或1，閱讀器將兩個(gè)新搜索前綴壓入查詢(xún)前綴棧prefix中，開(kāi)啟下一輪搜索[8]。

當(dāng)前組進(jìn)行非首輪識(shí)別時(shí)，此時(shí)搜索前綴棧中定有非空字符串，設(shè)棧頂字符串為M。閱讀器發(fā)送搜索前綴M給當(dāng)前組標(biāo)簽，標(biāo)簽將自身編號(hào)中與搜索前綴M匹配成功之后的字符串發(fā)送給閱讀器。閱讀器接收到字符串后，若檢測(cè)到?jīng)]有發(fā)生碰撞，則成功識(shí)別一個(gè)標(biāo)簽，且該標(biāo)簽的ID編號(hào)由搜索前綴M與收到的字符串連接組成；若檢測(cè)到發(fā)生碰撞，則根據(jù)首位碰撞位P生成兩個(gè)全新的搜索前綴M1和M2，這兩個(gè)新搜索前綴由之前的搜索前綴M與接收到的字符串中首位碰撞位P之前的部分以及首位碰撞位 P連接而成，且首位碰撞位P分別賦值0和1。閱讀器將兩個(gè)全新的搜索前綴壓入查詢(xún)前綴棧prefix中，開(kāi)啟新一輪搜索。

2.3 改進(jìn)型算法步驟介紹

分組完成后，RFID系統(tǒng)正式進(jìn)入標(biāo)簽識(shí)別環(huán)節(jié)。閱讀器從分組編號(hào)棧group中取出棧頂元素N1，從查詢(xún)前綴棧prefix中取出棧頂元素M，向場(chǎng)內(nèi)待識(shí)別標(biāo)簽發(fā)送命令(N1,M)。場(chǎng)內(nèi)所有待識(shí)別標(biāo)簽接收到該命令后，寄存器count中分組編號(hào)值與N1相同的標(biāo)簽被選中為當(dāng)前組標(biāo)簽。該組標(biāo)簽中與參數(shù)M相匹配的標(biāo)簽響應(yīng)該命令，發(fā)送自身ID編號(hào)給閱讀器。若此時(shí)搜索前綴M為空字符串，當(dāng)前組所有標(biāo)簽都會(huì)響應(yīng)該命令。

閱讀器收到返回的ID編號(hào)后，檢測(cè)是否發(fā)生數(shù)據(jù)碰撞，如果沒(méi)有發(fā)生碰撞，則成功識(shí)別一個(gè)標(biāo)簽，閱讀器從查詢(xún)前綴棧中取出棧頂元素，進(jìn)行下一輪識(shí)別；如果發(fā)生碰撞，則根據(jù)首位碰撞位P生成兩個(gè)新的搜索前綴M1和M2，閱讀器將兩個(gè)新的搜索前綴依次壓入查詢(xún)前綴棧prefix中。重復(fù)上述過(guò)程直到查詢(xún)前綴棧為空，就可以結(jié)束當(dāng)前組的識(shí)別，之后閱讀器從分組編號(hào)棧group中取出棧頂元素N2，開(kāi)啟下一組的識(shí)別，直到group為空，則沒(méi)有待識(shí)別標(biāo)簽，結(jié)束識(shí)別過(guò)程。以表2中6個(gè)標(biāo)簽為例，本文提出的改進(jìn)型算法的查詢(xún)樹(shù)如圖2所示。

圖2 改進(jìn)型算法查詢(xún)樹(shù)示例圖

由圖2可以看出，本文提出的新算法可以根據(jù)首位碰撞位生成兩個(gè)新的搜索前綴，相比傳統(tǒng)查詢(xún)樹(shù)算法在之前的搜索前綴后直接添加1或0的做法，有效解決了空搜索的問(wèn)題，提高了RFID系統(tǒng)的識(shí)別效率，且系統(tǒng)效率受標(biāo)簽ID長(zhǎng)度的影響程度有所降低。

2.4 RFID防碰撞系統(tǒng)結(jié)構(gòu)綜述

本設(shè)計(jì)中，RFID防碰撞系統(tǒng)硬件部分主要分為電子標(biāo)簽和閱讀器[9]。根據(jù)前文的算法介紹，本設(shè)計(jì)中閱讀器硬件系統(tǒng)可以分為分組模塊和識(shí)別模塊兩大部分。閱讀器硬件系統(tǒng)結(jié)構(gòu)圖如圖3所示。

圖3 閱讀器硬件系統(tǒng)結(jié)構(gòu)圖

由圖3可知，分組模塊主要包含請(qǐng)求模塊、接收模塊和確定模塊。其中，請(qǐng)求模塊負(fù)責(zé)向場(chǎng)內(nèi)待識(shí)別標(biāo)簽發(fā)送數(shù)值1 的總位數(shù)的請(qǐng)求命令；接收模塊負(fù)責(zé)接收標(biāo)簽返回的數(shù)值1的統(tǒng)計(jì)值的比特串，將其還原回?cái)?shù)值1的總位數(shù)，并將其儲(chǔ)存到閱讀器的分組編號(hào)棧group中；確定模塊負(fù)責(zé)將分組編號(hào)相同的標(biāo)簽編為一組。

識(shí)別模塊主要包括起始模塊、命令模塊、識(shí)別模塊、前綴生成模塊、判斷模塊和結(jié)束模塊。其中，起始模塊負(fù)責(zé)從分組編號(hào)棧group中取出棧頂元素N1;命令模塊負(fù)責(zé)從查詢(xún)前綴棧prefix中取出棧頂元素M，并向場(chǎng)內(nèi)待識(shí)別標(biāo)簽發(fā)送命令(N1,M)；識(shí)別模塊負(fù)責(zé)接收響應(yīng)(N1,M)命令的標(biāo)簽的ID，并檢測(cè)是否發(fā)生碰撞；前綴生成模塊負(fù)責(zé)根據(jù)首位碰撞位生成兩個(gè)全新的搜索前綴；判斷模塊負(fù)責(zé)查看查詢(xún)前綴棧prefix中是否有非空元素，若是，則進(jìn)入命令模塊，若否，則進(jìn)入結(jié)束模塊；結(jié)束模塊負(fù)責(zé)查看分組編號(hào)棧group是否有非空元素，若是，則進(jìn)入起始模塊，若否，則標(biāo)簽識(shí)別全部結(jié)束[10]。

3 改進(jìn)型算法仿真分析

本章利用Matlab軟件對(duì)動(dòng)態(tài)幀時(shí)隙ALOHA算法、二進(jìn)制樹(shù)算法、查詢(xún)樹(shù)算法以及本文提出的新算法的通信量和吞吐率進(jìn)行試驗(yàn)仿真。

仿真實(shí)驗(yàn)中，標(biāo)簽的數(shù)目的范圍取0～1000。為保證仿真試驗(yàn)結(jié)果的可靠性，仿真進(jìn)行了100次取其平均值，結(jié)果如圖4和圖5所示。

圖4 標(biāo)簽個(gè)數(shù)為不同值時(shí)系統(tǒng)通信量對(duì)比

從圖4可以看出，隨著待識(shí)別標(biāo)簽數(shù)目的增加，動(dòng)態(tài)幀時(shí)隙ALOHA算法、二進(jìn)制樹(shù)算法和查詢(xún)樹(shù)算法這三種算法的系統(tǒng)通信量呈線(xiàn)性增長(zhǎng)，而本文提出的新算法的系統(tǒng)通信量則呈對(duì)數(shù)增長(zhǎng)。其主要原因有兩個(gè)，一是本算法中新的搜索前綴由碰撞位產(chǎn)生，直接減少了閱讀器與標(biāo)簽的通信次數(shù)；二是標(biāo)簽ID編號(hào)與搜索前綴匹配成功后，只回傳匹配成功之后的數(shù)據(jù)位，直接減少了系統(tǒng)通信量。

由此可見(jiàn)，本文提出的新算法的兩點(diǎn)改進(jìn)，有效減少了通信時(shí)間的同時(shí)，減少了系統(tǒng)通信量，這也是該算法能夠減少標(biāo)簽識(shí)別總時(shí)長(zhǎng)，實(shí)現(xiàn)多標(biāo)簽快速識(shí)別的關(guān)鍵因素。

圖5 標(biāo)簽個(gè)數(shù)為不同值時(shí)系統(tǒng)的吞吐率對(duì)比

由圖5可以看出，本文提出的新算法的系統(tǒng)吞吐率明顯高于其他三種算法，且當(dāng)待識(shí)別標(biāo)簽數(shù)目增多時(shí)，其他幾種算法吞吐率波動(dòng)較大，而本文提出的算法性能穩(wěn)定，保持在65%左右。這主要是因?yàn)楸疚奶岢龅男滤惴ㄓ行p少了系統(tǒng)識(shí)別總時(shí)長(zhǎng)，從而顯著提高了系統(tǒng)識(shí)別吞吐率。

由仿真試驗(yàn)的結(jié)果圖可見(jiàn)，本文提出的算法能有效提高系統(tǒng)的識(shí)別效率，節(jié)約系統(tǒng)的通信量，相比與現(xiàn)存的其他幾種算法，更適合用于短時(shí)間內(nèi)大量標(biāo)簽的識(shí)別。

4 總結(jié)

本文提出了一種新算法來(lái)實(shí)現(xiàn)工業(yè)現(xiàn)場(chǎng)短時(shí)間內(nèi)大量標(biāo)簽的快速識(shí)別。該算法延續(xù)了查詢(xún)樹(shù)算法的優(yōu)點(diǎn)的同時(shí)，改進(jìn)了查詢(xún)樹(shù)算法中易出現(xiàn)空搜索的缺點(diǎn)，使新的查詢(xún)前綴根據(jù)碰撞位直接生成，生成的碰撞樹(shù)為滿(mǎn)二叉樹(shù)，有效避免了電子標(biāo)簽與閱讀器之間的無(wú)效通信。此外，匹配成功的標(biāo)簽響應(yīng)命令時(shí)，只回傳自身ID中與搜索前綴相匹配之后的數(shù)據(jù)，這就減少了標(biāo)簽與閱讀器間的數(shù)據(jù)通信量，進(jìn)一步優(yōu)化了算法的性能。

該算法通過(guò)以上兩點(diǎn)改進(jìn)，有效減少了RFID系統(tǒng)識(shí)別總時(shí)長(zhǎng)。此外，通過(guò)對(duì)待識(shí)別標(biāo)簽的分組從識(shí)別初始便減少了發(fā)生標(biāo)簽碰撞的可能性。仿真結(jié)果表明，本文提出的新算法吞吐率高達(dá)65%，且當(dāng)場(chǎng)內(nèi)存有大量待識(shí)別標(biāo)簽時(shí)，通信量?jī)H呈對(duì)數(shù)增長(zhǎng)?？梢?jiàn)該算法可有效運(yùn)用于工程機(jī)械智能制造生產(chǎn)線(xiàn)中，實(shí)現(xiàn)短時(shí)間大量標(biāo)簽的識(shí)別。