RFID中基于EPC G1G2的DTJ-ALOHA防碰撞算法仿真

楊曉嬌 葉 潤 吳必造

1(重慶交通大學(xué)信息技術(shù)中心 重慶 400074)2(電子科技大學(xué) 四川 成都 611731)3(中移物聯(lián)網(wǎng)有限公司 重慶 401336)

RFID中基于EPC G1G2的DTJ-ALOHA防碰撞算法仿真

楊曉嬌1葉 潤2吳必造3

1(重慶交通大學(xué)信息技術(shù)中心 重慶 400074)2(電子科技大學(xué) 四川 成都 611731)3(中移物聯(lián)網(wǎng)有限公司 重慶 401336)

針對EPC G1G2標(biāo)準(zhǔn)中的動態(tài)幀時隙防碰撞算法，在標(biāo)簽數(shù)量較多時，會導(dǎo)致Q值頻繁的更改，從而增加了閱讀器的負(fù)擔(dān)等問題，提出一種以碰撞、空閑和成功時隙的差值，作為判斷Q值改變門限的DTJ(Devalue Threshold Judgment)-ALOHA算法。通過Matlab仿真與EPC中算法做對比，驗(yàn)證了DTJ-ALOHA算法無論在Q值改變次數(shù)、平均吞吐率，還是閱讀器的開銷上都優(yōu)于常見改進(jìn)算法。

動態(tài)幀時隙 ALOHA算法 吞吐率 防碰撞 射頻識別RFID

0 引 言

目前，國內(nèi)外現(xiàn)有的針對RFID系統(tǒng)的大多數(shù)論文所研究以及改進(jìn)的防碰撞算法，大都是基于TDMA的時分多路算法的基礎(chǔ)上提出的[1-3]。根據(jù)算法思想的不同可分為下面幾類：1) 基于分時隙思想的，識別結(jié)果不確定的ALOHA及其衍生算法；2) 基于二分查找思想的，識別結(jié)果確定的二進(jìn)制及其衍生算法。ALOHA雖然屬于不確定性算法，但是由于其對硬件的要求沒有二進(jìn)制算法高而且其實(shí)現(xiàn)過程也相對簡單且易于實(shí)現(xiàn)，因此RFID系統(tǒng)在閱讀器作用域內(nèi)存在大量標(biāo)簽待識別時(此時防碰撞算法需要滿足：快速準(zhǔn)確地識別閱讀器作用域內(nèi)的所有標(biāo)簽)，由于系統(tǒng)實(shí)現(xiàn)簡單，自效率高等優(yōu)勢首選就是ALOHA及其衍生算法[4]。因此，本文提出的DTJ-ALOHA算法也是基于ALOHA的基礎(chǔ)上提出的。

現(xiàn)在國內(nèi)外大多數(shù)針對基于ALOHA的改進(jìn)算法的論文，主要是通過將閱讀器作用域中存在的標(biāo)簽分成幾組來對標(biāo)簽進(jìn)行分流而達(dá)到減少碰撞概率的目的，或者通過某種策略來動態(tài)地改變幀長等方法來提高RFID系統(tǒng)的吞吐率。但這些算法大都停留在理論層面，沒有和實(shí)際的國際標(biāo)準(zhǔn)協(xié)議中的防碰撞算法結(jié)合起來，因此，在工程中應(yīng)用得并不廣泛。本文就是針對EPC G1G2中推薦的DSF(Dynamic Framed Slotted)-ALOHA算法，對EPC G1G2協(xié)議中規(guī)定的DFS-ALOHA防碰撞算法在標(biāo)簽數(shù)量較多時，由于總時隙數(shù)的增加會導(dǎo)致空閑以及碰撞時隙也相應(yīng)的增多，使得Q值發(fā)生頻繁波動，以及頻繁計算Qfp(Q的浮點(diǎn)數(shù)形式)導(dǎo)致閱讀器負(fù)擔(dān)較重等缺陷，提出了一種根據(jù)碰撞、空閑以及成功時隙的差值作為Q值跳變門限的DTJ-ALOHA算法。最后通過在Matlab7.0平臺上Matlab編程模擬算法的執(zhí)行過程，對結(jié)果繪圖對比分析，驗(yàn)證了DTJ-ALOHA算法不論在控制Q值改變次數(shù)、時隙吞吐率以及系統(tǒng)閱讀器開銷等性能上都優(yōu)于推薦的EPCG1G2推薦的算法。

