Task offloading is one of the main techniques of the fog computing, and it means that the computation-limited nodes offload the tasks to the capable nodes for help. Firstly, we propose TOD (online learning-based task offloading algorithm for the dynamic fog networks under stationary status) using the MAB (multi-armed bandit) theory, which aims at minimizing the long term offloading delay and improving the task offloading success ratio. Then, we propose TOD-N (online learning-based task offloading algorithm for the dynamic fog networks under non-stationary status) to efficiently track the changes of the sharing computing resources and the channel environment. Moreover, we analyze the performances of the two algorithms on the optimality, the computational complexity, and the memory usage. Simulation results show that the long term average offloading delays achieved by the two algorithms are almost as good as the one achieved by the Oracle algorithm, and the offloading success ratios are also efficiently promoted. Moreover, TOD-N tracks the optimal resources efficiently under non-stationary network status.
TAN Youyu
,
CHEN Lei
,
ZHOU Mingtuo
,
WANG Kunlun
,
YANG Yang
,
ZHANG Wuxiong
. Online learning-based task offloading algorithms for dynamic fog networks[J]. Journal of University of Chinese Academy of Sciences, 2020
, 37(5)
: 688
-698
.
DOI: 10.7523/j.issn.2095-6134.2020.05.014
[1] Chen S, Zhao J. The requirements, challenges, and technologies for 5G of terrestrial mobile telecommunication[J]. IEEE Communications Magazine, 2014, 52(5):36-43.
[2] Bonomi F, Milito R, Zhu J, et al. Fog computing and its role in the internet of things[C]//Proceedings of the first edition of the MCC workshop on Mobile cloud computing. ACM, 2012:13-16.
[3] Mouradian C, Naboulsi D, Yangui S, et al. A comprehensive survey on fog computing:state-of-the-art and research challenges[J]. IEEE Communications Surveys & Tutorials, 2017, 20(1):416-464.
[4] Yang Y. Multi-tier computing networks for intel-ligent IoT[J].Nature Electronics, 2019, 2(1):4.
[5] Chen N, Yang Y, Zhang T, et al. Fog as a service technology[J]. IEEE Communications Magazine, 2018, 56(11):95-101.
[6] Chen X, Jiao L, Li W, et al. Efficient multi-user computation offloading for mobile-edge cloud computing[J]. IEEE/ACM Transactions on Networking, 2016(5):2795-2808.
[7] Dinh T Q, Tang J, 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.
[8] Liu Z, Yang X, Yang Y, et al. DATS:dispersive stable task scheduling in heterogeneous fog networks[J]. IEEE Internet of Things Journal, 2018,6(2):3423-3436.
[9] Mao Y, Zhang J, Song S H, et al. Stochastic joint radio and computational resource management for multi-user mobile-edge computing systems[J]. IEEE Transactions on Wireless Communications, 2017, 16(9):5994-6009.
[10] Ouyang T, Zhou Z, Chen X. Follow me at the edge:mobility-aware dynamic service placement for mobile edge computing[J]. IEEE Journal on Selected Areas in Communications, 2018, 36(10):2333-2345.
[11] Tan Y, Wang K, Yang Y, et al. Delay-optimal task offloading for dynamic fog networks[C]//2019 IEEE International Conference on Communications (ICC). IEEE, 2019.doi:10.1109/ICC.2019.8761113.
[12] Gittins J, Glazebrook K, Weber R. Multi-armed bandit allocation indices[M]. Hoboken, US:John Wiley & Sons, 2011.
[13] Auer P, Cesa-Bianchi N, Fischer P. Finite-time analysis of the multiarmed bandit problem[J]. Machine learning, 2002, 47(2/3):235-256.
[14] Bubeck S, Cesa-Bianchi N. Regret analysis of stochastic and nonstochastic multi-armed bandit problems[J]. Foundations and Trends® in Machine Learning, 2012, 5(1):1-122.
[15] Garivier A, Moulines E. On upper-confidence bound policies for switching bandit problems[C]//International Conference on Algorithmic Learning Theory. Berlin, Heidelberg:Springer, 2011:174-188.
[16] 田雷霞, 杨文国, 高随祥, 等. 不确定传输速率下无线资源调度问题的鲁棒优化模型[J]. 中国科学院大学学报, 2018, 35(1):18-25.
[17] 张剑, 邱玲, 陈正. 超密集网络中基于多连接的用户归属和功率控制联合优化[J]. 中国科学院大学学报, 2018, 35(1):126-130.
