基于終端能耗和系統(tǒng)時延最小化的邊緣計算卸載及資源分配機制

代美玲; 劉周斌; 郭少勇; 邵蘇杰; 邱雪松

doi:10.11999/JEIT180970

基于終端能耗和系統(tǒng)時延最小化的邊緣計算卸載及資源分配機制

doi: 10.11999/JEIT180970

北京郵電大學網絡與交換技術國家重點實驗室北京 100876

基金項目: 國家電網公司科技項目(52110118001H)

詳細信息

作者簡介:
代美玲：女，1995年生，博士生，研究方向為移動邊緣計算、區(qū)塊鏈

劉周斌：男，1972年生，高級工程師，研究方向為信息安全、能源互聯(lián)網和分布式系統(tǒng)

郭少勇：男，1985年生，講師，研究方向為電力物聯(lián)網與區(qū)塊鏈

邵蘇杰：男，1985年生，講師，研究方向為網絡管理與智能電網，邊緣計算

邱雪松：男，1973年生，教授，博士生導師，研究方向為網絡與業(yè)務管理

通訊作者:
邱雪松　xsqiu@bupt.edu.cn

中圖分類號: TP301.6
計量
- 文章訪問數(shù): 4334
- HTML全文瀏覽量: 2143
- PDF下載量: 221
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2018-10-17
- 修回日期: 2019-03-13
- 網絡出版日期: 2019-04-01
- 刊出日期: 2019-11-01

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

Funds: The State Grid Technology Project (52110118001H)

摘要

摘要: 通過移動邊緣計算下移云端的應用功能和處理能力支撐計算密集或時延敏感任務的執(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.
- Edge computing /
- Computing offloading /
- Resource allocation /
- Energy consumption /
- Delay of system

HTML全文

圖 1 分層邊緣云計算架構

下載: 全尺寸圖片幻燈片

圖 2 不同策略下移動終端總能耗變化

下載: 全尺寸圖片幻燈片

圖 3 不同策略下系統(tǒng)時延期望變化

下載: 全尺寸圖片幻燈片

圖 4 不同場景下邊緣節(jié)點資源分配情況

下載: 全尺寸圖片幻燈片

圖 5 權重對移動終端總能耗的影響

下載: 全尺寸圖片幻燈片

圖 6 權值對系統(tǒng)時延期望的影響

下載: 全尺寸圖片幻燈片

圖 7 z的變化對卸載決策的影響

下載: 全尺寸圖片幻燈片

表 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

參考文獻(15)

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.

施引文獻

資源附件(0)

訪問統(tǒng)計