News Release

Determining maximum allowable current of an RBS using a directed graph model and greedy algorithm

Peer-Reviewed Publication

Beijing Institute of Technology Press Co., Ltd

Fig. 1. A diagram of the proposed method, which contains 4 main steps.

image: 

Fig. 1. A diagram of the proposed method, which contains 4 main steps.

view more 

Credit: Space: Science & Technology

The central principle of the proposed MAC determination method is to connect the batteries within an RBS in parallel to the maximum possible extent, thereby maximizing the output current. To achieve this universally and automatically, the overall process is divided into the 4 steps shown in Fig. 1. First, a directed graph model is established for the subsequent computations. The nodes in the directed graph correspond to the connection points of components in the actual RBS. The edges in the directed graph correspond to the batteries, switches, and external electrical loads in the actual RBS. Each edge is assigned 2 attributes, a voltage difference and a resistance, based on the equivalent method. The model not only contains the connected relationships between batteries and switches but also retains the performance parameters of the batteries. Second, based on the equivalent circuit model, the MAC calculation problem is transformed into specific objective functions and constraints. The topology in the directed graph model is represented in the form of a matrix A in which element akl equals 1 for edge l leaving node k, -1 for edge l entering node k, or 0 otherwise. The dimensions of matrix A are reduced according to specific regulations of akl. Matrix Xs determines whether switch Sj is closed. According to Kirchhoff ’s laws, the output current Io and the currents of each battery Ib are ultimately represented, and the equivalent admittance matrix Yn of the circuit is defined. The indicator η is defined by the ratio of Io to max(Ib). To this end, the problem of finding the MAC is formulated as: max η(Xs), s.t. max(Ib)≤Im. Third, the shortest paths (SPs) (where additional batteries and switches on the path are penalized for distance) of the batteries are obtained using the Dijkstra algorithm to connect the batteries in the RBS in parallel. The distance ω of path p is ω(p) = Nsnb(p) + ns(p) and the shortest path SPi for battery Bi is SPi = arg min ω(p). Fourth, a greedy algorithm is used to organize the switches, allowing the batteries to connect via their SPs while satisfying the constraints, resulting in the MAC of the RBS.

 

Fig. 1. A diagram of the proposed method, which contains 4 main steps.

 

Then, the proposed method is applied to determine the MACs of 2 published RBS structures and a new one with a more complex structure, as shown in Fig. 5 (a) to (c) respectively. The following RBS systems are investigated and compared. (a) 3 different structures with the same 4 batteries. After obtaining the SPs, the MACs of the 3 RBS structures with 4 batteries are calculated using the proposed greedy algorithm. To verify and compare the proposed greedy algorithm, we also used the brute-force algorithm, which iterates through all possible switch states, and the heuristic algorithms (SA and GA) to calculate the MACs of the same RBSs. The final results of the brute-force algorithm are the same as those of the greedy algorithm. (b) the same structure as in Fig. 5C with 2/4/6 batteries. In this case, the proposed greedy algorithm still converges the fastest and achieves the correct MAC. The SA algorithm fails to obtain the correct MAC within the given number of iteration steps in the case of the 6-battery RBS structure. (c) the 4-battery structure in Fig. 5C with random isolated batteries. There are 4 possible scenarios for isolated batteries: (1) a single unhealthy battery, (2) 2 unhealthy batteries located in different substructures, (3) 2 unhealthy batteries located in the same substructure, and (4) 3 unhealthy batteries. The resulting MAC (η) values for these 4 scenarios are 2, 2, 1, and 1, respectively.

 

Fig. 5. Calculation results about the SPs in different 4-battery RBS structures.

 

Finally, the calculation results, computational complexity of the algorithm, and scenarios such as battery random isolation are also discussed sequentially. The correctness of the outcomes provided by the proposed greedy algorithm will now be discussed from 2 perspectives: circuit analysis and validation against the brute-force algorithm. On the one hand, adding more batteries to the main circuit only creates a series structure and does not improve the MAC, thus the switch-control scheme provided by the proposed greedy algorithm maximizes the RBS output current. On the other hand, the brute-force method yields the same η, indicating that the proposed greedy algorithm successfully identifies the MAC among all the potential reconfigured structures. The proposed greedy algorithm possesses a significant advantage in terms of its effectiveness and efficiency. As depicted in Fig. 7A to C, the brute-force algorithm comes at a high computational cost while ensuring the correctness of the results by exploring all possible switch states. The SA and GA algorithms require more iterations to converge to the final solution than the proposed greedy algorithm. Furthermore, this approach can handle RBSs with arbitrary structures, which is another significant advantage. Most of the existing RBS structures have simple topological characteristics, so calculating their MACs is relatively straightforward or even intuitive. However, these simple structures do not always fully satisfy the requirements of complex applications, such as dynamically adapting the circuit to variable and random operating conditions or actively equalizing differences between batteries in the RBS. Moreover, isolating the batteries disrupts the original regularity and symmetry of the topology, which complicates the otherwise simple structure, and the maximum output current of the system becomes more challenging to obtain. In contrast, the proposed method calculates the MAC of arbitrary RBS structures, most notably complex and flexible RBS structures.

 

Fig. 7. Temporal evolution of objective values in the iteration process for calculating RBS structures. (A) Evolution for the structure shown in Fig. 5A. (B) Evolution for the structure shown in Fig. 5B. (C) Evolution for the structure shown in Fig. 5C.


Disclaimer: AAAS and EurekAlert! are not responsible for the accuracy of news releases posted to EurekAlert! by contributing institutions or for the use of any information through the EurekAlert system.