移动边缘计算中的动态用户分配方法

doi:10.11896/jsjkx.200900079

计算机科学 ›› 2021, Vol. 48 ›› Issue (1): 58-64.doi: 10.11896/jsjkx.200900079

所属专题：智能化边缘计算

移动边缘计算中的动态用户分配方法

唐文君, 刘岳, 陈荣

大连海事大学信息科学技术学院辽宁大连 116026

收稿日期:2020-09-09 修回日期:2020-12-07 出版日期:2021-01-15 发布日期:2021-01-15
通讯作者: 陈荣(rchen@dlmu.edu.cn)
作者简介:wjtang@dlmu.edu.cn
基金资助:
国家自然科学基金(61672122,61902050,61602077);中央高校基本科研业务费专项基金(3132019355);赛尔创新项目(NGII20190627);中国博士后科学基金(2020M670736)

User Allocation Approach in Dynamic Mobile Edge Computing

TANG Wen-jun, LIU Yue, CHEN Rong

Department of Information Science and Technology,Dalian Maritime University,Dalian,Liaoning 116026,China

Received:2020-09-09 Revised:2020-12-07 Online:2021-01-15 Published:2021-01-15
About author:TANG Wen-jun,born in 1994,Ph.D student.Her main research interests include crowdsourcing workflows,crowd sourcing task assignment and web service testing.
CHEN Rong,born in 1969,Ph.D,professor,is a member of the IEEE and a member of the ACM.His main research interests include software diagnosis,collective intelligence,activity recognition,Internet and mobile computing.
Supported by:
National Natural Science Foundation of China(61672122,61902050,61602077),Fundamental Research Funds for the Central Universities of Ministry of Education of China(3132019355),ERNET Innovation Project (NGII20190627) and China Postdoctoral Science Foundation (2020M670736).

摘要/Abstract

摘要： 在边缘计算环境中,为用户匹配合适的服务器是一个关键问题,可以有效提升服务质量。文中将边缘用户分配问题转换为一个受距离和服务器资源约束的二分图匹配问题,并将其建模为一个0-1整数规划问题进行优化。在离线状态下,基于精确式算法的优化模型可以求得最优分配策略,但其求解时间过长,无法处理规模较大的数据,不适用于现实服务环境。因此,提出了基于启发式策略的在线分配方法,以在时间有限的情况下优化用户-服务器的分配。实验结果显示,基于近邻启发式的在线方法的竞争比能够接近100%,可以在可接受的时间范围内求得较优的分配解。同时,近邻启发式方法比其他基础启发式方法的表现更优秀。

关键词: 边缘计算, 边缘用户分配, 二分图匹配, 计算卸载, 启发式方法

Abstract: In edge computing environment,matching suitable servers for users is a key issue,which can effectively improve the quality of service.In this paper,the edge user assignment (EUA) problem is converted into a bipartite graph matching problem constrained by distance and server resources,and it is modeled as a 0-1 integer programming problem for optimal assignment solution.In the offline state,the optimization model based on exact algorithm can obtain the optimal assignment strategy,but its solution time is too long,and it cannot process large-scale of data,which is not suitable for the real service environment.Therefore,the online user assignment method based on heuristic strategy is proposed to optimize the user-server assignment under limited time.The experimental results show that the competitive ratio obtained by Proximal Heuristic online method (PH) can reach close to 100%,and can obtain a better assignment solution within an acceptable time.At the same time,the online PH method performs better than other basic heuristic methods.

Key words: Bipartite graph matching, Computing offloading, Edge computing, Edge user allocation, Heuristic method

中图分类号:

TP311.5

唐文君, 刘岳, 陈荣. 移动边缘计算中的动态用户分配方法[J]. 计算机科学, 2021, 48(1): 58-64. https://doi.org/10.11896/jsjkx.200900079

TANG Wen-jun, LIU Yue, CHEN Rong. User Allocation Approach in Dynamic Mobile Edge Computing[J]. Computer Science, 2021, 48(1): 58-64. https://doi.org/10.11896/jsjkx.200900079

