動態(tài)RFID系統(tǒng)中一種準確標簽估計的動態(tài)幀時隙ALOHA算法

王 達, 李曉武

(1. 湖北工業(yè)大學 太陽能高效利用湖北省協(xié)同創(chuàng)新中心， 湖北 武漢 430068； 2. 昆明理工大學 信息與自動化學院, 云南 昆明 650504； 3. 湖北工業(yè)大學 湖北省電網(wǎng)智能控制與裝備工程技術研究中心， 湖北 武漢 430068)

RFID技術是一種遠程數(shù)據(jù)錄入技術，該技術能夠較好地提高物流、超市、工廠的工作效率，RFID有如下特征：非接觸性，UFH超高頻閱讀器識別距離能夠達到1～15 m，甚至更遠；快速識別性，在多標簽環(huán)境下，大部分超高頻閱讀器的識別速度已經達到每秒識別100甚至更多的標簽，遠遠超過條碼的識別速度；較強的環(huán)境適應性，RFID能夠抗沖擊、振動、電磁、溫度和化學腐蝕影響。

通常在射頻通信系統(tǒng)中，閱讀器和標簽的通信是通過共享無線信道來實現(xiàn)的，當多個標簽同時響應閱讀器就會發(fā)生標簽碰撞，閱讀器不能正確讀到任何信息，我們把這種現(xiàn)象稱之為標簽碰撞問題，標簽碰撞使得閱讀器的讀寫速度大幅度降低。為了避免碰撞問題的發(fā)生，防碰撞協(xié)議是非常有必要的，好的防碰撞協(xié)議能夠有效提高閱讀器的標簽識別效率[1]。標簽識別效率也可以稱作吞吐量，是指單位時間(如時隙)內閱讀器識別標簽的數(shù)量[2]。迄今為止，傳統(tǒng)標簽識別環(huán)境(靜態(tài)場景)下的防碰撞協(xié)議研究已經比較成熟，這些協(xié)議可以分為兩類：隨機算法和確定算法[2-3]。通過這些算法，靜態(tài)場景下的標簽碰撞問題能夠得到較好的解決，靜態(tài)場景下的標簽識別效率能夠達到90%[3]。靜態(tài)場景下比較常見的協(xié)議類型是動態(tài)幀時隙ALOHA算法，該算法屬于隨機算法，當幀長等于未識別標簽數(shù)時，標簽的識別效率最大[4]。

RFID應用中還一類應用場景，在該場景中，標簽附著在目標的表面并沿著閱讀器信號區(qū)內的固定路徑移動，這種場景被稱為動態(tài)RFID系統(tǒng)[4-5]，動態(tài)RFID系統(tǒng)經常出現(xiàn)在物流的出入口。在動態(tài)RFID系統(tǒng)，標簽持續(xù)性的進入和離開信號區(qū)，動態(tài)RFID系統(tǒng)的概念圖見圖1。圖1中，閱讀器在標簽移動路徑的上方，陰影部分是閱讀器的應答區(qū)域，簡稱閱讀器信號區(qū)，標簽沿著直線AB和CD中間的軌道移動，標簽從左邊進入信號區(qū)，從右邊離開信號區(qū)。根據(jù)標簽的移動速度、閱讀器的長度可知標簽通過信號區(qū)所花費的時間，以上描述的場景是本論文要研究的場景。

和靜態(tài)場景RFID系統(tǒng)相比較，動態(tài)RFID系統(tǒng)的特點是：

(1) 標簽的可移動性。在識別過程中，標簽是可以移動的，閱讀器能夠對移動標簽進行識別。

(2) 標簽逗留的短暫性。標簽在閱讀器信號區(qū)內逗留時間是有限的，這和標簽移動速度、信號區(qū)長度有關，標簽在進入信號區(qū)前或離開信號區(qū)后，閱讀器不能識別標簽，標簽只有在閱讀器信號區(qū)內才有機會被識別。

(3) 標簽的丟失性。由于標簽的可移動性和標簽逗留的短暫性，標簽可能沒有被識別就離開閱讀器的信號區(qū)，這種標簽稱之為丟失標簽，在動態(tài)RFID系統(tǒng)中，減少標簽丟失是最重要的工作。評價動態(tài)RFID系統(tǒng)重要的性能指標不再是標簽識別效率，而是標簽丟失率TLR，其定義為

( 1 )

標簽丟失率TLR有如下特點：

(1) 當未識別標簽數(shù)密度過大時，標簽的丟失率會增加，如果標簽密度過大，標簽丟失不可避免，為減少標簽丟失率，減小標簽密度是必要的，實際應用中，有時標簽密度不可調整，如貼有標簽的商品已經裝入卡車中。

