智能制造中RFID區(qū)域碰撞問(wèn)題的研究與改進(jìn)

王 琪，王 濤，朱 青，邢 燕，陳金環(huán)

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

0 引言

智能制造（Intelligent Manufacturing，IM）是由智能機(jī)器和人類專家共同組成的人機(jī)一體化智能系統(tǒng)。大力發(fā)展智能制造產(chǎn)業(yè)既符合我國(guó)制造業(yè)發(fā)展的內(nèi)在要求，也是重塑我國(guó)制造業(yè)新優(yōu)勢(shì)、實(shí)現(xiàn)轉(zhuǎn)型升級(jí)的必然選擇。

智能制造的顯著特點(diǎn)是柔性制造和高效生產(chǎn)，這就需要對(duì)設(shè)備和原材料等數(shù)據(jù)的準(zhǔn)確高效提取。目前國(guó)內(nèi)大多數(shù)制造企業(yè)采用條形碼采集相關(guān)數(shù)據(jù)，識(shí)別效率不高，已無(wú)法滿足當(dāng)前制造業(yè)的需求。而RFID技術(shù)的出現(xiàn)大大地提高了識(shí)別效率使該問(wèn)題得到了解決。

所謂RFID，指的是射頻識(shí)別技術(shù)（Radio Frequency IDentification），它通過(guò)空間耦合的方式識(shí)別電子標(biāo)簽內(nèi)的信息，實(shí)現(xiàn)閱讀器與電子標(biāo)簽的數(shù)據(jù)交換。工業(yè)現(xiàn)場(chǎng)作業(yè)量大、流動(dòng)性強(qiáng)，在同一閱讀器的識(shí)別范圍內(nèi)，常會(huì)出現(xiàn)多個(gè)標(biāo)簽同時(shí)向閱讀器發(fā)送信息的情形，這就是標(biāo)簽碰撞，此時(shí)數(shù)據(jù)信息間相互干擾，標(biāo)簽數(shù)據(jù)無(wú)法被正確讀取。

現(xiàn)有的RFID標(biāo)簽防碰撞算法中性能較好的是動(dòng)態(tài)幀時(shí)隙ALOHA算法，它在一定程度上提高了系統(tǒng)的識(shí)別效率，但該算法仍存在較大的隨機(jī)性，存在標(biāo)簽饑餓問(wèn)題。此外，以二進(jìn)制搜索算法為代表的確定性防碰撞算法雖然解決了標(biāo)簽饑餓的問(wèn)題，但卻以系統(tǒng)復(fù)雜度高為代價(jià)，不適用于高實(shí)時(shí)性要求的工業(yè)現(xiàn)場(chǎng)。針對(duì)上述問(wèn)題，本文提出了一種改進(jìn)型分組動(dòng)態(tài)幀時(shí)隙ALOHA算法，有效提高了系統(tǒng)吞吐率的同時(shí)，節(jié)約了系統(tǒng)成本，可用于智能制造工業(yè)生產(chǎn)線中。

1 傳統(tǒng)ALOHA算法

ALOHA算法是根據(jù)RFID系統(tǒng)的特點(diǎn)不斷改進(jìn)形成的算法體系，它的本質(zhì)是分離標(biāo)簽應(yīng)答的時(shí)間[1]，即當(dāng)標(biāo)簽進(jìn)入閱讀器的讀取區(qū)域后，在不同時(shí)間響應(yīng)閱讀器的命令。若同時(shí)有多個(gè)標(biāo)簽響應(yīng)閱讀器的命令，會(huì)發(fā)生標(biāo)簽碰撞，標(biāo)簽碰撞分為兩種情況：一種是部分碰撞，另一種是完全碰撞，如圖1所示。

圖1 標(biāo)簽碰撞示意圖

發(fā)生碰撞了的標(biāo)簽都無(wú)法被閱讀器識(shí)別，此時(shí)閱讀器會(huì)發(fā)送命令讓這些標(biāo)簽轉(zhuǎn)入待命狀態(tài)，隨機(jī)等待一段時(shí)間后再重新發(fā)送應(yīng)答信號(hào)。

