基于動態(tài)Q學(xué)習(xí)的防碰撞算法的研究

陳　浩，張海峰，應(yīng)屹航

(1．杭州電子科技大學(xué)電子信息學(xué)院，浙江 杭州 310018；2．杭州國芯科技股份有限公司，浙江 杭州 310012)

?

基于動態(tài)Q學(xué)習(xí)的防碰撞算法的研究

陳浩1，張海峰1，應(yīng)屹航2

(1．杭州電子科技大學(xué)電子信息學(xué)院，浙江 杭州 310018；2．杭州國芯科技股份有限公司，浙江 杭州 310012)

在射頻識別系統(tǒng)中防碰撞是很關(guān)鍵的技術(shù)之一，針對EPC-C1G2協(xié)議的防碰撞算法中Q值調(diào)節(jié)不夠靈敏的不足，提出了一種雙參數(shù)且參數(shù)動態(tài)變化調(diào)節(jié)Q值的改進(jìn)算法(EDQ算法).在EDQ算法中，將單一參數(shù)C分為雙參數(shù)Cs和Cc，分別用來調(diào)節(jié)空閑和碰撞時隙的Q值.通過大量的實驗分析，提出了在不同Q值下雙參數(shù)Cs和Cc的最優(yōu)值.仿真實驗表明，算法能夠減少時隙的浪費，從而增大系統(tǒng)吞吐率，減少標(biāo)簽的識別時間.

射頻識別；防碰撞算法；Q值；系統(tǒng)吞吐率

0　引　言

無線射頻識別技術(shù)(Radio Frequency Identification，RFID)，是從二十世紀(jì)九十年代興起的一種非接觸的自動識別技術(shù)[1].對于一個RFID系統(tǒng)，同一時間可能有多個電子標(biāo)簽進(jìn)入射頻區(qū)域，在與閱讀器進(jìn)行通訊時發(fā)生信號混疊，產(chǎn)生所謂的碰撞.為了解決這個問題，各國的學(xué)者提出了一系列的標(biāo)簽防碰撞算法[2].目前，防碰撞算法主要分為兩類：一類是確定性防碰撞算法，主要是基于二進(jìn)制搜索方法，如動態(tài)二進(jìn)制搜索算法、后退索引二進(jìn)制算法等[3-4]；另外一類是隨機(jī)性防碰撞算法，主要是基于ALOHA的算法，如時隙ALOHA算法、幀時隙ALOHA算法和動態(tài)幀時隙ALOHA算法[5-7].EPCglobal公司提出的EPC-C1G2協(xié)議采用的防碰撞算法叫Q學(xué)習(xí)算法，稱為DQ算法，它是在幀時隙ALOHA算法基礎(chǔ)上提出的，該算法不用進(jìn)行未識別標(biāo)簽數(shù)目的估計，而是使用一種啟發(fā)式的方法使幀大小趨向最優(yōu)[8].但是DQ算法采用單一參數(shù)C調(diào)整Q值，且C是固定的，使得Q值的調(diào)整不夠靈敏.針對這個缺點，本文提出將參數(shù)C分成兩個不同的參數(shù)，并且隨著未識別標(biāo)簽數(shù)目的變化找到它們的最優(yōu)值.

1　EPC-C1G2防碰撞算法

EPC-C1G2協(xié)議提出的DQ算法使用Query命令初始化一個輪詢周期，包含一個時隙計數(shù)參數(shù)Q，參與輪詢的標(biāo)簽在收到Query命令后在(0，2Q-1)范圍內(nèi)產(chǎn)生一個隨機(jī)數(shù)，并將這個數(shù)寫入自身的時隙計數(shù)器.時隙計數(shù)器為0的標(biāo)簽向讀卡器發(fā)送一個RN16(16位的隨機(jī)數(shù)).隨機(jī)數(shù)不為0的標(biāo)簽等待下一條QueryRep或QueryAdjust命令.標(biāo)簽接收到QueryRep命令時，時隙計數(shù)器減1，當(dāng)時隙計數(shù)器為0時，標(biāo)簽發(fā)送應(yīng)答信息.標(biāo)簽接收到QueryAdjust命令時，調(diào)整Q值，并重新在(0，2Q-1)范圍內(nèi)產(chǎn)生一個隨機(jī)數(shù)寫入自身的時隙計數(shù)器，重復(fù)以上操作.

