1 引言

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

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

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

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

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

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

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

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

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

3 RFID 標簽數(shù)預測與信息幀設定實現(xiàn)方案

　　在RFID 系統(tǒng)應用時，系統(tǒng)閱讀器讀取的RFID 標簽數(shù)往往是未知的。根據(jù)上面RFID多標簽閱讀的防沖突算法分析結(jié)果上看，要實現(xiàn)具有解決RFID防沖突算法功能的系統(tǒng)方案，系統(tǒng)需要先進行現(xiàn)場的RFID 標簽數(shù)預測[5]。通?？梢酝ㄟ^以下幾種預測方法來實現(xiàn)：

　　1）最小預測（lowbound）[6、14]：即系統(tǒng)閱讀有沖突出現(xiàn)的話，至少有2 個以上的標簽存在，可以預測發(fā)生沖突的標簽個數(shù)至少為2*ak。

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

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

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

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

　　圖4 是對現(xiàn)場有大數(shù)量標簽（大于500）時采用分組算法和Lowbound、Schout、Vogt的預測方案比較仿真結(jié)果?？梢钥闯霾捎梅纸M算法的系統(tǒng)吞吐率在標簽數(shù)大于500 的時候可以達到很高，而其它幾種則降得很快。因此如果用在大規(guī)模的標簽識別時使用分組算法可以有效的提高系統(tǒng)的識別效率。

4 自適應信息幀時隙設置

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

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

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

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

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

5 總結(jié)

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

參 考 文 獻
[1] Klaus Finkenzeller 著.射頻識別技術[M].第三版.BeiJing:電子工業(yè)出版社,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-），女，福建莆田人，碩士生，研究方向為無線射頻識別；郭東輝（聯(lián)系人），男，教授，博士生導師.