動態RFID系統中一種準確標簽估計的動態幀時隙ALOHA算法

王 達, 李曉武

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

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

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

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

和靜態場景RFID系統相比較，動態RFID系統的特點是：

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

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

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

( 1 )

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

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

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

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

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

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

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

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

由以上優點可以看出，改進的協議綜合考慮了影響幀長的諸多因素，和傳統的動態幀時隙ALOHA算法相比，幀長的估計更適合于動態RFID系統。

1 相關工作

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

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

Step1在幀循環開始時，閱讀器對信號區內的所有標簽廣播一個請求命令“Query”，該命令包括一個動態幀長參數L。

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

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

L=2.39×C

( 2 )

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

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

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

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

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

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

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

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

nnew=tra×L

( 3 )

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

nc=2.39×C

( 4 )

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

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

( 5 )

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

( 6 )

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

L=nui=tra×L+2.39×C

( 7 )

式( 7 )的使用條件為

∑L(i)

( 8 )

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

2 動態RFID系統中一種考慮新進標簽動態幀時隙ALOHA協議

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

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

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

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

( 9 )

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

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

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

3 仿真和結果

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

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

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

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

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

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

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

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

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

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

4 結束語

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