密集環境下RFID系統濾波方法研究

郭鳳鳴，李兵，何怡剛

1.湖南機電職業技術學院，長沙410151

2.湖南大學電氣與信息工程學院，長沙410082

1 引言

物聯網利用射頻識別（RFID）、無線傳感網等信息傳感設備，將目標物與互聯網相連接，實現對目標物的智能化識別、定位、監控及管理等功能。RFID系統、數據庫及網絡數據處理能力的限制，使得從大量標簽識別碼（ID）數據中過濾出有用信息成為亟需解決的問題[1-2]。

文獻[3]介紹了典型的網絡數據包分類方法；文獻[4]討論了RFID濾波及網絡數據包分類方法的相似性；文獻[5]給出了RFID閱讀器讀濾波算法；文獻[6-7]提出了基于讀濾波的RFID濾波方法，重點解決了實際應用中去除噪聲及重復數據以準確獲取目標ID數據的問題，但所提出方法實時性較差，不符合快速濾波的應用需求。本文結合讀濾波算法及RFID空中接口通信協議規定的Select指令，提出了一種新的基于幾何算法的RFID濾波方法，并對該方法進行了仿真實驗。

2 RFID空中接口幾何濾波算法

密集環境RFID系統是設備部署環境中存在多個閱讀器及大量標簽，且支持較大數量的終端用戶及應用，如圖1所示。圖1中，空中接口層執行預濾波，中間件對預濾波做出響應；閱讀器層及中間件層執行后濾波；后濾波由讀濾波開始，且讀濾波受終端用戶及應用控制；中間件將部分后濾波任務分配給閱讀器，以減少中間件計算量及閱讀器與中間件網絡載荷。

圖1 密集環境RFID系統示意圖

2.1 RFID標簽數據結構及讀濾波

根據ISO/IEC 18000-6C標準，標簽數據一般包括版本號、域名管理者、對象分類及序列號4部分。編碼長度分為64位、96位及256位3種，以GID-96為例，標簽數據結構中4部分分別為8位、28位、24位及36位。閱讀器接收標簽數據后，基于按位模式對標簽數據進行讀濾波處理[5]。例如，可口可樂公司產品的GID-96編碼為35.00009F1.*.*，其中355m l罐裝可樂的對象分類代碼為000200，則可利用35.00009F1.000200.*從標簽數據中濾出355m l罐裝可樂產品[8]，從而實現讀濾波。

2.2 RFID空中接口標簽群管理

根據ISO/IEC 18000-6C[9]標準，閱讀器利用Select、Inventory及Access等3個指令管理標簽群。閱讀器通過一個或多個Select指令選擇特定標簽群執行Inventory指令。執行Select指令后，只有匹配標簽設置標記，其他標簽不執行Inventory過程。當匹配標簽群接收到Query指令時，Inventory循環開始，如圖2所示。Access過程是閱讀器對Inventory過程中指定的標簽進行讀寫操作。

圖2 單標簽響應過程示意圖

2.3 幾何濾波算法

讀濾波方法濾波器數據輸入端標簽數據數量較大，影響系統濾波效率。本文結合讀濾波算法及Select指令，利用矩形框幾何形式，給出空中接口濾波算法，所提出算法分三步完成。

步驟1 獲取包括所有矩形框的邊界盒，如圖3所示。圖3（a）中，利用邊界盒濾除數據源中冗余部分；但當標簽群范圍邊界存在讀濾波時，步驟1不能提高濾波效率，如圖3（b）所示。

圖3 步驟1示意圖

步驟2利用水平及垂直掃描線找出交叉點，以隔離矩形框組的重疊部分，如圖4所示。找到矩形框組重疊部分后，選擇單獨的隔離邊界盒。步驟2在利用多個Select指令濾除冗余區域的同時增加了系統時間消耗，且由于新的復制區域的出現，使得步驟2相較于步驟1增加了少量的冗余區域。