DQ算法使用參數(shù)Q使得幀長趨于最優(yōu)，Q參數(shù)是計算幀長的指數(shù)參數(shù)，幀長=2Q，同時取Q的浮點數(shù)NQ，用來進(jìn)行Q參數(shù)的計算.當(dāng)發(fā)送一個Query命令開啟一個輪詢周期時，讀卡器會在每個時隙接收標(biāo)簽的回復(fù).將時隙分為成功、碰撞和空閑時隙，依據(jù)這3個參數(shù)改變下一幀的大小.當(dāng)時隙為空閑時，NQ減去常數(shù)C；時隙為碰撞時，NQ加上常數(shù)C；時隙為成功時，NQ不變.在下一個時隙開始時取Q=round(NQ)，如果Q發(fā)生變化，則發(fā)送QueryAdjust命令，完成對幀長的調(diào)節(jié).在EPC-C1G2協(xié)議中建議0.1≤C≤0.5，單參數(shù)DQ算法流程圖如圖1所示.

2　改進(jìn)的防碰撞算法(EDQ算法)

2.1EDQ算法對DQ算法的改進(jìn)

本文從兩點來優(yōu)化DQ算法：

1)C的動態(tài)性.如果C比較大，那么幀長將會很快地收斂到最佳點，但是會在最佳點發(fā)生很大的震蕩；如果C比較小時，收斂到最佳點后改變會很小，但是收斂的速度將比較慢.由此可知，當(dāng)Q較大時，C應(yīng)該較?。籕較小時，C應(yīng)該較大.所以改進(jìn)的算法讓C跟隨標(biāo)簽數(shù)目的變化而取最佳值.

圖1　單參數(shù)DQ算法流程圖

2)C的差異性.一般情況下，在一個時隙里發(fā)生碰撞的概率要小于空閑的概率，所以在一幀中出現(xiàn)碰撞時隙的數(shù)目要小于空閑時隙的數(shù)目.DQ算法中，在碰撞時隙和空閑時隙使用單一參數(shù)C來調(diào)整Q值，是不合理的，不利于達(dá)到時隙的最佳分布，從而不利于提高系統(tǒng)的效率.本文提出使用兩個參數(shù)來調(diào)整Q值.

2.2EDQ算法流程

通過對DQ算法改進(jìn)的描述可知，本文設(shè)計算法流程如圖2所示.從圖2中可以看出，EDQ算法使用了兩個新的變量Cc和Cs，在碰撞時隙用Cc來調(diào)整NQ，而在空閑時隙，用Cs來調(diào)整NQ.如果Q值改變，讀卡器會發(fā)送QueryAdjust命令來改變幀長；如果Q值不變時，則發(fā)送QueryRep命令繼續(xù)進(jìn)行讀取操作.并且在輪詢過程中，Cc和Cs會根據(jù)Q值動態(tài)的變化.

圖2　雙參數(shù)且參數(shù)動態(tài)變化EDQ算法流程圖

2.3Cs與Cc的取值與優(yōu)化

在幀時隙ALOHA算法中，如果幀長為S，而未識別標(biāo)簽數(shù)為N，那么當(dāng)S=N的時候，系統(tǒng)效率最高.在系統(tǒng)效率最高時，可以得出系統(tǒng)碰撞概率pc和空閑概率ps：

(1)

(2)

如果N取無限大，可以得到pc=1-2/e,ps=1/e.在S=N的條件下，Q取值為最優(yōu)取值，顯然Cs與Cc的比值成反比，可得：

Cc/Cs=ps/pc=1/(e-2)≈1.4

(3)

在DQ算法中，Q值與參數(shù)C的最佳關(guān)系如表1所示.當(dāng)Q值增大時，C值變小.

在EDQ算法中，Cc和Cs需要符合下列條件：

1)Cc=1.4Cs；2)0.1≤Cc≤0.5；3)0.1≤Cs≤0.5.

假設(shè)在相同的Q值情況下，取一個參數(shù)t作為調(diào)節(jié)因子，且與參數(shù)C有如下的關(guān)系：Cs=tC；Cc=1.4Cs.其中，t是Cs和Cc的調(diào)節(jié)因子.

通過EQD算法，在Matlab中分別對相同Q值下的不同調(diào)節(jié)因子t的取值進(jìn)行仿真，得到系統(tǒng)效率.例如在Q=8，C=0.2，標(biāo)簽數(shù)目為256的情況下進(jìn)行仿真，如圖3所示，當(dāng)t=0.9時，系統(tǒng)效率最高.所以當(dāng)Q=8時，最優(yōu)參數(shù)Cc=0.25，Cs=0.18.

表1　Q值與C值最佳關(guān)系

圖3　Q=8時，參數(shù)Cs和Cc最優(yōu)值

通過Maltab仿真，得到在不同Q值下的調(diào)節(jié)因子t和最佳參數(shù)Cc，Cs的值，如表2所示.

表2　不同Q值下的最佳參數(shù)

3　系統(tǒng)仿真及性能分析

圖4　基于lowbound估計的DFSA，DQ和EDQ算法仿真

本文采用蒙特卡洛方法，在計算機(jī)上使用Matlab進(jìn)行仿真來驗證本文提出的EDQ算法，所有的實驗結(jié)果都是經(jīng)過100次的獨立實驗平均得到的.