1.1 純ALOHA算法

純ALOHA算法是指標(biāo)簽在發(fā)送應(yīng)答信號(hào)時(shí)可以任意選擇響應(yīng)時(shí)間，不需要同步各個(gè)標(biāo)簽的響應(yīng)時(shí)間。這種算法簡(jiǎn)單易行，但隨著電子標(biāo)簽數(shù)目的增多，發(fā)生標(biāo)簽碰撞的可能性增大，系統(tǒng)識(shí)別效率不高，近年來(lái)工業(yè)生產(chǎn)線中已漸漸淘汰這種算法。

1.2 幀時(shí)隙ALOHA算法

幀時(shí)隙ALOHA（Framed Slotted ALOHA，簡(jiǎn)稱FSA）算法是對(duì)純ALOHA算法的一種改進(jìn)，其核心思想是將數(shù)據(jù)幀離散成若干個(gè)幀時(shí)隙，待識(shí)別的標(biāo)簽隨機(jī)選擇幀中一個(gè)時(shí)隙響應(yīng)閱讀器的命令，以數(shù)據(jù)幀為周期進(jìn)行數(shù)據(jù)交換。

若一個(gè)時(shí)隙僅被唯一標(biāo)簽選中，則此標(biāo)簽被成功識(shí)別；若一個(gè)時(shí)隙被多于一個(gè)的標(biāo)簽選中，就會(huì)產(chǎn)生標(biāo)簽碰撞現(xiàn)象。碰撞的標(biāo)簽將在下一個(gè)幀中隨機(jī)地選擇一個(gè)時(shí)隙重新發(fā)送信息，整個(gè)算法過(guò)程都會(huì)如此循環(huán)，直到所有的標(biāo)簽均被識(shí)別。FSA算法工作過(guò)程如圖2所示。

圖2 幀時(shí)隙ALOHA算法工作過(guò)程示意圖

設(shè)數(shù)據(jù)幀有N個(gè)時(shí)隙，待識(shí)別標(biāo)簽個(gè)數(shù)為n，同時(shí)有r個(gè)標(biāo)簽選擇同一時(shí)隙的概率服從二項(xiàng)式分布定理[1]：

由式(1)知，一個(gè)時(shí)隙僅被一個(gè)標(biāo)簽選中的概率，即標(biāo)簽被成功讀取的概率為：

由此可以推算，一個(gè)數(shù)據(jù)幀內(nèi)成功讀取標(biāo)簽的時(shí)隙數(shù)為：

此時(shí)系統(tǒng)的吞吐率（識(shí)別效率）為：

為使系統(tǒng)獲得最優(yōu)性能，對(duì)式(4)求導(dǎo)：

可以得出：

將上式進(jìn)行變換：

當(dāng)n很大時(shí)，將上式做泰勒級(jí)數(shù)展開(kāi)：

上述推導(dǎo)表明：標(biāo)簽數(shù)目與數(shù)據(jù)幀長(zhǎng)度大致相等時(shí)，系統(tǒng)取得最優(yōu)性能。當(dāng)標(biāo)簽數(shù)目遠(yuǎn)大于數(shù)據(jù)幀長(zhǎng)度時(shí)，發(fā)生標(biāo)簽碰撞的可能性增加；當(dāng)標(biāo)簽數(shù)目遠(yuǎn)小于數(shù)據(jù)幀長(zhǎng)度時(shí)，造成時(shí)隙浪費(fèi)。因此希望閱讀器能夠根據(jù)標(biāo)簽數(shù)量動(dòng)態(tài)調(diào)整數(shù)據(jù)幀的長(zhǎng)度，提高RFID識(shí)別系統(tǒng)的穩(wěn)定性。

1.3 動(dòng)態(tài)幀時(shí)隙ALOHA算法

