劉 艷 ，張 玉 *

（1. 大連市環(huán)境感知與智能控制重點實驗室（大連大學），遼寧大連116622； 2. 大連大學信息工程學院，遼寧大連116622）

0 引言

射頻識別（Radio Frequency IDentification，RFID）標簽具有體積小、成本低、易于處理等優(yōu)點，目前被廣泛應用于倉庫管理、物流控制、智能貨架、產(chǎn)品追蹤等領域［1-2］。實際應用中，當兩個或多個標簽同時與閱讀器通信時，信號將互相干擾，產(chǎn)生標簽碰撞問題，導致標簽的識別準確率、速度和效率等性能變差，標簽防碰撞算法成為當前RFID系統(tǒng)亟待突破的關鍵技術之一［3］。

目前，標簽防碰撞算法主要有兩種：基于樹的算法和基于Aloha 協(xié)議的算法［4-8］。在大型 RFID 系統(tǒng)應用中，標簽群體很大，二叉樹算法的復雜度較高、延遲較長，無法滿足識別環(huán)境中實時識別的要求［9］。因此，基于Aloha協(xié)議的算法被廣泛采用，該算法簡單、使用成本低。文獻［10］中證明了在Aloha 算法中，當標簽數(shù)與幀長度相等時，系統(tǒng)最高吞吐量理論上可達0.368，幀長大小的選取對系統(tǒng)吞吐率高低起著十分關鍵的作用。文獻［11-12］中分別在基于Q 值算法和動態(tài)幀時隙Aloha（Dynamic Framed Slotted Aloha，DFSA）算法的基礎上，對標簽識別過程進行了優(yōu)化，使系統(tǒng)吞吐量大于0.6。文獻［13］中結合了Aloha 和樹類算法的優(yōu)點，首先利用DFSA 算法對標簽進行識別，然后通過最大碰撞位判斷將剩余標簽分為左右子樹，實現(xiàn)對部分碰撞標簽的成功識別，使系統(tǒng)吞吐量進一步提高到0.7。

傳統(tǒng)DFSA 算法基于標簽與時隙的一對一識別，系統(tǒng)吞吐量始終較低。為了解決這一問題，可并行識別方案被廣泛研究并使用［14-15］，它們突破了一個時隙只能識別一個標簽的束縛，可以大幅度提高標簽的吞吐量。Buzz 算法［16］借助壓縮感知概念來稀疏碰撞信號、解碼標簽信息、減少碰撞標簽；但它依賴于信道估計，當同時傳輸?shù)臉撕灁?shù)量超過100 時，Buzz算法的計算復雜性顯著增加，在涉及大量標簽的應用環(huán)境中效率更低。并行識別協(xié)議（Parallel Identification Protocol，PIP）算法［17］使用L-K 代碼進行識別，它用一個特殊設計的模式將標簽ID 編碼成一個位字符串，實現(xiàn)標簽并行識別；但是PIP算法中讀寫器必須已知整個標簽集，這在真實使用場景中不可實現(xiàn)。文獻［18-19］中提出了基于正交可變擴頻因子（Orthogonal Variable Spreading Factor，OVSF）碼的并行識別方案，該方案將擴頻通信技術和DFSA 算法相結合，擴頻通信技術的應用，實現(xiàn)了標簽的并行識別，提高了系統(tǒng)吞吐量；缺點是偽隨機碼的個數(shù)有限，并且每個標簽必須存儲2n(n =1，2，…)個擴頻碼，缺乏靈活性，且占用大量的標簽內(nèi)存資源。文獻［20］中將快速獨立成分分析（Fast Independent Component Analysis，F(xiàn)astICA）技術與DFSA 算法結合，提高了算法吞吐量，但要求閱讀器天線數(shù)為8。顯然，上述標簽識別方案均未涉及標簽完全識別的判斷標準，無法解決某一標簽始終不能被識別而導致的標簽“饑餓”問題［21］。