圖4 步驟2示意圖

步驟3 利用更多Select指令獲取更小冗余區域，如圖5所示。圖5（a）利用4個Select指令產生6個冗余區域；圖5（b）利用4個Select指令產生3個冗余區域。圖5中冗余區域遠小于整體區域。

圖5 步驟3示意圖

3 Inventory概率模型及濾波時間測試方法

空中接口濾波算法利用Select指令在數據源頭對標簽數據進行濾波，從而提高系統數據處理能力。為評估所提出空中接口濾波算法效率，本文提出Inventory概率模型及循環次數模型。

3.1 Inventory概率模型

定義ALOHA防沖突算法[10]中幀長度為Sf，標簽群大小為St。式（1）、（2）為文獻[10]給出的Sf概率模型。假設n個標簽的時隙數量為TSf，Stn，則系統效率Eff為：

為使系統效率最大，對式（1）求導，可得幀長度為Sf時最優響應標簽數Sto為：

3.1.1 單標簽響應、無響應及沖突響應概率模型

假設變量N服從關于η、p的二項分布，即有N～B(St，η)，其中，則根據概率質量函數可得n為：

一個Inventory周期內，單個標簽響應及空閑概率Pr及Pnr分別為：

定義沖突響應概率Pcr包括除Pr及Pnr外的情況，則結合式（3）、（4）可得Pcr為：

由式（3）～（5）可得，當Sf及Sto較大時有：

3.1.2 讀周期內Inventory循環次數模型

假設第c個標簽進入新Inventory循環的概率為Stc，則

由式（7）可知，當閱讀器在某段時間內未接收到標簽響應時，閱讀器完成讀周期。由式（7）可得：

則讀周期內Inventory循環次數Nir為：

3.2 濾波時間測試方法

假設Select、Inventory及讀濾波時間分別為ts、ti及tf，則RFID系統標簽識別時間t為：

3.2.1 Select時間近似計算

利用兩個Select指令計算ts，如圖6所示。標簽被初始標記（Flag）的概率為0.5，故第一個Select指令改變被選擇標簽群數量，第二個Select指令設置對話標記(A?B)。假設一個Select指令耗時為τ，則一個空中接口濾波耗時為2τ。假設空中接口濾波次數為k，則ts為：

圖6 兩次Select操作示意圖

3.2.2 Inventory時間近似計算

假設圖2中，第一個Inventory循環內發送Query指令，RN16，連續波及協議控制時間分別為ωQ-r、ωQ-nr及ωQ-cr，則第一個Inventory循環時間ti1為：

第二個Inventory循環發送Query Rep指令，則ti2為：

由式（12）、（13）可得，第n個Inventory循環時間為：

故ti為：

3.2.3 讀濾波時間近似計算

假設RFID系統中存在m個閱讀器，n個標簽，閱讀器及中間件濾波次數為γ，則當濾波過程采用線性查詢，即按位進行邏輯“與”操作時，tf-l為：

當濾波過程采用預構樹算法時，tf-p為：

4 仿真實驗

測試讀濾波線性查詢（LS）及所提出空中接口濾波算法條件下，RFID系統標簽識別時間t，并比較二者濾波效率。為簡化分析過程，根據文獻[10]，假設St=2Q，則由式（2）可得Sf=2Q+1，其中0≤Q≤15。所提出空中接口濾波算法三個步驟分別記為步驟1、步驟2、步驟3。

4.1 單閱讀器測試

實驗測試閱讀器進行5次讀濾波，且Q=4，5，6，7，即St分別為24、25、26及27時，ts、ti及tf的比例關系。相較于ts及ti，tf受系統部署方式及應用環境影響較大。根據文獻[4]，假設式（16）、（17）中γ=0.1為單次讀濾波最小計算消耗。利用Select及Inventory鏈路時間參數，獲取100次仿真的平均值。測試結果如圖7、8所示。圖7為ts、ti及tf比例關系；圖8為圖7中每個讀循環Inventory操作次數。

