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

閆麗娟 趙菊敏 李燈熬

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

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

閆麗娟 趙菊敏 李燈熬

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

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

RFID 有源標簽 能量 分組機制 無線通信

0 引言

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

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

1 系統(tǒng)模型

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

2 問題定義

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

(1)

3 ETBC協(xié)議

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

3.1 分組階段

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

(2)

3.2 樣本標簽選擇階段

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

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

(3)

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

當標簽知道它們的所有響應輪數(shù) i 時，對應的樣本標簽集合Sj就會在第i 輪保持通信狀態(tài)，其他樣本標簽集合則保持休眠狀態(tài)。通過通信和休眠兩種狀態(tài)的切換，就達到了減少標簽能量開銷的目的。

3.3 映射階段

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

3.4 回復階段

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

(4)

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

(5)

(6)

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

(7)

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

(8)

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

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

(9)

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

(10)

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

(11)

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

(12)

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

因此有：

(13)

(14)

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

(15)

4 仿真結(jié)果

4.1 設置參數(shù)

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

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

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

4.2.1 時間有效性

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

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

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

圖2 當α= 90%，β=10%時不同p值下

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

4.2.2 能量有效性

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

表1 能量-時間對應關系

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

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

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

圖3 能量-時間權衡曲線1

圖4 能量-時間權衡曲線2

5 結(jié)束語

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

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

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

[2] 靳祖光，陳超，唐堅.一種室內(nèi)導盲機器人的RFID語音交互系統(tǒng)設計[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技術在高校實驗室設備管理中的應用[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

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

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

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

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

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

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

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

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

TN911

A

10.16086/j.cnki.issn1000-0380.201505012

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