吳 垚,霍亮生,劉玉德,顧祖寶

(北京工商大學材料與機械工程學院,北京100048)

分組部分時隙幀預測的RFID防碰撞算法

吳 垚,霍亮生,劉玉德,顧祖寶

(北京工商大學材料與機械工程學院,北京100048)

針對最大幀長度受限情況下射頻識別中的標簽碰撞問題,提出分組部分時隙幀預測ALOHA算法。通過分組操作,限定每次待識別標簽數(shù)在最大幀長的有效識別范圍內。采用部分時隙幀預測,若部分時隙的碰撞或空閑比例超過門限值,則立即調整幀長,從而減少使用的時隙數(shù)。實驗結果表明,該算法能有效降低使用的時隙數(shù),提高系統(tǒng)識別效率,在標簽大量動態(tài)變化的情況下,平均識別率可達35.58%,具有良好的適用性。

射頻識別;防碰撞;動態(tài)幀時隙ALOHA;部分時隙;隨機數(shù)

1 概述

近幾年來,隨著物聯(lián)網(Internet of Things,IOT)的興起,作為其重要支撐的射頻識別(Radio Frequency Identification,RFID)技術得到了重視,在物流、零售、工業(yè)自動化等領域發(fā)展迅速。RFID系統(tǒng)實際工作時大量標簽可能處于一個讀寫器的作用范圍內,這將導致多個標簽同時響應讀寫器而造成標簽識別失敗,稱為標簽碰撞(Collision),因此需采用防碰撞算法最大限度地正確識別盡可能多的標簽。

標簽防碰撞算法可分為ALOHA算法和基于樹的防碰撞算法[1]。ALOHA算法實現(xiàn)結構簡單、成本較低,目前被廣泛使用,如全球超高頻RFID主流標準之一的ISO/IEC18000-6的TypeA和TypeC均基于ALOHA算法[2]。實際使用的幀時隙ALOHA算法將若干離散時隙組合成一幀,標簽在每一幀中隨機選擇一個時隙發(fā)送數(shù)據(jù)以減少標簽沖突的概率[3]。當幀長L和標簽數(shù)量n近似相等時,系統(tǒng)識別效率可達到最大值36.79%[4];當L和n相差很大時,系統(tǒng)識別效率較低。動態(tài)幀時隙 ALOHA(Dynamic Framed Slotted ALOHA,DFSA)算法使幀長動態(tài)近似等于待識別標簽數(shù),常見算法有Q算法(n=2Q)、Lower Bound[5](n=2C)、Schoute[6](n=2.39C)、Vogt[5]、Bayesian[7]等,其中,C為碰撞時隙數(shù)。DFSA算法在標簽相對較少的情況下識別效率較高[8],但在標簽數(shù)量很多、發(fā)送時隙受限時,DFSA算法幾乎顯示不出優(yōu)越性[9],且上述算法都是對實際情況的統(tǒng)計近似,具有一定的預測誤差。為解決最大幀長度受限情況下射頻識別中的標簽碰撞問題,本文提出一種分組部分時隙幀預測ALOHA算法。

2 分組部分時隙幀預測算法

2.1 分組

在實際RFID系統(tǒng)中受到體積等限制,標簽內的隨機數(shù)發(fā)生器一般為8位[10],這使得最大幀長為28=256。若限制最大幀長,DFSA算法整體性能較差,并最終退化為固定幀長ALOHA算法,如圖1所示。

圖1 DFSA算法效率

通過分組操作,將每組待識別標簽數(shù)量限定在最大幀長度能較好識別的有效范圍內。分組部分時隙幀預測(Grouping Part Slots Prediction ALOHA, GPSPA)算法將標簽分成3類:(1)待識別標簽組,馬上進行識別;(2)休眠標簽組,進入休眠狀態(tài),等待下一周期進行識別;(3)成功標簽組,已經成功進行數(shù)據(jù)交換的標簽為成功標簽,不再響應讀寫器命令。