参考文献

[1] SHI S,SUN H,CAO J,et al.Edge Computing－An Emerging Computing Model for the Internet of Everything Era [J].Journal of Computer Research and Development,2017,54(5):907-924.
[2] PATEL M,NAUGHTON B,CHAN C,et al.Mobile-edge computing introductory technical white paper[M].Mobile-edge Computing (MEC) Industry Initiative.2014:1089-7801.
[3] ZHANG W L,GUO B,SHEN Y,et al.Computation offloading on intelligent mobile terminal [J].Chinese Journal of Computers,2015,38(30):1021-1038.
[4] HE Q,CUI G,ZHANG X,et al.A game-theoretical approachfor user allocation in edge computing environment [J].IEEE Transactions on Parallel and Distributed Systems,2019,31(3):515-529.
[5] LAI P,HE Q,ABDELRAZEK M,et al.Optimal edge user allocation in edge computing with variable sized vector bin packing [C]//International Conference on Service-oriented Computing.2018:230-245.
[6] WU J,LIU T,LI J,et al.Research Progress on BlockchainTechnology in Mobile Edge Computing[J].Computer Engineering,2020,46(8):1-13.
[7] WANG Y,GE H,FENG A.Computation Offloading Strategy in Cloud-Assisted Mobile Edge Computing[J].Computer Engineering,2020,46(8):27-34.
[8] MACH P,BECVAR Z.Mobile edge computing:A survey on architecture and computation offloading [J].IEEE Communications Surveys & Tutorials,2017,19(3):1628-1656.
[9] RODRIGUES T G,SUTO K,NISHIYAMA H,et al.Hybridmethod for minimizing service delay in edge cloud computing through VM migration and transmission power control [J].IEEE Transactions on Computers,2016,66(5):810-819.
[10] JIA M,CAO J,YANG L.Heuristic offloading of concurrenttasks for computation-intensive applications in mobile cloud computing [C]// IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS).2014:352-357.
[11] CHEN X,CAI Y,LI L,et al.Energy-efficient resource allocation for latency-sensitive mobile edge computing [J].IEEE Transactions on Vehicular Technology,2019,69(2):2246-2262.
[12] YOU C,HUANG K,CHAE H,et al.Energy-efficient resource allocation for mobile-edge computation offloading [J].IEEE Transactions on Wireless Communications,2016,16(3):1397-1411.
[13] KAO Y H,KRISHNAMACHARI B,RA M R,et al.Hermes:Latency optimal task assignment for resource-constrained mobile computing [J].IEEE Transactions on Mobile Computing,2017,16(11):3056-3069.
[14] ZHANG H,GUO J,YANG L,et al.Computation offloadingconsidering fronthaul and backhaul in small-cell networks integrated with MEC[C]//IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS).2017:115-120.
[15] ZHANG J,HU X,NING Z,et al.Energy-latency tradeoff forenergy-aware offloading in mobile edge computing networks [J].IEEE Internet of Things Journal,2017,5(4):2633-2645.
[16] YANG T,TIAN L,SUN Q,et al.Computing Offloading Scheme Based on User Experiencein Mobile Edge Computing[J].Computer Engineering,2020,46(10):33-40.
[17] LIU T.Task Offloading Strategy for Minimizing Power Con-sumption in Two Layer Edge Computing Architecture[J].Journal of Chongqing University of Technology (Natural Science),2019,33(8):157-164.
[18] XIAO Y,KRUNZ M.QoE and power efficiency tradeoff for fog computing networks with fog node cooperation [C]//INFOCOM.2017:1-9.
[19] LUO J,DENG X,ZHANG H,et al.QoE-driven computation offloading for edge computing [J].Journal of Systems Architecture,2019,97:34-39.
[20] PENG Q,XIA Y.Mobility-Aware and Migration-Enabled Online Edge User Allocation in Mobile Edge Computing [C]// IEEE International Conference on Web Services.2019:91-98.

