基于移动边缘计算的任务迁移和协作式负载均衡机制

摘要/Abstract

摘要： 由于使用中心云服务会产生相应的延迟和通信成本,更靠近移动用户的移动边缘计算已经成为处理计算密集型和延迟敏感型应用程序的主要技术。位于网络边缘的小型云数据中心被称为微云,其能够为周围邻近的移动设备提供计算能力,减少服务交付的时延。然而,在移动微云组成的边缘网络环境下,负载均衡问题直接影响了任务的响应时间。为了提高用户服务质量,文中提出基于移动边缘计算的任务迁移和协作式负载均衡机制,包括分别针对用户和微云设计的延迟感知目标选择策略LATS和协作式负载均衡策略CLB。LATS根据微云当前的负载信息为移动用户选择最优的任务迁移对象;CLB使用Balls-into-bins模型,只需要获取局部信息就可以有效地实现移动微云之间的负载均衡。仿真结果表明,所提策略能够有效减小系统延迟和负载差异,同时降低通信和计算成本。

关键词: Balls-into-bins理论, 负载均衡, 计算通信成本, 移动边缘计算, 用户任务迁移

Abstract: Because of the corresponding delay and communication cost associated with the use of cloud service,mobile edge computing(MEC) which is closer to mobile users has become the main technology for processing computing-intensive and delay-sensitive applications.Small data centers located on the edge of network are called “cloudlets”,which can provide computing resource for nearby mobile devices.The service delivery delay can be reduced significantly by using MEC.However,in the edge network environment composed of mobile micro-clouds,load balancing directly affects the response time of tasks.In order to improve the quality of service for users,this paper proposed a task offloading and cooperative load balancing mechanism.The mechanism includes a latency-aware target selection strategy (LATS) for mobile users and a collaborative load-balancing strategy (CLB) for mobile cloudlets.LATS chooses the best task migration object for mobile users according to the current load information of cloudlets.CLB uses balls-in-bins theory and it can balance the task loads with extremely limited information.Simulations and evaluations demonstrate that the proposed mechanism can effectively reduce the system delay and load gaps,as well as the communication and computing cost.

Key words: Balls-into-bins theory, Computing and communication cost, Mobile edge computing, User task offloading, Workload balancing

中图分类号:

TP393

殷佳, 管昕洁, 白光伟. 基于移动边缘计算的任务迁移和协作式负载均衡机制[J]. 计算机科学, 2019, 46(12): 126-131. https://doi.org/10.11896/jsjkx.181202453

YIN Jia, GUAN Xin-jie, BAI Guang-wei. Task Offloading and Cooperative Load Balancing Mechanism Based on Mobile Edge Computing[J]. Computer Science, 2019, 46(12): 126-131. https://doi.org/10.11896/jsjkx.181202453

参考文献

