动态雾计算网络中基于在线学习的任务卸载算法

doi:10.7523/j.issn.2095-6134.2020.05.014

中国科学院大学学报 ›› 2020, Vol. 37 ›› Issue (5): 688-698.DOI: 10.7523/j.issn.2095-6134.2020.05.014

动态雾计算网络中基于在线学习的任务卸载算法

谭友钰^1,3,4,5, 陈蕾², 周明拓^1,5, 王昆仑^4,5, 杨旸^4,5, 张武雄¹

1. 中国科学院上海微系统与信息技术研究所, 上海 200050;
2. 国网浙江省电力有限公司, 杭州 310007;
3. 中国科学院大学, 北京 100049;
4. 上海科技大学, 上海 201210;
5. 上海雾计算实验室, 上海 201210

收稿日期:2019-01-30 修回日期:2019-03-28 发布日期:2020-09-15
通讯作者: 谭友钰
基金资助:
国家电网科技项目（52110418001U）和国家自然科学基金（61571004）资助

Online learning-based task offloading algorithms for dynamic fog networks

TAN Youyu^1,3,4,5, CHEN Lei², ZHOU Mingtuo^1,5, WANG Kunlun^4,5, YANG Yang^4,5, ZHANG Wuxiong¹

1. Shanghai Institute of Microsystem and Information Technology, Chinese Academy of Sciences, Shanghai 200050, China;
2. State Grid Zhejiang Power Co Ltd, Hangzhou 310007, China;
3. University of Chinese Academy of Sciences, Beijing 100049, China;
4. ShanghaiTech University, Shanghai 201210, China;
5. Shanghai Institute of Fog Computing Technology, Shanghai 201210, China

Received:2019-01-30 Revised:2019-03-28 Published:2020-09-15
Supported by:

摘要/Abstract

摘要： 任务卸载是雾计算的主要技术之一，即计算能力不足的节点将任务卸载给具有富余资源的节点帮助计算。以优化任务平均卸载时延和提升卸载服务成功率为目标，利用多臂老虎机理论为动态雾计算网络提出一种基于在线学习的任务卸载算法，可实时做出最优卸载决策。将该算法扩展到非稳定网络状态，使之可以动态追踪网络中节点的资源与环境变化，实时调整卸载决策。详细分析所提出算法的性能、复杂度和存储占用情况。仿真结果表明，这两种算法可达到的长期平均任务卸载时延均十分接近理想算法下的最优时延，卸载服务成功率也得到显著提升。此外，所提算法在非稳定的网络状态下能够追踪到计算资源与环境的变化。

关键词: 雾计算, 任务卸载, 在线学习, 多臂老虎机

Abstract: 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.

Key words: fog computing, task offloading, online learning, multi-armed bandit

中图分类号:

TN915

谭友钰, 陈蕾, 周明拓, 王昆仑, 杨旸, 张武雄. 动态雾计算网络中基于在线学习的任务卸载算法[J]. 中国科学院大学学报, 2020, 37(5): 688-698.

TAN Youyu, CHEN Lei, ZHOU Mingtuo, WANG Kunlun, YANG Yang, ZHANG Wuxiong. Online learning-based task offloading algorithms for dynamic fog networks[J]. , 2020, 37(5): 688-698.

参考文献

[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.

动态雾计算网络中基于在线学习的任务卸载算法

Online learning-based task offloading algorithms for dynamic fog networks

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

本文评价

访问统计

联系我们

[1]	戴志明, 周明拓, 杨旸, 李剑, 刘军. 智能工厂中的雾计算资源调度[J]. 中国科学院大学学报, 2021, 38(5): 702-711.
[2]	沈国锋, 周明拓, 李剑, 王华俊, 李凯, 杨旸. 雾计算使能的移动机器人编队跟随研究与设计[J]. 中国科学院大学学报, 2021, 38(4): 557-566.
[3]	朱兆伟, 刘婷, 钱骅, 罗喜良. 非稳态雾赋能网络中的在线任务卸载方法[J]. 中国科学院大学学报, 2020, 37(5): 699-707.