1 EPC中的動態(tài)幀時隙DFS-ALOHA算法

EPCglobal標(biāo)準(zhǔn)委員會的EPCC1G2中推薦的算法也是基于ALOHA的即DFS-ALOHA算法[5]。協(xié)議規(guī)定通過定義一個Q來根據(jù)時隙狀態(tài)靈活改變幀長，閱讀器通過向其作用域內(nèi)廣播發(fā)送Query、QueryAdjust和QueryRep等命令來改變幀長。并且根據(jù)標(biāo)簽的回復(fù)記錄下當(dāng)前時隙的狀態(tài)，然后根據(jù)統(tǒng)計的標(biāo)簽狀態(tài)來動態(tài)調(diào)整幀長，若Q值發(fā)生變化，則標(biāo)簽工作在2Q的動態(tài)幀長下[6]。

1.1EPCG1G2中DFS-ALOHA的涉及到的命令簡介

本節(jié)將對EPCG1G2協(xié)議中用到的命令(在第2節(jié)中DTJ-ALOHA算法中也會用到的命令)簡介[8]。

Query(Q)命令：目的是向標(biāo)簽發(fā)送Q值，標(biāo)簽從Query(Q)中獲取Q值后選擇x屬于[0，2Q-1]放到標(biāo)簽的SC(SlotCount)中，當(dāng)且僅當(dāng)SC中存儲的值通過QueryRep(n)命令自減為0時，標(biāo)簽才請求通信。

QueryAdjust(Q)：協(xié)議中規(guī)定的更新時隙的命令，用于向標(biāo)簽廣播用于計算時隙的參數(shù)Q。標(biāo)簽從QueryAdjust(Q)命令中獲取Q值后，先將其SC中數(shù)值清零，然后選擇x屬于[0，2Q-1]放到標(biāo)簽的SC(SlotCount)中。

QueryRep(n)：減少SC值命令，該命令攜帶一個參數(shù)n，閱讀器作用域范圍內(nèi)標(biāo)簽收到該命令廣播的n值后，根據(jù)SC=SC-n計算SC的值將其重新存儲在SC中(EPCG1G2中n=1)。

1.2EPCG1G2中的防碰撞算法思想

EPCG1G2中采用DSF-ALOHA算法識別標(biāo)簽的過程，如圖1所示，主要是根據(jù)當(dāng)前時隙的狀態(tài)來動態(tài)地調(diào)整Q值從而改變幀長，調(diào)整方法是：1) 若為空閑時隙則Qfp=Qfp-C；2) 若為碰撞時隙則Qfp=Qfp+ C；3) 若為成功時隙則Qfp=Qfp。每個時隙過后就對Qfp進(jìn)行計算Q=round(Qfp)(取整方法為四舍五入)。若本時隙結(jié)束后，經(jīng)過計算發(fā)現(xiàn)Q不等于Qstart，即需要更新Q值，接著發(fā)送QueryAdjust(Q)命令對Q值進(jìn)行更新；反之，則表示不需要更新Q值，只需閱讀器繼續(xù)處理下一個時隙即可，即發(fā)送QueryRep(1)命令繼續(xù)識別[9]。

圖1 EPC G1G2中建議調(diào)整Q值的方法(Qfp為Q的浮點(diǎn)形式)

在EPCG1G2協(xié)議規(guī)定C為浮點(diǎn)數(shù)，其取值范圍為0.1～0.5，且C取值由于Q的增大而減小[8]。這是因?yàn)楫?dāng)閱讀器作用域內(nèi)存在大量標(biāo)簽時，總時隙N也會很大，從而使得碰撞以及空閑時隙數(shù)也相應(yīng)的增加，由于推薦算法在每尋呼一個時隙就要對Q進(jìn)行一次浮點(diǎn)運(yùn)算，當(dāng)總時隙N很大時閱讀器進(jìn)行浮點(diǎn)數(shù)的運(yùn)算量也很大，此時閱讀器的負(fù)擔(dān)就很大，即便取C=0.1也會同樣會導(dǎo)致Q值頻繁的更新。因此，針對上述不足，本文提出了一種改進(jìn)的基于差值門限判決來決定Q值是否改變的DTJ-ALOHA算法。新算法不用進(jìn)行浮點(diǎn)預(yù)算，并且再標(biāo)簽數(shù)增加時不會導(dǎo)致Q值的頻繁更新。

