基于動態(tài)位隙分組盲分離的UHF RFID防碰撞算法

栗華，賈智平，王洪君，劉琚,3

（1. 山東大學 計算機科學與技術學院，山東 濟南 250100; 2. 山東大學 信息科學與工程學院，山東 濟南 250100；3. 西安電子科技大學 綜合業(yè)務網理論及關鍵技術國家重點實驗室，陜西 西安 710071）

1 引言

在標簽密集的RFID應用系統(tǒng)中，一個閱讀器的作用范圍內常常同時存在 2個或 2個以上的標簽。此時，閱讀器所發(fā)出的查詢命令往往會引起多個標簽的同時響應。這些響應信號混疊在一起，就會使標簽響應信號難以被閱讀器辨識，從而引起多標簽沖突(multi-tags collision)[1]。閱讀器為完成對所有標簽信息的閱讀，應將這些沖突的標簽逐個區(qū)分開來，然后再和它們逐個通信。閱讀器完成這類工作所使用的算法就是多標簽防碰撞算法（multi-tags anti-collision algorithms）。RFID防碰撞算法的標簽識別率（即：閱讀器每次閱讀操作可以成功讀取的標簽數，有時也稱為防碰撞算法的算法效率）與閱讀器的標簽吞吐率（閱讀器在單位時間內可以成功讀取的標簽數）密切相關，也與整個RFID應用系統(tǒng)的工作效率密切相關。

目前，常用的UHF RFID標簽防碰撞算法有2類，一類是基于Aloha技術的隨機性防碰撞算法，另一類是基于二進制樹搜索技術的確定性防碰撞算法。前者要求標簽在發(fā)生碰撞后重新隨機選擇發(fā)送時隙，后者將標簽進行樹形分類，逐步縮小響應標簽群的范圍。這2類防碰撞算法的目的都是縮小標簽響應范圍，最終使同一個時刻只有一個標簽對閱讀器的查詢命令做出響應。為此，閱讀器和標簽之間需要多次協(xié)調通信，從而使得單標簽識別時間加長，閱讀器的標簽識別率降低。如動態(tài)幀時隙Aloha算法的最大標簽識別率僅為 42.6%[2]，二進制樹回退算法的最大標簽識別率也低于 50%[2,3]。因此，若想進一步提高閱讀器的標簽識別率，必須采用新機制的防碰撞算法。

盲源分離(BSS, blind source separation)是20世紀80年代發(fā)展起來，并于21世紀流行起來的一種信號處理技術。盲源分離技術不利用任何訓練數據，也沒有許多先驗知識，只是基于源信號的某些最基本的統(tǒng)計特征（如統(tǒng)計獨立性），便可將源信號進行盲分離。這項技術已被廣泛應用于生物醫(yī)學工程、語音增強、遙感、雷達與通信系統(tǒng)等領域。

獨立分量分析(ICA)[4]是一種常用的盲源分離方法。這種盲源分離技術利用了多源信號之間的統(tǒng)計獨立性，并且是基于2個不確定性（即源信號排列順序的不確定性與源信號幅值和極性的不確定性）假設進行的。

由于多個 RFID標簽的反射數據間具有統(tǒng)計獨立性，符合ICA算法的源信號獨立性要求；標簽信號具有超高斯分布特性，符合ICA算法的源信號非高斯特性要求[5]；另外，由RFID編碼技術可知，其反向鏈路的 FM0編碼[6,7]標簽數據由碼元期間信號電平的相對變化情況來決定，而對于信號的符號是不敏感的。Miller編碼[6,7]與之類似，即標簽信號滿足ICA算法的信號幅值不確定性要求；而標簽識別的目標就是將各個標簽信號能夠正確無誤地識別出來，至于標簽識別的順序無關緊要，這就滿足了ICA算法的信號順序不確定性要求。由此可見，利用ICA技術將多天線閱讀器所接收的觀測信號進行盲處理，從而分離出各標簽信號，從理論上是可行的。

