Node Ordering in Power Flow Calculation Based on Graph Partitioning Algorithm

doi:10.11930/j.issn.1004-9649.2017.04.052.07

Abstract

Abstract: With the development of society, the topology of power grid is becoming more and more complex, and the dimension of power flow calculation is growing accordingly. Against this background, appropriate node ordering is needed to effectively accelerate the power flow calculation. As a scale-free network, the power system network can be abstracted into a graph to represent the topological relations between the various nodes. To solve the problem of node ordering, this paper presents a method based on dissection ordering algorithms to optimize node number, which can accelerate the speed of node ordering and power flow calculation of large scale system. Based on an example of IEEE 14-bus system, the process of the proposed method is described. The simulation results show that the speed and effectiveness of the proposed algorithm can satisfy online computing requirements.

Key words: node ordering, graph partitioning, power system calculation, nested dissection ordering algorithms

CLC Number:

TM744

TANG Can, GUO Rui, GU Liqiang, DONG Shufeng. Node Ordering in Power Flow Calculation Based on Graph Partitioning Algorithm[J]. Electric Power, 2017, 50(4): 52-58.

Add to citation manager EndNote|Ris|BibTeX

URL: https://www.electricpower.com.cn/EN/10.11930/j.issn.1004-9649.2017.04.052.07

https://www.electricpower.com.cn/EN/Y2017/V50/I4/52

References

