呂聰穎

LV Cong-ying

（南陽理工學院 計算機與信息工程學院，南陽 473000）

0 引言

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

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

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

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

1 新穎的防沖突算法

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

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

文獻[7]指出，vogt法需要在標簽數(shù)取值范圍內進行多次計算來確定極值，因此估算標簽數(shù)較為準確。為此，本文借鑒vogt法來進行標簽數(shù)目的確定。

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

該方法所引起的誤差估計ε可通過將一個閱讀周期內的各個加權誤差相加獲得：

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

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

1.2 標簽分組算法

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

根據(jù)統(tǒng)計學原理，每個標簽以相同的概率1/N選擇同一幀中的同一時隙做出響應，則l個標簽選擇同一幀中的同一時隙做出響應的概率B服從二項分布，即為：

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

文獻[8]提供了待識別標簽數(shù)與最佳幀長下所對應的分組數(shù)，如表1所示。

表1 待識別標簽數(shù)與最佳幀長和分組數(shù)的關系

1.3 具體算法流程

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

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

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

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

步驟4：設定Group=1；

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

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

步驟7：Group加1；轉步驟5。

2 仿真測試

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

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

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

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

3 結論

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

[1] 陸冰清,牛國柱,趙英臣.一種新型RFID動態(tài)多叉樹查詢防碰撞算法[J].制造業(yè)自動化,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] 滕培俊,熊偉,梁青,等.一種基于二進制樹的RFID防沖突算法研究[J].通信技術,2009,42(7):94-96.

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

[5] 孫文勝,金陳敏. 新型的RFID動態(tài)幀時隙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].通信學報,2010,31(6):49-57.