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

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

(江蘇財經職業(yè)技術學院 計算機技術與藝術設計系，淮安 223003)

0 引言

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

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

1 ALOHA防碰撞算法分析研究

1.1 經典ALOHA算法

圖1 經典ALOHA算法模擬圖

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

1.2 時隙ALOHA算法

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

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

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

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

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

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

2.1 算法的基本思想

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

圖2 標簽分組機制

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

2.2 最佳幀長度

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

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

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

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

對式（4）求導：

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

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

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

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

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

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

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

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

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

3 仿真分析研究

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

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

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

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

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

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

圖5 兩種算法吞吐率比較

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

4 結論

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

[1]周曉光,王曉華,王偉.射頻識別（RFID）系統(tǒ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].計算機工程,2009,35(20):267-269.

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

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