高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于混合粒子群算法的计算卸载成本优化

周天清 曾新亮 胡海琴

周天清, 曾新亮, 胡海琴. 基于混合粒子群算法的计算卸载成本优化[J]. 电子与信息学报, 2022, 44(9): 3065-3074. doi: 10.11999/JEIT211390
引用本文: 周天清, 曾新亮, 胡海琴. 基于混合粒子群算法的计算卸载成本优化[J]. 电子与信息学报, 2022, 44(9): 3065-3074. doi: 10.11999/JEIT211390
ZHOU Tianqing, ZENG Xinliang, HU Haiqin. Computation Offloading Cost Optimization Based on Hybrid Particle Swarm Optimization Algorithm[J]. Journal of Electronics & Information Technology, 2022, 44(9): 3065-3074. doi: 10.11999/JEIT211390
Citation: ZHOU Tianqing, ZENG Xinliang, HU Haiqin. Computation Offloading Cost Optimization Based on Hybrid Particle Swarm Optimization Algorithm[J]. Journal of Electronics & Information Technology, 2022, 44(9): 3065-3074. doi: 10.11999/JEIT211390

基于混合粒子群算法的计算卸载成本优化

doi: 10.11999/JEIT211390
基金项目: 国家自然科学基金(61861017, 61861018, 61961020, 62171119);国家重点研究开发计划(2020YFB1807201)
详细信息
    作者简介:

    周天清:男,副教授,研究方向为超密集组网、移动边缘计算

    曾新亮:男,硕士生,研究方向为超密集组网、移动边缘计算

    胡海琴:女,硕士生,研究方向为超密集组网、移动边缘计算

    通讯作者:

    周天清 zhoutian930@163.com

  • 中图分类号: TN929.5

Computation Offloading Cost Optimization Based on Hybrid Particle Swarm Optimization Algorithm