圖7 單閱讀器環境ts、ti及tf比例關系

圖8 讀循環Inventory操作次數

由圖7可見，空中接口濾波算法濾除了非目標標簽群；ts為固定值且遠小于ti，故雖然空中接口濾波算法增大了ts時間消耗，但其濾波效率仍優于線性查詢。ti為t主要影響因素；tf遠小于ts及ti，LS、步驟1、步驟2及步驟3的tf值分別為0.064、0.042、0.035及0.029，其對t影響最小。由圖8可見，讀循環Inventory次數隨St增大而增大；空中接口濾波中Select指令次數越多，濾除的非目標標簽群越多，故每個讀循環Inventory操作次數越少。

4.2 密集環境測試

實驗測試系統存在32個閱讀器，隨機產生1 024次讀濾波，Q=11，12，13，14，即St分別為211、212、213及214時，ts、ti及tf比例關系如圖9。

圖9 閱讀器密集環境ts、ti及tf比例關系

由圖9可見，閱讀器密集環境下，空中接口濾波算法濾波效率高于線性查詢方法。對于步驟1，由于邊界盒幾乎覆蓋整個標簽域空間，故步驟1濾波效率與LS相差較??；采用步驟2及步驟3，系統濾波效率得到較大提高，相較LS方法，系統標簽識別時間分別減少40%及50%。對于閱讀器密集環境，中間件接收32個濾波器數據，讀濾波發生在中間件，故相較于單閱讀器環境，此時ti及tf成為影響t的重要因素；ts大小固定，且遠小于ti及tf。

5 結束語

提出一種新的結合空中接口濾波及讀濾波的RFID濾波方法。測試結果表明，本文方法濾波效率優于線性查詢方法。對于單閱讀器環境，ti為t主要影響因素。對于密集環境，ti及tf為t主要影響因素；相較于線性查詢方法，本文方法濾波效率最大提高了50%。本文測試過程基于閱讀器接收標簽ID為隨機量假設前提，實際應用中，閱讀器接收到的標簽ID可能符合某種統計分布，其分布特性將對系統濾波效率產生影響。下一步，將針對實際應用中標簽ID分布特性，研究提出自適應的RFID系統濾波方法。

[1]Schreiber F A，Camplani R，Fortunato M，et al.PerLa：a language and middle ware architecture for data management and integration in pervasive information system[J].IEEE Transactions on Software Engineering，2012，38（2）：478-496.

[2]Lee C H，Chung C W.RFID data processing in supply chain management using a path encoding scheme[J].IEEE Transactions on Know ledge and Data Engineering，2011，23（5）：742-758.

[3]Gupta P，Mckeown N.A lgorithms for packet classification[J].IEEE Network，2001，15（2）：24-32.

[4]Park H S，Kim J D.Design and Implementation of a highs peed RFID data filtering engine[C]//Proc of EUC Workshops，2006，4097：423-434.

[5]Cglobal E P.Reader Protocol，Version1.1.2006.

[6]Bai Y，Wang F，Liu P.Efficiently filtering RFID data streams[C]//Proc Int VLDB Workshop on Clean Databases，2006：50-57.

[7]Wang F，Liu P.Temporal management of RFID data[C]//Pro of International Conference on Very Large Data Bases，2005：1128-1139.

[8]蔣韶鋼，譚杰.RFID中間件數據處理與過濾方法的研究[J].計算機應用，2008，28（10）：2613-2615.

[9]ISO/IEC Information Technology-Radio Frequency Identification for Item Management-Part 6：Parameters for Air Interface Communications at 860 MHz to 960 MHz[S].USA：ISO/IEC，2007.

[10]Lee S R，Joo S D，Lee CW.An enhanced dynam ic framed slotted ALOHA algorithm for RFID tag identification[C]//Proceedings of International Conference on Mobile and Ubiquitous System s，MobiQuitous，2005：166-174.