基于時隙ALOHA 的RFID 防沖突算法及其系統實現方案的分析研究

1 引言

　　無線射頻識別(RFID，Radio Frequency Identification)技術是近年來應用發展迅速的一種利用射頻通訊方式實現的無線非接觸式身份識別技術。RFID 技術應用系統[1]主要是由RFID標簽、標簽閱讀器及相應的計算機系統組成的，當系統要閱讀現場貼有RFID 標簽的對象時，系統由標簽閱讀器向RFID 標簽發送特定頻率的電磁波，RFID 標簽經電磁波的觸發將內部存儲的身份識別碼信息送出，這樣系統通過標簽閱讀器識別貨物并進行相應的信息處理。但是，如果有多個RFID 標簽接收到電磁波并同時發送信息，則標簽閱讀器接收到的信號就會互相干擾，不可避免地出現標簽閱讀沖突問題[1]。

　　目前解決RFID 標簽閱讀沖突問題主要是基于兩種防沖突算法即[1、2]：基于時隙ALOHA的防沖突算法和基于樹結構的防沖突算法。其中，前者是采用隨機選擇發送時間的方式，系統識別的可靠性相對差一些，但易于設計兌現；后者則采用二叉樹的搜索算法，系統識別的可靠性較高，但系統兌現時需要與RFID 標簽的識別碼信息相聯系，硬件設計較為復雜。因此，低成本的RFID 標簽一般是采用基于時隙ALOHA 的防沖突算法來設計的，如何提高該算法系統識別的可靠性是目前低成本RFID 標簽應用系統研究重點。

　　本文將首先介紹基于時隙ALOHA 的RFID 防沖突算法的基本實現原理，分析說明該算法的關鍵模型參數，指出設計該算法系統兌現的關鍵在于現場RFID 標簽數預測和時隙幀長確定問題，然后具體介紹幾種不同的標簽預測實現方案，并進行系統識別的性能仿真與分析，最后總結出各種情況下相對比較可行的系統實現方案。

2 基于時隙ALOHA 的RFID 防沖突算法

　　時隙ALOHA 算法（Framed Slotted ALOHA）簡稱FSA 是一種隨機時分多址方式[3] 的用戶信息通訊收發算法，它將信道用信息幀表示，把信息幀分成許多時隙 (slot)，每個標簽隨機選一個時隙來發送自己的識別碼信息。在整個信息幀的時間內每個RFID 只響應一次，如圖1 所示。

　　圖1 中每個圓圈代表一個RFID 標簽發出的識別碼信息，這樣閱讀器在整個信息幀接收過程中遇到的標簽回復有3 種情況，即：成功、空閑、沖突，它們可能分別代表在某個時隙內是一個標簽、沒有標簽或兩個以上標簽的應答。

　　實際情況中，由于各標簽距閱讀器距離不同，近距離標簽發送的信息可能覆蓋了遠距離標簽發出的信息，即使是時隙沖突，閱讀器也可能正確識別近距離標簽的信息。同樣，由于其他環境噪聲的影響，即使在一個時隙內只有一個RFID 標簽應答，閱讀器也可能無法閱讀成功。在不考慮這兩種不理想條件即捕獲效應和環境噪聲的影響[4]，若整個信息幀的時隙數設定為F，則閱讀N 個RFID 標簽時每個信息幀內成功、空閑和沖突的時隙數分別為：

　　因此，RFID 系統的閱讀吞吐率也稱識別效率即閱讀器在一個信息幀長的時間內能成功識別標簽數所占的比例可以表示為：

　　圖2 中給出利用Matlab 仿真的RFID 系統閱讀100 次積累的識別結果，其中系統仿真設定的信息幀長即時隙數設定按2 的冪次方遞增，即F 取值從16 到256 變化，橫坐標為標簽數N 從1 到1000 變化，縱坐標為閱讀吞吐率。可以看出當標簽個數接近信息幀長時，系統的吞吐率比較高，這與式（2）的結果是一致的，即最大閱讀吞吐率可通過式（2）對F進行微分即（dS/dF）F=N =0 得到。

3 RFID 標簽數預測與信息幀設定實現方案

　　在RFID 系統應用時，系統閱讀器讀取的RFID 標簽數往往是未知的。根據上面RFID多標簽閱讀的防沖突算法分析結果上看，要實現具有解決RFID防沖突算法功能的系統方案，系統需要先進行現場的RFID 標簽數預測[5]。通常可以通過以下幾種預測方法來實現：

