閆麗娟 趙菊敏 李燈熬

(太原理工大學(xué)信息工程學(xué)院，山西 太原 030024)

采用RFID技術(shù)查找暢銷類產(chǎn)品

閆麗娟 趙菊敏 李燈熬

(太原理工大學(xué)信息工程學(xué)院，山西 太原 030024)

在基于有源電子標(biāo)簽構(gòu)建的RFID系統(tǒng)中，如何以時(shí)間、能量有效的方式查找出暢銷類產(chǎn)品是一個(gè)重要的研究問題。針對(duì)多閱讀器RFID系統(tǒng)，首次對(duì)查找暢銷類產(chǎn)品過程中的能量問題進(jìn)行了研究，提出了一種基于分組機(jī)制的ETBC查找協(xié)議。該協(xié)議的核心思想是采用分組機(jī)制將同一屬性產(chǎn)品上附著的標(biāo)簽分為一組，根據(jù)查找要求在相應(yīng)組中找出樣本標(biāo)簽，并基于樣本標(biāo)簽回復(fù)的信息對(duì)其進(jìn)行暢銷類標(biāo)簽的查找。理論分析和仿真結(jié)果均表明了ETBC協(xié)議的有效性。相比針對(duì)全部標(biāo)簽進(jìn)行查找的協(xié)議，ETBC協(xié)議的能耗要低很多，協(xié)議執(zhí)行時(shí)間也大幅度減少。

RFID 有源標(biāo)簽 能量 分組機(jī)制 無(wú)線通信

0 引言

射頻識(shí)別(radio frequency identification，RFID)是一種無(wú)線通信技術(shù)。在很多應(yīng)用中，RFID系統(tǒng)可以用來(lái)追蹤產(chǎn)品的信息、對(duì)象跟蹤、超級(jí)市場(chǎng)和供應(yīng)鏈的管理等[1-7]。目前有源電子標(biāo)簽被大量使用，由于其工作的能量全部由電池提供，且更換大規(guī)模標(biāo)簽的電池是個(gè)棘手問題，因此針對(duì)基于有源電子標(biāo)簽構(gòu)建的RFID系統(tǒng),設(shè)計(jì)能量有效的監(jiān)控和識(shí)別協(xié)議是目前國(guó)內(nèi)外的一個(gè)研究熱點(diǎn)[8-10]。

目前，對(duì)于查找暢銷類產(chǎn)品這一領(lǐng)域的研究很少，且對(duì)標(biāo)簽的研究大多集中在以減少時(shí)間為目的。RFID標(biāo)簽的能量作為新的指標(biāo)越來(lái)越受到重視。鑒于此，提出了改進(jìn)的閾值分類(enhanced threshold-based classification，ETBC)協(xié)議，實(shí)現(xiàn)暢銷類產(chǎn)品的提取和分析，便于對(duì)產(chǎn)品的狀態(tài)進(jìn)行直觀評(píng)判。其主要目的就是在眾多產(chǎn)品中以高效、節(jié)能的方式查找出暢銷類產(chǎn)品，主要貢獻(xiàn)是首次提出了基于時(shí)間和能量有效的ETBC查找協(xié)議，并首次考慮了查找過程中的能量問題。

1 系統(tǒng)模型

本文考慮的RFID系統(tǒng)由3部分組成：后臺(tái)服務(wù)器、一組RFID閱讀器以及大量的RFID標(biāo)簽。假設(shè)后臺(tái)服務(wù)器存儲(chǔ)著系統(tǒng)中所有標(biāo)簽的信息，且閱讀器和標(biāo)簽之間的通信采用幀-時(shí)隙 ALOHA協(xié)議。在執(zhí)行協(xié)議的過程中，閱讀器首先向標(biāo)簽發(fā)送查詢命令，然后標(biāo)簽接收命令并返回相應(yīng)的回復(fù)信息。每一輪響應(yīng)中，閱讀器廣播查詢命令和當(dāng)前幀的時(shí)隙個(gè)數(shù)，每個(gè)標(biāo)簽通過Hash函數(shù)運(yùn)算，隨機(jī)選擇此幀中的一個(gè)時(shí)隙對(duì)閱讀器進(jìn)行回復(fù)。具體來(lái)說(shuō)，在每個(gè)查詢幀的開始，閱讀器廣播兩個(gè)參數(shù)：幀大小f和一個(gè)隨機(jī)數(shù)ri，其中f也就是幀包含的時(shí)隙個(gè)數(shù)，而ri用來(lái)幫助標(biāo)簽在該幀中通過Hash函數(shù)選擇一個(gè)時(shí)隙對(duì)閱讀器進(jìn)行回復(fù)。

