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

LONG Saiqin; WANG Cong; LONG Weifan; LIU Haolin; DENG Qingyong; LI Zhetao

doi:10.23919/cje.2022.00.223

Article Contents

Article Navigation > Chinese Journal of Electronics > 2022 > Accepted Manuscript

LONG Saiqin, WANG Cong, LONG Weifan, et al., “An Efficient Task Scheduling Algorithm in the Cloud and Edge Collaborative Environment,” Chinese Journal of Electronics, in press, doi: 10.23919/cje.2022.00.223, 2022.

Citation:

LONG Saiqin, WANG Cong, LONG Weifan, et al., “An Efficient Task Scheduling Algorithm in the Cloud and Edge Collaborative Environment,” Chinese Journal of Electronics, in press, doi: 10.23919/cje.2022.00.223, 2022.

Citation:

PDF( 4384 KB)

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

doi: 10.23919/cje.2022.00.223

LONG Saiqin^{1, 2
,},
WANG Cong^1
,,
LONG Weifan¹,
LIU Haolin¹,
DENG Qingyong^4
,,
LI Zhetao^{2, 3
,}

1.
School of Computer Science, Xiangtan University, Xiangtan, 411105, China
2.
College of Information Science and Technology, Jinan University, Guangzhou, Guangdong, 510632, China
3.
Hunan International Scientific and Technological Cooperation Base of Intelligent network, Xiangtan University, Xiangtan, Hunan 411105, China
4.
School of Computer Science and Engineering, Guangxi Normal University, Guilin, Guangxi 541000, China

More Information

Author Bio:
Saiqin LONG is with the College of Information Science and Technology, Jinan University, Guangzhou, 510632, China, and also with the Hunan International Scientific and Technological Cooperation Base of Intelligent network, Key Laboratory of Hunan Province for Internet of Things and Information Security, School of Computer Science, Xiangtan University, Xiangtan, 411105, 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 pursuing his M.E. degree in the School of Computer Science at 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 BEng degree and MEng degree in Computer Science and Technology from Xiangtan University, in 2018, 2021, respectively. He is a PhD candidate with the Academy for Engineering Technology, Fudan University. His research interests include cloud computing, game theory, reinforcement learning. He is a member of Chinese Computer Federation (CCF) (Email:)

Haolin LIU received the B.Eng. degree in 2010 and the Ph.D. degree in 2015 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, Xiangtan, China. His research interests include mobile edge computing, wireless sensor networks, and the Internet of Things. (Email:)

Qingyong DENG is an associate professor at the School of Computer Science and Engineering & School of Software, Guangxi Normal University, China. He received his master’s degree in Signal and Information Processing from Xiangtan University, China in 2009 and Ph.D. degree in Beijing University of Posts and Telecommunications (BUPT), China in 2019. He has published more than 30 referred journal papers in his current research interests, including IoT, compressed sensing, wireless network and smart city. He is a member of IEEE and CCF. (Email: dengqingyong@xtu.edu.cn)

Zhetao LI is a professor in School of Computer Science, Xiangtan University. He received the B.Eng. degree in Electrical Information Engineering from Xiangtan University in 2002, the M.Eng. degree in Pattern Recognition and Intelligent System from Beihang University in 2005, and the Ph.D. degree in Computer Application Technology from Hunan University in 2010. From Dec 2013 to Dec 2014, he was a post-doc in wireless network at Stony Brook University. He is a member of IEEE and CCF. (Email: liztchina@hotmail.com)
Received Date: 2022-03-22
Accepted Date: 2022-03-22

Available Online: 2022-03-22

Abstract

Abstract

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. Subsequently, we transform the edge nodes inside the cluster into a bipartite graph, and then propose a task scheduling algorithm based on maximum matching (SAMM). Finally, 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 tasks which can be completed and that meet the latest deadline constraints by 32%-47.2% under high load conditions.
- Bipartite Matching,
- Node Clustering,
- Edge-Edge Collaboration,
- Cloud-Edge Collaboration,
- Task Scheduling

FullText(HTML)

References(35)

References

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