一種RFID 標(biāo)簽估算方法

雷隆毓, 周向陽(yáng)

(貴州大學(xué) 電氣工程學(xué)院, 貴陽(yáng)50025)

0 引 言

無線射頻識(shí)別技術(shù) RFID(Radio Frequency Identi-fication)是一種自動(dòng)識(shí)別技術(shù),該技術(shù)具有許多優(yōu)點(diǎn),如抗干擾能力強(qiáng)、信息量大等。 但在RFID系統(tǒng)中,讀寫器可識(shí)別的范圍內(nèi),極容易出現(xiàn)多個(gè)標(biāo)簽同時(shí)返回閱讀器的請(qǐng)求,從而發(fā)生信息碰撞,使得閱讀器無法識(shí)別到碰撞標(biāo)簽,甚至?xí)霈F(xiàn)“標(biāo)簽饑餓”的情形。 如何在提高系統(tǒng)有效識(shí)別率和吞吐量的情況下解決標(biāo)簽間的碰撞,成為多標(biāo)簽防碰撞最為核心的問題。 因天線系統(tǒng)、讀寫器、標(biāo)簽成本和實(shí)際實(shí)現(xiàn)問題,空分多址,碼分多址,頻分多址三種訪問接入方法不適用于實(shí)際使用操作,因此RFID 系統(tǒng)通常使用時(shí)分多址方式進(jìn)行數(shù)據(jù)通信［1］。

時(shí)分多址訪問接入方式的多標(biāo)簽防碰撞算法分為兩種：一種是非確定性的ALOHA 算法,具體可分為：純ALOHA 算法、時(shí)隙ALOHA(Slotted ALOHA,SA)算法、幀時(shí)隙ALOHA(Frame-Slotted ALOHA,FSA)算法、動(dòng)態(tài)幀時(shí)隙ALOHA(Dynamic Frame-SlottedALOHA, DFSA) 算 法、 改 進(jìn) 動(dòng) 態(tài) 幀 時(shí) 隙ALOHA(Modi-fied Dynamic Frame- Slotted ALOHA,MDFSA)、分組動(dòng)態(tài)幀時(shí)隙ALOHA(Group Dynamic Frame- SlottedALOHA,GDFSA)算法。 對(duì)于另一種確定型的二進(jìn)制樹算法,因能保證所有的標(biāo)簽排列識(shí)別,而不會(huì)出現(xiàn)“標(biāo)簽饑餓”的問題,但會(huì)因?yàn)殚喿x器與標(biāo)簽之間的通信信息量,導(dǎo)致查詢?nèi)康臉?biāo)簽需要時(shí)間較長(zhǎng),系統(tǒng)負(fù)荷量大。 因等待時(shí)間過長(zhǎng),使得標(biāo)簽丟失量變大。 而概率型的ALOHA 算法對(duì)標(biāo)簽的要求相對(duì)較低,但不確定的隨機(jī)性,會(huì)出現(xiàn)“標(biāo)簽饑餓”問題。 因?yàn)樵撍惴ǖ牟淮_定性,系統(tǒng)識(shí)別效率較低,且僅當(dāng)標(biāo)簽數(shù)目和閱讀器給定的時(shí)隙數(shù)目一致時(shí)系統(tǒng)的識(shí)別效率平均值可達(dá)最大36.8%［1］。

1 問題描述

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

在幀時(shí)隙ALOHA(FSA)算法中,當(dāng)隙數(shù)和標(biāo)簽數(shù)相等時(shí),可得到系統(tǒng)的最大吞吐量36.8%,在實(shí)際中,標(biāo)簽中存儲(chǔ)數(shù)據(jù)的寄存器占8 位,因此標(biāo)簽的ID 的范圍為1～256 之間(十進(jìn)制)。 而實(shí)驗(yàn)測(cè)試結(jié)果發(fā)現(xiàn),當(dāng)幀時(shí)隙取值為256 時(shí)系統(tǒng)已經(jīng)達(dá)最大吞吐率。 在實(shí)際操作的過程中,在捕獲效應(yīng)和環(huán)境噪聲等各種因素的影響下,標(biāo)簽的吞吐量常常無法達(dá)到最大值。 因此,在FSA 算法的基礎(chǔ)上提出了動(dòng)態(tài)幀時(shí)隙ALOHA(DFSA)算法。