2 問題定義

在閱讀器的覆蓋范圍內(nèi)，假設(shè)有n件附有RFID標(biāo)簽的產(chǎn)品，每一類產(chǎn)品擁有唯一的Cid和tid。設(shè)N為任意類別的標(biāo)簽數(shù)量，暢銷類標(biāo)簽必須滿足式(1)中的兩個(gè)限制條件，其中Vh、Vl、α和β為給定的已知參數(shù)，Vh和Vl為閾值，α和β為概率值。任何一類標(biāo)簽數(shù)量超過Vh時(shí)被報(bào)道的概率至少為α，同時(shí)任何一類標(biāo)簽數(shù)量低于Vl時(shí)被報(bào)道的概率最多為β。

(1)

3 ETBC協(xié)議

針對(duì)查找暢銷類標(biāo)簽這一研究領(lǐng)域，ETBC協(xié)議分為分組階段、樣本標(biāo)簽選擇階段、映射階段、回復(fù)階段和最優(yōu)參數(shù)估計(jì)階段這5個(gè)階段。

3.1 分組階段

分組階段采用分組機(jī)制，即哈希分桶機(jī)制。在此階段，擁有同一屬性的標(biāo)簽屬于同一組，同一組中包含若干類標(biāo)簽。例如在一個(gè)超市中，定義組G1代表的是洗漱用品，那么G1中包含洗發(fā)水、牙膏和沐浴露等類別的產(chǎn)品。具體的分組機(jī)制如下：首先通過式(2)的哈希函數(shù)得到組號(hào)Gi，rj為隨機(jī)數(shù)；然后排除其他組的標(biāo)簽，直接從Gi組中查找暢銷類標(biāo)簽，這個(gè)Gi其實(shí)就是每個(gè)桶，這就是哈希分桶的原理。簡(jiǎn)單來(lái)說(shuō)，就是根據(jù)每個(gè)標(biāo)簽的Cid，通過哈希函數(shù)產(chǎn)生哈希值，然后將相同哈希值的標(biāo)簽放在同一組Gi中，就可以通過Hash這個(gè)間接作用，縮小標(biāo)簽的查找范圍，從而減少執(zhí)行時(shí)間。

(2)

3.2 樣本標(biāo)簽選擇階段

樣本標(biāo)簽選擇階段的主要思想是用哈希函數(shù)h(tid，ri)對(duì)標(biāo)簽進(jìn)行映射，其中，密鑰ri= f/p，f 為幀長(zhǎng)，p為采樣概率。經(jīng)過映射后，幀長(zhǎng)被擴(kuò)展成為f/p，再將擴(kuò)展的f/p均勻分為1/p個(gè)時(shí)間段，然后依次選取時(shí)間段里的標(biāo)簽作為樣本標(biāo)簽。這樣就成功地將所有標(biāo)簽幾乎均等地分成 j 組采樣標(biāo)簽集合S1～Sj。

假設(shè)w、p 和 f 為已知參數(shù)， w為仿真輪數(shù)。當(dāng) w < j 時(shí)，Sj集合中的標(biāo)簽在第 j 輪響應(yīng)，其余輪屬于休眠狀態(tài)；當(dāng)w > j 時(shí)，標(biāo)簽集合Sj的全部響應(yīng)輪數(shù) i 的規(guī)律如式(3)所示：

(3)

式中：a為整數(shù)，其值為[0，wp]間的所有整數(shù)。

當(dāng)標(biāo)簽知道它們的所有響應(yīng)輪數(shù) i 時(shí)，對(duì)應(yīng)的樣本標(biāo)簽集合Sj就會(huì)在第i 輪保持通信狀態(tài)，其他樣本標(biāo)簽集合則保持休眠狀態(tài)。通過通信和休眠兩種狀態(tài)的切換，就達(dá)到了減少標(biāo)簽?zāi)芰块_銷的目的。

3.3 映射階段

