管小衛(wèi)，傅 偉，蔣道霞

GUAN Xiao-wei, FU Wei, JIANG Dao-xia

(江蘇財(cái)經(jīng)職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)技術(shù)與藝術(shù)設(shè)計(jì)系，淮安 223003)

0 引言

射頻識別（RFID）是一種非接觸式自動識別技術(shù)。一個RFID系統(tǒng)[1]由閱讀器和標(biāo)簽構(gòu)成，現(xiàn)已廣泛應(yīng)用在防偽防盜、物流管理、交通管理等多個領(lǐng)域。在汽車防盜定位系統(tǒng)中，給每個汽車安裝一個標(biāo)簽，當(dāng)汽車進(jìn)入識別區(qū)時，若多個標(biāo)簽同時響應(yīng)閱讀器發(fā)送的查詢信息，標(biāo)簽之間必然發(fā)生碰撞。為了解決多標(biāo)簽碰撞問題，系統(tǒng)需要采用相應(yīng)的防碰撞算法來解決。目前解決多標(biāo)簽沖突問題的算法都是基于時分多址（TDMA）技術(shù)，主要有兩種類型的防碰撞算法：一種是基于二進(jìn)制樹結(jié)構(gòu)的確定性算法[2～4]，這類算法主要通過遞歸方法將沖突的標(biāo)簽分成兩個子集，逐漸縮小范圍，直到能正確識別出標(biāo)簽。但該類防碰撞算法需要閱讀器準(zhǔn)確的檢測出發(fā)生數(shù)據(jù)碰撞的比特位置。另一種是基于ALOHA的不確定性算法[5,6]，這類算法的缺點(diǎn)是時隙浪費(fèi)、吞吐量低。

由于汽車進(jìn)入閱讀器識別區(qū)的時間較短，且在不同的時間段車流量有較大變化，若采用幀時隙ALOHA算法，當(dāng)汽車數(shù)量較少時將造成時隙浪費(fèi)，在汽車數(shù)量遠(yuǎn)大于時隙數(shù)時，碰撞概率增加，系統(tǒng)的識別率將急劇下降。對于分組幀時隙ALOHA算法的研究，S.R.Lee[7]等人提出的分組幀時隙ALOHA算法是將幀長設(shè)為最大，當(dāng)標(biāo)簽數(shù)量大于最大幀長時再將標(biāo)簽分組，在標(biāo)簽數(shù)量較少時造成時隙浪費(fèi)；尹君[8]等人提出了基于分組動態(tài)幀時隙的RFID防碰撞算法，根據(jù)標(biāo)簽距離閱讀器的距離將標(biāo)簽分組，需在標(biāo)簽內(nèi)加入晶體管，提高了標(biāo)簽的復(fù)雜度和成本；張學(xué)軍[9]等人提出的基于標(biāo)簽識別碼分組的連續(xù)識別防碰撞算法研究是基于標(biāo)簽編碼分組的二進(jìn)制樹結(jié)構(gòu)確定性防碰撞算法；蘇恒陽[10]等人提出的改進(jìn)的動態(tài)時隙自適應(yīng)條件的方法將標(biāo)簽分組，但在分組前需確定標(biāo)簽數(shù)，閱讀器需對標(biāo)簽數(shù)進(jìn)行評估。在本系統(tǒng)中，標(biāo)簽先進(jìn)入閱讀器識別區(qū)一般也先離開，因此可采用先到先識別的方式，將標(biāo)簽按照進(jìn)入識別區(qū)的時間進(jìn)行分組，先識別最先進(jìn)入識別區(qū)的組，以提高標(biāo)簽識別率?；谏鲜龇治?，本文提出了一種基于時間段分組的幀時隙ALOHA算法，仿真結(jié)果表明,本方法能有效提高系統(tǒng)的吞吐量，減少時隙浪費(fèi)。

1 ALOHA防碰撞算法分析研究

1.1 經(jīng)典ALOHA算法

圖1 經(jīng)典ALOHA算法模擬圖

在經(jīng)典ALOHA算法中，當(dāng)標(biāo)簽進(jìn)入閱讀器識別區(qū)后，標(biāo)簽自動向閱讀器發(fā)送自己的ID，如果在此時間段內(nèi)沒有其他標(biāo)簽發(fā)送ID到閱讀器，那么閱讀器就能正確識別此標(biāo)簽，否則將不能正確識別，產(chǎn)生沖突。當(dāng)沖突發(fā)生時，閱讀器將發(fā)送一條命令讓所有的標(biāo)簽停止當(dāng)前的發(fā)送，等待一個隨機(jī)的時間后重發(fā)自己的ID，直到所有標(biāo)簽被正確識別后，整個循環(huán)才停止。經(jīng)典ALOHA算法思想簡單，隨機(jī)性大，沖突率高，如圖1所示，當(dāng)標(biāo)簽2和標(biāo)簽3發(fā)送自己ID時，由于時間間隔小于T0，就發(fā)生沖突，信道利用率較低，吞吐率最大約為18.4%。

