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

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: Edge computing, Computing offloading, Edge user allocation, Bipartite graph matching, Heuristic method

中图分类号:

TP311.5

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

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

参考文献

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

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

User Allocation Approach in Dynamic Mobile Edge Computing

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10

[1]	李辉, 李秀华, 熊庆宇, 文俊浩, 程路熙, 邢镔. 边缘计算助力工业互联网:架构、应用与挑战[J]. 计算机科学, 2021, 48(1): 1-10.
[2]	刘通, 方璐, 高洪皓. 边缘计算中任务卸载研究综述[J]. 计算机科学, 2021, 48(1): 11-15.
[3]	梁俊斌, 田凤森, 蒋婵, 王天舒. 物联网中多设备多服务器的移动边缘计算任务卸载技术综述[J]. 计算机科学, 2021, 48(1): 16-25.
[4]	于天琪, 胡剑凌, 金炯, 羊箭锋. 基于移动边缘计算的车载CAN网络入侵检测方法[J]. 计算机科学, 2021, 48(1): 34-39.
[5]	马堉银, 郑万波, 马勇, 刘航, 夏云霓, 郭坤银, 陈鹏, 刘诚武. 一种基于深度强化学习与概率性能感知的边缘计算环境多工作流卸载方法[J]. 计算机科学, 2021, 48(1): 40-48.
[6]	毛莺池, 周彤, 刘鹏飞. 基于延迟接受的多用户任务卸载策略[J]. 计算机科学, 2021, 48(1): 49-57.
[7]	余雪勇, 陈涛. 边缘计算场景中基于虚拟映射的隐私保护卸载算法[J]. 计算机科学, 2021, 48(1): 65-71.
[8]	高基旭, 王珺. 一种基于遗传算法的多边缘协同计算卸载方案[J]. 计算机科学, 2021, 48(1): 72-80.
[9]	杨紫淇, 蔡英, 张皓晨, 范艳芳. 基于负载均衡的VEC服务器联合计算任务卸载方案[J]. 计算机科学, 2021, 48(1): 81-88.
[10]	单美静, 秦龙飞, 张会兵. L-YOLO:适用于车载边缘计算的实时交通标识检测模型[J]. 计算机科学, 2021, 48(1): 89-95.
[11]	郦睿翔, 毛莺池, 郝帅. 基于近似匹配的移动边缘计算缓存管理方法[J]. 计算机科学, 2021, 48(1): 96-102.
[12]	郭飞雁, 唐兵. 基于用户延迟感知的移动边缘服务器放置方法[J]. 计算机科学, 2021, 48(1): 103-110.
[13]	赵明. 边缘计算技术及应用综述[J]. 计算机科学, 2020, 47(6A): 268-272.
[14]	胡锦天, 王高才, 徐晓桐. 移动边缘计算中具有能耗优化的任务迁移策略[J]. 计算机科学, 2020, 47(6): 260-265.
[15]	简琤峰, 平靖, 张美玉. 面向边缘计算的Storm边缘节点调度优化方法[J]. 计算机科学, 2020, 47(5): 277-283.