[1]BOTTA A,DE DONATO W,et al.Integration of cloud computing and internet of things:A survey[J].Future Generation Computer Systems,2016,56(2):684-700.
[2]OHU Y C,PATEL M,SABELLA D,et al.Mobile Edge Computing:A Key Technology towards 5G[J].ETSI White Paper,2015,11(11):1-16.
[3]JIA M K,LIANG W F,XU Z C,et al.Cloudlet load balancing in wireless metropolitan area networks[C]//Proceedings of IEEE INFOCOM.San Francisco,CA,USA,2016:1-9.
[4]KUMAR K,LIU J,LU Y H,et al.A Survey of Computation Offloading for Mobile Systems[J].Mobile Networks and Applications,2013,18(1):129-140.
[5]JIA M,CAO J,LIANG W.Optimal cloudlet placement and user to cloudlet allocation in wireless metropolitan area networks[J].IEEE Transactions on Cloud Computing,2017,5(4):725-737.
[6]TRAN T X,HAJISAMI A,PANDEY P.Collaborative mobile edge computing in 5g networks:New paradigms,scenarios,and challenges[J].IEEE Communications Magazine,2017,55(4):54-61.
[7]CLINCH S,HARKES J,FRIDAY A,et al.How close is close enough? understanding the role of cloudlets in supporting display appropriation by mobile users[C]//Proceedings of IEEE Pervasive Computing and Communication.Switzerland,2012:122-127.
[8]CAO H,CAI J.Distributed multiuser computation offloading for cloudlet-based mobile cloud computing:A game-theoretic machine learning approach[J].IEEE Transactions on Vehicular Technology,2018,67(1):752-764.
[9]JEONG S,SIMEONE O,KANG J.Mobile edge computing via a UAV-Mounted cloudlet:Optimization of bit allocation and path planning[J].IEEE Transactions on Vehicular Technology,2018,67(3):2049-2063.
[10]XU Z,LIANG W,XU W,et al.Efficient algorithms for capacitated cloudlet placements[J].IEEE Transactions on Parallel and Distributed Systems,2016,27(10):2866-2880.
[11]ZHAO J,YANG K,WEI X,et al.A heuristic clustering-based task deployment approach for load balancing using Bayes theorem in cloud environment[J].IEEE Transactions on Parallel and Distributed Systems,2016,27(2):305-316.
[12]VÖCKING B.How asymmetry helps load balancing[J].Journal of the ACM (JACM),2003,50(4):568-589.
[13]MITZENMACHER M.The power of two choices in randomized load balancing[J].IEEE Transactions on Parallel and Distributed Systems,2001,12(10):1094-1104.
[14]FERNANDO N,LOKE S W,RAHAYU W.Mobile cloud computing:A survey[J].Future Generation Computer Systems,2013,29(1):84-106.
[15]BASTUG E,BENNIS M,DEBBAH M.Living on the Edge:The Role of Proactive Caching in 5G Wireless Networks[J].IEEE Communications Magazine,2014,52(8):82-89.
[16]SATYANARAYANAN M,BAHL P,CACERES R,et al.The case for VM-based cloudlets in mobile computing[J].IEEE Pervasive Computing,2009,8(4):14-23.
[17]MAO B Y,YOU C S,ZHANG J.A survey on mobile edge computing:The communication perspective[J].IEEE Communications Surveys & Tutorials,2017,19(4):2322-2358.
[18]ZHANG Y,NIYATO D,WANG P,et al.Dynamic OffloadingAlgorithm in Intermittently Connected Mobile Cloudlet Systems[C]//Proceedings of IEEE International Conference on Communications.Sydney,Australia,2014.
[19]HUU T T,THAM C K,NIYATO D.To Offload or to Wait:An Opportunistic Offloading Algorithm for Parallel Tasks in a Mobile Cloud[C]//Proceedings of IEEE 6th International Confe-rence on Cloud Computing Technology and Science.Singapore,2014.
[20]ZHANG Y,NIYATO D,WANG P.Offloading in mobile cloudlet systems with intermittent connectivity[J].IEEE Transactions on Mobile Computing,2015,14(12):2516-2529.
[21]GUO X J,LIU L Q,CHANG Z,et al.Data offloading and task allocation for cloudlet-assisted ad hoc mobile clouds[J].Wireless Network,2018,24(1):79-88.
[22] TOURNOUX P U,LEGUAY J,BENBADIS F,et al.The accordion phenomenon:Analysis,characterization,and impact on DTN routing[C]//Proceedings of INFOCOM.Brazil,2009:1116-1124.
[23]LI Q Y,YANG P T,FAN X C,et al.Taming the big to small:Efficient selfish task allocation in mobile crowdsourcing systems[J].Concurrency and Computation Practice and Experience,2017,29(14):2213-2226.
[24]LIU Y,LEE M J,ZHENG Y.Adaptive multi-resource allocation for cloudlet-based mobile cloud computing system[J].IEEE Transactions on Mobile Computing,2016,15(10):2398-2410.
[25]PEARCE O,GAMBLIN T,DE SUPINSKI B R,et al.Quantifying the effectiveness of load balance algorithms[C]//Proceedings of the 26th ACM International Conference on Supercomputing.San Servolo Island,Venice,Italy,2012:185-194.
[26]CHEN Z,HU W L,WANG J J,et al.An empirical study of latency in an emerging class of edge computing applications for wearable cognitive assistance[C]//Proceedings of the Second ACM/IEEE Symposium on Edge Computing Article.San Jose,California,2017.
[27]LIU D,CHEN Y,CHAI K K,et al.Distributed latency-energy aware user association in 3-tier HetNets with hybrid energy sources[C]//Proceedings of IEEE Globecom Workshops.Austin,TX,USA,2014.
[28]KIM S H,WHITT W.Statistical analysis with Little’s Law[J].The Institute for Operations Research and the Management Science,2013,16(4):1030-1045.
[29]BERENBRINK P,FRIEDETZKY T,GOLDBERG L A,et al. Distributed selfish load balancing[C]//Proceedings of theSe-venteenth Annual ACM-SIAM Symposium on Discrete Algorithm.Miami,Florida,2006:354-363.

相关文章 15

[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]	田真真, 蒋维, 郑炳旭, 孟利民. 基于服务器集群的负载均衡优化调度算法 Load Balancing Optimization Scheduling Algorithm Based on Server Cluster 计算机科学, 2022, 49(6A): 639-644. https://doi.org/10.11896/jsjkx.210800071
[6]	谢万城, 李斌, 代玥玥. 空中智能反射面辅助边缘计算中基于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
[7]	周天清, 岳亚莉. 超密集物联网络中多任务多步计算卸载算法研究 Multi-Task and Multi-Step Computation Offloading in Ultra-dense IoT Networks 计算机科学, 2022, 49(6): 12-18. https://doi.org/10.11896/jsjkx.211200147
[8]	高捷, 刘沙, 黄则强, 郑天宇, 刘鑫, 漆锋滨. 基于国产众核处理器的深度神经网络算子加速库优化 Deep Neural Network Operator Acceleration Library Optimization Based on Domestic Many-core Processor 计算机科学, 2022, 49(5): 355-362. https://doi.org/10.11896/jsjkx.210500226
[9]	彭冬阳, 王睿, 胡谷雨, 祖家琛, 王田丰. 视频缓存策略中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
[10]	张海波, 张益峰, 刘开健. 基于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
[11]	谭双杰, 林宝军, 刘迎春, 赵帅. 基于机器学习的分布式星载RTs系统负载调度算法 Load Scheduling Algorithm for Distributed On-board RTs System Based on Machine Learning 计算机科学, 2022, 49(2): 336-341. https://doi.org/10.11896/jsjkx.201200126
[12]	夏中, 向敏, 黄春梅. 基于CHBL的P2P视频监控网络分层管理机制 Hierarchical Management Mechanism of P2P Video Surveillance Network Based on CHBL 计算机科学, 2021, 48(9): 278-285. https://doi.org/10.11896/jsjkx.201200056
[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]	宋海宁, 焦健, 刘永. 高速公路中的移动边缘计算研究 Research on Mobile Edge Computing in Expressway 计算机科学, 2021, 48(6A): 383-386. https://doi.org/10.11896/jsjkx.200900212
[15]	王政, 姜春茂. 一种基于三支决策的云任务调度优化算法 Cloud Task Scheduling Algorithm Based on Three-way Decisions 计算机科学, 2021, 48(6A): 420-426. https://doi.org/10.11896/jsjkx.201000023

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed