为充分发掘分布在不同位置上的雾节点的计算资源，任务卸载被寄予众望。在雾计算场景下，以尽可能减少任务卸载的长期成本为目标，试图寻找一个高效的在线任务卸载方法。为此，这一问题被建模成一个随机规划问题，该问题中系统参数所对应的随机变量的期望会在未知时刻突变，系统参数相关信息只能在任务完成后的反馈中获得。基于非稳态多臂老虎机模型，提出一个高效的算法来解决这一具有挑战性的随机优化问题，给出理论分析证明该算法的渐进最优性。数值实验证明了该算法的优越性。
To fully exploit the computational resources in different fog nodes, task offloading is emerging. In this work, under the fog computing scenario, an efficient online task offloading strategy is investigated to minimize the long-term cost of task offloading. To achieve this goal, the problem is modeled as a stochastic optimization problem. Moreover, the system parameters are characterized by random variables, and their expectations may change abruptly at unknown time slot. Besides, the information about the system parameters is only available through the feedbacks after the task finishes. Using the non-stationary multi-armed bandit framework, we propose an efficient algorithm to handle this challenging stochastic programming. Furthermore, theoretical analyses are presented to prove the asymptotic optimality of the proposed algorithm. Numerical results reveal the advantages of this algorithm.
[1] 王雷,王平建,向继. 云存储环境中的统一认证技术[J]. 中国科学院大学学报,2015,32(5):682-688.
[2] Dinh T Q, Tang J, La Q D, et al. Offloading in mobile edge computing:task allocation and computational frequency scaling[J]. IEEE Transaction on Communication, 2017, 65(8):3571-3584.
[3] You C, Huang K, Chae H, et al. Energy-efficient resource allocation for mobile-edge computation offloading[J]. IEEE Transaction on Wireless Communication, 2017, 16(3):1397-1411.
[4] Kwak J, Kim Y, Lee J, et al. DREAM:Dynamic resource and task allocation for energy minimization in mobile cloud systems[J]. IEEE Journal on Selected Areas of Communication, 2015, 33(12):2510-2523.
[5] 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 Transaction on Wireless Communication, 2017, 16(9):5994-6009.
[6] Pu L, Chen X, Xu J, et al. D2D fogging:an energy-efficient and incentive-aware task offloading framework via network-assisted D2D collaboration[J]. IEEE Journal on Selected Areas of Communication, 2016, 34(12):3887-3901.
[7] Yang Y, Zhao S, Zhang W, et al. DEBTS:delay energy balanced task scheduling in homogeneous fog networks[J]. IEEE Internet Things Journal, 2018, 5(3):2094-2106.
[8] Chen X. Decentralized computation offloading game for mobile cloud computing[J]. IEEE Transaction on Parallel and Distributed Systems, 2015, 26(4):974-983.
[9] Chen T, Giannakis G B. Bandit convex optimization for scalable and dynamic IoT management[J]. IEEE Internet Things Journal, 2019, 6(1):1276-1286.
[10] Tekin C, Van Der Schaar M. An experts learning approach to mobile service offloading[C]//The IEEE Annual Allerton Conference on Communication, Control, and Computing. 2014:643-650.
[11] Auer P, Cesa-Bianchi N, Fischer P. Finite-time analysis of the multiarmed bandit problem[J]. Machine Learning, 2002, 47(2):235-256.
[12] 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.
[13] Berry D A, Fristedt B. Bandit problems:sequential allocation of experiments[M]. London, U.K.:Chapman & Hall, 1985.
[14] Garivier A, Moulines E. On upper-confidence bound policies for switching bandit problems[C]//The 2011 International Conference on Algorithmic Learning Theory, 2011:174-188.
[15] Joulani P, Gyorgy A, Szepesvari C. Online learning under delayed feedback[C]//The 30th International Conference on Machine Learning. 2013:1453-1461.
[16] Zhu Z, Liu T, Jin S, et al. Learn and pick right nodes to offload[EB/OL].(2018-04-24)[2019-02-10].https://arxiv.org/pdf/1804.08416.pdf.
