一种移动边缘计算中最小总滞后时间的调度算法A Scheduling Algorithm for Minimum Total Delay Time in Mobile Edge Computing

DOI: 10.12677/SEA.2019.86036, PDF, HTML, XML, 下载: 294  浏览: 632

Abstract: As an emerging architecture, mobile edge computing extends cloud computing services to the edge of the network close to users through mobile edge computing servers, meeting the needs of appli-cations that require real-time control and real-time data analysis. However, due to the limited computing power of the mobile edge computing server, the delay time of the task is long. In order to improve the status quo, this paper proposes a scheduling algorithm with minimum total delay time. The server determines the optimal order of task calculation to minimize the total lag time. In addition, this paper also proposes an incentive mechanism that allows users to submit tasks with reasonable computational effort and expected completion time, while reducing the number and amount of submitted tasks when the server computing resources are insufficient. The results show that the proposed algorithm’s performance is close to the traditional scheduling algorithms, and increases 17% to 200% in total delay time and average delay time.

1. 引言

2. 问题描述

Figure 1. Framework of mobile edge computing

$\begin{array}{cc}\mathrm{min}& \underset{i=0}{\overset{n}{\sum }}{l}_{i}\\ \text{s}\text{.t}\text{.}& {f}_{i}\le \underset{i=0}{\overset{n}{\sum }}{p}_{i},\forall i\\ & {s}_{i}+{p}_{i}={f}_{i},\forall i\end{array}$ (1)

3. 调度算法

1) 某种顺序的任务排列： $\left\{{t}_{0},{t}_{1},\cdots ,{t}_{k-1},{t}_{k+1},\cdots ,{t}_{k+\delta }\right\}$

2) 任务 ${t}_{k}$

3) 某种顺序的任务排列： $\left\{{t}_{k+\delta +1},{t}_{k+\delta +2},\cdots ,{t}_{n}\right\}$

${f}_{k}\left(\delta \right)=\underset{j\le k|\delta }{\sum }{p}_{j}$ (2)

$V\left(\varnothing ,\gamma \right)=0$ (3)

$V\left(\left\{j\right\},\gamma \right)=\mathrm{max}\left(0,\gamma +{p}_{j}-{d}_{j}\right)$ (4)

$\begin{array}{c}V\left(T\left(j,n,k\right),t\right)=\mathrm{min}\left(V\left(j,{k}^{\prime }+\delta ,{k}^{\prime }\right),\gamma \right)+\mathrm{max}\left(0,{f}_{{k}^{\prime }}\left(\delta \right)-{d}_{{k}^{\prime }}\right)\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}+V\left(T\left({k}^{\prime }+\delta +1,n,{k}^{\prime }\right),{f}_{{k}^{\prime }}\left(\delta \right)\right)\end{array}$ (5)

${p}_{{k}^{\prime }}=\mathrm{max}\left({p}_{{j}^{\prime }}|{j}^{\prime }\in T\left(j,n,k\right)\right)$ (6)

$V\left(\left\{{t}_{0},{t}_{1},\cdots ,{t}_{n}\right\},0\right)$ (7)

4. 激励机制

${C}_{i}=\alpha {p}_{i}\cdot {\beta }^{{d}_{i}-{p}_{i}}\cdot {\text{e}}^{\gamma P}$ (8)

5. 实验与性能分析

5.1. 实验设置

5.2. 结果分析

Figure 2. Comparison of total delay time

Figure 3. Comparison of average delay time

Figure 4. Comparison of scheduling order calculation time

