引言

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

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

1　動態幀時隙ALOHA算法

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

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

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

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

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

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

2. 1　算法遵循的原則
1) 時隙分配原則
散列樹形搜索反碰撞算法標簽通過散列運算選擇幀時隙,而不是隨機選擇時隙。散列運算用于建立從標簽關鍵碼到幀時隙的映射,這一過程由散列函數完成。一般情況下,散列函數是一個壓縮映射函數。考慮到算法的實用性,本文選用式(1)所示的散列函數作為標簽時隙分配原則。

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

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

2) 幀長度改變原則
動態改變幀長度是保證反碰撞算法標簽識別效率的典型措施,散列樹形搜索反碰撞算法根據碰撞率和搜索深度動態改變幀長度。改變原則是:當2. 3922ck大于當前幀長度且不大于系統允許的最大幀長度時, 下一幀的幀長度改變為與當前幀長度的2倍最鄰近的質數,此時,下一幀稱為當前幀的擴展幀,當前幀是下一幀的原始幀;否則, 選擇當前幀中一碰撞時隙,選取不大于當前幀長度的質數作為幀長度開始深度搜索,此時當前幀稱為下一幀的父幀, 下一幀稱為當前幀的子幀。

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

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

由此啟示得出散列運算參數w 的改變原則是:子幀的w值是父幀w與L的乘積。另外,值得說明的是,運用式(1) 所示的散列函數進行遞歸搜索時,能夠區分出所有碰撞標簽,即能保證遞歸返回。這是因為算法的極限情況為w、L 都等于2,此時相當于比較兩個關鍵碼的每一位, 不相等的兩個數至少有一位不等,故散列深度搜索可以識別出所有標簽。

2. 2　算法描述
(1) 閱讀器和標簽交互過程
閱讀器向標簽發送命令字,標簽根據命令字,決定是否響應及在何時隙響應閱讀器命令。閱讀器收到標簽響應后,向標簽發送確認,標簽收到確認后,進入休眠狀態,稱為已讀標簽。

(2) 重要數據結構
標簽自身變量: ftag 和stag 分別表示幀號和時隙號, 用于匹配閱讀器命令的相應域,決定是否響應閱讀器命令。初始狀態為ftag = stag = - 1。閱讀器命令字Comm and (w, L, f, s) :其中f、s用作標簽選擇,分別表示幀號、時隙號。若s等于- 1, 選取新進入閱讀器識別區域的標簽和ftag 等于f的所有未讀標簽響應。s大于- 1時, 僅選取于ftag等于f且stag等于s的未讀標簽。w、L用作被選標簽散列運算的參數,確定響應時隙。

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

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

閱讀器算法流程如下:
步驟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) 算法結束; else goto步驟7;

標簽算法流程如下:
步驟1: ftag = stag = - 1;
步驟2:接收命令(w, L, f, s) ;
步驟3: if ( s = = - 1) { 根據式(1) 計算stag; 在第stag時隙發送數據; }else { if ( f = =ftag ) {根據式(1) 計算stag; 在第stag時隙發送數據; } }
步驟4: if (收到閱讀器確認) {不再響應同一閱讀器的請求; 算法結束; }else { ftag ++; goto步驟2; }

3　算法性能分析與比較

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



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

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

3. 2　識別效率分析比較
本節采用文獻[ 13 ]的算法性能評價標準,定義標簽識別效率,如表達式(4) 所示。一般認為在唯一時隙可以正確識別標簽,因此唯一時隙數在幀中的比例能夠體現系統的時隙有效利用率,用其作為標簽識別效率的衡量標準是合理的。

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

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

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

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



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



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

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

p0 單調性和極值證明:




所以, p0 是r的單調遞減函數,當r趨近于0時, p0 趨近于0. 368。也就是說,當幀長度遠小于標簽關鍵碼空間時,空時隙有最大概率0. 368,隨著幀長度與標簽關鍵碼空間的比例增大,空時隙概率下降。

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



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

3. 3　識別時間仿真比較
根據EDFSA算法和散列樹形搜索反碰撞算法的基本思想,編寫了仿真程序。在仿真環境下, EDFSA初始幀長度為10,兩算法最大幀長度為256時,系統識別總時間隨著標簽數目的變化情況如圖1所示。當標簽數目小于60時, EDFSA算法總體識別時間小于散列樹形搜索反碰撞算法的總體識別時間,這是因為散列樹形搜索反碰撞算法初始幀長度為59,標簽數小于59時,可能浪費時隙。當標簽數目大于60時,兩種算法的系統總體識別時間與標簽數目呈線性關系。這說明兩種算法在標簽數目大于最大幀長度時,都有分組標簽的作用,限制了響應標簽數,使識別時間與標簽數目保持線性關系。但兩條曲線的斜率不同,在標簽數目較多時,散列樹形搜索反碰撞算法優于EDFSA算法,這是因為散列樹形搜索反碰撞算法有較高的識別效率。



圖1　識別時間t與標簽數目n的關系

4　結語

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