高级搜索

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

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

引用本文: 代美玲, 刘周斌, 郭少勇, 邵苏杰, 邱雪松. 基于终端能耗和系统时延最小化的边缘计算卸载及资源分配机制[J]. 电子与信息学报, 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, 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, FL, 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, CA, 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]. AGHA G and VAN HOUDT B. Quantitative Evaluation of Systems. 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]

      张海波, 李虎, 陈善学, 贺晓帆. 超密集网络中基于移动边缘计算的任务卸载和资源优化. 电子与信息学报,

    2. [2]

      赵星, 彭建华, 游伟. 基于Lyapunov优化的隐私感知计算卸载方法. 电子与信息学报,

    3. [3]

      王汝言, 徐宁宁, 吴大鹏. 能耗和时延感知的虚拟化云无线接入网络资源分配机制. 电子与信息学报,

    4. [4]

      张骥先, 谢宁, 张学杰, 李伟东. 基于监督学习的可信云计算资源拍卖机制研究. 电子与信息学报,

    5. [5]

      王汝言, 梁颖杰, 崔亚平. 车辆网络多平台卸载智能资源分配算法. 电子与信息学报,

    6. [6]

      崔苗, 喻鑫, 李学易, 张广驰, 刘怡俊. 多用户多载波无线携能通信系统的上下行联合资源分配. 电子与信息学报,

    7. [7]

      王汝言, 李宏娟, 吴大鹏. 基于Stackelberg博弈的虚拟化无线传感网络资源分配策略. 电子与信息学报,

    8. [8]

      梁靓, 武彦飞, 冯钢. 基于在线拍卖的网络切片资源分配算法. 电子与信息学报,

    9. [9]

      张达敏, 张绘娟, 闫威, 陈忠云, 辛梓芸. 异构网络中基于能效优化的D2D资源分配机制. 电子与信息学报,

    10. [10]

      熊余, 杨娅娅, 张振振, 蒋婧. 软件定义时分波分复用无源光网络中基于带宽预测的资源分配策略. 电子与信息学报,

    11. [11]

      唐伦, 杨希希, 施颖洁, 陈前斌. 无线虚拟网络中基于自回归滑动平均预测的在线自适应虚拟资源分配算法. 电子与信息学报,

    12. [12]

      唐伦, 魏延南, 马润琳, 贺小雨, 陈前斌. 虚拟化云无线接入网络下基于在线学习的网络切片虚拟资源分配算法. 电子与信息学报,

    13. [13]

      王汝言, 李宏娟, 吴大鹏, 李红霞. 基于半马尔科夫决策过程的虚拟传感网络资源分配策略. 电子与信息学报,

    14. [14]

      唐伦, 马润琳, 杨恒, 陈前斌. 基于非正交多址接入的网络切片联合用户关联和功率分配算法. 电子与信息学报,

    15. [15]

      邹虹, 高毅爽, 闫俊杰. 带有卸载时延感知的边缘云增强FiWi网络节能机制. 电子与信息学报,

    16. [16]

      张海波, 荆昆仑, 刘开健, 贺晓帆. 车联网中一种基于软件定义网络与移动边缘计算的卸载策略. 电子与信息学报,

    17. [17]

      崔维嘉, 张鹏, 巴斌. 基于循环匹配追踪的稀疏重构时延估计算法. 电子与信息学报,

    18. [18]

      唐伦, 周钰, 杨友超, 赵国繁, 陈前斌. 5G网络切片场景中基于预测的虚拟网络功能动态部署算法. 电子与信息学报,

    19. [19]

      唐伦, 周钰, 谭颀, 魏延南, 陈前斌. 基于强化学习的5G网络切片虚拟网络功能迁移算法. 电子与信息学报,

    20. [20]

      路新华, MANCHÓNCarles Navarro, 王忠勇, 张传宗. 大规模MIMO系统上行链路时间-空间结构信道估计算法. 电子与信息学报,

  • 图 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 = \emptyset $
     输入:各用户终端计算任务请求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)$;
     依据步骤13中公式计算${\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下载量:  34
  • 文章访问数:  578
  • HTML全文浏览量:  351
文章相关
  • 通讯作者:  邱雪松, xsqiu@bupt.edu.cn
  • 收稿日期:  2018-10-17
  • 录用日期:  2019-03-13
  • 网络出版日期:  2019-04-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

/

返回文章