计算机科学

计算机科学 ›› 2023, Vol. 50 ›› Issue (11A): 221200150-8.doi: 10.11896/jsjkx.221200150

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

基于博弈论的多边缘服务器负载均衡策略

翁杰1,2, 林兵2,3, 陈星1,2   

  1. 1 福州大学计算机与大数据学院 福州 350108
    2 福建省网络计算与智能信息处理重点实验室 福州 350108
    3 福建师范大学物理与能源学院 福州 350117
  • 发布日期:2023-11-09
  • 通讯作者: 林兵(WheelLX@163.com)
  • 作者简介:(wengjiefzu@163.com)
  • 基金资助:
    国家自然科学基金(62072108);福建省高校产学合作项目(2022H6024)

Multi-edge Server Load Balancing Strategy Based on Game Theory

WENG Jie1,2, LIN Bing2,3, CHEN Xing1,2   

  1. 1 College of Computer and Data Science,Fuzhou University,Fuzhou 350108,China
    2 Fujian Provincial Key Laboratory of Networking Computing and Intelligent Information Processing,Fuzhou 350108,China
    3 College of Physics and Energy,Fujian Normal University,Fuzhou 350117,China
  • Published:2023-11-09
  • About author:WENG Jie,born in 1999,postgraduate,is a member of China Computer Federation.His main research interests include cloud computing and edge computing and game theory.
    LIN Bing,born in 1986,Ph.D,associate professor,postgraduate supervisor,is a member of China Computer Federation.His main research interests include cloud computing and intelligent computing and its application.
  • Supported by:
    National Natural Science Foundation of China(62072108) and University-Industry Cooperation of Fujian Pro-vince(2022H6024).

PDF (PC)

162

摘要： 移动边缘计算(Mobile Edge Computing,MEC)作为一种新兴的计算范式,旨在弥补物联网中移动设备的计算、存储和带宽等资源的不足。由于地域、时间等因素,边缘服务器间的负载差异大,因此边缘服务器的负载均衡至关重要。文中提出了一种基于博弈论的边缘服务器负载均衡策略,其满足边缘服务器间的负载均衡需求。首先,将MEC服务器负载均衡问题建模为非合作博弈,引入基于近端分解算法(Proximal Decomposition Algorithm,PDA)的正则化方法来得到唯一的纳什均衡解。然后,根据建立的博弈模型,提出了一种分布式边缘服务器负载均衡算法(Distributed Load Balancing Algorithm,DLBA),优化系统响应时间与能耗。实验结果表明,DLBA能够通过较少的迭代次数快速达到纳什均衡点,且DLBA得到的策略在平均响应时延方面较本地计算策略、基于计算能力分配策略降低了18.39%和9.91%;在平均能耗方面较本地计算策略、基于计算能力分配策略降低了2.42%和7.33%;与粒子群遗传算法得到的最优策略差距较小,但计算时间仅为粒子群遗传算法的1.81%。因此,该策略可以有效降低系统响应时间和能量消耗,且执行时间较短,适用于真实场景。

关键词: 移动边缘计算, 博弈论, 非合作博弈, 分布式, 负载均衡

Abstract: As an emerging computing paradigm,mobile edge computing aims to make up for the shortage of computing,storage and bandwidth of mobile devices in the Internet of Things.Due to geographical and time factors,the load of edge servers varies greatly,so the load balancing of multi-edge servers is very important.This paper proposes a multi-edge server load balancing strategy based on game theory to meet the load balancing requirements among edge servers.Firstly,the MEC server load balancing problem is modeled as a non-cooperative game,and the unique Nash equilibrium solution is obtained by introducing the regularization method based on proximal decomposition algorithm.Then,according to the established game model,a distributed load balancing algorithm(DLBA) is proposed to optimize the system response time and energy consumption.Experimental results show that DLBA can quickly reach Nash equilibrium with fewer iterations.Compared with the local computing strategy and computing power allocation strategy,the average response delay of DLBA strategy is reduced by 18.39% and 9.91%,and the average energy consumption is reduced by 2.42% and 7.33%.The gap between DLBA and the optimal strategy obtained by particle swarm optimization genetic algorithm is small,but the computation time is only 1.81% of that of particle swarm optimization genetic algorithm.Therefore,the proposed strategy can effectively reduce the system response time and energy consumption,and the execution speed is fast,which is applicable to real scenarios.

Key words: Mobile edge computing, Game theory, Non-cooperative game, Distributed, Load balancing

中图分类号: 

  • TP393
