周 旋，鄔云文，向長青，丁 雷

（1.吉首大學 通信與電子工程學院，湖南 吉首 416000；2.湖南省普通高校近地空間電磁環(huán)境監(jiān)測與建模重點實驗室，湖南 長沙 410114；3.吉首大學 物理與機電工程學院，湖南 吉首 416000）

0 引 言

RFID 技術具有遠距離非接觸且批量識別的特點[1-2]，應用非常廣泛。當前，RFID 技術的相關研究內容有很多，例如RFID 標簽識別算法、RFID 通信模塊的濾波電路等[3]。RFID 系統在進行多標簽批量識別時，由于閱讀器的性能和系統選用的算法限制，常出現標簽的識別碰撞，以及部分標簽因多次發(fā)生碰撞造成始終未被識別的“餓死現象”[4]。在當前的研究中，RFID 多標簽識別算法是研究熱點之一。

在RFID 算法研究領域，目前研究較多的是確定性算法（如樹型類算法）和各種不確定性算法，不確定性算法以動態(tài)時隙ALOHA 算法為基礎[4-9]。文獻[10]提出了一種基于二叉樹和多叉樹的RFID 防碰撞算法，該算法單時隙內可同時識別兩個標簽，吞吐率達到65.7%，但是該樹型算法縱深太大，耗用時間太長。文獻[11-16]提出的6 個算法仍然存在吞吐率較低、吞吐率不穩(wěn)定、空閑時隙多、資源過多閑置、縱深太大等問題。

本文提出一種結合偽ID 碼，同時基于標簽可并行識別技術的防碰撞算法（Pseudo ID Code Logistic DFSA算法，PILD 算法）。該算法結合偽ID 碼分組和標簽可并行識別技術，提高了RFID 標簽識別傳輸的吞吐率，從而在占用相同傳輸頻帶的條件下，提升RFID 多標簽識別系統的傳輸性能，有效地減少了單個標簽因多次碰撞發(fā)生“餓死現象”的概率。本文對RFID 識別過程進行理論推導及數學分析，對算法的吞吐率、標簽的總查詢次數和標簽的平均查詢次數進行Mathematica 仿真，同時對仿真結果進行分析。另外，對比分析PILD 算法、基于偽ID 碼的樹型防碰撞算法，單純的Logistic-DFSA 算法的信息傳輸性能。

1 PILD 算法過程的理論分析

對于待識別標簽，首先通過偽ID 碼分組，當出現選擇同一個偽ID 碼的標簽數大于1 的情況時，采用標簽并行識別算法進行識別。在本章中首先對利用偽ID 碼將待識別標簽分組的情況進行分析，接著分析碰撞ID 碼的并行識別過程。

1.1 偽ID 碼識別過程理論分析

設閱讀器根據估算標簽數產生一組偽ID 碼，每個標簽在偽ID 碼的取值范圍內隨機選取一個偽ID 碼作為自己的標識符。其中，某個偽ID 碼被m個標簽同時選中的概率為：

式中：L為閱讀器所產生的偽ID 碼的個數；n為識別范圍內待識別標簽的總數量；m為選中當前偽ID 碼的標簽個數。

當單個標簽選中的偽ID 碼（即識別成功偽ID 碼）的期望和偽ID 碼總個數的比值取極限值時，存在如下關系：

此時，識別成功的偽ID 碼數量達到理論最大值?，F實情況下，式中n的數量很大，1可忽略不計，故取L=n。

在使用Logistic-DFSA 算法對標簽進行識別之前，首先，閱讀器估算識別范圍內標簽總數n，然后閱讀器把n發(fā)給標簽，標簽的隨機數生成器在1～n之間生成一個數作為偽ID 碼。此時，偽ID 碼有以下幾種情況：

1）該偽ID 碼無標簽選擇，即m=0；

2）有1 個標簽選擇該偽ID 碼，即m=1；

3）選擇該偽ID 碼的標簽數大于等于2，即m≥2，此時發(fā)生了傳統算法中的碰撞現象。

當m=0 時，由式（1）推導可得識別過程中出現空ID碼概率為：

當m=1時，由式（1）可得成功識別偽ID碼的概率為：

當m≥2 時，該偽ID 碼即為通常意義的碰撞ID 碼，由式（1）、式（2）推導出m≥2 時的標簽碰撞概率Pm公式為：