以ISO/IEC 18000-6C中推薦的Q算法為基礎設計GPSPA算法。Q算法的基本思想為:Q為一非負整數(shù),幀長度L=2Q。若碰撞時隙數(shù)C＞空閑時隙數(shù)E,則Q值加1;若碰撞時隙數(shù)C＜空閑時隙數(shù)E,則Q值減1。其實質是幀長度按照2倍長度變化。

假定有n個待識別的電子標簽,幀長度為L個時隙,忽略環(huán)境噪聲對信號傳輸及接收的影響。由于電子標簽隨機選擇時隙,r個電子標簽的響應服從二項分布[11],當且僅當一個時隙中有一個電子標簽響應(即r=1)時,電子標簽才能被讀寫器成功識別,因此一幀中成功識別的標簽數(shù)目為:

定義系統(tǒng)識別效率=成功識別標簽數(shù)量/使用的時隙數(shù)量[12],由式(1)可得系統(tǒng)識別效率為:

在L和2L長度下,系統(tǒng)效率應該相同[7]。令ρL=ρ2L,可解得臨界標簽數(shù)為:

將幀長L=256帶入式(3),可得臨界標簽數(shù)為354。這說明考慮到統(tǒng)計效應,幀長為256時隙的一幀最多可識別354個標簽,故可將354作為分組數(shù)目。

分組操作的具體實現(xiàn)為:首先將估計標簽數(shù)除以354,向無窮方向取整后得到組數(shù),然后讀寫器廣播分組命令,每個待識別標簽產生從1～組數(shù)的隨機數(shù),以此作為組號。從1號組開始,各組依次作為待識別組進行識別,成功識別的標簽記組號為0,不再響應讀寫器分組指令。

2.2 部分時隙幀預測

在傳統(tǒng)的DFSA算法中,不管采用何種標簽估計算法,都必須完全遍歷一幀中所有時隙。不妨考慮2種極端情況:時隙數(shù)遠小于標簽數(shù)量時會出現(xiàn)大量時隙碰撞;若時隙數(shù)遠大于標簽數(shù),則有眾多時隙空閑。由數(shù)理統(tǒng)計學的知識可知,部分時隙的統(tǒng)計特性完全可以代表整體幀的統(tǒng)計特性。設采樣率為SA,則通過檢驗前SA×L部分時隙的碰撞和空閑狀態(tài),可以推斷整幀的碰撞與空閑情況。若在前SA×L個時隙內,碰撞時隙所占百分比大于判斷門限,則可推知幀長過小,應將幀長度立即擴大;若空閑時隙百分比大于判斷門限,則可認為幀長過大,應將幀長立即縮小。GPSPA算法采用部分時隙幀預測,若調整幀長能節(jié)省(1-SA)×L個時隙。

算法具體實現(xiàn)為:每次識別時,先檢驗前SA×L個時隙情況,若碰撞、空閑時隙比例超過門限值,則按照2倍或1/2的關系立即調整幀長;若未達到判決門限,可認為幀長無需立即調整,繼續(xù)檢測剩余時隙;如此循環(huán)往復對所有組進行識別,直到所有標簽均被成功識別。

2.3 算法分析

GPSPA根據(jù)標簽沖突情況高效地調節(jié)數(shù)據(jù)幀長度,試圖使幀長動態(tài)接近未識別標簽數(shù)。將數(shù)據(jù)幀根據(jù)沖突情況進行變長,會給物理層和網絡層帶來一定的處理開銷。具體表現(xiàn)在:RFID物理層頻繁發(fā)收無線電波,會增加讀寫器和電子標簽的處理功耗;網絡層對數(shù)據(jù)幀進行封裝時,由于幀長不定長,會增加網絡層設備復雜性。但是綜合分析后可認為,GPSPA算法非常適用于實際工業(yè)情況下,即標簽數(shù)量在大范圍內動態(tài)變化時[13]。GPSAP算法以犧牲一定功耗和處理算法復雜性的代價下,大大提高了系統(tǒng)效率,極大地節(jié)省了使用的時隙數(shù)目,并使系統(tǒng)識別效率較為穩(wěn)定地工作在接近極限效率36.79%,具有良好的應用前景。

2.4 GPSPA算法流程