動(dòng)態(tài)幀時(shí)隙ALOHA（Dynamic Frame Slotted ALOHA，簡(jiǎn)稱DFSA）算法能夠動(dòng)態(tài)改變數(shù)據(jù)幀的長(zhǎng)度，使之始終與待識(shí)別的標(biāo)簽數(shù)目大致相同，使系統(tǒng)具備最優(yōu)性能 。但是，工業(yè)現(xiàn)場(chǎng)作業(yè)量大，肯定會(huì)出現(xiàn)標(biāo)簽數(shù)目遠(yuǎn)大于數(shù)據(jù)幀長(zhǎng)度的情況。由于硬件條件的約束，數(shù)據(jù)幀的長(zhǎng)度不可能無(wú)限增大（最大長(zhǎng)度為Mmax=256）[2]。針對(duì)這一問(wèn)題，本文提出將工業(yè)現(xiàn)場(chǎng)待識(shí)別的標(biāo)簽分組，每次閱讀器僅對(duì)一組標(biāo)簽進(jìn)行識(shí)別的方案，同時(shí)根據(jù)每輪統(tǒng)計(jì)所得碰撞時(shí)隙數(shù)動(dòng)態(tài)改變數(shù)據(jù)幀的長(zhǎng)度，使系統(tǒng)具備最優(yōu)性能。

2 改進(jìn)型算法性能分析

本文采用的算法延續(xù)了DFSA算法的優(yōu)點(diǎn)，并根據(jù)將待識(shí)別標(biāo)簽數(shù)量估算值進(jìn)行分組；此外，同時(shí)開(kāi)始四個(gè)時(shí)隙接收信號(hào)，根據(jù)統(tǒng)計(jì)所得碰撞時(shí)隙數(shù)來(lái)動(dòng)態(tài)改變數(shù)據(jù)幀的長(zhǎng)度。

2.1 待識(shí)別標(biāo)簽數(shù)目估算與分組

系統(tǒng)獲得最優(yōu)性能時(shí)，數(shù)據(jù)幀中一個(gè)時(shí)隙中發(fā)生標(biāo)簽碰撞的概率為ε=0.4180[3]，則一個(gè)時(shí)隙中發(fā)生標(biāo)簽碰撞的標(biāo)簽的個(gè)數(shù)為：

在正式進(jìn)行標(biāo)簽識(shí)別前，系統(tǒng)首先要對(duì)標(biāo)簽進(jìn)行一輪快速識(shí)別，統(tǒng)計(jì)本輪識(shí)別中碰撞時(shí)隙數(shù)為C0，則待識(shí)別的標(biāo)簽總數(shù)為：

求得的待識(shí)別標(biāo)簽總數(shù)n后，考慮是否對(duì)電子標(biāo)簽進(jìn)行分組，限制每次參與應(yīng)答的標(biāo)簽的數(shù)量，使之與當(dāng)前數(shù)據(jù)幀的長(zhǎng)度相匹配。

根據(jù)式(4)，將兩條吞吐率曲線交點(diǎn)處的標(biāo)簽數(shù)量，作為閱讀器調(diào)整幀長(zhǎng)的臨界值[4]。即：

其中，a，b為標(biāo)簽的分組數(shù)，設(shè)a取1，b取2，代入式(13)得：

可以求得標(biāo)簽數(shù)目分組的臨界值為：

若已知待識(shí)別標(biāo)簽數(shù)目為n，當(dāng)n＜354時(shí)，不對(duì)標(biāo)簽進(jìn)行分組；當(dāng)354＜n＜610時(shí)，將標(biāo)簽分為兩組：一組包含256個(gè)標(biāo)簽，另一組為剩余標(biāo)簽；當(dāng)610＜n＜866，則將標(biāo)簽分為三組：其中兩組的標(biāo)簽數(shù)為256，另一組為剩余標(biāo)簽；以此類推。

