改進的基于ALOHA的RFID防碰撞算法

王勇，李婷

（南京郵電大學(xué)，江蘇 南京 210023）

改進的基于ALOHA的RFID防碰撞算法

王勇，李婷

（南京郵電大學(xué)，江蘇 南京 210023）

為了解決RFID系統(tǒng)中電子標(biāo)簽識別效率不高的問題，對基于ALOHA的隨機性防碰撞算法進行了詳細分析，提出了一種新的ALOHA防碰撞算法。在該算法中，針對標(biāo)簽估計，采用動態(tài)調(diào)整的方式自動改變標(biāo)簽估計式中的系數(shù)，使得標(biāo)簽估計個數(shù)隨著已識別的標(biāo)簽數(shù)動態(tài)變化，從而估計下一幀待識別標(biāo)簽數(shù)；而對于幀長調(diào)整，根據(jù)估計的標(biāo)簽數(shù)，通過幀長與標(biāo)簽數(shù)分組的關(guān)系確定。通過MATLAB進行仿真，結(jié)果表明，該算法能明顯提高系統(tǒng)的吞吐率和穩(wěn)定性。

RFID；ALOHA算法；吞吐率；分組；標(biāo)簽估計

1 引言

無線射頻識別（radio frequency identification，RFID）是一種利用射頻信號和空間耦合的傳輸特性進行雙向通信，實現(xiàn)對物體非接觸式自動識別的技術(shù)[1]。隨著科學(xué)技術(shù)的發(fā)展，RFID技術(shù)現(xiàn)已廣泛應(yīng)用于倉庫管理[2]、室內(nèi)定位[3]、圖書館管理[4]等諸多領(lǐng)域。然而當(dāng)有2個或2個以上的標(biāo)簽在相同信道同時與閱讀器進行通信時，由于不同的信號會產(chǎn)生混疊和干擾，使讀寫器不能對任意一個標(biāo)簽進行識別，從而產(chǎn)生碰撞，導(dǎo)致標(biāo)簽識別和數(shù)據(jù)傳送失敗[5,6]。因此為了實現(xiàn)電子標(biāo)簽的有效、可靠識別，如何解決防碰撞問題成為RFID技術(shù)研究的關(guān)鍵點之一。

目前，解決碰撞問題的算法主要有基于ALOHA的隨機性防碰撞算法[7,8]和基于二進制樹的確定性防碰撞算法[9-11]，并在此基礎(chǔ)上對兩種算法進行改進。其中，隨機性防碰撞算法改進的關(guān)鍵點在于幀長的調(diào)整，使其動態(tài)地與待讀標(biāo)簽數(shù)相吻合，尤其適用于標(biāo)簽密集、數(shù)量較多的情況，確定性防碰撞算法的改進在于減少信息冗余和尋求合理的尋址策略。隨機性防碰撞算法簡單、成本低，但系統(tǒng)吞吐率易受標(biāo)簽數(shù)、幀長等的影響；確定性防碰撞算法雖然能保證每個標(biāo)簽?zāi)芗皶r被識別，但具有整個識別周期過長、系統(tǒng)設(shè)計較為復(fù)雜、標(biāo)簽成本較高等缺點[12,13]。

同時近幾年來，針對ALOHA防碰撞算法效率不高的特點，雖然人們提出了各種針對標(biāo)簽估計和幀長調(diào)整的動態(tài)幀時隙ALOHA算法來改進算法效率，但是由于大多都是通過采用上一幀的識別情況來估計標(biāo)簽數(shù)和使幀長等于標(biāo)簽數(shù)來改進算法，所以系統(tǒng)的識別效率一般不超過36.8%。

針對這一特點，本文主要研究針對物流貨物管理、健康管理、畜牧業(yè)流通等RFID主要應(yīng)用領(lǐng)域的防碰撞算法，并在分析了各類ALOHA防碰撞算法后，提出了一種新的ALOHA防碰撞算法。在算法中，采用動態(tài)自適應(yīng)調(diào)整方式，根據(jù)每次估計的標(biāo)簽數(shù)，動態(tài)調(diào)整估計因子，使下一次待識別的標(biāo)簽數(shù)與實際標(biāo)簽數(shù)更接近。同時，為了使系統(tǒng)效率高于理論上當(dāng)幀長與待識別標(biāo)簽數(shù)相等時的效率，本文幀長由幀長與標(biāo)簽數(shù)的分組關(guān)系確定。仿真表明，改進的算法能使系統(tǒng)的效率有所改善。

