Computation Offloading Cost Optimization Based on Hybrid Particle Swarm Optimization Algorithm
-
摘要: 为了满足用户日益增长的计算密集型和时延敏感型服务需求，同时最小化计算任务的处理成本，在时延约束下，该文针对超密集异构边缘计算网络，构建了有关任务卸载、无线资源管理、计算资源块分配的联合优化问题。考虑到所规划的问题具有非线性和混合整数的形式，且为满足约束条件及提升算法收敛速率，通过改进分层自适应搜索(HAS)算法设计了混合粒子群优化 (HPSO)算法来求解所提出的问题。仿真结果表明，HPSO算法明显优于现有算法，能有效降低任务处理成本。Abstract: In order to meet the ever-increasing computation-intensive and delay-sensitive service requirements of users, as well as minimizing the processing cost of computation tasks, an optimization problem of joint task offloading, wireless resource management, and computation resource block allocation are formulated for ultra-dense heterogeneous edge computing networks under users’ delay constraints. Such a formulated problem is in a nonlinear and mixed-integer form. In order to meet the constraints and improve the convergence speed of algorithm, a Hybrid Particle Swarm Optimization (HPSO) algorithm is developed by improving Hierarchical Adaptive Search (HAS) algorithm. The simulation results show that HPSO algorithm is superior to other benchmark algorithms under users’ delay constraints, and can reduce the task processing cost effectively.
-
表 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 实验参数
参数 数值 参数 数值 系统带宽W 20 MHz 资源块的计算能力${f^{{\text{unit}}}}$ 1 GHz 设备最大发射功率${p^{{\text{max}}}}$ 23 dBm 资源块的个数U 100 任务的数据大小${d_k}$ 2～5 Mbit 种群大小I 16 单位任务计算量${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/JEIT180592ZHANG 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.00207DU 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.016YUAN 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)
计量
- 文章访问数: 386
- HTML全文浏览量: 109
- PDF下载量: 98
- 被引次数: 0
