郭鳳鳴，李兵，何怡剛

1.湖南機(jī)電職業(yè)技術(shù)學(xué)院，長沙410151

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

1 引言

物聯(lián)網(wǎng)利用射頻識別（RFID）、無線傳感網(wǎng)等信息傳感設(shè)備，將目標(biāo)物與互聯(lián)網(wǎng)相連接，實(shí)現(xiàn)對目標(biāo)物的智能化識別、定位、監(jiān)控及管理等功能。RFID系統(tǒng)、數(shù)據(jù)庫及網(wǎng)絡(luò)數(shù)據(jù)處理能力的限制，使得從大量標(biāo)簽識別碼（ID）數(shù)據(jù)中過濾出有用信息成為亟需解決的問題[1-2]。

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

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

密集環(huán)境RFID系統(tǒng)是設(shè)備部署環(huán)境中存在多個(gè)閱讀器及大量標(biāo)簽，且支持較大數(shù)量的終端用戶及應(yīng)用，如圖1所示。圖1中，空中接口層執(zhí)行預(yù)濾波，中間件對預(yù)濾波做出響應(yīng)；閱讀器層及中間件層執(zhí)行后濾波；后濾波由讀濾波開始，且讀濾波受終端用戶及應(yīng)用控制；中間件將部分后濾波任務(wù)分配給閱讀器，以減少中間件計(jì)算量及閱讀器與中間件網(wǎng)絡(luò)載荷。

圖1 密集環(huán)境RFID系統(tǒng)示意圖

2.1 RFID標(biāo)簽數(shù)據(jù)結(jié)構(gòu)及讀濾波

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

2.2 RFID空中接口標(biāo)簽群管理

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

圖2 單標(biāo)簽響應(yīng)過程示意圖

2.3 幾何濾波算法

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

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

圖3 步驟1示意圖

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

圖4 步驟2示意圖

步驟3 利用更多Select指令獲取更小冗余區(qū)域，如圖5所示。圖5（a）利用4個(gè)Select指令產(chǎn)生6個(gè)冗余區(qū)域；圖5（b）利用4個(gè)Select指令產(chǎn)生3個(gè)冗余區(qū)域。圖5中冗余區(qū)域遠(yuǎn)小于整體區(qū)域。

圖5 步驟3示意圖

3 Inventory概率模型及濾波時(shí)間測試方法

空中接口濾波算法利用Select指令在數(shù)據(jù)源頭對標(biāo)簽數(shù)據(jù)進(jìn)行濾波，從而提高系統(tǒng)數(shù)據(jù)處理能力。為評估所提出空中接口濾波算法效率，本文提出Inventory概率模型及循環(huán)次數(shù)模型。

3.1 Inventory概率模型

定義ALOHA防沖突算法[10]中幀長度為Sf，標(biāo)簽群大小為St。式（1）、（2）為文獻(xiàn)[10]給出的Sf概率模型。假設(shè)n個(gè)標(biāo)簽的時(shí)隙數(shù)量為TSf，Stn，則系統(tǒng)效率Eff為：

為使系統(tǒng)效率最大，對式（1）求導(dǎo)，可得幀長度為Sf時(shí)最優(yōu)響應(yīng)標(biāo)簽數(shù)Sto為：

3.1.1 單標(biāo)簽響應(yīng)、無響應(yīng)及沖突響應(yīng)概率模型

假設(shè)變量N服從關(guān)于η、p的二項(xiàng)分布，即有N～B(St，η)，其中，則根據(jù)概率質(zhì)量函數(shù)可得n為：

一個(gè)Inventory周期內(nèi)，單個(gè)標(biāo)簽響應(yīng)及空閑概率Pr及Pnr分別為：

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

由式（3）～（5）可得，當(dāng)Sf及Sto較大時(shí)有：

3.1.2 讀周期內(nèi)Inventory循環(huán)次數(shù)模型

假設(shè)第c個(gè)標(biāo)簽進(jìn)入新Inventory循環(huán)的概率為Stc，則

由式（7）可知，當(dāng)閱讀器在某段時(shí)間內(nèi)未接收到標(biāo)簽響應(yīng)時(shí)，閱讀器完成讀周期。由式（7）可得：

則讀周期內(nèi)Inventory循環(huán)次數(shù)Nir為：

3.2 濾波時(shí)間測試方法

假設(shè)Select、Inventory及讀濾波時(shí)間分別為ts、ti及tf，則RFID系統(tǒng)標(biāo)簽識別時(shí)間t為：

3.2.1 Select時(shí)間近似計(jì)算

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

圖6 兩次Select操作示意圖

3.2.2 Inventory時(shí)間近似計(jì)算

假設(shè)圖2中，第一個(gè)Inventory循環(huán)內(nèi)發(fā)送Query指令，RN16，連續(xù)波及協(xié)議控制時(shí)間分別為ωQ-r、ωQ-nr及ωQ-cr，則第一個(gè)Inventory循環(huán)時(shí)間ti1為：

第二個(gè)Inventory循環(huán)發(fā)送Query Rep指令，則ti2為：

由式（12）、（13）可得，第n個(gè)Inventory循環(huán)時(shí)間為：

故ti為：

3.2.3 讀濾波時(shí)間近似計(jì)算

假設(shè)RFID系統(tǒng)中存在m個(gè)閱讀器，n個(gè)標(biāo)簽，閱讀器及中間件濾波次數(shù)為γ，則當(dāng)濾波過程采用線性查詢，即按位進(jìn)行邏輯“與”操作時(shí)，tf-l為：

當(dāng)濾波過程采用預(yù)構(gòu)樹算法時(shí)，tf-p為：

4 仿真實(shí)驗(yàn)

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

4.1 單閱讀器測試

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

圖7 單閱讀器環(huán)境ts、ti及tf比例關(guān)系

圖8 讀循環(huán)Inventory操作次數(shù)

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

4.2 密集環(huán)境測試

實(shí)驗(yàn)測試系統(tǒng)存在32個(gè)閱讀器，隨機(jī)產(chǎn)生1 024次讀濾波，Q=11，12，13，14，即St分別為211、212、213及214時(shí)，ts、ti及tf比例關(guān)系如圖9。

圖9 閱讀器密集環(huán)境ts、ti及tf比例關(guān)系

由圖9可見，閱讀器密集環(huán)境下，空中接口濾波算法濾波效率高于線性查詢方法。對于步驟1，由于邊界盒幾乎覆蓋整個(gè)標(biāo)簽域空間，故步驟1濾波效率與LS相差較?。徊捎貌襟E2及步驟3，系統(tǒng)濾波效率得到較大提高，相較LS方法，系統(tǒng)標(biāo)簽識別時(shí)間分別減少40%及50%。對于閱讀器密集環(huán)境，中間件接收32個(gè)濾波器數(shù)據(jù)，讀濾波發(fā)生在中間件，故相較于單閱讀器環(huán)境，此時(shí)ti及tf成為影響t的重要因素；ts大小固定，且遠(yuǎn)小于ti及tf。

5 結(jié)束語

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

[1]Schreiber F A，Camplani R，F(xiàn)ortunato 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中間件數(shù)據(jù)處理與過濾方法的研究[J].計(jì)算機(jī)應(yīng)用，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.