2 ALOHA類算法

ALOHA算法是一種最基本、最簡單的標(biāo)簽防碰撞算法，它是基于TDMA的一種防碰撞算法，是基于概率的算法。該算法是指閱讀器在不同的時間分別與處于閱讀器讀取范圍內(nèi)的標(biāo)簽通信，從而減少沖突發(fā)生的概率，主要包括改進型的 ALOHA[14]和時隙 ALOHA（slotted-ALOHA）算法[15,16]。

2.1 純ALOHA算法

純ALOHA（P-ALOHA）算法是一種標(biāo)簽先發(fā)言的算法，標(biāo)簽進入閱讀器作用范圍獲得能量，將自己的編碼信息發(fā)給閱讀器，在此過程中，如果有其他標(biāo)簽同時發(fā)送信息，就發(fā)生信號重疊，導(dǎo)致信息完全碰撞或部分碰撞，系統(tǒng)最大吞吐率約為18.4%。

2.2 時隙ALOHA算法

時隙ALOHA算法是對純ALOHA 算法一種最簡單的改進算法，能夠節(jié)約時間。它是在純ALOHA算法的基礎(chǔ)上，把閱讀器發(fā)送信號的時間劃分成多個連續(xù)的離散時隙（slot），而由系統(tǒng)時鐘對時隙長度進行控制。與基本ALOHA算法相比，時隙ALOHA算法中任何一個時隙內(nèi)只存在一個標(biāo)簽成功識別或無標(biāo)簽響應(yīng)或多個標(biāo)簽完全碰撞，沒有基本ALOHA算法中的部分碰撞，所以返回數(shù)據(jù)發(fā)送碰撞的時間減少了一半，這樣提高了信道利用率，系統(tǒng)吞吐率提高1倍，系統(tǒng)最大吞吐率約為36.8%，如圖1所示。

圖1 不同輸入負載的系統(tǒng)吞吐率

2.3 幀時隙ALOHA算法

幀時隙ALOHA算法是在時隙ALOHA算法基礎(chǔ)上的改進，閱讀器將一幀分成N個時隙，每個時隙的長度大于標(biāo)簽的響應(yīng)時間。標(biāo)簽接到閱讀器的請求信號后，在N個時隙中隨機選擇一個時隙通信。如果一個時隙只被唯一的標(biāo)簽選中，則此時隙中標(biāo)簽傳輸?shù)男畔⒈婚喿x器成功接收，標(biāo)簽被正確識別。如果有兩個或兩個以上的標(biāo)簽選擇了同一時隙發(fā)送，則會產(chǎn)生沖突，這些同時發(fā)送信息的標(biāo)簽就不能被讀寫器成功識別。整個算法的識別過程都會如此循環(huán)，一直到所有標(biāo)簽都被識別完成。

假設(shè)幀長為N，閱讀器可識別范圍內(nèi)標(biāo)簽數(shù)為n，并假定所有標(biāo)簽均勻分布在各個時隙，即標(biāo)簽選擇每個時隙的概率都是1/N，那么在一個時隙內(nèi)具有r個標(biāo)簽的概率將服從二項分布。

具有r個標(biāo)簽的時隙期望值為：

該時隙為空時隙、成功時隙、碰撞時隙的概率分別為：

該時隙為空時隙、成功時隙、碰撞時隙的期望值分別為：

系統(tǒng)吞吐率為：

對式（9）求導(dǎo)，即可得出最佳幀長為：

當(dāng)n足夠大時，由泰勒展開式，可得：

所以，當(dāng)閱讀器幀長N和未識別標(biāo)簽數(shù)量n相等時，標(biāo)簽成功傳輸概率最大，系統(tǒng)工作在最佳狀態(tài)，同時系統(tǒng)效率在標(biāo)簽數(shù)量趨于無窮大時約為36.8%。

圖2為幀時隙ALOHA算法在不同幀長條件下，標(biāo)簽數(shù)量和系統(tǒng)吞吐率的關(guān)系曲線。可以看出，當(dāng)標(biāo)簽數(shù)遠小于閱讀器的幀時隙數(shù)時，會造成時隙的浪費，當(dāng)標(biāo)簽數(shù)和閱讀器的幀時隙數(shù)相等時，系統(tǒng)的吞吐率最大。

圖2 不同幀長的系統(tǒng)吞吐率曲線

2.4 動態(tài)幀時隙ALOHA算法