設某個偽ID 碼同時有m個標簽選中的情況，出現了碰撞，運用公式（5）并結合標簽并行識別算法給出該標簽出現m個碰撞問題的算法實現方法，并計算標簽查詢次數和吞吐率。

1.2 標簽可并行識別過程的算法實現

通過采用Logistic-DFSA 算法實現標簽的并行識別。算法Logistic-DFSA 是一種基于Logistic 映射和DFSA 算法的可并行識別算法，該算法將Logistic 混沌映射應用于擴頻通信，實現了動態(tài)幀擴頻標簽識別。Logistic 映射是一種常用混沌映射，具有較好的遍歷性、自相關性和互相關性，且該映射應用于擴頻通信中可以滿足大容量系統的要求[16]。該算法每個時隙中的標簽數nslot計算公式為：

式中，F為初始幀長，通常選取F=8。

某個時隙能夠識別m個標簽（即同時選中同一個偽ID 碼的標簽數）的概率為：

當擴頻碼數量為M時，由式（6）和式（7）可得一幀中可識別的標簽數量為：

式中：ncg為一幀中可成功識別的標簽數量；nsx為每個時隙中的標簽數；擴頻碼數量M可選用16、32 或64。

前文對偽ID 碼識別過程及并行識別過程進行了分析，給出了標簽并行算法的方法——PILD 算法，來解決出現碰撞的問題。下面從理論上對PILD 算法的實現及該算法的性能進行分析。

2 PILD 算法的實現及性能理論分析

基于偽ID 碼的樹型算法存在每個時隙只能識別一個標簽的限制。標簽可并行識別算法（Logistic-DFSA）存在的問題是：當標簽數量過多時，會造成標簽幀過長，導致算法的吞吐率急劇下降。本文定義吞吐率為吞吐量總數和查詢總次數的比值。針對以上一系列問題，提出結合偽ID 碼和Logistic-DFSA 算法的PILD 算法，該算法可以極大地降低標簽查詢次數，增大吞吐率。在本章中將闡述算法流程的實現和對算法的性能進行分析。

2.1 算法實現

首先，由預測算法估計得出識別范圍內標簽的總數量，然后對所有標簽使用偽ID 碼進行分組。如果出現多個標簽選擇同一個偽ID 碼，則采用標簽并行識別算法——Logistic-DFSA 算法進行處理。PILD 算法具體流程如下：

步驟1：閱讀器通過使用標簽預測算法預測識別范圍內待識別標簽的數量n。

步驟2：閱讀器向標簽發(fā)送數值n，n為步驟1 中閱讀器預測的待識別標簽數量。標簽在接收到數值n后，利用隨機數生成器隨機產生1～n內的任意一個數作為自己的偽ID 碼。

步驟3：閱讀器設立初始值為0 的變量a和i，變量a用于判斷是否識別完所有的標簽，變量i用于判斷并記錄當前偽ID 碼的使用情況。

步驟4：若a＜n且i≤n，則執(zhí)行步驟5；否則算法結束，完成所有標簽的識別。

步驟5：當i≤n時，閱讀器向識別范圍內所有標簽發(fā)送判斷數值i，i為閱讀器產生的偽ID 碼。標簽在接收到i后，判斷自己的偽ID 碼是否與接收到的偽ID 碼i相等，如果相等表明該標簽選擇了當前閱讀器發(fā)送的偽ID 碼，此時該標簽進行響應。

步驟6：閱讀器在相應的時間內判斷是否有標簽進行響應。若沒有標簽響應，則表示當前偽ID 碼為空偽ID 碼，執(zhí)行賦值語句i=i+1，轉到步驟4 進行下一個偽ID碼識別；若有標簽響應，則繼續(xù)執(zhí)行步驟7。

步驟7：閱讀器判斷響應的標簽是否發(fā)生碰撞，即選擇當前偽ID 碼的標簽個數m是否大于等于2（本文m為同一時間選中同一偽ID 碼的標簽數。m的取值在2≤m≤3 范圍內概率大）。若有發(fā)生碰撞，則利用標簽并行識別算法（Logistic-DFSA 算法）進行識別，并向識別完成的標簽發(fā)送靜默指令，接下來執(zhí)行公式（9）所表示的程序賦值語句，同時執(zhí)行賦值語句i=i+1；若響應的標簽沒有發(fā)生碰撞，則直接識別回應響應的標簽，識別完成后，向其發(fā)送靜默指令并執(zhí)行a=a+1。最后執(zhí)行賦值語句i=i+1，轉到步驟4。

