Dynamic load balancing method based on optimal complete matching of weighted bipartite graph for simulation tasks in multi-energy system digital twin applications

• Published in: Energy reports 2022-04, Vol.8, p.1423-1431
• Main Authors: Tang, Xueyong, Ding, Yi, Lei, Jinyong, Yang, He, Song, Yankan
• Format: Article
• Language: English
• Subjects: Digital twin; Load balancing; Simulation computing task blocks; Weighted bipartite graph
• ISSN: 2352-4847; 2352-4847
• DOI: 10.1016/j.egyr.2021.11.145

As demands of renewable energy and more energy storages in power systems promote, the digital twin technology for multi-energy system draws attention from the researchers in power system and energy area. The load balancing algorithm of the digital twin server cluster significantly impacts the computing performance of the computing nodes. Optimal complete matching of a weighted bipartite graph is proposed to allocate computing task blocks to each computing node evenly. In the proposed algorithm, the computation times of simulation computing task blocks are estimated and the computation time of one single step in the task blocks are used as dynamic load indicators of the computing nodes. The indices are fed back to the scheduling server in real time. With the total steps of the simulation computing task blocks and the computation time of each single step for the task blocks, a fully weighted bipartite graph of computing nodes and simulation computing task blocks is constructed, greedy expansion of the Hungarian algorithm is used to optimize the complete matching of this weighted bipartite graph. Based on the optimization results, the task blocks are allocated to the computing nodes correspondingly in real time. Simulation-driven model parameter correction function, the representative simulation computing applications of digital twin for multi-energy system was used to test the proposed algorithm and the results show a significant improvement of the load balancing effect at the computing nodes.