引言

無線射頻識(shí)別技術(shù)(Radio Frequency Identification, RF ID)是利用射頻信號(hào)和空間耦合(電感或電磁耦合)傳輸特性自動(dòng)識(shí)別目標(biāo)物體的技術(shù) 。RF ID系統(tǒng)一般由電子標(biāo)簽(應(yīng)答器, Tag)和閱讀器(讀頭, Reader)組成。閱讀器負(fù)責(zé)發(fā)送廣播并接收標(biāo)簽的標(biāo)識(shí)信息;標(biāo)簽收到廣播命令后將自身標(biāo)識(shí)信息發(fā)送給閱讀器。當(dāng)閱讀器識(shí)別區(qū)域內(nèi)存在兩個(gè)或者兩個(gè)以上的標(biāo)簽在同一時(shí)刻向閱讀器發(fā)送標(biāo)識(shí)信息時(shí),將產(chǎn)生沖突,解決沖突的方法稱為反碰撞算法。

對(duì)于反碰撞問題, EPCglobal組織提出了基于位的二叉樹算法和基于ALOHA的算法, ISO組織制定了自適應(yīng)協(xié)議和二叉樹搜索算法 , ISO 的自適應(yīng)協(xié)議和EPCglobal的基于ALOHA的算法非常相似。諸多學(xué)者對(duì)反碰撞問題做了深入探討:文獻(xiàn)[ 2, 9 ]通過調(diào)整最大閱讀時(shí)間間隔來降低因碰撞引起的錯(cuò)誤拒絕問題,未闡述具體反碰撞措施;文獻(xiàn)[ 4, 5 ]的機(jī)理是基于位的二叉樹算法,算法的實(shí)施需要閱讀器檢測(cè)數(shù)據(jù)碰撞比特位的準(zhǔn)確位置;文獻(xiàn)[ 10, 11 ]分別提出了不同的標(biāo)簽數(shù)目估計(jì)算法( TEM) ;文獻(xiàn)[ 12 ]運(yùn)用自適應(yīng)環(huán)協(xié)議解決碰撞問題,與文獻(xiàn)[ 11 ]有異曲同工之效,但文獻(xiàn)[ 11, 12 ]的反碰撞算法對(duì)于標(biāo)簽數(shù)目巨大,幀長度受限的情況無能為力;文獻(xiàn)[ 13 ]提出了改進(jìn)的動(dòng)態(tài)幀時(shí)隙ALOHA 算法EDFSA(Enhanced Dynamic Framed Slotted ALOHA)反碰撞算法,通過將標(biāo)簽分組來限制響應(yīng)標(biāo)簽數(shù)目,保證標(biāo)簽識(shí)別效率期望值在34. 6% ～36. 8%之間。本文提出散列樹形搜索反碰撞算法,該算法無需閱讀器檢測(cè)數(shù)據(jù)碰撞比特位的準(zhǔn)確位置,標(biāo)簽識(shí)別效率期望值突破了EDFSA算法36. 8%的界限,在識(shí)別大量標(biāo)簽時(shí),標(biāo)簽識(shí)別時(shí)間小于EDFSA算法所需時(shí)間。

1　動(dòng)態(tài)幀時(shí)隙ALOHA算法

動(dòng)態(tài)幀時(shí)隙ALOHA (Dynamic Framed Slotted ALOHA,DFSA)算法,將時(shí)間劃分成時(shí)間片(稱為時(shí)隙) ,閱讀器命令以及標(biāo)簽的數(shù)據(jù)發(fā)送必須在給定時(shí)隙內(nèi)完成。閱讀器發(fā)送命令后,等待一組時(shí)隙,接收來自標(biāo)簽的數(shù)據(jù)信息。這組時(shí)隙構(gòu)成一幀,時(shí)隙的個(gè)數(shù)稱為幀長度。標(biāo)簽收到閱讀器命令后,在幀長度范圍內(nèi),隨機(jī)選擇時(shí)隙發(fā)送數(shù)據(jù),這樣就出現(xiàn)了唯一時(shí)隙(只有一個(gè)標(biāo)簽選擇的時(shí)隙) 、碰撞時(shí)隙和空時(shí)隙。為減少標(biāo)簽碰撞,根據(jù)標(biāo)簽數(shù)目確定合適的幀長度是非常重要的。動(dòng)態(tài)改變幀長度有兩種簡(jiǎn)單方法 ,即門限值法和指數(shù)法。但它們對(duì)標(biāo)簽數(shù)目的估計(jì)比較粗略,算法靈敏度低。