動態(tài)幀時隙ALOHA （dynamic framed slotted ALOHA,DFSA）算法針對幀時隙ALOHA算法的標(biāo)簽數(shù)目與幀長度相差越多，系統(tǒng)性能越差的這個缺點，提出了一種彌補和改善的方法[17]。具體的做法就是使用動態(tài)的幀時隙數(shù)，使得每幀內(nèi)的時隙數(shù)接近系統(tǒng)中標(biāo)簽的數(shù)目，是一種改進的FSA算法，在該算法中，閱讀器能動態(tài)調(diào)整下一次閱讀循環(huán)中每幀的時隙數(shù)目。

3 改進幀時隙ALOHA算法

通過對上面ALOHA算法的分析可知，影響系統(tǒng)吞吐率的因素主要有標(biāo)簽個數(shù)的估計和幀長的調(diào)整。其中，在當(dāng)前研究中較多使用的標(biāo)簽估計算法有最小二乘算法、Schoute算法以及Vogt算法。在這些算法中，每識別完一幀時隙后，雖然能根據(jù)上一幀的識別情況估算出下一幀待識別的標(biāo)簽數(shù)，并使幀長等于標(biāo)簽數(shù)，從而計算出系統(tǒng)的吞吐率，但是它們僅僅使用了本次查詢的碰撞標(biāo)簽來進行估計，且系數(shù)幾乎都是常數(shù)，并沒有進行驗證。同時，使幀長等于標(biāo)簽估計數(shù)，雖然能使系統(tǒng)吞吐率達到最大值，但是碰撞率也隨之變大，并不能使系統(tǒng)工作在穩(wěn)定吞吐率下，因此提出了一種新的防碰撞算法。

3.1 標(biāo)簽估計

本標(biāo)簽估計算法是對參考文獻[18]中算法的改進，核心是根據(jù)本次查詢的標(biāo)簽數(shù)情況，估計出下一幀的標(biāo)簽數(shù)，然后根據(jù)已有的標(biāo)簽估計算法，至下一次查詢時，估計出該次查詢的標(biāo)簽數(shù)，然后對其進行比較，得出預(yù)測因子，從而使系統(tǒng)能根據(jù)兩次連續(xù)的讀取狀態(tài)自動調(diào)整，而當(dāng)前一幀的碰撞時隙數(shù)為零，未識別標(biāo)簽又不為零時，不停止查詢，而是繼續(xù)以初始設(shè)置幀長，對系統(tǒng)進行查詢，從而形成一個周期，直到所有的標(biāo)簽被識別完。

設(shè)第i次查詢后，空閑時隙數(shù)、成功時隙數(shù)、碰撞時隙數(shù)分別為 C0(i)、C1(i)、Ck(i)，待識別的下一幀時隙數(shù)與碰撞時隙數(shù)呈線性關(guān)系，即：

那么就可以根據(jù)第次查詢的碰撞時隙數(shù)預(yù)測下一幀的標(biāo)簽數(shù)，這里k不是固定不變的，而是根據(jù)實際情況進行調(diào)整。

第i+1次查詢后，可以采用JaeRyongCha提出的第一種標(biāo)簽估計算法進行標(biāo)簽估計，為：

則可以求出預(yù)測標(biāo)簽與驗證標(biāo)簽的相對誤差為：

為了使相對誤差的平方最小，使ε2對k求導(dǎo)，可得：

值得注意的是，第i+1的標(biāo)簽估計仍需第i+1的標(biāo)簽估計完成后才能得到，這是不現(xiàn)實的，因此調(diào)整為：

從而得到下一幀待識別的標(biāo)簽數(shù)為：

其中，Ck(0)等于初始設(shè)置的幀長；當(dāng)Ck(i)為零而系統(tǒng)標(biāo)簽未識別完時，系統(tǒng)繼續(xù)以初始設(shè)置幀長識別標(biāo)簽，直到所有標(biāo)簽被識別完。

3.2 幀長調(diào)整

由式（4）、式（5）可知，雖然當(dāng)標(biāo)簽數(shù)與幀長相等時，系統(tǒng)能達到最大的吞吐率，但是系統(tǒng)的碰撞率也隨即增大，且如果標(biāo)簽數(shù)量和系統(tǒng)能達到的幀長最大值相差很多，碰撞問題將難以解決。本算法是根據(jù)分組的思想來提高系統(tǒng)的吞吐率。算法首先確定出以2的次冪連續(xù)為幀長時，如4、8、16、32，系統(tǒng)吞吐率曲線交點處的標(biāo)簽數(shù)，那么該標(biāo)簽數(shù)即可作為調(diào)整幀長和標(biāo)簽分組數(shù)的臨界點。一旦標(biāo)簽數(shù)達到該臨界點，就可以調(diào)整相應(yīng)幀長的大小。而通過計算，可得兩相鄰曲線的標(biāo)簽交點數(shù)為：

