呂聰穎

LV Cong-ying

（南陽理工學(xué)院 計(jì)算機(jī)與信息工程學(xué)院，南陽 473000）

0 引言

RFID[1]技術(shù)被廣泛用于運(yùn)輸系統(tǒng)、電子客票、訪問控制、動(dòng)物識(shí)別、物流及供應(yīng)鏈管理等領(lǐng)域。在RFID系統(tǒng)中，當(dāng)兩個(gè)以上的標(biāo)簽在同一時(shí)刻向閱讀器發(fā)送標(biāo)識(shí)信號(hào)時(shí)，信號(hào)將產(chǎn)生疊加而導(dǎo)致閱讀器不能正常解析標(biāo)簽發(fā)送的信號(hào)，即標(biāo)簽信號(hào)沖突問題。

基于ISO和EPC機(jī)構(gòu)，有三類著名的解決標(biāo)簽信號(hào)沖突問題的算法：二叉樹算法(Binary Tree,簡(jiǎn)寫B(tài)T)、基于幀的時(shí)隙ALOHA算法(Framed Slotted ALOHA,簡(jiǎn)寫FSA)及動(dòng)態(tài)幀時(shí)隙ALOHA算法(Dynamic Framed Slotted ALOHA,簡(jiǎn)寫DSFA)。然而，種種研究表明這些算法需要大量的時(shí)間去識(shí)別標(biāo)簽。

許多改進(jìn)的防沖突算法已提出來了：Cho[2]等人提出在RFID系統(tǒng)中采用校驗(yàn)位的思想，不必檢查標(biāo)簽中的所有位，該方法大大減少了閱讀器發(fā)送請(qǐng)求的數(shù)量，從而可縮短在閱讀器范圍內(nèi)識(shí)別所有標(biāo)簽的時(shí)間；滕培俊[3]等人通過對(duì)查詢樹算法及其性能的研究，提出了一種沖突跟蹤樹型算法，結(jié)果表明該算法在時(shí)間復(fù)雜度和通信復(fù)雜度兩方面都有良好改善；王玉青[4]等人對(duì)幀長(zhǎng)進(jìn)行了研究，提出了一種動(dòng)態(tài)改變幀長(zhǎng)的方法。仿真結(jié)果表明，標(biāo)簽數(shù)量較大時(shí)，該方法可使系統(tǒng)效率達(dá)到最佳，時(shí)延最少；孫文勝[5]等人提出了根據(jù)幀時(shí)隙信息結(jié)合貝葉斯準(zhǔn)則對(duì)標(biāo)簽數(shù)目進(jìn)行估計(jì)，從提高估算準(zhǔn)確性的角度對(duì)動(dòng)態(tài)幀時(shí)隙ALOHA算法進(jìn)行了改進(jìn)。

文獻(xiàn)[6]指出，當(dāng)系統(tǒng)中的標(biāo)簽數(shù)量較少時(shí)，BT算法比FSA和DFSA更有效。而當(dāng)標(biāo)簽數(shù)量較多時(shí)，BT算法比DFSA表現(xiàn)得糟糕?；谠摻Y(jié)論及以往研究成果，本文提出了一種新穎的RFID防沖突算法，仿真結(jié)果表明該算法在所用時(shí)隙數(shù)量及獲得吞吐量方面明顯優(yōu)于BT和DFSA算法。

1 新穎的防沖突算法

欲對(duì)標(biāo)簽進(jìn)行分組，首先必須估計(jì)閱讀器范圍內(nèi)的標(biāo)簽數(shù)目，從而才可以確定所用的組數(shù)。假定N表示時(shí)隙數(shù)，即幀長(zhǎng)，規(guī)定N的最大值為Nmax=256；n表示待識(shí)別的標(biāo)簽數(shù)；c1表示只有一個(gè)標(biāo)簽發(fā)送數(shù)據(jù)的時(shí)隙數(shù)，即正確發(fā)送數(shù)據(jù)的時(shí)隙數(shù)；c0表示沒有標(biāo)簽發(fā)送數(shù)據(jù)的時(shí)隙數(shù)，即空時(shí)隙數(shù)；ck≥2表示多于一個(gè)標(biāo)簽發(fā)送數(shù)據(jù)的時(shí)隙數(shù)，即碰撞時(shí)隙數(shù)。

1.1 標(biāo)簽數(shù)目的確定

文獻(xiàn)[7]指出，vogt法需要在標(biāo)簽數(shù)取值范圍內(nèi)進(jìn)行多次計(jì)算來確定極值，因此估算標(biāo)簽數(shù)較為準(zhǔn)確。為此，本文借鑒vogt法來進(jìn)行標(biāo)簽數(shù)目的確定。

由于每一次碰撞至少涉及兩個(gè)標(biāo)簽，而每個(gè)標(biāo)簽只能選擇一個(gè)時(shí)隙發(fā)送數(shù)據(jù)，因此，標(biāo)簽數(shù)目c的下限估算可采用下式：

該方法所引起的誤差估計(jì)ε可通過將一個(gè)閱讀周期內(nèi)的各個(gè)加權(quán)誤差相加獲得：

使該誤差值最小的n即為所估計(jì)的標(biāo)簽數(shù)目。

式(2)中，P(μ=mc)表示具有c(c=0,1,2,…,n)個(gè)標(biāo)簽的時(shí)隙數(shù)mc的分布概率，定義如下：

1.2 標(biāo)簽分組算法

為使算法更有效，分組數(shù)必須與標(biāo)簽數(shù)相一致。也即，標(biāo)簽數(shù)越少，組數(shù)越少。