1.2 時隙ALOHA算法

時隙ALOHA算法是在經(jīng)典ALOHA算法基礎(chǔ)上的擴(kuò)展，改進(jìn)的思想是將時間分成多個離散的時隙，且每個時隙大于標(biāo)簽響應(yīng)的時間長度，標(biāo)簽只能在每個時隙起始發(fā)送數(shù)據(jù)，閱讀器控制在同步時隙內(nèi)傳送數(shù)據(jù)。由于時隙ALOHA算法數(shù)據(jù)幀固定，不能根據(jù)實(shí)際標(biāo)簽數(shù)量來調(diào)整幀的大小，所以只有在標(biāo)簽較少時，性能表現(xiàn)良好，標(biāo)簽數(shù)量增多時，系統(tǒng)性能急劇惡化，系統(tǒng)性能不穩(wěn)定。與經(jīng)典ALOHA算法相比，信道利用率理論上能提高一倍，吞吐率最大約為36.8%。

1.3 靜態(tài)幀時隙ALOHA算法

幀時隙ALOHA算法是在時隙ALOHA算法基礎(chǔ)上的改進(jìn)，閱讀器將一幀分成N個時隙，每個時隙的長度大于標(biāo)簽的響應(yīng)時間。標(biāo)簽接到閱讀器的請求信號后，在N個時隙中隨機(jī)選擇一個時隙通信。該方法需要閱讀器和標(biāo)簽之間的同步操作，并且?guī)淖畲髸r隙數(shù)N預(yù)先設(shè)定。該算法適用于傳輸數(shù)據(jù)量較大的場合，當(dāng)標(biāo)簽數(shù)遠(yuǎn)大于閱讀器的幀時隙數(shù)時，在幀周期內(nèi)會頻繁發(fā)生標(biāo)簽碰撞，識別標(biāo)簽的時間將會大大增加，當(dāng)標(biāo)簽數(shù)遠(yuǎn)小于閱讀器的幀時隙數(shù)時，會造成時隙的浪費(fèi)，當(dāng)標(biāo)簽數(shù)和閱讀器的幀時隙數(shù)時相等時，系統(tǒng)的吞吐率最大。

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

動態(tài)幀時隙ALOHA算法是基于靜態(tài)幀時隙ALOHA算法的改進(jìn)，它根據(jù)標(biāo)簽數(shù)和時隙數(shù)等信息來動態(tài)調(diào)整幀長度，從而克服靜態(tài)幀時隙ALOHA算法的缺點(diǎn)。當(dāng)標(biāo)簽數(shù)大于時隙數(shù)時，通過加大幀長度來較少碰撞；當(dāng)標(biāo)簽數(shù)小于時隙數(shù)時，則會減小幀長度，從而避免時隙浪費(fèi)。動態(tài)幀時隙ALOHA算法能提高標(biāo)簽的識別率，但是由于硬件條件的限制，不能無限增加幀長度（通常一幀不超過256個時隙）。因此，當(dāng)標(biāo)簽數(shù)量較大時，幀長度也隨之變大，增加系統(tǒng)的工作負(fù)擔(dān)。

2 基于時間段分組的幀時隙ALOHA算法

2.1 算法的基本思想

首先根據(jù)標(biāo)簽進(jìn)入閱讀器識別區(qū)的時間順序?qū)?biāo)簽分組，然后再利用幀時隙ALOHA算法對組內(nèi)的標(biāo)簽進(jìn)行識別。算法的標(biāo)簽分組機(jī)制如圖2所示。

圖2 標(biāo)簽分組機(jī)制

每個標(biāo)簽分配一個時間分組計(jì)數(shù)器，閱讀器每隔時間分組周期T向識別區(qū)內(nèi)的標(biāo)簽群發(fā)送時間分組指令，在此時間段內(nèi)到達(dá)的所有標(biāo)簽具有相同的時間分組值。標(biāo)簽的時間分組值初始化為0，每收到一次分組指令后所有時間分組值都加1。因此，時間分組值越大表示標(biāo)簽越先進(jìn)入識別區(qū)，所以閱讀器先識別時間分組值最大的標(biāo)簽群。