　　1）最小預測（lowbound）[6、14]：即系統閱讀有沖突出現的話，至少有2 個以上的標簽存在，可以預測發生沖突的標簽個數至少為2*ak。

　　2）Schout 預測[4、6、12、13]：若在每個信息幀中每個標簽選擇時隙符合λ=1 的泊松分布，則信息幀中各沖突時隙平均響應的標簽個數約為2.39，這樣可以預測未識別的標簽數為2.39*ak。

　　3) Vogt 預測 [2、11]：它是通過比較實際的成功、空閑、沖突時隙數與理論的成功、空閑、沖突時隙數得出誤差最小的結果來預測未知標簽數，即：

　　其中，c1、ck、c0 為實際測得的成功、空閑、沖突時隙數值。在標簽數N 取值范圍[C1+2*CK，……，2*（C1+2*CK）]內找到最小的ε值，所對應的N 值就是預測的標簽數。圖3 分別給出采用Lowbound、Schout、Vogt 三種不同的標簽數預測實現方案的系統仿真結果，它們均先預測確定現場可能的標簽數后再來設定最佳信息幀長度，并重復閱讀100次。與FSA（即信息幀長度固定為256）相比，可以看出基于標簽數預測的系統，系統閱讀吞吐率有明顯改善。

　　但是總的來說，對于現場有大數量標簽（特別是標簽數大于500）時，采用式（2）由預測標簽數來設置最佳信息幀長度的實現方案顯然是不合適的。因此，有人提出了采用分組應答響應的方法[7]來實現，即當標簽數超過354 個時，將標簽進行分組，選擇1 組的先應答，識別完1 組之后再識別2 組……，分組數和標簽數目的關系如表一。

　　圖4 是對現場有大數量標簽（大于500）時采用分組算法和Lowbound、Schout、Vogt的預測方案比較仿真結果。可以看出采用分組算法的系統吞吐率在標簽數大于500 的時候可以達到很高，而其它幾種則降得很快。因此如果用在大規模的標簽識別時使用分組算法可以有效的提高系統的識別效率。

4 自適應信息幀時隙設置

　　從前面分析與仿真結果上看，要獲得最高的吞吐率或最佳識別效率，先得預測獲得可能的標簽數，并設置最佳的信息幀長度[5]。但是，任何RFID 系統在不同場合要識別的標簽數的變化范圍很大，要直接預測標簽數并設置好最佳信息幀長度在實際電路實現系統設計是比較復雜，且帶來額外功耗[8]。事實上，RFID 系統中常用2 的n 次冪作為信息幀長度，其中 n取1 到8（即最大的幀長為256，最小為2，但更多最小取16)，如Vogt 預測[11]提出的幀長和標簽數的關系如表二，當標簽個數在1—9 之間時，幀長采用16。

　　為了簡化實際電路的兌現設計，通常采用基于標簽數預測的冪指數信息幀長度設置方法， 如在最新的EPC Gen2 標準[15]中采用了Q-Algorithm 的自適應信息幀時隙設置方案，當一個幀中出現過多的沖突時隙時，閱讀器提前結束該幀發送一個新的更大的幀；當一個幀中出現過多的空閑時隙時，此幀也不是最佳的幀，閱讀器提前結束該幀發送一個新的小的幀。具體實現方案如圖5 所示：

　　圖5 中參數Q、Qfp 和c 均為正整數，信息幀長度為F=2^Q-1，Q 是動態變化的，初值取round(Qfp)。一個時隙之后，若該時隙是沖突時隙，則將Qfp 加上參數c；若是空閑時隙，則將Qfp 減去參數c；若是成功時隙，則Qfp 保持不變。閱讀器根據新的Q=round(Qfp)來決定是繼續發送下一個時隙還是重新開啟一個新的幀。

　　EPC Gen2 采用Q-Algorithm 在標簽數變化很大的范圍內要實現高吞吐率主要取決于參數c 的取值。c 太大會造成幀長變化過于頻繁，太小又不能迅速的實現最佳幀的選擇。在EPC標準中c 的取值并未規定，因此必須找到合適的c 取值。文獻[8]中幀長小于64 的全部取c最大值0.5，幀長64 到512 之間c 值取線性減小變化，幀長大于1024 的全部取c 最小值0.1。該取值方法比較簡單且符合實際，實現結果也較理想，如圖6。圖6 中x 軸是標簽從1 到1000變化，y 軸左邊圖形顯示識別一個標簽所需的平均時隙數為3，右邊圖形顯示在標簽數大范圍的變化內都保持較高的吞吐率。文獻[9]中提出了另外一種方案，時隙沖突和空閑時所取的c 值不等，但成一定比例，這種方案相對復雜。