[1] 史进,涂光瑜,罗毅. 电力系统复杂网络特性分析与模型改进[J]. 中国电机工程学报,2008,28（25）：93-98.
SHI Jin, TU Guangyu, LUO Yi. Complex network characteristic analysis and model improving of the power system[J]. Proceedings of the CSEE, 2008, 28(25): 93-98.
[2] 陈国章,向兵,姜炜超,等. 基于无标度网络的电力系统模型及优化[J]. 电测与仪表,2010,47（S1）：39-42.
CHEN Guozhang, XIANG Bing, JIANG Weichao, et al . A collaboration model of power system based on scale-free networks[J]. Electrical Measurement & Instrumentation, 2010, 47（S1）: 39-42.
[3] 王光增,曹一家,包哲静,等. 一种新型电力网络局域世界演化模型[J]. 物理学报,2009,58（6）：3597-3602.
WANG Guangzeng, CAO Yijia, BAO Zhejing, et al . A novel local-world evolving network model for power grid[J]. Acta Physica Sinica, 2009, 58(6): 3597-3602.
[4] 丁理杰,曹一家,刘美君. 复杂电力网络的连锁故障动态模型与分析[J]. 浙江大学学报（工学版）,2008,42（4）：641-646.
DING Lijie, CAO Yijia, LIU Meijun. Dynamic modeling and analysis on cascading failure of complex power grids[J]. Journal of Zhejiang University (Engineering Science), 2008, 42(4): 641-646.
[5] 颜伟,黄正波,余娟,等. 牛顿法潮流计算的高效综合稀疏技术[J]. 中国电力,2010,43（7）：19-23.
YAN Wei, HUANG Zhengbo, YU Juan, et al . Integrated sparse technique of Newton power flow calculation[J]. Electric Power, 2010,43(7): 19-23.
[6] ALSAC O, STOTT B, TINNEY W F. Sparsity-oriented compensation methods for modified network solutions[J]. IEEE Transactions on Power Apparatus and Systems, 1983, 102(5): 1050-1060.
[7] TINNEY W F. Citation classic-direct solutions of sparse network equations by optimally ordered triangular factorization[J]. Current Contents/Engineering Technology & Applied Sciences, 1979(18): 12.
[8] DAVIS T A, GILBERT J R, LARIMORE S I, et al . A column approximate minimum degree ordering algorithm[J]. ACM Transactions on Mathematical Software, 2004, 30(3): 353-376.
[9] GOMEZ-EXPOSITO A, FRANQUELO L G. An efficient ordering algorithm to improve sparse vector methods [J]. IEEE Transactions on Power Systems, 1988, 3(4): 1538-1544.
[10] BETANCOURT R. An efficient heuristic ordering algorithm for partial matrix refactorization[J]. IEEE Transactions on Power Systems, 1988, 3(3): 1181-1187.
[11] 彭春华,徐雪松. 基于蚁群算法的电力网络节点编号多方案优化[J]. 电力系统及其自动化学报,2007,19（2）：60-65.
PENG Chunhua, XU Xuesong. Electric power network node numbering multi-scheme optimization based on ant colony algorithm[J]. Proceedings of the CSU-EPSA, 2007, 19(2): 60-65.
[12] 罗军,于歆杰. 基于遗传算法的稀疏节点优化编号方法[J]. 电网技术,2006,30（22）：54-58.
LUO Jun, YU Xinjie. Sparsity node ordering technology based on genetic algorithms[J]. Power System Technology, 2006, 30(22): 54-58.
[13] 王立峰,武哲. 单亲遗传算法在有限元网格节点编号优化问题中的应用[J]. 科学技术与工程,2011,11（3）：456-460.
WANG Lifeng, WU Zhe. Optimal scheme of node labels in finite element mesh by partheno-genetic algorithm[J]. Science Technology and Engineering, 2011, 11(3): 456-460.
[14] 蔡中勤,郭志忠. 基于逆流编号法的辐射型配电网牛顿法潮流[J]. 中国电机工程学报,2000,20（6）：14-17.
CAI Zhongqin, GUO Zhizhong. Newton load flow for radial distribution network based on upstream labeling technique[J]. Proceedings of the CSEE, 2000, 20(6): 14-17.
[15] 蔡中勤,郭志忠,陈学允. 辐射状配电网的逆流编号法[J]. 电力系统自动化,1999,23（24）：16-19.
CAI Zhongqin, GUO Zhizhong, CHEN Xueyun. Upstream bus-labeling technique for radial distribution networks[J]. Automation of Electric Power Systems, 1999, 23(24): 16-19.
[16] LUO G X, SEMLYEN A. A efficient load flow for large weakly meshed networks [J]. IEEE Transactions on Power Systems, 1990, 5(4): 1309-1316.
[17] SHIRMOHAMMADI D, HONG H W, SEMLYEN A, et al . A compensation-based power flow method for weakly meshed distribution and transmission networks[J]. IEEE Transactions on Power Systems, 1988, 3(2): 753-762.
[18] ZHANG F, CHENG C S. A modified Newton method for radial distribution system power flow analysis[J]. IEEE Transactions on Power Systems, 1997, 12(1): 389-396.
[19] 杨启文,蒋静坪,张国宏. 遗传算法优化速度的改进[J]. 软件学报,2001,12（2）：270-275.
YANG Qiwen, JIANG Jingping, ZHANG Guohong. Improving optimization speed for genetic algorithms[J]. Journal of Software, 2001, 12(2): 270-275.
[20] 黄翰,郝志峰,吴春国,等. 蚁群算法的收敛速度分析[J]. 计算机学报,2007,30（8）：1344-1353.
HUANG Han, HAO Zhifeng, WU Chunguo, et al . The convergence speed of ant colony optimization[J]. Chinese Journal of Computers, 2007, 30(8): 1344-1353.
[21] 林济铿,王旭东,李胜文,等. 基于含连通图约束的背包问题的图分割方法[J]. 中国电机工程学报,2012,32（10）：134-141.
LIN Jikeng, WANG Xudong, LI Shengwen, et al . Graph partitioning method based on connected graph constrained knapsack problem [J]. Proceedings of the CSEE, 2012, 32(10): 134-141.
[22] 韩平,刘嘉超,周欢,等. 考虑节点类型的节点优化方法改进[J]. 电网与清洁能源,2010,26（11）：50-54.
HAN Ping, LIU Jiachao, ZHOU Huan, et al . Improvement of node optimizing with node type considered[J]. Power System and Clean Energy, 2010, 26(11): 50-54.