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

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

doi:10.11999/JEIT180970

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

doi: 10.11999/JEIT180970 cstr: 32379.14.JEIT180970

北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室北京 100876

基金項(xiàng)目: 國(guó)家電網(wǎng)公司科技項(xiàng)目(52110118001H)

詳細(xì)信息

作者簡(jiǎn)介:
代美玲：女，1995年生，博士生，研究方向?yàn)橐苿?dòng)邊緣計(jì)算、區(qū)塊鏈

劉周斌：男，1972年生，高級(jí)工程師，研究方向?yàn)樾畔踩?、能源互?lián)網(wǎng)和分布式系統(tǒng)

郭少勇：男，1985年生，講師，研究方向?yàn)殡娏ξ锫?lián)網(wǎng)與區(qū)塊鏈

邵蘇杰：男，1985年生，講師，研究方向?yàn)榫W(wǎng)絡(luò)管理與智能電網(wǎng)，邊緣計(jì)算

邱雪松：男，1973年生，教授，博士生導(dǎo)師，研究方向?yàn)榫W(wǎng)絡(luò)與業(yè)務(wù)管理

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

中圖分類號(hào): TP301.6
計(jì)量
- 文章訪問數(shù): 4392
- HTML全文瀏覽量: 2208
- PDF下載量: 221
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2018-10-17
- 修回日期: 2019-03-13
- 網(wǎng)絡(luò)出版日期: 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)

摘要

摘要: 通過移動(dòng)邊緣計(jì)算下移云端的應(yīng)用功能和處理能力支撐計(jì)算密集或時(shí)延敏感任務(wù)的執(zhí)行成為當(dāng)前的發(fā)展趨勢(shì)。但面對(duì)眾多移動(dòng)終端用戶時(shí)，如何有效利用計(jì)算資源有限的邊緣節(jié)點(diǎn)來保障終端用戶服務(wù)質(zhì)量(QoS)成為關(guān)鍵問題。為此，該文融合邊緣云與遠(yuǎn)端云構(gòu)建了一種分層的邊緣云計(jì)算架構(gòu)，以此架構(gòu)為基礎(chǔ)，以最小化移動(dòng)設(shè)備能耗和任務(wù)執(zhí)行時(shí)間為目標(biāo)，將問題形式化描述為資源約束下的最小化能耗和時(shí)延加權(quán)和的凸優(yōu)化問題，并提出基于乘子法的計(jì)算卸載及資源分配機(jī)制解決該問題。實(shí)驗(yàn)結(jié)果表明，在計(jì)算任務(wù)量很大的情況下，提出的計(jì)算卸載及資源分配機(jī)制能夠有效降低移動(dòng)終端能耗，并在任務(wù)執(zhí)行時(shí)延方面較局部計(jì)算與計(jì)算卸載機(jī)制分別降低最高60%與10%，提高系統(tǒng)性能。
- 邊緣計(jì)算 /
- 計(jì)算卸載 /
- 資源分配 /
- 終端能耗 /
- 系統(tǒng)時(shí)延
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 分層邊緣云計(jì)算架構(gòu)

下載: 全尺寸圖片幻燈片

圖 2 不同策略下移動(dòng)終端總能耗變化

下載: 全尺寸圖片幻燈片

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

下載: 全尺寸圖片幻燈片

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

下載: 全尺寸圖片幻燈片

圖 5 權(quán)重對(duì)移動(dòng)終端總能耗的影響

下載: 全尺寸圖片幻燈片

圖 6 權(quán)值對(duì)系統(tǒng)時(shí)延期望的影響

下載: 全尺寸圖片幻燈片

圖 7 z的變化對(duì)卸載決策的影響

下載: 全尺寸圖片幻燈片

表 1 多用戶計(jì)算卸載

初始化：各移動(dòng)終端數(shù)量$n$及計(jì)算能力${C_i}$，邊緣節(jié)點(diǎn)計(jì)算能力　${C_{{\rm{edge}}}}$，遠(yuǎn)端云節(jié)點(diǎn)計(jì)算能力${C_{{\rm{cloud}}}}$，無線帶寬資源$B$，權(quán)值$V\,$，　$S = \varnothing $;
輸入：各用戶終端計(jì)算任務(wù)請(qǐng)求REQ($\left[ {{\lambda _1}, {\lambda _2}, ·\!·\!· , {\lambda _n}} \right]$);
輸出：最優(yōu)卸載決策$S = {X^*}$;
$C_i^{{\ \rm{edge}}} = {{{C_{{\rm{edge}}}}} / n}$;
while TRUE do;
接收用戶計(jì)算卸載請(qǐng)求REQ，提取請(qǐng)求中的對(duì)應(yīng)任務(wù)信息：　$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ù)可行解代入目標(biāo)函數(shù)，取使目標(biāo)函數(shù)最小的整數(shù)解為最優(yōu)　整數(shù)解；
end for;
回傳最優(yōu)解${X^*}$，移動(dòng)終端接收卸載決策，執(zhí)行任務(wù)；
end while.

下載: 導(dǎo)出CSV

表 2 多用戶計(jì)算卸載及資源分配機(jī)制

初始化：$n$, ${C_i}$, ${C_{{\rm{edge}}}}$, ${C_{{\rm{cloud}}}}$, $B$，權(quán)值$V\,$, $S = \varnothing $
輸入：各用戶終端計(jì)算任務(wù)請(qǐng)求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;
接收用戶計(jì)算卸載請(qǐng)求REQ，提取任務(wù)信息：　$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)$;
依據(jù)上述公式計(jì)算${\beta _k}$值；
end while;
對(duì)$ < {x_i}, x_i^{{\rm{edge}}}, x_i^{{\rm{cloud}}} > $求最優(yōu)整數(shù)解，返回${S_k}^* = < {X_k}^, {C_k}^ > $，　按${X_k}^$進(jìn)行計(jì)算卸載，按${C_k}^$進(jìn)行計(jì)算資源分配；
end while.

下載: 導(dǎo)出CSV

參考文獻(xiàn)(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.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問統(tǒng)計(jì)