DFSA 算法的步驟：閱讀器通過標(biāo)簽估計(jì)算法估計(jì)其閱讀范圍內(nèi)的標(biāo)簽數(shù)目n,設(shè)定一個(gè)幀長(zhǎng)為L(zhǎng)的幀時(shí)隙,并發(fā)送查詢指令至標(biāo)簽,標(biāo)簽在接受指令后隨即產(chǎn)生一個(gè)在1～L 范圍內(nèi)的隨機(jī)數(shù),并在該隨機(jī)數(shù)對(duì)應(yīng)的時(shí)隙時(shí)刻響應(yīng)。 若出現(xiàn)了碰撞,則閱讀器讓碰撞的標(biāo)簽停止發(fā)送數(shù)據(jù),等待下一幀的時(shí)隙安排。 該幀識(shí)別結(jié)束,重新進(jìn)行估計(jì)標(biāo)簽估計(jì),調(diào)整幀長(zhǎng),進(jìn)行下一幀的識(shí)別［2］。

DFSA 算法可以根據(jù)標(biāo)簽數(shù)量動(dòng)態(tài)調(diào)整幀長(zhǎng),較好地適應(yīng)系統(tǒng)變化,然而最大吞吐率到達(dá)的一個(gè)條件為標(biāo)簽數(shù)和幀長(zhǎng)一致。 但實(shí)際操作中,無法準(zhǔn)確的得知標(biāo)簽總數(shù),標(biāo)簽數(shù)量不能直接提供給閱讀器,導(dǎo)致系統(tǒng)的吞吐率無法得到最大值,所以如何估計(jì)標(biāo)簽算法成為DFSA 算法中的一個(gè)重要的研究方向［3］。

標(biāo)簽估計(jì)算法往往使用于每次碰撞之后,估計(jì)剩下的標(biāo)簽數(shù)量,即標(biāo)簽估計(jì)算法一般是基于上一幀的碰撞情況,從而估計(jì)標(biāo)簽總數(shù)或者下一幀的幀長(zhǎng)設(shè)定。

1.2 系統(tǒng)吞吐率

設(shè)閱讀器的幀長(zhǎng)為L(zhǎng),閱讀器作用范圍內(nèi)的標(biāo)簽總數(shù)為n,當(dāng)任一時(shí)隙中有r 個(gè)標(biāo)簽,其概率服從二項(xiàng)分布定理,且某個(gè)標(biāo)簽處于幀內(nèi)任一時(shí)隙的概率為：

空時(shí)隙的發(fā)生概率為：

成功時(shí)隙的發(fā)生概率為：

動(dòng)態(tài)幀時(shí)隙ALOHA 算法的吞吐率函數(shù)表達(dá)式(不考慮通信干擾的情況)為：

式(6)對(duì)n 求導(dǎo)后,可得出最優(yōu)幀的大小為L(zhǎng) =n ＋1,而再代入(5)式中,可知道系統(tǒng)的最大吞吐率穩(wěn)定在36.8%［4］。

1.3 常用標(biāo)簽估計(jì)算法

系統(tǒng)的吞吐率主要取決于標(biāo)簽個(gè)數(shù)的估計(jì)以及幀長(zhǎng)的調(diào)整,特別是標(biāo)簽總數(shù)的估計(jì)。 目前有幾種主要的標(biāo)簽估計(jì)算法：

(1)最小值估計(jì)算法。 某一時(shí)隙發(fā)生碰撞時(shí)至少有兩個(gè)標(biāo)簽,因?yàn)樵O(shè)置為未識(shí)別標(biāo)簽數(shù)至少為碰撞數(shù)目的兩倍。 該估計(jì)算法簡(jiǎn)單,但當(dāng)標(biāo)簽數(shù)量較大時(shí),其誤差率較大。

(2)Schoute 算法。 在最小值標(biāo)簽估計(jì)算法的基礎(chǔ)上改進(jìn),因標(biāo)簽識(shí)別過程中整體服從泊松分布,計(jì)算得知各碰撞時(shí)隙平均響應(yīng)的標(biāo)簽個(gè)數(shù)約為2.39,可以預(yù)測(cè)未識(shí)別標(biāo)簽的個(gè)數(shù)為2.39 乘碰撞時(shí)隙數(shù)目。 該算法比最小值估計(jì)算法更加精確。