另外，利用快速ICA（fast ICA）算法對多標簽隨機混合數據進行了盲分離，具有運算量低，運算速度快，便于硬件實現等優(yōu)點使其特別適合于多標簽數據的盲分離。

本文首先分析了UHF RFID多天線系統(tǒng)的系統(tǒng)模型，據此分析了基于 TDMA技術的多標簽混合數據之間的盲分離可行性。在此基礎上，提出了基于位隙動態(tài)分組的盲分離（BSDBG, blind separation and dynamic bit-slot grouping）多標簽防碰撞算法。文中分析了該算法的基本原理、算法性能以及算法性能與天線個數的關系等內容。理論分析和仿真實驗證明該算法的標簽識別率可超過 1，遠遠超過了傳統(tǒng)隨機性和確定性的TDMA RFID防碰撞算法的標簽識別率。

2 UHF RFID多天線系統(tǒng)模型及多標簽混合數據可分離性分析

多天線 RFID系統(tǒng)中的閱讀器具有多天線結構，其系統(tǒng)模型如圖1所示。

圖1 多天線UHF RFID系統(tǒng)模型

閱讀器的多個天線會同時輻射載波信號，標簽從這些載波信號接收電磁能量為其自身供電，同時標簽對這些載波信號進行反向散射調制，以實現信號的反向傳遞。

假設在閱讀器作用范圍內存在N個標簽sT1,sT2,…,sTN，閱讀器具有M個天線，接收到M個混合信號x1,x2,…,xM，經過閱讀器盲分離處理后的輸出信號為1y,2y,…,Ny。

這里假定js具有單位功率（實際標簽反射功率的不一致可以歸結到式中衰減系數ija里面去），ija就是綜合考慮了各種因素的閱讀器接收功率的衰減因子。

當線性混合系統(tǒng)中的n個源信號s1,s2,… ,sn之間具有統(tǒng)計獨立性時，盲源分離技術可以簡化為ICA技術。為求解ICA問題，一般需要滿足如下幾個假設條件[8]。

1) 各個源信號s1,s2,… ,sn都是零均值的實值隨機信號，并且在任意時刻這些信號之間都是相互統(tǒng)計獨立的。

2) 源信號數目n和觀測信號數目m相等，混合矩陣A為n階未知方陣，且滿秩。

3) 不允許有2個以上的源信號是高斯信號，否則源信號不可分。這是由于2個以上的統(tǒng)計獨立性高斯信號的混合信號仍然是高斯信號，無法對其進行唯一性分解。

4) 各觀測信號引入的噪聲很小，甚至可以忽略不計。對于噪聲較大的情況，可以將噪聲也視為一個信號源，并將它與其他信號源分離開來。

5) 求解 ICA時，需要對各源信號的概率分布有一些基本的先驗知識，比如各源信號的概率分布具有超高斯分布特性（如拉普拉斯分布）或者亞高斯分布特性（如均勻分布）。

當式（3）中，M＞N時，A為列滿秩的，這時稱盲源分離為超定的。當M＜N時，A為行滿秩的，這時稱盲源分離為欠定的。當MN= 時，A為滿秩方陣，這時稱盲源分離為正定的。正定盲源分離具有唯一解，超定盲源分離多個觀測信號之間往往具有非獨立性，利用主成分分析（PCA, principal component analysis）技術，使混合矩陣變?yōu)榉疥嚭螅梢郧蟪龉烙嬓盘柕奈ㄒ唤?。而對于欠定盲源分離則不具備唯一解，欲求得確定性解，需要其他約束條件，實現起來比較困難。為使用ICA，應使多標簽信號為超定或者正定的。

為滿足多標簽混合信號的超定或正定盲分離要求，閱讀器天線的個數應該大于或者等于需要同時讀取的標簽的個數。在標簽密集的應用環(huán)境里，在閱讀器作用范圍之內，同時存在的標簽數目可能很多（如零售行業(yè)，常常多余10個）。而受成本的制約，閱讀器天線的個數不可能很多（一般情況下應少于8個）。為保證同時響應的標簽數目少于天線的數目，可利用位隙分組算法對標簽進行分組，通過選擇合適的組數，使得每個組內的標簽個數不多于天線個數，再用盲源分離技術對混合信號進行盲分離。

