《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 微波|射頻 > 設(shè)計(jì)應(yīng)用 > 基于EPC Gen2防碰撞算法的研究與優(yōu)化
基于EPC Gen2防碰撞算法的研究與優(yōu)化
2018年電子技術(shù)應(yīng)用第4期
孫 磊1,2,莊健敏1,張釗鋒1
1.中國科學(xué)院上海高等研究院,上海201210;2.中國科學(xué)院大學(xué),北京100190
摘要: 防碰撞算法是射頻識(shí)別(RFID)關(guān)鍵技術(shù)之一。基于EPC Gen2標(biāo)準(zhǔn)的Q值防碰撞算法,提出了InnerQ算法,利用對(duì)碰撞時(shí)隙再次處理的方法,解決原有算法Q值反復(fù)跳變的問題,并提高了系統(tǒng)吞吐率,突破了ALOHA類算法吞吐率最高為36.8%的瓶頸,提高了RFID系統(tǒng)性能。
中圖分類號(hào): TP301
文獻(xiàn)標(biāo)識(shí)碼: A
DOI:10.16157/j.issn.0258-7998.173485
中文引用格式: 孫磊,莊健敏,張釗鋒. 基于EPC Gen2防碰撞算法的研究與優(yōu)化[J].電子技術(shù)應(yīng)用,2018,44(4):138-141,145.
英文引用格式: Sun Lei,Zhuang Jianmin,Zhang Zhaofeng. Study and optimization of the anti-collision algorithm based on EPC Gen2 standard[J]. Application of Electronic Technique,2018,44(4):138-141,145.
Study and optimization of the anti-collision algorithm based on EPC Gen2 standard
Sun Lei1,2,Zhuang Jianmin1,Zhang Zhaofeng1
1.Shanghai Advanced Research Institute,Chinese Academy of Science,Shanghai 201210,China; 2.University of the Chinese Academy of Science(UCAS),Beijing 100190,China
Abstract: Anti-collision algorithm is one of key technologies of RFID. This paper proposes a new anti-collision algorithm called InnerQ, based on the Q-algorithm in the EPC Gen2 standard. The proposed algorithm solves the problem of Q value changed frequently and improves the throughput of the system breaking the bottleneck of the ALOHA-based algorithm whose throughput is limited to 36.8%, using the method of reprocessing the collision slots, thus improves the system performance.
Key words : RFID;anti-collision algorithm;throughput

0 引言

    射頻識(shí)別(Radio Frequency Identification,RFID)是一種可以通過無線電信號(hào)識(shí)別特定目標(biāo)并讀寫相關(guān)數(shù)據(jù)的無線通信技術(shù)[1]。RFID系統(tǒng)的射頻通信部分包括閱讀器和標(biāo)簽,當(dāng)閱讀器的電磁能量覆蓋范圍內(nèi)同時(shí)有多個(gè)標(biāo)簽向該閱讀器返回信息時(shí),閱讀器便無法正確識(shí)別任何一個(gè)標(biāo)簽的信息,這種現(xiàn)象稱之為標(biāo)簽碰撞。

    目前,國際通用標(biāo)準(zhǔn)EPC Gen2中采用的防碰撞算法可用于解決標(biāo)簽碰撞問題。EPC Gen2算法基于ALOHA類算法,有很好的自適應(yīng)性,實(shí)現(xiàn)簡(jiǎn)單,有較低的識(shí)別時(shí)延,但是缺點(diǎn)是吞吐率較低。前人的一些文章中對(duì)EPC Gen2防碰撞算法進(jìn)行了優(yōu)化,吞吐率有所提高,但都難于實(shí)現(xiàn),并且很多文章也沒能突破在標(biāo)簽數(shù)比較多的情況下,吞吐率僅為36.8%的瓶頸[2-4]

    本文提出的優(yōu)化方案在分析了EPC Gen2算法和動(dòng)態(tài)幀時(shí)隙ALOHA算法(Dynamic Frame Slotted ALOHA,DFSA)[5]的特點(diǎn)和性能的基礎(chǔ)上,提出了InnerQ算法,仍然保持了ALOHA類算法的易于實(shí)現(xiàn)的優(yōu)點(diǎn),減少了標(biāo)簽碰撞時(shí)隙數(shù),同時(shí)提高了系統(tǒng)吞吐率,突破了36.8%的瓶頸。

1 研究現(xiàn)狀

