基于近似匹配的移动边缘计算缓存管理方法

doi:10.11896/jsjkx.200800215

计算机科学 ›› 2021, Vol. 48 ›› Issue (1): 96-102.doi: 10.11896/jsjkx.200800215

基于近似匹配的移动边缘计算缓存管理方法

郦睿翔, 毛莺池, 郝帅

河海大学计算机与信息学院南京 211100

收稿日期:2020-08-30 修回日期:2020-11-07 出版日期:2021-01-15 发布日期:2021-01-15
通讯作者: 毛莺池(yingchimao@hhu.edu.com)
作者简介:loye317@sina.com
基金资助:
国家重点研发计划(2018YFC0407105);国家自然科学基金重点项目(61832005);华能集团重点研发课题(HNKJ17-21)

Cache Management Method in Mobile Edge Computing Based on Approximate Matching

LI Rui-xiang, MAO Ying-chi, HAO Shuai

School of Computer and Information,Hohai University,Nanjing 211100,China

Received:2020-08-30 Revised:2020-11-07 Online:2021-01-15 Published:2021-01-15
About author:LI Rui-xiang,born in 1996,master candidate,is a student member of China Computer Federation.His main research interests include edge computing,and federated learning.
MAO Ying-chi,born in 1976,Ph.D,professor,is a senior member of China Computer Federation.Her main research interests include cloud computing and edge computing,mobile sen-sing systems and internet of things.
Supported by:
National Key R&D Program of China(2018YFC0407105),Key Project of National Nature Science Foundation of China(61832005) and Key Technology Project of China Huaneng Group (HNKJ17-21).

摘要/Abstract

摘要： 针对终端用户产生大量相同或相似计算请求的情况,可以通过近似匹配在边缘服务器缓存空间中查找相似数据,选取可复用的计算结果。现有算法大多未考虑数据分布不均的问题,导致计算量和时间开销较大,对此文中提出基于动态局部敏感哈希算法与加权k近邻算法的缓存数据选择策略(Cache Selection Strategy based on Dynamic-LSH algorithm and Weighted-KNN algorithm,CSS-DLWK)。其中,Dynamic-LSH算法能够针对数据分布不均的问题,根据数据分布的变化动态调整哈希桶粒度,从缓存空间中选出与输入数据相似的数据集合;Weighted-KNN算法以距离和样本数为权重,对由Dynamic-LSH算法获取的相似数据集合进行数据再选取,得到与输入数据最相似的数据,获取相应的计算结果以供复用。仿真实验结果表明,在CIFAR-10数据集中,与基于A-LSH算法与H-KNN算法的缓存选取策略相比,CSS-DLWK策略的平均选取准确率提高了4.1%;与传统的LSH算法相比,其平均选取准确率提高了16.8%。CSS-DLWK策略能够在可接受的数据选取时间开销内,有效地提高可复用数据选取的准确率,从而减少边缘服务器的重复计算。

关键词: 移动边缘计算, 缓存替换, 近似匹配, 数据复用, 局部敏感哈希算法

Abstract: For the case of massive identical or similar computing requests from end users,a search of similar data in the cache space of the edge server by approximate match can be applied to select computing results that can be reused.Most of the existing algorithms do not consider the uneven distribution of data,resulting in a large amount of calculation and time overhead.In this paper,a cache selection strategy based on dynamic-locality sensitive hashing (LSH) algorithm and Weighted-k nearest neighbor (KNN) algorithm(CSS-DLWK) is proposed.The Dynamic-LSH algorithm can deal with uneven data distribution by dynamically adjusting the hash bucket size accordingly,thereby selecting data sets that are similar to the input data from the cache space.Then,regarding distance and sample size as weights,the weighted-KNN algorithm re-selects the data in the similar data sets acquired by the dynamic-LSH algorithm.From this approach,the data most similar to the input data are obtained,and the corresponding computing result is acquired for reuse.As demonstrated by simulation experiments,in the CIFAR-10 dataset,CSS-DLWK increases the ave-rage selection accuracy by 4.1% compared to the cache selection strategy based on A-LSH and H-KNN algorithms.The improvement is 16.8% compared to traditional LSH algorithms.Overall,with acceptable time costs in data selection,the proposed strategy can effectively improve the selection accuracy of reusable data,thereby reducing repetitive computation in the edge server.