(2) 標簽移動速度過快，標簽丟失率會增加。如果標簽移動速度過快，標簽丟失不可避免，為減少標簽丟失率，減小標簽移動速度是必要的，當標簽密度不可調整時，調整標簽移動速度就變得很重要。

盡量降低標簽丟失率是動態(tài)RFID系統(tǒng)的重要任務，一般要求標簽的丟失率盡可能低[5]。為了降低動態(tài)RFID系統(tǒng)的標簽丟失率，需要對原有的標簽識別協(xié)議做改進，本文主要對廣泛使用的動態(tài)幀時隙協(xié)議做改進，這種改進主要體現(xiàn)在協(xié)議中的幀長調整算法，改進后的協(xié)議優(yōu)點是：

(1) 考慮了當前幀識別結果對標簽識別的影響。

(2) 考慮了新進標簽對標簽識別的影響。

(3) 考慮了部分未識別標簽離開閱讀器的信號區(qū)對標簽識別的影響。

(4) 可以用來改進動態(tài)幀時隙算法，使其能夠適應動態(tài)RFID系統(tǒng)。

由以上優(yōu)點可以看出，改進的協(xié)議綜合考慮了影響幀長的諸多因素，和傳統(tǒng)的動態(tài)幀時隙ALOHA算法相比，幀長的估計更適合于動態(tài)RFID系統(tǒng)。

1 相關工作

目前，關于如何準確確定動態(tài)RFID系統(tǒng)的標簽識別方法的研究不多，文獻[6]通過路徑損耗和多路徑效應等物理參數(shù)來判斷標簽的數(shù)量，但這并非本文研究的重點。

對于靜態(tài)場景下的RFID標簽的防碰撞協(xié)議已經研究的比較成熟[7-12]，本文首先說明一種經典的隨機型標簽防碰撞算法Vogt-DFSA[11]，該算法為本文所提協(xié)議的基礎算法，了解了Vogt-DFSA協(xié)議及其改進算法，有助于實現(xiàn)其他經典及高效協(xié)議，Vogt-DFSA協(xié)議的步驟如下：

Step1在幀循環(huán)開始時，閱讀器對信號區(qū)內的所有標簽廣播一個請求命令“Query”，該命令包括一個動態(tài)幀長參數(shù)L。

Step2信號區(qū)內所有收到“Query”命令的標簽隨機選擇一個0到L-1的時隙，然后在選擇的時隙傳輸其ID給閱讀器。對于任意時隙，根據(jù)傳輸?shù)那闆r，時隙分為空閑、成功及碰撞時隙3種?？臻e時隙指的是沒有任何標簽選擇該時隙傳輸其ID給閱讀器。成功時隙是指只有一個標簽選擇該時隙傳輸其ID。碰撞時隙表示有兩個或兩個以上標簽選擇該時隙傳輸其ID號。

Step3當一個幀所有時隙都處理完，假如出現(xiàn)E個空閑時隙，S個成功時隙，C個碰撞時隙，并且E+S+C=L。根據(jù)概率論如果碰撞時隙數(shù)C較大，可以判斷幀長設置過小，相對幀長而言，未識別標簽數(shù)過多。如果空閑時隙E較大，說明幀長設置過大，相對幀長而言，未識別標簽數(shù)較少。因此幀結束后根據(jù)當前識別狀況(如碰撞數(shù)、成功時隙數(shù)、空閑時隙數(shù))重新設置幀長是有意義的，可以減少碰撞或空閑時隙的大量出現(xiàn)。幀長設置的原則是當幀長等于未識別標簽數(shù)時，標簽的識別效率最優(yōu)。一種簡單的調整幀長方案為[11]

L=2.39×C

( 2 )

如果當前幀沒有出現(xiàn)碰撞，標簽識別處理結束；否則執(zhí)行Step1。式( 2 )假設的是未識別標簽數(shù)等于碰撞數(shù)的2.39倍。

以上是靜態(tài)場景下動態(tài)幀時隙ALOHA算法設計的主要步驟和構想，幀長調整的主要目標是使得幀長大小等于未識別標簽數(shù)，并且?guī)L調整主要依靠幀結束后的碰撞數(shù)、成功時隙數(shù)、空閑時隙數(shù)進行判斷[7-9]。

對于動態(tài)RFID系統(tǒng)，如果只依靠幀結束后的碰撞數(shù)、成功時隙數(shù)、空閑時隙數(shù)來調整幀長是不合理的。因為在動態(tài)RFID系統(tǒng)一幀執(zhí)行完后，未識別標簽數(shù)由新進標簽和當前幀引起碰撞時隙的部分標簽組成。為了分析在動態(tài)RFID系統(tǒng)中未識別標簽數(shù)，假設：