另一方面，閱讀器設(shè)定的數(shù)據(jù)幀長(zhǎng)度一般為二的冪次方，如16、32、64、128、256。故不同范圍的標(biāo)簽數(shù)目n相對(duì)應(yīng)的幀長(zhǎng)度如表1所示。

表1 不同標(biāo)簽個(gè)數(shù)對(duì)應(yīng)的幀長(zhǎng)度和分組情況

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

本文所采用的算法中，閱讀器首先選定一組標(biāo)簽為當(dāng)前組，并根據(jù)該組標(biāo)簽的數(shù)目，決定初始時(shí)隙范圍參數(shù)Q（取值范圍為0～15）的值，隨后生成長(zhǎng)度為2Q的數(shù)據(jù)幀。選定的初始時(shí)隙范圍參數(shù)Q應(yīng)滿足使當(dāng)前數(shù)據(jù)幀長(zhǎng)度與當(dāng)前組待識(shí)別標(biāo)簽數(shù)目大致相同。

隨后，閱讀器向所有當(dāng)前組標(biāo)簽發(fā)送帶有參數(shù)Q的請(qǐng)求響應(yīng)命令Query（Q），標(biāo)簽收到Query命令后做出響應(yīng)，由標(biāo)簽自帶的隨機(jī)數(shù)生成器T生成一個(gè)[0，2Q-1]范圍內(nèi)的隨機(jī)數(shù)作為時(shí)隙值并儲(chǔ)存在自身的隨機(jī)數(shù)儲(chǔ)存器S中。

然后，閱讀器發(fā)送一條包含時(shí)隙請(qǐng)求參數(shù)R（R=0）的命令開(kāi)啟第R 組時(shí)隙接收信號(hào)[5]。

時(shí)隙值在[4×R，4×R+3] 范圍內(nèi)的標(biāo)簽響應(yīng)此命令，返回一個(gè)16位的隨機(jī)數(shù)N16；若當(dāng)前時(shí)隙只有一個(gè)標(biāo)簽響應(yīng)，閱讀器成功與標(biāo)簽建立通信，向標(biāo)簽發(fā)送確認(rèn)命令，被正確識(shí)別的標(biāo)簽將自身的EPC數(shù)據(jù)發(fā)送給閱讀器；若當(dāng)前時(shí)隙有多個(gè)標(biāo)簽響應(yīng)，閱讀器收到多個(gè)標(biāo)簽發(fā)送的隨機(jī)數(shù)發(fā)生信息碰撞，則將該時(shí)隙標(biāo)記為碰撞時(shí)隙；若當(dāng)前時(shí)隙無(wú)標(biāo)簽響應(yīng)，則標(biāo)記為空閑時(shí)隙。

閱讀器識(shí)別完一組時(shí)隙后，自動(dòng)將R值加一，跳轉(zhuǎn)到下一組時(shí)隙的識(shí)別過(guò)程，繼續(xù)發(fā)送請(qǐng)求響應(yīng)命令，如此循環(huán)。識(shí)別完當(dāng)前組所有標(biāo)簽后，閱讀器統(tǒng)計(jì)本輪識(shí)別過(guò)程中空閑時(shí)隙、成功時(shí)隙和碰撞時(shí)隙的數(shù)量，分別記為C0、C1和C2；根據(jù)統(tǒng)計(jì)結(jié)果動(dòng)態(tài)調(diào)整當(dāng)前組下一輪識(shí)別過(guò)程的幀時(shí)隙數(shù)。設(shè)當(dāng)前幀時(shí)隙數(shù)為M=2Q，調(diào)整方法如下：

1）如果C2≥0.7M，則將下一輪識(shí)別過(guò)程的幀時(shí)隙數(shù)調(diào)整為2M=2Q+1，即隨機(jī)數(shù)Q的值加1；

2）如果C2＜0.7M，則下一輪識(shí)別過(guò)程的幀時(shí)隙數(shù)依然為M=2Q，即隨機(jī)數(shù)Q的值不變；