針對上述問題，本文提出了基于Logistic 映射的DFSA（Logistic-DFSA）算法。該算法利用Logistic 映射可以產(chǎn)生數(shù)量巨大序列的優(yōu)點，將Logistic 映射引入擴頻通信技術中［22］，滿足大容量識別系統(tǒng)的需求；同時，因為Logistic 映射可以根據(jù)需要產(chǎn)生隨意碼長序列，且每個標簽僅需存儲一個擴頻碼序列，避免了OVSF 碼的靈活性差和占用大量內(nèi)存的缺點；將擴頻通信技術與DFSA 算法結合，突破了Aloha 算法碰撞時隙中無法識別標簽的限制；通過幀長、擴頻碼長度和標簽數(shù)量對系統(tǒng)識別過程中吞吐量的影響變化的研究，確定最優(yōu)幀長、擴頻碼長度；根據(jù)一幀結束后剩余標簽數(shù)量，給出標簽可完全識別的重復幀算法。最后，通過仿真實驗驗證本文算法用于標簽識別時，具有需要較少總時隙數(shù)、系統(tǒng)吞吐量較高、標簽識別率可達100%的優(yōu)勢。

1 Logistic-DFSA算法

本文基于擴頻通信技術解決Aloha 算法中一個時隙只能識別一個標簽的瓶頸問題，將Logistic 混沌映射應用于擴頻通信中，解決擴頻碼序列數(shù)量有限的問題；在標簽識別吞吐量分析基礎上，確定最優(yōu)碼長與幀長；利用重復幀算法進行標簽完全識別。

1.1 改進的標簽識別算法

圖1 為本文可并行識別標簽的方案與傳統(tǒng)動態(tài)幀時隙Aloha 算法識別標簽方案的對比。其中，F(xiàn)rame 為標簽識別幀，Slot 為標簽選擇通信時隙，Tag 為標簽號。第一幀識別結束后，存在未成功識別標簽，需要開始新的一幀（即第二幀）繼續(xù)識別，直至所有標簽識別完畢。

圖1（a）為傳統(tǒng)動態(tài)幀Aloha 算法，標簽只有在成功時隙（只有一個標簽的時隙，如圖1（a）的Frame1中slot1）中才可成功識別，導致每幀識別結束后，仍有大量未識別標簽，需要多幀才能完成標簽的全部識別，系統(tǒng)吞吐量較低。本文采用的擴頻通信技術的可并行標簽識別方案中因為應用了擴頻技術，碰撞不再只是簡單的多標簽選擇同一時隙碰撞，而是如圖1（b）中所示，標簽識別時隙分為四種：

1）成功時隙：只有一個標簽的時隙或者一個時隙中的多個標簽選擇互不相同的擴頻碼序列，標簽可成功識別，如圖1（b）的 Frame1 中 Slot4 的 Tag9，F(xiàn)rame2 中 Slot1 的 Tag1、Tag2、Tag6。

2）部分碰撞時隙：多個標簽，但是存在碼不同標簽，此標簽可被成功識別，如圖1（b）的Frame1中Slot3的Tag4、Tag6。

3）完全碰撞時隙：大于等于2 個標簽的時隙且所有標簽的擴頻碼相同，如圖 1（b）的 Frame1 中 Slot1 的 Tag1、Tag2、Tag7。

4）空時隙：沒有標簽的時隙，如圖1（b）Frame1中Slot2。

圖1 傳統(tǒng)幀時隙Aloha算法與并行識別算法對比Fig. 1 Comparison of traditional framed slotted Aloha algorithm and parallel identification algorithm

1.2 偽碼序列生成及分析

擴頻通信技術廣泛應用于信息通信中，生成擴頻序列方式的選取十分重要。m 序列、Gold 序列是常用的擴頻通信序列，但是當RFID 系統(tǒng)中標簽數(shù)量較大時，這些序列的數(shù)量遠遠滿足不了大容量系統(tǒng)的要求。沃爾什矩陣和OVSF 序列由哈達瑪矩陣產(chǎn)生，也經(jīng)常用于擴頻通信，但是每個標簽需要存儲的擴頻碼序列數(shù)量為2n(n = 1，2，…)，產(chǎn)生擴頻碼速度過慢，占用過多標簽存儲空間。

混沌理論生成偽隨機數(shù)方式簡單、快速且易于實現(xiàn)，已被廣泛應用于各個領域。每個標簽根據(jù)初值不同迭代一個對應長度序列，用于擴頻通信。常用混沌映射有Logistic 映射、Tent 映射、Henon 映射、Chebyshev 映射、組合混沌映射等。本文選取Logistic 映射生成偽隨機數(shù)，因為與其他幾種混沌映射相比，它具有較好遍歷性、自相關和互相關性。Logistic 混沌映射表達式描述為：

