雷隆毓, 周向陽

(貴州大學 電氣工程學院, 貴陽50025)

0 引 言

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

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

1 問題描述

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

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

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

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

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

1.2 系統(tǒng)吞吐率

設閱讀器的幀長為L,閱讀器作用范圍內的標簽總數(shù)為n,當任一時隙中有r 個標簽,其概率服從二項分布定理,且某個標簽處于幀內任一時隙的概率為：

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

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

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

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

1.3 常用標簽估計算法

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

(1)最小值估計算法。 某一時隙發(fā)生碰撞時至少有兩個標簽,因為設置為未識別標簽數(shù)至少為碰撞數(shù)目的兩倍。 該估計算法簡單,但當標簽數(shù)量較大時,其誤差率較大。

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

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

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

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

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

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

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

2 標簽估計算法

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

2.1 本文思想

本文算法思想為：理想中成功時隙與空閑時隙的比例對應實際成功時隙與空閑時隙的比例,從而計算出標簽總數(shù)。

已知(3)式為某個時隙沒有標簽的概率,則某幀長內空閑時隙數(shù)目的數(shù)學期望為公式(3)乘上幀長。 同理可得某幀長內成功時隙數(shù)目的數(shù)學期望。

可得公式(7)為某幀長內空閑時隙數(shù)目的數(shù)學期望：

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

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

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

2.2 算法過程

(1)閱讀器設定一個幀長,并發(fā)出識別命令。

(2)標簽響應,并返回預定時隙。

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

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

(5)閱讀器發(fā)出多次識別命令,收集標簽返回的時隙預定結果,求出該幀長內的標簽總數(shù),轉(6)。

(6)進行第一次識別,識別后下一幀,幀長設定為標簽總數(shù)減去上一幀的成功時隙數(shù)。

3 仿真驗證

本文使用隨機數(shù)據(jù)對本文算法進行仿真驗證,對本文算法和其他算法做一個對比。

3.1 仿真環(huán)境

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

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

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

3.3 對比算法介紹

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

3.4 仿真情況

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

圖1 擬合對比圖Fig. 1 Matching comparison

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

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

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

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

當幀長為180 時,隨著標簽數(shù)量的增加,成功時隙／空閑時隙的比例,結果如圖3 所示。

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

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

4 結束語

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

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

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

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

誤差較大,一次的成功時隙和空閑時隙的發(fā)生情況存在不穩(wěn)定性,因為用于判斷標簽總數(shù)存在誤差,且誤差率較大,因而只能運用于大致比較,可使用于確認是否需要使用分組算法。

需要大量的數(shù)據(jù)基礎,因為成功時隙和空閑時隙的不穩(wěn)定性,因此需要閱讀器多次發(fā)出識別信號以獲得大量的數(shù)據(jù)基礎,從而保證結果穩(wěn)定。