相关文章 15

[1]	孙慧婷, 范艳芳, 马孟晓, 陈若愚, 蔡英. VEC中基于动态定价的车辆协同计算卸载方案 Dynamic Pricing-based Vehicle Collaborative Computation Offloading Scheme in VEC 计算机科学, 2022, 49(9): 242-248. https://doi.org/10.11896/jsjkx.210700166
[2]	于滨, 李学华, 潘春雨, 李娜. 基于深度强化学习的边云协同资源分配算法 Edge-Cloud Collaborative Resource Allocation Algorithm Based on Deep Reinforcement Learning 计算机科学, 2022, 49(7): 248-253. https://doi.org/10.11896/jsjkx.210400219
[3]	张翀宇, 陈彦明, 李炜. 边缘计算中面向数据流的实时任务调度算法 Task Offloading Online Algorithm for Data Stream Edge Computing 计算机科学, 2022, 49(7): 263-270. https://doi.org/10.11896/jsjkx.210300195
[4]	李梦菲, 毛莺池, 屠子健, 王瑄, 徐淑芳. 基于深度确定性策略梯度的服务器可靠性任务卸载策略 Server-reliability Task Offloading Strategy Based on Deep Deterministic Policy Gradient 计算机科学, 2022, 49(7): 271-279. https://doi.org/10.11896/jsjkx.210600040
[5]	方韬, 杨旸, 陈佳馨. D2D辅助移动边缘计算下的卸载策略优化 Optimization of Offloading Decisions in D2D-assisted MEC Networks 计算机科学, 2022, 49(6A): 601-605. https://doi.org/10.11896/jsjkx.210200114
[6]	刘漳辉, 郑鸿强, 张建山, 陈哲毅. 多无人机使能移动边缘计算系统中的计算卸载与部署优化 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
[7]	袁昊男, 王瑞锦, 郑博文, 吴邦彦. 基于Fabric的电子病历跨链可信共享系统设计与实现 Design and Implementation of Cross-chain Trusted EMR Sharing System Based on Fabric 计算机科学, 2022, 49(6A): 490-495. https://doi.org/10.11896/jsjkx.210500063
[8]	谢万城, 李斌, 代玥玥. 空中智能反射面辅助边缘计算中基于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
[9]	周天清, 岳亚莉. 超密集物联网络中多任务多步计算卸载算法研究 Multi-Task and Multi-Step Computation Offloading in Ultra-dense IoT Networks 计算机科学, 2022, 49(6): 12-18. https://doi.org/10.11896/jsjkx.211200147
[10]	彭冬阳, 王睿, 胡谷雨, 祖家琛, 王田丰. 视频缓存策略中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
[11]	张海波, 张益峰, 刘开健. 基于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
[12]	林潮伟, 林兵, 陈星. 边缘环境下基于模糊理论的科学工作流调度研究 Study on Scientific Workflow Scheduling Based on Fuzzy Theory Under Edge Environment 计算机科学, 2022, 49(2): 312-320. https://doi.org/10.11896/jsjkx.201000102
[13]	梁俊斌, 张海涵, 蒋婵, 王天舒. 移动边缘计算中基于深度强化学习的任务卸载研究进展 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
[14]	薛艳芬, 高继梅, 范贵生, 虞慧群, 许亚杰. 边缘计算中基于能耗感知的容错协同任务执行算法 Energy-aware Fault-tolerant Collaborative Task Execution Algorithm in Edge Computing 计算机科学, 2021, 48(6A): 374-382. https://doi.org/10.11896/jsjkx.200900027
[15]	宋海宁, 焦健, 刘永. 高速公路中的移动边缘计算研究 Research on Mobile Edge Computing in Expressway 计算机科学, 2021, 48(6A): 383-386. https://doi.org/10.11896/jsjkx.200900212

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

移动边缘计算中的动态用户分配方法

User Allocation Approach in Dynamic Mobile Edge Computing

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0