高级搜索

基于终端能耗和系统时延最小化的边缘计算卸载及资源分配机制

代美玲 刘周斌 郭少勇 邵苏杰 邱雪松

引用本文: 代美玲, 刘周斌, 郭少勇, 邵苏杰, 邱雪松. 基于终端能耗和系统时延最小化的边缘计算卸载及资源分配机制[J]. 电子与信息学报, 2019, 41(11): 2684-2690. doi: 10.11999/JEIT180970 shu
Citation:  Meiling DAI, Zhoubin LIU, Shaoyong GUO, Sujie SHAO, Xuesong QIU. A Computation Offloading and Resource Allocation Mechanism Based on Minimizing Devices Energy Consumption and System Delay[J]. Journal of Electronics and Information Technology, 2019, 41(11): 2684-2690. doi: 10.11999/JEIT180970 shu

基于终端能耗和系统时延最小化的边缘计算卸载及资源分配机制

    作者简介: 代美玲: 女,1995年生,博士生,研究方向为移动边缘计算、区块链;
    刘周斌: 男,1972年生,高级工程师,研究方向为信息安全、能源互联网和分布式系统;
    郭少勇: 男,1985年生,讲师,研究方向为电力物联网与区块链;
    邵苏杰: 男,1985年生,讲师,研究方向为网络管理与智能电网,边缘计算;
    邱雪松: 男,1973年生,教授,博士生导师,研究方向为网络与业务管理
    通讯作者: 邱雪松,xsqiu@bupt.edu.cn
  • 基金项目: 国家电网公司科技项目(52110118001H)

摘要: 通过移动边缘计算下移云端的应用功能和处理能力支撑计算密集或时延敏感任务的执行成为当前的发展趋势。但面对众多移动终端用户时,如何有效利用计算资源有限的边缘节点来保障终端用户服务质量(QoS)成为关键问题。为此,该文融合边缘云与远端云构建了一种分层的边缘云计算架构,以此架构为基础,以最小化移动设备能耗和任务执行时间为目标,将问题形式化描述为资源约束下的最小化能耗和时延加权和的凸优化问题,并提出基于乘子法的计算卸载及资源分配机制解决该问题。实验结果表明,在计算任务量很大的情况下,提出的计算卸载及资源分配机制能够有效降低移动终端能耗,并在任务执行时延方面较局部计算与计算卸载机制分别降低最高60%与10%,提高系统性能。