3 基于位隙動態(tài)分組的盲分離 UHF RFID多標簽防碰撞算法描述

C. S. Kim等[9]提出了一種利用位隙（bit-slot）來對標簽進行分組，實現標簽防碰撞的算法。該算法的基本思想就是在標簽收到閱讀器的盤存命令后，令一個128bit的二進制數任意一比特（隨機選擇）為 1，而其他的比特為 0，在回答閱讀器的提問時，標簽將這個128bit的二進制數回答出來，閱讀器可以根據這個128bit的數哪一比特是1，來實現標簽的分組，如圖2所示。

圖2 位隙算法工作原理

需要特別說明的是位隙信息0的載波調制方法與普通標簽識別碼ID及其他信息0的載波調制方法是不同的。對于位隙信息中的0比特，標簽不對載波進行任何調制。這樣做的目的是防止各標簽發(fā)送位隙信息時引起0和1的沖突，造成閱讀器無法完成對位隙信息中為1的比特的識別。

位隙信息和 ID信息調制方法的對比如圖 3所示。

圖3 位隙信息調制方法

位隙分組追求的目標是在閱讀器天線數量和標簽數量確定的情況下選擇一個合適的組數。所謂的合適分組數就是采用該分組數進行分組后能夠使每個分組內標簽的個數剛剛小于或者等于天線數M，剛剛能夠滿足 ICA算法的正定或者超定要求。如果少于該分組數，則分組后的標簽混合數據無法滿足正定或超定要求，如果多于該分組數，則每次同時識別的標簽數又太少，算法整體效率將有所降低。同時，分組的最終目的是為了正確地分離出數據，至少使得分離出的數據符合編碼要求，進而能夠識別出每一比特是0還是1。為此，這里采用2次判定決定合適的分組數。將標簽混合數據是否滿足正定或超定性要求為第一次判定，判定的方法就是查看觀測數據陣列的秩（低噪聲工作環(huán)境）或者觀測數據相關矩陣（較強噪聲工作環(huán)境）的主特征值數是否小于或者等于天線數量（小于為超定，等于為正定）。以分離結果是否清晰可讀（即分離信號是否符合 FM0編碼規(guī)則）為二次判定。只有同時滿足這2次判定，但分組數又比較小的情況下，該分組數才是合適的分組數。

整個算法的步驟如下。

1) 當標簽進入閱讀器的工作范圍時，閱讀器將開始位隙序列（SSNB, start serial number of bitslot）長度初始化為1。

2) 閱讀器發(fā)出一個 Query (SSNB)。所有的標簽在收到該命令后，根據SSNB的大小確定自己的響應位隙（RSNB, response serial number of bit-slot）長度，并隨機選擇1bit為1，其他比特都是0。然后對該命令作出響應，將它們的標簽RSNB傳送回閱讀器。閱讀器檢查所收到的標簽返回位隙值RSNB。

3) 如果接收的RSNB所有比特都為0，則說明已沒有標簽存在，轉 8)結束。否則，令查詢 SNB（QSNB, query serial number of bitslot）為零，找到接收RSNB中為1的最低比特，讓QSNB對應的位為1，其他比特保持為0，形成本組的查詢QSNB。并將RSNB中這個為1的最低比特清0。

4) 閱讀器發(fā)出一個位隙盤存命令 QueryRepB(QSNB)，所有標簽在收到該命令后將自己的RSNB與QSNB進行比較，若其RSNB等于QSNB則對閱讀器的盤存命令作出響應，將它們的 16bit隨機數RN16或者32bit隨機數RN32傳送回閱讀器。如果閱讀器沒有收到標簽響應信號，說明本組內已沒有標簽需要讀取，轉3)。否則，繼續(xù)。