GPSPA算法流程如圖2所示。

圖2 GPSPA算法流程

3 仿真實驗與分析

為了驗證GPSPA算法的優(yōu)勢,利用Matlab進行4組仿真,每組實驗均進行100次取均值。

3.1 仿真實驗

將GPSPA與DFSA中性能較好的Schoute算法進行比較,其中GPSPA算法參數(shù)如表1所示。

表1 GPSPA仿真參數(shù)

仿真結果如圖 3、圖 4所示。由圖 3可見, GPSPA較Schoute算法具有更高更穩(wěn)定的系統(tǒng)識別效率。在標簽數(shù)大量動態(tài)變化的情況下,系統(tǒng)識別效率的平均值可達35.58%。當標簽數(shù)量為1 000時,GPSPA算法效率是Schoute的1.75倍;標簽數(shù)量為 1 200時,GPSPA算法效率是 Schoute的2.5倍。圖4說明GPSPA使用時隙明顯少于Schoute算法,尤其是當標簽數(shù)較大時,GPSPA節(jié)省的時隙數(shù)更為可觀。

圖3 GPSPA(SA=0.5)和Schoute的系統(tǒng)識別率比較

圖4 GPSPA(SA=0.5)和Schoute使用時隙數(shù)比較

3.2 采樣率對系統(tǒng)識別效率的影響

下面分析采樣率對系統(tǒng)識別效率的影響。GPSPA參數(shù)分別如表2所示變化,得到仿真結果如圖5所示。由圖5可知當采樣率SA較小時,算法效果更好。因為可根據(jù)小部分時隙的統(tǒng)計情況及時調整幀長度,若采樣率為100%,GPSPA算法系統(tǒng)識別效率最低。

表2 采樣率仿真參數(shù)

圖5 采樣率對GPSPA算法的影響

3.3 判決門限對系統(tǒng)識別效率的影響

令GPSPA參數(shù)變化如表3所示,得到仿真結果如圖6所示。由圖6可見判決條件越寬松,系統(tǒng)效率振動程度越大,但總的說來,不同判決門限下系統(tǒng)效率接近,可以不將判決門限作為重點考慮因素。

表3 判決門限仿真參數(shù)

圖6 不同判決門限系統(tǒng)下識別率對GPSPA算法的影響

3.4 初始幀長度對系統(tǒng)識別效率的影響

令參數(shù)變化如表4所示,對系統(tǒng)仿真后得系統(tǒng)識別效率如圖7所示。由圖7可見,當標簽數(shù)較小時,較小的初始幀長度具有較高的識別效率,但當標簽數(shù)目遠大于256時,初始幀長度為256具有更高的效率。對于標簽數(shù)量較大的情形,可將初始幀長度定義為256。

圖7 初始幀長度對GPSPA算法的影響

4 結束語

本文在研究ISO/IEC18000-6C標準中ALOHA防碰撞算法的基礎上,提出一種基于分組部分時隙幀預測ALOHA算法。該算法能適應電子標簽大量動態(tài)變化的環(huán)境。通過分組,將遠超過最大幀長256時隙的標簽分成待識別組、休眠組、成功組3類,通過分別對各組進行識別,可在最大幀長度限制下有效地進行系統(tǒng)識別。根據(jù)部分時隙的統(tǒng)計性質能代表整幀的情況,對部分時隙的碰撞、空閑情況進行統(tǒng)計,若發(fā)現(xiàn)部分時隙的碰撞或空閑百分比超過門限值,則立即調整幀長,能節(jié)省較多時隙。仿真結果表明,本文提出的算法能有效降低使用時隙數(shù),提高系統(tǒng)識別效率,表現(xiàn)出較優(yōu)越的性能,尤其對標簽數(shù)量劇烈變化、實時性要求較高的物聯(lián)網終端RFID系統(tǒng)具有良好的適用性。

[1] 趙瑞思,李 濤,張 帥,等.RFID動態(tài)標簽估計防碰撞算法[J].計算機工程,2012,38(8):249-251.