其中：xn∈ (0，1)；α是系統(tǒng)控制參數(shù)。當α ∈ [3.57，4]時，系統(tǒng)為混沌狀態(tài)。α = 4 時，稱為滿映射（函數(shù)曲線取滿了值域空間）。n為迭代次數(shù)，xn表示系統(tǒng)在給定初值之后迭代了n - 1次的狀態(tài)值。為映射整個迭代空間，本文選取滿映射混沌狀態(tài)，即α = 4。Logistic混沌映射具有如下性質(zhì)：

1）序列概率密度：

其中ρ(x)與初始值x0無關，所以該系統(tǒng)具有普遍性。

2）序列均值：

3）自相關函數(shù)：

4）互相關函數(shù)，其中，初值分別為x10、x20：

由上述分析可知，Logistic 映射具有良好的自相關和互相關性能，能夠應用到擴頻通信中，且Logistic 映射根據(jù)選取初值不同可迭代出大量序列，因此，可以滿足大容量系統(tǒng)的要求。

1.3 碼長選取

傳統(tǒng)DFSA 算法基于標簽與時隙的一對一識別，出現(xiàn)大量碰撞時隙，系統(tǒng)吞吐量較低，本文引入的擴頻通信技術，改變了這種關系，可以大幅度提高系統(tǒng)吞吐量，改變這種關系的關鍵是標簽碼長的選取。

初始幀長為F，標簽數(shù)為N，擴頻碼長度為m時，可用作擴頻碼的混沌序列的數(shù)量為M。假設所有時隙均為碰撞時隙，利用平均分配原則，每個時隙中的標簽數(shù)為：

擴頻碼數(shù)量為M時，一幀中可以識別的標簽數(shù)量為：

標簽識別時，通常情況下選取初始幀長F = 8，則標簽數(shù)N與擴頻碼數(shù)量M對可識別標簽數(shù)nSucc的影響如表1所示。

由表1可知，M = 16時，當標簽數(shù)N = 528，沒有標簽能被成功識別；M = 32 時，當標簽數(shù)N = 1296，沒有標簽能被成功識別；M = 64 時，當標簽數(shù)N = 3 085，沒有標簽能被成功識別。一幀中沒有標簽能被成功識別，即幀中時隙全為完全碰撞時隙，浪費了一幀的同時，將直接影響下一幀最優(yōu)幀長的選取，應避免這種情況的發(fā)生。

1.4 幀長選取

基于1.3 節(jié)中的條件，某個時隙能夠識別n 個標簽的概率為：

n個標簽出現(xiàn)在一個時隙中的概率為：

結合式（8）和（9），當前識別所有標簽的系統(tǒng)吞吐量為：

當M ＞ 2時，式（8）可表示為：

對式（11）中的F求偏導，求駐點，得到：

化簡得，N = FM 為唯一駐點：當F ＞ N M 時，T(N，F(xiàn)，M)單 調(diào) 遞 減 ；F ＜ N M 時 ，T(N，F(xiàn)，M) 單 調(diào) 遞 增 。 函 數(shù)T(N，F(xiàn)，M)的最大值為：

因此，N = FM可作為識別標簽時的幀長選取依據(jù)。文獻［10］證明DFSA 算法的最大系統(tǒng)吞吐量為e-1，所以由式（13）可知，本文算法系統(tǒng)吞吐量最大值為DFSA算法的M倍。

本文以被普遍看好的無源標簽智能倉儲環(huán)境為例，實際應用中倉儲貨架一般在1～2 m，而無源RFID 的感應范圍在60 cm左右，因此在閱讀器有效識別范圍內(nèi)存在的標簽數(shù)量是有限的（＜2 000 個），本文假設估計算法估計的標簽數(shù)量最大值為2 000。圖2 為本文算法在標簽數(shù)N ∈(1，2 000)時，對應不同幀長F和擴頻碼數(shù)量M 下的系統(tǒng)最大吞吐量。可以明顯看出，擴頻碼數(shù)量M 越大時，隨著幀長增加，系統(tǒng)吞吐量下降越快，所以，幀長過大時，將失去擴頻通信應用于DFSA 算法的優(yōu)勢。