6. 结语

 [1] Pan, J. and Mcelhannon, J. (2017) Future Edge Cloud and Edge Computing for Internet of Things Applications. IEEE Internet of Things Journal, 5, 439-449. https://doi.org/10.1109/JIOT.2017.2767608 [2] Shirazi, S. (2017) The Extended Cloud: Review and Analysis of Mobile Edge Computing and Fog from a Security and Resilience Perspective. IEEE Journal on Selected Areas in Communications, 35, 2586-2595. https://doi.org/10.1109/JSAC.2017.2760478 [3] Filip, I., Postoaca, A., Stochitoiu, R., et al. (2019) Data Capsule: Representation of Heterogeneous Data in Cloud-Edge Computing. IEEE Access, 7, 49558-49567. https://doi.org/10.1109/ACCESS.2019.2910584 [4] Wang, S., Zhang, X., Zhang, Y., et al. (2017) A Survey on Mobile Edge Networks: Convergence of Computing, Caching and Communications. IEEE Access, 5, 6757-6779. https://doi.org/10.1109/ACCESS.2017.2685434 [5] Mach, P. and Becvar, Z. (2017) Mobile Edge Computing: A Survey on Architecture and Computation Offloading. IEEE Communications Surveys & Tutorials, 19, 1628-1656. https://doi.org/10.1109/COMST.2017.2682318 [6] Mao, Y., You, C., Zhang, J., et al. (2017) A Survey on Mo-bile Edge Computing: The Communication Perspective. IEEE Communications Surveys & Tutorials, 19, 2322-2358. https://doi.org/10.1109/COMST.2017.2745201 [7] Abbas, N., Zhang, Y., Taherkordi, A., et al. (2017) Mobile Edge Computing: A Survey. IEEE Internet of Things Journal, 5, 450-465. https://doi.org/10.1109/JIOT.2017.2750180 [8] Chen, S., Wen, H., Wu, J., et al. (2019) Internet of Things Based Smart Grids Supported by Intelligent Edge Computing. IEEE Access, 7, 74089-74102. https://doi.org/10.1109/ACCESS.2019.2920488 [9] Feng, J., Liu, Z., Wu, C., et al. (2017) AVE: Autonomous Vehicular Edge Computing Framework with ACO-Based Scheduling. IEEE Transactions on Vehicular Technology, 66, 10660-10675. https://doi.org/10.1109/TVT.2017.2714704 [10] Krishnan, P.R., Durga, P. and Srihari, R.E. (2018) IoT Based Smart Edge for Global Health: Remote Monitoring with Severity Detection and Alerts Transmission. IEEE Internet of Things Journal, 6, 2449-2462. https://doi.org/10.1109/JIOT.2018.2870068 [11] Qiu, X., Chen, W., Hong, Z., et al. (2019) Online Deep Reinforcement Learning for Computation Offloading in Blockchain-Empowered Mobile Edge Computing. IEEE Transactions on Vehicular Technology, 68, 8050-8062. https://doi.org/10.1109/TVT.2019.2924015 [12] Yu, S., Langar, R., Fu, X., et al. (2018) Computation Offloading with Data Caching Enhancement for Mobile Edge Computing. IEEE Transactions on Vehicular Technology, 67, 11098-11112. https://doi.org/10.1109/TVT.2018.2869144 [13] Hu, M., Zhuang, L., Wu, D., et al. (2019) Learn-ing Driven Computation Offloading for Asymmetrically Informed Edge Computing. IEEE Transactions on Parallel and Distributed Systems, 30, 1802-1815. https://doi.org/10.1109/TPDS.2019.2893925 [14] Zhang, T. (2017) Data Offloading in Mobile Edge Computing: A Coalition and Pricing Based Approach. IEEE Access, 6, 2760-2767. https://doi.org/10.1109/ACCESS.2017.2785265 [15] Chen, M. and Hao, Y. (2018) Task Offloading for Mobile Edge Computing in Software Defined Ultra-Dense Network. IEEE Journal on Selected Areas in Communications, 36, 587-597. https://doi.org/10.1109/JSAC.2018.2815360 [16] Li, S., Tao, Y., Qin, X., et al. (2019) Energy-Aware Mobile Edge Computation Offloading for IoT over Heterogenous Networks. IEEE Access, 7, 13092-13105. https://doi.org/10.1109/ACCESS.2019.2893118 [17] Pinedo, M. (2000) Scheduling: Theory, Algorithms, and Systems. 2th Edition, Prentice Hall Inc., Englewood Cliffs.