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

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

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

0 引言

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

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

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

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

1 傳統(tǒng)ALOHA算法

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

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

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

1.1 純ALOHA算法

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

1.2 幀時隙ALOHA算法

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

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

圖2 幀時隙ALOHA算法工作過程示意圖

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

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

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

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

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

可以得出：

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

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

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

1.3 動態(tài)幀時隙ALOHA算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真分析

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

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

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

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

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

4 結(jié)束語

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

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

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