Application of Cross Link Table in Power System Flow Calculation

In the 2020 planning and design of Shanghai Electric Power Bureau, it is necessary to calculate various operation modes and grid structures. During the calculation process, it was found that if the usual compressed array storage method is used, a lot of modification work is required. Therefore, this paper proposes a cross-linked list method to store the network's topological structure and numerical information in a cross-linked list, making it independent of the calculation, which can ensure the reusability and flexibility of the data. This method is suitable for power system calculations that are closely related to topology. This paper briefly introduces the flow calculation.

1 Cross Link List

1.1 Introduction to Cross Linked List

The orthogonal linked list representation of sparse matrices uses multiple linked lists to store sparse matrices. Each non-zero element in the sparse matrix is ​​represented by a node. Generally, a node consists of five domains. As shown in Figure 1 (a), the row, column, and value domain represent the row number, column number, and value of a non-zero element, respectively. The down pointer (down) is used to link the node representing the next non-zero element in the same column, and the right pointer (right) is used to link the node representing the next non-zero element in the same row. In this way, a circular linked list is formed between the nodes representing the non-zero elements in each row, and a circular linked list is also formed between the nodes representing the non-zero elements in each column. At the same time, each row and column of the circular linked list has a header node to facilitate operations such as node insertion and deletion. The row number, column number, and value domain of the header node are useless. To save storage, these two groups of empty header nodes can be used together. The downward pointer of each header node links to the non-zero element node of the corresponding column, and the right pointer is used to link to the non-zero element node of the corresponding row. In addition, the numerical domain is used as a pointer to link each empty header node into a linked list. The entire table has a total empty header pointer, and the number of matrix rows m and columns n are marked where the general nodes are marked with row numbers and column numbers. There is a pointer (root) pointing to this total header node. Since the total header node links to the header nodes of each row and column, all non-zero elements of this matrix can be accessed step by step through this pointer to the total header node.

1.2 The formation of cross-linked lists in the trend

In the power flow calculation, considering the particularity of the power system, the cross-link table is partially simplified.

(1) Each linked list is a one-way linked list, and the non-zero elements in the linked list are sorted by their row numbers.

(2) For non-zero elements, their down pointers and row values ​​are omitted, and the list head node is omitted.

(3) The row header node omits its rows, columns and value range, and adds a diagonal element pointer to point to the matrix diagonal element. The total header node is the header of the row header node linked list.

If the position of the header node in the header node linked list is nCol, then the nodes in the non-zero element linked list of this row are all associated with the nCol-th node.

There are two non-zero element node pointers and a header node pointer in the header node. The first non-zero element node pointer mpRight points to the first non-zero element in the linked list of this row, and the second non-zero element node pointer mpCorner points to the non-zero element in the linked list of this row with the same row number as the corresponding row, that is, the diagonal element. The header node pointer points to the header node of the next row.

The node has three members. The pointer mpRight points to the next node associated with the header node of this row. Data contains the value or structure corresponding to this association. This contains the admittance, and mnCol is the node number of this non-zero element node.

2 Cross Link List Flow Method

2.1 Formation of the admittance matrix

In general power flow calculations, the admittance matrix must be formed in advance by opening a large enough array in the program. Although compressed storage technology is used, the disadvantages of static arrays cannot be overcome. The program cannot know exactly how much memory space is required, so it has to open a relatively large array. In this way, when the number of nodes is relatively small, the memory space is wasted; when the number of nodes is large, the program cannot handle it. The advantage of a cross linked list is that the memory required for all nodes is dynamically applied, including the header node (the number of which is determined by the number of nodes) and the non-zero element node (the number of which is determined by the number of branches).

In this matrix, the Data of the diagonal elements is the node self-admittance, and the Data of the non-diagonal elements is the mutual conductance between the node corresponding to the non-zero element and the node corresponding to its header node.

After reading in the number of nodes, the program initializes the linked list of the header node. The number of header nodes is one greater than the number of nodes. The linked list linked to the last header node stores the node's ground admittance. Subsequently, for each node read in, a diagonal element is inserted after the corresponding header node, and the diagonal element pointer points to it; for each branch read in, if it is a new branch, a non-zero element node corresponding to another node is inserted after the header node corresponding to each node of this branch, and then the mutual conductance of the two nodes is modified, otherwise the mutual conductance is modified directly. After all the mutual conductances are formed, the self-conductance of each node can be calculated. The method is to accumulate the Data values ​​of all non-zero elements in the linked list after this header node, and then multiply by -1. The node's ground admittance can include this part in the calculation. The root pointer points to the total header node, which is the first node in the linked list of header nodes.