2 DTJ-ALOHA算法

在實(shí)際RFID系統(tǒng)中時隙數(shù)N不能為任意值，N的取值只能是2Q(Q=0,1,2,…)則可以計算得出，標(biāo)簽根據(jù)接收到的Q值生成的時隙數(shù)可為0,2,4,…,128,256,512，且當(dāng)Q值越大對Q值進(jìn)行加或者減1操作后，對N的波動會越大。本文根據(jù)碰撞、空閑、和成功時隙個數(shù)的差值表達(dá)式來作為Q改變的依據(jù)，從而規(guī)避了上述問題，提出了一種新的算法。下面介紹DTJ-ALOHA算法是如何提出的。

在ALOHA算法的基礎(chǔ)上面，可推導(dǎo)得出在FS-ALOHA算法中，某時隙中存在k個標(biāo)簽的概率為：

(1)

同理，由式(1)令X=1即可得出有且僅有一個標(biāo)簽選擇當(dāng)前時隙(表示當(dāng)前時隙為成功時隙)的概率為：

(2)

對式(2)進(jìn)行Matlab仿真分別令N=16,32,64,128,256時可以得出算法的吞吐率隨標(biāo)簽個數(shù)的變化規(guī)律，如圖2所示(從左到右依次為N=16,32,64,128,256的圖像)。

圖2 N=16，32，64，128，256時FS-ALOHA 算法吞吐率與標(biāo)簽個數(shù)的關(guān)系

由圖2可知，要保持吞吐率較高，則取兩條曲線的交點(diǎn)間部分對應(yīng)的時隙數(shù)(如標(biāo)簽個數(shù)在ab段時取時隙數(shù)N=64)，吞吐率較高的兩條直線的交點(diǎn)即為時隙數(shù)為N的曲線與時隙數(shù)為2N和N/2的交點(diǎn)(以N=64這條曲線的吞吐率為例分析，與2N的交點(diǎn)即為b點(diǎn)與2/N的交點(diǎn)即為a點(diǎn))?？梢酝瞥鰰r隙數(shù)分別為N以及2N的兩條吞吐率曲線的交點(diǎn)所對應(yīng)的標(biāo)簽個數(shù)nN=2N為：

(3)

(4)

由式(1)令k=0可以推出，沒有一個標(biāo)簽選擇某時隙的概率(該時隙為空閑時隙)Pnull為：

(5)

同理k>1可推出不止一個標(biāo)簽選擇某時隙的概率(即該時隙為碰撞時隙)Pcoll為：

(6)

以圖2中ab段對應(yīng)的N=64的吞吐率曲線為例，該曲線的頂點(diǎn)(即吞吐率最高)所對應(yīng)的x軸標(biāo)簽個數(shù)也大概為64左右，其余吞吐率曲線也是當(dāng)N約等于n時，吞吐率最高。下面以N=16時碰撞、成功以及空閑時隙占總時隙的概率，隨標(biāo)簽個數(shù)的變化規(guī)律為例進(jìn)行Matlab仿真，結(jié)果如圖3所示。從圖中的概率曲線可以得出當(dāng)算法吞吐率較高時，碰撞概率與成功概率差值以及空閑概率與成功概率的差值較小。

圖3 幀長為N=64時FS-ALOHA算法時碰撞、成功以及空閑時隙概率隨標(biāo)簽個數(shù)n的變化圖

所以，本文提出了一種根據(jù)碰撞與成功以及空閑與成功時隙的差值作為閾值來控制Q值的改變，將Q值由Q變?yōu)镼+1的閾值Th+定義為：Th+=N×(Pcol-Psuc)，將Q值由Q變?yōu)镼-1的閾值Th-定義為：Th-=N×(Pnull-Psuc)將前面定義的式(5)、式(6)代入閾值Th+和Th-表達(dá)式化簡可得出：