　　采用EPC Gen2 標準中的算法優勢一是系統的總體識別時間較少，系統吞吐率高；二是閱讀器中初始幀長值（即Q 值）的設置不受限制，如圖7。圖7 中橫軸1 和2 分別代表標簽數200 個和400 個，Q 初值分別取1-8 的變化，發現最終的識別時間幾乎無差別，這主要就是算法自適應調整的優勢。采用EPC Gen2 標準中的算法劣勢是系統由于調整幀長過于頻繁而造成功耗的增加[10]。

5 總結

　　防沖突算法是射頻識別系統實現標簽快速識別的關鍵。本文通過對現有幾種代表性的防沖突算法的比較研究，對防沖突算法有更加深刻的理解。Vogt 提出的預測識別范圍內所有標簽的機制，預測準確度高；分組算法采用冪次變化幀長且系統的識別時間短，吞吐率高，非常適合實際的應用；EPC Gen2 標準提出的Q-Algorithm 算法使系統能自適應的調整，識別效率高，在超高頻射頻識別系統中得到廣泛的應用。

參 考 文 獻
[1] Klaus Finkenzeller 著.射頻識別技術[M].第三版.BeiJing:電子工業出版社,2006.

[2] MaurizioA.Bonuccelli,Francesca Lonetti ,Francesca Martelli. Instant collision resolution for tag identification in RFID networks[A]. Ad Hoc Networks, Elsevier, Volume 5, Issue 8, November 2007

[3] L. Burdet. RFID multiple access methods[A]. Technical Report ETH Zurich, 2004.

[4] FRITS C. SCHOUTE. Dvnamic Frame Length ALOHA[A]. IEEE Transaction on Communications,1983

[5] Jae-RyongCha ,Jae-HyunKim. Novel Anti-collision Algorithms for Fast Object Identification in RFID System [A].in Proc. International Conference on Parallel and Distributed Systems, 2005

[6] Christian Floerkemeier. Transmission control scheme for fast RFID object identification[A].IEEE PerCom Workshop on Pervasive Wireless Networking, Italy, March 2006

[7] Su-RyunLee,Sung-DonJoo,Chae-WooLee. An Enhanced Dynamic Framed Slotted ALOHA Algorithm for RFID Tag Identification[A]. Proceedings of the Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, San Diego, CA, USA, July 2005

[8] Inwhee Joe,Juno Lee. A Novel Anti-Collision Algorithm with Optimal Frame Size for RFID System[A]. 2007.SERA 2007. 5th ACIS International Conference,2007

[9]DonghwanLee,KyungkyuKim,WonjunLee. Q -Algorithm: An Enhanced RFID Tag Collision Arbitration
Algorithm[J].Computer Science, 2007, Volume 4611:23-32

[10] Jianwei Wang, Dong Wang, Yuping Zhao .A Novel Anti-Collision Algorithm with Dynamic Tag Number Estimation for RFID Systems[A]. Communication Technology, 2006. ICCT '06,Nov.2006

[11] Harald Vogt. Efficient Object Identification with Passive RFID Tags[A]. in Proceedings of the IEEE
International Conference on Systems, Man and Cybernetics (SMC '02), Hammamet, Tunisia, October 2002

[12] Qiaoling Tong, Xuecheng Zou, Dongsheng Liu,et al. Modeling the Anti-collision Process of RFID System byMarkov Chain[A].Wireless Communications, Networking and Mobile Computing, 2007. WiCom 2007

[13] Christian Floerkemeier , Matthias Wille. Comparison of Transmission Schemes for Framed ALOHA basedRFID[A]. Applications and the Internet Workshops, 2006. SAINT Workshops 2006

[14] Tae-Wook Hwang, Byong-Gyo Lee, Young Soo Kim, et al. Improved Anti-collision Scheme for High Speed Identification in RFID System[A]. Innovative Computing, Information and Control, 2006. ICICIC '06
[15] EPCTM Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for ommunications at 860 MHz – 960 MHz Version 1.1.0 Draft1, EPCglobal Inc,2005

作者簡介：
吳偉貞（1983-），女，福建莆田人，碩士生，研究方向為無線射頻識別；郭東輝（聯系人），男，教授，博士生導師.