基于缓存替换算法的EPCIS查询机制

孔德瀚，邱晓丽,刘永山

(1．燕山大学 信息科学与工程学院，河北 秦皇岛 066004；2．河北传媒学院 信息技术与文化管理学院，河北 石家庄 050071)



基于缓存替换算法的EPCIS查询机制

孔德瀚1，邱晓丽2,刘永山1

(1．燕山大学 信息科学与工程学院，河北 秦皇岛 066004；2．河北传媒学院 信息技术与文化管理学院，河北 石家庄 050071)

针对物联网应用时对EPCIS(electronic product Code information services)数据库的大量的查询请求，在已有的EPCIS查询机制的研究基础上，提出了一种基于缓存的EPCIS查询机制．通过减少对EPCIS数据库的访问次数以缩短请求响应时间，提出了一种基于代价函数的缓存替换算法．研究结果表明，与现有的一些传统缓存替换算法相比，本文给出的缓存替换算法能进一步提高EPCIS 查询模块的效率．

EPCIS查询机制；缓存；代价函数；替换算法

在信息技术高速发展的今天，物联网已作为实现“智慧地球”的一种关键技术，被越来越多的企业、专家和学者对其加以研究和应用．EPCIS(electronic product Code information services EPC信息服务)作为物联网中重要的组成部分，需要频繁通过网络交换EPC相关数据，追踪和管理产品信息[1-2]，其中涉及到的大量查询请求，需要EPCIS存储和处理海量数据，这是对EPCIS查询机制响应能力的巨大挑战，所以，通过对EPCIS查询机制的研究来提高查询效率意义重大．

目前，对EPCIS查询机制进行的探讨和研究大都建立在EPC global组织提出的EPCIS规范的基础之上[3]，主要研究成果[4-6]有：北京大学基于SaaS模式的RFID公共服务平台的研究，在国内首次实现了完整的信息查询功能；上海交通大学研究了具有物品追踪功能的RFID公共服务体系，一个轻量级的信息服务查询机制；华中科技大学研究了经过防火墙后允许客户端应用程序和服务提供端在Internet上进行通讯交互的EPCIS机制．但是，对如何进一步提高EPCIS查询效率，使EPCIS模块更加适应物联网快速发展需求方面并没有过深入研究．

针对上述情况，为了进一步提高EPCIS的查询效率，使产品信息的追踪和交换更加方便、快捷，促进物联网技术的快速发展，探讨了基于缓存替换算法的EPCIS查询机制．

1 一种基于缓存的EPCIS查询机制

EPCIS拥有查询接口和返回接口与客户端应用程序进行交互，当指定一个EPC编码来查询与之对应的产品的详细信息时，涉及到EPCIS系统的运行原理图，如图1模块所示．

图1 EPCIS运行原理Fig 1 EPCIS runs schematic

由EPCIS运行原理图可以看出当查询EPC编码产品信息时，首先由客户端应用程序发送SOAP查询请求给应用服务器；服务器响应此查询请求后，由SOAP查询引擎将程序指向查询模块中的事件查询接口代理模块；查询请求经过解析后，将要进行的查询以及参数信息传递给查询产生模块，并在EPCIS存储数据库中进行相应查询；查询结束后，查询结果先传递到事件查询接口代理模块，再由此模块返回给客户端应用程序．

图2 EPCIS查询模块抽象模型Fig 2 EPCIS query module abstract model Figure

图2所示的EPCIS查询模块抽象模型图是将EPC global标准所提出的EPCIS查询机制模型抽象为客户端应用程序对EPCIS存储数据库的查询操作．在数据库应用系统中，体现其性能好坏的一个重要指标就是查询效率，不同查询方式或者数据库设置都会影响查询的效率．此外，长时间、频繁地查询访问数据库也会造成数据库查询的性能损耗．

缓存(Cache)是介于数据库与客户端应用程序之间临时存放数据库中数据的存储器，具有很高的数据交换速度，因此在应用程序和查询数据库之间加入缓存是改善访问效率的一种有效手段．缓存中存放的是查询结果的数据集，应用程序在进行重复查询时，可以直接从缓存中将数据读写出来，只有首次查询时结果集需要通过查询EPCIS数据库得到，这样就避免了频繁访问数据库进行查询．因此在理论上可以提高EPCIS系统查询效率，避免数据库查询的服务器性能损耗．另外，在程序设定的时间或者遇到指定的特殊事件时，缓存会更新数据．

基于缓存的EPCIS查询模块结构图如图3所示.

图3 基于缓存的EPCIS查询模块结构Fig.3 Cache-based EPCIS query module structure diagram

2 代价函数缓存替换算法

缓存替换算法的关键是找到缓存中那些被访问可能性较低、数据检索延迟较长、更新频率高且需要较大内存的结果集，并将其替换出内存．因此，受缓存大小的限制，为了保证较高的缓存命中率，构建一种更有效的缓存替换算法尤为重要.关于缓存替换算法，已经有很多学者进行了深入的研究，提出了多种算法[7-9]，如LRU、SIZE、GD、HYBRID、LRV等，然而上述算法都各有利弊，在此引入代价函数缓存替换算法．

2.1 代价函数

为 EPCIS缓存中的查询对象定义代价函数Ci(t)：

(1)

式(1)中Si表示第i个缓存对象占用空间的大小；mi表示查询时访问缓存结果集的总次数；Cti表示通过缓存结果集检索数据需要的时间延迟；P表示使用率，体现的是缓存对象在下一次被访问的可能性大小．