Th+= N×(Pcol-Psuc)=

(7)

Th-= N×(Pnull-Psuc)=

(8)

由式(7)和式(8)可以得出Q值及其與Th+和Th-取值為表1所示。

表1 Q值與其對應(yīng)的閾值Th

表1中提前計算好了Q跳變的閾值，閱讀器只需要根據(jù)每個時隙的狀態(tài)做一個簡單的比較以及加減法運(yùn)算，這樣就有效解決了本節(jié)開始提出的由于做浮點(diǎn)運(yùn)算而導(dǎo)致閱讀器負(fù)擔(dān)增加的問題。

因此，下面簡單介紹DTJ-ALOHA算法的程序流程圖。

按照如圖4所示的流程，當(dāng)閱讀器向標(biāo)簽發(fā)出通信請求后，根據(jù)回復(fù)的個數(shù)確定本時隙碰撞、空閑還是成功時隙。接著統(tǒng)計本幀中空閑、碰撞以及成功時隙的個數(shù)。

圖4 DTJ-ALOHA算法的詳細(xì)程序流程圖

如果本時隙為非成功時隙，則比較碰撞時隙與空閑時隙大小，1)若Qcoll>Qsuc將碰撞時隙與成功時隙差值與表1中對應(yīng)Th+的閾值進(jìn)行比較，如果統(tǒng)計的時隙數(shù)差超過閾值，則表示碰撞時隙過多，應(yīng)增加時隙數(shù)，發(fā)送QueryAdjust(Q)命令調(diào)整Q值來更新時隙數(shù)，反之沒有超過閾值表示時隙數(shù)不變發(fā)送QueryRep(1)命令繼續(xù)讀取下一個時隙。2)若Qcoll≤Qsuc將空閑時隙與成功時隙差值與表1中對應(yīng)Th-的閾值進(jìn)行比較，如果統(tǒng)計的時隙數(shù)之差超過閾值，則表示空閑時隙過多，應(yīng)減少總時隙數(shù)，發(fā)送QueryAdjust(Q)命令通過調(diào)整Q值來更新總時隙數(shù)，反之沒有超過閾值表示時隙數(shù)不變發(fā)送QueryRep(1)命令繼續(xù)讀取下一個時隙。

由表1可以看出，DTJ-ALOHA算法的閾值Th+和Th-是根據(jù)Q值動態(tài)變化的，且Q值越大Th+和Th-越大。這樣就避免了在標(biāo)簽數(shù)量較大時，由于Q值的頻繁改變而增加閱讀器負(fù)擔(dān)的問題。因此，DTJ-ALOHA算法在標(biāo)簽數(shù)量不確定時，特別是個數(shù)動態(tài)變化，或者有大規(guī)模標(biāo)簽待識別時，優(yōu)勢明顯。

3 DTJ-ALOHA算法的仿真以及結(jié)果分析

本文的所有仿真實(shí)驗(yàn)都是在Matlab7.0平臺上進(jìn)行的。分別編程實(shí)現(xiàn)不同算法識別標(biāo)簽的過程，再統(tǒng)計運(yùn)行的結(jié)果，為了減小偶然因素對算法評估造成影響，本文中所有圖中的結(jié)果都是識別相同的標(biāo)簽50次后的結(jié)果所取的平均值。

首先分別編程實(shí)現(xiàn)EPCG1G2算法以及DTJ-ALOHA算法的執(zhí)行過程，得出它們發(fā)送QueryAdjust(Q)改變Q值的次數(shù)對比如圖5所示。

圖5 采用閾值跳變來更改Q值與EPC G1G2推薦方法改變Q值需要發(fā)送QueryAdjust()命令次數(shù)的對比圖

由圖5可看出EPCG1G2算法當(dāng)標(biāo)簽個數(shù)增加時不論C取何知，Q值改變次數(shù)都稱線性增加，反之DTJ-ALOHA算法的控制在30以內(nèi)，從而減少了閱讀器的負(fù)擔(dān)。

通過圖5與表2可看出，不論標(biāo)簽多與少，改進(jìn)算法都將Q值改變次數(shù)控制在一定范圍30內(nèi)。即改進(jìn)算法相比于EPCG1G2算法適應(yīng)性較好。

表2 Q值改變次數(shù)對比圖

本文中將RFID系統(tǒng)中ALOHA算法的平均吞吐率定義為：有效時隙數(shù)(成功時隙數(shù))/總時隙(閱讀器識別完其作用域內(nèi)全部標(biāo)簽共需要的時隙數(shù))。

從圖6可以看出，大規(guī)模標(biāo)簽識別過程中，改進(jìn)算法DTJ-ALOHA的吞吐率穩(wěn)定在35.5%左右，EPC G1G2算法吞吐率穩(wěn)定在34.5%(C=0.1)和33%(C=0.5)左右，驗(yàn)證了改進(jìn)算法即DTJ-ALOHA閾值跳變算法比EPCG1G2算法的吞吐率更優(yōu)。

圖6 吞吐率比較圖

當(dāng)前針對動態(tài)幀時隙ALOHA的改進(jìn)算法主要是基于對標(biāo)簽數(shù)估計算法，算法的主要思路是閱讀器先讀取完N個時隙的信息，并統(tǒng)計碰撞率空閑率，并根據(jù)某種算法來估計待識別標(biāo)簽的數(shù)量，然后調(diào)整Q值，這類常見動態(tài)ALOHA改進(jìn)的算法，優(yōu)勢是Q值改變次數(shù)相對較小。但由于這類算法每次對待識別標(biāo)簽數(shù)進(jìn)行估計前，都需要先統(tǒng)計N個時隙的狀態(tài)，并以此為依據(jù)結(jié)合算法來調(diào)整幀長，因此這類改進(jìn)算法適應(yīng)性即吞吐率沒有DTJ-ALOHA算法好。

由于閱讀器開銷大小直接決定了識別其作用范圍內(nèi)所有標(biāo)簽的耗時長短，也就直接影響了識別的準(zhǔn)確率。是衡量算法效率的關(guān)鍵指標(biāo)。為了證明本文提出的DTJ-ALOHA算法的可行性，下面將常見的動態(tài)幀時隙的改進(jìn)算法與本文提出的DTJ-ALOHA算法在閱讀開銷上進(jìn)行仿真對比。

根據(jù)表3中規(guī)定的命令長度，對DTJ-ALOHA算法、基于標(biāo)簽數(shù)估計的動態(tài)幀時隙ALOHA算法以及EPCG1G2算法對閱讀器讀取標(biāo)簽過程中的開銷(發(fā)送數(shù)據(jù)量)做仿真。

表3 EPC C1G2協(xié)議命令/參數(shù)長度

圖6和圖7的結(jié)果已經(jīng)驗(yàn)證了改進(jìn)的DTJ-ALOHA算法在關(guān)鍵性能指標(biāo)上不僅優(yōu)于EPC G1G2推薦的算法也優(yōu)于常見的改進(jìn)(基于標(biāo)簽估計的動態(tài)幀時隙ALOHA)算法。

圖7 三種不同算法對應(yīng)的閱讀器開銷對比圖

4 結(jié) 語