(1) 標簽的流量等于tra，單位為標簽/時隙。假如標簽流量tra等于0.8，意味著一個時隙只有0.8個標簽進入信號區(qū)，這樣規(guī)定標簽流量的單位有利于分析動態(tài)RFID系統(tǒng)的性能。

(2) 標簽的幀長用L來表示，單位為時隙。

(3) 標簽的逗留時間用Dcov表示，單位為時隙，意味著標簽通過閱讀器信號區(qū)需要Dcov個時隙，超過Dcov時隙，標簽將離開閱讀器信號區(qū)。

(4) 一幀結束后，閱讀器能統(tǒng)計到E個空閑時隙、S個成功時隙、C個碰撞時隙。

基于以上假設和分析，當前幀識別過程中，新進標簽數(shù)nnew為

nnew=tra×L

( 3 )

當前幀識別過程中，碰撞標簽也屬于未識別標簽，碰撞標簽導致的未識別標簽數(shù)nc為

nc=2.39×C

( 4 )

本文中采用碰撞時隙數(shù)的2.39倍作為參與碰撞的標簽數(shù)量[11]。因為碰撞標簽與新進標簽相比，比較接近信號區(qū)的出口，部分碰撞標簽可能沒有等到下一幀的識別就離開閱讀器信號區(qū)，為了便于理解，圖2為前后兩幀信號區(qū)內未識別標簽的分布情況。

圖2(a)為幀識別前的未識別標簽分布情況，圖2(b)中，虛線左邊為幀識別過程中進入信號區(qū)的未識別標簽分布情況，虛線右邊為參與幀識別后的未識別標簽分布，這些未識別標簽是由于標簽碰撞產生的?？梢钥闯?，當標簽流量恒定時(這是本文的研究場景)，新進標簽的標簽密度更大，而已參與幀識別標簽的標簽密度更低。因此，虛線左邊的標簽密度大于虛線右邊的標簽密度，并且，虛線右邊的標簽又分為兩份，其中，虛線右側和信號區(qū)右邊界左側的標簽是未離開信號區(qū)的碰撞標簽；信號區(qū)右邊界右側的標簽為離開信號區(qū)的未識別標簽。

( 5 )

根據(jù)以上的分析，一幀后未識別標簽數(shù)nui或新幀長L′應設置為

( 6 )

當標簽識別處于開始階段(見圖3)，圖3(a)表示閱讀器剛開始識別標簽，信號區(qū)內未識別標簽數(shù)量只分布在信號區(qū)的左邊，圖3(b)顯示一幀執(zhí)行完后，前一幀剩余未識別的標簽分布在虛線右邊，并且沒有碰撞標簽離開閱讀器的信號區(qū)，因此，式( 6 )應改變?yōu)?/p>

L=nui=tra×L+2.39×C

( 7 )

式( 7 )的使用條件為

∑L(i)

( 8 )

式( 8 )所給條件表示識別的起始若干幀長小于標簽的逗留時間Dcov時，幀長調整采用式( 7 )，否則幀長調整采用式( 6 )。在本文中不討論標簽識別末期沒有新標簽進入信號區(qū)的情況，這是因為采用動態(tài)幀時隙ALOHA算法識別標簽的閱讀器不能檢測是否有新進標簽進入。

2 動態(tài)RFID系統(tǒng)中一種考慮新進標簽動態(tài)幀時隙ALOHA協(xié)議

動態(tài)RFID系統(tǒng)中考慮新進標簽動態(tài)幀時隙ALOHA協(xié)議(以下簡稱DFSA-CN協(xié)議)的步驟為:

Step1在幀循環(huán)開始時，閱讀器對信號區(qū)內的所有標簽廣播一個請求命令“Query”，該命令包括了一個動態(tài)幀長參數(shù)L，初始幀長設置為128。

Step2信號區(qū)內所有收到“Query”命令的標簽隨機選擇一個0到L-1的時隙，然后在選擇的時隙傳輸它的ID給閱讀器。

Step3當一個幀所有時隙都處理完，根據(jù)前文分析調整下一幀的幀長，調整算法為

( 9 )

如果當前幀的成功時隙數(shù)和碰撞時隙數(shù)的和為0，標簽識別處理結束；否則執(zhí)行Step1。

Step4閱讀器識別結束的條件是成功時隙數(shù)和碰撞時隙數(shù)之和為0，因為在標簽流入信號區(qū)流量恒定的條件下，在一幀結束后，成功時隙數(shù)和碰撞時隙數(shù)之和大于0，只有當標簽流入信號區(qū)為0時，才會出現(xiàn)成功時隙數(shù)和碰撞時隙數(shù)之和為0。