5) 閱讀器檢查觀測信號X的秩或者其相關矩陣的主特征值數是否小于閱讀器天線數量M，如果小于M，說明符合初步判定要求，進而利用FastICA算法對觀測信號X進行解混合，查看每個分離信號是否清晰可辨，如果清晰可辨，則滿足二次判定標準，計算出本組的分離矩陣W，轉步驟7)。如果初步判定標準或者二次判定標準不滿足，則說明分組數量太少ICA無法正確將數據分離，繼續(xù)執(zhí)行步驟6)。

6) 閱讀器將盤存開始位隙序列長度 SSNB乘2，轉步驟2)。

7) 閱讀器發(fā)出讀本組命令Read(QSNB)，本組內標簽繼續(xù)發(fā)送自己的PC+EPC+CRC16信息，閱讀器利用本組分離矩陣W繼續(xù)分離所接收的信息，檢查無誤后，存儲這些標簽的信息，并將成功讀取的標簽除掉，轉步驟4)。

8) 結束。

4 BSDBG算法性能分析與驗證

設標簽個數為n，閱讀器天線個數為M，分組數SG，系統(tǒng)工作環(huán)境符合ICA算法信噪比要求，那么通過位隙分組后，通過動態(tài)探索盡量使每個組內的標簽個數小于等于M。

為達到這一最佳分組，需要分組探索的次數為

其中，ceil( . )表示向上取整，如ceil( 0 .4)= 1 ，ceil( 1 .6) = 2 。

分組數的調整是以乘2方式進行的，因此計算分組搜索次數的式(4)中存在lb(ceil(n/M) )項。

標簽位隙分組數為

通過位隙分組后一個組內沒有任何標簽的概率為

一個組內有一個或者多個標簽選擇的概率為

具有單個或者多個標簽的組的個數為

分離這些標簽數據所需要的查詢次數為

總的查詢次數為

算法標簽識別率（即算法效率）為

假定標簽數n=1～256，閱讀器天線數為M= 4 ,分組數Gs、總查詢次數S(n)以及算法標簽識別率E(n)隨標簽數n變化的規(guī)律如圖4～圖6所示。

圖4M=4時標簽分組數GS隨標簽數量n的變化情況

通過圖4可以看出分組數是階躍變化的，這是由于算法為了加快搜索最佳分組數，分組數是采用逐次加倍的方式來變換的，這也就導致了圖6中算法標簽識別率的階躍性變化。

圖5表示隨著標簽數的增加，總的查詢時間是增加的，但是增加的速度并不快，甚至比標簽自身增加的速率還要低，這也正解釋了圖6中大部分情況下（總標簽數遠低于天線數時除外）算法的標簽識別率都大于1。

本算法和傳統(tǒng)隨機性 DFSA防碰撞算法以及BTS算法效率的比較如圖7所示。

圖5M=4時總查詢次數S(n)隨標簽數量n的變化情況

圖6M=4時算法標簽識別率E(n)隨標簽數量n的變化情況

圖7 BSDBG算法與DFSA和BTS算法標簽識別率比較

由圖7可見，本文所提出的BSDBG算法效率遠高于傳統(tǒng)的隨機性算法DFSA和確定性算法BTS的算法效率。在天線數 4M= 時，BSDBG算法效率的平均值和最大值為

下面調整天線數M，使其從2逐漸變到32，標簽數n仍然為1～512，算法平均效率隨天線數M變化情況如圖8和表1所示。

圖8 算法平均標簽識別率隨天線數量M的變化情況

表1 算法平均效率隨天線數量M的變化情況

由表1和圖8可見，隨著天線數量的增加，算法平均效率基本上是按線性增加的，但增加的速率沒有天線數量增加的速率大。

當某個分組的標簽個數多于M，使得ICA算法無法將多個信源分開時，算法會自動增加SG使其加倍，然后重新進行分組。