根據(jù)統(tǒng)計(jì)學(xué)原理，每個(gè)標(biāo)簽以相同的概率1/N選擇同一幀中的同一時(shí)隙做出響應(yīng)，則l個(gè)標(biāo)簽選擇同一幀中的同一時(shí)隙做出響應(yīng)的概率B服從二項(xiàng)分布，即為：

由此可知，n與N大致相等時(shí)，系統(tǒng)吞吐量最大(約為36.8%)。當(dāng)n遠(yuǎn)大于N時(shí)，可對(duì)標(biāo)簽進(jìn)行分組，即限定每次識(shí)別標(biāo)簽的數(shù)目，且規(guī)定在同一時(shí)間只能有一組標(biāo)簽做出響應(yīng)。定義標(biāo)簽分組數(shù)M為：

文獻(xiàn)[8]提供了待識(shí)別標(biāo)簽數(shù)與最佳幀長(zhǎng)下所對(duì)應(yīng)的分組數(shù)，如表1所示。

表1 待識(shí)別標(biāo)簽數(shù)與最佳幀長(zhǎng)和分組數(shù)的關(guān)系

1.3 具體算法流程

參數(shù)設(shè)置：Group：當(dāng)前組數(shù)；Total_Tag：總的標(biāo)簽集合；Slot：識(shí)別某標(biāo)簽所用的時(shí)隙；Total_Slot：總時(shí)隙數(shù)。

步驟1：Total_Slot=0，Total_Tag={}；

步驟2：估算標(biāo)簽總數(shù)n；

步驟3：根據(jù)n計(jì)算分組數(shù)M；

步驟4：設(shè)定Group=1；

步驟5：如果Group＞M，則算法結(jié)束；

步驟6：采用QBT算法識(shí)別Group組中的標(biāo)簽，將識(shí)別的標(biāo)簽加入集合Total_Tag，并將所用時(shí)隙Slot加入Total_Slot；

步驟7：Group加1；轉(zhuǎn)步驟5。

2 仿真測(cè)試

目的：通過統(tǒng)計(jì)標(biāo)簽數(shù)取值不同時(shí)所需的時(shí)隙數(shù)及系統(tǒng)的吞吐量來評(píng)估算法的性能?；贛atlab平臺(tái)進(jìn)行測(cè)試，n取值0～1000。

圖1 標(biāo)簽數(shù)不同時(shí)各算法所需的時(shí)隙數(shù)

圖2 標(biāo)簽數(shù)不同時(shí)各算法 獲得的吞吐量

由圖1可知，當(dāng)標(biāo)簽數(shù)較少時(shí)，BT算法所需的時(shí)隙數(shù)與本算法相差不大，但當(dāng)標(biāo)簽數(shù)＞500，本算法要大大優(yōu)于其他兩種算法。由圖2可知，當(dāng)標(biāo)簽數(shù)小于Nmax=256(最大幀長(zhǎng))，本算法所獲得的系統(tǒng)吞吐量與DFSA相差不大，但當(dāng)標(biāo)簽數(shù)遠(yuǎn)大于Nmax=256時(shí)，本算法所獲得的系統(tǒng)吞吐量仍然保持35%，而DFSA卻不容樂觀。

3 結(jié)論

借鑒以往研究成果，提出了一種新穎的求解RFID標(biāo)簽沖突問題的算法：提出采用vogt來估計(jì)待識(shí)別標(biāo)簽數(shù)，并推導(dǎo)出相應(yīng)的分組策略，接下來采用BT法對(duì)每組中的標(biāo)簽進(jìn)行識(shí)別，發(fā)揮出BT法善于識(shí)別少量標(biāo)簽的特性。仿真結(jié)果表明，該算法在所需時(shí)隙數(shù)和獲得系統(tǒng)吞吐量方面明顯優(yōu)于BT法和DFSA法。

[1] 陸冰清,牛國(guó)柱,趙英臣.一種新型RFID動(dòng)態(tài)多叉樹查詢防碰撞算法[J].制造業(yè)自動(dòng)化,2012,34(8):12-15.

[2] J.S.Cho,J.D.Shin,S.K.Kim. RFID Tag Anti-Collision Protocol: Query Tree with Reversed IDs[C].ICACT,2008:225-230.

[3] 滕培俊,熊偉,梁青,等.一種基于二進(jìn)制樹的RFID防沖突算法研究[J].通信技術(shù),2009,42(7):94-96.

[4] 王玉青,李開宇,孫純鵬. 改進(jìn)動(dòng)態(tài)幀時(shí)隙ALOHA算法[J].電子科技,2012,25(7):76-79.

[5] 孫文勝,金陳敏. 新型的RFID動(dòng)態(tài)幀時(shí)隙ALOHA防碰撞算法[J].信息與控制,2012,41(2):233-237.

[6] S.Makwimanloy,P.Kovintavewat,U.Ketprom. A New Anti-Collision Based on A-Priori Information[C]. Proc.of ECTICON,2008: 733-736.

[7] Vogt H. Multiple object identification with passive RFID tags[C].Proceedings of IEEE International Conference on Systems,Man,and Cybernetics.Hammamet,Tunisia:IEEE,2002,1-6.

[8] Cha Jaeryong,Kim Jaehyun.Novel anti-collision algorithms for fast object identification in RFID system[C].IEEE Proceedings of the 11th International Conference on Parallel and Distributed Systems (ICPADS05),Fukuoka:IEEE CS Press,2005.

[9] 王雪,錢志鴻,胡正超,等.基于二叉樹的RFID防碰撞算法的研究[J].通信學(xué)報(bào),2010,31(6):49-57.