改進(jìn)的動(dòng)態(tài)幀時(shí)隙ALOHA算法EDFSA有較好的標(biāo)簽數(shù)目估計(jì)算法。若用三元組< c0 c1 ck >表示一幀中空時(shí)隙數(shù)、唯一時(shí)隙數(shù)和碰撞時(shí)隙數(shù), L表示幀長度(下文中使用此符號(hào)將不再說明) ,目前EDFSA算法常采用下面三種估計(jì)標(biāo)簽數(shù)的方法:

1) 用公式2ck + c1 +ξ估計(jì)(ξ表示修正值);
2) 用碰撞比例ck /L 估計(jì) ;
3) 用2. 3922ck 估計(jì)。

EDFSA算法能根據(jù)標(biāo)簽數(shù)估計(jì)值動(dòng)態(tài)改變幀長度,當(dāng)標(biāo)簽數(shù)目超過系統(tǒng)允許的最大幀長度時(shí),采用分組策略,限制響應(yīng)標(biāo)簽數(shù)目, 保證標(biāo)簽識(shí)別效率期望值穩(wěn)定在34. 6% ～3618%之間。但是EDFSA算法的標(biāo)簽識(shí)別效率期望值沒有突破36. 8%的界限。為此,本文提出散列樹形搜索反碰撞算法,其標(biāo)簽識(shí)別效率期望值保持在36. 8%～1之間。

2　散列樹形搜索反碰撞算法

標(biāo)簽通過散列運(yùn)算選擇時(shí)隙,若散列溢出會(huì)造成多標(biāo)簽在同一時(shí)隙中碰撞,閱讀器選擇碰撞時(shí)隙的標(biāo)簽進(jìn)行遞歸搜索識(shí)別,直觀上標(biāo)簽識(shí)別軌跡呈n叉樹狀,為此,本文稱這種解決標(biāo)簽沖突的方法為散列樹形搜索反碰撞算法。

2. 1　算法遵循的原則
1) 時(shí)隙分配原則
散列樹形搜索反碰撞算法標(biāo)簽通過散列運(yùn)算選擇幀時(shí)隙,而不是隨機(jī)選擇時(shí)隙。散列運(yùn)算用于建立從標(biāo)簽關(guān)鍵碼到幀時(shí)隙的映射,這一過程由散列函數(shù)完成。一般情況下,散列函數(shù)是一個(gè)壓縮映射函數(shù)?？紤]到算法的實(shí)用性,本文選用式(1)所示的散列函數(shù)作為標(biāo)簽時(shí)隙分配原則。

hash ( key) = (õkey /w」) %L (1)

其中, key表示標(biāo)簽的關(guān)鍵碼, w 為閱讀器發(fā)送給標(biāo)簽的正整數(shù),為保證散列的效果,幀長度L一般取質(zhì)數(shù)。例如,若某標(biāo)簽的關(guān)鍵碼key為12345,閱讀器發(fā)送給標(biāo)簽的w、L值分別為59、19, 根據(jù)式(1) 得Hash ( key) 等于0, 那么關(guān)鍵碼為12345的標(biāo)簽選擇第0時(shí)隙發(fā)送數(shù)據(jù)。

2) 幀長度改變?cè)瓌t
動(dòng)態(tài)改變幀長度是保證反碰撞算法標(biāo)簽識(shí)別效率的典型措施,散列樹形搜索反碰撞算法根據(jù)碰撞率和搜索深度動(dòng)態(tài)改變幀長度。改變?cè)瓌t是:當(dāng)2. 3922ck大于當(dāng)前幀長度且不大于系統(tǒng)允許的最大幀長度時(shí), 下一幀的幀長度改變?yōu)榕c當(dāng)前幀長度的2倍最鄰近的質(zhì)數(shù),此時(shí),下一幀稱為當(dāng)前幀的擴(kuò)展幀,當(dāng)前幀是下一幀的原始幀;否則, 選擇當(dāng)前幀中一碰撞時(shí)隙,選取不大于當(dāng)前幀長度的質(zhì)數(shù)作為幀長度開始深度搜索,此時(shí)當(dāng)前幀稱為下一幀的父幀, 下一幀稱為當(dāng)前幀的子幀。

