计算机科学 ›› 2021, Vol. 48 ›› Issue (1): 96-102.doi: 10.11896/jsjkx.200800215
所属专题： 智能化边缘计算
郦睿翔, 毛莺池, 郝帅
LI Rui-xiang, MAO Ying-chi, HAO Shuai
摘要： 针对终端用户产生大量相同或相似计算请求的情况,可以通过近似匹配在边缘服务器缓存空间中查找相似数据,选取可复用的计算结果。现有算法大多未考虑数据分布不均的问题,导致计算量和时间开销较大,对此文中提出基于动态局部敏感哈希算法与加权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策略能够在可接受的数据选取时间开销内,有效地提高可复用数据选取的准确率,从而减少边缘服务器的重复计算。
中图分类号:
| [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. |
| [1] | 于滨, 李学华, 潘春雨, 李娜. 基于深度强化学习的边云协同资源分配算法 Edge-Cloud Collaborative Resource Allocation Algorithm Based on Deep Reinforcement Learning 计算机科学, 2022, 49(7): 248-253. https://doi.org/10.11896/jsjkx.210400219 |
| [2] | 李梦菲, 毛莺池, 屠子健, 王瑄, 徐淑芳. 基于深度确定性策略梯度的服务器可靠性任务卸载策略 Server-reliability Task Offloading Strategy Based on Deep Deterministic Policy Gradient 计算机科学, 2022, 49(7): 271-279. https://doi.org/10.11896/jsjkx.210600040 |
| [3] | 方韬, 杨旸, 陈佳馨. D2D辅助移动边缘计算下的卸载策略优化 Optimization of Offloading Decisions in D2D-assisted MEC Networks 计算机科学, 2022, 49(6A): 601-605. https://doi.org/10.11896/jsjkx.210200114 |
| [4] | 刘漳辉, 郑鸿强, 张建山, 陈哲毅. 多无人机使能移动边缘计算系统中的计算卸载与部署优化 Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems 计算机科学, 2022, 49(6A): 619-627. https://doi.org/10.11896/jsjkx.210600165 |
| [5] | 谢万城, 李斌, 代玥玥. 空中智能反射面辅助边缘计算中基于PPO的任务卸载方案 PPO Based Task Offloading Scheme in Aerial Reconfigurable Intelligent Surface-assisted Edge Computing 计算机科学, 2022, 49(6): 3-11. https://doi.org/10.11896/jsjkx.220100249 |
| [6] | 周天清, 岳亚莉. 超密集物联网络中多任务多步计算卸载算法研究 Multi-Task and Multi-Step Computation Offloading in Ultra-dense IoT Networks 计算机科学, 2022, 49(6): 12-18. https://doi.org/10.11896/jsjkx.211200147 |
| [7] | 彭冬阳, 王睿, 胡谷雨, 祖家琛, 王田丰. 视频缓存策略中QoE和能量效率的公平联合优化 Fair Joint Optimization of QoE and Energy Efficiency in Caching Strategy for Videos 计算机科学, 2022, 49(4): 312-320. https://doi.org/10.11896/jsjkx.210800027 |
| [8] | 张海波, 张益峰, 刘开健. 基于NOMA-MEC的车联网任务卸载、迁移与缓存策略 Task Offloading,Migration and Caching Strategy in Internet of Vehicles Based on NOMA-MEC 计算机科学, 2022, 49(2): 304-311. https://doi.org/10.11896/jsjkx.210100157 |
| [9] | 梁俊斌, 张海涵, 蒋婵, 王天舒. 移动边缘计算中基于深度强化学习的任务卸载研究进展 Research Progress of Task Offloading Based on Deep Reinforcement Learning in Mobile Edge Computing 计算机科学, 2021, 48(7): 316-323. https://doi.org/10.11896/jsjkx.200800095 |
| [10] | 宋海宁, 焦健, 刘永. 高速公路中的移动边缘计算研究 Research on Mobile Edge Computing in Expressway 计算机科学, 2021, 48(6A): 383-386. https://doi.org/10.11896/jsjkx.200900212 |
| [11] | 范艳芳, 袁爽, 蔡英, 陈若愚. 车载边缘计算中基于深度强化学习的协同计算卸载方案 Deep Reinforcement Learning-based Collaborative Computation Offloading Scheme in VehicularEdge Computing 计算机科学, 2021, 48(5): 270-276. https://doi.org/10.11896/jsjkx.201000005 |
| [12] | 李振江, 张幸林. 减少核心网拥塞的边缘计算资源分配和卸载决策 Resource Allocation and Offloading Decision of Edge Computing for Reducing Core Network Congestion 计算机科学, 2021, 48(3): 281-288. https://doi.org/10.11896/jsjkx.200700025 |
| [13] | 姚泽玮, 林嘉雯, 胡俊钦, 陈星. 基于PSO-GA的多边缘负载均衡方法 PSO-GA Based Approach to Multi-edge Load Balancing 计算机科学, 2021, 48(11A): 456-463. https://doi.org/10.11896/jsjkx.210100191 |
| [14] | 徐旭, 钱丽萍, 吴远. 基于移动边缘计算的区块链计算资源分配和收益分享研究 Computation Resource Allocation and Revenue Sharing Based on Mobile Edge Computing for Blockchain 计算机科学, 2021, 48(11): 124-132. https://doi.org/10.11896/jsjkx.201100205 |
| [15] | 梁俊斌, 田凤森, 蒋婵, 王天舒. 物联网中多设备多服务器的移动边缘计算任务卸载技术综述 Survey on Task Offloading Techniques for Mobile Edge Computing with Multi-devices and Multi-servers in Internet of Things 计算机科学, 2021, 48(1): 16-25. https://doi.org/10.11896/jsjkx.200500095 |
|
||
首页