下面分析標簽數n及天線數M對動態(tài)分組準確度的影響。

一個組內具有多于M個標簽的概率為

當標簽數n較大時Cn

i的計算比較費時，并且精度難以保證，可以采用遞歸方法來實現。

設：

那么：

或者：

下面分析povernM隨n和M變化的規(guī)律。設標簽數n仍然為1～512，povernM隨標簽數n變化的規(guī)律如圖9（天線數M= 4 ）和圖10（天線數M= 8 ）所示。

圖9M=4時，組內多于M個標簽的概率隨標簽數量變化的情況

由圖9和圖10可見，由于采用動態(tài)分組，標簽個數的增加并沒有導致一個組內具有多于M個標簽的概率增加。并且天線個數 4M= 時，99.5%以上的分組具有少于M個標簽，能夠被 ICA算法正確分離。天線個數 8M= 時，99.94%以上的分組具有少于M個標簽，能夠被ICA算法正確分離。

圖10M=8時，組內多于M個標簽的概率隨標簽數量變化的情況

5 結束語

利用現代信號處理技術，特別是多天線技術來實現多標簽防碰撞是 RFID防碰撞算法新的發(fā)展趨勢，也是突破傳統(tǒng)算法性能不高的有效途徑。本文分析了多天線UHF RFID系統(tǒng)的數學模型，通過對該模型的分析，得出多天線UHF RFID系統(tǒng)多標簽混合數據完全符合獨立分量分析（ICA）算法的約束條件。為將源信號正確地分離出來，ICA算法要求觀測信號的數目應大于或等于源信號的數目。為滿足這一要求，本文利用位隙算法對標簽進行分組，使每組內的標簽數小于閱讀器天線數，然后在組內再使用ICA算法進行標簽數據分離。據此，提出一種新的位隙動態(tài)分組盲分離多標簽防碰撞算法（BSDBG算法）。本文從理論上分析和實驗上驗證了這種算法的標簽識別率完全可以超過1，遠遠超過了傳統(tǒng)TDMA類型的防碰撞算法的標簽識別率。

[1] FINKENZELLER K. RFID Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification[M]. Chichester:Wiley, 2003.

[2] LIANG B, HU A Q, QIN Z Y. Trends and brief comments on anti-collision techniques in radio frequency identification systems[A].Proceedings of the 6th Int Conf on ITS Telecommunications[C].Chengdu, China, 2006.241-245.

[3] 余松森，詹宜巨，彭衛(wèi)東. 基于返回式索引的二進制樹形搜索反碰撞算法及其實現[J]. 計算機工程與應用, 2004, 40(16): 26-28.YU S S, ZHAN Y J, PENG W D. An anti-collision algorithm based on binary-tree searching of regressive index and its practice[J]. Computer Engineering and Applications, 2004, 40(16) : 26-28.

[4] AAPO H, ERKKI O. Independent component analysis: algorithms and applications[J]. Neural Networks, 2000, 13(4-5): 411-430.

[5] YUAN S, PETER J H, MARLIN H M. Application of ICA in collision resolution for passive RFID communication[A]. Proceedings of the World Congress on Engineering and Computer Science[C]. San Francisco, USA, 2009. 1292-1297.

[6] EPCGLOBAL, EPCTM. Radio Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860MHz～960MHz Version 1.0.9[S]. 2005.

[7] ISO/IEC18000-6. Radio Frequency Identification for Item Management-part 6: Parameters for Air Interface Communications at 860MHz～960MHz[S]. 2010.

[8] 馬建倉, 牛奕龍, 陳海洋. 盲信號處理[M]. 北京: 國防工業(yè)出版社,2006.MA J C, NIU Y L, CHEN H Y. Blind Signal Processing[M]. Beijing:National Defence Industry Press, 2006.

[9] KIM C S, PARK K L, KIM H C,et al. An efficient stochastic anti-collision algorithm using bit-slot mechanism[A]. Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications[C]. Las Vegas, USA, 2004. 652-656.