基于緩存替換算法的EPCIS查詢機制

孔德瀚，邱曉麗,劉永山

(1．燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島 066004；2．河北傳媒學(xué)院 信息技術(shù)與文化管理學(xué)院，河北 石家莊 050071)

?

基于緩存替換算法的EPCIS查詢機制

孔德瀚1，邱曉麗2,劉永山1

(1．燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島 066004；2．河北傳媒學(xué)院 信息技術(shù)與文化管理學(xué)院，河北 石家莊 050071)

針對物聯(lián)網(wǎng)應(yīng)用時對EPCIS(electronic product Code information services)數(shù)據(jù)庫的大量的查詢請求，在已有的EPCIS查詢機制的研究基礎(chǔ)上，提出了一種基于緩存的EPCIS查詢機制．通過減少對EPCIS數(shù)據(jù)庫的訪問次數(shù)以縮短請求響應(yīng)時間，提出了一種基于代價函數(shù)的緩存替換算法．研究結(jié)果表明，與現(xiàn)有的一些傳統(tǒng)緩存替換算法相比，本文給出的緩存替換算法能進一步提高EPCIS 查詢模塊的效率．

EPCIS查詢機制；緩存；代價函數(shù)；替換算法

在信息技術(shù)高速發(fā)展的今天，物聯(lián)網(wǎng)已作為實現(xiàn)“智慧地球”的一種關(guān)鍵技術(shù)，被越來越多的企業(yè)、專家和學(xué)者對其加以研究和應(yīng)用．EPCIS(electronic product Code information services EPC信息服務(wù))作為物聯(lián)網(wǎng)中重要的組成部分，需要頻繁通過網(wǎng)絡(luò)交換EPC相關(guān)數(shù)據(jù)，追蹤和管理產(chǎn)品信息[1-2]，其中涉及到的大量查詢請求，需要EPCIS存儲和處理海量數(shù)據(jù)，這是對EPCIS查詢機制響應(yīng)能力的巨大挑戰(zhàn)，所以，通過對EPCIS查詢機制的研究來提高查詢效率意義重大．

目前，對EPCIS查詢機制進行的探討和研究大都建立在EPC global組織提出的EPCIS規(guī)范的基礎(chǔ)之上[3]，主要研究成果[4-6]有：北京大學(xué)基于SaaS模式的RFID公共服務(wù)平臺的研究，在國內(nèi)首次實現(xiàn)了完整的信息查詢功能；上海交通大學(xué)研究了具有物品追蹤功能的RFID公共服務(wù)體系，一個輕量級的信息服務(wù)查詢機制；華中科技大學(xué)研究了經(jīng)過防火墻后允許客戶端應(yīng)用程序和服務(wù)提供端在Internet上進行通訊交互的EPCIS機制．但是，對如何進一步提高EPCIS查詢效率，使EPCIS模塊更加適應(yīng)物聯(lián)網(wǎng)快速發(fā)展需求方面并沒有過深入研究．

針對上述情況，為了進一步提高EPCIS的查詢效率，使產(chǎn)品信息的追蹤和交換更加方便、快捷，促進物聯(lián)網(wǎng)技術(shù)的快速發(fā)展，探討了基于緩存替換算法的EPCIS查詢機制．

1 一種基于緩存的EPCIS查詢機制

EPCIS擁有查詢接口和返回接口與客戶端應(yīng)用程序進行交互，當(dāng)指定一個EPC編碼來查詢與之對應(yīng)的產(chǎn)品的詳細(xì)信息時，涉及到EPCIS系統(tǒng)的運行原理圖，如圖1模塊所示．

圖1 EPCIS運行原理Fig 1 EPCIS runs schematic

由EPCIS運行原理圖可以看出當(dāng)查詢EPC編碼產(chǎn)品信息時，首先由客戶端應(yīng)用程序發(fā)送SOAP查詢請求給應(yīng)用服務(wù)器；服務(wù)器響應(yīng)此查詢請求后，由SOAP查詢引擎將程序指向查詢模塊中的事件查詢接口代理模塊；查詢請求經(jīng)過解析后，將要進行的查詢以及參數(shù)信息傳遞給查詢產(chǎn)生模塊，并在EPCIS存儲數(shù)據(jù)庫中進行相應(yīng)查詢；查詢結(jié)束后，查詢結(jié)果先傳遞到事件查詢接口代理模塊，再由此模塊返回給客戶端應(yīng)用程序．

圖2 EPCIS查詢模塊抽象模型Fig 2 EPCIS query module abstract model Figure

