Turn off MathJax
Article Contents
SHAO Sisi, LIU Shangdong, LI Kui, YOU Shuai, QIU Huajie, YAO Xiaoliang, JI Yimu. LBA-ECA Load Balancing Algorithm Based on Weighted Bipartite Graph for Edge Computing[J]. Chinese Journal of Electronics. doi: 10.1049/cje.2021.00.289
Citation: SHAO Sisi, LIU Shangdong, LI Kui, YOU Shuai, QIU Huajie, YAO Xiaoliang, JI Yimu. LBA-ECA Load Balancing Algorithm Based on Weighted Bipartite Graph for Edge Computing[J]. Chinese Journal of Electronics. doi: 10.1049/cje.2021.00.289

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

doi: 10.1049/cje.2021.00.289
Funds:  This work is 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 (No. 2019K024), Six talent peak projects in Jiangsu Province (JY02), Postgraduate Research and Practice Innovation Program of Jiangsu Province (KYCX19 0921, KYCX19 0906), Zhejiang Lab (2021KF0AB05), NUPT DingShan Scholar Project and NUPTSF (NY219132)
More Information
  • Author Bio:

    was born in 1997. She is a PhD. 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)

    was born in 1979. He received PhD. 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)

    was born in 1988. He is a PhD. 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)

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

    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)

    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)

    (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
  • 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.
  • loading
  • [1]
    H. Wang, J. Gong, Y. Zhuang, et al., “Task scheduling for edge computing with health emergency and human behavior consideration in smart homes,” 2017 IEEE International Conference on Big Data, 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. Mu?o, “An edge computing architecture in the Internet of Things,” 2018 IEEE 21st International Symposium on Real-Time Distributed Computing, 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 and 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,” 2018 27th International Conference on Computer Communication and Networks, 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,” 2016 IEEE Global Communications Conference, 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,” 2016 IEEE International Symposium on Information Theory, 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, Chinese Journal of Computers, vol.43, no.03, 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
  • 加载中

Catalog

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

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

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

    Figures(4)  / Tables(5)

    Article Metrics

    Article views (154) PDF downloads(15) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return