圖2 最大期望吞吐量與M及F的關系(N ∈(1，1024))Fig. 2 Relationship between maximum expected throughput and M and F(N ∈ (1，1024))

1.5 標簽識別結束標準

基于Aloha 防碰撞算法中，標簽隨機選取時隙與閱讀器通信，可能存在某些標簽始終無法選取時隙的情況，從而出現(xiàn)標簽“饑餓”問題，即識別周期中可能存在始終無法識別的標簽，因此，有必要確定是否已成功識別所有標簽，以終止標簽識別。

理論上，基于Aloha 防碰撞算法可以根據(jù)幀內(nèi)成功識別的標簽數(shù)量或根據(jù)是否有標簽回復來決定是否終止識別周期。Aloha防碰撞算法中，識別標簽數(shù)量等于真正標簽數(shù)量時終止識別；或者開始新幀時，回復的時隙中只有空時隙，則判定標簽完全識別。但RFID系統(tǒng)實際應用場景中，標簽數(shù)量是未知的，需由標簽估計算法確定，標簽數(shù)量較大時，估計誤差也隨之增加，此時上述方法已不能確定是否結束標簽識別；另外，回復時隙中可能都為空閑時隙，因為沒有標簽選取通信時隙，但是卻有標簽未被識別。為了解決上述問題，本文提出了以下重復幀算法。

假設估計的標簽數(shù)量為n^，每輪閱讀器識別的標簽數(shù)量為Ni(i= 1，2，…)，那么終止標簽識別判斷如下：

步驟1 假設現(xiàn)在識別結束幀為第i幀，統(tǒng)計每次識別結束剩余標簽數(shù)量ni=ni-1-Ni（其中i= 2，3，…，n1=n^）。

步驟2 如果ni= 0 或者ni＜0，廣播QueryAdjust（Fi），進入步驟1；如果ni= 0，并且已重復過QueryAdjust（Fi），則執(zhí)行步驟4；如果ni＞0，并且連續(xù)兩幀沒有標簽回復，執(zhí)行步驟4；否則，請繼續(xù)執(zhí)行步驟3。

步驟3 開始一個新的識別幀。

步驟4 結束識別周期。

1.6 算法流程

本文所提Logistic-DFSA 算法識別標簽流程如圖3 所示。其中，F(xiàn)為幀長，m為碼長，SN為標簽選取通信時隙，SC為標簽選取擴頻碼。

圖3 Logistic-DFSA算法流程Fig. 3 Flowchart of Logistic-DFSA algorithm

2 仿真與結果分析

為驗證標簽識別算法的性能，本文從閱讀器識別所有標簽所需幀數(shù)、總時隙數(shù)和系統(tǒng)吞吐量三個方面，利用Matlab仿真軟件對 DFSA［8］、CSP-FSA（Continuous Slot Prediction-Frame Slot Aloha）［11］、DFBT（Dynamic Framed Binary Tree）［13］、OVSFDFSA［19］算法以及本文改進的基于Logistic 映射的動態(tài)幀時隙Aloha 算法（Logistic-DFSA）進行了仿真實驗對比，初始幀長F初始= 8，本文算法選取碼長m= 31，可用于擴頻通信的序列數(shù)量為M= 64［23］，OVSF 碼長m= 32，可用于擴頻通信的序列數(shù)量為M= 32，標簽樣本數(shù)量最大為2 000，以50 為間隔，每個樣本數(shù)量取50次仿真結果平均值。

2.1 幀數(shù)

圖4 所示為識別所有標簽所需幀數(shù)對比。DFSA 算法因為標簽與時隙的一對一識別，碰撞標簽數(shù)量較多，需要較多幀識別全部標簽；CSP-FSA 算法通過連續(xù)幀狀態(tài)的預測，可以跳出識別效率較低幀，重新開始新的一幀，增加了識別幀數(shù)；DFBT 算法中，通過二進制搜索樹算法對未識別標簽進行分裂，實現(xiàn)部分碰撞標簽成功識別，減少下一幀將要識別的標簽數(shù)量，從而減少識別標簽所需幀數(shù)；OVSF-DFSA 算法和本文Logistic-DFSA 算法中，幀長選取為DFSA 和DFBT 算法的1/M，但是擴頻通信技術的應用，識別標簽幀數(shù)仍有較大優(yōu)勢。本文Logistic-DFSA 算法在相同碼長的情況下，相比OVSF-DFSA算法，擁有更多的擴頻碼數(shù)量，所以識別標簽所需幀數(shù)更少。