(3)Vogt 法。 利用切比雪夫不等式法估計(jì)標(biāo)簽數(shù)量,根據(jù)理論成功、空閑、碰撞時(shí)隙與實(shí)際時(shí)隙對(duì)比,找出最小誤差結(jié)果,從而估計(jì)標(biāo)簽數(shù)量。 該算法適用于標(biāo)簽動(dòng)態(tài)增加,精確度較高,但其計(jì)算復(fù)雜度也較高。

(4)偽貝葉斯法。 將閱讀器前一次的碰撞、空閑、成功時(shí)隙數(shù)作為一個(gè)先驗(yàn)分布,從此求出標(biāo)簽的一個(gè)概率分布函數(shù),通過數(shù)學(xué)期望來估計(jì)標(biāo)簽數(shù)目。

(5)生日悖論標(biāo)簽估計(jì)法。 利用同一天生日的概率問題對(duì)應(yīng)發(fā)生碰撞的概率,計(jì)算出成功識(shí)別的概率和碰撞概率,從而估計(jì)標(biāo)簽總數(shù)。

(6)Khandelwal 標(biāo)簽估計(jì)法。 通過空閑時(shí)隙所占總時(shí)隙的概率估算標(biāo)簽的總數(shù)量,當(dāng)空閑時(shí)隙增加時(shí),動(dòng)態(tài)地估計(jì)標(biāo)簽的數(shù)量。

(7)Tag Estimation Method I 法。 利用碰撞率(碰撞時(shí)隙數(shù)與幀長(zhǎng)的比值)估算標(biāo)簽總數(shù)。

(8)最小均方差法。 該算法使用切比雪夫定理和最小均方差相結(jié)合的方法來估計(jì)標(biāo)簽數(shù)量。 根據(jù)切比雪夫定理可知,每個(gè)標(biāo)簽識(shí)別周期結(jié)束時(shí),已識(shí)別標(biāo)簽數(shù)和標(biāo)簽總數(shù)之比會(huì)收斂到一個(gè)值。

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

在DFSA 算法中,當(dāng)幀長(zhǎng)等于待識(shí)別標(biāo)簽個(gè)數(shù)時(shí),理論上可以得到最大的系統(tǒng)吞吐率。 通過對(duì)前面幾種不同的標(biāo)簽估計(jì)算法的比較和研究,多種數(shù)學(xué)規(guī)則和概率原則已經(jīng)應(yīng)用了許多,本文給出一種研究時(shí)隙比例的思想,大致估算標(biāo)簽總數(shù)。

2.1 本文思想

本文算法思想為：理想中成功時(shí)隙與空閑時(shí)隙的比例對(duì)應(yīng)實(shí)際成功時(shí)隙與空閑時(shí)隙的比例,從而計(jì)算出標(biāo)簽總數(shù)。

已知(3)式為某個(gè)時(shí)隙沒有標(biāo)簽的概率,則某幀長(zhǎng)內(nèi)空閑時(shí)隙數(shù)目的數(shù)學(xué)期望為公式(3)乘上幀長(zhǎng)。 同理可得某幀長(zhǎng)內(nèi)成功時(shí)隙數(shù)目的數(shù)學(xué)期望。

可得公式(7)為某幀長(zhǎng)內(nèi)空閑時(shí)隙數(shù)目的數(shù)學(xué)期望：

由公式(9)可以看出當(dāng)中含有標(biāo)簽總數(shù)和幀長(zhǎng),因而可以利用實(shí)際中的成功時(shí)隙和空閑時(shí)隙的比例,通過該比例計(jì)算出標(biāo)簽總數(shù)。 但由于實(shí)際中一次碰撞出現(xiàn)的成功時(shí)隙和空閑時(shí)隙的結(jié)果有不確定性,如果使用該公式,需要具備一定的數(shù)據(jù)基礎(chǔ)。

通過對(duì)公式(6)求導(dǎo), 得出最優(yōu)幀長(zhǎng)為n ＋1,即L = n ＋1 ,對(duì)比公式(9),可知：當(dāng)系統(tǒng)達(dá)到最佳吞吐率時(shí),幀長(zhǎng)L =n ＋1,成功時(shí)隙和空閑時(shí)隙的比值為1,即成功時(shí)隙與空閑時(shí)隙相等。