English

    1. [1]

      CHEN T Y H, RAVINDRANATH L, DENG Shuo, et al. Glimpse: Continuous, real-time object recognition on mobile devices[C]. Proceedings of the 13th ACM Conference on Embedded Networked Sensor Systems, Seoul, South Korea, 2015: 155–168.

    2. [2]

      LEE H S and LEE J W. Task offloading in heterogeneous mobile cloud computing: Modeling, analysis, and cloudlet deployment[J]. IEEE Access, 2018, 6: 14908–14925. doi: 10.1109/ACCESS.2018.2812144

    3. [3]

      VAN DEN BOSSCHE R, VANMECHELEN K, and BROECKHOVE J. Cost-optimal scheduling in hybrid IaaS clouds for deadline constrained workloads[C]. Proceedings of the IEEE 3rd International Conference on Cloud Computing, Miami, USA, 2010: 228–235.

    4. [4]

      TONG Liang, LI Yong, and GAO Wei. A hierarchical edge cloud architecture for mobile computing[C]. Proceedings of the IEEE INFOCOM 2016- the 35th Annual IEEE International Conference on Computer Communications, San Francisco, USA, 2016: 1–9.

    5. [5]

      DU Jianbo, ZHAO Liqiang, FENG Jie, et al. Computation offloading and resource allocation in mixed fog/cloud computing systems with Min-Max fairness guarantee[J]. IEEE Transactions on Communications, 2018, 66(4): 1594–1608. doi: 10.1109/TCOMM.2017.2787700

    6. [6]

      AHMAD A, PAUL A, KHAN M, et al. Energy efficient hierarchical resource management for mobile cloud computing[J]. IEEE Transactions on Sustainable Computing, 2017, 2(2): 100–112. doi: 10.1109/TSUSC.2017.2714344

    7. [7]

      KAO Y H, KRISHNAMACHARI B, RA M R, et al. Hermes: Latency optimal task assignment for resource-constrained mobile computing[J]. IEEE Transactions on Mobile Computing, 2017, 16(11): 3056–3069. doi: 10.1109/TMC.2017.2679712

    8. [8]

      WU Huaming, KNOTTENBELT W, WOLTER K, et al. An Optimal Offloading Partitioning Algorithm in Mobile Cloud Computing[M]. Cham, Springer, 2016: 311–328.

    9. [9]

      DINH T Q, TANG Jianhua, LA Q D, et al. Offloading in mobile edge computing: task allocation and computational frequency scaling[J]. IEEE Transactions on Communications, 2017, 65(8): 3571–3584. doi: 10.1109/TCOMM.2017.2699660

    10. [10]

      MENG Xianling, WANG Wei, and ZHANG Zhaoyang. Delay-constrained hybrid computation offloading with cloud and fog computing[J]. IEEE Access, 2017, 5: 21355–21367. doi: 10.1109/ACCESS.2017.2748140

    11. [11]

      WANG Yanting, SHENG Min, WANG Xijun, et al. Mobile-edge computing: partial computation offloading using dynamic voltage scaling[J]. IEEE Transactions on Communications, 2016, 64(10): 4268–4282. doi: 10.1109/TCOMM.2016.2599530

    12. [12]

      CHEN Xu, JIAO Lei, LI Wenzhong, et al. Efficient multi-user computation offloading for mobile-edge cloud computing[J]. IEEE/ACM Transactions on Networking, 2016, 24(5): 2795–2808. doi: 10.1109/TNET.2015.2487344

    13. [13]

      CHEN Xu. Decentralized computation offloading game for mobile cloud computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(4): 974–983. doi: 10.1109/TPDS.2014.2316834

    14. [14]

      CARDELLINI V, DE NITTO PERSONÉ V, DI VALERIO V, et al. A game-theoretic approach to computation offloading in mobile cloud computing[J]. Mathematical Programming, 2016, 157(2): 421–449. doi: 10.1007/s10107-015-0881-6

    15. [15]

      CHEN Menghsi, DONG Min, and LIANG Ben. Joint offloading decision and resource allocation for mobile cloud with computing access point[C]. Proceedings of 2016 IEEE International Conference on Acoustics, Speech and Signal Processing, Shanghai, China, 2016: 3516–3520.

    1. [1]

      唐伦, 肖娇, 魏延南, 赵国繁, 陈前斌. 基于云雾混合计算的车联网联合资源分配算法. 电子与信息学报, 2020, 42(0): 1-8.

    2. [2]

      夏士超, 姚枝秀, 鲜永菊, 李云. 移动边缘计算中分布式异构任务卸载算法. 电子与信息学报, 2020, 41(0): 1-8.

    3. [3]

      高东, 梁子林. 基于能量效率的双层非正交多址系统资源优化算法. 电子与信息学报, 2020, 42(5): 1237-1243.

    4. [4]

      刘通, 唐伦, 何小强, 陈前斌. 融合区块链与雾计算系统中基于网络时延和资源管理的优化任务卸载方案. 电子与信息学报, 2020, 42(0): 1-6.

    5. [5]

      唐伦, 魏延南, 谭颀, 唐睿, 陈前斌. H-CRAN网络下联合拥塞控制和资源分配的网络切片动态资源调度策略. 电子与信息学报, 2020, 42(5): 1244-1252.

    6. [6]

      陈前斌, 管令进, 李子煜, 王兆堃, 杨恒, 唐伦. 基于深度强化学习的异构云无线接入网自适应无线资源分配算法. 电子与信息学报, 2020, 42(6): 1468-1477.

    7. [7]

      陈前斌, 谭颀, 魏延南, 贺兰钦, 唐伦. 异构云无线接入网架构下面向混合能源供应的动态资源分配及能源管理算法. 电子与信息学报, 2020, 42(6): 1428-1435.

    8. [8]

      邵鸿翔, 孙有铭, 蔡佶昊. 面向用户体验的多小区混合非正交多址接入网络资源分配方法. 电子与信息学报, 2020, 42(0): 1-8.

    9. [9]

      张海波, 程妍, 刘开健, 贺晓帆. 车联网中整合移动边缘计算与内容分发网络的移动性管理策略. 电子与信息学报, 2020, 42(6): 1444-1451.

    10. [10]

      于存谦, 张黎, 何荣希, 李靖宇. 弹性光网络中时延感知的降级恢复路由与频谱分配算法. 电子与信息学报, 2020, 41(0): 1-9.

    11. [11]

      王君珂, 印珏, 牛人杰, 任少康, 晁洁. DNA计算与DNA纳米技术. 电子与信息学报, 2020, 42(6): 1313-1325.

    12. [12]

      殷志祥, 唐震, 张强, 崔建中, 杨静, 王日晟, 赵寿为, 张居丽. 基于DNA折纸基底的与非门计算模型. 电子与信息学报, 2020, 42(6): 1355-1364.

    13. [13]

      陈容, 陈岚, WAHLAArfan Haider. 基于公式递推法的可变计算位宽的循环冗余校验设计与实现. 电子与信息学报, 2020, 42(5): 1261-1267.

    14. [14]

      曾菊玲, 张春雷, 蒋砺思, 夏凌. 基于信道定价的无线虚拟网络资源分配策略:匹配/Stackelberg分层博弈. 电子与信息学报, 2020, 41(0): 0-7.

    15. [15]

      姜文, 牛杰, 吴一戎, 梁兴东. 机载多通道SAR运动目标方位向速度和法向速度联合估计算法. 电子与信息学报, 2020, 42(6): 1542-1548.

    16. [16]

      周丽丽, 闫晶晶, 穆中林, 王桥桥, 刘承琳, 何立风. 各向同性电离层低频一跳天波时延特性研究. 电子与信息学报, 2020, 42(7): 1606-1610.

    17. [17]

      刘焕淋, 杜理想, 陈勇, 胡会霞. 串扰感知的空分弹性光网络频谱转换器稀疏配置和资源分配方法. 电子与信息学报, 2020, 42(7): 1718-1725.

    18. [18]

      智慧, 王飞跃, 黄子菊. 大规模MIMO系统中联合用户分组和联盟博弈的动态导频分配方案. 电子与信息学报, 2020, 42(7): 1686-1693.

    19. [19]

      晋守博, 魏章志, 李耀红. 基于大通讯时滞的二阶多智能体系统的一致性分析. 电子与信息学报, 2020, 42(0): 1-6.

    20. [20]

      裴二荣, 易鑫, 邓炳光, 李金艳, 张蕾. D2D辅助的NB-IoT中能耗和传输成功率的最优折中. 电子与信息学报, 2020, 41(0): 1-8.

  • 图 1  分层边缘云计算架构

    图 2  不同策略下移动终端总能耗变化

    图 3  不同策略下系统时延期望变化

    图 4  不同场景下边缘节点资源分配情况

    图 5  权重对移动终端总能耗的影响

    图 6  权值对系统时延期望的影响

    图 7  z的变化对卸载决策的影响

    表 1  多用户计算卸载

     初始化:各移动终端数量$n$及计算能力${C_i}$,边缘节点计算能力
     ${C_{{\rm{edge}}}}$,远端云节点计算能力${C_{{\rm{cloud}}}}$,无线带宽资源$B$,权值$V\,$, $S = \varnothing $;
     输入:各用户终端计算任务请求REQ($\left[ {{\lambda _1}, {\lambda _2}, ·\!·\!· , {\lambda _n}} \right]$);
     输出:最优卸载决策$S = {X^*}$;
     $C_i^{{\ \rm{edge}}} = {{{C_{{\rm{edge}}}}} / n}$;
     while TRUE do;
     接收用户计算卸载请求REQ,提取请求中的对应任务信息: $B_i^{{\rm{in}}}, {V_i}, B_i^{{\rm{out}}}, P_i^{\rm{c}}, P_i^{{\rm{up}}}, {\lambda _i}$;
     for each $i \in \left\{ {1, 2, ·\!·\!· , n} \right\}$ do;
     引入拉格朗日函数,求得满足KKT条件的最优解
     $ < {x_i}, x_i^{{\rm{edge}}}, x_i^{{\rm{cloud}}} > $;
     最优解向下取整,得整数解$ < x' + {1_i}, x_i^{'{\rm{edge}}}, x_i^{'{\rm{cloud}}} > $, $ < {x'_i}, x_i^{'{\rm{edge}}} + 1, x_i^{'{\rm{cloud}}} > $, $ < {x'_i}, x_i^{'{\rm{edge}}}, x_i^{'{\rm{cloud}}} + 1 > $;
     将整数可行解代入目标函数,取使目标函数最小的整数解为最优 整数解;
     end for;
     回传最优解${X^*}$,移动终端接收卸载决策,执行任务;
     end while.
    下载: 导出CSV

    表 2  多用户计算卸载及资源分配机制

     初始化:$n$, ${C_i}$, ${C_{{\rm{edge}}}}$, ${C_{{\rm{cloud}}}}$, $B$,权值$V\,$, $S = \varnothing $
     输入:各用户终端计算任务请求REQ($\left[ {{\lambda _1}, {\lambda _2}, ·\!·\!· , {\lambda _n}} \right]$)
     输出:最优卸载决策$S = {X^*}$
     $C_i^{{\ \rm{edge}}} = {{{C_{{\rm{edge}}}}} / n}$, ${C_0} = < C_1^{{\ \rm{edge}}}, C_2^{{\ \rm{edge}}}, ·\!·\!· , C_n^{{\ \rm{edge}}} > $;
     while TRUE do;
     接收用户计算卸载请求REQ,提取任务信息:
     $B_i^{{\rm{in}}}, {V_i}, B_i^{{\rm{out}}}, P_i^{\rm{c}}, P_i^{{\rm{up}}}, {\lambda _i}$;
     for each $i \in \left\{ {1, 2, ·\!·\!· , n} \right\}$ do;
     引入拉格朗日函数,求得满足KKT条件的最优解
     $ < {x_i}, x_i^{{\rm{edge}}}, x_i^{{\rm{cloud}}} > $;
     end for;
     得到平均资源分配条件下的初始最优解${X^*}$, ${X_0} = {X^*}$;
     ${S_0} = < {X_0}, {C_0} > $;
     ${\mu ^{\left( 1 \right)}} = \left( {1, 1, ·\!·\!· , 1} \right)$, ${\eta ^{\left( 1 \right)}} = \left( {1, 1, ·\!·\!· , 1} \right)$, $\varepsilon = {10^{ - 5}}$, $M = 2$,
     $\theta = 0.8$, $\alpha = 2$;
     $k = k + 1$;
     ${S_1} = {\rm{BFGS}}\left( {\varphi \left( {S, \mu , \eta , M} \right)} \right)$;
     ${\beta _k} = {\left\{ {\sum\limits_{i = 1}^n {{h_i}^2\left( {{S_k}} \right)} + \sum\limits_{j = 1}^{4n + 1} {{{\left[ {\left( {\min {g_j}\left( {{S_k}} \right), \frac{{{{\left( {{\eta ^{\left( K \right)}}} \right)}_j}}}{M}} \right)} \right]}^2}} } \right\}^{{1 / 2}}}$;
     while ${\beta _k} > \varepsilon $ do;
     更新罚函数:若${\beta _k} > \theta \cdot {\beta _k}$,则$M = \alpha \cdot M$,否则$M$不变;
     更新乘子向量${\mu ^{\left( k \right)}}$, ${\eta ^{\left( k \right)}}$;
     $k = k + 1$;
     ${S_k} = {\rm{BFGS}}\left( {\varphi \left( {S, \mu , \eta , M} \right)} \right)$;
     依据上述公式计算${\beta _k}$值;
     end while;
     对$ < {x_i}, x_i^{{\rm{edge}}}, x_i^{{\rm{cloud}}} > $求最优整数解,返回${S_k}^* = < {X_k}^*, {C_k}^* > $,
     按${X_k}^*$进行计算卸载,按${C_k}^*$进行计算资源分配;
     end while.
    下载: 导出CSV
  • 加载中
图(7)表(2)
计量
  • PDF下载量:  90
  • 文章访问数:  2358
  • HTML全文浏览量:  1163
文章相关
  • 通讯作者:  邱雪松, xsqiu@bupt.edu.cn
  • 收稿日期:  2018-10-17
  • 录用日期:  2019-03-13
  • 网络出版日期:  2019-04-01
  • 刊出日期:  2019-11-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章