圖2所示的EPCIS查詢模塊抽象模型圖是將EPC global標(biāo)準(zhǔn)所提出的EPCIS查詢機制模型抽象為客戶端應(yīng)用程序?qū)PCIS存儲數(shù)據(jù)庫的查詢操作．在數(shù)據(jù)庫應(yīng)用系統(tǒng)中，體現(xiàn)其性能好壞的一個重要指標(biāo)就是查詢效率，不同查詢方式或者數(shù)據(jù)庫設(shè)置都會影響查詢的效率．此外，長時間、頻繁地查詢訪問數(shù)據(jù)庫也會造成數(shù)據(jù)庫查詢的性能損耗．

緩存(Cache)是介于數(shù)據(jù)庫與客戶端應(yīng)用程序之間臨時存放數(shù)據(jù)庫中數(shù)據(jù)的存儲器，具有很高的數(shù)據(jù)交換速度，因此在應(yīng)用程序和查詢數(shù)據(jù)庫之間加入緩存是改善訪問效率的一種有效手段．緩存中存放的是查詢結(jié)果的數(shù)據(jù)集，應(yīng)用程序在進行重復(fù)查詢時，可以直接從緩存中將數(shù)據(jù)讀寫出來，只有首次查詢時結(jié)果集需要通過查詢EPCIS數(shù)據(jù)庫得到，這樣就避免了頻繁訪問數(shù)據(jù)庫進行查詢．因此在理論上可以提高EPCIS系統(tǒng)查詢效率，避免數(shù)據(jù)庫查詢的服務(wù)器性能損耗．另外，在程序設(shè)定的時間或者遇到指定的特殊事件時，緩存會更新數(shù)據(jù)．

基于緩存的EPCIS查詢模塊結(jié)構(gòu)圖如圖3所示.

圖3 基于緩存的EPCIS查詢模塊結(jié)構(gòu)Fig.3 Cache-based EPCIS query module structure diagram

2 代價函數(shù)緩存替換算法

緩存替換算法的關(guān)鍵是找到緩存中那些被訪問可能性較低、數(shù)據(jù)檢索延遲較長、更新頻率高且需要較大內(nèi)存的結(jié)果集，并將其替換出內(nèi)存．因此，受緩存大小的限制，為了保證較高的緩存命中率，構(gòu)建一種更有效的緩存替換算法尤為重要.關(guān)于緩存替換算法，已經(jīng)有很多學(xué)者進行了深入的研究，提出了多種算法[7-9]，如LRU、SIZE、GD、HYBRID、LRV等，然而上述算法都各有利弊，在此引入代價函數(shù)緩存替換算法．

2.1 代價函數(shù)

為 EPCIS緩存中的查詢對象定義代價函數(shù)Ci(t)：

(1)

式(1)中Si表示第i個緩存對象占用空間的大??；mi表示查詢時訪問緩存結(jié)果集的總次數(shù)；Cti表示通過緩存結(jié)果集檢索數(shù)據(jù)需要的時間延遲；P表示使用率，體現(xiàn)的是緩存對象在下一次被訪問的可能性大?。?/p>

假設(shè)處理最后一次查詢請求訪問緩存后經(jīng)過的時間為tc，第k次和第k-1次訪問緩存的時間差為tk，第k次和第k-1次訪問緩存后的平均訪問時間差分別為λk和λk-1，則

λk=αtk+(1-α)λk-1，

(2)

其中，α為設(shè)定的參數(shù)(α≥0.5)，λ是對當(dāng)前緩存對象訪問率的反映．則緩存對象被訪問的概率為

(3)

其中λm為最后一次查詢請求時訪問緩存后的平均訪問時間差.

所以，緩存對象經(jīng)過時間tc后再次被訪問的概率為

(4)

緩存對象下一次被訪問時需要經(jīng)歷的平均時間差為

(5)

則平均使用率為

(6)

2.2 算法的工作流程及代碼實現(xiàn)

代價函數(shù)緩存替換算法工作流程如下：

1) 當(dāng)需要緩存新的查詢結(jié)果集時，依照代價函數(shù)公式計算函數(shù)值，依據(jù)函數(shù)值大小對緩存空間中的對象進行排序；

2) 依據(jù)新緩存對象的大小檢查是否有足夠的緩存空間，如果空間足夠則直接將緩存對象加載更新．如果空間不足，則使用替換算法重復(fù)執(zhí)行步驟3)，直到有足夠的緩存剩余空間加載更新緩存對象為止；

3)將上述代價函數(shù)值最小的緩存對象依次替換出來．

算法的偽代碼如下：

if(CRZ >= querriedSize)