1.1 DFSA算法介紹

    DFSA算法是一種可以動(dòng)態(tài)調(diào)整幀長(zhǎng),使幀長(zhǎng)接近待識(shí)別標(biāo)簽數(shù)目,讓系統(tǒng)吞吐率盡可能保持在最大值的一種算法。當(dāng)幀長(zhǎng)等于待識(shí)別標(biāo)簽數(shù)目時(shí),系統(tǒng)吞吐率達(dá)到最大值,并且當(dāng)標(biāo)簽數(shù)遠(yuǎn)大于1時(shí),吞吐率的峰值保持在36.8%。證明過程參見文獻(xiàn)[6]。

1.2 EPC Gen2算法介紹

    EPC Gen2標(biāo)準(zhǔn)中的防碰撞算法也是一種特殊的DFSA算法。該算法由讀寫器定義一段時(shí)間長(zhǎng)度(包含若干個(gè)時(shí)隙),當(dāng)標(biāo)簽接收到對(duì)應(yīng)命令后,隨機(jī)選擇一個(gè)時(shí)隙進(jìn)行接入。讀寫器通過Query、QueryRep、QueryAdjust等指令的組合對(duì)標(biāo)簽中時(shí)隙計(jì)數(shù)器數(shù)值進(jìn)行調(diào)整,當(dāng)標(biāo)簽的計(jì)數(shù)器值為0時(shí)進(jìn)行響應(yīng)。在一個(gè)盤存(Inventory)周期中包含多個(gè)幀。EPC Gen2防碰撞算法可以在盤存過程中的任意時(shí)刻動(dòng)態(tài)調(diào)整幀長(zhǎng),使未識(shí)別標(biāo)簽進(jìn)入下一幀的響應(yīng)周期中[7]

1.2.1 EPC Gen2防碰撞算法的實(shí)現(xiàn)步驟

    該算法流程如圖1所示,具體實(shí)現(xiàn)步驟如下:

jsj5-t1.gif

    (1)Q初始值設(shè)為4。讀寫器發(fā)出Query(Q)指令,開始一個(gè)盤存周期。

    (2)標(biāo)簽會(huì)在[0,2Q-1]范圍內(nèi)生成一個(gè)隨機(jī)數(shù)載入到標(biāo)簽時(shí)隙計(jì)數(shù)器。同時(shí)在閱讀器端將2Q載入到閱讀器時(shí)隙計(jì)數(shù)器,以此記錄當(dāng)前幀長(zhǎng)剩余時(shí)隙數(shù)。

    (3)標(biāo)簽時(shí)隙計(jì)數(shù)器的值為0時(shí)進(jìn)行響應(yīng),若當(dāng)前時(shí)隙只有一個(gè)標(biāo)簽進(jìn)行響應(yīng),則為成功時(shí)隙。若有兩個(gè)或兩個(gè)以上標(biāo)簽進(jìn)行響應(yīng),則為碰撞時(shí)隙,Qfp的值加上C值;若沒有標(biāo)簽響應(yīng),則為空閑時(shí)隙,Qfp的值減去C值。

    (4)當(dāng)前時(shí)隙處理完成,閱讀器的時(shí)隙計(jì)數(shù)器減去1。若閱讀器的時(shí)隙計(jì)數(shù)器減為0,則再次發(fā)送Querry命令,開啟新的一幀,回到步驟(2);若閱讀器的時(shí)隙計(jì)數(shù)不為零,并且Q值發(fā)生了變化,則發(fā)送QueryAdjust命令,調(diào)整Q值,開啟新的一幀,回到步驟(2);若閱讀器的時(shí)隙計(jì)數(shù)器不為零,并且Q值未發(fā)生改變,則發(fā)送QuerryRep命令,標(biāo)簽時(shí)隙計(jì)數(shù)器的值減1,回到步驟(3)。如此循環(huán)往復(fù)。

1.2.2 EPC Gen2防碰撞算法的性能分析

    在識(shí)別過程中,參數(shù)Q決定了標(biāo)簽產(chǎn)生的隨機(jī)數(shù)的范圍,參數(shù)C決定了是否改變幀長(zhǎng)以適應(yīng)標(biāo)簽數(shù)目的變化,從而直接影響系統(tǒng)的性能。該算法并不消耗大量的運(yùn)算去估算待識(shí)別標(biāo)簽的數(shù)量,只是去統(tǒng)計(jì)碰撞時(shí)隙、空閑時(shí)隙的次數(shù)。當(dāng)接入信道連續(xù)的發(fā)生1/C次碰撞或空閑時(shí),Q值進(jìn)行加1或減1操作。該算法實(shí)現(xiàn)簡(jiǎn)單,但也有如下兩個(gè)缺點(diǎn):

    (1)Q值反復(fù)跳變。

    標(biāo)準(zhǔn)規(guī)定Q的初始值等于4,當(dāng)標(biāo)簽數(shù)量比較多時(shí),Q值會(huì)依次增加到某一個(gè)值,并在該值左右反復(fù)跳變。Q值每改變一次,標(biāo)簽就得重新生成一次隨機(jī)數(shù),即使當(dāng)Q值改變到合理范圍(2Q接近標(biāo)簽個(gè)數(shù)),仍會(huì)反復(fù)跳變,導(dǎo)致標(biāo)簽做大量的無用動(dòng)作,增加識(shí)別時(shí)延。舉例說明:在標(biāo)簽數(shù)量為200、600和1 000的情況下,待識(shí)別標(biāo)簽數(shù)目的變化和Q值的關(guān)系如圖2所示。

jsj5-t2.gif

    (2)幀長(zhǎng)并不能做到和標(biāo)簽數(shù)相等,導(dǎo)致吞吐率較低。

    由于Q值控制的幀長(zhǎng)始終是2的冪,而標(biāo)簽數(shù)量不可能總是2的冪,因此該算法的吞吐率一定無法達(dá)到36.8%的理論值。由于C值對(duì)吞吐率有直接的影響,而標(biāo)準(zhǔn)中又沒有給出具體的取值,因此不同的文章選取不同的C值,分析得到的吞吐率也不同。為了便于研究,本文借鑒文獻(xiàn)[8],采用基于經(jīng)驗(yàn)值的C=0.8/Q調(diào)整Qfp的值,使得系統(tǒng)吞吐率能夠保持在32%左右。

2 優(yōu)化算法的提出

    本文提出的優(yōu)化算法InnerQ,針對(duì)上文提到的兩個(gè)問題進(jìn)行優(yōu)化。InnerQ算法由兩部分組成,一是穩(wěn)定Q值算法,二是碰撞時(shí)隙再處理算法。

2.1 穩(wěn)定Q值算法

    由上文分析可知,當(dāng)標(biāo)簽數(shù)量比較多時(shí),Q值會(huì)從初始值增加到某一個(gè)值,然后在這一個(gè)值左右反復(fù)跳變。可以設(shè)計(jì)穩(wěn)定Q值算法,記錄Q值的變化過程,一旦檢測(cè)到Q值不是依次遞增或遞減,而是反復(fù)跳變,則固定下Q值,讓讀寫器不再反復(fù)發(fā)送QuerryAdjust,導(dǎo)致所有待識(shí)別標(biāo)簽都反復(fù)生成隨機(jī)數(shù)。將Q值固定后的狀態(tài)定義為Q值穩(wěn)定狀態(tài)。具體算法流程如圖3所示。

jsj5-t3.gif

    達(dá)到Q值穩(wěn)定狀態(tài)后,標(biāo)簽時(shí)隙的分布相對(duì)比較分散,不會(huì)出現(xiàn)大量標(biāo)簽都選擇同一個(gè)時(shí)隙,也不會(huì)出現(xiàn)大量的空閑時(shí)隙,造成時(shí)隙浪費(fèi)的情況。在某一個(gè)時(shí)隙內(nèi)標(biāo)簽接入成功、發(fā)生碰撞及空閑的概率[9]如式(1)所示:

jsj5-gs1-2.gif

    由式(2)可以仿真得到總的標(biāo)簽數(shù)量n與達(dá)到穩(wěn)定狀態(tài)后的Q值,以及達(dá)到穩(wěn)定狀態(tài)后,碰撞時(shí)隙中平均包含的標(biāo)簽數(shù)量Nc的對(duì)應(yīng)關(guān)系,結(jié)果如表1所示。

jsj5-b1.gif

    由表1可以得出結(jié)論,當(dāng)Q值穩(wěn)定后,標(biāo)簽的分布比較分散,每一個(gè)碰撞時(shí)隙的標(biāo)簽數(shù)量是少量的,在2~6的范圍內(nèi)。

2.2 碰撞時(shí)隙再處理算法

    達(dá)到Q值穩(wěn)定狀態(tài)后,只是標(biāo)簽選擇接入的時(shí)隙比較分散,但是仍有碰撞標(biāo)簽的存在。這些標(biāo)簽需要再次處理,才能全部識(shí)別。本文提出的方案出于兼容性的考慮,借鑒了原先的EPC Gen2防碰撞算法的處理邏輯,并且它是一種特殊的DFSA算法,而DFSA算法在標(biāo)簽個(gè)數(shù)比較少時(shí),吞吐率是比較高的。

    證明過程如下:

    設(shè)幀長(zhǎng)為L(zhǎng),標(biāo)簽數(shù)為n。某個(gè)時(shí)隙僅被一個(gè)標(biāo)簽選擇的概率為Ps,則:

