基于終端能耗和系統(tǒng)時延最小化的邊緣計算卸載及資源分配機制
doi: 10.11999/JEIT180970
-
北京郵電大學網絡與交換技術國家重點實驗室 北京 100876
A Computation Offloading and Resource Allocation Mechanism Based on Minimizing Devices Energy Consumption and System Delay
-
State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China
-
摘要: 通過移動邊緣計算下移云端的應用功能和處理能力支撐計算密集或時延敏感任務的執(zhí)行成為當前的發(fā)展趨勢。但面對眾多移動終端用戶時,如何有效利用計算資源有限的邊緣節(jié)點來保障終端用戶服務質量(QoS)成為關鍵問題。為此,該文融合邊緣云與遠端云構建了一種分層的邊緣云計算架構,以此架構為基礎,以最小化移動設備能耗和任務執(zhí)行時間為目標,將問題形式化描述為資源約束下的最小化能耗和時延加權和的凸優(yōu)化問題,并提出基于乘子法的計算卸載及資源分配機制解決該問題。實驗結果表明,在計算任務量很大的情況下,提出的計算卸載及資源分配機制能夠有效降低移動終端能耗,并在任務執(zhí)行時延方面較局部計算與計算卸載機制分別降低最高60%與10%,提高系統(tǒng)性能。
-
關鍵詞:
- 邊緣計算 /
- 計算卸載 /
- 資源分配 /
- 終端能耗 /
- 系統(tǒng)時延
Abstract: To support the execution of computation-intensive, delay-sensitive computing task by moving down the computing and processing capability in mobile edge computing becomes the current trend. However, when serving a large number of mobile users, how to use effectively the edge nodes with limited computing resources to ensure Quality of service (QoS) of end-user has become a key issue. To solve this problem, the edge cloud and remote cloud are combined to build a layered edge cloud computing architecture. Based on this architecture, with the goal of minimizing mobile device energy consumption and task execution time, the problem which is proved to be convex is formulated to minimize the weight sum of energy and delay. A computation offloading and resource allocation mechanism based on multiplier method is proposed. Simulations are conducted to evaluate the proposed mechanism. Compared with local computing and computation offloading mechanism, the proposed mechanism can effectively reduce the energy consumption of mobile device and the delay of system by up to 60% and 10%, respectively.-
Key words:
- Edge computing /
- Computing offloading /
- Resource allocation /
- Energy consumption /
- Delay of system
-
表 1 多用戶計算卸載
初始化:各移動終端數(shù)量$n$及計算能力${C_i}$,邊緣節(jié)點計算能力
${C_{{\rm{edge}}}}$,遠端云節(jié)點計算能力${C_{{\rm{cloud}}}}$,無線帶寬資源$B$,權值$V\,$, $S = \varnothing $;輸入:各用戶終端計算任務請求REQ($\left[ {{\lambda _1}, {\lambda _2}, ·\!·\!· , {\lambda _n}} \right]$); 輸出:最優(yōu)卸載決策$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; 引入拉格朗日函數(shù),求得滿足KKT條件的最優(yōu)解
$ < {x_i}, x_i^{{\rm{edge}}}, x_i^{{\rm{cloud}}} > $;最優(yōu)解向下取整,得整數(shù)解$ < 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 > $; 將整數(shù)可行解代入目標函數(shù),取使目標函數(shù)最小的整數(shù)解為最優(yōu) 整數(shù)解; end for; 回傳最優(yōu)解${X^*}$,移動終端接收卸載決策,執(zhí)行任務; 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]$) 輸出:最優(yōu)卸載決策$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; 引入拉格朗日函數(shù),求得滿足KKT條件的最優(yōu)解
$ < {x_i}, x_i^{{\rm{edge}}}, x_i^{{\rm{cloud}}} > $;end for; 得到平均資源分配條件下的初始最優(yōu)解${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; 更新罰函數(shù):若${\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}}} > $求最優(yōu)整數(shù)解,返回${S_k}^* = < {X_k}^*, {C_k}^* > $,
按${X_k}^*$進行計算卸載,按${C_k}^*$進行計算資源分配;end while. 下載: 導出CSV
-
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. 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 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. 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. 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 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 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 WU Huaming, KNOTTENBELT W, WOLTER K, et al. An Optimal Offloading Partitioning Algorithm in Mobile Cloud Computing[M]. Cham, Springer, 2016: 311–328. 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 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 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 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 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 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 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. -