圖4 不同標簽數(shù)時各算法識別標簽所需的幀數(shù)對比Fig. 4 Comparison of frames of each algorithm for identifying different numbers of tags

2.2 總時隙數(shù)

總時隙數(shù)為標簽識別時系統(tǒng)所需要的成功時隙數(shù)、碰撞時隙數(shù)、空時隙數(shù)總和。防碰撞算法的目的是減少碰撞時隙數(shù)和空閑時隙數(shù)，提高成功時隙數(shù)，但傳統(tǒng)的DFSA 算法只能在一個時隙中識別一個標簽，碰撞時隙數(shù)量較多，所以傳統(tǒng)DFSA 算法需要較大幀長和多幀識別標簽，導致總時隙數(shù)較大；CSP-FSA 算法通過時隙預測機制，可以跳出無效時隙，避免了無效時隙的浪費，識別標簽總時隙數(shù)有所減少；DFBT 算法中，通過幀時隙Aloha 算法識別和碰撞標簽的分裂樹識別，減少了下一幀需要識別的標簽數(shù)量，所以總時隙數(shù)相比傳統(tǒng)DFSA算法較少。在本文算法中，由于一個時隙可以識別的標簽數(shù)量由碼長控制，當碼長選取合適數(shù)值時，可以將碰撞時隙中的標簽完全識別，從而將碰撞時隙轉化為成功時隙，或者識別碰撞時隙中部分標簽，將完全碰撞時隙轉化為部分碰撞時隙，所需總時隙數(shù)大幅減少。如圖5 所示，當標簽數(shù)為2 000時，本文所提算法相較于DFSA、CSP-FSA、DFBT、OVSF-DFSA算法總時隙數(shù)分別減少98.3%、97.2%、96.7%、48.3%。由此可見，閱讀器與標簽之間的通信次數(shù)與通信量大幅減少，Logistic-DFSA算法用于標簽識別時，復雜度較低。

圖5 不同標簽數(shù)時各算法的總時隙數(shù)對比Fig. 5 Comparison of total number of slots of each algorithm with different number of tags

2.3 吞吐量

系統(tǒng)吞吐量是標簽識別時最重要的衡量系統(tǒng)效率的指標。系統(tǒng)吞吐量T 的定義為可識別標簽數(shù)N 與所需總時隙數(shù)S比值，即T = N/S。

圖6 所示為標簽數(shù)與吞吐量對比，本文Logistic-DFSA 算法和 OVSF-DFSA 算法相較于 DFSA、CSP-FSA 和 DFBT 算法吞吐量方面有較大優(yōu)勢，原因在于本文算法與OVSF-DFSA 算法采用了擴頻通信技術，通過對碰撞時隙中的標簽全部識別或部分識別，減少了傳統(tǒng)算法里面的碰撞時隙數(shù)量。相同碼長時，本文采用的Logistic 混沌映射方案可提供數(shù)量更多的擴頻碼序列，所以相較于OVSF-DFSA 算法，在同一個碰撞時隙中可以識別更多的標簽，從而減少下一幀需要識別的標簽數(shù)量。本文所提算法吞吐量分別是DFSA、CSP-FSA、DFBT、OVSFDFSA算法吞吐量的61、32、31、2倍。

圖6 不同標簽數(shù)時各算法的吞吐量對比Fig. 6 Comparison of throughput of each algorithm with different number of tags

3 結語

本文針對標簽防碰撞算法吞吐量較低問題，提出了基于Logistic 映射的標簽可并行識別方案，實現(xiàn)了一個時隙多個標簽的并行識別，給出了最優(yōu)的碼長與幀長選取方法，并根據(jù)標簽識別時反饋給閱讀器ID 信息，確立了標簽完全識別的判斷標準。仿真實驗證明，本文Logistic-DFSA 算法用較小幀數(shù)和總時隙數(shù)有效識別閱讀器識別范圍內(nèi)標簽，實現(xiàn)了較高的系統(tǒng)吞吐量。但是算法在執(zhí)行過程中，仍會出現(xiàn)少量無效時隙，下一步算法重點是跳過無效時隙，進一步提高標簽識別吞吐量。