3) 散列參數(shù)選擇原則
散列溢出會(huì)造成標(biāo)簽碰撞。例如,閱讀器識(shí)別域內(nèi)有兩個(gè)標(biāo)簽關(guān)鍵碼分別為key1 = 54321, key2 = 54380,當(dāng)w = 1, L =59時(shí),由式(1) 得, hash ( key1) = hash ( key2) = 41,即兩標(biāo)簽同時(shí)在第41時(shí)隙發(fā)送數(shù)據(jù),碰撞由此產(chǎn)生。散列樹形搜索反碰撞算法通過遞歸搜索碰撞時(shí)隙, 識(shí)別出發(fā)生碰撞的所有標(biāo)簽。遞歸搜索時(shí), 必須適當(dāng)改變散列參數(shù),使父幀映射到同一時(shí)隙的標(biāo)簽盡可能映射到子幀的不同時(shí)隙。分析碰撞標(biāo)簽關(guān)鍵碼的特點(diǎn),會(huì)發(fā)現(xiàn)上面例子中兩個(gè)標(biāo)簽的關(guān)鍵碼可分別表示為: key1 = 54321 = 920 ×59 + 41, key2 =54380 = 921 ×59 + 41。

顯然, key1、key2最大差異在于它們包含不同個(gè)數(shù)的59, 所以, 要將兩個(gè)標(biāo)簽分配到不同時(shí)隙,只需在子幀中令w = 59, L = 19, 進(jìn)行散列運(yùn)算, 即得
hash ( key1) = 8, hash ( key2) = 9,這樣在子幀中,兩標(biāo)簽會(huì)在不同時(shí)隙發(fā)送數(shù)據(jù),避免了再次沖突。

由此啟示得出散列運(yùn)算參數(shù)w 的改變?cè)瓌t是:子幀的w值是父幀w與L的乘積。另外,值得說明的是,運(yùn)用式(1) 所示的散列函數(shù)進(jìn)行遞歸搜索時(shí),能夠區(qū)分出所有碰撞標(biāo)簽,即能保證遞歸返回。這是因?yàn)樗惴ǖ臉O限情況為w、L 都等于2,此時(shí)相當(dāng)于比較兩個(gè)關(guān)鍵碼的每一位, 不相等的兩個(gè)數(shù)至少有一位不等,故散列深度搜索可以識(shí)別出所有標(biāo)簽。

2. 2　算法描述
(1) 閱讀器和標(biāo)簽交互過程
閱讀器向標(biāo)簽發(fā)送命令字,標(biāo)簽根據(jù)命令字,決定是否響應(yīng)及在何時(shí)隙響應(yīng)閱讀器命令。閱讀器收到標(biāo)簽響應(yīng)后,向標(biāo)簽發(fā)送確認(rèn),標(biāo)簽收到確認(rèn)后,進(jìn)入休眠狀態(tài),稱為已讀標(biāo)簽。

(2) 重要數(shù)據(jù)結(jié)構(gòu)
標(biāo)簽自身變量: ftag 和stag 分別表示幀號(hào)和時(shí)隙號(hào), 用于匹配閱讀器命令的相應(yīng)域,決定是否響應(yīng)閱讀器命令。初始狀態(tài)為ftag = stag = - 1。閱讀器命令字Comm and (w, L, f, s) :其中f、s用作標(biāo)簽選擇,分別表示幀號(hào)、時(shí)隙號(hào)。若s等于- 1, 選取新進(jìn)入閱讀器識(shí)別區(qū)域的標(biāo)簽和ftag 等于f的所有未讀標(biāo)簽響應(yīng)。s大于- 1時(shí), 僅選取于ftag等于f且stag等于s的未讀標(biāo)簽。w、L用作被選標(biāo)簽散列運(yùn)算的參數(shù),確定響應(yīng)時(shí)隙。

