分組部分時(shí)隙幀預(yù)測的RFID防碰撞算法

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

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

分組部分時(shí)隙幀預(yù)測的RFID防碰撞算法

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

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

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

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

1 概述

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

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

2 分組部分時(shí)隙幀預(yù)測算法

2.1 分組

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

圖1 DFSA算法效率

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

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

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

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

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

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

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

2.2 部分時(shí)隙幀預(yù)測

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

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

2.3 算法分析

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

2.4 GPSPA算法流程

GPSPA算法流程如圖2所示。

圖2 GPSPA算法流程

3 仿真實(shí)驗(yàn)與分析

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

3.1 仿真實(shí)驗(yàn)

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

表1 GPSPA仿真參數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

[1] 趙瑞思,李 濤,張 帥,等.RFID動態(tài)標(biāo)簽估計(jì)防碰撞算法[J].計(jì)算機(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.射頻識別技術(shù)[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標(biāo)簽反碰撞識別算法[J].計(jì)算機(jī)工程,2010,36(20):241-243.

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

[12] 程文青,趙夢欣,徐 晶.改進(jìn)的 RFID動態(tài)幀時(shí)隙ALOHA算法[J].華中科技大學(xué)學(xué)報(bào):自然科學(xué)版, 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

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

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

2013-06-14

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