2025年4月6日 2:36 星期日
 引 en
×

分享给微信好友或者朋友圈

使用微信“扫一扫”功能。

移动边缘计算中基于混合人工蜂群算法的计算卸载策略

  • 沈正林1

    机 构：

    1. 成都信息工程大学 计算机学院,成都, 610225

    ×
  • ，吴涛1

    机 构：

    1. 成都信息工程大学 计算机学院,成都, 610225

    ×
  • ，周启钊1

    机 构：

    1. 成都信息工程大学 计算机学院,成都, 610225

    ×
  • ，陈曦2

    机 构：

    2. 西南民族大学 计算机科学与技术学院,成都, 610225

    ×

1. 成都信息工程大学 计算机学院,成都, 610225；
2. 西南民族大学 计算机科学与技术学院,成都, 610225；

Computational offloading strategy based on hybrid artificial bee colony algorithm in mobile edge computing

  • SHEN Zhenglin1

    Affiliation：

    1. School of Computer Science,Chengdu University of Information Technology,Chengdu 610225 ,China

    ×
  • ，WU Tao1

    Affiliation：

    1. School of Computer Science,Chengdu University of Information Technology,Chengdu 610225 ,China

    ×
  • ，ZHOU Qizhao1

    Affiliation：

    1. School of Computer Science,Chengdu University of Information Technology,Chengdu 610225 ,China

    ×
  • ，CHEN Xi2

    Affiliation：

    2. School of Computer Science and Technology,Southwest Minzu University,Chengdu 610225 ,China

    ×

1. School of Computer Science,Chengdu University of Information Technology,Chengdu 610225 ,China；
2. School of Computer Science and Technology,Southwest Minzu University,Chengdu 610225 ,China；

作者简介:

沈正林,男,硕士生,主要从事边缘计算研究．1843963412@qq.com

通讯作者:

吴涛,女,博士,教授,主要从事并行计算、边缘计算与网络安全等方面的研究．wut@cuit.edu.cn

中图分类号:TN925.5；TP18

文献标识码:A

DOI:10.13878/j.cnki.jnuist.20230731005