3）如果C2≈0，則將參與下一輪識(shí)別過(guò)程的幀時(shí)隙數(shù)調(diào)整為0.5M=2Q-1，即隨機(jī)數(shù)Q的值減1。

根據(jù)上述1）、2）、3）方法動(dòng)態(tài)調(diào)整當(dāng)前組數(shù)據(jù)幀的長(zhǎng)度，直至某次識(shí)別過(guò)程中沒(méi)有一個(gè)標(biāo)簽被識(shí)別，則認(rèn)為當(dāng)前組所有標(biāo)簽具備識(shí)別，系統(tǒng)跳轉(zhuǎn)到下一組的識(shí)別過(guò)程。

3 仿真分析

取標(biāo)簽個(gè)數(shù)n的范圍為0～1000，通過(guò)對(duì)比標(biāo)簽個(gè)數(shù)為不同值時(shí)所需要的總時(shí)隙數(shù)和吞吐率，比較FSA算法、DFSA算法與本文提出的算法的性能優(yōu)劣。其中，F(xiàn)SA算法中幀長(zhǎng)取定值為256，DFSA算法的幀長(zhǎng)度選取原則如表1所示。本文進(jìn)行了100次仿真取其平均值。

由圖3可以看出，當(dāng)標(biāo)簽數(shù)目0～256的范圍內(nèi)時(shí)，3種算法的所需的時(shí)隙數(shù)大致相同，而隨著標(biāo)簽個(gè)數(shù)的增加，F(xiàn)SA算法和DFSA算法所需的時(shí)隙數(shù)呈指數(shù)增加，本文算法所需的時(shí)隙數(shù)呈線性增長(zhǎng)。主要原因是當(dāng)標(biāo)簽數(shù)量巨大時(shí)，本文算法能根據(jù)碰撞時(shí)隙的數(shù)目動(dòng)態(tài)的改變數(shù)據(jù)幀的長(zhǎng)度。可見(jiàn)本文提出的算法能夠顯著減少識(shí)別所需的總時(shí)隙數(shù)，從而減少識(shí)別總耗時(shí)，提高系統(tǒng)的識(shí)別效率。

圖3 標(biāo)簽個(gè)數(shù)為不同值時(shí)需要的總時(shí)隙數(shù)對(duì)比

由圖4可以看出FSA算法與DFSA算法的吞吐率都不高，不超過(guò)百分之三十五，而本文提出的算法的吞吐率穩(wěn)定在百分之四十五，可見(jiàn)本文算法有效地提高了系統(tǒng)的吞吐率；此外，當(dāng)標(biāo)簽數(shù)目超過(guò)一定限值時(shí)，F(xiàn)SA算法和DFSA算法的吞吐率急劇下降，而本文算法的吞吐率能基本保持穩(wěn)定，從而保證了系統(tǒng)性能的穩(wěn)定。

仿真結(jié)果表明，本文提出的算法系統(tǒng)吞吐率最高可達(dá)48%，提高了干擾環(huán)境下多標(biāo)簽系統(tǒng)的讀取效率，本算法可以有效運(yùn)用于工業(yè)現(xiàn)場(chǎng)的RFID系統(tǒng)中。

4 結(jié)束語(yǔ)

即根據(jù)待識(shí)別標(biāo)簽數(shù)目的估算值選擇初始時(shí)隙參數(shù)Q的大小，同時(shí)開(kāi)啟四個(gè)時(shí)隙接收信號(hào)，并根據(jù)每輪統(tǒng)計(jì)所得碰撞時(shí)隙數(shù)有針對(duì)性地改變下一輪數(shù)據(jù)幀的長(zhǎng)度。仿真結(jié)果表明，本算法吞吐率最高可達(dá)48%，且當(dāng)標(biāo)簽數(shù)目逐漸增多時(shí)，本算法性能較穩(wěn)定，可以有效運(yùn)用于智能制造工業(yè)現(xiàn)場(chǎng)的RFID系統(tǒng)中。

本文在DFSA算法的基礎(chǔ)上提出一種改進(jìn)型算法，

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