因此可以得出結(jié)論：即得到最佳吞吐率時(shí),理論空閑時(shí)隙數(shù)目與成功時(shí)隙數(shù)目相等。 可以利用成功時(shí)隙與空閑時(shí)隙的比例來判斷標(biāo)簽總數(shù)是否大于幀長(zhǎng),當(dāng)標(biāo)簽總數(shù)大于256 最大幀長(zhǎng)時(shí),可以進(jìn)行標(biāo)簽分組。 由于碰撞出現(xiàn)的空閑時(shí)隙和成功時(shí)隙的結(jié)果不穩(wěn)定,所以只能通過比例是否明顯大于1 來判定標(biāo)簽總數(shù)和幀長(zhǎng)的關(guān)系。

2.2 算法過程

(1)閱讀器設(shè)定一個(gè)幀長(zhǎng),并發(fā)出識(shí)別命令。

(2)標(biāo)簽響應(yīng),并返回預(yù)定時(shí)隙。

(3)閱讀器通過對(duì)比成功時(shí)隙及空閑時(shí)隙的比例關(guān)系,確定是否分組。 若成功時(shí)隙和空閑時(shí)隙的比值遠(yuǎn)遠(yuǎn)大于1,則得出標(biāo)簽總數(shù)大于幀長(zhǎng),需要更改幀長(zhǎng)或者進(jìn)行分組算法進(jìn)行識(shí)別,轉(zhuǎn)(4),否則轉(zhuǎn)(5)。

(4)使用分組算法,分組后閱讀器重新設(shè)定幀長(zhǎng)并發(fā)出多次識(shí)別命令,收集多次返回的預(yù)定時(shí)隙結(jié)果,取得均值后求出該幀長(zhǎng)內(nèi)的標(biāo)簽總數(shù),轉(zhuǎn)(6)。

(5)閱讀器發(fā)出多次識(shí)別命令,收集標(biāo)簽返回的時(shí)隙預(yù)定結(jié)果,求出該幀長(zhǎng)內(nèi)的標(biāo)簽總數(shù),轉(zhuǎn)(6)。

(6)進(jìn)行第一次識(shí)別,識(shí)別后下一幀,幀長(zhǎng)設(shè)定為標(biāo)簽總數(shù)減去上一幀的成功時(shí)隙數(shù)。

3 仿真驗(yàn)證

本文使用隨機(jī)數(shù)據(jù)對(duì)本文算法進(jìn)行仿真驗(yàn)證,對(duì)本文算法和其他算法做一個(gè)對(duì)比。

3.1 仿真環(huán)境

本文算法代碼使用MATLAB 語(yǔ)言實(shí)現(xiàn),硬件環(huán)境是8 核Intel i5 處理器,內(nèi)存為8GB,硬盤為1TB的筆記本,底層操作系統(tǒng)為Windows 10。

3.2 仿真數(shù)據(jù)

本文算法使用隨機(jī)數(shù)據(jù),使用MATLAB 內(nèi)部函數(shù)生成隨機(jī)數(shù),仿真的標(biāo)簽總數(shù)由1 到300。

3.3 對(duì)比算法介紹

在Schoute 標(biāo)簽估算算法中,所有標(biāo)簽在一幀內(nèi)符合λ = 1 的泊松分布,則每個(gè)碰撞時(shí)隙中平均有2.39 個(gè)標(biāo)簽,因此當(dāng)標(biāo)簽數(shù)等于幀長(zhǎng)的情況下得到L=n=2.39*C,C 為上一幀碰撞總數(shù)。 這個(gè)結(jié)果是在最大系統(tǒng)效率前提下得出的,該方法精度不高,但是算法相對(duì)簡(jiǎn)單［5］。

3.4 仿真情況

對(duì)本文想法做了一次碰撞之后的仿真,運(yùn)用MATLAB 對(duì)第一次碰撞結(jié)果仿真標(biāo)簽總數(shù)由1 到300,同時(shí)找了y=x 線性方程作為標(biāo)準(zhǔn)線,圖1 為仿真結(jié)果。

圖1 擬合對(duì)比圖Fig. 1 Matching comparison

由圖1 可看出本想法與實(shí)際的標(biāo)簽量走勢(shì)一致,但是結(jié)果極不穩(wěn)定,這是因?yàn)闃?biāo)簽實(shí)際碰撞得出的空閑時(shí)隙和成功時(shí)隙的結(jié)果不穩(wěn)定,而本文想法為理想的碰撞結(jié)果,因此需要大量的數(shù)據(jù)基礎(chǔ)。