PILD 算法流程如圖1 所示。

圖1 PILD 算法流程

2.2 性能分析

PILD 算法的識別次數為：

每個偽ID 碼最多有m個標簽同時選中，出現m≤6情況的概率較大，故Logistic-DFSA 選用32 個擴頻碼即可完成識別。由式（5）可得在本算法中Logistic-DFSA的查詢次數，即偽ID 碼識別后的碰撞次數QLogistic，公式如下：

由式（3）、式（4）、式（11）推導出偽ID 碼識別次數QID的表達式為：

由式（10）～式（12）得PILD 算法識別總次數公式為：

由式（13）可推出PILD 算法的吞吐率為：

式中：T為吞吐率；Q為PILD 算法的總查詢次數；n為預測標簽總數。

由2.1節(jié)可知，當L≈n時，吞吐率最大，由式（14）得：

n趨近無窮大時，對式（14）求極值得到該算法吞吐率的最大值Tmax為0.791092。傳統算法一次只能識別一個標簽，存在某些標簽因多次發(fā)生碰撞而未被識別的餓死現象，而本文算法運用可并行識別算法很好地緩解了這種情況。下文對PILD 算法的標簽餓死概率進行分析。

2.3 PILD 算法的標簽餓死概率

RFID 標簽識別過程中，傳統算法會發(fā)生有些標簽因多次發(fā)生碰撞而未被識別的現象，即標簽餓死現象。PILD 算法的標簽餓死概率定義式為：

式中T為PILD 算法的吞吐率。在本文中，對比算法的標簽餓死概率也由該公式得出。由公式（15）得PILD 算法的標簽餓死概率為20.89%。

3 對比算法的吞吐率和查詢次數

對比基于偽ID 碼的樹型防碰撞算法和單純使用Logistic-DFSA 算法識別標簽的性能。

3.1 基于偽ID 碼的樹型防碰撞算法

該算法首先利用偽ID 碼對待識別標簽進行分組識別，若回應的標簽無碰撞則直接識別，若發(fā)生碰撞則采用碰撞跟蹤樹型算法進行識別。

由文獻[15]可得基于偽ID 碼的樹型防碰撞算法的總查詢次數計算公式為：

由于在該算法中吞吐量總數為標簽的總數量，故吞吐率計算公式為：

式中：T為吞吐率；Tmax為該算法吞吐率最大值；Q為標簽查詢總次數。該算法吞吐率最大值為0.614 1。由公式（15）得該算法的標簽餓死概率為38.59%。

3.2 Logistic-DFSA 算法

由本文的1.2 節(jié)可知，Logistic-DFSA 算法某個時隙能識別m個標簽的關系式為式（7），一幀中可識別的標簽數為式（8），而m個標簽出現在一個時隙中的概率為：

擴頻碼數量為M時，由式（8）可得查詢次數為：

該算法的吞吐量總數[16]為：

式中Q1為Logistic-DFSA 算法的吞吐量總數。

當M＞2 時，由式（20）可得：

由式（19）和式（21）可得該算法的吞吐率為：

當擴頻碼M=32，幀長F=8，標簽數量為800 時，吞吐率T(n,F,M)=0.029 56；當擴頻碼M=32，幀長F=8，標簽數量為1 200 時，吞吐率T(n,F,M) =0.00152。由此可見，在標簽數大于800 時，該算法的吞吐率趨于0。

式（20）中T(n,F,M) 為Logistic-DFSA 算法吞吐率，該算法吞吐率最大值為：

由公式（15）得該算法的標簽餓死概率最小值為24.47%。本文對PILD 算法的實現進行了理論推導，給出了算法流程圖，對該算法的性能進行了理論分析，推導出了查詢總次數和吞吐率的計算公式，同時，給出了吞吐率最大值。

4 仿真及性能對比分析

4.1 實驗設置