Funds: The National Natural Science Foundation of China (61861017, 61861018, 61961020, 62171119), The National Key Research and Development Program of China (2020YFB1807201)
  • 摘要: 为了满足用户日益增长的计算密集型和时延敏感型服务需求,同时最小化计算任务的处理成本,在时延约束下,该文针对超密集异构边缘计算网络,构建了有关任务卸载、无线资源管理、计算资源块分配的联合优化问题。考虑到所规划的问题具有非线性和混合整数的形式,且为满足约束条件及提升算法收敛速率,通过改进分层自适应搜索(HAS)算法设计了混合粒子群优化 (HPSO)算法来求解所提出的问题。仿真结果表明,HPSO算法明显优于现有算法,能有效降低任务处理成本。
  • 图  1  系统模型

    图  2  算法流程图

    图  3  单价变化对任务平均处理时延的影响

    图  5  适应度值的搜索情况

    图  4  单价变化对任务平均处理成本的影响

    表  1  基于DE的自适应遗传算法(算法1)

     步骤1 设置迭代次数${t_1} = 0$,初始化种群中的I个体;根据
         式(16)计算所有个体的适应度值,并找到当前最佳个
         体,以当前最佳个体更新历史最佳个体。
     步骤2 以锦标赛算法建立新种群,若历史最佳个体未被选入新
         种群,则用它取代新种群中最差的个体。
     步骤3 所有个体根据概率式(21)执行多样性增强的变异,并对
         计算资源块进行溢出检测及处理。
     步骤4 根据式(16)计算所有个体的适应度值。
     步骤5 任意两个相邻个体以概率(17)执行交叉操作,并对计算
         资源块进行溢出检测及处理。
     步骤6 所有个体根据规则式(19)以概率式(18)执行变异操作,
         并对计算资源块进行溢出检测及处理。
     步骤7 根据式(16)计算所有个体的适应度值,并更新当代最佳
         个体和历史最佳个体。
     步骤8 ${t_1} = {t_1} + 1$;如果${t_1} < {T_1}$,则回到步骤2,否则输出当
         前种群并终止循环,$ {T_1} $为迭代终止次数。
    下载: 导出CSV

    表  2  自适应粒子群算法(算法2)

     步骤1 设置迭代次数${t_2} = 0$与${\rho ^{{t_2}}} = 1$;以算法1的输出初始化
         ${\text{sl}}_{ik}^{{t_2}}$, ${\text{ql}}_{ik}^{{t_2}}$, ${\text{spbest}}_{ik}^{{t_2}}$与${\text{qpbest}}_{ik}^{{t_2}}$;以区间[0,1]的随机数初
         始化${\text{sv}}_{ik}^{{t_2}}$与${\text{qv}}_{ik}^{{t_2}}$;找到初始种群中的全局最佳粒子。
     步骤2 根据式(23)更新惯性权重。
     步骤3 根据式(22)、式(24)更新粒子的速度和位置,并对计算
         资源块进行溢出检测及处理。
     步骤4 根据式(16)计算所有粒子的适应度值;对于任意一粒子,
         如果它的当前适应度值高于自身的历史最高值,则更新
         自身的历史最佳粒子,然后在所有历史最佳粒子中找到
         全局最佳粒子。
     步骤5 根据式(25)、式(26)更新全局最佳粒子的速度和位置,
         并对计算资源块进行溢出检测及处理。
     步骤6 根据式(27)更新缩放因子$\rho $。
     步骤7 ${t_2} = {t_2} + 1$;如果${t_2} < {T_2}$,回到步骤2,否则输出所有
         的卸载决策${\text{sgbes}}{{\text{t}}_k}$与资源块分配决策${\text{qgbes}}{{\text{t}}_k}$,其中
         ${T_2}$为粒子群算法的最大迭代次数。
    下载: 导出CSV

    表  3  计算资源块按需分配策略(算法3)

     输入:种群规模I,MT的数量K,${T_k} = ({d_k},{l_k}, $$ T_k^{{\text{max}}})$,初始卸
        载决策$s_{ik}^0$,计算资源块总数U,上行速率${r_{nk}}$。
     输出:初始计算资源块分配决策$q_{ik}^0$。
     步骤1 如果$s_{ik}^0 = 0$,令$q_{ik}^0 = 0$;如果$s_{ik}^0 \ne 0$,即对于MTk
         计算其任务在基站的剩余可执行时间${\text{RE}}{{\text{S}}_k}$。
     步骤2 如果${\text{RE}}{{\text{S}}_k} \le 0$,说明任务需要卸载,但由于初始过程中
         随机生成的卸载决策无法保证关联的基站是理想的,那
         么令此时MTk分配到的计算资源块个数$q_{ik}^0 = 1$;如果
         ${\text{RE}}{{\text{S}}_k} > 0$,结合式(8),此时MTk分配到的计算资源块
         个数$q_{ik}^0 = {\text{round}} \left( {{d_k}{l_k}/({\text{RE}}{{\text{S}}_k}{f^{{\text{unit}}}}) + 0.5} \right)$。
     步骤3 对MTk分配到的计算资源块进行溢出检测及处理。
    下载: 导出CSV

    表  4  实验参数

    参数数值参数数值
    系统带宽W20 MHz资源块的计算能力${f^{{\text{unit}}}}$1 GHz
    设备最大发射功率${p^{{\text{max}}}}$23 dBm资源块的个数U100
    任务的数据大小${d_k}$2~5 Mbit种群大小I16
    单位任务计算量${l_k}$1000 cycles/bit能耗单价${\omega _1}$1.519×10–4 元/kJ
    任务的截止时延$T_k^{{\text{max}}}$1~10 s无线资源单价${\omega _2}$1/2/3/4/5 元/(MHz·s)
    能量系数$\alpha $10–24计算资源块单价${\omega _3}$0.1/0.2/0.3/0.4/0.5 元/个
    设备的计算能力${f^{{\text{loc}}}}$0.7 GHz
    下载: 导出CSV
  • [1] SENG Shuming, LUO Changqing, LI Xi, et al. User matching on blockchain for computation offloading in ultra-dense wireless networks[J]. IEEE Transactions on Network Science and Engineering, 2021, 8(2): 1167–1177. doi: 10.1109/TNSE.2020.3001081
    [2] LIN Yan, ZHANG Yijin, LI Jun, et al. Popularity-aware online task offloading for heterogeneous vehicular edge computing using contextual clustering of bandits[J]. IEEE Internet of Things Journal, 2022, 9(7): 5422–5433. doi: 10.1109/JIOT.2021.3109003
    [3] GUO Hongzhi, ZHANG Jie, LIU Jiajia, et al. Energy-aware computation offloading and transmit power allocation in ultradense IoT networks[J]. IEEE Internet of Things Journal, 2019, 6(3): 4317–4329. doi: 10.1109/JIOT.2018.2875535
    [4] GUO Fengxian, ZHANG Heli, JI Hong, et al. An efficient computation offloading management scheme in the densely deployed small cell networks with mobile edge computing[J]. IEEE/ACM Transactions on Networking, 2018, 26(6): 2651–2664. doi: 10.1109/TNET.2018.2873002
    [5] LIN Yan, ZHANG Rong, YANG Luxi, et al. User-centric clustering for designing ultradense networks: Architecture, objective functions, and design guidelines[J]. IEEE Vehicular Technology Magazine, 2019, 14(3): 107–114. doi: 10.1109/MVT.2019.2903741
    [6] WU Yuan, SHI Jiajun, NI Kejie, et al. Secrecy-based delay-aware computation offloading via mobile edge computing for Internet of Things[J]. IEEE Internet of Things Journal, 2019, 6(3): 4201–4213. doi: 10.1109/JIOT.2018.2875241
    [7] 张海波, 李虎, 陈善学, 等. 超密集网络中基于移动边缘计算的任务卸载和资源优化[J]. 电子与信息学报, 2019, 41(5): 1194–1201. doi: 10.11999/JEIT180592

    ZHANG Haibo, LI Hu, CHEN Shanxue, et al. Computing offloading and resource optimization in ultra-dense networks with mobile edge computation[J]. Journal of Electronics &Information Technology, 2019, 41(5): 1194–1201. doi: 10.11999/JEIT180592
    [8] PHAM Q V, LE L B, CHUNG S H, et al. Mobile edge computing with wireless backhaul: Joint task offloading and resource allocation[J]. IEEE Access, 2019, 7: 16444–16459. doi: 10.1109/ACCESS.2018.2883692
    [9] LI Huilin, XU Haitao, ZHOU Chengcheng, et al. Joint optimization strategy of computation offloading and resource allocation in multi-access edge computing environment[J]. IEEE Transactions on Vehicular Technology, 2020, 69(9): 10214–10226. doi: 10.1109/TVT.2020.3003898
    [10] CHEN Min and HAO Yixue. Task offloading for mobile edge computing in software defined ultra-dense network[J]. IEEE Journal on Selected Areas in Communications, 2018, 36(3): 587–597. doi: 10.1109/JSAC.2018.2815360
    [11] 杜剑波, 薛哪哪, 孙艳, 等. 基于NOMA的车辆边缘计算网络优化策略[J]. 物联网学报, 2021, 5(1): 19–26. doi: 10.11959/j.issn.2096-3750.2021.00207

    DU Jianbo, XUE Nana, SUN Yan, et al. Optimization strategies in NOMA-based vehicle edge computing network[J]. Chinese Journal on Internet of Things, 2021, 5(1): 19–26. doi: 10.11959/j.issn.2096-3750.2021.00207
    [12] YANG Chao, LIU Yi, CHEN Xin, et al. Efficient mobility-aware task offloading for vehicular edge computing networks[J]. IEEE Access, 2019, 7: 26652–26664. doi: 10.1109/ACCESS.2019.2900530
    [13] THAI M T, LIN Y D, LAI Yuancheng, et al. Workload and capacity optimization for cloud-edge computing systems with vertical and horizontal offloading[J]. IEEE Transactions on Network and Service Management, 2020, 17(1): 227–238. doi: 10.1109/TNSM.2019.2937342
    [14] ZHOU Tianqing, QIN Dong, NIE Xuefang, et al. Energy-efficient computation offloading and resource management in ultradense heterogeneous networks[J]. IEEE Transactions on Vehicular Technology, 2021, 70(12): 13101–13114. doi: 10.1109/TVT2021.3116955
    [15] 席裕庚, 柴天佑, 恽为民. 遗传算法综述[J]. 控制理论与应用, 1996, 33(6): 697–708.

    XI Yugeng, CHAI Tianyou, and YUN Weimin. Survey on genetic algorithm[J]. Control Theory and Applications, 1996, 33(6): 697–708.
    [16] KENNEDY J and EBERHART R. Particle swarm optimization[C]. ICNN'95-International Conference on Neural Networks, Perth, Australia, 1995: 1942–1948.
    [17] LI Meiyi, CAI Zixing, and SUN Guoyun. An adaptive genetic algorithm with diversity-guided mutation and its global convergence property[J]. Journal of Central South University of Technology, 2004, 11(3): 323–327. doi: 10.1007/s11771-004-0066-6
    [18] 袁晓玲, 陈宇. 自适应权重粒子群算法在阴影光伏发电最大功率点跟踪(MPPT)中的应用[J]. 中国电力, 2013, 46(10): 85–90. doi: 10.3969/j.issn.1004-9649.2013.10.016

    YUAN Xiaoling and CHEN Yu. Applications of adaptive particle swarm optimization algorithm to MPPT of shadow photovoltaic power generation[J]. Electric Power, 2013, 46(10): 85–90. doi: 10.3969/j.issn.1004-9649.2013.10.016
    [19] VAN DEN BERGH F. An analysis of particle swarm optimizers[D]. [Ph. D. dissertation], University of Pretoria, 2002.
    [20] VAN DEN BERGH F and ENGELBRECHT A P. A new locally convergent particle swarm optimiser[C]. The IEEE International Conference on Systems, Man and Cybernetics, Yasmine Hammamet, Tunisia, 2002: 96–101.
  • 加载中
图(5) / 表(4)
计量
  • 文章访问数:  175
  • HTML全文浏览量:  34
  • PDF下载量:  67
  • 被引次数: 0
出版历程
  • 收稿日期:  2021-12-01
  • 录用日期:  2022-05-24
  • 修回日期:  2022-05-08
  • 网络出版日期:  2022-05-27
  • 刊出日期:  2022-09-19

目录

    /

    返回文章
    返回