二維表Table[N um W FL en S qu Flag ]:閱讀器用該表以幀為單位記錄標(biāo)簽識(shí)別軌跡。其中, N um 列表示幀號(hào),W 列表示該幀標(biāo)簽散列運(yùn)算時(shí)的w值, FL en列表示幀長度, S qu列是該幀的碰撞時(shí)隙隊(duì)列, Flag列標(biāo)識(shí)該幀是否為下一幀的原始幀(1:是, 0:非) 。

(3)算法描述
散列樹形搜索是應(yīng)用于RF ID系統(tǒng)的反碰撞算法,算法的實(shí)施依賴于閱讀器和標(biāo)簽。因此下面分兩部分描述算法的詳細(xì)流程。表1給出了算法描述中所用符號(hào)的含義。

閱讀器算法流程如下:
步驟1: L = 59, w = 1, f = 0, s = - 1;
步驟2: Comm and (w, L, f, s) ; squ = Generate_queue ( ) ;Add_recorder( f, w, L, squ, 0) ;
步驟3: if ( ! ck ) { delete ( f) ; f - - ; goto步驟7; } else goto步驟4;
步驟4: if (2. 3922ck > = L ) goto步驟5; else goto 步驟6;
步驟5: if ( prim e (23 L) > LMAX ) goto 步驟6;
else {L = prim e (23 L) ; s = - 1; w = 1; SetFlag ( f) ; f ++;Comm and (w, L, f, s) ; squ = Genera te_queue ( ) ;A dd_recorder( f, w, L, squ, 0) ;} goto 步驟3;
步驟6:
if (L en ( f) > 5) L = 5; else L = L ittle (Len ( f) ) ;
s = S lot ( f) ; w = Len ( f) 3 W eigh t ( f) ; f ++;
Comm and (w, L, f, s) ; squ = Generate_queue ( ) ;
Add_recorder( f, w, L, squ, 0) ;goto步驟3;
步驟7: if ( Flag ( f) ) { delete ( f) ; f - - ; goto 步驟9; } else goto 步驟8;
步驟8: deleteS lot ( f) ; if ( S lot ( f) = = - 1) { delete ( f) ; f - - ; goto步驟9; } else goto 步驟6;
步驟9: if ( f < 0) 算法結(jié)束; else goto步驟7;

標(biāo)簽算法流程如下:
步驟1: ftag = stag = - 1;
步驟2:接收命令(w, L, f, s) ;
步驟3: if ( s = = - 1) { 根據(jù)式(1) 計(jì)算stag; 在第stag時(shí)隙發(fā)送數(shù)據(jù); }else { if ( f = =ftag ) {根據(jù)式(1) 計(jì)算stag; 在第stag時(shí)隙發(fā)送數(shù)據(jù); } }
步驟4: if (收到閱讀器確認(rèn)) {不再響應(yīng)同一閱讀器的請(qǐng)求; 算法結(jié)束; }else { ftag ++; goto步驟2; }

3　算法性能分析與比較