然后再根據(jù)系統(tǒng)最大效率與標(biāo)簽數(shù)進行分組，將各種標(biāo)簽數(shù)量下的幀長調(diào)整情況補充完整，見表1。

表1 標(biāo)簽數(shù)分組與幀長選擇

3.3 算法流程

改進算法實現(xiàn)流程如圖3所示。首先系統(tǒng)進行初始化，設(shè)置初始幀長、初始標(biāo)簽數(shù)。然后閱讀器發(fā)送查詢命令，讀取標(biāo)簽，記錄標(biāo)簽響應(yīng)情況：若空閑，則空閑時隙加1；若識別，則成功時隙加1；若碰撞，則碰撞時隙加1。記錄完后，根據(jù)碰撞情況，采用標(biāo)簽估計算法，估計出下一幀待識別的標(biāo)簽數(shù)，并根據(jù)幀長與標(biāo)簽數(shù)分組關(guān)系確定下一幀的幀長：若未識別標(biāo)簽數(shù)不為零且上一幀碰撞標(biāo)簽數(shù)不為零，則進入下一幀識別；若未識別標(biāo)簽數(shù)不為零且上一幀碰撞標(biāo)簽數(shù)為零，則進入下一周期，重新開始識別。

圖3 改進算法實現(xiàn)流程

4 算法仿真與分析

圖4 改進算法與固定幀算法的系統(tǒng)吞吐率對比

本文采用MATLAB軟件對改進算法進行仿真，并與固定幀時隙ALOHA算法進行系統(tǒng)吞吐率對比，改進算法中標(biāo)簽數(shù)目設(shè)置為100，初始幀長設(shè)置為16，固定幀時隙ALOHA算法固定幀長設(shè)置為32，標(biāo)簽數(shù)為100。仿真結(jié)果如圖4所示。從圖4中可以看出，本改進算法的系統(tǒng)吞吐率明顯優(yōu)于固定幀時隙ALOHA算法，最大系統(tǒng)吞吐率可以達到42.19%，且隨著標(biāo)簽數(shù)的增多，系統(tǒng)的吞吐率能以一定的穩(wěn)定狀態(tài)維持在35%左右，高于固定幀時隙ALOHA算法。

5 結(jié)束語

針對幀時隙ALOHA算法系統(tǒng)吞吐率在標(biāo)簽數(shù)達到一定程度后急劇下降的情況，本文對幀時隙ALOHA算法進行了改進，首先通過驗證機制對標(biāo)簽進行了估計，然后由標(biāo)簽數(shù)與幀長分組關(guān)系調(diào)整了幀長。改進后，由仿真結(jié)果可以看出，系統(tǒng)具有相對穩(wěn)定的吞吐率且以一定的周期循環(huán)，同時系統(tǒng)吞吐率明顯高于幀時隙ALOHA算法，并且算法簡單，成本低。

[1]LU Y,WU Z,GAO Z M.Advanced technologies,embedded and multimedia for human-centric computing[M].Netherlands:Springer,2014:655-661.

[2]王亞青,凌翔,白小波.基于RFID的倉庫管理系統(tǒng)研究[J].物流工程與管理,2015,37(3):37,92-93.WANG Y Q,LING X,BAI X B.Warehouse management system based on RFID [J].Logistics Engineering and Management,2015,37(3):37,92-93.

[3]吳文炤,王瀟,趙鯤鵬,等.基于RFID技術(shù)的智慧園區(qū)室內(nèi)定位算法[J].電信科學(xué)，2016,32(3):187-191.WU W Z,WANG X,ZHAO K P,et al.Indoor localization algorithm based on RFID technology forsmartpark[J].Telecommunications Science,2016,32(3):187-191.

[4]胡英俊.基于RFID技術(shù)的圖書館管理系統(tǒng)研究[J].信息技術(shù),2013(9):176-178.HU Y J.Research on library management system based on RFID technology[J].Information Technology,2013(9):176-178.

[5]周沫.超高頻射頻識別系統(tǒng)標(biāo)簽檢測性能研究 [D].南京:南京郵電大學(xué),2013.ZHOU M.The research of tag identification performance in UHF RFID system[D].Nanjing:Nanjing University of Posts and Telecommunications,2013.

