LBA-EC: Load Balancing Algorithm Based on Weighted Bipartite Graph for Edge Computing

SHAO Sisi; LIU Shangdong; LI Kui; YOU Shuai; QIU Huajie; YAO Xiaoliang; JI Yimu

doi:10.23919/cje.2021.00.289

Volume 32 Issue 2

Mar. 2023

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2023 > 32(2): 313-324

SHAO Sisi, LIU Shangdong, LI Kui, et al., “LBA-EC: Load Balancing Algorithm Based on Weighted Bipartite Graph for Edge Computing,” Chinese Journal of Electronics, vol. 32, no. 2, pp. 313-324, 2023, doi: 10.23919/cje.2021.00.289

Citation:

SHAO Sisi, LIU Shangdong, LI Kui, et al., “LBA-EC: Load Balancing Algorithm Based on Weighted Bipartite Graph for Edge Computing,” Chinese Journal of Electronics, vol. 32, no. 2, pp. 313-324, 2023, doi: 10.23919/cje.2021.00.289

Citation:

PDF( 3909 KB)

LBA-EC: Load Balancing Algorithm Based on Weighted Bipartite Graph for Edge Computing

doi: 10.23919/cje.2021.00.289

SHAO Sisi^{1, 2
,},
LIU Shangdong^{1, 2, 3, 4
,},
LI Kui^{1, 2
,},
YOU Shuai^{1, 2
,},
QIU Huajie^{1, 2
,},
YAO Xiaoliang^{1, 2
,},
JI Yimu^{1, 2, 3, 4
,}

1.
School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, China
2.
Institue of High Performance Computing and Bigdata, Nanjing University of Posts and Telecommunications, Nanjing 210003, China
3.
Nanjing Center of HPC China, Nanjing 210003, China
4.
Jiangsu HPC and Intelligent Processing Engineer Research Center, Nanjing 210003, China

Funds: This work was supported by the National Key R&D Program of China (2020YFB2104000, 2020YFB2104002), Natural Science Foundation of the Jiangsu Province (Higher Education Institutions) (BK20170900, 19KJB520046, 20KJA520001), Innovative and Entrepreneurial Talents Projects of Jiangsu Province, Jiangsu Planned Projects for Postdoctoral Research Funds (2019K024), Six Talent Peak Projects in Jiangsu Province (JY02), Postgraduate Research and Practice Innovation Program of Jiangsu Province (KYCX19 0921, KYCX19 0906), Open Research Project of Zhejiang Lab (2021KF0AB05), and NUPT DingShan Scholar Project and NUPTSF (NY219132)

More Information

Author Bio:
Sisi SHAO was born in 1997. She is a Ph.D. candidate at the School of Internet of Things, Nanjing University of Posts and Telecommunications. Her main research interests include cloud computing, edge computing task scheduling and security. (Email: 361571409@qq.com)

Shangdong LIU was born in 1979. He received Ph.D. degree in Southeast University. He is a Lecturer at the School of Computer, Nanjing University of Posts and Telecommunications. His main research interests include network behavior analysis, big data, and AI. (Email: lsd@njupt.edu.cn)

Kui LI was born in 1988. He is a Ph.D. candidate at the School of Internet of Things, Nanjing University of Posts and Telecommunications. His research interests include high performance computing, big data theory and technology. (Email: 825315689@qq.com)

Shuai YOU was born in 1995. He is a Ph.D. candidate at the School of Internet of Things, Nanjing University of Posts and Telecommunications. His research interests include machine learing, CV, and edge computing. (Email:1065858439@qq.com)

Huajie QIU was born in 1997. He is an M.S. candidate at the School of Computer, Nanjing University of Posts and Telecommunications. His research interests include cloud computing, cloud task scheduling, and reinforcement learning. (Email: 1029930034@qq.com)

