UHF 頻段RFID 系統(tǒng)防碰撞算法研究

1、UHF頻段RFID系統(tǒng)防碰撞算法研究張玉平1,趙東東,洪輝(上海大學通信學院通信與信息系統(tǒng)摘要:防碰撞技術(shù)是決定RFID系統(tǒng)性能的關(guān)鍵因素之一,特別是UHF頻段,防碰撞性能決定著多目標的識別率、識別速度。本文著重研究UHF頻段RFID系統(tǒng)防碰撞解決方案和算法改進問題,探討盤存周期內(nèi)總時隙數(shù)的選取,并對系統(tǒng)效率進行仿真,提出簡單易行的提高系統(tǒng)效率的方法。關(guān)鍵詞:RFID 防碰撞系統(tǒng)效率中圖分類號:TN99 文獻標示碼:AStudies on Anti-collision Algorithms Used in UHF RFID SystemZHANGYu-ping,ZHAO Dong-dong(D

2、epartment of Communication and Information Engineering,Shanghai University, 200072Abstract: Anti-collision technology is one of the key factors that determine RFID system performance, especially for UHF RFID, multiple object identification depends onAnti-collision performance. This paper emphaticall

3、y studies the solution andimprovement of anti-collision algorithm, and the selected number of invention cycleslots, updating of Q will be discussed. We propose a method to achieve higher systemefficiency based on the simulation.Key words:RFID anti-collision system efficiency1 引言射頻識別技術(shù)(RFID,Radio Fre

4、quency Identification是一種非接觸的自動識別技術(shù),與條形碼識別相比,具有識別距離長、無需人工干預、存儲容量大等特點。根據(jù)RFID系統(tǒng)調(diào)制載波頻率不同,RFID系統(tǒng)可以分為低頻(30300kHz、高頻(330MHz、超高頻UHF (300-960MHz以及微波頻段(2.45.8GHz。完整的RFID系統(tǒng)包括四部分:射頻卡/標簽(Tag、讀寫器(Reader和天線(Antenna、主機管理系統(tǒng)和網(wǎng)絡(luò)。很多應(yīng)用場合,在讀寫器信號作用范圍內(nèi)需要對多個物體進行識別,此時多個標簽與讀寫器之間的通信,存在信道爭用問題。傳統(tǒng)的信道爭用,其解決的方法大致可以分為如下4種:空分多址(SDMA、

5、頻分多址(FDMA、碼分多址(CDMA和時分多址(TDMA。但在RFID系統(tǒng)中,除了受復雜性和成本的制約,還要解決本身通信的因素,如無源標簽需其提供能量、標簽總數(shù)未知、碰撞判決需讀寫器控制、防碰撞協(xié)議要簡單易實現(xiàn)等。在RFID無源標簽系統(tǒng)中,目前廣泛使用的防碰撞算法大都是基于TDMA,比較經(jīng)典的兩類基本方法是:基于Aloha算法和基于二進制樹搜索算法。對于UHF頻段的RFID系統(tǒng),信號識別的距離遠,覆蓋的范圍廣,因而需識別的標簽數(shù)量大,若識別的物體有一定的速度,更需要良好的防碰撞算法以減少沖突達到快速、準確識別多個目標的目的。2 UHF頻段RFID系統(tǒng)防碰撞方案在UHF工作頻段,主要是ISO/

6、IEC 18000-6(針對頻率為860960MHz用于物品管理的無接觸通信空中接口參數(shù)標準,包括A、B、C(EPC Class1 Gen2標準納入18000-6C三種類型。如表1所示它們采用的防碰撞算法也都不同,均是基本算法的改進應(yīng)用。表1 ISO/IEC 18000-6標準三種類型比較1類型技術(shù)特征TYPE A(CDTYPE B(CD TYPEC 工作頻段 860960MHz 速率 33kb/s 10kb/s或40kb/s 26.7128kb/s讀寫器到標簽編碼方式 PIE 曼徹斯特 PIE(脈沖寬度編碼速率 40kb/s 40kb/s FM0:40640kb/s子載頻調(diào)制:5320 kb

7、/s編碼方式 FM0 FM0 FM0或Miller調(diào)制子載頻標簽到讀寫器唯一識別符長度64bit 64bit可變,最小16bit,最大496bit算法 ALOHA 二進制樹時隙隨機防碰撞類型概率概率概率線形250個標簽/256個時隙,自適應(yīng)分配,基本呈線形多達2256個標簽呈線形進入多達215個標簽呈線形,大于此數(shù)的具有唯一電子產(chǎn)品編碼(EPC的標簽呈N*logN防碰撞算法標簽查詢能力不少于250個不少于250個具有唯一標識的標簽數(shù)量不受限制TYPE A采用的是一種動態(tài)時隙ALOHA算法防碰撞協(xié)議。標簽內(nèi)硬件需有隨機數(shù)發(fā)生器和比較器,設(shè)計相對簡單。TYPE A防碰撞機制的不足之處是:若標簽數(shù)目

8、與初始時隙數(shù)相差較大時,防碰撞的過程會比較長。TYPE B應(yīng)用的防碰撞機制要較TYPE A的更有效一些,它利用隨機產(chǎn)生的0、1信號達到了二進制樹形搜索的效果,但防碰撞的效率會隨標簽數(shù)量增多而下降。TYPE C應(yīng)用的防碰撞算法是時隙隨機防碰撞仲裁機制,是動態(tài)時隙ALOHA算法的改進,在幀大小調(diào)整方面與以往動態(tài)幀時隙ALOHA算法有很大改進,目前沒有找到這樣調(diào)整的理論依據(jù)。但它具有較高的閱讀速率,在美國已達到1500標簽/秒,歐洲可達到600 標簽/秒1;同時也適合在高密度多個讀寫器環(huán)境下工作。3 算法改進探討與分析為了縮短二進制樹搜索算法的查詢時間和返回信息比特數(shù),有人提出了動態(tài)二進制搜索算法,

9、還有很多研究者提出其他新穎的改進的方法。如文獻2提出修剪枝的二進制樹形搜索,文獻3提出基于返回式二進制樹形搜索。也有將二進制樹搜索算法和ALOHA算法結(jié)合起來4,共同實現(xiàn)系統(tǒng)的高效率。由于ALOHA算法簡單,易實現(xiàn),且對標簽數(shù)目變化有較好的適應(yīng),因而得到廣泛應(yīng)用,同時不斷被優(yōu)化和改進,因此本文重點分析ALOHA算法的改進和仿真。最基本的ALOHA 算法存在部分碰撞和完全碰撞,導致碰撞發(fā)生的概率很大,其碰撞期為數(shù)據(jù)幀的兩倍。并且最大系統(tǒng)吞吐率僅為18.4%。為了提高系統(tǒng)吞吐率和改善它的可行性和有效性,文獻5提出時隙 ALOHA 和幀時隙ALOHA 算法,并且很多研究者試圖找出幀大小的選取、估測未

10、讀標簽的數(shù)量6。上節(jié)中提到的TYPE C 采用的正是幀時隙ALOHA 算法的應(yīng)用改進,可以實現(xiàn)對大量標簽的識別,但是在實際應(yīng)用中,總是希望系統(tǒng)的識別效率盡可能高,系統(tǒng)的開銷盡可能小,因此,占用的時隙數(shù)也會相應(yīng)減少,實際工作的效率也會提高。4仿真結(jié)果仿真實驗采用Matlab 7平臺,研究標簽盤存動態(tài)時隙大小對系統(tǒng)效率的影響。記錄標簽數(shù)從0到600變化時(以2Q 遞增變化系統(tǒng)效率變化曲線,為算法的改進提供理論的基礎(chǔ)。為了使系統(tǒng)保持較高的效率,必須動態(tài)改變幀時隙大小,并且通過反饋估算標簽數(shù)量,當幀時隙大小與待讀標簽數(shù)量相當時,此時系統(tǒng)的效率最大。假設(shè)不考慮捕獲效應(yīng)(指若干標簽的應(yīng)答碰撞時,離RFID

11、 讀寫器較近的標簽可能因其信號較強而覆蓋其他標簽的信號N 為輪詢的時隙長度,n 為某時刻讀寫器信號范圍內(nèi)未讀標簽數(shù),r 個標簽出現(xiàn)在某個給定時隙概率服從二項分布為6:1,11(1r n r n N n B r r N N = (1那么相應(yīng)的只分配一個標簽在某時隙中的概率為:11,11(11n n NB n N N =總時隙中成功讀取的標簽數(shù)為: 1,11,11(11n N nn N a N B N n N N = (2 系統(tǒng)的效率定義為時隙中只分配一個標簽數(shù)和當前時隙總數(shù)比值,即,1N n S a N =。由圖1所示,采用總固定時隙數(shù)時,當標簽數(shù)越大時,采用的時隙數(shù)相對增大,系統(tǒng)的效率才會保持

12、較高水平,當達到一定數(shù)量時,系統(tǒng)效率又會下降,需要再次調(diào)整總時隙數(shù)。 對(2式求導可知,1ln(11n N =(3 n 為(3時,S 最大。將(3變換,可得:1111111111111n n n n e n N n e e n >>+020040060000.10.20.30.4S Number of Unread Tags圖1 系統(tǒng)效率與標簽數(shù)量關(guān)系曲線 圖2 理想的系統(tǒng)效率曲線若采取合適的反饋,合理的估算方法,使Q 動態(tài)變化,可以使系統(tǒng)效率明顯增大,理想情況可達到如圖2所示。若估算的標簽數(shù)n 小于當前時隙數(shù)N ,減小幀中時隙數(shù),若n 大于當前時隙數(shù),需增加時隙數(shù)N ,而反饋量采

13、用何種參數(shù),如何實際取值,可以根據(jù)實驗和環(huán)境來調(diào)整、測試、驗證。由于估測標簽的數(shù)量取決于采取的估測方法,且系統(tǒng)實現(xiàn)較為復雜,本文提出采用時隙聯(lián)合空閑率門限和碰撞率門限調(diào)整當前采用的時隙幀數(shù),具體可行結(jié)合實驗進一步驗證可行性。5 總結(jié)本文分析了UHF 頻段RFID 的防碰撞方案,并具體仿真了算法的改進途徑和更新時隙的方法,提出聯(lián)合考慮空閑率和碰撞率的方法,調(diào)整總時隙數(shù),能夠讓系統(tǒng)的效率大大提高,需要進一步結(jié)合實驗驗證。但從RFID 系統(tǒng)應(yīng)用的角度來看,目前的防碰撞算法的識別率、識別速度、信道利用率(突破36.8%的系統(tǒng)效率限制有待進一步提高,也需加強對安全和個人隱私等方面的考慮。在算法優(yōu)化改進時

14、,進一步考慮功率消耗和模擬實際信道建模等。為配合多個目標、高速運動物體的識別等復雜系統(tǒng)的應(yīng)用,這些方面需作更深入的研究。 6 參考文獻2 余松森.基于修剪枝的二進制樹形搜索反碰撞算法與實現(xiàn)J.計算機工程,2005(8:217-218.University ,2006,28(SI :133-136.4 Binetti, G ., Boggia, G ., Camarda, P. ,Grieco, L. A .A Hashing-based Anti-Collision Algorithmfor RFID Tag Identification.Wireless Communication Syst

15、ems, 2007.ISWCS 2007.4th International Symposium on 17-19 Oct.2007 Page(s:524-528./ 06_rfid-mac_report.pdf.6 Lee Suryun,Joo Sungdon,Lee Chaewoo.An enhanced dynamic framed slotted ALOHAalgorithm for RFID tagC.IEEE Proceedings of the Second Annual International Conference on Mobile and Ubiquitous Syst

16、ems:Networking and Services (MobiQuitous05.San Diego: IEEE CS Press,2005:166-172.7 高樂,吳援明,王曉磊.一種用于RFID系統(tǒng)中的幀長度調(diào)整方法J.微計算機信息,2007,2-2:213-215。作者簡介:張玉平(1982,女(漢,上海大學通信與信息系,碩士研究生,主要研究方向為移動通信系統(tǒng)、射頻識別技術(shù)。趙東東(1954,男(漢,上海大學通信與信息系副教授,現(xiàn)任上海大學通信工程系副主任?，F(xiàn)研究方向:移動通信,數(shù)字通信。洪輝(1982,男(漢,上海大學通信與信息系,碩士研究生,主要研究方向為計算機通信網(wǎng)絡(luò)及其服務(wù)

17、質(zhì)量(QoS。Biography: Zhang Yu-ping (1982-, Female (Han, graduate student in Dept. of Communication and Information, Shanghai University, focus on mobile communication and RFID technology. Associate professor Zhao Dong-dong (1954-, male(Han, assistant dean of Communication Engineering, Shanghai University, focus on mobile and digital communication. HongHui (1982-, male (Han, gradua