本階段對(duì)同一組中的所有標(biāo)簽進(jìn)行映射，對(duì)屬于同一組的不同類的標(biāo)簽依次進(jìn)行映射。一類標(biāo)簽中的任意標(biāo)簽tid選擇時(shí)隙值為1+h(tid,ri)+(d-1)x的時(shí)隙進(jìn)行映射，從而形成映射圖Bi。其中，Bi的長(zhǎng)度是f； h(·)是一個(gè)哈希函數(shù)，它的范圍是[0，x-1]；x為一類標(biāo)簽映射的幀長(zhǎng)；d是本組中每類標(biāo)簽的響應(yīng)次序。根據(jù)每類標(biāo)簽的響應(yīng)次序，可以得到映射圖LBi，其中LBi的長(zhǎng)度是x。根據(jù)Gi、Bi和f 的不同，本文可以有效地縮小標(biāo)簽查找范圍。

3.4 回復(fù)階段

在第i輪中，因?yàn)?LBi(Cid)的長(zhǎng)度為x且一個(gè)標(biāo)簽只能使邏輯位圖中的一個(gè)位為1，所以標(biāo)簽選擇映射圖LBi(Cid)中的任意一位并將其置“ 1 ” 的概率為1/x。而其他類的任意一個(gè)標(biāo)簽將這個(gè)位置“1”的概率為1/f。因此，LBi(Cid)中任意一位保持零的概率為：

(4)

因此，本文運(yùn)用似然函數(shù)L來(lái)觀察此幀中所有zi的值。在k個(gè)LBi中，有：

(5)

(6)

似然函數(shù)求極大值等價(jià)于對(duì)數(shù)似然函數(shù)求極大值。式(5)的對(duì)數(shù)似然函數(shù)形式如下：

(7)

由于ln(L)對(duì)k的導(dǎo)數(shù)存在，故將ln(L)對(duì)k進(jìn)行求導(dǎo)，令其為0，得似然方程：

(8)

對(duì)式(8)結(jié)果進(jìn)行化簡(jiǎn)，得到如下估計(jì)量：

其次，學(xué)生管理者的引導(dǎo)教育作用。學(xué)生管理者對(duì)學(xué)生的要求和引導(dǎo)是培養(yǎng)學(xué)生基本素質(zhì)的關(guān)鍵，如果學(xué)生管理者每一項(xiàng)工作都對(duì)學(xué)生要求嚴(yán)格，精益求精，會(huì)對(duì)學(xué)生產(chǎn)生潛移默化的影響，讓學(xué)生在耳濡目染中形成工匠精神。

(9)

3.5 最優(yōu)參數(shù)估計(jì)階段

(10)

把式(9)代入式(10)，可得：

(11)

因此，閱讀器報(bào)道一個(gè)符合條件的Cid的概率為：

(12)

根據(jù)zi的分布，可以得到下面的式子：

因此有：

(13)

(14)

類似地，式(1)中的第二個(gè)限制如下：

(15)

4 仿真結(jié)果

4.1 設(shè)置參數(shù)

本文的仿真基于PhilipsI-Code的系統(tǒng)，ETBC協(xié)議只需要確定空和非空時(shí)隙，而tshort可以滿足這個(gè)要求，其值為321μs。假設(shè)n=1 000 000，將標(biāo)簽分為G1和G2兩個(gè)組。G1中n=600 000，G2中n=400 000，G1和G2中分別包含2 000類標(biāo)簽。首先，針對(duì)G1隨機(jī)地從[300，600]分別選取y個(gè)值作為y類暢銷類標(biāo)簽的數(shù)量，然后將剩余標(biāo)簽數(shù)量分到其余的非暢銷類標(biāo)簽中, 非暢銷類標(biāo)簽數(shù)量必須低于300。G2中的分組方法和G1類似。G1中每類標(biāo)簽的范圍為(0，600]，Vh=300。G2中每類標(biāo)簽的范圍為(0，400]，Vh=200。在每次仿真中，ETBC計(jì)算wf的最小值，即tshortwf+廣播輪詢請(qǐng)求的時(shí)間，但廣播輪詢請(qǐng)求的時(shí)間可以忽略。

4.2 試驗(yàn)結(jié)果與分析

下面進(jìn)行了多次仿真來(lái)測(cè)試所提出協(xié)議的性能，主要測(cè)試協(xié)議兩方面的性能：時(shí)間有效性和能量有效性。假設(shè)通過分析后查找的是G1中的暢銷類標(biāo)簽，得到下面的仿真數(shù)據(jù)。

4.2.1 時(shí)間有效性