進(jìn)行了100 次本文算法的仿真并取平均值后,得到了圖2,作為對(duì)比,這里加上了一次函數(shù)與Schoute 算法作為對(duì)比。

由圖2 的結(jié)果可以看出當(dāng)實(shí)驗(yàn)100 次后,本文方法能夠很好的擬合出標(biāo)簽總數(shù),甚至要比Schoute算法更加貼近標(biāo)準(zhǔn)線y = x。

圖2 100 次數(shù)據(jù)基礎(chǔ)下的擬合對(duì)比圖Fig. 2 Matching comparison chart based on 100 times data

當(dāng)幀長(zhǎng)為180 時(shí),隨著標(biāo)簽數(shù)量的增加,成功時(shí)隙／空閑時(shí)隙的比例,結(jié)果如圖3 所示。

圖3 成功時(shí)隙／空閑時(shí)隙隨標(biāo)簽總數(shù)變化Fig. 3 Change of successful time slot ／ idle time slot with the total number of tags

由圖3 可以看出,隨著標(biāo)簽數(shù)量的增加,成功時(shí)隙／空閑時(shí)隙的比值越來越大,而在150 到180 左右達(dá)到1,即當(dāng)標(biāo)簽總數(shù)小于幀長(zhǎng)時(shí),成功時(shí)隙小于空閑時(shí)隙；而當(dāng)標(biāo)簽總數(shù)大于幀長(zhǎng)時(shí),成功時(shí)隙大于空閑時(shí)隙；當(dāng)標(biāo)簽總數(shù)與幀長(zhǎng)相等時(shí),空閑時(shí)隙與成功時(shí)隙相等。

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

(1)適用于分組算法,利用第一次碰撞時(shí)出現(xiàn)的空閑時(shí)隙和成功時(shí)隙的比例,判斷標(biāo)簽總數(shù)與幀長(zhǎng)的關(guān)系。 當(dāng)成功時(shí)隙大于空閑時(shí)隙,即成功時(shí)隙／空閑時(shí)隙＞1 時(shí),標(biāo)簽總數(shù)大于幀長(zhǎng)；當(dāng)成功時(shí)隙小于空閑時(shí)隙,即成功時(shí)隙／空閑時(shí)隙＜1 時(shí),標(biāo)簽總數(shù)小于幀長(zhǎng)。

算法具體實(shí)施方法：首次識(shí)別,設(shè)定一個(gè)幀長(zhǎng),通過識(shí)別后得到碰撞結(jié)果,得出成功時(shí)隙和空閑時(shí)隙的比例,判斷標(biāo)簽總數(shù)與幀長(zhǎng)的關(guān)系,若成功時(shí)隙和空閑時(shí)隙的比值遠(yuǎn)遠(yuǎn)大于1,則得出標(biāo)簽總數(shù)大于幀長(zhǎng),需要更改幀長(zhǎng)或者進(jìn)行分組算法進(jìn)行識(shí)別。

(2)適用于估計(jì)標(biāo)簽總數(shù),識(shí)別標(biāo)簽前,模擬100 次碰撞結(jié)果,得出成功時(shí)隙和空閑時(shí)隙的比例,再利用公式(9),計(jì)算得出標(biāo)簽總數(shù)n。

算法具體實(shí)施方法：當(dāng)閱讀器進(jìn)行識(shí)別時(shí),向標(biāo)簽發(fā)出多次識(shí)別信號(hào),收集多次的成功時(shí)隙和空閑時(shí)隙的結(jié)果,取得均值后求得標(biāo)簽總數(shù)。 進(jìn)行識(shí)別,幀長(zhǎng)設(shè)定為最開始的標(biāo)簽總數(shù)減成功時(shí)隙。本文算法的缺點(diǎn)：

誤差較大,一次的成功時(shí)隙和空閑時(shí)隙的發(fā)生情況存在不穩(wěn)定性,因?yàn)橛糜谂袛鄻?biāo)簽總數(shù)存在誤差,且誤差率較大,因而只能運(yùn)用于大致比較,可使用于確認(rèn)是否需要使用分組算法。

需要大量的數(shù)據(jù)基礎(chǔ),因?yàn)槌晒r(shí)隙和空閑時(shí)隙的不穩(wěn)定性,因此需要閱讀器多次發(fā)出識(shí)別信號(hào)以獲得大量的數(shù)據(jù)基礎(chǔ),從而保證結(jié)果穩(wěn)定。