一種新穎的RFID標簽防沖突算法

呂聰穎

LV Cong-ying

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

0 引言

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

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

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

文獻[6]指出，當系統中的標簽數量較少時，BT算法比FSA和DFSA更有效。而當標簽數量較多時，BT算法比DFSA表現得糟糕。基于該結論及以往研究成果，本文提出了一種新穎的RFID防沖突算法，仿真結果表明該算法在所用時隙數量及獲得吞吐量方面明顯優于BT和DFSA算法。

1 新穎的防沖突算法

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

1.1 標簽數目的確定

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

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

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

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

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

1.2 標簽分組算法

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

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

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

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

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

1.3 具體算法流程

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

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

步驟2：估算標簽總數n；

步驟3：根據n計算分組數M；

步驟4：設定Group=1；

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

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

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

2 仿真測試

目的：通過統計標簽數取值不同時所需的時隙數及系統的吞吐量來評估算法的性能。基于Matlab平臺進行測試，n取值0～1000。

圖1 標簽數不同時各算法所需的時隙數

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

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

3 結論

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

[1] 陸冰清,牛國柱,趙英臣.一種新型RFID動態多叉樹查詢防碰撞算法[J].制造業自動化,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] 王玉青,李開宇,孫純鵬. 改進動態幀時隙ALOHA算法[J].電子科技,2012,25(7):76-79.

[5] 孫文勝,金陳敏. 新型的RFID動態幀時隙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.