Xiaoliang YAO was born in 1999. He is an M.S. candidate at the School of Computer, Nanjing University of Posts and Telecommunications. His main research interests include AI. (Email: 1392803263@qq.com)

Yimu JI (corresponding author) was born in 1978. He is a Professor at the School of Computer, Nanjing University of Posts and Telecommunications. His main research interests include the security and applications in cloud computing, bigdata, IoT, and AI. (Email: jiym@njupt.edu.cn)
Received Date: 2021-02-03
Accepted Date: 2021-12-04

Available Online: 2021-12-18

Publish Date: 2023-03-05

Abstract

Abstract

Compared with cloud computing environment, edge computing has many choices of service providers due to different deployment environments. The flexibility of edge computing makes the environment more complex. The current edge computing architecture has the problems of scattered computing resources and limited resources of single computing node. When the edge node carries too many task requests, the makespan of the task will be delayed. We propose a load balancing algorithm based on weighted bipartite graph for edge computing (LBA-EC), which makes full use of network edge resources, reduces user delay, and improves user service experience. The algorithm is divided into two phases for task scheduling. In the first phase, the tasks are matched to different edge servers. In the second phase, the tasks are optimally allocated to different containers in the edge server to execute according to the two indicators of energy consumption and completion time. The simulations and experimental results show that our algorithm can effectively map all tasks to available resources with a shorter completion time.
- Edge computing,
- Weighted bipartite graph,
- Load balancing

FullText(HTML)

References(25)

References

