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

閆麗娟 趙菊敏 李燈熬

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

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

閆麗娟 趙菊敏 李燈熬

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

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

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

0 引言

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

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

1 系統(tǒng)模型

本文考慮的RFID系統(tǒng)由3部分組成：后臺服務(wù)器、一組RFID閱讀器以及大量的RFID標(biāo)簽。假設(shè)后臺服務(wù)器存儲著系統(tǒng)中所有標(biāo)簽的信息，且閱讀器和標(biāo)簽之間的通信采用幀-時隙 ALOHA協(xié)議。在執(zhí)行協(xié)議的過程中，閱讀器首先向標(biāo)簽發(fā)送查詢命令，然后標(biāo)簽接收命令并返回相應(yīng)的回復(fù)信息。每一輪響應(yīng)中，閱讀器廣播查詢命令和當(dāng)前幀的時隙個數(shù)，每個標(biāo)簽通過Hash函數(shù)運(yùn)算，隨機(jī)選擇此幀中的一個時隙對閱讀器進(jìn)行回復(fù)。具體來說，在每個查詢幀的開始，閱讀器廣播兩個參數(shù)：幀大小f和一個隨機(jī)數(shù)ri，其中f也就是幀包含的時隙個數(shù)，而ri用來幫助標(biāo)簽在該幀中通過Hash函數(shù)選擇一個時隙對閱讀器進(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)中的兩個限制條件，其中Vh、Vl、α和β為給定的已知參數(shù)，Vh和Vl為閾值，α和β為概率值。任何一類標(biāo)簽數(shù)量超過Vh時被報道的概率至少為α，同時任何一類標(biāo)簽數(shù)量低于Vl時被報道的概率最多為β。

(1)

3 ETBC協(xié)議

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

3.1 分組階段

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

(2)

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

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

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

(3)

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

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

3.3 映射階段

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

3.4 回復(fù)階段

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

(4)

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

(5)

(6)

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

(7)

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

(8)

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

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

(9)

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

(10)

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

(11)

因此，閱讀器報道一個符合條件的Cid的概率為：

(12)

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

因此有：

(13)

(14)

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

(15)

4 仿真結(jié)果

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

本文的仿真基于PhilipsI-Code的系統(tǒng)，ETBC協(xié)議只需要確定空和非空時隙，而tshort可以滿足這個要求，其值為321μs。假設(shè)n=1 000 000，將標(biāo)簽分為G1和G2兩個組。G1中n=600 000，G2中n=400 000，G1和G2中分別包含2 000類標(biāo)簽。首先，針對G1隨機(jī)地從[300，600]分別選取y個值作為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計算wf的最小值，即tshortwf+廣播輪詢請求的時間，但廣播輪詢請求的時間可以忽略。

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

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

4.2.1 時間有效性

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

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

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

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

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

4.2.2 能量有效性

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

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

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

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

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

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

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

5 結(jié)束語

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

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

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

[2] 靳祖光，陳超，唐堅.一種室內(nèi)導(dǎo)盲機(jī)器人的RFID語音交互系統(tǒng)設(shè)計[J].自動化儀表，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ī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

國家自然科學(xué)基金青年科學(xué)基金資助項目(編號：61303207)；

國家自然科學(xué)基金面上基金資助項目(編號：61371062)；

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

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

山西省國際合作基金資助項目(編號：2012081031)；

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

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

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

TN911

A

10.16086/j.cnki.issn1000-0380.201505012

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