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

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

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

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

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

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

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

射頻識別;防碰撞;動態幀時隙ALOHA;部分時隙;隨機數

1 概述

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

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

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

2.1 分組

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

圖1 DFSA算法效率

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

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

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

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

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

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

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

2.2 部分時隙幀預測

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

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

2.3 算法分析

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

2.4 GPSPA算法流程

GPSPA算法流程如圖2所示。

圖2 GPSPA算法流程

3 仿真實驗與分析

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

3.1 仿真實驗

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

表1 GPSPA仿真參數

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

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

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

3.2 采樣率對系統識別效率的影響

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

表2 采樣率仿真參數

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

3.3 判決門限對系統識別效率的影響

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

表3 判決門限仿真參數

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

3.4 初始幀長度對系統識別效率的影響

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

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

4 結束語

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

[1] 趙瑞思,李 濤,張 帥,等.RFID動態標簽估計防碰撞算法[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版.吳曉峰,陳大才,譯.北京:電子工業出版社,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] 郭來功,黃友銳,蔡 俊.優化的動態幀時隙ALOHA防碰撞算法[J].計算機應用研究,2012,29(11): 4141-4143.

[12] 程文青,趙夢欣,徐 晶.改進的 RFID動態幀時隙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);北京工商大學研究生科研學術創新基金資助項目。

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

2013-06-14

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