Volume 33 Issue 5
Sep.  2024
Turn off MathJax
Article Contents
Saiqin LONG, Cong WANG, Weifan LONG, et al., “An Efficient Task Scheduling Algorithm in the Cloud and Edge Collaborative Environment,” Chinese Journal of Electronics, vol. 33, no. 5, pp. 1296–1307, 2024 doi: 10.23919/cje.2022.00.223
Citation: Saiqin LONG, Cong WANG, Weifan LONG, et al., “An Efficient Task Scheduling Algorithm in the Cloud and Edge Collaborative Environment,” Chinese Journal of Electronics, vol. 33, no. 5, pp. 1296–1307, 2024 doi: 10.23919/cje.2022.00.223

An Efficient Task Scheduling Algorithm in the Cloud and Edge Collaborative Environment

doi: 10.23919/cje.2022.00.223
More Information
  • Author Bio:

    Saiqin LONG is with the College of Information Science and Technology, Jinan University, Guangzhou, China, and also with the Hunan International Scientific and Technological Cooperation Base of Intelligent Network, the Key Laboratory of Hunan Province for Internet of Things and Information Security, School of Computer Science, Xiangtan University, Xiangtan, China. (Email: xxgcxyxtu@sina.com)

    Cong WANG received the B.E. degree in computer science and technology from Zhengzhou University, Zhengzhou, China in 2021, and he is a M.E. candidate in the School of Computer Science, Xiangtan University. His research interests include cloud computing, container scheduling, and cloud-side collaboration. He is a Member of the China Computer Federation (CCF). (Email: congwcn@foxmail.com)

    Weifan LONG received the B.E. degree and M.E degree in computer science and technology from Xiangtan University, in 2018 and 2021, respectively. He is a Ph.D. candidate with the Academy for Engineering Technology, Fudan University, Shanghai, China. His research interests include cloud computing, game theory, reinforcement learning

    Haolin LIU received the B.E. and Ph.D. degree from Sichuan University, Chengdu, China. He is currently an Associate Professor with the Key Laboratory of Hunan Province for Internet of Things and Information Security and School of Computer Science, Xiangtan University. His research interests include mobile edge computing, wireless sensor networks, and Internet of things

    Qingyong DENG is an Associate Professor at the School of Computer Science and Engineering and the School of Software, Guangxi Normal University. He received the M.E. degree from Xiangtan University and Ph.D. degree from Beijing University of Posts and Telecommunications. His research interests include IoT, compressed sensing, wireless network, etc. (Email: dengqingyong@xtu.edu.cn)

    Zhetao LI is a Professor in the School of Computer Science, Xiangtan University. He received the B.E. degree from Xiangtan University, the M.E. degree from Beihang University, and the Ph.D. degree from Hunan University. From Dec 2013 to Dec 2014, he was a Post-doc in wireless network at Stony Brook University, NY, USA. (Email: liztchina@hotmail.com)

  • Corresponding author: Email: liztchina@hotmail.com
  • Received Date: 2022-07-21
  • Accepted Date: 2023-01-05
  • Available Online: 2022-03-22
  • Publish Date: 2024-09-05
  • With the advent of the 5G era and the accelerated development of edge computing and Internet of Things technologies, the number of tasks to be processed by mobile devices continues to increase. Edge nodes become incapable of facing massive tasks due to their own limited computing capabilities, and thus the cloud and edge collaborative environment is produced. In order to complete as many tasks as possible while meeting the deadline constraints, we consider the task scheduling problem in the cloud-edge and edge-edge collaboration scenarios. As the number of tasks on edge nodes increases, the solution space becomes larger. Considering that each edge node has its own communication range, we design an edge node based clustering algorithm (ENCA), which can reduce the feasible region while dividing the edge node set. We transform the edge nodes inside the cluster into a bipartite graph, and then propose a task scheduling algorithm based on maximum matching (SAMM). Our ENCA and SAMM are used to solve the task scheduling problem. Compared with the other benchmark algorithms, experimental results show that our algorithms increase the number of the tasks which can be completed and meet the latest deadline constraints by 32%–47.2% under high load conditions.
  • loading
  • [1]
    P. Lai, Q. He, J. Grundy, et al., “Cost-effective app user allocation in an edge computing environment,” IEEE Transactions on Cloud Computing, vol. 10, no. 3, pp. 1701–1713, 2022. doi: 10.1109/TCC.2020.3001570
    [2]
    I. M. Ibrahim, S. R. M. Zeebaree, M. A. M. Sadeeq, et al., “Task scheduling algorithms in cloud computing: A review,” Turkish Journal of Computer and Mathematics Education (TURCOMAT), vol. 12, no. 4, pp. 1041–1053, 2021. doi: 10.17762/turcomat.v12i4.612
    [3]
    F. Y. Hu, L. L. Lv, T. L. Zhang, et al., “Vehicular task scheduling strategy with resource matching computing in cloud-edge collaboration,” IET Collaborative Intelligent Manufacturing, vol. 3, no. 4, pp. 334–344, 2021. doi: 10.1049/cim2.12023
    [4]
    J. J. Guo, C. L. Li, Y. Chen, et al., “On-demand resource provision based on load estimation and service expenditure in edge cloud environment,” Journal of Network and Computer Applications, vol. 151, article no. 102506, 2020. doi: 10.1016/j.jnca.2019.102506
    [5]
    J. Schmitt, J. Bönig, T. Borggräfe, et al., “Predictive model-based quality inspection using machine learning and edge cloud computing,” Advanced Engineering Informatics, vol. 45, article no. 101101, 2020. doi: 10.1016/j.aei.2020.101101
    [6]
    P. F. Hu, S. Dhelim, H. S. Ning, et al., “Survey on fog computing: Architecture, key technologies, applications and open issues,” Journal of Network and Computer Applications, vol. 98, pp. 27–42, 2017. doi: 10.1016/j.jnca.2017.09.002
    [7]
    S. Z. Bi and Y. J. Zhang, “Computation rate maximization for wireless powered mobile-edge computing with binary computation offloading,” IEEE Transactions on Wireless Communications, vol. 17, no. 6, pp. 4177–4190, 2018. doi: 10.1109/TWC.2018.2821664
    [8]
    X. F. Cao, G. M. Tang, D. K. Guo, et al., “Edge federation: Towards an integrated service provisioning model,” IEEE/ACM Transactions on Networking, vol. 28, no. 3, pp. 1116–1129, 2020. doi: 10.1109/TNET.2020.2979361
    [9]
    Y. M. Miao, G. X. Wu, M. Li, et al., “Intelligent task prediction and computation offloading based on mobile-edge cloud computing,” Future Generation Computer Systems, vol. 102, pp. 925–931, 2020. doi: 10.1016/j.future.2019.09.035
    [10]
    H. Yuan, G. M. Tang, X. Y. Li, et al., “Online dispatching and fair scheduling of edge computing tasks: A learning-based approach,” IEEE Internet of Things Journal, vol. 8, no. 19, pp. 14985–14998, 2021. doi: 10.1109/JIOT.2021.3073034
    [11]
    J. H. Zhao, Q. P. Li, Y. Gong, et al., “Computation offloading and resource allocation for cloud assisted mobile edge computing in vehicular networks,” IEEE Transactions on Vehicular Technology, vol. 68, no. 8, pp. 7944–7956, 2019. doi: 10.1109/TVT.2019.2917890
    [12]
    X. L. Xu, X. Zhang, X. H. Liu, et al., “Adaptive computation offloading with edge for 5g-envisioned internet of connected vehicles,” IEEE Transactions on Intelligent Transportation Systems, vol. 22, no. 8, pp. 5213–5222, 2021. doi: 10.1109/TITS.2020.2982186
    [13]
    X. Zheng, M. C. Li, and J. Guo, “Task scheduling using edge computing system in smart city,” International Journal of Communication Systems, vol. 34, no. 6, article no. e4422, 2021. doi: 10.1002/dac.4422
    [14]
    J. Edinger, M. Breitbach, N. Gabrisch, et al., “Decentralized low-latency task scheduling for Ad-Hoc computing,” in Proceedings of the 2021 IEEE International Parallel and Distributed Processing Symposium (IPDPS), Portland, OR, USA, pp.776–785, 2021.
    [15]
    Y. X. Sun, S. Zhou, and J. Xu, “EMM: Energy-aware mobility management for mobile edge computing in ultra dense networks,” IEEE Journal on Selected Areas in Communications, vol. 35, no. 11, pp. 2637–2646, 2017. doi: 10.1109/JSAC.2017.2760160
    [16]
    T. Q. Dinh, Q. D. La, T. Q. S. Quek, et al., “Learning for computation offloading in mobile edge computing,” IEEE Transactions on Communications, vol. 66, no. 12, pp. 6353–6367, 2018. doi: 10.1109/TCOMM.2018.2866572
    [17]
    X. L. Xu, Y. C. Li, T. Huang, et al., “An energy-aware computation offloading method for smart edge computing in wireless metropolitan area networks,” Journal of Network and Computer Applications, vol. 133, pp. 75–85, 2019. doi: 10.1016/j.jnca.2019.02.008
    [18]
    H. L. Zhang, J. Guo, L. C. Yang, et al., “Computation offloading considering fronthaul and backhaul in small-cell networks integrated with MEC,” in Proceedings of the 2017 IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), Atlanta, GA, USA, pp.115–120, 2017.
    [19]
    L. C. Yang, H. L. Zhang, M. Li, et al., “Mobile edge computing empowered energy efficient task offloading in 5G,” IEEE Transactions on Vehicular Technology, vol. 67, no. 7, pp. 6398–6409, 2018. doi: 10.1109/TVT.2018.2799620
    [20]
    S. Q. Long, W. F. Long, Z. T. Li, et al., “A game-based approach for cost-aware task assignment with QoS constraint in collaborative edge and cloud environments,” IEEE Transactions on Parallel and Distributed Systems, vol. 32, no. 7, pp. 1629–1640, 2021. doi: 10.1109/TPDS.2020.3041029
    [21]
    H. S. Tan, Z. H. Han, X. Y. Li, et al., “Online job dispatching and scheduling in edge-clouds,” in Proceedings of the IEEE INFOCOM 2017-IEEE Conference on Computer Communications, Atlanta, GA, USA, pp.1–9, 2017.
    [22]
    X. Long, J. G. Wu, and L. Chen, “Energy-efficient offloading in mobile edge computing with edge-cloud collaboration,” in Proceedings of the 18th International Conference on Algorithms and Architectures for Parallel Processing, Guangzhou, China, pp.460–475, 2018.
    [23]
    M. Z. Du, Y. Wang, K. J. Ye, et al., “Algorithmics of cost-driven computation offloading in the edge-cloud environment,” IEEE Transactions on Computers, vol. 69, no. 10, pp. 1519–1532, 2020. doi: 10.1109/TC.2020.2976996
    [24]
    K. Y. Liu, J. Peng, H. Li, et al., “Multi-device task offloading with time-constraints for energy efficiency in mobile cloud computing,” Future Generation Computer Systems, vol. 64, pp. 1–14, 2016. doi: 10.1016/j.future.2016.04.013
    [25]
    H. C. Duan, C. Chen, G. Y. Min, et al., “Energy-aware scheduling of virtual machines in heterogeneous cloud computing systems,” Future Generation Computer Systems, vol. 74, pp. 142–150, 2017. doi: 10.1016/j.future.2016.02.016
    [26]
    K. K. Gai, M. K. Qiu, and H. Zhao, “Energy-aware task assignment for mobile cyber-enabled applications in heterogeneous cloud computing,” Journal of Parallel and Distributed Computing, vol. 111, pp. 126–135, 2018. doi: 10.1016/j.jpdc.2017.08.001
    [27]
    Z. H. Li, X. R. Yu, L. Yu, et al., “Energy-efficient and quality-aware VM consolidation method,” Future Generation Computer Systems, vol. 102, pp. 789–809, 2020. doi: 10.1016/j.future.2019.08.004
    [28]
    G. Peng, H. M. Wu, H. Wu, et al., “Constrained multiobjective optimization for IoT-enabled computation offloading in collaborative edge and cloud computing,” IEEE Internet of Things Journal, vol. 8, no. 17, pp. 13723–13736, 2021. doi: 10.1109/JIOT.2021.3067732
    [29]
    S. D. Wang, Y. Q. Li, S. C. Pang, et al., “A task scheduling strategy in edge-cloud collaborative scenario based on deadline,” Scientific Programming, vol. 2020, article no. 3967847, 2020. doi: 10.1155/2020/3967847
    [30]
    C. S. You, K. B. Huang, and H. Chae, “Energy efficient mobile cloud computing powered by wireless energy transfer,” IEEE Journal on Selected Areas in Communications, vol. 34, no. 5, pp. 1757–1771, 2016. doi: 10.1109/JSAC.2016.2545382
    [31]
    J. K. Ren, G. D. Yu, Y. H. He, et al., “Collaborative cloud and edge computing for latency minimization,” IEEE Transactions on Vehicular Technology, vol. 68, no. 5, pp. 5031–5044, 2019. doi: 10.1109/TVT.2019.2904244
    [32]
    G. Z. Zhang, T. Q. S. Quek, M. Kountouris, et al., “Fundamentals of heterogeneous backhaul design—analysis and optimization,” IEEE Transactions on Communications, vol. 64, no. 2, pp. 876–889, 2016. doi: 10.1109/TCOMM.2016.2515596
    [33]
    A. Al-Shuwaili, O. Simeone, A. Bagheri, et al., “Joint uplink/downlink optimization for backhaul-limited mobile cloud computing with user scheduling,” IEEE Transactions on Signal and Information Processing over Networks, vol. 3, no. 4, pp. 787–802, 2017. doi: 10.1109/TSIPN.2017.2668142
    [34]
    M. Dawande, J. Kalagnanam, P. Keskinocak, et al., “Approximation algorithms for the multiple knapsack problem with assignment restrictions,” Journal of Combinatorial Optimization, vol. 4, no. 2, pp. 171–186, 2000. doi: 10.1023/A:1009894503716
    [35]
    S. Martello and P. Toth, Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, Inc., New York, NY, USA, pp.157-179,1990.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(12)  / Tables(1)

    Article Metrics

    Article views (494) PDF downloads(41) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return