作為對(duì)比，將ETBC協(xié)議和目前最好的閾值分類(threshold-basedclassification，TBC)[3]協(xié)議進(jìn)行比較。TBC協(xié)議是對(duì)所有標(biāo)簽進(jìn)行查找，而ETBC協(xié)議是對(duì)pn個(gè)標(biāo)簽進(jìn)行查找。

不同α、β時(shí)兩種協(xié)議執(zhí)行時(shí)間的變化情況如圖1、圖2所示。仿真結(jié)果表明，ETBC協(xié)議執(zhí)行時(shí)間明顯比TBC協(xié)議小。當(dāng)采集概率p不同時(shí)，執(zhí)行時(shí)間也不同，顯然，p對(duì)執(zhí)行時(shí)間有一定的影響。通過對(duì)比發(fā)現(xiàn)ETBC協(xié)議的性能最好，相比于p=1，ETBC在p=0.5時(shí)其執(zhí)行時(shí)間較小。

圖1 當(dāng)α= 95%，β=5%時(shí)不同p值下兩種協(xié)議的執(zhí)行時(shí)間比較曲線

圖2 當(dāng)α= 90%，β=10%時(shí)不同p值下

從圖1和圖2可以看出，在給定p值情況下，隨著α減小、β增加，TBC和ETBC的執(zhí)行時(shí)間也同時(shí)減少，這是因?yàn)檩^大的α和較小的β意味著對(duì)執(zhí)行時(shí)間有更高的精度要求。

4.2.2 能量有效性

通過分析采樣概率p和執(zhí)行時(shí)間之間的關(guān)系，發(fā)現(xiàn)隨著p的減小，執(zhí)行時(shí)間也減小。當(dāng)閾值Vl固定且p變化時(shí)，得到了表1的數(shù)據(jù)。如表1所示，采樣概率p和執(zhí)行時(shí)間之間存在著一定的關(guān)系，即當(dāng)p∈[0,0.09]時(shí)，隨著采樣概率p的增加，執(zhí)行時(shí)間逐漸減低，而當(dāng)p∈[0.1,1.0]時(shí)，隨著p的增加，執(zhí)行時(shí)間逐漸增加。下面的試驗(yàn)結(jié)果是在α、β、Vl、p四個(gè)參數(shù)不同時(shí)，根據(jù)ETBC方案中的限制條件(1)得出的執(zhí)行時(shí)間。

表1 能量-時(shí)間對(duì)應(yīng)關(guān)系

當(dāng)p∈[0.1，1]時(shí)，執(zhí)行ETBC協(xié)議時(shí)最小的執(zhí)行時(shí)間如表1所示。當(dāng)p∈[0,0.09]時(shí)，可以看出能量和時(shí)間之間存在一種權(quán)衡的關(guān)系。

圖3、圖4比較了ETBC在不同的α、β、Vl下的能量-時(shí)間權(quán)衡圖。當(dāng)α、β的值不同時(shí)，執(zhí)行時(shí)間和采樣概率p也不同，能量-時(shí)間權(quán)衡曲線也不一樣。在圖3、圖4中，曲線最低點(diǎn)的執(zhí)行時(shí)間是最小的，但其能量消耗并不是最小的。

數(shù)據(jù)表明，采樣概率p越小意味著能量開銷越小，但p不能隨便選取，必須符合式(1)的限制。

圖3 能量-時(shí)間權(quán)衡曲線1

圖4 能量-時(shí)間權(quán)衡曲線2

5 結(jié)束語(yǔ)

本文針對(duì)基于有源標(biāo)簽構(gòu)建的RFID系統(tǒng)[11]，提出了一種基于分組機(jī)制的時(shí)間、能量有效的快速暢銷類產(chǎn)品查找協(xié)議ETBC。以前的研究大部分關(guān)注于時(shí)間，而本文首次關(guān)注了查找過程中的能量問題，并發(fā)現(xiàn)了ETBC協(xié)議查找過程中能量和時(shí)間之間存在的一種權(quán)衡關(guān)系。經(jīng)一系列的理論推導(dǎo)和試驗(yàn)表明，ETBC可靈活地選擇參數(shù)，操作簡(jiǎn)單，可在任何精度下查找出暢銷類標(biāo)簽。