{

add(querriedSet[i]) to (CacheList)

CRZ -= querriedSize

return CacheList

}

else

{

Call EachCostValaue of CacheList(C[i])

Sort (CacheList) by (C[i])

do

{

Erase (CacheList[1]，CacheList)

CRZ += querriedSize

}while(CRZ < querriedSize)

add(querriedSet[i]) to (CacheList)

CRZ -= querriedSize

return CacheList

}

3 仿真實驗及仿真結(jié)果

實驗環(huán)境采用Ubuntu系統(tǒng)平臺，Apache http server 服務(wù)器，MySQL6.0數(shù)據(jù)庫管理系統(tǒng)，Memcached緩存系統(tǒng).在此環(huán)境設(shè)置下，用C++語言編程，實現(xiàn)基于代價函數(shù)的緩存替換算法運算，并通過緩存仿真軟件分別測試：當(dāng)EPCIS查詢機制發(fā)送數(shù)據(jù)查詢請求時，不同算法的命中率以及加入緩存機制與直接從數(shù)據(jù)庫中讀取數(shù)據(jù)相比，響應(yīng)時間的快慢．

3.1 緩存算法性能評價指標(biāo)

緩存算法的評價指標(biāo)主要是訪問延遲、命中率和字節(jié)命中率．當(dāng)用戶對數(shù)據(jù)庫發(fā)出查詢請求時，如果要查詢的數(shù)據(jù)在緩存空間里，則稱為本次請求命中；反之，如果要查詢的數(shù)據(jù)不在緩存空間里，需要查詢模塊通過查詢EPCIS數(shù)據(jù)庫才能得到數(shù)據(jù)，則稱為本次請求缺失．查詢的數(shù)據(jù)命中的次數(shù)占總的請求次數(shù)的比例稱為命中率．緩存空間中已命中的字節(jié)數(shù)占所有查詢結(jié)果集字節(jié)數(shù)的比例稱字節(jié)命中率．

如果要查詢的數(shù)據(jù)已命中，那么從緩存中讀取數(shù)據(jù)的時間很短，訪問延遲可以忽略不計．若要查詢的數(shù)據(jù)沒有被命中，查詢模塊通過查詢EPCIS數(shù)據(jù)庫讀取數(shù)據(jù)時就會因為數(shù)據(jù)大小和網(wǎng)絡(luò)的影響產(chǎn)生訪問延遲．所以命中率越高，訪問延遲就越?。瑯樱彺嬷械淖止?jié)命中率越高，緩存空間的利用率越高，需要通過訪問EPCIS數(shù)據(jù)庫傳輸?shù)淖止?jié)數(shù)越少，訪問延遲也就越?。虼耍岣呔彺婷新?、字節(jié)命中率是提高EPCIS查詢機制效率的有效途徑．

綜合考慮了緩存對象的大小、被訪問的總次數(shù)、使用率、獲取時間這幾個影響查詢效率的主要因素，代價函數(shù)式可以反映出被命中的緩存對象歷史軌跡，且函數(shù)簡單，容易計算．

3.2 仿真實驗結(jié)果與分析

緩存仿真器里輸入的數(shù)據(jù)來自DEC實驗室訪問日志記錄，分別設(shè)置緩存空間大小為總文檔大小的1%、5%，直到40%．當(dāng)緩存大小繼續(xù)增大至總文檔大小的40%時，由于緩存空間遠(yuǎn)遠(yuǎn)大于緩存需要的空間，上述3種緩存替換算法的字節(jié)性能及命中率都趨于一致．實驗在具有相同緩存大小、相同請求輸入序列的基礎(chǔ)上對代價函數(shù)(CECRA)、SIZE與HYBRID 3種緩存替換算法的性能進行了對比實驗，將程序運行輸出的各種算法的命中率、緩存命中率畫圖如圖4、圖5所示．

圖4 命中率與緩存大小的關(guān)系Fig.4 Relation of hit rate and cache size

圖5 字節(jié)命中率與緩存大小的關(guān)系Fig.5 Relation of byte hit rate and cache size

由圖4、圖5可以看出，與SIZE和HYBRID基于函數(shù)的緩存替換算法相比，基于代價函數(shù)的緩存替換算法提高了緩存對象的命中率和字節(jié)命中率．將這種替換算法應(yīng)用到基于緩存的EPCIS查詢模塊中，可以進一步將EPCIS的查詢效率提高．

4 結(jié)論