[1]	H. Wang, J. Gong, Y. Zhuang, et al. “Task scheduling for edge computing with health emergency and human behavior consideration in smart homes,” in Proceedings of 2017 IEEE International Conference on Big Data, Boston, MA, USA, pp.1213–1222, 2017.
[2]	W. Shi and S. Dustdar, “The promise of edge computing,” Computer, vol.49, no.5, pp.78–81, 2016. doi: 10.1109/MC.2016.145
[3]	C. M. Fernández, M. D. Rodríguez, and B. R. Muo, “An edge computing architecture in the Internet of things,” in Proceedings of 2018 IEEE 21st International Symposium on Real-Time Distributed Computing, Singapore, pp.99–102, 2018.
[4]	G. Li, Y. Yao, J. Wu, et al., “A new load balancing strategy by task allocation in edge computing based on intermediary nodes,” EURASIP Journal on Wireless Communications and Networking, vol.2020, no.1, pp.1–10, 2020. doi: 10.1186/s13638-019-1618-7
[5]	W. Liu, Y. C. Huang, W. Du, et al., “Resource-constrained serial task offload strategy in mobile edge computing,” Journal of Software, vol.31, no.6, pp.1889–1908, 2020.
[6]	H. Lu, C. Gu, F. Luo, et al., “Optimization of lightweight task offloading strategy for mobile edge computing based on deep reinforcement learning,” Future Generation Computer Systems, vol.102, pp.847–861, 2020. doi: 10.1016/j.future.2019.07.019
[7]	H. Wu, S. Deng, W. Li, et al. “Request dispatching for minimizing service response time in edge cloud systems,” in Proceedings of 2018 27th International Conference on Computer Communication and Networks, Hangzhou, China, pp.1–9, 2018.
[8]	K. Kaur, T. Dhand, N. Kumar, et al., “Container-as-a-service at the edge: Trade-off between energy efficiency and service availability at fog nano data centers,” IEEE Wireless Communications, vol.24, no.3, pp.48–56, 2017. doi: 10.1109/MWC.2017.1600427
[9]	H. Ishibuchi, T. Yoshida, and T. Murata, “Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling,” IEEE Transactions on Evolutionary Computation, vol.7, no.2, pp.204–223, 2003. doi: 10.1109/TEVC.2003.810752
[10]	M. Dorigo, M. Birattari, and T. Stutzle, “Ant colony optimization,” IEEE Computational Intelligence Magazine, vol.1, no.4, pp.28–39, 2006. doi: 10.1109/MCI.2006.329691
[11]	M. Dai, D. Tang, A. Giret, et al., “Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm,” Robotics and Computer-Integrated Manufacturing, vol.29, no.5, pp.418–429, 2013. doi: 10.1016/j.rcim.2013.04.001
[12]	Z. H. Zhan, X. F. Liu, Y. J. Gong, et al., “Cloud computing resource scheduling and a survey of its evolutionary approaches,” ACM Computing Surveys (CSUR), vol.47, no.4, pp.1–33, 2015.
[13]	L. Yang, J. Cao, G. Liang, et al., “Cost aware service placement and load dispatching in mobile cloud systems,” IEEE Transactions on Computers, vol.65, no.5, pp.1440–1452, 2015.
[14]	L. Guo, S. Zhao, S. Shen, et al., “Task scheduling optimization in cloud computing based on heuristic algorithm,” Journal of Networks, vol.7, no.3, article no.547, 2012.
[15]	J. Wan, B. Chen, S. Wang, et al., “Fog computing for energy-aware load balancing and scheduling in smart factory,” IEEE Transactions on Industrial Informatics, vol.14, no.10, pp.4548–4556, 2018. doi: 10.1109/TII.2018.2818932
[16]	D. Zeng, L. Gu, S. Guo, et al., “Joint optimization of task scheduling and image placement in fog computing supported software-defined embedded system,” IEEE Transactions on Computers, vol.65, no.12, pp.3702–3712, 2016. doi: 10.1109/TC.2016.2536019
[17]	V. B. Souza, X. Masip-Bruin, E. Marín-Tordera, et al., “Towards distributed service allocation in fog-to-cloud (f2c) scenarios,” in Proceedings of 2016 IEEE Global Communications Conference, Washington, DC, USA, pp.1–6, 2016.
[18]	S. K. Mishra, D. Puthal, J. J. P. C. Rodrigues, et al., “Sustainable service allocation using a metaheuristic technique in a fog server for industrial applications,” IEEE Transactions on Industrial Informatics, vol.14, no.10, pp.4497–4506, 2018. doi: 10.1109/TII.2018.2791619
[19]	J. Liu, Y. Mao, J. Zhang, et al., “Delay-optimal computation task scheduling for mobile-edge computing systems,” in Proceedings of 2016 IEEE International Symposium on Information Theory, Barcelona, Spain, pp.1451–1455, 2016.
[20]	X. Li, J. Wan, H. N. Dai, et al., “A hybrid computing solution and resource scheduling strategy for edge computing in smart manufacturing,” IEEE Transactions on Industrial Informatics, vol.15, no.7, pp.4225–4234, 2019. doi: 10.1109/TII.2019.2899679
[21]	C. Li, J. Tang, H. Tang, et al., “Collaborative cache allocation and task scheduling for data-intensive applications in edge computing environment,” Future Generation Computer Systems, vol.95, pp.249–264, 2019. doi: 10.1016/j.future.2019.01.007
[22]	T. Wang, X. Wei, Y. Liang, et al., “Dynamic tasks scheduling based on weighted bi-graph in mobile cloud computing,” Sustainable Computing: Informatics and Systems, vol.19, pp.214–222, 2018. doi: 10.1016/j.suscom.2018.05.004
[23]	S. L. Zhang, C. Liu, Y. B. Han, et al., “DANCE: A service adaptation method for cloud-end dynamic integration,” Chinese Journal of Computers, vol.43, no.3, pp.423–439, 2020. (in Chinese)
[24]	C. Pahl, “Containerization and the paas cloud,” IEEE Cloud Computing, vol.2, no.3, pp.24–31, 2015. doi: 10.1109/MCC.2015.51
[25]	D. Bernstein, “Containers and cloud: From LXC to Docker to kubernetes,” IEEE Cloud Computing, vol.1, no.3, pp.81–84, 2014. doi: 10.1109/MCC.2014.51