宋瑞玲，高仲合

（曲阜師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，山東 日照 276826）

0 引言

射頻識(shí)別（RFID，Radio Frequency Identification）是一種使用射頻通信實(shí)現(xiàn)的非接觸式自動(dòng)識(shí)別技術(shù)[1]。根據(jù)射頻耦合方式的不同[2]，RFID可以分為電感耦合方式和反向散射耦合方式，根據(jù)供電方式的不同，標(biāo)簽又可以分為主動(dòng)式標(biāo)簽和被動(dòng)式標(biāo)簽。典型的RFID系統(tǒng)主要由標(biāo)簽（Tag）、閱讀器（Reader）和天線（Antenna）3部分組成[3]，閱讀器和電子標(biāo)簽之間信號(hào)傳輸是通過閱讀器和電子標(biāo)簽上的天線耦合來完成的，信息交互通常是采用詢問-問答的方式。目前，RFID技術(shù)由于其自身免接觸、識(shí)別距離遠(yuǎn)、可以同時(shí)識(shí)別多個(gè)運(yùn)動(dòng)物體等優(yōu)點(diǎn)而廣泛應(yīng)用于多個(gè)領(lǐng)域。

電子標(biāo)簽碰撞問題是指當(dāng)閱讀器向工作場(chǎng)區(qū)內(nèi)的一組電子標(biāo)簽發(fā)出查詢指令時(shí)，有2個(gè)或2個(gè)以上的電子標(biāo)簽同時(shí)響應(yīng)閱讀器的查詢，返回信息產(chǎn)生相互干擾，從而導(dǎo)致閱讀器不能正確識(shí)別其中任何一個(gè)電子標(biāo)簽的信息，為了解決這個(gè)問題，必須采用防碰撞算法。防碰撞算法一般采用時(shí)分多址方式，目前采用ALOHA算法和二進(jìn)制搜索樹型算法來解決讀寫器碰撞[4]?；贏LOHA的算法簡(jiǎn)單易行而被廣泛應(yīng)用。基于ALOHA算法有純ALOHA算法、幀時(shí)隙 ALOHA算法、動(dòng)態(tài)幀時(shí)隙 ALOHA算法[5]（DFSA，Dynamic Frame Slotted ALOHA Algorithm）分組的動(dòng)態(tài)幀時(shí)隙 ALOHA算法[6]。本文介紹的算法是在分組的動(dòng)態(tài)幀時(shí)隙 ALOHA算法的基礎(chǔ)上提出來的。

1 多種防碰撞技術(shù)

1.1 純ALOHA算法

純ALOHA算法的思想很簡(jiǎn)單，即只要有數(shù)據(jù)待發(fā)，就可以發(fā)送，向閱讀器發(fā)送數(shù)據(jù)是隨機(jī)的，不需要同步，并且沒有檢測(cè)機(jī)制，雖然實(shí)現(xiàn)起來簡(jiǎn)單，但是發(fā)生碰撞的幾率很大。所以純ALOHA算法的信道利用率不高，吞吐率最大約18.4%。

1.2 時(shí)隙ALOHA算法

時(shí)隙算法是在純 ALOAH算法的基礎(chǔ)上改進(jìn)的，時(shí)隙ALOHA算法是將時(shí)間分為多個(gè)離散時(shí)隙，標(biāo)簽只能在時(shí)隙的起始發(fā)送數(shù)據(jù)，這種算法必須有全局的時(shí)間同步。該算法相比于純ALOHA算法，信道利用率理論上能提高一倍。但是，該算法只是在電子標(biāo)簽較少時(shí)，才能表現(xiàn)出較好的性能，在標(biāo)簽數(shù)增多時(shí)系統(tǒng)性能會(huì)急劇惡化。系統(tǒng)的吞吐率 S和幀產(chǎn)生率G的關(guān)系如圖1所示。

圖1 純ALOHA和時(shí)隙的ALOHA算法吞吐率

由圖1可以看到純ALOHA算法當(dāng)G=0.5時(shí)吞吐率S達(dá)到最大約是18.4%，時(shí)隙ALOHA算法當(dāng)G=1時(shí)吞吐率最大約36.8%。

1.3 幀時(shí)隙ALOHA算法