This admittance matrix contains the topological structure of the grid and the values ​​related to it. This matrix is ​​basically unchanged in the program. The original data stored in this matrix is ​​relatively independent.

2.2 Formation of B1 and B2

In this paper, the PQ decomposition method is used for power flow calculation.

Matrix B1 is the matrix formed by removing the slack nodes from the original admittance matrix. All data of the B1 matrix are taken from the original admittance matrix, and the difference is the row number of the node. The row number of the node in the admittance matrix is ​​the node number of the original node, while the row number of the node in the B1 matrix is ​​the node number rearranged after removing the slack nodes in the admittance matrix. The program must record this correspondence between node numbers. Matrix B2 is the matrix formed by removing the slack nodes and PQ nodes from the original admittance matrix. Similarly, the program must also record the correspondence between the node number of the B2 matrix and the node number of the original admittance matrix. If the ground admittance of the node is considered, it is only necessary to access the linked list corresponding to the ground admittance in the header node linked list, and search by row number to obtain the corresponding ground admittance.

In the PQ decomposition method, the B1 and B2 matrices only need to be formed once each time. In fact, if the Newton method is used, the Jacobian matrix needs to be formed each time, and the relative independence of the admittance matrix becomes more advantageous.

The cross-linked list method stores the network topology and related values ​​together. Its storage structure provides the basis for separating the mathematical equation-solving method from the network analysis. The following steps are pure mathematical problems.

2.3 Optimal sorting and other problems

The principle of optimal sorting is consistent with that of other storage structures, but the processing method of injection elements is different. The compressed storage method of static arrays handles injection elements by reserving space at the end of each row. Its defect also lies in the setting of the size of the reserved space. In the cross-linked list method, the processing of injection elements is very convenient. If an injection element is generated during sorting, just insert a new node in each corresponding row. In this way, the processing of injection elements only needs to be considered during sorting, and does not need to be considered when forming a matrix or when analyzing the system.

After the B1 and B2 matrices are formed and sorted, the equation needs to be solved. This mainly involves the formation of the factor table and elimination and back-substitution. The LU decomposition method can be used to find the factor table. The principle is the same, just pay attention to the storage structure of the cross-linked list. After the factor table is formed and eliminated and back-substituted, the equation is solved.

Then, iterate repeatedly according to the process. When the power deviation is less than the convergence accuracy, the calculation can be ended.

3 Examples

According to the admittance matrix calculated by the IEEE14 node model (only part of it is listed, the real part of the admittance matrix is ​​omitted), the admittance to the ground of node No. 9 is not included in the original data.

As shown above, when the admittance matrix is ​​output, the diagonal elements are output first (accessing the diagonal element pointer can obtain it), and the subsequent data is output in the order of the cross linked list.

4 Conclusion

The usual array storage method belongs to a static data structure, and its type definition or variable description must be given in the description section of the program. Some programs use the malloc function or the new operator to dynamically apply for arrays, but the array is still an implementation of space reservation, which still has the disadvantages of static arrays. The cross linked list is a dynamic data structure, and its size can change during program execution. The number of nodes in the cross linked list grows dynamically during program execution, and the admittance matrix is ​​gradually formed as data is input. Using a cross linked list for storage can make storage allocation more flexible and make better use of memory.

Corresponding to node operations such as adding or deleting nodes and lines in the power system, the cross-linked list method is more convenient and faster to implement than the static array. The formation of the admittance matrix in the cross-linked list method itself is the result of the node insertion operation. For example, the method of adding a line is exactly the same as the method of adding a line when reading data.

The usual processing method is to store the topology structure and grid data separately in two arrays. Then use the other array as an index to access the topology structure and data. The cross-linked list storage method stores the grid topology structure and data together. Therefore, the system analysis method and mathematical processing method in the power flow calculation can be separated, and the processing of various data can be modularized.

If you encapsulate a cross linked list in C++, you can make the access to the cross linked list as convenient as accessing a two-dimensional array. The encapsulated cross linked list will have strong reusability. As a custom data type, it can make the program highly readable and easy to compile and maintain.