相比針對(duì)全部標(biāo)簽進(jìn)行查找的協(xié)議，ETBC協(xié)議的能耗要低很多，特別適用于利用內(nèi)嵌電池供電的有源標(biāo)簽。同時(shí)，ETBC協(xié)議的執(zhí)行時(shí)間也顯著低于TBC協(xié)議。仿真結(jié)果顯示，ETBC可以減少執(zhí)行時(shí)間和能量開銷，是一種高效的方法，即使在高度精確的環(huán)境下也可以執(zhí)行得很好。

[1] 李建坡，姜雪，隋吉生.電動(dòng)汽車充電站RFID智能信息管理系統(tǒng)[J].自動(dòng)化儀表，2014,34(11)：62-65.

[2] 靳祖光，陳超，唐堅(jiān).一種室內(nèi)導(dǎo)盲機(jī)器人的RFID語(yǔ)音交互系統(tǒng)設(shè)計(jì)[J].自動(dòng)化儀表，2014,35(3)：73-76.

[3] Luo W，Qiao Y，Chen S.An efficient protocol for RFID multigroup threshold-based classification[C]∥Proceeding of IEEE Infocom，2013.

[4] Zheng Y，Li M.ZOE:fast cardinality estimation for large-scale RFID Systems[C]∥Proceeding of Infocom，2013.

[5] Li T,Chen S,Ling Y.Identifying the missing tags in a large RFID system[C]∥Proceeding of ACM Mobihoc，2010.

[6] Kodialam M，Lau W C，Nandagopal T.Identifying RFID tag categories in linear time[C]∥Proceeding of ACM Mobihoc，2009.

[7] Sheng B，Chiu C T，Li Q，et al.Finding popular categories for RFID Tags[C]∥Proceeding ACM Mobihoc，2008.

[8] Li T，Wu S，Chen S.Energy efficient algorithms for the RFID estimation problem[C]∥Proceeding of IEEE Infocom，2010.

[9] Qiao Y,Chen S,Li T.Energy-efficient polling protocols in RFID Systems[C]∥Proceeding of ACM Mobihoc，2011.

[10]Luo W，Chen S，Li T，et al.Probabilistic missing-tag detection and energy-time tradeoff in large-scale RFID systems[C]∥Proceeding of ACM Mobihoc，2012.

[11]胡文鋒，王玲玲，翁紹捷.RFID技術(shù)在高校實(shí)驗(yàn)室設(shè)備管理中的應(yīng)用[J].科技資訊，2011(32)：33-34.

Finding Bestsellers Categories by Using RFID Technology

In the RFID systems that constructed based on active tags, how to find the bestsellers categories in both time and energy efficient manner is an important research topic. Aiming at the multi-reader RFID system, for the first time, the energy issue in process of finding bestseller categories is researched, and the enhanced threshold-based classification(ETBC) finding protocol based on grouping mechanism is proposed. The core ideas of this protocol is using grouping mechanism, to make the tags adhered on same category products in a group, and in accordance with the finding requirement to find out the sample tag in corresponding group; and to find the bestsellers categories tags based on the reply messages from the sample tag. The theoretical analysis and simulation result all indicate the effectiveness of the ETBC protocol. Comparing with the finding protocol for all of the tags, ETBS protocol features lower power consumption, the execution time of protocol is also greatly reduced.

Radio frequency identification(RFID) Active tags Energy Grouping mechanism Wireless communication

國(guó)家自然科學(xué)基金青年科學(xué)基金資助項(xiàng)目(編號(hào)：61303207)；

國(guó)家自然科學(xué)基金面上基金資助項(xiàng)目(編號(hào)：61371062)；

教育部2012年高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金聯(lián)合資助項(xiàng)目(編號(hào)：20121402120020)；

山西省科學(xué)技術(shù)發(fā)展項(xiàng)目工業(yè)部分基金資助項(xiàng)目(編號(hào)：20120321024-01)；

山西省國(guó)際合作基金資助項(xiàng)目(編號(hào)：2012081031)；

2012年山西省留學(xué)回國(guó)人員科技活動(dòng)擇優(yōu)基金資助項(xiàng)目；

2013年山西省留學(xué)回國(guó)人員科研基金資助項(xiàng)目(編號(hào)：2013-032)。

閆麗娟(1989-)，女，現(xiàn)為太原理工學(xué)校信息與通信工程專業(yè)在讀碩士研究生；主要從事RFID技術(shù)、無(wú)線傳感器網(wǎng)絡(luò)技術(shù)的研究。

TN911

A

10.16086/j.cnki.issn1000-0380.201505012

修改稿收到日期：2014-10-14。