Key words: Mobile edge computing, Cache replacement, Approximate matching, Data reuse, Locality sensitive hashing algorithm

中图分类号:

TP399

郦睿翔, 毛莺池, 郝帅. 基于近似匹配的移动边缘计算缓存管理方法[J]. 计算机科学, 2021, 48(1): 96-102.

LI Rui-xiang, MAO Ying-chi, HAO Shuai. Cache Management Method in Mobile Edge Computing Based on Approximate Matching[J]. Computer Science, 2021, 48(1): 96-102.

参考文献

[1] SHI W,CAO J,ZHANG Q,et al.Edge computing:Vision and challenges[J].IEEE Internet of Things Journal,2016,3(5):637-646.
[2] GUO Y,LIU F,CAI Z,et al.Edge-based efficient search over encrypted data mobile cloud storage[J].Sensors,2018,18(4):1189.
[3] MASTORAKIS S,MTIBAA A,LEE J,et al.ICedge:WhenEdge Computing Meets Information-Centric Networking[J].IEEE Internet of Things Journal,2020,7(5):4203-4217.
[4] SANADHYA S,SIVAKUMAR R,KIM K H,et al.Asymmetric caching:improved network deduplication for mobile devices[C]//Proceedings of the 18th Annual International Conference on Mobile Computing and Networking.ACM,2012:161-172.
[5] GUO Y,LIU F,CAI Z,et al.Edge-based efficient search over encrypted data mobile cloud storage[J].Sensors,2018,18(4):1189.
[6] SUN S Y,YAO W B,LI X Y.DARS:A dynamic adaptive replica strategy under high load Cloud-P2P[J].Future Generation Computer Systems,2018,78:31-40.
[7] ANDONI A,INDYK P.Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions[C]//2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06).IEEE,2006:459-468.
[8] BECKMANN N,KRIEGEL H P,SCHNEIDER R,et al.The R^*-tree:An Efficient and Robust Access Method for Points and Rectangles[C]//Proceedings of the ACM SIGMOD Confe-rence on Management of Data.1990:322-331.
[9] SAMET H.The design and analysis of spatial data structures[M].Reading,MA:Addison-Wesley,1990.
[10] YIANILOS P N.Data structures and algorithms for nearestneighbor search in general metric spaces[C]//Soda.1993:311-321.
[11] SANADHYA S,SIVAKUMAR R,KIM K H,et al.Asymmetric caching:improved network deduplication for mobile devices[C]//Proceedings of the 18th Annual International Conference on Mobile Computing and Networking.ACM,2012:161-172.
[12] DUBOIS L,AMALDAS M,SHEPPARD E.Key considerations as deduplication evolves into primary storage[J].White Paper,2011,223310.
[13] KANNAN K,BHATTACHARYA S,RAJ K,et al.Seesaw-similarity exploiting storage for accelerating analytics workflows[C]//8th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage'16).2016.
[14] TANG Y,YANG J.Secure deduplication of general computa-tions[C]//2015 USENIX Conference on Annual Technical Conference.2015:319-331.
[15] ZHANG Z,TAO M.Accelerated Deep Reinforcement Learning for Wireless Coded Caching[C]//2019 IEEE/CIC International Conference on Communications in China (ICCC).IEEE,2019:249-254.
[16] ZHU H,CAO Y,WANG W,et al.Deep reinforcement learning for mobile edge caching:Review,new features,and open issues[J].IEEE Network,2018,32(6):50-57.
[17] ZHONG C,GURSOY M C,VELIPASALAR S.A deep reinforcement learning-based framework for content caching[C]//2018 52nd Annual Conference on Information Sciences and Systems (CISS).IEEE,2018:1-6.
[18] GUO P,HU B,LI R,et al.Foggycache:Cross-device approximate computation reuse[C]//Proceedings of the 24th Annual International Conference on Mobile Computing and Networking.ACM,2018:19-34.
[19] GUO P,HU W.Potluck:Cross-application approximate deduplication for computation-intensive mobile applications[C]//Proceedings of the Twenty-Third International Conference on Architectural Support for Programming Languages and Operating Systems.2018:271-284.
[20] LI Y,CHENG B.An improved k-nearest neighbor algorithm and its application to high resolution remote sensing image classification.[C]//2009 17th International Conference on Geoinforma-tics.IEEE,2009:1-4.
[21] PEREZ S.Lets smartphone cameras understand what they see[EB/OL].https://techcrunch.com/2017/05/17/google-lens/.
[22] LOWE D G.Distinctive Image Features from Scale-InvariantKeypoints[J].International Journal of Computer Vision,2004,60(2):91-110.
[23] ANDONI A,INDYK P.E2LSH:Exact euclidean locality-sensitive hashing[EB/OL].http://web.mit.edu/andoni/www/LSH/.
[24] COVER T,HART P.Nearest Neighbor pattern classification[J].IEEE Transactions on Information Theory,1967,13(1):21-27.
[25] SHAH J,SMOLENSKI B,YANTORNO R,et al.Sequentialknearest neighbor pattern recognition for usable speech classification[C]//2004 12th European Signal Processing Conference.Vienna,2004:741-744.
[26] RUSSAKOVSKY O,DENG J,SU H,et al.ImageNet Large Scale Visual Recognition Challenge[J].International Journal of Computer Vision,2015,115(3):211-252.
[27] KRIZHEVSKY A,HINTON G.Learning Multiple Layers of Features from Tiny Images[R].University of Toronto,2009.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于近似匹配的移动边缘计算缓存管理方法