[1]ANANTHANARAYANAN G,BAHL P,BODÍK P,et al.Real-time video analytics:The killer app for edge computing[J].Computer,2017,50(10):58-67.
[2]LI X,ZHANG X.Multi-task allocation under time constraints in mobile crowdsensing[J].IEEE Transactions on Mobile Computing,2019,20(4):1494-1510.
[3]XIANG C,ZHOU Y,DAI H,et al.Reusing delivery drones for urban crowdsensing[J].IEEE Transactions on Mobile Computing,2023,22(5):2972-2988.
[4]WANG Y,CHEN I R,WANG D C.A survey of mobile cloud computing applications:Perspectives and challenges[J].Wireless Personal Communications,2015,80(4):1607-1623.
[5]ABBAS N,ZHANG Y,TAHERKORDI A,et al.Mobile edgecomputing:A survey[J].IEEE Internet of Things Journal,2017,5(1):450-465.
[6]CHEN Q L,KUANG Z F.Task Offloading and Service Caching Algorithm Based on DDPG in Edge Computing[J].Computer Engineering,2021,47(10):26-33.
[7]ZHANG Y L,LIANG Y,YIN M,et al.Survey on the Methods of Computation Offloading in Mobile Edge Computing[J].Chinese Journal of Computers,2021,44(12):2406-2430.
[8]WANG S,TUOR T,SALONIDIS T,et al.Adaptive federated learning in resource constrained edge computing systems[J].IEEE Journal on Selected Areas in Communications,2019,37(6):1205-1221.
[9]DONG S,LI H L,QU Y,et al.Survey of Research on Computation Unloading Strategy in Mobile Edge Computing[J].Computer Science,2019,46(11):32-40.
[10]CHEN M H,LIANG B,DONG M.Joint offloading and resource allocation for computation and communication in mobile cloud with computing access point[C]//IEEE Conference on Compu-ter Communications(INFOCOM 2017).IEEE,2017:1-9.
[11]SHAH-MANSOURI H,WONG V W S.Hierarchical fog-cloud computing for IoT systems:A computation offloading game[J].IEEE Internet of Things Journal,2018,5(4):3246-3257.
[12]LIU S,YU Y,GUO L,et al.Adaptive delay-energy balancedpartial offloading strategy in Mobile Edge Computing networks[J/OL].Digital Communications and Networks,2022.http://doi,org/10.1016/j.dcan.2022.05.029.
[13]BERALDI R,MTIBAA A,ALNUWEIRI H.Cooperative load balancing scheme for edge computing resources[C]//2017 Se-cond International Conference on Fog and Mobile Edge Computing(FMEC).IEEE,2017:94-100.
[14]LIN B,ZHU F,ZHANG J,et al.A time-driven data placement strategy for a scientific workflow combining edge computing and cloud computing[J].IEEE Transactions on Industrial Informa-tics,2019,15(7):4254-4265.
[15]LIU C,LI K,LI K.A game approach to multi-servers load ba-lancing with load-dependent server availability consideration[J].IEEE Transactions on Cloud Computing,2018,9(1):1-13.
[16]FAN W,YAO L,HAN J,et al.Game-Based Multitype Task Of-floading Among Mobile-Edge-Computing-Enabled Base Stations[J].IEEE Internet of Things Journal,2021,8(24):17691-17704.
[17]CHEN X,HU J,CHEN Z,et al.A reinforcement learning-empowered feedback control system for industrial internet of things[J].IEEE Transactions on Industrial Informatics,2021,18(4):2724-2733.
[18]SHORTLE J F,THOMPSON J M,GROSS D,et al.Fundamentals of queueing theory[M].John Wiley & Sons,2018.
[19]LI S,TAO Y,QIN X,et al.Energy-aware mobile edge computation offloading for IoT over heterogenous networks[J].IEEE Access,2019,7:13092-13105.
[20]OWEN G.Game theory[M].Emerald Group Publishing,2013.
[21]BOYD S,BOYD S P,VANDENBERGHE L.Convex optimization[M].Cambridge university press,2004.
[22]SCUTARI G,PALOMAR D P,FACCHINEI F,et al.Monotone games for cognitive radio systems[M]//Distributed Decision Making and Control.Springer,London,2012:83-112.
[23]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.
[24]YI C,CAI J.A queueing game approach for fog computing with strategic computing speed control[C]//2019 IEEE Global Communications Conference(GLOBECOM).IEEE,2019:1-6.
[25]YAO Z W,LIN J W,HU J Q.PSO-GA Based Approach toMulti-edge Load Balancing[J].Computer Science,2021,48(S2):8.
[26]POLI R,KENNEDY J,BLACKWELL T.Particle swarm optimization[J].Swarm Intelligence,2007,1(1):33-57.
[27]MIRJALILI S.Genetic algorithm[M]//Evolutionary Algo-rithms and Neural Networks.Cham:Springer,2019:43-55.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发