基于時(shí)隙ALOHA 的RFID 防沖突算法及其系統(tǒng)實(shí)現(xiàn)方案的分析研究

1 引言

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

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

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

2 基于時(shí)隙ALOHA 的RFID 防沖突算法

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

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

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

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

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

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

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

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

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

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

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

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

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

4 自適應(yīng)信息幀時(shí)隙設(shè)置

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

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

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

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

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

5 總結(jié)

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

參 考 文 獻(xiàn)
[1] Klaus Finkenzeller 著.射頻識(shí)別技術(shù)[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-），女，福建莆田人，碩士生，研究方向?yàn)闊o線射頻識(shí)別；郭東輝（聯(lián)系人），男，教授，博士生導(dǎo)師.