2.2 最佳幀長度

令一幀的時隙數(shù)為L，標(biāo)簽總數(shù)為n，有x個標(biāo)簽選擇同一時隙的概率P為：

在一幀的識別周期后，成功識別標(biāo)簽的時隙數(shù)期望值為：

規(guī)定系統(tǒng)的吞吐率為：

本文提出的基于時間段分組的幀時隙ALOHA算法中，首先根據(jù)標(biāo)簽進(jìn)入閱讀器識別區(qū)的時間順序?qū)?biāo)簽分成N組，然后再利用幀時隙ALOHA算法對組內(nèi)的標(biāo)簽進(jìn)行識別。由以上公式可得，分組后系統(tǒng)的吞吐率S為：

對式（4）求導(dǎo)：

令式（5）值為0，通過解上述方程式，可得出最佳幀長度為：

當(dāng)n很大時，通過泰勒級數(shù)簡化式（6）得：

由以上公式可知，當(dāng)每個分組的標(biāo)簽數(shù)與幀長度大約相等時，在一個識別周期內(nèi)能識別的標(biāo)簽數(shù)最多，即系統(tǒng)獲得最大吞吐率。當(dāng)車速在40km/h～60km/h時，閱讀器識別區(qū)內(nèi)的車輛數(shù)約為200，一輛汽車從進(jìn)入識別區(qū)到離開一般為10秒，可設(shè)時間分組周期T的值為2秒（當(dāng)車速提高時，可通過適當(dāng)減小T的值來減少組內(nèi)的標(biāo)簽數(shù)），將車輛近似均分為5組，每組標(biāo)簽數(shù)量在25～45之間，所以本文幀長度設(shè)為32。

2.3 算法的實(shí)現(xiàn)流程

在如圖3所示的算法實(shí)現(xiàn)流程圖中，首先閱讀器的時間段命令參數(shù)R的值初始化為1；標(biāo)簽未進(jìn)入閱讀器識別區(qū)時，標(biāo)簽時間段分組數(shù)D的值初始化為0，進(jìn)入識別區(qū)后，每接收一次時間段分組指令后值都加1；然后，閱讀器發(fā)送激活信號，將其識別區(qū)內(nèi)時間段分組數(shù)與時間段命令參數(shù)相等的標(biāo)簽激活，激活的標(biāo)簽采用ALOHA算法傳送信息，步驟如下：

圖3 基于時間段分組的幀時隙ALOHA算法實(shí)現(xiàn)流程

1）首批進(jìn)入閱讀器識別區(qū)的標(biāo)簽若無發(fā)生碰撞（全部給出應(yīng)答信號），即被激活，則R值仍為1；若標(biāo)簽碰撞，即在一個時間段分組周期內(nèi)無法識別所有標(biāo)簽，則R值加1，轉(zhuǎn)步驟2）執(zhí)行。

2）標(biāo)簽繼續(xù)接收閱讀器分組指令，在上個時間段分組周期內(nèi)未被識別的標(biāo)簽D值加1，若仍與R值相等，標(biāo)簽繼續(xù)發(fā)送應(yīng)答信號；在一個時間段分組周期內(nèi)無發(fā)生標(biāo)簽碰撞，R值減1，閱讀器發(fā)送激活信號，將D=R的標(biāo)簽激活后繼續(xù)識別標(biāo)簽。若上一個時間段分組周期里有未被識別的標(biāo)簽，那么新進(jìn)入識別區(qū)的標(biāo)簽時間分組值D加1，但不接收激活信號，直到其時間段分組值D與時間段命令參數(shù)R相等時才接收激活信號。

最后，閱讀器向已識別的標(biāo)簽發(fā)送去激活信號，標(biāo)簽不再接收激活信號，等待一定的時間之后，將時間段分組數(shù)D設(shè)置為0，可再次接收閱讀器發(fā)生的激活信號；未識別的標(biāo)簽，若在連續(xù)兩個分組周期內(nèi)沒有接收到時間段分組指令，則將時間段分組數(shù)D設(shè)置為0。

3 仿真分析研究

在汽車防盜定位系統(tǒng)中，汽車標(biāo)簽數(shù)量一般在100～250之間，假設(shè)汽車在閱讀器識別區(qū)內(nèi)的停留時間為10秒，將閱讀器的時間段分組周期設(shè)置為2秒，識別區(qū)內(nèi)的標(biāo)簽被近似均分為5組，每組標(biāo)簽數(shù)量在25～45之間，幀長度L的取值按2的冪次方遞增，標(biāo)簽數(shù)與不同幀長度和分組數(shù)具體設(shè)定值如表1所示。