参考文献 1
Mao Y Y,You C S,Zhang J,et al.A survey on mobile edge computing:the communication perspective[J].IEEE Communications Surveys & Tutorials,2017,19(4):2322-2358
查找原文
参考文献 2
董思岐,李海龙,屈毓锛,等.移动边缘计算中的计算卸载策略研究综述[J].计算机科学,2019,46(11):32-40;DONG Siqi,LI Hailong,QU Yuben,et al.Survey of research on computation unloading strategy in mobile edge computing[J].Computer Science,2019,46(11):32-40
查找原文
参考文献 3
Liang L,Xiao J T,Ren Z,et al.Particle swarm based service migration scheme in the edge computing environment[J].IEEE Access,2020,8:45596-45606
查找原文
参考文献 4
章呈瑞,柯鹏,尹梅.改进人工蜂群算法及其在边缘计算卸载的应用[J].计算机工程与应用,2022,58(7):150-161;ZHANG Chengrui,KE Peng,YIN Mei.Improved artificial bee colony algorithm and its application in edge computing offloading[J].Computer Engineering and Applications,2022,58(7):150-161
查找原文
参考文献 5
Sun Y Y,Song C H,Yu S M,et al.Energy-efficient task offloading based on differential evolution in edge computing system with energy harvesting[J].IEEE Access,2021,9:16383-16391
查找原文
参考文献 6
罗斌,于波.移动边缘计算中基于粒子群优化的计算卸载策略[J].计算机应用,2020,40(8):2293-2298;LUO Bin,YU Bo.Computation offloading strategy based on particle swarm optimization in mobile edge computing[J].Journal of Computer Applications,2020,40(8):2293-2298
查找原文
参考文献 7
Islam A,Debnath A,Ghose M,et al.A survey on task offloading in multi-access edge computing[J].Journal of Systems Architecture,2021,118:102225
查找原文
参考文献 8
Abbasi M,Mohammadi-Pasand E,Khosravi M R.Intelligent workload allocation in IoT-fog-cloud architecture towards mobile edge computing[J].Computer Communications,2021,169:71-80
查找原文
参考文献 9
简琤峰,陈家炜,张美玉.面向边缘计算的改进混沌蝙蝠群协同调度算法[J].小型微型计算机系统,2019,40(11):2424-2430;JIAN Chengfeng,CHEN Jiawei,ZHANG Meiyu.Improved chaotic bat swarm cooperative scheduling algorithm for edge computing[J].Journal of Chinese Computer Systems,2019,40(11):2424-2430
查找原文
参考文献 10
Feng S L,Chen Y J,Zhai Q H,et al.Optimizing computation offloading strategy in mobile edge computing based on swarm intelligence algorithms[J].EURASIP Journal on Advances in Signal Processing,2021,2021(1):1-15
查找原文
参考文献 11
Pham H G T,Pham Q V,Pham A T,et al.Joint task offloading and resource management in NOMA-based MEC systems:a swarm intelligence approach[J].IEEE Access,2020,8:190463-190474
查找原文
参考文献 12
刘建华,李炜,刘佳嘉,等.基于多代理模仿学习的普适边缘计算资源分配[J].南京信息工程大学学报,2024,16(1):83-96;LIU Jianhua,LI Wei,LIU Jiajia,et al.Resource allocation for pervasive edge computing based on multi-agent imitation learning[J].Journal of Nanjing University of Information Science & Technology,2024,16(1):83-96
查找原文
参考文献 13
Tizhoosh H R.Opposition-based learning:a new scheme for machine intelligence[C]//International Conference on Computational Intelligence for Modelling,Control and Automation and International Conference on Intelligent Agents,Web Technologies and Internet Commerce.November 28-30,2005,Vienna,Austria.IEEE,2006:695-701
查找原文
参考文献 14
匡芳君,金忠,徐蔚鸿,等.Tent混沌人工蜂群与粒子群混合算法[J].控制与决策,2015,30(5):839-847;KUANG Fangjun,JIN Zhong,XU Weihong,et al.Hybridization algorithm of Tent chaos artificial bee colony and particle swarm optimization[J].Control and Decision,2015,30(5):839-847
查找原文
参考文献 15
Alatas B.Chaotic bee colony algorithms for global numerical optimization[J].Expert Systems with Applications,2010,37(8):5682-5687
查找原文
参考文献 16
Mirjalili S.SCA:a sine cosine algorithm for solving optimization problems[J].Knowledge-Based Systems,2016,96:120-133
查找原文
参考文献 17
雍龙泉,黎延海,贾伟.正弦余弦算法的研究及应用综述[J].计算机工程与应用,2020,56(14):26-34;YONG Longquan,LI Yanhai,JIA Wei.Literature survey on research and application of sine cosine algorithm[J].Computer Engineering and Applications,2020,56(14):26-34
查找原文
目录contents

    摘要

    计算卸载是移动边缘计算(Mobile Edge Computing,MEC)中的关键技术．针对多用户多MEC服务器场景中计算卸载策略的不足,本文提出一种混合人工蜂群算法(Artificial Reverse Sine-Cosine,ARSC)．首先,使用反向学习策略初始化种群,优化种群的初始解;然后,在雇佣蜂阶段利用正余弦算法的全局最优引导信息,提升算法的局部搜索能力;最后，为了平衡算法的全局搜索能力和局部搜索能力,引入动态感知因子对算法的步长因子进行改进．仿真实验结果表明,相比基于粒子群算法的卸载策略、基于人工蜂群算法的卸载策略,ARSC策略在系统时延、系统能耗、收敛性等指标上均有所改善．

    Abstract

    Computational offloading is an essential technology in Mobile Edge Computing (MEC).To address the shortage of computational offloading strategies in multi-user and multi-MEC server scenarios,this paper proposes a hybrid artificial bee colony approach (Artificial Reverse Sine-Cosine,ARSC).First,the opposition-based learning strategy is used to initialize the population and optimize the initial solution of the population.Then the global optimal bootstrap information of the sine-cosine algorithm is exploited to improve the local search capability in the employed bee stage.Finally,to balance the global and local search capability of the approach,the step size factor is adapted by introducing dynamic perception.Simulation results show that the proposed ARSC approach outperforms offloading strategies based on particle swarm algorithm and artificial bee colony algorithm in convergence,latency,and energy consumption.

  • 0 引言

  • 近年来，随着物联网、云计算、大数据等技术的高速发展，用户数据规模呈指数型增长．传统的云计算模式需要上传大量本地数据到云服务器，但由于云服务器部署离本地终端较远，传输过程中的响应延迟、能量损耗、网络干扰、数据安全等问题难以避免．为了解决云计算中心离终端设备较远带来的时延、能耗等问题，学者们提出将云的功能向网络边缘转移[1]．在接近移动终端设备的网络边缘端，移动边缘计算（Mobile Edge Computing，MEC）作为提供信息技术服务且具有计算能力的一种新型网络结构和计算范式被提出．

  • 边缘计算并不是取代云计算，而是作为传统云计算的延伸．它将部分数据处理和服务迁移到离用户更近的网络边缘节点上，从而降低网络延迟、提高用户体验和数据安全性．然而，移动设备仍然面临着资源和能耗方面的限制，无法满足一些复杂或者实时性要求高的任务[2]．因此，如何将这些计算任务卸载到边缘服务器进行处理，成为边缘计算中备受关注的关键技术．

  • 国内外研究人员针对边缘计算中的计算卸载进行了大量研究．文献[3]将工业物联网环境下的任务卸载问题建模为一个多用户多边缘服务器问题，使用粒子群算法（Particle Swarm Optimization，PSO）对任务进行卸载．文献[4]针对多设备MEC系统中计算任务的执行时间以及终端设备的能耗最小化问题，构建了一个云服务器辅助的多MEC服务器计算卸载模型，并提出一种改进的人工蜂群算法（Artificial Bee Colony algorithm，ABC）．文献[5]针对能量和频谱资源稀缺的问题，提出一种基于差分进化算法（Differential Evolution，DE）的任务卸载方法，该方案考虑了能源站的发射功率和边缘服务器的计算能力等约束条件，建立了无线能源供应的边缘计算网络模型．文献[6]将工业生产线中的计算卸载问题建模为多用户、多MEC时延优化问题，为了消除本地设备使用能耗来换取时延的问题，通过惩罚函数平衡时延与能耗，并提出一种基于粒子群算法优化的卸载策略．

  • 任务卸载策略求解过程属于NP难问题[7]，MEC研究中大多将其转化为多因素优化问题．文献[8]在物联网场景下，使用遗传算法作为任务卸载策略，显著降低了设备的能耗和数据传输的时延．为了解决边缘计算中任务卸载调度的优化问题，文献[9]对蝙蝠群算法（BA）进行改进，提出一种改进混沌蝙蝠群协同卸载方法，该方案大大减少了任务完成的时延，从而满足任务实时处理的需求．文献[10]通过对模型中的三个目标分别进行归一化，消除维度的影响，对模型进行了改进，并引入灰狼优化算法（GWO）求解模型．文献[11]基于非正交多址的多址边缘计算系统，研究了卸载决策、子信道分配、发射功率和计算资源分配的联合优化问题，使用鲸鱼群算法（WOA）解决了发射功率和子信道分配的问题．文献[12]将多代理生成对抗模仿学习和马尔可夫策略相结合以逼近专家性能，实现算法的在线执行，最后结合非支配排序遗传算法Ⅱ（NSGA-Ⅱ），对时延和能耗进行联合优化．

  • 现有研究中的MEC卸载策略模型缺少对排队等待时延的考虑，无法有效均衡边缘服务器的计算资源．为了降低任务积压在服务器中导致系统时延增加的影响，采用积压队列模型，以防止边缘服务器中的任务队列因积压过多的计算任务导致系统总的时延增加，并针对多用户多MEC系统卸载模型，提出一种混合人工蜂群算法（Artificial Reverse Sine-Cosine，ARSC）．ARSC使用反向学习策略对人工蜂群算法的初始化阶段进行优化，并充分考虑正余弦算法收敛性强的优点，通过融合正余弦算法，提升算法的局部搜索能力．同时，引入动态感知因子改进算法的步长因子，进一步平衡算法的全局搜索能力和局部探索能力．

  • 1 系统模型

  • 本研究构建了一个多用户多MEC系统架构，如图1所示．系统包含用户层、边缘层．边缘层有m个基站，MEC={1，2，3，···，m}，每个基站上部署一个边缘服务器．本研究主要着眼于移动边缘计算网络中卸载任务的调配，使计算资源的调配更加高效合理，因此移动设备产生的计算任务采用二元任务迁移模型．二元任务迁移模型是指移动设备产生的单个任务是不可拆分的，任务要么被卸载到边缘服务器，要么在本地终端进行计算．每个任务由一个三元组构成，ti={wi，fi，cpui}，其中，wi表示任务的数据量，fi表示每bit数据需要的cpu时钟周期数，cpui表示任务所需要的计算资源．

  • 1.1 时延模型

  • 任务在不同的设备上执行有不同的时延模型:当任务在本地移动设备上执行，只需要考虑任务在移动设备上产生的计算时延; 当任务被卸载到边缘服务器上执行，需要考虑任务上传的传输时延、服务器上的等待时延、计算时延、下传的传输时延．因为下传时延远远低于上传时延，故本文不考虑下传的传输时延．

  • 图1 系统架构

  • Fig.1 System architecture

  • 1.1.1 本地计算时延模型

  • 当移动设备在本地执行的时候，其任务执行时间如式（1）所示，其中，flocal，i为移动设备的cpu时钟频率．

  • Tlocal ,i=wififlocal ,i
    (1)

  • 1.1.2 积压队列模型

  • 边缘服务器节点的计算能力是有限的，当一个服务节点中积压大量计算任务时，会产生等待时延，从而导致系统时延的增加．为了有效利用边缘服务器中的计算资源来减少等待时延，所以引入积压队列模型．当任务在边缘服务器中的计算时延超过在本地计算时延时，边缘服务器拒接卸载当前任务．边缘节点中任务队列的执行过程如图2所示．

  • 任务1、任务2、任务3，任务4到达边缘服务器节点的时间分别为t1，t2，t3，t4．假设，任务1~3到达服务器节点时，服务器的计算资源能够满足任务1~3立刻执行，而任务4到达边缘服务器节点时计算资源不能够满足任务4立即执行，需要等待其他任务执行完成后释放计算资源才能执行．假设任务1释放计算资源后能够满足任务4的需求，并且任务4在边缘服务器的计算时延不超过本地计算时延，则任务4的等待时延为任务1的执行完成时延t5与任务4的到达时延t4的差值．如果任务4在边缘服务器中的计算时延超过本地计算时延，则拒接卸载．

  • 任务在边缘服务器中的计算时延存在如下两种情况：

  • 图2 边缘节点任务队列执行过程

  • Fig.2 Computing process of edge node tasks

  • 1）当任务到达边缘服务器后，若当前边缘服务器的计算资源不能满足任务立即执行，此时需要等待任务队列中其他任务执行完成后方可参与计算，任务时延（Tmec，i）如式（2）所示:

  • Tmec ,i=Ttrans ,i+Twait ,i+Texecute ,i, s.t. cpui>cpuj,Tmec ,i⩽Tleaol ,i.
    (2)

  • 传输时延（Ttrans，i）如式（3）所示，其中，γi，j表示移动设备与边缘服务器之间的传输速率．香农公式（4）中，W表示移动设备与边缘服务器之间的传输带宽，pi表示移动设备的发射功率，Hi，j表示移动设备和边缘服务器之间的信道增益，N0表示噪声功率．

  • Ttrans ,i=wiγi,j,
    (3)
  • γi,j=W⋅lb⁡1+pi⋅Hi,jN0.
    (4)

  • 执行时延（Texecute，i）如式（5）所示，其中，fmec，j表示边缘服务器的cpu时钟频率．

  • Texecute ,i=wififmec ,j
    (5)

  • 边缘服务器中的积压任务队列S（j）采用先进先出队列模型（First Input First Output，FIFO），任务遵循先来先服务原则，积压队列如图3所示．通过任务队列可以计算任务的等待时延（Twait，i），如式（6）所示．首先从任务队列中找到最快释放资源并且能够满足任务i需求的任务完成时间Tmec，k，然后再根据任务i的到达时间Ttrans，i，两者的差值即任务i的等待时延.

  • Twait ,i=0, s.t. cpui⩽cpujTmec ,k-Ttrans ,i, s.t. cpui>cpuj.
    (6)

  • 图3 积压队列模型

  • Fig.3 Backlog queue model

  • 2）当任务到达边缘服务器后，若边缘服务器剩余资源满足任务所需计算资源，即cupi≤cpuj，Tmec，i≤Tlocal，i，此时任务可以立即执行，任务完成时间如式（7）所示:

  • Tmec ,i=Ttrans ,i+Texecute ,i, s.t. cpui<cpuj,Tmec ,i⩽Tleaol ,i.
    (7)

  • 1.2 能耗模型

  • ARSC算法设计的初衷是降低移动设备的时延和能耗，所以在能耗模型中只考虑移动设备的执行能耗和传输能耗．

  • 任务在本地执行的能耗和任务的传输能耗分别如式（8）和（9）所示，其中，Tlocal，i表示任务的本地执行时延，Ttrans，i表示任务传输时延，plocal，i表示移动设备的本地计算功率，pi表示移动设备的发射功率．

  • Elocal ,i=Tlocal ,i⋅plocal ,i,
    (8)
  • Etrans ,i=Ttrans ,i⋅pi⋅
    (9)

  • 任务总的时延Tall和总的能耗Eall分别如式（10）和（11）所示，其中，k=1代表任务在本地执行，k=0代表任务在边缘服务器中执行．

  • Tall =∑t=0n kTlocal ,i+(1-k)Tmec ,i,
    (10)
  • Eall =∑t=0n kElocal ,i+(1-k)Etrans ,i,
    (11)

  • 1.3 目标函数

  • 把当前系统模型转化为有约束条件下联合时延和能耗的最小化问题，目标函数Q如式（12）所示．

  • Q=exp⁡-θ1TL-Tall TL+θ2EL-Eall EL
    (12)
  • s.t. Tall <TL,Eall<EL,Tmec,i⩽Tlocal ,i,cpui<cpuj,θ1,θ2∈[0,1],θ1+θ2=1.
    (13)

  • 其中:TL为所有任务在本地设备执行的时延; EL为所有任务在本地设备执行的能耗; Tall和Eall越小，目标函数值Q越小; 系数θ1和θ2分别表示时延和能耗在系统中所占的比重，为了平衡时延和能耗，本文θ1和θ2取值都为0.5．

  • 2 基于ARSC算法的卸载决策

  • 2.1 基本的人工蜂群算法

  • 1）初始化阶段:设定蜜源数量NS、问题维度D、最大迭代次数Gmax、最大失败尝试次数Nlimit，根据式（14）初始化蜜源位置．其中，Xjmax、Xjmin分别表示各维度的上下界，rand（0，1）表示[0，1]上均匀分布的随机数．

  • Xi,j=Xjmin+rand⁡(0,1)×Xjmax-Xjmin,i∈1,2,⋯,NS,j∈{1,2,⋯,D}.
    (14)

  • 2）雇佣蜂阶段:雇佣蜂更新蜜源位置的公式如式（15）所示．其中，φ为[-1，1]之间均匀分布的随机数，Xi，jnew 表示新的蜜源位置．比较新蜜源位置和旧蜜源位置，使用贪婪策略保留较好的蜜源．

  • Xi,jnew =Xi,j+φXi,j+Xk,j,k∈1,2,⋯,NS.
    (15)

  • 3）跟随蜂阶段:跟随蜂收集雇佣蜂传递的蜜源信息按照式（16）计算跟随每一个雇佣蜂的概率，然后以轮盘赌策略的方式来选择跟随对象．其中:f（Xi）表示最小化问题的函数值; fitnessi代表适应度值（式（17）），适应度值越大的蜜源越优秀，越容易被选择．

  • pi= fitness i∑j=1NS fitnessj,
    (16)
  • fitness i=1+fXi, fXi<0;11+fXi, fXi⩾0.
    (17)

  • 4）侦察蜂阶段:当蜜源位置超过Nlimit次都没有更新，则雇佣蜂会放弃该蜜源转化为侦察蜂，并按照式（14）重新初始化蜜源位置．

  • 2.2 混合人工蜂群算法

  • 2.2.1 反向学习策略

  • 传统的人工蜂群算法初始化蜜源位置采用随机策略，而蜜源位置在解空间的分布直接影响算法的收敛速度和最终结果．为了改善蜜源位置，采用反向学习（Opposition-Based Learning，OBL）对初始解进行优化．反向学习[13]是一种优化策略，基本思想是通过计算当前解的反向解来扩大搜索范围，以此来找出问题更好的解．

  • 根据式（18）生成反向解，然后使用贪婪策略从正向解和反向解的集合H中选出NS个目标函数值最优的解作为初始种群S0．

  • Xi,jreverse =Xjmax+Xjmin-Xi,j,
    (18)
  • H=X1,X2,⋯,XNS,XNS+1reverse ,⋯,X2NSreverse .
    (19)

  • 2.2.2 正余弦策略

  • 基本人工蜂群算法（ABC）及其搜索策略侧重于提升全局搜索能力[14]，但由于ABC在每一代不直接使用全局最优信息，只是存储其最优信息，导致其局部搜索能力较弱[15]．为了增强算法的局部搜索能力，在人工蜂群算法的雇佣蜂阶段引入正余弦算法（Sine-Cosine Algorithm，SCA）[16]．这种方法通过采用正余弦算法中的全局最优解的引导信息来增强算法的局部搜索能力，利用正余弦算法的正余弦模型的振荡特性来平衡探索与开发能力．混合人工蜂群算法的雇佣蜂阶段蜜源位置更新策略为

  • Xi,jt+1=Xi,jt+r1sin⁡r2⋅r3Xbest -Xi,jt,r4<0.5;Xi,jt+r1cos⁡r2⋅r3Xbest -Xi,jt,r4⩾0.5.
    (20)

  • 其中:r2是[0，2π]之间的随机数，表示当前个体更新时朝向或远离当前最优个体所能达到的最远距离; r3是[0，2]之间的随机数，决定了当前已知最优个体影响当前个体的程度; r4是[0，1]之间的随机数，表示在正弦函数和余弦函数之间的随机取值，解除了移动步长和移动方向可能的耦合关系; r1是当前个体在迭代中的移动步长，

  • r1=a-attmax
    (21)

  • 其中:a是一个常数; tmax是最大迭代次数．当步长因子r1较高时，表示有利于全局搜索，当步长因子较低时有利于局部搜索．因此，步长因子对寻找最优解至关重要，故在此处引入动态感知因子（Dynamic Perception，DP）[17]．动态感知因子可以帮助算法在前期阶段提升算法的全局搜索能力，扩大搜索的解空间，在算法后期提升算法的局部搜索能力，提升算法获取最优解的能力．

  • DP=a1-ttmax2, t>tmax2;a1-ttmax2, t⩽tmax2.
    (22)

  • 2.2.3 编码和解码

  • 为了使人工蜂群算法和正余弦算法能够应用于边缘计算卸载问题，需要对算法进行离散化处理．

  • 假设边缘服务器的数量为m、任务数量为n，卸载决策如式（23）所示，X表示一个卸载策略，其中，xi的取值表示分配到边缘服务器或者本地设备．

  • X=x1,x2,⋯,xn,x∈[0,m].
    (23)

  • 1）对人工蜂群蜜源位置更新策略进行离散化:式（24）中的Vi，j表示位移的增量.假设边缘服务器数量m为5，任务数量n为5，Vi，j的取值范围是[-5，5]．Vi，j大于0表示计算位置向后移动，Vi，j小于0表示向前移动，Vi，j等于0表示任务继续在当前服务器进行计算．人工蜂群算法位置更新策略如式（25）所示，为了保证更新后的位置值在区间[0，5]，需要对相加后的位置值取余．

  • Vi,j=φXi,j+Xk,j,
    (24)
  • Xi,j=Xi,j+Vi,j%m, vi,j⩾0;Xi,j+Vi,j+m%m, vi,j<0.
    (25)

  • 2）对正余弦算法的位置更新进行离散化:式（26）中的Vi，j表示向着最优解移动的方向和大小．为了保证Vi，j的值在区间[-5，5]，当Vi，j的值比-5低时，令Vi，j=-5，当Vi，j的值大于5时，令Vi，j=5．正余弦算法的位置更新公式如式（27）所示．

  • Vi,j=r1⋅sin⁡r2⋅r3Xbest -Xi,jt, r4<0.5;r1⋅cos⁡r2⋅r3Xbest -Xi,jt, r4⩾0.5.
    (26)
  • Xi,jt+1=Xi,jt+Vi,j'%m, vi,j⩾0;Xi,jt+Vi,j'+m%m, vi,j<0.
    (27)

  • 2.2.4 算法伪代码

  • ARSC算法如下所示：

  • 3 仿真结果分析

  • 3.1 仿真环境和参数

  • 本文所有算法通过Python3实现，实验环境为 Windows10 64 位操作系统，Intel Core i5-11400H CPU，16 GB内存．仿真用到的主要参数如表1所示．

  • 3.2 结果分析

  • 根据表1的仿真参数进行实验，本文采用本地卸载策略（LA）、随机卸载策略（RA）、基于粒子群算法的卸载策略（PSO）、基于人工蜂群算法的卸载策略（ABC）、混合人工蜂群算法卸载策略（ARSC）来分析系统总的时延和能耗．

  • 3.2.1 不同任务数量下的能耗和时延

  • 为了比较不同任务数量下的各卸载决策的能耗和时延，本组实验参数设置为任务数量分别为50、100、150、200、250，边缘服务器数量设置为10个，任务的数据量为20 MB．实验结果如图4所示．由图4可知，在不同任务数量下ARSC方法的时延和能耗都优于其他方法．在任务数量为250时，ARSC方法相较于本地卸载和随机卸载分别降低51.3%、21.8%的时延和90.3%、47.2%的能耗; 相较于ABC方法和PSO方法，在任务数量为250的则分别降低16.3%、16.6%的时延和11.9%、31.5%的能耗．由此可见，ARSC算法的局部搜索能力和全局搜索能力相较于ABC算法都得到了改善．

  • 表1 参数设置

  • Table1 Parameter setting

  • 图4 不同任务数量下的系统时延和能耗

  • Fig.4 System latency and energy consumption for different number of tasks

  • 3.2.2 各方法收敛性对比

  • 为了比较ARSC、ABC、PSO三种算法的收敛性，设置任务数量为50，边缘服务器数量为10，实验结果如图5所示．由图5可知，ARSC算法有很强的全局搜索能力，在算法的前期不断寻找全局最优解，且在后期拥有良好的局部搜索能力．在时延上，ARSC相较于ABC和PSO算法，分别降低6.4%和11.7%; 在能耗上，ARSC算法相较于ABC算法和PSO算法，分别降低5.2%和6.6%．

  • 图5 方法收敛性比较

  • Fig.5 Comparison of algorithm convergence

  • 3.2.3 任务的等待时延分析

  • 为了分析任务所需计算资源增多时，是否造成系统的等待时延增加．本组实验参数设置任务数量为50，任务的数据量为20 MB，边缘服务器的数量为10，任务所需资源量为1、1.5、2、2.5和3 GHz．由图6可知．当任务所需计算资源为0.5、1和1.5 GHz时，任务的等待时延在总的系统时延中所占比重较少，此时的边缘服务器资源能够满足同时执行多个任务，所以系统总的时延增加较少．当任务所需的计算资源达到1.5 GHz以上时，等待时延在总的系统时延中占比较大，系统总的等待时延增加较多，此时的边缘服务器资源不能同时满足多个任务同时执行，造成统总的时延和等待时延的增加．ARSC卸载策略相比其他卸载策略总的等待时延最小．

  • 3.2.4 不同任务数据量下的时延和能耗

  • 为了比较不同任务数据量下的各卸载决策的能耗和时延，本组实验参数设置为任务数量为50，边缘服务器数量设置为10个，任务的数据量分别7、14、21、28和35 MB．实验结果如图7所示．由图7可知，随着任务的数据量增加本地卸载策略的时延和能耗会快速增加，而基于ARSC方法的卸载策略的时延和能耗相对于其他方法都是最优的．在数据量为35 MB下，相较于LA、RA、PSO、ABC卸载策略，时延分别降低61.6%、19.1%、5.4%、2.5%，能耗分别降低66.1%、25.8%、8.8%、8.3%．

  • 图6 任务所需计算资源对系统时延的影响

  • Fig.6 Impact of computational resources required for tasks on system latency

  • 图7 不同任务数据量下的系统时延和能耗

  • Fig.7 System latency and energy consumption for different task data volumes

  • 4 结论

  • 本文针对多用户多MEC场景下计算卸载问题进行了研究．首先，将该场景下的计算卸载问题转化为联合时延和能耗最小化模型，并提出积压队列模型，防止边缘服务器中积压过多计算任务导致的系统总时延的增加．其次，提出一种混合人工蜂群算法卸载策略ARSC，该算法利用正余弦算法的全局最优引导信息提升人工蜂群算法的局部搜索能力，同时使用反向学习策略优化算法的初始阶段，并引入动态感知因子进一步平衡算法的全局搜索能力和局部搜索能力．最后，对算法进行离散化处理，使其符合边缘计算应用模型．通过实验分析表明，ARSC算法相较于ABC、PSO算法，在系统时延、能耗、系统总的代价等指标上均有改善．

  • 参考文献

    • [1] Mao Y Y,You C S,Zhang J,et al.A survey on mobile edge computing:the communication perspective[J].IEEE Communications Surveys & Tutorials,2017,19(4):2322-2358

    • [2] 董思岐,李海龙,屈毓锛,等.移动边缘计算中的计算卸载策略研究综述[J].计算机科学,2019,46(11):32-40;DONG Siqi,LI Hailong,QU Yuben,et al.Survey of research on computation unloading strategy in mobile edge computing[J].Computer Science,2019,46(11):32-40

    • [3] Liang L,Xiao J T,Ren Z,et al.Particle swarm based service migration scheme in the edge computing environment[J].IEEE Access,2020,8:45596-45606

    • [4] 章呈瑞,柯鹏,尹梅.改进人工蜂群算法及其在边缘计算卸载的应用[J].计算机工程与应用,2022,58(7):150-161;ZHANG Chengrui,KE Peng,YIN Mei.Improved artificial bee colony algorithm and its application in edge computing offloading[J].Computer Engineering and Applications,2022,58(7):150-161

    • [5] Sun Y Y,Song C H,Yu S M,et al.Energy-efficient task offloading based on differential evolution in edge computing system with energy harvesting[J].IEEE Access,2021,9:16383-16391

    • [6] 罗斌,于波.移动边缘计算中基于粒子群优化的计算卸载策略[J].计算机应用,2020,40(8):2293-2298;LUO Bin,YU Bo.Computation offloading strategy based on particle swarm optimization in mobile edge computing[J].Journal of Computer Applications,2020,40(8):2293-2298

    • [7] Islam A,Debnath A,Ghose M,et al.A survey on task offloading in multi-access edge computing[J].Journal of Systems Architecture,2021,118:102225

    • [8] Abbasi M,Mohammadi-Pasand E,Khosravi M R.Intelligent workload allocation in IoT-fog-cloud architecture towards mobile edge computing[J].Computer Communications,2021,169:71-80

    • [9] 简琤峰,陈家炜,张美玉.面向边缘计算的改进混沌蝙蝠群协同调度算法[J].小型微型计算机系统,2019,40(11):2424-2430;JIAN Chengfeng,CHEN Jiawei,ZHANG Meiyu.Improved chaotic bat swarm cooperative scheduling algorithm for edge computing[J].Journal of Chinese Computer Systems,2019,40(11):2424-2430

    • [10] Feng S L,Chen Y J,Zhai Q H,et al.Optimizing computation offloading strategy in mobile edge computing based on swarm intelligence algorithms[J].EURASIP Journal on Advances in Signal Processing,2021,2021(1):1-15

    • [11] Pham H G T,Pham Q V,Pham A T,et al.Joint task offloading and resource management in NOMA-based MEC systems:a swarm intelligence approach[J].IEEE Access,2020,8:190463-190474

    • [12] 刘建华,李炜,刘佳嘉,等.基于多代理模仿学习的普适边缘计算资源分配[J].南京信息工程大学学报,2024,16(1):83-96;LIU Jianhua,LI Wei,LIU Jiajia,et al.Resource allocation for pervasive edge computing based on multi-agent imitation learning[J].Journal of Nanjing University of Information Science & Technology,2024,16(1):83-96

    • [13] Tizhoosh H R.Opposition-based learning:a new scheme for machine intelligence[C]//International Conference on Computational Intelligence for Modelling,Control and Automation and International Conference on Intelligent Agents,Web Technologies and Internet Commerce.November 28-30,2005,Vienna,Austria.IEEE,2006:695-701

    • [14] 匡芳君,金忠,徐蔚鸿,等.Tent混沌人工蜂群与粒子群混合算法[J].控制与决策,2015,30(5):839-847;KUANG Fangjun,JIN Zhong,XU Weihong,et al.Hybridization algorithm of Tent chaos artificial bee colony and particle swarm optimization[J].Control and Decision,2015,30(5):839-847

    • [15] Alatas B.Chaotic bee colony algorithms for global numerical optimization[J].Expert Systems with Applications,2010,37(8):5682-5687

    • [16] Mirjalili S.SCA:a sine cosine algorithm for solving optimization problems[J].Knowledge-Based Systems,2016,96:120-133

    • [17] 雍龙泉,黎延海,贾伟.正弦余弦算法的研究及应用综述[J].计算机工程与应用,2020,56(14):26-34;YONG Longquan,LI Yanhai,JIA Wei.Literature survey on research and application of sine cosine algorithm[J].Computer Engineering and Applications,2020,56(14):26-34

  • 基本信息

    中图分类号: TN925.5；TP18
    文献标识码: A
    DOI: 10.13878/j.cnki.jnuist.20230731005

    基金信息

    四川省重点研发计划(23ZDYF0171, 23RKX0645)；

    引用信息

    稿件历史

    收稿日期: 2023-07-31

  • 参考文献

    • [1] Mao Y Y,You C S,Zhang J,et al.A survey on mobile edge computing:the communication perspective[J].IEEE Communications Surveys & Tutorials,2017,19(4):2322-2358

    • [2] 董思岐,李海龙,屈毓锛,等.移动边缘计算中的计算卸载策略研究综述[J].计算机科学,2019,46(11):32-40;DONG Siqi,LI Hailong,QU Yuben,et al.Survey of research on computation unloading strategy in mobile edge computing[J].Computer Science,2019,46(11):32-40

    • [3] Liang L,Xiao J T,Ren Z,et al.Particle swarm based service migration scheme in the edge computing environment[J].IEEE Access,2020,8:45596-45606

    • [4] 章呈瑞,柯鹏,尹梅.改进人工蜂群算法及其在边缘计算卸载的应用[J].计算机工程与应用,2022,58(7):150-161;ZHANG Chengrui,KE Peng,YIN Mei.Improved artificial bee colony algorithm and its application in edge computing offloading[J].Computer Engineering and Applications,2022,58(7):150-161

    • [5] Sun Y Y,Song C H,Yu S M,et al.Energy-efficient task offloading based on differential evolution in edge computing system with energy harvesting[J].IEEE Access,2021,9:16383-16391

    • [6] 罗斌,于波.移动边缘计算中基于粒子群优化的计算卸载策略[J].计算机应用,2020,40(8):2293-2298;LUO Bin,YU Bo.Computation offloading strategy based on particle swarm optimization in mobile edge computing[J].Journal of Computer Applications,2020,40(8):2293-2298

    • [7] Islam A,Debnath A,Ghose M,et al.A survey on task offloading in multi-access edge computing[J].Journal of Systems Architecture,2021,118:102225

    • [8] Abbasi M,Mohammadi-Pasand E,Khosravi M R.Intelligent workload allocation in IoT-fog-cloud architecture towards mobile edge computing[J].Computer Communications,2021,169:71-80

    • [9] 简琤峰,陈家炜,张美玉.面向边缘计算的改进混沌蝙蝠群协同调度算法[J].小型微型计算机系统,2019,40(11):2424-2430;JIAN Chengfeng,CHEN Jiawei,ZHANG Meiyu.Improved chaotic bat swarm cooperative scheduling algorithm for edge computing[J].Journal of Chinese Computer Systems,2019,40(11):2424-2430

    • [10] Feng S L,Chen Y J,Zhai Q H,et al.Optimizing computation offloading strategy in mobile edge computing based on swarm intelligence algorithms[J].EURASIP Journal on Advances in Signal Processing,2021,2021(1):1-15

    • [11] Pham H G T,Pham Q V,Pham A T,et al.Joint task offloading and resource management in NOMA-based MEC systems:a swarm intelligence approach[J].IEEE Access,2020,8:190463-190474

    • [12] 刘建华,李炜,刘佳嘉,等.基于多代理模仿学习的普适边缘计算资源分配[J].南京信息工程大学学报,2024,16(1):83-96;LIU Jianhua,LI Wei,LIU Jiajia,et al.Resource allocation for pervasive edge computing based on multi-agent imitation learning[J].Journal of Nanjing University of Information Science & Technology,2024,16(1):83-96

    • [13] Tizhoosh H R.Opposition-based learning:a new scheme for machine intelligence[C]//International Conference on Computational Intelligence for Modelling,Control and Automation and International Conference on Intelligent Agents,Web Technologies and Internet Commerce.November 28-30,2005,Vienna,Austria.IEEE,2006:695-701

    • [14] 匡芳君,金忠,徐蔚鸿,等.Tent混沌人工蜂群与粒子群混合算法[J].控制与决策,2015,30(5):839-847;KUANG Fangjun,JIN Zhong,XU Weihong,et al.Hybridization algorithm of Tent chaos artificial bee colony and particle swarm optimization[J].Control and Decision,2015,30(5):839-847

    • [15] Alatas B.Chaotic bee colony algorithms for global numerical optimization[J].Expert Systems with Applications,2010,37(8):5682-5687

    • [16] Mirjalili S.SCA:a sine cosine algorithm for solving optimization problems[J].Knowledge-Based Systems,2016,96:120-133

    • [17] 雍龙泉,黎延海,贾伟.正弦余弦算法的研究及应用综述[J].计算机工程与应用,2020,56(14):26-34;YONG Longquan,LI Yanhai,JIA Wei.Literature survey on research and application of sine cosine algorithm[J].Computer Engineering and Applications,2020,56(14):26-34

    • 地址：江苏省南京市宁六路219号    邮编：210044

    联系电话：025-58731025    E-mail：nxdxb@nuist.edu.cn

    南京信息工程大学学报 ® 2025 版权所有  技术支持：北京勤云科技发展有限公司