Cache Management Method in Mobile Edge Computing Based on Approximate Matching

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10

[1]	梁俊斌, 田凤森, 蒋婵, 王天舒. 物联网中多设备多服务器的移动边缘计算任务卸载技术综述[J]. 计算机科学, 2021, 48(1): 16-25.
[2]	于天琪, 胡剑凌, 金炯, 羊箭锋. 基于移动边缘计算的车载CAN网络入侵检测方法[J]. 计算机科学, 2021, 48(1): 34-39.
[3]	毛莺池, 周彤, 刘鹏飞. 基于延迟接受的多用户任务卸载策略[J]. 计算机科学, 2021, 48(1): 49-57.
[4]	郭飞雁, 唐兵. 基于用户延迟感知的移动边缘服务器放置方法[J]. 计算机科学, 2021, 48(1): 103-110.
[5]	胡锦天, 王高才, 徐晓桐. 移动边缘计算中具有能耗优化的任务迁移策略[J]. 计算机科学, 2020, 47(6): 260-265.
[6]	田贤忠, 姚超, 赵晨, 丁军. 一种面向5G网络的移动边缘计算卸载策略[J]. 计算机科学, 2020, 47(11A): 286-290.
[7]	刘伟, 孙童心, 杜薇. 面向访问模式的混合内存缓存替换策略[J]. 计算机科学, 2020, 47(10): 130-135.
[8]	谷晓会,章国安. SDN在车载网中的应用综述[J]. 计算机科学, 2020, 47(1): 237-244.
[9]	殷佳, 管昕洁, 白光伟. 基于移动边缘计算的任务迁移和协作式负载均衡机制[J]. 计算机科学, 2019, 46(12): 126-131.
[10]	董思岐, 李海龙, 屈毓锛, 张钊, 胡磊. 移动边缘计算中的计算卸载策略研究综述[J]. 计算机科学, 2019, 46(11): 32-40.
[11]	杨冬菊,冯凯. 基于缓存的分布式统一身份认证优化机制研究[J]. 计算机科学, 2018, 45(3): 300-304.
[12]	田铭,邬江兴,兰巨龙. 信息中心网络中基于局部内容活跃度的自适应缓存算法[J]. 计算机科学, 2016, 43(11): 164-171.
[13]	叶剑虹，叶双. 基于混合模式的流媒体缓存调度算法[J]. 计算机科学, 2013, 40(2): 61-64.
[14]	黄敏蔡志刚. 缓存替换算法研究综述[J]. 计算机科学, 2006, 33(B12): 191-193.
[15]	佘堃牛新征周明天. 证书系统缓存替换算法的研究[J]. 计算机科学, 2004, 31(2): 89-92.