幀時(shí)隙ALOHA算法是在時(shí)隙ALOHA算法的基礎(chǔ)上提出的，將N個(gè)時(shí)隙組成一幀，標(biāo)簽在N個(gè)時(shí)隙中隨機(jī)選擇一個(gè)時(shí)隙發(fā)送信息。幀時(shí)隙要求閱讀器和標(biāo)簽數(shù)之間的同步操作，并且每幀的最大時(shí)隙數(shù)N需要預(yù)先設(shè)定。讀寫器附近所有標(biāo)簽服從相同的統(tǒng)計(jì)規(guī)律，且在同一幀的標(biāo)簽機(jī)會(huì)均等，則 r個(gè)標(biāo)簽出現(xiàn)在某個(gè)給定時(shí)隙概率服從二項(xiàng)分布。

令一幀的時(shí)隙數(shù)為N，標(biāo)簽數(shù)為n,則有r個(gè)標(biāo)簽發(fā)生在某一時(shí)隙的概率是:

某個(gè)時(shí)隙中只有一個(gè)標(biāo)簽發(fā)生的概率為:

則所有標(biāo)簽中被成功讀取的標(biāo)簽數(shù)為:

系統(tǒng)的吞吐率:

對(duì)式（4）求導(dǎo)數(shù)，得出到:

所以當(dāng)閱讀器的幀時(shí)隙數(shù)跟標(biāo)簽數(shù)目相等時(shí)，系統(tǒng)吞吐率最大。N的不同取值對(duì)應(yīng)的系統(tǒng)吞吐率如圖2所示。

圖2 不同幀長(zhǎng)對(duì)應(yīng)吞吐率

1.4 動(dòng)態(tài)幀時(shí)隙ALOHA算法（DFSA）

由式（5）知幀長(zhǎng)和標(biāo)簽數(shù)相等時(shí)系統(tǒng)吞吐率最大，但是幀時(shí)隙ALOHA算法由于幀長(zhǎng)固定會(huì)出現(xiàn)標(biāo)簽數(shù)量和幀長(zhǎng)不均衡問題，問了解決這個(gè)問題，出現(xiàn)了動(dòng)態(tài)幀時(shí)隙ALOHA算法，它的思想是根據(jù)前一陣的讀取結(jié)果動(dòng)態(tài)減少或增加下一幀的時(shí)隙數(shù)。

有一點(diǎn)值得注意，就是閱讀器設(shè)定的幀時(shí)隙數(shù)是定值[7]，如 1、8、16、32、64、128、256。所以我們經(jīng)常根據(jù)上一輪估算未識(shí)讀的標(biāo)簽數(shù)以如下方法來確定下一幀長(zhǎng)，如表1所示。

表1 不同標(biāo)簽個(gè)數(shù)對(duì)應(yīng)幀長(zhǎng)度

2 改進(jìn)的分組動(dòng)態(tài)幀時(shí)隙ALOHA算法

2.1 分組動(dòng)態(tài)幀時(shí)隙算法

在動(dòng)態(tài)幀時(shí)隙算法中，由于硬件的限制，幀長(zhǎng)并不能無限的增大，目前所允許的最大幀長(zhǎng)一般不大于256。如果標(biāo)簽數(shù)量增加到遠(yuǎn)遠(yuǎn)大于256時(shí)，由圖2可以看到系統(tǒng)吞吐率明顯在下降。分組動(dòng)態(tài)幀時(shí)隙算法思想是先估算未讀標(biāo)簽的數(shù)量[8]，如果標(biāo)簽數(shù)小于256，直接利用動(dòng)態(tài)幀時(shí)隙算法使幀長(zhǎng)度盡可能的接近標(biāo)簽數(shù)；如果大于256就把要識(shí)讀的標(biāo)簽先分組,每次只識(shí)別其中的一組，從而改善標(biāo)簽過多系統(tǒng)吞吐率下降的問題。

2.2 算法思想

傳統(tǒng)的分組算法，閱讀器把標(biāo)簽分成若干組，然后一組一組地將標(biāo)簽識(shí)別出來，在每一組中閱讀器必須不斷的調(diào)整幀的長(zhǎng)度，直到這一組的標(biāo)簽被全部識(shí)別。

本文改進(jìn)算法的思路:

1）閱讀器估讀待識(shí)別的標(biāo)簽數(shù)目N，閱讀器發(fā)送包含此標(biāo)簽數(shù)目信息的Detect指令。