假设处理最后一次查询请求访问缓存后经过的时间为tc，第k次和第k-1次访问缓存的时间差为tk，第k次和第k-1次访问缓存后的平均访问时间差分别为λk和λk-1，则

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

(2)

其中，α为设定的参数(α≥0.5)，λ是对当前缓存对象访问率的反映．则缓存对象被访问的概率为

(3)

其中λm为最后一次查询请求时访问缓存后的平均访问时间差.

所以，缓存对象经过时间tc后再次被访问的概率为

(4)

缓存对象下一次被访问时需要经历的平均时间差为

(5)

则平均使用率为

(6)

2.2 算法的工作流程及代码实现

代价函数缓存替换算法工作流程如下：

1) 当需要缓存新的查询结果集时，依照代价函数公式计算函数值，依据函数值大小对缓存空间中的对象进行排序；

2) 依据新缓存对象的大小检查是否有足够的缓存空间，如果空间足够则直接将缓存对象加载更新．如果空间不足，则使用替换算法重复执行步骤3)，直到有足够的缓存剩余空间加载更新缓存对象为止；

3)将上述代价函数值最小的缓存对象依次替换出来．

算法的伪代码如下：

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 仿真实验及仿真结果

实验环境采用Ubuntu系统平台，Apache http server 服务器，MySQL6.0数据库管理系统，Memcached缓存系统.在此环境设置下，用C++语言编程，实现基于代价函数的缓存替换算法运算，并通过缓存仿真软件分别测试：当EPCIS查询机制发送数据查询请求时，不同算法的命中率以及加入缓存机制与直接从数据库中读取数据相比，响应时间的快慢．

3.1 缓存算法性能评价指标

缓存算法的评价指标主要是访问延迟、命中率和字节命中率．当用户对数据库发出查询请求时，如果要查询的数据在缓存空间里，则称为本次请求命中；反之，如果要查询的数据不在缓存空间里，需要查询模块通过查询EPCIS数据库才能得到数据，则称为本次请求缺失．查询的数据命中的次数占总的请求次数的比例称为命中率．缓存空间中已命中的字节数占所有查询结果集字节数的比例称字节命中率．

如果要查询的数据已命中，那么从缓存中读取数据的时间很短，访问延迟可以忽略不计．若要查询的数据没有被命中，查询模块通过查询EPCIS数据库读取数据时就会因为数据大小和网络的影响产生访问延迟．所以命中率越高，访问延迟就越小．同样，缓存中的字节命中率越高，缓存空间的利用率越高，需要通过访问EPCIS数据库传输的字节数越少，访问延迟也就越小．因此，提高缓存命中率、字节命中率是提高EPCIS查询机制效率的有效途径．

综合考虑了缓存对象的大小、被访问的总次数、使用率、获取时间这几个影响查询效率的主要因素，代价函数式可以反映出被命中的缓存对象历史轨迹，且函数简单，容易计算．

3.2 仿真实验结果与分析

缓存仿真器里输入的数据来自DEC实验室访问日志记录，分别设置缓存空间大小为总文档大小的1%、5%，直到40%．当缓存大小继续增大至总文档大小的40%时，由于缓存空间远远大于缓存需要的空间，上述3种缓存替换算法的字节性能及命中率都趋于一致．实验在具有相同缓存大小、相同请求输入序列的基础上对代价函数(CECRA)、SIZE与HYBRID 3种缓存替换算法的性能进行了对比实验，将程序运行输出的各种算法的命中率、缓存命中率画图如图4、图5所示．

图4 命中率与缓存大小的关系Fig.4 Relation of hit rate and cache size

图5 字节命中率与缓存大小的关系Fig.5 Relation of byte hit rate and cache size

由图4、图5可以看出，与SIZE和HYBRID基于函数的缓存替换算法相比，基于代价函数的缓存替换算法提高了缓存对象的命中率和字节命中率．将这种替换算法应用到基于缓存的EPCIS查询模块中，可以进一步将EPCIS的查询效率提高．

4 结论

用户查询EPC信息时，缓存空间的加入可以大大降低对数据库的访问频率，且由于从缓存中存取数据的速度明显高于访问数据库，所以在EPCIS查询模块中加入缓存机制对EPCIS查询效率的提升有很大作用．在已有的缓存替换算法基础上进行研究与改进，通过提高缓存的性能进一步提高EPCIS查询的效率．根据仿真实验数据可以得出，基于代价函数的缓存替换算法可以提高缓存命中率和字节命中率，加入缓存后，可以进一步减少应用程序访问数据库的次数，缩短访问延迟时间．由此可见，基于缓存的EPCIS查询机制与标准的EPCIS查询机制相比，缓存替换算法在提高查询效率方面具有明显优势．

[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网络信息服务查询机制研究与开发[D].上海:上海交通大学，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] 傅啸．面向防伪应用的 RFID 公共服务平台安全技术研究与开发[D]．上海：上海交通大学，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网络中信息服务的设计与应用研究[D]．武汉：华中科技大学，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.

(责任编辑：孟素兰)

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—)，男，辽宁大连人，燕山大学在读博士研究生，主要从事空间数据库和虚拟现实研究．

邱晓丽(1983—)，女，河北清河人，河北传媒学院讲师，主要从事物联网技术与计算机理论研究． E-mail:qiuxiaoli005900@126.com

TP301.6

A

1000-1565(2016)05-0541-06