计算机科学 ›› 2021, Vol. 48 ›› Issue (11A): 456-463.doi: 10.11896/jsjkx.210100191

• 网络& 通信 • 上一篇    下一篇

基于PSO-GA的多边缘负载均衡方法

姚泽玮, 林嘉雯, 胡俊钦, 陈星   

  1. 福州大学数学与计算机科学学院 福州350108
    福建省网络计算与智能信息处理重点实验室(福州大学) 福州350108
  • 出版日期:2021-11-10 发布日期:2021-11-12
  • 通讯作者: 林嘉雯(ljw@fzu.edu.cn)
  • 作者简介:zeweiy7052@163.com
  • 基金资助:
    国家自然科学基金项目(62072108);福建省自然科学基金杰青项目(2020J06014);福建省自然科学基金项目(2018J07005)

PSO-GA Based Approach to Multi-edge Load Balancing

YAO Ze-wei, LIU Jia-wen, HU Jun-qin, CHEN Xing   

  1. College of Mathematics and Computer Science,Fuzhou University,Fuzhou 350108,China
    Fujian Key Laboratory of Network Computing and Intelligent Information Processing (Fuzhou University),Fuzhou 350108,China
  • Online:2021-11-10 Published:2021-11-12
  • About author:YAO Ze-wei,born in 1998,postgraduate.His main research interests include computation offloading,computational intelligence and its applications.
    LIN Jia-wen,born in 1985,Ph.D,lecturer,postgraduate supervisor,is a member of CCF.Her main research interests include intelligent information processing,computer vision and medical image analysis.
  • Supported by:
    National Natural Science Foundation of China(62072108),Natural Science Foundation of Fujian Province for Distinguished Young Scholars(2020J06014) and Natural Science Foundation of Fujian Province(2018J07005).

摘要: 移动边缘计算(Mobile Edge Computing,MEC)作为一种新的范式,可以解决移动设备的计算资源、存储资源短缺的问题。通过无线网络,它将移动设备上的密集型任务迁移到用户附近的边缘上执行,最后把运行结果传回给移动设备。由于用户移动的随机性,部署在城市的每个边缘的负载情况通常是不一致的。针对多边缘的负载均衡问题,考虑通过任务调度来最小化边缘集合中最大的任务响应时间,从而提高移动设备的性能。首先,对多边缘负载均衡问题进行形式化定义;其次,提出粒子群遗传算法(Particle Swarm Optimization-Genetic Algorithm,PSO-GA)来解决多边缘负载均衡问题;最后通过仿真实验,将该算法与随机迁移算法和贪心算法进行对比与分析。实验结果表明,PSO-GA得到的结果最高分别优于随机迁移算法和贪心算法51.58%和26.34%。因此,PSO-GA在缩短边缘的任务响应时间、改善用户体验方面具有较好的潜力。

关键词: 负载均衡, 粒子群遗传算法, 任务响应时间, 移动边缘计算

Abstract: As a new paradigm,mobile edge computing (MEC) can provide an efficient method to solve the computing and storage resource constraints of mobile devices.Through the wireless network,it migrates the intensive tasks on mobile devices to the edges near the users for execution,then the edges transmit the execution results back to mobile devices.Due to the randomness of users' movement,the load on each edge which deployed in the city is usually inconsistent.To solve the problem of multi-edge load balancing,the task scheduling is considered to minimize the maximum response time of tasks in the edge set,thereby improving the performance of mobile devices.Firstly,the multi-edge load balancing problem is formally defined.Then particle swarm optimization-genetic algorithm(PSO-GA) is proposed to solve the multi-edge load balancing problem.Finally,the performance of the algorithm is compared and analyzed with the random migration algorithm and the greedy algorithm through simulation experiments.The experimental results show that PSO-GA is superior to random migration and greedy algorithm by 51.58% and 26.34%,respectively.Therefore,PSO-GA has a better potential for reducing task response time of the edges and improving user experience.

Key words: Load balancing, Mobile edge computing, Particle swarm optimization-genetic algorithm, Task response time

中图分类号: 

  • TP301
[1]FAN X,CAO J,MAO H.A survey of mobile cloud computing[J].zTE Communications,2011,9(1):4-8.
[2]HU Y C,PATEL M,SABELLA D,et al.Mobile edge comput-ing-A key technology towards 5G[J].ETSI White Paper,2015,11(11):1-16.
[3]MAO Y,YOU C,ZHANG J,et al.A survey on mobile edge computing:The communication perspective[J].IEEE Communications Surveys & Tutorials,2017,19(4):2322-2358.
[4]SATYANARAYANAN M,BAHL P,CÁCERES R,et al.The Case for VM-Based Cloudlets in Mobile Computing[J].Pervasive Computing,IEEE,2009,8(4):14-23.
[5]WANG T,WEI X,LIANG T,et al.Dynamic tasks scheduling based on weighted bi-graph in Mobile Cloud Computing[J].Sustainable Computing:Informatics and Systems,2018,19:214-222.
[6]RAMASUBBAREDDY S,SASIKALA R.RTTSMCE:a re-sponse time aware task scheduling in multi-cloudlet environment[J].International Journal of Computers and Applications,2019(1):1-6.
[7]SOMULA R,SASIKALA R.A load and distance aware edge selection strategy in multi-cloudlet environment[J].International Journal of Grid and High Performance Computing (IJGHPC),2019,11(2):85-102.
[8]ZHANG Q.Research on Task Offloading Technology in Mobile Cloud Computing[D].Harbin:Harbin Institute of Technology,2016.
[9]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,2015,5(4):725-737.
[10]MA L,WU J,CHEN L,et al.Fast algorithms for capacitated cloudlet placements[C]//2017 IEEE 21st International Conference on Computer Supported Cooperative Work in Design (CSCWD).IEEE,2017:439-444.
[11]XU Z,LIANG W,XU W,et al.Capacitated cloudlet placements in wireless metropolitan area networks[C]//2015 IEEE 40th Conference on Local Computer Networks (LCN).IEEE,2015:570-578.
[12]YAO D,GUI L,HOU F,et al.Load balancing oriented computation offloading in mobile cloudlet [C]//2017 IEEE 86th Vehicular Technology Conference (VTC-Fall).IEEE,2017:1-6.
[13]OMARA F A,ARAFA M M.Genetic algorithms for task scheduling problem[J].Journal of Parallel and Distributed Computing,2010,70(1):13-22.
[14]GONG Y G.Research on The Combination of Particle Swarm Optimization and Genetic Algorithm[D].Guangzhou:Sun Yat-sen University,2007.
[15]KLEINROCK L.Queueing systems,volume 2:Computer applications[M].New York:wiley,1976.
[16]KENNEDY J,EBERHART R.Particle swarm optimization[C]//Proceedings of ICNN'95-International Conference on Neural Networks.IEEE,1995:1942-1948.
[17]SRINIVAS M,PATNAIK L M.Genetic algorithms:a survey[J].Computer,1994,27(6):17-26.
[18]PRIDDY K L,KELLER P E.Artificial neural networks:an introduction[M].SPIE Press,2005.
[19]AGARWAL M,SRIVASTAVA G M S.Genetic algorithm-enabled particle swarm optimization (PSOGA)-based task schedu-ling in cloud computing environment[J].International Journal of Information Technology & Decision Making,2018,17(4):1237-1267.
[20]JIA M,LIANG W,XU Z,et al.Qos-aware cloudlet load balancing in wireless metropolitan area networks[J].IEEE Transactions on Cloud Computing,2018,8(2):623-634.
[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
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!