本文在EPC G1G2的DFS-ALOHA算法基礎(chǔ)上提出了一種基于差值門限判決的DTJ-ALOHA算法，改進(jìn)算法采用差值判決替代C值來觸發(fā)Q值的改變，因而不用進(jìn)行浮點(diǎn)運(yùn)算，減輕了閱讀器的計算量。由于閾值的動態(tài)變化也使得算法在標(biāo)簽個數(shù)不確定時始終能保持較優(yōu)的吞吐率。相比于其他改進(jìn)的動態(tài)幀時隙算法(讀完N個時隙再改變Q值)本算法延續(xù)了EPCG1G2 快速動態(tài)調(diào)整Q值的優(yōu)勢。然后通過在Matlab7.0平臺上編程模擬算法的執(zhí)行過程，仿真證明了DTJ-ALOHA算法將Q值改變次數(shù)控制在30以內(nèi)，且算法的平均吞吐率穩(wěn)定在35.5%左右。最后通過仿真證明了本文提出的DTJ-ALOHA算法在閱讀器開銷這一衡量算法的關(guān)鍵指標(biāo)上是優(yōu)于常見的基于標(biāo)簽估計的改進(jìn)的動態(tài)幀時隙ALOHA算法，且DTJ-ALOHA算法并沒有額外的增加尋呼命令，因此可以在EPCG1G2協(xié)議上直接實(shí)現(xiàn)。由于基于EPCG1G2協(xié)議的實(shí)現(xiàn)的RFID系統(tǒng)常用于有大規(guī)模標(biāo)簽待識別的系統(tǒng)比如大型港口、大型商場等實(shí)際應(yīng)用環(huán)境，因此本文提出的DTJ-ALOHA算法有一定的實(shí)用價值，可應(yīng)用在RFID系統(tǒng)大規(guī)模標(biāo)簽待識別環(huán)境中。

[1] 孫其博,劉杰,黎羴,等.物聯(lián)網(wǎng):概念、架構(gòu)與關(guān)鍵技術(shù)研究綜述[J].北京郵電大學(xué)學(xué)報,2010,33(3):2-3.

[2] 黃玉蘭,夏璞,夏巖,等.物聯(lián)網(wǎng)射頻識別(RFID)核心技術(shù)詳解[M].北京:人民郵電出版社,2012:22-25.

[3] 石封查,崔琛,余劍.基于標(biāo)簽運(yùn)動的一種新型RFID防碰撞算法[J].計算機(jī)科學(xué),2013,40(6):76-79.

[4]FinkenZellerK.射頻識別(RFID)技術(shù)―無線電感應(yīng)的應(yīng)答器和非接觸IC卡原理與應(yīng)用[M].2版.北京:電子工業(yè)出版社,2001:98-101.

[5]EPCGlobal.EPCRadio-FrequencyIdentityProtocolsGengernation-1[S].American:UCC,2013-10-31.

[6] 肖?；?王紅明.一種基于DFSA防碰撞協(xié)議的FBF改進(jìn)算法研究[J].計算機(jī)應(yīng)用與軟件,2013,30(7):305-308.

[7]ChaJR,KimJH.DynamicframedslottedALOHAalgorithmsusingfasttagestimationmethodforRFIDsystem[C]//ConsumerCommunicationsandNETWORKINGConference,2006.Ccnc.2006:768-772.

[8]EPCGlobal.EPCRadio-FrequencyIdentityProtocolsGengernation-2UHFRFIDProtocolforCommunicationat860MHZ～ 960MHZVersion[S].California:EPCGlobal,2008.

[9] 徐圓圓,曾雋芳,劉禹.基于Aloha算法的幀長及分組數(shù)改進(jìn)研究[J].計算機(jī)工程,2008,3(12):57-59.

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

SIMULATION OF DTJ-ALOHA ANTI-COLLISION ALGORITHM BASED ON EPC G1G2 IN RFID

Yang Xiaojiao1Ye Run2Wu Bizao3

1(InformationTechnologyCentre,ChongqingJiaotongUniversity,Chongqing400074,China)2(UniversityofElectronicScienceandTechnologyofChina,Chengdu611731,Sichuan,China)3(ChinaMobileIOTCompanyLimited,Chongqing401336,China)

In the dynamic frame slot ALOHA in the EPC G1G2 standard, when the number of tags is large, the Q value frequently changes, thereby increasing the burden on the reader and other problems. DTJ-ALOHA algorithm is proposed, which takes the difference of the collision, idle and success slots as the threshold to judge the Q value. Compared with the EPC algorithm through Matlab simulation, it is proved that the DTJ-ALOHA algorithm is better than the common improved algorithm in terms of the number of change of Q value, the average throughput, and the cost of the reader.

Dynamic frame slot ALOHA algorithm Throughput Anti-collision RFID

2015-05-25。楊曉嬌，工程師，主研領(lǐng)域：RFID防碰撞算法。葉潤，博士生。吳必造，工程師。

TP312

A

10.3969/j.issn.1000-386x.2017.06.054