3. 1　算法復(fù)雜度分析
散列樹形搜索反碰撞算法運(yùn)用散列運(yùn)算將標(biāo)簽分組,減少碰撞,通過遞歸深度搜索識(shí)別碰撞標(biāo)簽。如用T ( n表示識(shí)別n個(gè)標(biāo)簽的時(shí)間復(fù)雜度, i表示分組數(shù), j表示每組的標(biāo)簽個(gè)數(shù),則可列出時(shí)間復(fù)雜度的遞歸方程,如公式(2) 所示:



本算法的最壞情況是:遞歸深度搜索標(biāo)簽時(shí), 碰撞頻繁,導(dǎo)致幀長度L為2, w為2的x次冪,也即該算法的特例———二叉樹搜索反碰撞算法。此時(shí)i = j = 2, 由(3) 得, T ( n) =O ( n) 。

算法的空間復(fù)雜度取決于搜索深度, 最壞情況仍然是二叉樹狀搜索,搜索深度約為log2 n + 1。所以, 散列樹形搜索反碰撞算法的空間復(fù)雜度S ( n) = O ( log2 n) 。

3. 2　識(shí)別效率分析比較
本節(jié)采用文獻(xiàn)[ 13 ]的算法性能評(píng)價(jià)標(biāo)準(zhǔn),定義標(biāo)簽識(shí)別效率,如表達(dá)式(4) 所示。一般認(rèn)為在唯一時(shí)隙可以正確識(shí)別標(biāo)簽,因此唯一時(shí)隙數(shù)在幀中的比例能夠體現(xiàn)系統(tǒng)的時(shí)隙有效利用率,用其作為標(biāo)簽識(shí)別效率的衡量標(biāo)準(zhǔn)是合理的。

α =c1/L×100%                    (4)
下面用n表示出現(xiàn)在閱讀器識(shí)別域內(nèi)的實(shí)際標(biāo)簽數(shù)目, m表示整個(gè)標(biāo)簽關(guān)鍵碼空間, pk 表示同一時(shí)隙被k個(gè)標(biāo)簽占有的概率, ak 表示被k個(gè)標(biāo)簽占有的時(shí)隙數(shù)的期望值。在概率論中可以用a1 估計(jì)c1 ,于是系統(tǒng)效率期望值η可用(5) 表示。

η = E (α) =a1/L×100%                   (5)

EDFSA算法運(yùn)用幀長度L和標(biāo)簽數(shù)n趨于相等時(shí),系統(tǒng)有最大識(shí)別效率36. 8% 這一原理[13 ] , 通過估計(jì)標(biāo)簽數(shù)目來確定幀長度,使得幀長度和標(biāo)簽數(shù)趨于相等,當(dāng)估計(jì)標(biāo)簽數(shù)超過最大幀長度時(shí), 以分組的方式, 限制響應(yīng)標(biāo)簽數(shù), 保證幀長度與響應(yīng)標(biāo)簽數(shù)趨于相等,使標(biāo)簽識(shí)別效率穩(wěn)定在34. 6% ～36. 8% 之間。

散列樹形搜索反碰撞算法, 運(yùn)用散列方法將標(biāo)簽映射到幀時(shí)隙內(nèi),第一幀w為1,相當(dāng)于將標(biāo)簽關(guān)鍵碼空間分為L組,每組有m /L個(gè)標(biāo)簽(最后一組可能少一些) 。k個(gè)標(biāo)簽占有同一時(shí)隙的情況是由于m /L個(gè)標(biāo)簽中有k個(gè)標(biāo)簽隨機(jī)出現(xiàn)在閱讀器識(shí)別區(qū)域內(nèi)而產(chǎn)生的, 因此, 散列樹形搜索反碰撞算法中,第一幀pk 表達(dá)式為式(6) 。當(dāng)然, 如散列樹形搜索反碰撞算法所描述的那樣,以后的各幀關(guān)鍵碼空間將不斷縮小,其效率問題可從討論第一幀效率函數(shù)特性而得到。



下面討論散列樹形搜索反碰撞算法第一幀的單調(diào)性、極值問題,式(7) 求導(dǎo)得:



式(9) 說明η是r的單調(diào)遞增函數(shù);式(10) 則表明,當(dāng)r趨近于0時(shí),η有最小極限值36. 8%。也就是說, 當(dāng)幀長度遠(yuǎn)小于標(biāo)簽關(guān)鍵碼空間時(shí), 識(shí)別效率期望值為36. 8% , 隨著幀長度與標(biāo)簽關(guān)鍵碼空間的比例增大,識(shí)別效率隨之增加。下面論證空時(shí)隙概率與r的關(guān)系。

由(6) 式得: p0 = (1 - L /m ) m /L = (1 - r) 1 / r。

p0 單調(diào)性和極值證明:




所以, p0 是r的單調(diào)遞減函數(shù),當(dāng)r趨近于0時(shí), p0 趨近于0. 368。也就是說,當(dāng)幀長度遠(yuǎn)小于標(biāo)簽關(guān)鍵碼空間時(shí),空時(shí)隙有最大概率0. 368,隨著幀長度與標(biāo)簽關(guān)鍵碼空間的比例增大,空時(shí)隙概率下降。

假設(shè)第二幀是對(duì)碰撞時(shí)隙的深度搜索, 不是第一幀的擴(kuò)展幀,那么按照算法流程,第二幀的w值應(yīng)等于第一幀的幀長度L,幀長度設(shè)為L ′,于是pk ,η表達(dá)式如(11) (12) :



顯然LL ′/m>L/m, 前面已經(jīng)證明所以η是r的單調(diào)遞增函數(shù),所以第二周期的識(shí)別效率要高于第一周期的識(shí)別效率。同理,如算法流程中描述的那樣, 隨著幀號(hào)的增大, 標(biāo)簽識(shí)別效率期望值逐步提高。

3. 3　識(shí)別時(shí)間仿真比較
根據(jù)EDFSA算法和散列樹形搜索反碰撞算法的基本思想,編寫了仿真程序。在仿真環(huán)境下, EDFSA初始幀長度為10,兩算法最大幀長度為256時(shí),系統(tǒng)識(shí)別總時(shí)間隨著標(biāo)簽數(shù)目的變化情況如圖1所示。當(dāng)標(biāo)簽數(shù)目小于60時(shí), EDFSA算法總體識(shí)別時(shí)間小于散列樹形搜索反碰撞算法的總體識(shí)別時(shí)間,這是因?yàn)樯⒘袠湫嗡阉鞣磁鲎菜惴ǔ跏紟L度為59,標(biāo)簽數(shù)小于59時(shí),可能浪費(fèi)時(shí)隙。當(dāng)標(biāo)簽數(shù)目大于60時(shí),兩種算法的系統(tǒng)總體識(shí)別時(shí)間與標(biāo)簽數(shù)目呈線性關(guān)系。這說明兩種算法在標(biāo)簽數(shù)目大于最大幀長度時(shí),都有分組標(biāo)簽的作用,限制了響應(yīng)標(biāo)簽數(shù),使識(shí)別時(shí)間與標(biāo)簽數(shù)目保持線性關(guān)系。但兩條曲線的斜率不同,在標(biāo)簽數(shù)目較多時(shí),散列樹形搜索反碰撞算法優(yōu)于EDFSA算法,這是因?yàn)樯⒘袠湫嗡阉鞣磁鲎菜惴ㄓ休^高的識(shí)別效率。