2）如果 N>256的話，這里幀長(zhǎng)取最大幀長(zhǎng)度256，轉(zhuǎn)到步驟3；否則依據(jù)表1確定幀長(zhǎng)度，直接響應(yīng)，然后轉(zhuǎn)到步驟4。

3）每個(gè)標(biāo)簽從1-N中隨機(jī)的選擇一個(gè)數(shù)字載入時(shí)隙計(jì)數(shù)器，然后數(shù)字小于等于256的數(shù)字去響應(yīng)相應(yīng)的閱讀器時(shí)隙，大于256的暫時(shí)不響應(yīng)（可以看成是分成兩組，小于等于256的一組，大于256是一組）。

4）統(tǒng)計(jì)該識(shí)別周期中一共正確識(shí)別的標(biāo)簽數(shù)Nr，用N減去Nr得出未識(shí)別的標(biāo)簽數(shù)目（N=N-Nr），如果未識(shí)別的標(biāo)簽數(shù)為零，說明全部識(shí)別，否則跳到步驟2。

算法流程圖如圖3所示。

圖3 算法流程

2.3 仿真結(jié)果

利用Matlab仿真平臺(tái)，最大幀長(zhǎng)度取得是256，仿真結(jié)果如圖4、圖5 所示。圖4記錄標(biāo)簽在0～1000變化時(shí)，改進(jìn)后的動(dòng)態(tài)幀時(shí)隙ALOHA算法所消耗的時(shí)隙數(shù)，并和動(dòng)態(tài)幀時(shí)隙ALOHA算法，分組的動(dòng)態(tài)幀時(shí)隙ALOHA算法作了對(duì)比?？梢钥闯霎?dāng)標(biāo)簽數(shù)量大時(shí)改進(jìn)后的算法有明顯優(yōu)勢(shì)。圖5仿真了改進(jìn)后分組動(dòng)態(tài)幀時(shí)隙ALOHA算法系統(tǒng)吞吐率，可見在此算法中，系統(tǒng)吞吐率隨標(biāo)簽數(shù)量的增多幾乎不變，一直穩(wěn)定在36%附近。

圖4 三種算法的性能比較

圖5 改進(jìn)算法的系統(tǒng)吞吐率

3 結(jié)語

傳統(tǒng)的RFID防碰撞算法識(shí)讀標(biāo)簽時(shí)需要的時(shí)隙數(shù)隨標(biāo)簽數(shù)目的增加急速增加，系統(tǒng)吞吐率變低。本文提出的算法通過一種有效的分組方法限制響應(yīng)標(biāo)簽數(shù)量解決了該問題,當(dāng)標(biāo)簽數(shù)很大時(shí)消耗時(shí)隙數(shù)相對(duì)較少，系統(tǒng)吞吐率也保持在相對(duì)穩(wěn)定的較高值。

[1]王睿,趙龑.RFID技術(shù)及應(yīng)用系統(tǒng)構(gòu)架的研究[J].通信技術(shù),2009,42(209):116-118.

[2]單承贛,單玉峰,姚磊.射頻識(shí)別（RFID）原理與應(yīng)用[M].北京:電子工業(yè)出版社,2008.

[3]李學(xué)嬌,賈小愛,趙磊,等.基于后退式索引的動(dòng)態(tài)樹型防碰撞算法[J].通信技術(shù),2009,42(06):118-120.

[4]魏東梅,黃景武,鄒傳云.調(diào)頻CMDA的RFID防碰撞算法研究[J].信息安全與通信保密,2011(08):41-43.

[5]張頗,崔喆.RFID系統(tǒng)中一種改進(jìn)防碰撞算法[J].計(jì)算機(jī)應(yīng)用,2008,28(08):2141-2143.

[6]程文青,趙夢(mèng)欣,徐晶.改進(jìn)的RFID動(dòng)態(tài)幀時(shí)隙ALOHA算法[J].華中科技大學(xué)學(xué)報(bào),2007,35(06):14-16.

[7]尹君,何恰剛,李兵,等.基于分組動(dòng)態(tài)幀時(shí)隙的RFID防碰撞算法[J].計(jì)算機(jī)工程,2009,35(20):267-269.

[8]單劍鋒,謝建兵,莊琴清.基于分組的動(dòng)態(tài)幀時(shí)隙 ALOHA防碰撞算法研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2011,21(11):40-41.