在RFID防碰撞算法中，系統(tǒng)效率是衡量系統(tǒng)性能的重要指標(biāo).在Matlab軟件中，分別對基于lowbound預(yù)測的動態(tài)幀時隙、DQ算法以及EDQ算法的吞吐率進(jìn)行仿真.標(biāo)簽范圍在100～1 000，仿真結(jié)果如圖4所示.可以看到基于lowbound估計的動態(tài)幀時隙算法的系統(tǒng)吞吐率基本保持在31.5%，而DQ算法的系統(tǒng)吞吐率基本維持在33%，本文提出的EDQ算法的系統(tǒng)吞吐率保持在34.5%，特別在標(biāo)簽數(shù)目很大時，EDQ算法更具有優(yōu)勢.

4　結(jié)束語

本文在研究EPC-C1G2協(xié)議的DQ防碰撞算法的基礎(chǔ)上，發(fā)現(xiàn)使用單一且不變的參數(shù)C對Q值進(jìn)行調(diào)節(jié)時，不能迅速地使幀長接近未識別的標(biāo)簽數(shù)目，從而提出了使用兩個參數(shù)Cc和Cs分別調(diào)節(jié)碰撞和空閑時隙的Q值，而且這兩個參數(shù)具有一定的比值關(guān)系，同時這兩個參數(shù)隨著Q值的變化而動態(tài)地做出改變.EDQ算法可以通過參數(shù)Cc和Cs迅速調(diào)節(jié)Q值，使幀長更加接近未識別標(biāo)簽數(shù)目，獲得更高的系統(tǒng)吞吐率.

[1]米志強(qiáng),楊曙,王武,等.射頻識別(RFID)技術(shù)與應(yīng)用[M].北京:電子工業(yè)出版社,2011:3-4.

[2]FINKENZELLER K.RFID Handbook:Radio-frequency Identification Fundamentals and Application (Second Edition)[M].England:John Wiley and Sons,2003:1-10.

[3]杜海濤,徐昆良,王威廉.基于返回式二進(jìn)制樹形搜索的反碰撞算法[J].云南大學(xué)學(xué)報(自然科學(xué)版),2006,28(1):133-136.

[4]MYUNG J,LEE W,SRIVASTAVA J,et al.Tag-Splitting:Adaptive Collision Arbitration Protocols for RFID Tag Identification[J].Parallel and Distributed Systems,IEEE Transactions on,2007,18(6):763-775.

[5]CHEN W T.An accurate tag estimate method for improving the performance of an RFID anti-collision algorithm based on dynamic frame length ALOHA[J].Automation Science and Engineering,IEEE Transaction on,2009,6(1):9-15.

[6]NAMBOODIRI V, DESILVA M, DEEGALA K,et al.An extensive study of slotted Aloha-basedRFID anti-collision protocols[J].Computer communications,2012,35(16):1955-1966.

[7]郭志濤,程林林,周艷聰,等.動態(tài)幀時隙ALOHA算法的改進(jìn)[J].計算機(jī)應(yīng)用研究,2012,29(3):907-909.

[8]馬倩,石良平,周力宏.ISO18000_6C標(biāo)準(zhǔn)的防碰撞算法研究[J].計算機(jī)應(yīng)用,2008,28(S2):341-343.

Research on Anti-collision Algorithm Based on Dynamic Q Learning

CHEN Hao1, ZHANG Haifeng1, YING Yihang2

(1.SchoolofElectronicInformation,HangzhouDianziUniversity,HangzhouZhejiang310018,China;2.HangzhouNationalChipScience&TechnologyCo.Ltd.,HangzhouZhejiang310012,China)

Anti-collision is the key technology in the radio frequency identification system, as the insufficient ofQadjustment is not sensitive enough in anti-collision algorithm for EPC-C1G2 protocol, an improved algorithm(EDQ algorithm) is proposed for adjusting theQvalue of the dual-parameter and parameter can be dynamic changing. In the EDQ algorithm, the single parameterCis divided into two parametersCsandCc, which are used to adjust theQvalue of the idle and collision slots. Through the analysis of a lot of experiments, the optimal values of the dual-parameterCcandCsare presented under differentQvalue. The simulation experiments show that the algorithm can reduce the waste of time slots, thus increasing the system throughput rate and reducing the time of label identification.

radio frequency identification; anti-collision algorithm;Qvalue; system throughput rate

10.13954/j.cnki.hdu.2016.01.006

2015-06-23

陳浩(1990-)，男，江蘇泰州人，碩士研究生，電子與通信工程.通信作者:張海峰副教授，E-mail: hfzhang0811@hdu.edu.cn.

TP391.41

A

1001-9146(2016)01-0027-05