表1 標(biāo)簽數(shù)與不同幀長度和分組數(shù)

為了驗(yàn)證本文的提出的算法性能，分析標(biāo)簽數(shù)n、幀長度L以及分組時在不同取值系統(tǒng)的吞吐率，這里取值為0～300，利用MATLAB對算法的設(shè)計(jì)和性能進(jìn)行仿真和分析。

圖4 采用不同的幀長度時系統(tǒng)吞吐率比較

幀長度L取不同值時系統(tǒng)吞吐率的仿真結(jié)果如圖4所示。當(dāng)幀長度L=16，標(biāo)簽數(shù)n在50-100之間時，系統(tǒng)獲得較高吞吐率；同時，隨著標(biāo)簽數(shù)量的增加，若不進(jìn)行分組，系統(tǒng)的吞吐率會急劇下降。本系統(tǒng)中每組標(biāo)簽數(shù)量在25～45之間，與32相近，所以取幀長度L=32，系統(tǒng)的吞吐率最高，且比較穩(wěn)定，與推導(dǎo)的最優(yōu)幀長度相符。

本算法是對幀時隙ALOHA算法的一種改進(jìn)，所以分別與幀長度為128和256的幀時隙ALOHA算法進(jìn)行比較，仿真結(jié)果如圖5所示。

圖5 兩種算法吞吐率比較

仿真結(jié)果表明，基于時間段分組的幀時隙ALOHA算法在標(biāo)簽數(shù)量n在100～250之間時系統(tǒng)的吞吐率最優(yōu)且穩(wěn)定；當(dāng)標(biāo)簽數(shù)量n在130～210時，優(yōu)于幀時隙ALOHA算法，車速在60km/h～80km/h時，本算法優(yōu)于幀時隙ALOHA算法，具有明顯的性能優(yōu)勢，有效地提高了系統(tǒng)的吞吐率。

4 結(jié)論

針對汽車防盜定位系統(tǒng)，本文對幀時隙ALOHA算法做了改進(jìn)，根據(jù)標(biāo)簽進(jìn)入閱讀器識別區(qū)的時間順序?qū)?biāo)簽進(jìn)行分組，提出一種基于時間段分組的幀時隙ALOHA防碰撞算法。仿真結(jié)果表明：在一個閱讀器識別區(qū)內(nèi)車輛數(shù)量在100～250之間，采用本算法具有明顯的優(yōu)勢，系統(tǒng)的吞吐率最優(yōu)且穩(wěn)定，大大提高了汽車標(biāo)簽的識別率。

[1]周曉光,王曉華,王偉.射頻識別（RFID）系統(tǒng)設(shè)計(jì).仿真與應(yīng)用[M].北京:人民郵電出版社,2008:119-135.

[2]Myung J,Lee W,Srivastava J.Adaptive Binary Splitting for Efficient RFID Tag Anti-collision[J].IEEE Communications Letters,2006,10(3):144-146.

[3]Kim S H,Park P G An Efficient Tree-based Tag Anticollision Protocol for RFID Systems[J].IEEE Trans,on Letters,2007,11(5):449-451.

[4]Lai Yuan-Cheng, Lin Chih-Chung. A Pair-resolution Blocking Algorithm on Adaptive Binary Splitting for RFID System[J].IEEE Communications Letters,2008,12(6):432-434.

[5]孟淑玲.射頻識別系統(tǒng)中防沖突算法的研究[D].天津.2008.5.

[6]LEE D,CHOI J,LEE W,et al.A time-optimal anticollision algo-rithm for FSA-based RFID systems[J].ETRI Journal,2011,33(3):458-461.

[7]S.R.Lee,S.D.Joo,C.W.Lee. An enhance dynamic framed slotted ALOHA algorithm for RFID tag identification[J].Mobile and Ubiquitous Systems:Networking and Services,MobiQuitous Jul.2005:166-172.

[8]尹君,何怡剛,李兵,鄧曉,譚陽紅,肖迎群.基于分組動態(tài)幀時隙的RFID防碰撞算法[J].計(jì)算機(jī)工程,2009,35(20):267-269.

[9]張學(xué)軍,王娟等,王鎖萍.基于標(biāo)簽識別碼分組的連續(xù)識別防碰撞算法研究[J].電子與信息學(xué)報.2011,(05).

[10]蘇恒陽,譚英麗.改進(jìn)的RFID動態(tài)幀時隙ALOHA算法[J].計(jì)算機(jī)仿真,2011,28(8):148-152.DOI:10.3969/j.issn.1006-9348.2011.08.036.