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

楊曉嬌 葉 潤 吳必造

1(重慶交通大學信息技術中心 重慶 400074)2(電子科技大學 四川 成都 611731)3(中移物聯網有限公司 重慶 401336)

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

楊曉嬌1葉 潤2吳必造3

1(重慶交通大學信息技術中心 重慶 400074)2(電子科技大學 四川 成都 611731)3(中移物聯網有限公司 重慶 401336)

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

動態幀時隙 ALOHA算法 吞吐率 防碰撞 射頻識別RFID

0 引 言

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

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

1 EPC中的動態幀時隙DFS-ALOHA算法

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

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

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

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

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

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

1.2EPCG1G2中的防碰撞算法思想

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

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

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

2 DTJ-ALOHA算法

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

在ALOHA算法的基礎上面，可推導得出在FS-ALOHA算法中，某時隙中存在k個標簽的概率為：

(1)

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

(2)

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

圖2 N=16，32，64，128，256時FS-ALOHA 算法吞吐率與標簽個數的關系

由圖2可知，要保持吞吐率較高，則取兩條曲線的交點間部分對應的時隙數(如標簽個數在ab段時取時隙數N=64)，吞吐率較高的兩條直線的交點即為時隙數為N的曲線與時隙數為2N和N/2的交點(以N=64這條曲線的吞吐率為例分析，與2N的交點即為b點與2/N的交點即為a點)。可以推出時隙數分別為N以及2N的兩條吞吐率曲線的交點所對應的標簽個數nN=2N為：

(3)

(4)

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

(5)

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

(6)

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

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

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

Th+= N×(Pcol-Psuc)=

(7)

Th-= N×(Pnull-Psuc)=

(8)

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

表1 Q值與其對應的閾值Th

表1中提前計算好了Q跳變的閾值，閱讀器只需要根據每個時隙的狀態做一個簡單的比較以及加減法運算，這樣就有效解決了本節開始提出的由于做浮點運算而導致閱讀器負擔增加的問題。

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

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

圖4 DTJ-ALOHA算法的詳細程序流程圖

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

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

3 DTJ-ALOHA算法的仿真以及結果分析

本文的所有仿真實驗都是在Matlab7.0平臺上進行的。分別編程實現不同算法識別標簽的過程，再統計運行的結果，為了減小偶然因素對算法評估造成影響，本文中所有圖中的結果都是識別相同的標簽50次后的結果所取的平均值。

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

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

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

通過圖5與表2可看出，不論標簽多與少，改進算法都將Q值改變次數控制在一定范圍30內。即改進算法相比于EPCG1G2算法適應性較好。

表2 Q值改變次數對比圖

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

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

圖6 吞吐率比較圖

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

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

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

表3 EPC C1G2協議命令/參數長度

圖6和圖7的結果已經驗證了改進的DTJ-ALOHA算法在關鍵性能指標上不僅優于EPC G1G2推薦的算法也優于常見的改進(基于標簽估計的動態幀時隙ALOHA)算法。

圖7 三種不同算法對應的閱讀器開銷對比圖

4 結 語

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

[1] 孫其博,劉杰,黎羴,等.物聯網:概念、架構與關鍵技術研究綜述[J].北京郵電大學學報,2010,33(3):2-3.

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

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

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

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

[6] 肖海慧,王紅明.一種基于DFSA防碰撞協議的FBF改進算法研究[J].計算機應用與軟件,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算法的幀長及分組數改進研究[J].計算機工程,2008,3(12):57-59.

[10] 吳淼,劉德盟,張釗鋒.基于EPCGen2防碰撞機制的研究與優化[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。楊曉嬌，工程師，主研領域：RFID防碰撞算法。葉潤，博士生。吳必造，工程師。

TP312

A

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