從以上的算法可見，當一幀結束后，DFSA-CN協(xié)議將會考慮新進標簽和未識別標簽離開信號區(qū)對幀長的影響，這就是該協(xié)議與原有DFSA協(xié)議的關鍵不同點。

3 仿真和結果

為了評估本文所給協(xié)議的性能，把DFSA-CN和經典的動態(tài)幀時隙ALOHA協(xié)議(DFSA)進行比較，通過變化標簽流量tra、標簽逗留時間Dcov和初始幀長L三個角度分析它們對兩種協(xié)議標簽丟失率TLR的影響。本文仿真采用蒙特卡洛方法，仿真不考慮閱讀器對標簽發(fā)送指令所耗費的時間，只考慮標簽向閱讀器發(fā)送信息所耗費的時間(用時隙來表示)，因為RFID系統(tǒng)通信的主要時間損耗發(fā)生在標簽向閱讀器發(fā)送信息的過程中。

在圖4(a)為tra變化對標簽丟失率TLR的影響，該仿真實驗環(huán)境參數(shù)為：Dcov=1 000時隙，L=32時隙。仿真中，流量的單位是每時隙有多少個標簽進入閱讀器信號區(qū)內，如當標簽流量為0.5時，這表示一個時隙內有0.5個標簽進入閱讀器信號區(qū)，即兩個時隙有一個標簽進入信號區(qū)，從該仿真可見：

(1) 隨著標簽流量tra的增加，兩種協(xié)議的標簽丟失率都在增加，因為在相同的時間內進入閱讀器信號區(qū)的標簽數(shù)量更多，導致標簽丟失較多。

圖4(b)為Dcov變化對標簽丟失率TLR的影響，該仿真實驗環(huán)境參數(shù)為：tra=0.8標簽/時隙，L=32時隙。在該仿真中，標簽逗留時間單位是時隙，由圖4(b)可見：

(1) 隨著標簽逗留時間Dcov的增加，兩種協(xié)議的TRL緩慢降低，降低速度較慢，因為隨著標簽逗留時間增加，閱讀器有更多機會識別碰撞標簽，而TRL降低緩慢的原因是標簽進入信號區(qū)的流量沒有改變，標簽流量的變化是標簽丟失率變化的主要因素。

(2)在相同的標簽逗留時間Dcov條件下，DFSA-CN的標簽丟失率小于DFSA的標簽丟失率，如在標簽逗留時間為2 000時隙時，DFSA-CN丟失率為0. 206 1，而DFSA的標簽丟失率則為0.266 4，這是因為DFSA-CN協(xié)議考慮了新進信號區(qū)標簽和離開信號區(qū)標簽對標簽識別的影響。

圖4(c)為L變化對標簽丟失率TLR的影響，該仿真實驗環(huán)境參數(shù)為：tra=0.5標簽/時隙，Dcov=1 000 時隙。仿真中幀長單位是時隙，由圖4(c)可見：

(1) 隨著初始幀長L的增加，兩種協(xié)議的標簽丟失率TRL先降低后增加，這是因為太小的幀長，將導致碰撞較多，這會增加標簽的丟失率。同樣幀長太長將產生過多的空閑時隙，這也會增加標簽的丟失率。

(2) 在相同的初始幀長L條件下，DFSA-CN的標簽丟失率小于DFSA的標簽丟失率，如初始幀長為128時隙時，DFSA-CN丟失率為0.238 3，而DFSA的標簽丟失率為0.296 9，因為DFSA-CN協(xié)議考慮了新進信號區(qū)標簽和離開信號區(qū)標簽對標簽識別的影響。

圖4的仿真結果從3個角度分析了DFSA-CN協(xié)議的性能，這些仿真都顯示本文所給協(xié)議DFSA-CN具有更優(yōu)良的性能，即在相同的條件下，DFSA-CN的標簽丟失率都低于DFSA。

4 結束語

本文對動態(tài)RFID系統(tǒng)進行了深入分析，并給出適合動態(tài)RFID系統(tǒng)的DFSA-CN協(xié)議，文中分析了動態(tài)RFID系統(tǒng)未識別標簽的新進標簽、碰撞標簽組成部分，一幀結束后新標簽進入信號區(qū)的數(shù)量，一幀結束后離開信號區(qū)的碰撞標簽數(shù)量。由于所給協(xié)議DFSA-CN能準確確定未讀標簽的數(shù)量，從而給出了較為合理的幀長函數(shù)。本文調整幀長的思路可以用于改進大部分動態(tài)幀時隙ALOHA協(xié)議的標簽估計算法。