jsj5-gs3-5.gif

    該函數(shù)圖像如圖4所示。可以觀察到,當(dāng)標(biāo)簽數(shù)量小于40時(shí),吞吐率明顯高于36.8%,并且隨著標(biāo)簽的減少,吞吐率有大幅度的提高。而這個(gè)特點(diǎn)被很多研究EPC Gen2防碰撞算法優(yōu)化的學(xué)者忽視,并沒有充分利用,導(dǎo)致提出的優(yōu)化方案總是想辦法讓吞吐率接近36.8%,而始終無法超過這個(gè)理論瓶頸。

jsj5-t4.gif

    本文首先利用上文提到的Q值穩(wěn)定算法,使得每一碰撞時(shí)隙標(biāo)簽的個(gè)數(shù)平均在2~6之間,對(duì)這些碰撞標(biāo)簽再處理并不影響到其他時(shí)隙的標(biāo)簽,同時(shí)又利用了DFSA算法在標(biāo)簽個(gè)數(shù)少時(shí)吞吐率高的特性,大幅度提高了系統(tǒng)的吞吐率。算法流程圖如圖5所示。

jsj5-t5.gif

    需要注意的是,本文在碰撞時(shí)隙再處理時(shí)借鑒了原有標(biāo)準(zhǔn)中Q值的處理流程,但是也有一些變動(dòng),其中有個(gè)明顯的變動(dòng)是Q值的初始值要從4改成2。因?yàn)橛杀?的數(shù)據(jù)可知:碰撞時(shí)隙內(nèi)的標(biāo)簽數(shù)量在2~6個(gè)之間。Q值等于2時(shí)是更接近實(shí)際標(biāo)簽的數(shù)量,雖然做不到理論上的嚴(yán)格相等,但是在數(shù)學(xué)規(guī)律上符合DFSA算法在標(biāo)簽數(shù)量比較少時(shí)吞吐率較高的規(guī)律。圖6展示了不同的Q的初始值對(duì)應(yīng)吞吐率的變化情況。

jsj5-t6.gif

3 仿真結(jié)果與分析

    為了從實(shí)驗(yàn)角度證實(shí)InnerQ算法的有效性,利用仿真軟件MATLAB分別對(duì)EPC Gen2算法、DFSA算法、InnerQ算法進(jìn)行仿真。標(biāo)簽數(shù)量1 000個(gè)。由于這3種算法都是基于ALOHA算法改進(jìn)的隨機(jī)性算法,仿真的結(jié)果是取500次實(shí)驗(yàn)的平均值。以系統(tǒng)吞吐率、碰撞時(shí)隙個(gè)數(shù)、總時(shí)隙個(gè)數(shù)這3個(gè)指標(biāo)作為評(píng)價(jià)標(biāo)準(zhǔn),仿真得到的結(jié)果如圖7~圖9所示。

jsj5-t7.gif

jsj5-t8.gif

jsj5-t9.gif

    圖7截取了標(biāo)簽數(shù)量從100~1 000個(gè)的數(shù)據(jù)來展示,結(jié)果表明DFSA算法的吞吐率始終保持在36.8%,與本文的的理論分析和前人的研究結(jié)果相吻合。本文提出的InnerQ算法結(jié)合了DFSA算法在少量標(biāo)簽的情況下吞吐率比較高的特點(diǎn),利用碰撞時(shí)隙再處理的思想,使系統(tǒng)吞吐率穩(wěn)定在42%左右。

    圖8的結(jié)果表明,InnerQ算法的碰撞時(shí)隙個(gè)數(shù)明顯小于優(yōu)化之前的算法。因?yàn)閮?yōu)化算法使得碰撞時(shí)隙內(nèi)的標(biāo)簽數(shù)目比較少,這樣再次處理時(shí),發(fā)生碰撞的機(jī)率就比較小,碰撞時(shí)隙數(shù)自然就會(huì)減少。

    圖9的結(jié)果顯示,DFSA算法、EPC Gen2算法和InnerQ算法在識(shí)別標(biāo)簽總時(shí)隙的差別上不算太大,雖然利用碰撞時(shí)隙再處理的方法其實(shí)是相當(dāng)于引進(jìn)了更多的時(shí)隙,但是碰撞時(shí)隙內(nèi)的標(biāo)簽較少,并且穩(wěn)定Q值算法,使得Q值不再反復(fù)跳變,相當(dāng)于減少了不必要的時(shí)隙浪費(fèi)。所以優(yōu)化算法在整體上并沒有增加過多額外的時(shí)隙。