圖1　識(shí)別時(shí)間t與標(biāo)簽數(shù)目n的關(guān)系

4　結(jié)語

本文在分析DFSA、EDFSA等目前流行的RF ID系統(tǒng)反碰撞算法優(yōu)劣的基礎(chǔ)上,針對(duì)EDFSA算法識(shí)別效率期望值不能突破36. 8%、基于位的二叉樹搜索算法要求閱讀器檢測(cè)碰撞數(shù)據(jù)比特位的準(zhǔn)確位置等不足,提出了散列樹形搜索反碰撞算法。該算法運(yùn)用散列運(yùn)算為標(biāo)簽分配時(shí)隙,通過樹形深度搜索解決碰撞,提高了標(biāo)簽識(shí)別效率。文中闡述了算法遵循的三原則,設(shè)計(jì)了算法的詳細(xì)流程。通過建立并分析標(biāo)簽識(shí)別效率的評(píng)價(jià)模型,證明了散列樹形搜索反碰撞算法標(biāo)簽識(shí)別效率期望值在36. 8%～1之間,優(yōu)于EDFSA算法34. 6%～36. 8%的系統(tǒng)識(shí)別效率期望值。仿真驗(yàn)證表明,當(dāng)標(biāo)簽數(shù)目大于60時(shí),該算法的標(biāo)簽識(shí)別總時(shí)間比EDFSA算法的少,特別是在標(biāo)簽數(shù)目很大時(shí),該算法表現(xiàn)出明顯優(yōu)勢(shì)。另外,散列樹形搜索反碰撞算法不需要閱讀器檢測(cè)碰撞數(shù)據(jù)比特位的準(zhǔn)確位置,簡(jiǎn)化了RF ID系統(tǒng)的軟件設(shè)計(jì)。散列樹形搜索反碰撞算法突破了傳統(tǒng)ALOHA反碰撞算法標(biāo)簽識(shí)別效率期望值36. 8%的界限,在標(biāo)簽數(shù)目很大的場(chǎng)合,算法性能表現(xiàn)良好。該算法對(duì)解決反碰撞問題有理論意義,也勢(shì)必推動(dòng)RF ID系統(tǒng)在礦山跟蹤系統(tǒng)、汽車監(jiān)控、電子支付等領(lǐng)域的應(yīng)用。