用戶查詢EPC信息時，緩存空間的加入可以大大降低對數(shù)據(jù)庫的訪問頻率，且由于從緩存中存取數(shù)據(jù)的速度明顯高于訪問數(shù)據(jù)庫，所以在EPCIS查詢模塊中加入緩存機制對EPCIS查詢效率的提升有很大作用．在已有的緩存替換算法基礎(chǔ)上進行研究與改進，通過提高緩存的性能進一步提高EPCIS查詢的效率．根據(jù)仿真實驗數(shù)據(jù)可以得出，基于代價函數(shù)的緩存替換算法可以提高緩存命中率和字節(jié)命中率，加入緩存后，可以進一步減少應(yīng)用程序訪問數(shù)據(jù)庫的次數(shù)，縮短訪問延遲時間．由此可見，基于緩存的EPCIS查詢機制與標(biāo)準(zhǔn)的EPCIS查詢機制相比，緩存替換算法在提高查詢效率方面具有明顯優(yōu)勢．

[1] PILAR M L，PEDRO M，JOSEMARIA M S，et al．An efficient distributed discovery service for EPCglobal network in nested package scenarios[J].Journal of Network and Computer Applications，2011，34(3): 925-937.DOI:10.1016/j.jnca.2010.04.018.

[2] TAEWOO N，KEUNHYUK Y.Business-aware framework for supporting RFID-enabled applications[J].Journal of Network and Computer Applications,2011，34(3): 958-971.

[3] 李佶．EPC網(wǎng)絡(luò)信息服務(wù)查詢機制研究與開發(fā)[D].上海:上海交通大學(xué)，2012. LI J.Research and realization of information service query mechanism in EPC network[D].Shanghai: Shanghai Jiao Tong University,2012.

[4] ZHAO W，LI X P，LIU D X，et al.SaaS mode based region RFID public service platform[Z].3rd International Conference on Convergence and Hybrid Information Technology，2008．DOI: 10.1109/ICCIT.2008.88.

[5] 傅嘯．面向防偽應(yīng)用的 RFID 公共服務(wù)平臺安全技術(shù)研究與開發(fā)[D]．上海：上海交通大學(xué)，2011. FU X.Research and developing for security technology of RFID public services infrastructure to anti-counterfeiting [D].Shanghai: Shanghai Jiao Tong University,2011.

[6] 李再進．EPC網(wǎng)絡(luò)中信息服務(wù)的設(shè)計與應(yīng)用研究[D]．武漢：華中科技大學(xué)，2005. LI Z J.The research of design and application of information service in the EPC network[D].Wuhan: Huazhong University of Science and Technology,2005.

[7] CAO P ,IRANI S.Cost-aware WWW proxy caching algorithms[J].Proceedings of the Usenix Symposium on Internet Technology and Systems，1997，12(97): 193-206.

[8] PODLIPNIG S，B?SZ?RMENYI L.A survey of web cache replacement strategies[J].ACM Computing Surveys (CSUR)，2003，35(4):374-398.DOI: 10.1145/954339.954341.

[9] BATALIN M A，SUKHATME G S.The analysis of an efficient algorithm for robot coverage and exploration based on sensor network deployment[Z].The 2005 IEEE International Conference on Robotics and Automation.Barcelona，Spain ,2005.DOI: 10.1109/ ROBOT.2005.1570648.

(責(zé)任編輯：孟素蘭)

On query mechanism of EPCIS based on cost function of cache replacement algorithms

KONG Dehan1,QIU Xiaoli2,LIU Yongshan1

(1.College of Information Science and Engineering,Yanshan University,Qinhuangdao 066004,China;2.College of Information Technology and Cultural Management Insitute,Hebei Institute of Communications,Shijiazhuang 050071,China)

With the increasing requests to the EPCIS for application in internet of things,we put forward a cache based query mechanism for EPCIS on the basis of exisiting query mechanism.The response time of query request can be shortened，when the counts of client application access to the EPCIS database is reduced.In addition，we also get a replacement algorithm based on cost function.The simulation experimental results show the proposed replacement algorithm has better performance than some other cache replacement algorithms which further improves the efficiency of the EPCIS query module.

EPCIS query mechanism；cache；cost function；replacement algorithm

10.3969/j.issn.1000-1565.2016.05.015

2016-03-13

河北省人力資源和社會保障研究課題(JRS-2015-3051)

孔德瀚(1985—)，男，遼寧大連人，燕山大學(xué)在讀博士研究生，主要從事空間數(shù)據(jù)庫和虛擬現(xiàn)實研究．

邱曉麗(1983—)，女，河北清河人，河北傳媒學(xué)院講師，主要從事物聯(lián)網(wǎng)技術(shù)與計算機理論研究． E-mail:qiuxiaoli005900@126.com

TP301.6

A

1000-1565(2016)05-0541-06