4 結(jié)論

    本文研究了DFSA算法和EPC Gen2算法的特性,指出了其中被很多人忽略的地方,從理論和仿真數(shù)據(jù)上證明,本文提出的優(yōu)化算法可以突破原來的ALOHA類算法在多標(biāo)簽識(shí)別的情況下,吞吐率最高只能達(dá)到36.8%的瓶頸。優(yōu)化算法的吞吐率提高到了42%左右,碰撞時(shí)隙數(shù)也有了大幅減少,同時(shí)確保了與當(dāng)前標(biāo)準(zhǔn)的兼容性,可以快速投入到實(shí)際的生產(chǎn)中,具有很好的應(yīng)用前景。

參考文獻(xiàn)

[1] 杜云明,周楊.無線射頻識(shí)別技術(shù)與應(yīng)用研究[J].自動(dòng)化技術(shù)與應(yīng)用,2010,29(5):52-55.

[2] 任守綱,楊帆,王浩云,等.基于判決門限的RFID防碰撞Q值算法[J].計(jì)算機(jī)科學(xué),2014,41(8):154-157.

[3] 吳淼,劉德盟,張釗鋒.基于EPC Gen2防碰撞機(jī)制的研究與優(yōu)化[J].微電子學(xué)與計(jì)算機(jī),2013,30(5):100-103.

[4] LEE D,BANG O,IM S,et al.Efficient dual bias Q-Algo-rithm and optimum weights for EPC Class 1 Generation 2 protocol[C].Wireless Conference,2008. Ew 2008. European.IEEE,2008:1-5.

[5] CHA J R,KIM J H.Dynamic frame slotted ALOHA algo-rithms using fast tag estimation method for RFID system[C].Proceeding of the IEEE International Conference on Consumer Communications,2006:768-772.

[6] LEE S R,JOO S D,LEE C W.An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification[C].IEEE Computer Society,2005:166-174.

[7] EPC Global.Radio-frequency identity protocols Class-1 Generation-2 UHF RFID protocol for communications at 860 MHz-960 MHz version 1.2.0[S/OL].(2008-05-11)[2017-08-08].URL:http://www.gs1.org/sites/default/files/docs/epc/uhfc1g2_1_2_0-standard-20080511.pdf.

[8] FLOERKEMEIER C,WILLE M.Comparison of transmission schemes for framed ALOHA based RFID protocols[C].International Symposium Applications and the Internet Workshops.Phoenix,2006:94-97.

[9] CHA J R,KIM J H.Novel anti-collision algorithms for fastobject identification in RFID system[C].International Conference on Parallel and Distributed Systems. Fukuoka,2005:63-67.



作者信息:

孫  磊1,2,莊健敏1,張釗鋒1

(1.中國科學(xué)院上海高等研究院,上海201210;2.中國科學(xué)院大學(xué),北京100190)

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。
主站蜘蛛池模板: 国产欧美日本亚洲精品一4区 | 亚洲精品在线播放视频 | 日韩男女做性高清在线观看 | 天天综合色网 | 国产成人精品三级91在线影院 | 一个人看的免费高清视频www | a级免费看| 97国产伦子在线观看 | 天天射日日干 | 日本中文字幕视频 | 亚洲精品天堂在线观看 | 久久国产精品佐山爱 | 欧美在线综合 | 日本一区二区三区不卡在线看 | 一区在线观看 | 日韩激情小视频 | 在线视频三区 | 91黄色软件 | 天堂网国产 | 日韩美女免费线视频网址 | 一级女人18片毛片免费视频 | 国产伦精品一区二区三区无广告 | 日韩伦理网站 | 色版视频 | 午夜dj免费高清在线观看影院 | 国产91在线看 | 久久久精品2018免费观看 | 国产免费看网站v片不遮挡 国产免费黄视频 | 波多野结衣一区二区三区高清在线 | 精品国产乱码一区二区三区 | 98精品国产高清在线看入口 | 妞干网免费在线 | 美国成人免费视频 | 福利片在线观看免费高清 | 夜色爽爽 | 香蕉视频污污 | 亚洲图片欧美文学小说激情 | 国产大片黄 | 老司机成人免费精品视频 | 欧美人与禽杂交大片 | 成人夜夜|