為了驗證PILD 算法的性能，對Logistic-DFSA 算法、基于偽ID 碼的樹型防碰撞算法、PILD 算法從系統吞吐率、總查詢次數和平均查詢次數三方面進行Mathematica 仿真，并對仿真結果進行分析。仿真環(huán)境采用普通智能倉庫，以通用無源標簽為例，初始幀長F=8，擴頻碼數量選取32，標簽樣本數量最大為2 000 個。由于選中同一偽ID 碼的標簽數m≥7 概率近似為0，所以仿真中以標簽數碰撞數m≤6 為例。

4.2 吞吐率

PILD 算法的吞吐率計算公式為式（14），基于偽ID碼的樹型防碰撞算法吞吐率定義為式（17），Logistic-DFSA 算法的吞吐率計算公式為（22）。按照實驗設置進行仿真，圖2 所示為在待識別標簽總數相等的情況下，PILD 算法、基于偽ID 碼的樹型防碰撞算法和Logistic-DFSA 算法三種算法的吞吐率對比圖。

在圖2 中點劃線為：基于偽ID 碼的樹型防碰撞算法的吞吐率和標簽數量的關系曲線，實線為PILD 算法吞吐率和標簽數量關系曲線，虛線為Logistic-DFSA 算法的吞吐率和標簽數量關系曲線。由圖2 可知PILD 算法的吞吐率變化為：隨著標簽數的增多，吞吐率迅速增加至0.791 092，保持穩(wěn)定?；趥蜪D 碼的樹型防碰撞算法的吞吐率特性為：呈現先迅速下降后穩(wěn)定的趨勢，穩(wěn)定在0.614 1。Logistic-DFSA 算法吞吐率最大為0.755 3，這種算法的特性呈現為：隨著標簽數量的增加，算法的吞吐率先增大再減小。標簽數目在126.86 個時吞吐率達到最大值0.755 3，在標簽數目大于800 個時吞吐率趨于0，與理論計算結果一致。由此可見，PILD 算法性能比Logistic-DFSA 算法穩(wěn)定，吞吐率比基于偽ID 碼的樹型防碰撞算法的吞吐率提高了28.82%，相比于Logistic-DFSA 算法吞吐率提高了4.74%。

圖2 吞吐率和標簽數量關系圖

4.3 查詢次數分析

PILD 算法的總查詢計算公式為式（13）；基于偽ID碼的樹型防碰撞算法的總查詢次數計算公式為式（16）；Logistic-DFSA 算法的總查詢次數計算公式為式（19）。平均查詢次數計算方法為，即查詢總次數與總標簽數的比值。從圖3的總查詢次數對比結果可知，PILD算法的總查詢次數明顯少于基于偽ID碼的樹型防碰撞算法的查詢次數，傳輸效率明顯比基于偽ID 碼的樹型防碰撞算法要高。Logistic-DFSA 算法的總查詢次數呈指數增長。當標簽數大于1 400個時，PILD算法的總查詢次數在三種算法中最少。

圖3 總查詢次數對比

由圖4 所示的平均查詢次數對比結果可知，PILD 算法的標簽平均查詢次數為1.26 次；基于偽ID 碼的樹型防碰撞算法的標簽平均查詢次數為1.6 次；Logistic-DFSA 算法標簽的平均查詢次數呈曲線變化，先逐漸減小后逐漸增大。當標簽數大于1 400 個時，PILD 算法中的標簽平均查詢次數最小。

圖4 平均查詢次數對比

4.4 標簽餓死概率對比

標簽餓死概率計算公式為式（15）。圖5 為三種算法標簽餓死概率對比圖。由圖5 可知，三種算法中PILD算法的標簽餓死率最低且保持不變，系統性能穩(wěn)定。

圖5 三種算法標簽餓死概率對比

5 結 論

已有的RFID 識別算法存在吞吐率較低、吞吐率不穩(wěn)定、空閑時隙多、資源過多閑置、縱深太大等問題。針對以上問題，本文提出了PILD 算法，即結合偽ID 碼分組和并行識別標簽技術的算法，該算法穩(wěn)定性好且吞吐率理論計算達到0.791092，相比基于偽ID 碼的樹型防碰撞算法提高了28.82%，相對于Logistic-DFSA 算法吞吐率提高了4.74%；平均標簽查詢次數為1.26 次，在標簽數大于1 400 時，PILD 算法在三種算法中識別總次數最少；偽ID 碼分組識別的應用有效地減少了“餓死現象”的概率。本文理論結論與仿真結果一致。