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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

當(dāng)式（3）中，M＞N時，A為列滿秩的，這時稱盲源分離為超定的。當(dāng)M＜N時，A為行滿秩的，這時稱盲源分離為欠定的。當(dāng)MN= 時，A為滿秩方陣，這時稱盲源分離為正定的。正定盲源分離具有唯一解，超定盲源分離多個觀測信號之間往往具有非獨立性，利用主成分分析（PCA, principal component analysis）技術(shù)，使混合矩陣變?yōu)榉疥嚭?，可以求出估計信號的唯一解。而對于欠定盲源分離則不具備唯一解，欲求得確定性解，需要其他約束條件，實現(xiàn)起來比較困難。為使用ICA，應(yīng)使多標(biāo)簽信號為超定或者正定的。

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

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

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

圖2 位隙算法工作原理

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

位隙信息和 ID信息調(diào)制方法的對比如圖 3所示。

圖3 位隙信息調(diào)制方法

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

整個算法的步驟如下。

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

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

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

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

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

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

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

8) 結(jié)束。

4 BSDBG算法性能分析與驗證

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

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

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

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

標(biāo)簽位隙分組數(shù)為

通過位隙分組后一個組內(nèi)沒有任何標(biāo)簽的概率為

一個組內(nèi)有一個或者多個標(biāo)簽選擇的概率為

具有單個或者多個標(biāo)簽的組的個數(shù)為

分離這些標(biāo)簽數(shù)據(jù)所需要的查詢次數(shù)為

總的查詢次數(shù)為

算法標(biāo)簽識別率（即算法效率）為

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

圖4M=4時標(biāo)簽分組數(shù)GS隨標(biāo)簽數(shù)量n的變化情況

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

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

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

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

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

圖7 BSDBG算法與DFSA和BTS算法標(biāo)簽識別率比較

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

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

圖8 算法平均標(biāo)簽識別率隨天線數(shù)量M的變化情況

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

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

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

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

一個組內(nèi)具有多于M個標(biāo)簽的概率為

當(dāng)標(biāo)簽數(shù)n較大時Cn

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

設(shè)：

那么：

或者：

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

圖9M=4時，組內(nèi)多于M個標(biāo)簽的概率隨標(biāo)簽數(shù)量變化的情況

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

圖10M=8時，組內(nèi)多于M個標(biāo)簽的概率隨標(biāo)簽數(shù)量變化的情況

5 結(jié)束語

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

[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)東. 基于返回式索引的二進制樹形搜索反碰撞算法及其實現(xiàn)[J]. 計算機工程與應(yīng)用, 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.