[2] International Organization for Standardization.ISO/IEC 18000-6-2003 Information Technology Automatic Identification and Data Capture Techniques-Radio Frequency Identification forItem ManagementAir Interface[S].2003.

[3] Wong C P,Feng Quanyuan.Grouping Based Bit-slot ALOHA ProtocolforTag Anti-collision in RFID Systems[J].IEEE Communications Letters,2007,11 (12):946-948.

[4] Klaus Finkenzeller.射頻識別技術[M].3版.吳曉峰,陳大才,譯.北京:電子工業(yè)出版社,2006.

[5] Vogt H.EfficientObjectIdentification with Passive RFID Tags[C]//Proc.of International Conference on Pervasive Computing.[S.1.]:IEEE Press,2002: 98-113.

[6] Schoute F.Dynamic Frame Length ALOHA[J].IEEE Transactions on Communications,1983,31(4):565-568.

[7] Floerkemeier C.Transmission Control Scheme for fast RFID Object Identification[C]//Proc.of the 4th Annual IEEE International Conference on Pervasive Computing and Communications Workshops.[S.1.]:IEEE Press, 2006:222-229.

[8] Cui Yinghua,Wang Huiyang.A New Anti-collision Method for RFID Systems[C]//Proc.of the 12th IEEE International Symposium on Computational Intelligence and Informatics.Budapest,Hungary:[s.n.],2011:549-556.

[9] Hwang T W,Lee B G,Kim Y S,et al.Improved Anticollision Scheme for High Speed Identification in RFID System[C]//Proc.ofInternationalConferenceon Innovative Computing,Information and Control.Beijing, China:[s.n.],2006:123-129.

[10] 李 慧,張治國.不定長RFID標簽反碰撞識別算法[J].計算機工程,2010,36(20):241-243.

[11] 郭來功,黃友銳,蔡 俊.優(yōu)化的動態(tài)幀時隙ALOHA防碰撞算法[J].計算機應用研究,2012,29(11): 4141-4143.

[12] 程文青,趙夢欣,徐 晶.改進的 RFID動態(tài)幀時隙ALOHA算法[J].華中科技大學學報:自然科學版, 2007,35(6):14-16.

[13] Gao Jianliang,Wang Jianxin,He Jianbiao,et al.Query Splitting-based Anticollision forMobileRFID-based Internet-of-things [J]. International Journal of Distributed Sensor Networks,2013,(2013):674-698.

編輯 索書志

RFID Anti-collision Algorithm of Grouping Part Time Slot Frame Prediction

WU Yao,HUO Liang-sheng,LIU Yu-de,GU Zu-bao
(School of Material and Mechanical Engineering,Beijing Technology and Business University,Beijing 100048,China)

To solve the tags collision problem in Radio Frequency Identification(RFID)system where the maximum size of frame is limited,this paper proposes a new Grouping Part time Slot frame Prediction ALOHA(GPSPA) algorithm.Tags are divided into smaller groups considering the limited frame size's capability.Part slots prediction scheme is used in identification to decide whether to change the frame size immediately.If the empty or collision slots percentage exceeds the threshold value,the frame size is changed promptly.Simulation results show that the proposed algorithm can increase the system efficiency and consume fewer slots than previous work.Besides,the influence of the parameters of the algorithm is discussed by simulation tests.The system identification efficiency can maintain 35.58%, approximating to the limit value,where dynamic tags are changing greatly.The proposed algorithm provides a good solution for RFID systems where the tags are changing within a wide range and the frame size is limited.

Radio Frequency Identification(RFID);anti-collision;Dynamic Framed Slotted ALOHA(DFSA);part time slot;random number

1000-3428(2014)09-0280-04

A

TP391

10.3969/j.issn.1000-3428.2014.09.056

北京市教委重大基金資助重點項目(PXM2013_014213_000037);北京工商大學研究生科研學術創(chuàng)新基金資助項目。

吳 垚(1990-),男,碩士研究生,主研方向:無線射頻識別,嵌入式系統(tǒng);霍亮生、劉玉德,教授;顧祖寶,碩士研究生。

2013-06-14

2013-09-28E-mail:wuyao391@163.com