[6]JIA X,FENG Q,FAN T,et al.RFID technology and its applications in internet of things (IOT)[C]//The 2nd International Conference on Consumer Electronics,Communications and Networks,April 21-23,2012,Yichang,China.New Jersey:IEEE Press,2012:1282-1285.

[7]孟淑玲.射頻識別系統(tǒng)中防沖突算法的研究[D].天津：天津大學(xué),2008.MENG S L.Research on anti-collision algorithm in RFID system[D].Tianjin:Tianjin University,2008

[8]LEE D,CHOI J,LEE W,et al.A time-optimal anti-collision algorithm for FSA based RFID systems[J].Etri Joural,2011,33(3):458-461.

[9]MYUNG J,LEE W,SRIVASTAVA J.Adaptive binary splitting for efficient RFID tag anti collision[J].IEEE communications Letters,2006,10(3):144-146.

[10]KIM S H,PARK P G.An efficient tree-based tag anti-collision protocol for RFID systems[J].IEEE Transactions on Letters,2007,11(5):449-451.

[11]LAI Y C,LIN C C.A pair resolution blocking algorithm on adaptive binary splitting for RFID systems [J]. IEEE Communications Letters,2008,12(6):432-234.

[12]尹君,何怡剛,李兵.基于分組動態(tài)幀時隙的RFID防碰撞算法[J].計算機工程,2009,35(20):267-269.YIN J,HE Y G,LI B.RFID anti-collision algorithm based on grouping dynamic frame slotted[J].Computer Engineering,2009,35(20):267-269.

[13]胡玲敏.RFID系統(tǒng)的防碰撞算法研究[D].杭州:杭州電子科技大學(xué),2011.HU L M.Research on anti-collision algorithm in RFID system[D].Hangzhou:Hangzhou Dianzi University,2011.

[14]單建鋒,陳明,謝建兵.基于ALOHA算法的RFID防碰撞研究[J].南京郵電大學(xué)學(xué)報(自然科學(xué)報),2013,33(1):56-61.SHAN J F,CHEN M,XIE J B.Research on RFID anti-collision technnology based on Aloha algorithm [J].Journal of Nanjing University of Posts and Telecommunications(Natural Science Edition),2013,33(1):56-61.

[15]WANG H,PEI C,SU B.Collision free arbitration protocol for activeRFID systems [J].JournalofCommunicationsand Networks,2012,14(1):34-39.

[16]舒遠仲,田蕾,張麗.基于排隊理論的時隙ALOHA防碰撞算法[J].計算機工程與設(shè)計,2013,34(7):2632-2636.SHU Y Z,TIAN L,ZHANG L.Timeslots ALOHA anti-collision algorithm based on queuing theory[J].Computer Engineering and Design,2013,34(7):2632-2636.

[17]SCHOUTE F C.Dynamic frame length ALOHA [J].IEEE Transactions on Communications,1983,31(4):565-568.

[18]栗華.UHF RFID多標(biāo)簽防碰撞算法的研究與性能分析[D].濟南:山東大學(xué),2011.LI H.Research and performance analysis of UHF RFID multi-tag anti-collision algorithms[D].Jinan:Shandong University,2011.

Improved RFID anti-collision algorithm based on ALOHA

WANG Yong,LI Ting
Nanjing University of Posts and Telecommunications,Nanjing 210023,China

In order to solve the problem of low efficiency of electronic tag identification in RFID system,a new ALOHA anti-collision algorithm was presented.In this algorithm,the coefficients of the tag estimation were automatically changed by using the dynamic adjustment method,which made the number of tag estimation could be dynamic changed with the number of identified tags,then the number of tags to be identified was estimated.And for the frame length adjustment,it could be determined by the relationship between the length of the frame and the tag number according to the estimated number of tags.With the tool of MATLAB,the results show that the proposed algorithm can significantly improve the throughput and stability of the system.

RFID,ALOHA algorithm,throughput,grouping,tag estimation

TP391

A

10.11959/j.issn.1000-0801.2016174

2016-03-30；

2016-06-15

王勇（1961-），男，博士，南京郵電大學(xué)教授，主要研究方向為虛擬儀器（VXI），測量與控制技術(shù)，各類通信網(wǎng)的監(jiān)測、監(jiān)控與管理。

李婷（1991-），女，南京郵電大學(xué)碩士生，主要研究方向為精密測試技術(shù)與智能儀器。